3

注: これは、プレフィックス式の欠落を解析する再帰的降下の優先順位のより詳細なバージョンです。

私は単純な言語パーサーを構築していますが、優先順位の低いプレフィックス式に問題があります。文法の例を次に示します。

E = E8
E8 = E7 'OR' E8 | E7
E7 = E6 'XOR' E7 | E6
E6 = E5 'AND' E6 | E5
E5 = 'NOT' E5 | E4
E4 = E3 '==' E4 | E3 '!=' E4 | E3
E3 = E2 '<' E3 | E2 '>' E3 | E2
E2 = E1 '+' E2 | E1 '-' E2 | E1 '*' E2 | E1 '+' E2 | E1
E1 = '(' E ')' | 'true' | 'false' | '0'..'9'

ただし、この文法は、より優先順位の高い中置演算子の RHS として使用される場合、NOT に対しては正しく機能しません。つまり、次のようになります。

true == NOT false

これは、RHS で必要な == 演算子が原因でありE3、これは「NOT」操作ではありません。

この文法を表現する正しい方法がわかりませんか? この単純化された再帰的降下アプローチを使用してまだ可能ですか、それともより機能的なアルゴリズム (ヤードの迂回または先行登攀) に移行する必要がありますか?

正しく解析する必要があるいくつかの例を次に示します。

  • 入力true == 1 < 2、出力==(true, <(1, 2))
  • 入力1 < 2 == true、出力==(<(1, 2), true)
  • 入力NOT true == false、出力NOT(==(true, false))
  • 入力true == NOT false、出力==(true, NOT(false))** が機能しない
  • 入力true < NOT false、出力<(true, NOT(false))** が機能しない

Recursive Descent precedence parsing missing prefix expression (ie , , etc)で提案されているように、中置式の RHS で使用するレベルE4、E3、およびを変更しようとしました。ただし、これはこれらのレベル間の優先順位を壊します。つまり、誤って<(==(true, 1), 2)` になります。E2E5E3 '==' E5E3 '<' E5true == 1 < 2parsed as

4

1 に答える 1

0

あなたの言語が定義されている方法に固執するとき、あなたは持つことができません

true == NOT false

あなたの言語で有効な用語として。その時だから

NOT false == true

あいまいです: 解析ツリーは次のいずれかになります。

    NOT
     | 
    ==
   /  \
false true

また

   ==
  /  \
 NOT true
  |
false

ご了承ください

true == NOT (false)

はあなたの言語で有効な用語です。あなたの言語のおそらくより直感的な定義は、NOTレベルを から にE5下げることE2です。それで

true == NOT false 
NOT false == true

は両方とも有効であり、 とNOTバインドしfalseます。そして、2 番目の式の別の意味は次のように表されます。

NOT (false == true)

これらのオプションで満足できない場合は、ツールを変更/拡張する必要があります。たとえば、yacc/bison パーサーを使用すると、演算子の優先順位を明示的に定義できます。たとえば、ここを参照してください

于 2014-06-21T21:08:54.500 に答える