Prett Parsing — метод Вогана Пратта для разбора выражений

В тему компиляций и вычислений выражений.

В далёком 1973 году Воган Прэтт (Vaughan Pratt) предложил простой и эффективный метод разбора выражений, не использующий ни автоматы, ни грамматику как таковую.

Идея заключается в том, что каждый символ (token) наделяется свойствами:
lbp = приоритет связывания символа слева,
nud = функция, определяющая результат применения оператора в начале выражения,
led = функция, определяющая результат применения в середине выражения.

Основной разбор осуществляется по схеме:

разбор(приоритет продолжения):
    вытолкнуть символ из входного потока
    результат = вызов nud этого символа
    пока приоритет lbp следующего в потоке символа > приоритета продолжения:
        вытолкнуть символ из входного потока
        результат = применени led этого символа к текущему результату

Константы и переменные имеют приоритет связывания 0, а функция nud возвращает их значение (или ссылку). Поэтому применение разбора к константам сразу возратит их значение.
Для бинарных операторов функция led рекурсивно вызывает продолжение разбора (справа) вплоть до более низкого приоритета, и делает что-нибудь с уже накопленым (слева) результатом, и полученным рекурсивно.
Результат применения оператора аггрегируется для внешнего вызова.
Много-арные операторы — получают аргументы дополнительным вызовом функции разбора.
Префиксные операторы делаются с помощью определения для них функции nud.
Для правостороннего связывания меняется приоритет продолжения рекурсивного разбора.

На сайте effbot.org приводится подробная реализация на питоне.
Там же есть ссылки для жаваскрипта и схемы.

operators = { # приоритеты и функции led
    '+': [1, lambda left: "(%s + %s)" % (left, parse(1))],
    '*': [2, lambda left: "(%s * %s)" % (left, parse(2))],
    '^': [3, lambda left: "(%s ^ %s)" % (left, parse(3))],
    '$': [0]
    }

def lbp(t):
    try:
        return operators[t][0]
    except KeyError:
        return 0
    
def nud(t):
    return t

def led(t,left):
    return operators[t][1](left)

# можно соорудить класс для каждого оператора, но это очень больше строчек получится.

def parse(rbp=0):
    global tokens
    tok = tokens.pop(0)
    result = nud(tok)
    while lbp(tokens[0]) > rbp:
        tok = tokens.pop(0)
        result = led(tok,result)
    return result

def evaluate(expr):
    global tokens
    tokens = expr.split(" ") + ['$']
    parse()

Примеры работы:
>>> evaluate("a + b * c ^ d * e + f")
   a|+,b,*,c,^,d,*,e,+,f,$
 = a
   +|b,*,c,^,d,*,e,+,f,$
     b|*,c,^,d,*,e,+,f,$
   = b
     *|c,^,d,*,e,+,f,$
       c|^,d,*,e,+,f,$
     = c
       ^|d,*,e,+,f,$
         d|*,e,+,f,$
       = d
     = (c ^ d)
   = (b * (c ^ d))
     *|e,+,f,$
       e|+,f,$
     = e
   = ((b * (c ^ d)) * e)
 = (a + ((b * (c ^ d)) * e))
   +|f,$
     f|$
   = f
 = ((a + ((b * (c ^ d)) * e)) + f)
>>>
>>> evaluate("a * b + c ^ d + e * f")
   a|*,b,+,c,^,d,+,e,*,f,$
 = a
   *|b,+,c,^,d,+,e,*,f,$
     b|+,c,^,d,+,e,*,f,$
   = b
 = (a * b)
   +|c,^,d,+,e,*,f,$
     c|^,d,+,e,*,f,$
   = c
     ^|d,+,e,*,f,$
       d|+,e,*,f,$
     = d
   = (c ^ d)
 = ((a * b) + (c ^ d))
   +|e,*,f,$
     e|*,f,$
   = e
     *|f,$
       f|$
     = f
   = (e * f)
 = (((a * b) + (c ^ d)) + (e * f))