是否找到不是LL(1)的语言? [英] Finding a language that is not LL(1)?
问题描述
最近我一直在处理很多不是LL(1)的语法，其中许多可以转换为LL(1)的语法.
I've been playing around with a lot of grammars that are not LL(1) recently, and many of them can be transformed into grammars that are LL(1).
但是，我从未见过不含糊的语言的示例，该示例不是LL(1).换句话说，一种语言的语法没有任何歧义，不是LL(1))，我也不知道如何证明我偶然发现了一种语言.
However, I have never seen an example of an unambiguous language that is not LL(1). In other words, a language for which any unambiguous grammar for the language is not LL(1)), nor do I have any idea how I would go about proving that I had found one if I accidentally stumbled across one.
有人知道如何证明一种特定的语言不是LL(1)吗?
Does anyone know how to prove that a particular unambiguous language is not LL(1)?
推荐答案
我想了好一会儿，然后在维基百科:
I was thinking about the question a while and then found this language at Wikipedia:
S -> A | B
A -> 'a' A 'b' | ε
B -> 'a' B 'b' 'b' | ε
他们声称上述语法描述的语言无法用LL(k)语法描述.您仅询问了LL(1)，这非常简单.仅具有第一个符号，您不知道序列是"ab"还是"aab"(或任何其他递归序列)，因此您无法选择正确的规则.因此，该语言绝对不是LL(1).
They claim the language described by the grammar above cannot be described by LL(k) grammar. You asked about LL(1) only and this is pretty straightforward. Having first symbol only, you don't know if the sequence is 'ab' or 'aab' (or any more recursive one) and therefore you cannot choose the right rule. So the language is definitely not LL(1).
对于此语法生成的每个序列，也只有一个派生树.因此，语言是明确的.
Also for every sequence generated by this grammar there is only one derivation tree. So the language is unambiguous.
问题的第二部分要难一些.证明该语言是LL(1)相比相反要容易得多(不存在描述该语言的LL(1)语法).我认为您只是创建一种描述语言的语法，然后尝试使其成为LL(1).发现无法解决的冲突后，您必须以某种方式利用它并创建证明.
The second part of your question is a little harder. It is much easier to prove the language is LL(1), than the opposite (there is no LL(1) grammar describing the language). I think you just create a grammar describing the language, then you try to make it LL(1). After discovering a conflict which cannot be resolved you somehow have to take advantage of it and create a proof.
这篇关于是否找到不是LL(1)的语言?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
