Prett Parsing-式を解析するためのWogan Prattの方法

コンパイルと式の​​計算の対象。



1973年に、ヴォーン・プラットは、オートマトンも文法も使用しない式を解析するための簡単で効果的な方法を提案しました。



アイデアは、各トークンにプロパティが与えられるということです:

lbp =左側のシンボルバインディングの優先順位、

nud =式の先頭に演算子を適用した結果を決定する関数、

led =式の途中でアプリケーションの結果を決定する関数。



主な分析は、スキームに従って実行されます。

解析(継続優先):
    入力ストリームから文字をプッシュします
    結果=このキャラクターのヌードコール
    一方、ストリーム文字の次のlbp優先度>継続の優先度:
        入力ストリームから文字をプッシュします
         result =このシンボルのledを現在の結果に適用する


定数と変数のバインディング優先度は0であり、nud関数はそれらの値(または参照)を返します。 したがって、定数に解析を適用すると、その値がすぐに返されます。

二項演算子の場合、led関数は再帰的に解析を継続して(右)優先度を下げ、結果を既に蓄積(左)して再帰的に取得した結果を処理します。

オペレーターを適用した結果は、外部呼び出しのために集約されます。

多項演算子-解析関数への追加の呼び出しによって引数を受け取ります。

プレフィックス演算子は、それらに対してnud関数を定義することにより行われます。

右手バインディングの場合、再帰的解析の継続の優先順位が変更されます。



Effbot.orgは詳細なPython実装を提供します。

JavaScriptとスキーマのリンクがあります。



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







All Articles