如何确定语言是否为ll(1)lr(0)slr(1)

首先,有点迂腐。您无法确定 语言 是从检查语法中得到的,你只能对 语法 本身。对于存在ll(1)语法的语言,编写非ll(1)语法是完全可能的。

别挡道了:

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

• 检查语法并寻找 违规行为 各种语法类型的约束。例如:ll(1)允许右递归,但不允许左递归,因此,包含左递归的语法不是ll(1)。(对于其他语法属性,您将不得不花费一些高质量的时间来定义,因为我现在记不起任何其他东西了。)

回答你的主要问题:对于一个非常简单的语法,可能不需要先构造集合,然后再跟随集合,就可以确定它是否是ll(1)。

A+A+A

不是ll(1),而

A~B

是。

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

A、B、A
B+a+A

这不是ll(1),但可能不是很明显

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

expr→term'+'term
术语→因子'*'因子
系数→数字(‘expr’)

这种语法只处理乘法和加法,而且还不清楚语法是否为ll(1)。仍然可以通过查看语法来评估它,但是随着语法的增长,它变得不那么具有可行性。如果我们要为整个编程语言定义语法,那么几乎可以肯定,它将进行一些复杂的分析。

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

一个方面,“语言/语法是否含糊不清”,是 a known undecidable question 像 Post correspondence 和 halting 问题。

直接摘自AHO等人的《编译器:原理、技术和工具》。

第223页:

语法G是ll(1) 当且仅当 每当a-> 阿尔法 γ 贝塔 是G的两个不同产物,满足以下条件:

1. 对于没有终端“A”,两者都要做 阿尔法 和 贝塔 派生以“a”开头的字符串
2. 至多一个 阿尔法 和 贝塔 无法派生空字符串
3. 如果 贝塔 可以通过零个或多个转换到达空转换,然后 阿尔法 不派生以后面(a)中的终端开头的任何字符串。同样,如果 阿尔法 可以通过零个或多个转换到达空转换,然后 贝塔 不派生以后面(a)中的终端开头的任何字符串

本质上,这是一个验证语法通过成对不连接测试的问题,并且也不涉及左递归。或者更简洁地说,留下递归或不明确的语法g不能是ll(1)。

检查语法是否含糊不清。如果是,那么语法就不是ll(1),因为没有不明确的语法是ll(1)。

是的,这是所有语法的捷径。

1)如果a->b1 b2……bn 然后是第一个(b1)交集,第一个(b2)交集。第一个(bn)=空集,然后是ll(1)语法

2)如果a->b1 epsilon 则b1交叉口跟随(a)为空集

3)如果g是任何语法,使得每个非终端只派生一个产品,那么语法是ll(1)

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

• 构造lr(0)dfa、e的follow set和slr action/goto表。
• 这是一个lr(0)语法吗?证明你的答案。
• 使用SLR表,显示LR解析器解析的步骤(移位、缩减、接受):
  id ( id + id )