2

ステートメントが定義されている文法を考慮して、ステートメントのあいまいさを検出することになっている宿題があります。

例:

Grammar: S -> S + S | S * S | id
Statement: id * id + id

2 つの解析ツリーが可能であるため、上記のステートメントはあいまいです。

私は今のところ、次の曖昧さを念頭に置いています。

1) 演算子の優先順位 (上記の例)
2) If-else ぶら下がりケース
3) 無限ループ (上記の例は左再帰)
4) 結合性

どれが実行可能か、さらに教えていただけますか?

lex と bison (yacc) を使用してこのパーサーを設計し、2 日以内に提出する必要があるため、文法とステートメントのあいまいさについてポインタがあれば役立ちます。

4

2 に答える 2

1

さて、あなたがあなたの命令でlexとbisonを持っているなら、あなたは単に文法をbisonに与えることができ、それはそれが曖昧であるかどうかを教えてくれます。

それ以外の場合は、文法をあいまいにする競合があるかどうかを判断するために、LALR1パーサジェネレータアルゴリズム全体を構築する必要があります。これらの競合は、パーサー構築段階のかなり遅い段階で検出されます(私のパーサージェネレーターは、テーブル生成ステップで競合を検出します)。おそらく、私のコードがどのようにそれを行うかからいくつかの指針を得ることができます、それはhttps://github.com/Dervall/Pigletにあります

ボトムアップパーサーでのshift/reduceおよびreduce/reduceの古典的なケースは、配置しようとしているトークンと同じ優先順位を持つエントリで既に入力されているアクションテーブルの一部を入力しようとしたときに発生します。初期化。

LLパーサーについて話している場合、無限ループは実際にはあいまいな文法の場合ではありません。文法はあいまいでないようにリファクタリングできます。

また、ステートメント自体は、文法があいまいであるかどうかにはまったく影響しません。与えられた入力に関係なく、あいまいでした。

于 2012-04-18T14:01:30.140 に答える
1

一般的にはできません-文法のあいまいさは決定不可能です。

とはいえ、明らかにあいまいな、認識できる文法パターンがいくつかあります。

  • 左再帰と右再帰の両方である(役に立たない)非終端記号はあいまいです(他のぶら下がりを除いて、上記のすべてのケースをカバーします)。
  • 一方が他方の接頭辞である2つの右再帰規則を持つ(役に立たない)非終端記号はあいまいです(dangling-elseをカバーします)。
于 2012-04-18T17:48:01.753 に答える