# ch17-LR(1)-LR(1) 语法分析器

# SLR(1)

# 文法FOLLOW(E)

SLR(1) 分析表

• 算一下FOLLOW(A)后面能跟哪些终结符，这些终结符所对应的单元格才填规约，其他的都不规约

# 分析表和两种冲突

# 非 SLR(1) 文法举例

指针文法

• 看到=，先移入，=也属于follow®，所以也要规约，所以冲突

• 即使考虑了= ∈ Follow®, 对该文法来说仍然不够

• 因为, 这仅仅说明 = 可能跟在 R 后面, 是一种 “粗糙” 的估计

实际上, 该文法没有以 R = · · · 开头的最右句型

• FIRST(γ)肯定包含在FOLLOW(A)中，所以缩小了范围

• 规约的时候的依据
• 是怎么来的，follow(A)
• 来的时候谁跟在后面，first(γ)

# LR(1)

核心是看a怎么计算

每一个项，都要计算 , 后面的部分

• 求闭包closure
• 从一个状态goto到另一个状态

• β有可能是空，所以FIRST(βa) != FIRST(a)
• 这是唯一区别

• 增广的文法，期望输入以S开头，$结束

# 实例演示

• 先算FIRST和FOLLOW

# 构造规则：

• 可能的句柄能不能规约只看是不是a，只在a这个位置上规约他
• a可能是集合，比如之前例子里的c/d，那么只在c和d那两个终结符的单元格里规约他

Definition (LR(1) 文法)

如果文法 G 的LR(1) 分析表是无冲突的, 则 G 是 LR(1) 文法

对应的正则表达式：L(G) = c ∗ dc∗ d

输入ccdcd$过程：

• 移入0$
• 移入c3
• 移入c3
• 看到d，d4
• 看到c，弹出d，状态3，加入C，状态8
• 看到c，规约，弹出c，C，状态0，压入C，状态2
• 看到c，状态6
• 看到d，状态7
• 看到$，弹出d，状态6，移入C，状态9
• 看到$，弹出C，c，状态,2，移入C，状态5
• 看到$，弹出CC，状态0，移入S，状态1

LR(1) 虽然强大, 但是生成的 LR(1) 分析表可能过大, 状态过多

LALR(1) : 合并具有相同核心 LR(0)项的状态 (忽略不同的向前看符号)

• 但是合并完并不是完全的LR(0)，比如例子里的0125状态都比LR(0)有更多的信息

• 36状态合并，出边都是相同的C,c,d（ LR(0)相同，决定了出边相同）

• 47合并状态也是一样的，36通过d去往47，同理89状态也可以合并

• 合并时先选没有出边的状态

LALR(1)能力比LR(1)弱，但事实上很多语言的实现都是LALR(1)

# 关于冲突的证明

• 不可能同时包含下面的两个状态，因为A表示规约，B表示移入
• 还有一段没听懂（

Q: 但是你却通过 LR(1) 自动机构造 LALR(1) 项集族?

第 4.7.5 节 (本科教学版): 高效构造 LALR(1) 语法分析表的方法

与直觉上认知矛盾