parsing - 如何判断一种语言是否为 LL(1) LR(0) SLR(1)

Question

是否有一种简单的方法可以确定语法是否为 LL(1)、LR(0)、SLR(1)... 只需查看语法而不进行任何复杂的分析？

例如：要确定 BNF 语法是否为 LL(1)，您必须计算 First 和 Follow 集——在某些情况下这可能很耗时。

有没有人知道如何更快地做到这一点？任何帮助将不胜感激！

score 34 · Accepted Answer

首先，有点迂腐。您无法通过检查语法来确定语言是否为 LL(1)，您只能对语法本身进行陈述。完全有可能为存在 LL(1) 语法的语言编写非 LL(1) 语法。

顺便说一句：

您可以为语法编写一个解析器，并让一个程序首先为您计算并遵循集合和其他属性。毕竟，这是 BNF 语法的一大优势，它们是机器可理解的。
检查语法并寻找违反各种语法类型约束的情况。例如：LL(1) 允许右递归但不允许左递归，因此，包含左递归的文法不是 LL(1)。（对于其他语法属性，您将不得不花一些时间来定义定义，因为我现在不记得其他任何事情了 :)。

score 15 · Accepted Answer

回答您的主要问题：对于一个非常简单的语法，可以在不构造 FIRST 和 FOLLOW 集的情况下确定它是否为 LL(1)，例如

A → A + A | 一种

不是 LL(1)，而

一个 → 一个 | b

是。

但是当你变得比这更复杂时，你需要做一些分析。

A → B | A
B → A + A

这不是 LL(1)，但可能不会立即明显

算术的语法规则很快变得非常复杂：

expr → term { '+' term }
term → factor { '*' factor }
factor → number | '(' 表达式 ')'

该文法只处理乘法和加法，目前尚不清楚该文法是否为 LL(1)。仍然可以通过查看语法来评估它，但是随着语法的增长，它变得不那么可行了。如果我们要为整个编程语言定义语法，几乎肯定会进行一些复杂的分析。

也就是说，有一些明显的迹象表明语法不是 LL(1)——就像上面的 A → A + A——如果你能在你的语法中找到任何这些，你就会知道它需要重写如果您正在编写递归下降解析器。但是没有捷径可以验证语法是否为LL(1)。

score 9 · Accepted Answer

一方面，“语言/语法是否有歧义”是一个已知的不可判定问题，例如邮政通信和停顿问题。

score 9 · Accepted Answer

直接来自 Aho 等人的《编译器：原理、技术和工具》一书。人。

第 223 页：

一个文法 G 是 LL(1)当且仅当当 A -> alpha | beta是 G 的两个不同产生，以下条件成立：

对于没有终端“a”，alpha和beta都派生以“a”开头的字符串
至多alpha和beta之一可以导出空字符串
如果beta可以通过零个或多个转换到达空转换，则alpha不会派生任何以 FOLLOW(A) 中的终端开头的字符串。同样，如果alpha可以通过零个或多个转换到达空转换，则beta不会派生任何以 FOLLOW(A) 中的终端开头的字符串

本质上，这是验证语法通过成对不相交测试并且不涉及左递归的问题。或者更简洁地说，左递归或模棱两可的文法 G 不能是 LL(1)。

score 2 · Accepted Answer

检查语法是否有歧义。如果是，则文法不是 LL(1)，因为没有歧义文法是 LL(1)。

score 0 · Accepted Answer

是的，有 ll(1) 语法的快捷方式

1) 如果 A->B1|B2|.......|Bn then first(B1)intersection first(B2)intersection .first(Bn)=empty set 那么它是 ll(1) 语法

2) 如果 A->B1|epsilon 则 B1 交集 follow(A) 为空集

3) 如果 G 是任何文法，使得每个非终结符只派生一个产生式，则文法为 LL(1)

score -2 · Accepted Answer

p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id

7 回答 7