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

标签 c parsing context-free-grammar ll lr

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

相关文章:

theory - 将 CFG 转换为 CNF

在 C 中将字符串转换为 mpz_t

jquery - 为什么 jQuery.parseJSON 不是一个函数?

python - 重新格式化从 Python 中的 CSV 文件读取的列表中的项目

python - 使用 Python 解析文本文件

compiler-construction - 将属性从 flex 返回给 bison

c - 如何在 macOS 上找到 C 头文件 errno.h 的位置?

c - 在 htons 和 htonl 之间做出选择

c - 如何在C中制作自己的IO功能?

c - 为什么 C 的 BNF 语法允许使用空的 init-declarators 序列进行声明?