4

我还没有找到答案。是否存在无法转换为 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)

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

4

1 回答 1

4

一般来说，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's，不提供有用的信息。如需严格证明，请在此处查看已接受答案的第二部分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规则似乎很复杂，很难马上回答。您可以尝试手动对所有冲突的替代方案执行左分解，或者使用一些辅助工具，如ANTLR。

于 2015-07-17T23:15:48.570 回答