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

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

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

有谁知道如何更快地做到这一点？真的很感激任何帮助!

1> Aaron Maenpa..：

---

首先,有点迂腐.您无法确定语言是否为LL(1)来检查语法,您只能对语法本身进行语句.完全可以为存在LL(1)语法的语言编写非LL(1)语法.

除此之外:

您可以为语法编写解析器,并首先计算程序,然后跟随集合和其他属性.毕竟,这是BNF语法的最大优势,它们是机器可理解的.

检查语法并查找违反各种语法类型约束的情况.例如:LL(1)允许右递归而不是左递归,因此,包含左递归的语法不是LL(1).(对于其他语法属性,你将不得不花费一些时间来定义,因为我现在不记得其他任何东西:).

---

迂腐+1.这是一个关键的区别,而且它通常被掩盖的事实是理解的障碍.

---

关于语言和语法之间区别的好处.如果语法不是LL(1),则仍然可以为该语言构造LL(1)语法.

2> Bruce Alderm..：

---

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

A→A + A | 一个

不是LL(1),而

A→a | b

是.

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

A→B | a
B→A + A.

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

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

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

这个语法只处理乘法和加法,并且已经不能立即清楚语法是否为LL(1).通过查看语法仍然可以对其进行评估,但随着语法的增长,它变得不那么可行.如果我们为整个编程语言定义语法,那么几乎可以肯定会进行一些复杂的分析.

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

---

@jpalecek:如果非终结符号可空,你实际上确实需要LL(1)的FOLLOW集合.这样,您可以"查看"非终结符以查看要使用的生产.

3> BCS..：

---

一方面,"语言/语法含糊不清",是一个已知的不可判定的问题,如邮政通信和停止问题.

4> 小智..：

---

直接来自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).