parsing - 如何判断一种语言是否是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)。 (对于其他语法属性，您将不得不花一些时间来研究定义，因为我现在记不起任何其他内容:)。