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

Question

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

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

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

Answer 1

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

解决了这个问题：

• 您可以为语法编写一个解析器，并让一个程序首先计算并遵循集合和其他属性。 毕竟，这是 BNF 语法的一大优势，它们是机器可理解的。

• 检查语法并查找违反各种语法类型约束的情况。 例如：LL(1)允许右递归但不允许左递归，因此包含左递归的语法不是LL(1)。 （对于其他语法属性，您将不得不花一些时间来处理定义，因为我现在记不起任何其他内容:)。

Answer 2

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

A → A + A | 一个

不是 LL(1)，而

A → 一个 |

群岛

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

A → B | 一个
B → A + A

这不是 LL(1)，但可能不会立即显而易见

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

expr → 项 { '+' 项 }
项 → 因子 { '*' 因子 }
因数 → 数 | '('表达式')'

该语法仅处理乘法和加法，并且目前还不能立即明确该语法是否为 LL(1)。 仍然可以通过查看语法来评估它，但随着语法的增长，它变得不太可行。 如果我们要为整个编程语言定义语法，那么几乎肯定需要进行一些复杂的分析。

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

Answer 3

一方面，“语言/语法是否模糊”，是一个已知的不可判定问题，例如帖子通信和停止问题。

Answer 4

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

第 223 页：

文法 G 是 LL(1) 当且仅当每当 A -> 时 阿尔法 | beta 是 G 的两个不同产生式，满足以下条件：

1. 对于没有终结符“a”，alpha 和 beta 都派生出以“开头的字符串” a"
2. 最多 alpha 和 beta 之一可以导出空字符串
3. 如果 beta 可以通过零个或多个转换到达空转换，则 < em>alpha 不会在 FOLLOW(A) 中派生任何以终结符开头的字符串。 同样，如果alpha可以通过零个或多个转换到达空转换，那么beta不会派生出任何以FOLLOW(A)中的终结符开头的字符串

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

Answer 5

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

Answer 6

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

1) if A->B1|B2|.......|Bn
那么first(B1)intersection first(B2)intersection .first(Bn)=空集那么它是ll(1)语法

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

3) 如果 G 是任意文法，使得每个非终结符仅导出一个产生式，则该文法为 LL(1)

Answer 7

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

• 构造 LR(0) DFA、E 的 FOLLOW 集和 SLR 操作/转到表。
• 这是 LR(0) 语法吗？ 证明你的答案。
• 使用 SLR 表，显示 LR 解析器解析的步骤（移位、归约、接受）：
  id ( id + id )