文法がLL(1)、LR(0)、SLR(1)のいずれであるかを識別する方法とは？

質問

文法がLL(1)、LR(0)、SLR(1)であるかどうかは、どのように判別するのですか？

どなたか、この例、または他の例を使って説明していただけませんか？

X → Yz｜a

Y → bZ｜ε

Z → ε

どのように解決するのですか？

文法がLL(1)であるかどうかを調べるには、LL(1)構文解析表を作成し、矛盾がないかを確認する方法がある。 これらのコンフリクトは

• FIRST/FIRST の競合。ここでは、2 つの異なるプロダクションが非終端記号/終端記号のペアで予測される必要があります。
• FIRST/FOLLOW 競合。2 つの異なるプロダクションが予測され、1 つは何らかのプロダクションが取られ、記号の非ゼロ数に展開されることを表し、1 つは何らかの非終端が最終的に空の文字列に展開されるべきことを示すプロダクションが使用されることを表します。
• FOLLOW/FOLLOW の競合。非終端記号が最終的に空の文字列に展開されることを示す 2 つのプロダクションが互いに競合する場合。

各非終端記号のFIRSTとFOLLOWのセットを構築して、これを文法で試してみましょう。 ここでは、次のようになります。

FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon} 

また、FOLLOWの集合が

FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}

これより、以下のようなLL(1)の解析テーブルを構築することができます。

    a    b    z   $
X   a    Yz   Yz  
Y        bZ   eps
Z             eps

この構文解析表を矛盾なく作ることができるので、文法はLL(1)となります。

文法がLR(0)かSLR(1)かを調べるには、まずその文法のLR(0)構成集合を全て構築することから始めます。 この場合、Xを開始記号と仮定すると、次のようになります。

(1)
X' -> .X
X -> .Yz
X -> .a
Y -> .
Y -> .bZ

(2)
X' -> X.

(3)
X -> Y.z

(4)
X -> Yz.

(5)
X -> a.

(6)
Y -> b.Z
Z -> .

(7)
Y -> bZ.

これより、状態(1)でshift/reduceの競合があるため、この文法はLR(0)ではないことがわかる。 具体的には、シフト項目X→.a、Y→.があるため、aをシフトするか、空文字列をreduceするかは分からない。より一般的には、ε-productionを持つ文法はLR(0)にならない。

しかし、この文法はSLR(1)であるかもしれない。 これを見るには、特定の非終端記号のルックアヘッドセットで各減少を補強する。 これは、このSLR(1)構成セットのセットを返します。

(1)
X' -> .X
X -> .Yz [$]
X -> .a  [$]
Y -> .   [z]
Y -> .bZ [z]

(2)
X' -> X.

(3)
X -> Y.z [$]

(4)
X -> Yz. [$]

(5)
X -> a.  [$]

(6)
Y -> b.Z [z]
Z -> .   [z]

(7)
Y -> bZ. [z]

ルックヘッドがzの時だけreduceを行うので、状態①のshift/reduceの衝突はなくなりました。

お役に立てれば幸いです。