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

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

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

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

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

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

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
</code>



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]) &gt; 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))
за статью спасибо qmax
Социальные закладки: