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 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:

Quelques remarques éparses sur l'algorithme de Pratt.

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.

  1. En fait, la technique est applicable à tout type d'expression. Mais pour les fins de l'exercice, nous concentrerons notre attention sur les expressions arithmétiques exclusivement.