parsing - 文法の作り方 LL(1)

Question

私は次の文法を持っています：

S→aSbS| b S a S | ε

そのための小さなコンパイラを書こうとしているので、LL(1)にしたいと思います。ここで FIRST/FOLLOW の競合が発生しているようです。それを解決するには置換を使用する必要があることはわかっていますが、どうすればよいか正確にはわかりません。これが私の提案する文法ですが、それが正しいかどうかはわかりません:

S-> aSbT | イプシロン

T-> bFaF| イプシロン

F->イプシロン

誰か助けてくれませんか？

Answer 1

LR 構文解析に関する彼の元の論文で、Knuth はこの言語に次の文法を与えており、これは「この言語の最も簡潔で明確な文法である」と推測しています。

S → ε | aAbs | BBAS

A → ε | アバ

B → ε | ばば

直観的に、これは A と B の文字列をブロックに分割して完全にバランスを取ろうとします。a で始まり b で終わるブロックもあれば、b で始まり a で終わるブロックもあります。

FIRST および FOLLOW セットは次のように計算できます。

FIRST(S) = { ε, a, b }

FIRST(A) = { ε, a }

FIRST(B) = { ε, b }

FOLLOW(S) = { $ }

フォロー(A) = { b }

フォロー(B) = { a }

これに基づいて、次の LL(1) 解析テーブルを取得します。

   |   a   |   b   |   $   
 --+-------+-------+-------
 S | aAbS  | bBaS  |  e
 A | aAbA  |   e   |
 B |   e   | bBaB  |

つまり、この文法は LR(1) だけでなく、LL(1) でもあります。

お役に立てれば！