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

Question

有没有一种简单的方法来确定一个文法是否是LL(1)，LR(0)，SLR(1)……仅仅看语法而不做任何复杂的分析？

例如:要确定BNF语法是否为LL(1)，您必须先计算集合，然后再计算集合-在某些情况下，这可能很耗时。

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

Answer 1

首先，有点卖弄学问。您不能确定语言是否为LL(1)通过检查它的语法，您只能对语法本身作出声明。为存在LL(1)文法的语言编写非LL(1)文法是完全可能的。

这样就不会有什么问题了：

，，

• ，你可以为语法写一个解析器，然后让一个程序先计算，然后再计算集合和其他属性。毕竟，这是BNF语法的最大优势，它们是机器违反语法，并查找各种语法类型的约束的违反行为( comprehensible.
• Inspect )。例如: LL(1)允许右递归，但不允许左递归，因此，包含左递归的语法不是LL(1)。(对于其他语法属性，您必须花一些高质量的时间在定义上，因为我现在想不起其他任何东西了：)。

Answer 2

回答你的主要问题:对于一个非常简单的语法，可以确定它是否是LL(1)，而不需要先构造和跟随集合，例如

A→A+A|a

不是LL(1)，而是

A→a|b

是。

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

A→B|a

B→A+A

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

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

expr→term { '+‘term }

术语→因子{ '*‘因子}

系数表达式编号| '(‘→')’

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

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

Answer 3

一方面，“是语言/语法不明确”，就像Post correspondence和halting问题一样。