L'algorithme de Vaughan-Pratt
Cet article expose l'algorithme de Vaughan-Pratt, présenté pour la première fois en 1973. Dans le cadre restreint de l'analyse syntaxique d'expressions arithmétiques[1], l'algorithme de Vaughan-Pratt offre une alternative intéressante à la descente récursive. Il peut même être jumelé à celle-ci pour bâtir des analyseurs syntaxiques complets.
Descente récursive
Les analyseurs syntaxiques par descente récursive sont généralement reconnus pour leur simplicité et leur flexibilité. En substance, leur structure interne reproduit la structure de la grammaire cible à travers une série de fonctions mutuellement récursives, généralement une par production.
Pour illustrer cette technique, considérons un analyseur syntaxique d'expressions arithmétiques dont la grammaire est composée des quatre productions ci-dessous.
<expression> ::= <term> { ('+'|'-') <term>}
<term> ::= <factor> { ('*'|'/') <factor>}
<factor> ::= ('+'|'-') <factor> | <power>
<power> ::= <number> { '^' <factor> }
Chacun des symboles terminaux de la grammaire sera représenté par une classe. Les instances de ces classes constitueront les nœuds de l'arbre syntaxique.
class token:
'''base class for all token'''
def __repr__(self):
return str(self.value)
class binop(token):
'''base class for all binary oparator'''
first = None
second = None
def __str__(self):
name = self.__class__.__name__.replace('op', '')
return '(%s %s %s)' % (name, self.first, self.second)
class addop(binop):
'''addition operator'''
value = '+'
class minop(binop):
'''substraction operator'''
value = '-'
class mulop(binop):
'''multiplication operator'''
value = '*'
class divop(binop):
'''division operator'''
value = '/'
class powop(binop):
'''power operator'''
value = '^'
class number(token):
'''wrapper around number'''
def __init__(self, value):
self.value = int(value)
def __str__(self):
return '(num %s)' % (str(self.value))
class endtok(token):
'''special token type, marking the end of tokens'''
value = 'eop'
Étant donnée la simplicité de la grammaire, à partir d'une chaîne de caractères contenant une expression arithmétique, l'analyseur lexical (une simple fonction dans le cas présent) instanciera directement les objets qui constitueront les nœuds de l'arbre syntaxique. Si la grammaire était plus complexe, une telle approche serait évidemment inapplicable.
class TokenizeError(Exception):
def __init__(self, unexpected, pos):
self.unexpected = unexpected
self.pos = pos
def __str__(self):
return "unexpected char '%s' at pos %s" % \
(str(self.unexpected), str(self.pos))
def tokenize(s):
'''tokenize(string) -> list of tokens'''
result = []
pos = 0
while pos < len(s):
c = s[pos]
if c.isspace():
pass
elif c == '+':
result.append(addop())
elif c == '-':
result.append(minop())
elif c == '*':
result.append(mulop())
elif c == '/':
result.append(divop())
elif c == '^':
result.append(powop())
elif c.isdigit():
num = c
pos += 1
while pos < len(s):
c = s[pos]
if c.isdigit():
num += c
pos += 1
else:
break
if pos < len(s) and s[pos].isalpha():
raise TokenizeError(s[pos], pos + 1)
pos -= 1
result.append(number(num))
else:
raise TokenizeError(c, pos + 1)
pos += 1
result.append(endtok())
return result
>>> tokenize('1+2*4^2-6/3')
[1, +, 2, *, 4, ^, 2, -, 6, /, 3, eop]
>>> tokenize(' 6-\t4* 5')
[6, -, 4, *, 5, eop]
Voici maintenant le cœur de l'analyseur syntaxique par descente récursive: les fonctions expression, term, factor et power. Chacune encode les règles associées aux productions correspondantes de la grammaire définie précédemment.
tokens = [] # token buffer
token = None # current token
class ParseError(Exception):
def __init__(self, want, got):
self.want = want
self.got = got
def __str__(self):
return 'expected %s but got %s' % \
(str(self.want), str(self.got))
def next():
'''put the next token into token global variable'''
global token, tokens
try:
old = token
token = tokens.pop(0)
return old
except IndexError:
raise ParseError('more token', 'nothing !')
def parse(s):
'''parse and eval s, an expression string'''
global tokens
tokens = tokenize(s)
print('Token:', tokens)
next()
return expression()
def expression():
'''<term> [('+'|'-') <term>]*'''
global token
exp = term()
while isinstance(token, minop) or \
isinstance(token, addop):
lhs = exp # save lhs
exp = next() # set op as root
exp.first = lhs # set op lhs
exp.second = term() # set op rhs
# check to see if we've missed some tokens
if not isinstance(token, endtok):
raise ParseError('eop', token.value)
return exp
def term():
'''<factor> [('*'|'/') <factor>]*'''
global token
exp = factor()
while isinstance(token, mulop) or \
isinstance(token, divop):
lhs = exp # save lhs
exp = next() # set op as root
exp.first = lhs # set op lhs
exp.second = factor() # set rhs
return exp
def factor():
'''('+'|'-') <factor> | <power>'''
global token
if isinstance(token, addop):
next() # don't put unary plus
return factor() # in the parse tree
elif isinstance(token, minop):
unary = next() # set root
unary.first = factor() # set lhs
return unary
return power()
def power():
'''<number> [ '^' <factor> ]'''
global token
if not isinstance(token, number):
raise ParseError('number', token.value)
exp = next() # eat number
if isinstance(token, powop):
lhs = exp # save lhs
exp = next() # set root
exp.first = lhs # set lhs
exp.second = factor() # set rhs
return exp
Tel que mentionné précédemment, la principale qualité de l'analyse par descente récursive réside dans sa simplicité. Par contre, beaucoup d'appels de fonction sont générés inutilement pour analyser chaque symbole. En ne considérant que les méthodes term, factor et power, on constate que 3 appels sont nécessaires pour analyser chaque nombre de l'expression arithmétique. Pour s'en convaincre il suffit d'étudier la trace obtenue lors de l'analyse de l'expression 1+2-3.
expression(<>)
term(<>)
factor(<>)
power(<>)
return <<num 1>>
return <<num 1>>
return <<num 1>>
term(<>)
factor(<>)
power(<>)
return <<num 2>>
return <<num 2>>
return <<num 2>>
term(<>)
factor(<>)
power(<>)
return <<num 3>>
return <<num 3>>
return <<num 3>>
return <<min <add <num 1> <num 2>> <num 3>>>
Avec une grammaire d'expressions comprenant davantage de productions, la quantité d'appels serait d'autant plus élevée. Rien de bien dramatique de nos jours, mais tout de même quelque chose d'un peu dérangeant.
De plus, il y une certaine verbosité associée à l'analyse par descente récursive. Devoir coder une méthode par production n'est certainement pas une situation optimale, surtout lorsque chacune d'elles présente de si fortes similitudes.
C'est alors qu'entre en scène l'algorithme de Vaughan-Pratt.
L'algorithme de Vaughan-Pratt
Présenté pour la première fois dans le cadre du Principles of Programming Languages Symposium de 1973, l'algorithme de Vaughan-Pratt est un judicieux mélange entre l'algorithme shunting-yard et l'analyse syntaxique par descente récursive. Comme Pratt le dit lui-même dans l'introduction de son article de 1973, Top Down Operator Precedance, la technique est simple à comprendre, triviale à implanter, simple à utiliser et efficace en pratique sinon en théorie.
Pour bien saisir l'élégance de la méthode, il suffit de remarquer que le travail d'un analyseur syntaxique se résume pour l'essentiel à résoudre des problèmes de préséance. C'est-à-dire que pour un opérande donné, nous devons être en mesure de déterminer à quel opérateur se dernier est associé.
Dans le cas de l'analyse par descente récursive, la préséance des opérateurs était exprimée à même la grammaire. Pour sa part, la technique de Pratt associe à chaque token un niveau de préséance (binding power), d'où le lien avec l'algorithme shunting-yard, et deux méthodes: nud (null denotation) et led (left denotation). Sans surprise, plus le niveau de préséance d'un opérateur est grand, plus la préséance de l'opérateur est grande. Par exemple, l'opérateur de multiplication aura un niveau de préséance supérieur à l'opérateur d'addition. Toute l'information nécessaire à l'analyse d'un token lui est donc directement associée (dans notre cas, sous la forme de méthodes et d'attributs) plutôt que d'être encodée au sein d'une grammaire.
Considérant une liste de tokens, l'analyse syntaxique consiste alors à exécuter le code associé à chaque token de gauche à droite en appelant, selon le cas,
- la méthode nud lorsque le token n'est pas précédé par une expression,
- la méthode led avec comme argument l'arbre syntaxique à gauche de l'opérateur lorsque le token est précédé par une expression.
La fonction expression se charge d'effectuer ce travail (elle remplace les fonctions expression, term, factor et power de l'implantation par descente récursive).
def expression(rbp=0):
global token
t = token
next()
left = t.nud()
while rbp < token.bp:
t = token
next()
left = t.led(left)
return left
Dans son article, Pratt décrit le fonctionnement de la méthode expression à l'aide de ce diagramme d'états:
Finalement, voici comment les classes représentant les tokens de l'implantation précédente ont été modifiées pour être utilisées avec l'algorithme de Vaughan-Pratt.
class token():
'''base class for all token'''
bp = 0 # bp default to 0
def nud(self):
raise Exception('nud is not implemented on %s' %s\
(self.__class__.__name__))
def led(self, left):
raise Exception('led is not implemented on %s' %s\
(self.__class__.__name__))
def __repr__(self):
return str(self.value)
class binop(token):
'''base class for all binary oparator'''
first = None
second = None
def __str__(self):
name = self.__class__.__name__.replace('op', '')
return '(%s %s %s)' % (name, self.first, self.second)
class prefix(binop):
'''
Default implementation of the nud method,
should be inherited by prefix operators.
'''
def nud(self):
self.first = expression(70)
return self
class infix(binop):
'''
Default implementation of the led method,
should be inherited by infix operators.
'''
def led(self, left):
self.first = left
self.second = expression(self.bp)
return self
class infixr(binop):
'''
Default implementation of the led method,
should be inherited by infixr operators.
'''
def led(self, left):
self.first = left
self.second = expression(self.bp-1)
return self
class addop(infix):
'''addition operator'''
value = '+'
bp = 50
class minop(infix, prefix):
'''substraction operator'''
value = '-'
bp = 50
def __str__(self):
if self.second is None:
return '(min %s)' % (self.first)
return '(min %s %s)' % (self.first, self.second)
class mulop(infix):
'''multiplication operator'''
value = '*'
bp = 60
class divop(infix):
'''division operator'''
value = '/'
bp = 60
class powop(infixr):
'''power operator'''
value = '^'
bp = 70
class number(token):
'''wrapper around number'''
def __init__(self, value):
self.value = int(value)
def nud(self):
return self
def __str__(self):
return '(num %s)' % (str(self.value))
class endtok(token):
'''mark the end of tokens'''
value = 'eop'
Hormis les méthodes nud et led et le binding power ajoutés à chaque token, trois classes additionnelles sont ajoutées:
- infix fournit une implantation de base de la méthode led pour les opérateurs en notation infixée associant à gauche,
- infixr fournit une implantation de base de la méthode led pour les opérateurs en notation infixée associant à droite,
- prefix fournit une implantation de base de la méthode nud pour les opérateurs utilisés en notation préfixée.
Quelques remarques éparses sur l'algorithme de Pratt.
- Le binding power de l'opérateur de gauche est toujours passé en argument à expression, 0 lors de l'appel initial. C'est la valeur de ce binding power qui détermine à quel moment la boucle de la méthode expression est arrêtée.
- Lors des appels à expression, token doit contenir un opérande qui sera initialement placé dans la variable left, puis mis à jour au fil des appels effectués sur t.led(left).
- Pour chacun des appels à expression, c'est au moins 2 tokens qui sont consommés: un opérande et un opérateur.
- Les méthodes nud et led devraient toujours retourner en laissant dans la variable token un opérateur.
- Expression retourne toujours en laissant dans la variable token un opérateur, ou un marqueur de fin de programme (eop) le cas échéant.
Pour mieux comprendre le fonctionnement de l'algorithme de Vaughan-Pratt, le plus simple est sans doute d'en étudier quelques traces.
Par exemple, pour l'expression 1+2-3, voici la trace obtenue:
expression(0)
{1}.nud()
return <num 1>
{+}.led(<num 1>)
expression(50)
{2}.nud()
return <num 2>
return <num 2>
return <add <num 1> <num 2>>
{-}.led(<add <num 1> <num 2>>)
expression(50)
{3}.nud()
return <num 3>
return <num 3>
return <min <add <num 1> <num 2>> <num 3>>
return <min <add <num 1> <num 2>> <num 3>>
L'expression <min <add <num 1> <num 2>> <num 3>> correspond à l'arbre syntaxique de la figure suivante.
De même, pour l'expression 2+3*4-5, voici la trace obtenue:
expression(0)
{2}.nud()
return <num 2>
{+}.led(<num 2>)
expression(50)
{3}.nud()
return <num 3>
{*}.led(<num 3>)
expression(60)
{4}.nud()
return <num 4>
return <num 4>
return <mul <num 3> <num 4>>
return <mul <num 3> <num 4>>
return <add <num 2> <mul <num 3> <num 4>>>
{-}.led(<add <num 2> <mul <num 3> <num 4>>>)
expression(50)
{5}.nud()
return <num 5>
return <num 5>
return <min <add <num 2> <mul <num 3> <num 4>>> <num 5>>
return <min <add <num 2> <mul <num 3> <num 4>>> <num 5>>
Dans ce cas, l'expression <min <add <num 2> <mul <num 3> <num 4>>> <num 5>> correspond à l'arbre syntaxique ci-dessous.
Conclusion
L'algorithme de Vaughan-Pratt est un outil puissant pour effectuer l'analyse syntaxique d'expressions arithmétiques, mais il peut également être utilisé pour effectuer l'analyse syntaxique de langages de programmation fonctionnels tels Lisp et Scheme, voire même JavaScript. Jumelé à une descente récursive, il est possible de l'intégrer avantageusement au sein d'un analyseur syntaxique dont la porté est beaucoup plus grande.