FIRST セットと FOLLOW セットとは何ですか? それらは解析で何に使用されますか? トップダウンまたはボトムアップのパーサーに使用されますか?
次の一連の文法規則について、FIRST および FOLLOW SETS について説明してもらえますか。
E := E+T | T
T := T*V | T
V := <id>
3453 次
3 に答える
3
これらは通常、LL (トップダウン) パーサーで使用され、実行中のパーサーが解析を続行する方法が複数ある状況に遭遇するかどうかを確認します。
"a" が入力で次に来ると、A または B を展開するかどうかわからないため、代替手段がありA | B、さらにあり、FIRST/FIRST 競合が発生します (先読みが 1 であると仮定)。FIRST(A) = {"a"}FIRST(B) = {"b", "a"}
反対に、null 可能な非端末がある場合は、「a」が含まれAOpt: ("a")?ていないことを確認する必要がFOLLOW(AOpt)あります。そうしないと、AOpt を展開するかどうかわからないためですS: AOpt "a"。S または AOpt のいずれかが " a" は、FIRST/FOLLOW 競合を引き起こします。
パフォーマンス上の理由から、解析プロセス中に FIRST セットを使用することもできます。null 許容の非ターミナル NullableNt がある場合は、それを展開して何かを消費できるかどうかを確認できます。またはFIRST(NullableNt)、次のトークンが含まれているかどうかを確認し、そうでない場合は単に無視する方が速い場合があります (バックトラッキングと予測解析)。もう 1 つのパフォーマンスの改善は、レキシカル スキャナーに現在の FIRST セットを追加で提供することです。これにより、スキャナーは可能なすべての端末を試すのではなく、コンテキストで現在許可されている端末のみを試行します。これは予約された端末と競合しますが、それらは常に必要というわけではありません。
ボトムアップ パーサーには、Reduce/Reduce と Shift/Reduce というさまざまな種類の競合があります。また、FIRST,FOLLOW ではなくアイテム セットを使用して競合を検出します。
左再帰が含まれているため、あなたの文法は LL パーサーでは機能しません。しかし、E、T、および V の FIRST セットは {id} になります (あなたT := T*V | Tが意図されていると仮定するとT := T*V | V)。
于 2013-05-01T10:16:04.663 に答える
0
ウィキペディアはあなたの友達です。LL パーサーとファースト/フォロー セットの説明を参照してください。
基本的に、それらはパーサー構築の基本として使用されます。たとえば、パーサー ジェネレーターの一部として使用されます。それらを使用して文法の特性について推論することもできますが、ほとんどの人はこれを行う必要はあまりありません。
于 2010-09-30T10:43:27.417 に答える