12:05 PM

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

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

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

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

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

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

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

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

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))[/cc]

за статью спасибо qmax

0 Comments