c -是否存在一个LR(k)语法而没有LL(1)等价

Question

我还没有找到这个问题的答案。是否存在与上下文无关且无歧义且不能转换为LL(1)的语法?

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

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

这是LR(k)语法没有LL(1)等效的例子还是我做错了什么?

编辑:我复制了错误的名字，我想复制参数声明:

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的字符串，后面跟着相同或更少数量的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 -> , ...

需要注意的是，parameter-list设置的FOLLOW将包含,字符，这可能导致FIRST-FOLLOW冲突。如果是这样的话，那么我们也需要查看parameter-list定义来修复这个冲突。

编辑: parameter-declaration规则似乎很复杂，不能马上回答。您可以尝试手动对所有冲突的选项执行左分解，或者使用一些辅助工具，如ANTLR。