1

バイナリの合計/積の解析は簡単ですが、解析する文法を定義するのに問題があります

a + b * c + d + e

なので

sum(a, prod(b, c), d, e)

私の最初の（ナイーブな）試みは、61シフト/競合の削減を生み出しました。

私はJavaカップを使用しています（ただし、他のパーサージェネレーターのソリューションは簡単に変換できると思います）。

4

1 に答える 1

3

次のANTLR文法：

parse
  :  exp EOF
  ;

exp
  :  add_exp
  ;

add_exp
  :  mul_exp ('+' mul_exp)* 
  ;

mul_exp
  :  atom ('*' atom)* 
  ;

atom
  :  Number
  |  '(' exp ')'
  ;

Number
  :  'a'..'z'
  ;

a + b * c + d + e入力を次のように解析します。

代替テキストhttp://img266.imageshack.us/img266/7099/17212574.png

ご覧のとおり、mul_expはツリー内で最も遠くにあり、（ツリー内を適切に「ウォーク」して）最初に評価されます。

入力a + b * (c + d) + eは次のように解析されます。

代替テキストhttp://img688.imageshack.us/img688/2207/89332200.png

画像はANTLRWorksで生成されました。

編集：

ANTLRWorksのようなツールを使用すると、文法のデバッグが簡単になります。たとえば、atom上の文法のルールをクリックすると、次のものが自動的に生成され、画面の下部に表示されます。

代替テキストhttp://img340.imageshack.us/img340/6793/53395907.png

もちろん、そのルールはまったく複雑ではありませんが、より複雑なルールを使用するようになると、そのように視覚化するのは非常に簡単です。

HTH。

于 2010-05-03T11:41:21.203 に答える