拡張文法なしでLR構文解析を実行できない場合は何ですか?
質問
多くの標準コンパイラ設計テキストは、LR解析の最初のステップとして増強された文法の構築について言及しています。
理由は頻繁に
です- スタートシンボルが生産 の右手になる場合に必要です。
- スタートシンボルのRHSに複数のプロダクションがある場合は必要です。
私はDFAの非常に最初の状態の解析テーブルの行動部分であれば、「$」の入り物の下で「成功」を提供することを私達は拡張文法を必要としないだろうと考えた。それは正しいか、私は何かが足りないのですか?
編集:ここで私たちが成功として解析を宣言できると思います:
S - > 現在の状態からスタックのTTOPを追いかけるのではなく、「a」を減らした後、私たちは単に「$」と成功の成功
を見ることができます解決
構文解析テーブルを持つと、文法を参照せずに文を解析(または拒否)できます。それでその時点で、文法が増大していなかったという事実は、本質的に訴訟です。 (拡張開始シンボルの唯一の生産に添付されているユーザー意味対処があったが、それは不可能であるように思われるが、それが不可能であるように思われる。)
と、大部分のパーサ発生器が、入力された開始を待つのではなく、入力された終了マーカーの shift を受け入れたアクションの shift を実行することによって、それを最適化することは確かにそうです。シンボルの生産量を削減します。その最適化により、拡張開始シンボルはパーサーアクションでは使用されませんので、シンボル自体は存在する必要はありません。パーサージェネレータが文法を拡張した場合、その増大は1つの小さなミステリーを除いて、次のような入力の終わりのシンボルは何ですか?それは任意の厳密な右側には現れない。
とにかく、その点はそれが解析されていないということです。これは拡張された文法を必要とします。拡張された文法は解析テーブルを作成するために必要です。必要な場合は、本質的に、入力終了シンボルのLookAheadに関連付けられているデフォルト以外の削減動作がある場合です。その削減動作は、拡張開始シンボルの製造を含む状態の分析を通して、解析テーブルに正しく追加されただけであった。
(厳密に言えば、以前に参加しているように、入力終了シンボルは文法の中に右側に存在しない限り、解析テーブルには実際には存在できず、文法は拡張されています。拡張は追加の非端末を追加するだけでなく、入力終了シンボル自体も追加されます。)