c - 是否存在没有 LL(1) 等价物的 LR(k) 文法

Question

我还没有找到答案。是否存在无法转换为 LL(1) 的上下文无关且无歧义的语法？

我发现了一个我不知道如何转换为 LL(1) 的作品:parameter-type-list C99中的生产:

parameter-type-list:
    parameter-list
    parameter-list , ...

这是一个没有 LL(1) 等价物的 LR(k) 语法的例子还是我做错了什么？

编辑:我复制了错误的名称，我的意思是复制参数声明:

parameter-declaration:
    declaration-specifiers declarator
    declaration-specifiers abstract-declarator(opt)

问题在于声明符和抽象声明符都具有 ( 在它们的第一组中，但也被保留了递归。

Answer 1

一般来说，LR(k)语法比 LL(k) 更强大.这意味着有些语言带有 LR(k)解析器，但不是 LL(k) .

示例之一是用语法定义的语言:

S -> a S 
S -> P
P -> a P b
P -> \epsilon

或者，换句话说，字符串 a 's，后跟相同或更少数量的 b的。这源于 LL(k)解析器必须对每个 a 做出决定遇到 - 是否与一些 b 配对- 展望不超过 k输入符号，但也可以是 a的，没有提供有用的信息。
对于严格的证明，请在此处查看已接受答案的第二部分 https://cs.stackexchange.com/questions/3350/is-this-language-ll1-parseable

但是，您的示例可以是简单的 left factored在 LL(1) 语法中是

parameter-type-list -> parameter-list optional-ellipsis
optional-ellipsis -> \epsilon
optional-ellipsis -> , ...

一记 FOLLOW设置为 parameter-list将包含 ,字符，这会导致 FIRST-FOLLOW冲突。如果是这样，那么我们需要查看 parameter-list定义来解决这个冲突。

编辑: parameter-declaration规则似乎很复杂，立即回答。您可以尝试对所有冲突的替代方案手动执行左分解，或者使用一些辅助工具，例如 ANTLR .