私は最近、LL(1) ではない多くの文法をいじっていますが、それらの多くは LL(1) の文法に変換できます。
しかし、 LL(1) ではない明確な言語の例を見たことがありません。言い換えれば、その言語の明確な文法が LL(1) ではない言語であり、偶然見つけた場合に、それを見つけたことをどのように証明できるかわかりません。
特定の明確な言語が LL(1) ではないことを証明する方法を知っている人はいますか?
2912 次
1 に答える
5
私はその質問についてしばらく考えていましたが、ウィキペディアで次の言葉を見つけました。
S -> A | B
A -> 'a' A 'b' | ε
B -> 'a' B 'b' 'b' | ε
彼らは、上記の文法で記述された言語は LL(k) 文法では記述できないと主張しています。LL(1) についてのみ質問しましたが、これは非常に簡単です。最初のシンボルしかないため、シーケンスが 'ab' か 'aab' (またはそれ以上の再帰的なもの) かがわからないため、正しいルールを選択できません。したがって、言語は間違いなく LL(1) ではありません。
また、この文法によって生成されるすべてのシーケンスに対して、派生ツリーは 1 つしかありません。したがって、言語は明確です。
あなたの質問の2番目の部分は少し難しいです。その言語が LL(1) であることを証明する方が、逆の場合よりもはるかに簡単です (言語を記述する LL(1) 文法はありません)。言語を記述する文法を作成し、それを LL(1) にしようとしているだけだと思います。解決できない競合を発見した後、何らかの形でそれを利用して証明を作成する必要があります。
于 2011-07-28T23:18:37.390 に答える