5

主に解析の詳細に関連する、LALR(1) パーサーの競合に関するいくつかの質問:

  1. 教科書に記載されているさまざまな LALR(1) パーサーによると、シフト/リデュースの競合が発生した場合、そもそも文法が LALR(1) ではないという兆候ですよね?

  2. LR(1) から LALR(1) への状態のマージが行われるため、有効なLALR(1) 文法でReduce/Reduce の競合が発生する可能性がありますよね?

  3. YACC と GNU Bison で使用されている優先順位と結合性は、シフト/競合の削減を支援するために導入されたツールですよね?

  4. さらに、競合するシフト/リデュース ルールの優先順位が先読みシンボルの優先順位と等しい場合にのみ、パーサーが結合性をチェックする必要があります。それ以外の場合、結合性は無関係ですよね?

私は 100% 確信が持てないので質問しています。本は競合解決についてあまり詳しく説明していません。この件に関して私が見つけた数行は GNU Bison マニュアルにあるだけです。

上記の Bison マニュアル リンクに関する質問:

  • 競合ルールや先読みトークンに優先順位がなければ、選択肢は SHIFT だと主張するのはなぜですか? リダクション ルールに優先順位がある場合、優先順位がまったくない先読みよりも優先されると思います。
4

1 に答える 1

5

  1. LALR(k) の構築中に競合 (shift/reduce または reduce/reduce) が見つかった場合、文法は LALR(k) ではありません。

  2. LR(1) から LALR(1) への状態のマージはシフト/リデュースの競合を生成できません。ただし、削減/削減の競合が発生する可能性があります。存在する場合、文法は LR(1) ですが、LALR(1) ではありません。(これは実際には「妥当性」の問題ではなく、特定のアルゴリズムによる解析可能性の問題です。)

  3. はい、優先順位 (および優先順位の単なるサブケースである結合性) により、シフト/削減の競合を解決できます。

  4. 優先度は、プロダクション(左側) と先読みトークン(右側)の比較です。結合性は、使用される比較演算子に影響を与えます: ≤ または < (または、 の場合は%nonassocerror-on-equal)。

Dragon bookには、アルゴリズムに関する優れた議論があります。ただし、それほど複雑ではありません。プロダクションが「勝った」場合、パーサーは縮小します。それ以外の場合はシフトします。

%precおまけの質問: 優先ルールは、プロダクション (プロダクションの最後のターミナルの優先順位を介して、またはデフォルトで) と先読みトークンの両方に優先順位が定義されている場合にのみ適用されます。これらのいずれかに優先宣言がない場合は、シフトが優先されます。それは論理的ではないように思えるかもしれませんが、それはその通りです。

于 2014-02-20T04:18:30.170 に答える