是否存在没有LL(1)等效的LR(k)文法？
是否存在没有LL(1)等效的LR(k)文法？
提问于 2015-07-17 22:48:39
我还没找到答案。是否有上下文自由且不含糊的语法不能转换为LL(1)？
我发现了一个无法转换为LL(1)的产品:C99中的C99产品：
parameter-type-list:
parameter-list
parameter-list , ...这是一个没有LL(1)等价的LR(k)语法的例子，还是我做错了什么？
编辑:我复制了错误的名称，我想复制参数声明：
parameter-declaration:
declaration-specifiers declarator
declaration-specifiers abstract-declarator(opt)问题在于声明器和抽象声明器都有(在它们的第一个集合中)，但是仍然是递归的。
回答 1
Stack Overflow用户
发布于 2015-07-17 23:15:48
一般来说，LR(k)语法比LL(k)更强大。这意味着有一些带有LR(k)解析器的语言，但没有LL(k)。
其中一个例子是用语法定义的语言：
S -> a S
S -> P
P -> a P b
P -> \epsilon或者，换句话说，a的字符串，后面跟着相同或更少的b的字符串。这是因为LL(k)解析器必须对遇到的每一个a做出一个决定--它是否与某些b配对--只看输入的k符号，但它们也可以是a的，没有提供有用的信息。要获得严格的证明，请看这里https://cs.stackexchange.com/questions/3350/is-this-language-ll1-parseable所接受的答案的第二部分。
但是，在LL(1)语法中，您的示例可以是简单的左因子
parameter-type-list -> parameter-list optional-ellipsis
optional-ellipsis -> \epsilon
optional-ellipsis -> , ...请注意，FOLLOW设置为parameter-list将包含,字符，这可能导致FIRST-FOLLOW冲突。如果是这样的话，那么我们也需要看到parameter-list定义来解决这个冲突。
编辑:立即回答 parameter-declaration规则似乎非常复杂。您可以尝试手动对所有冲突的备选方案执行左因式分解，或者使用一些辅助工具，如反。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/31485799
复制相关文章
相似问题
腾讯云开发者
