我还没有找到答案。是否存在无法转换为 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)
问题在于声明符和抽象声明符都具有 ( 在它们的第一组中,但也被保留了递归。
最佳答案
一般来说,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 .
关于c - 是否存在没有 LL(1) 等价物的 LR(k) 文法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31485799/