文法を作るLL（1）

Question

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

S→a S b S | b S a S | ε

私は小さなコンパイラを書こうとしているので、LL（1）にしたいと思います。私はここにFIRST/FOLLOWの矛盾があるように見えますが、私はそれを解決するために代用を使わなければならないことを知っています。ここに提案された文法がありますが、正しいかどうかはわかりません：

S-> aSbT |イプシロン

T-> bFaF |イプシロン

F->は、誰かがイプシロン

を助けることはできますか？彼のoriginal paper on LR parsingで

Answer 1

、クヌースは、彼が「この言語の最も短い可能な明確な文法である：」推測し、この言語は、次の文法を与え

S →＆イプシロン。 | aAbS | bBaS

→ε; | aAbA

B →ε; | bBaB

直感的に、これはAsとBsの任意の文字列を完全に均衡するブロックに分割しようとします。いくつかのブロックはaで始まり、bで終わりますが、他のブロックはbで始まりaで終わります。

我々は最初に計算し、次のようにセットに従うことができる：

FIRST（S）= {＆イプシロン;,、B}

FIRST（A）= {＆イプシロン;, A}

FIRST（B）= {＆イプシロン;, B}

フォロー（S）= {$}

FOLLOW（A）= {B}

フォロー（B）= {A}これに基づい

、我々は、（1）下記LLを解析取得テーブル：

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

ので、この文法であるのみならず、LR（1）それはLL（1）でもあります。

希望すると便利です。