ch17-LR(1)-LR(1) 语法分析器
SLR(1)
文法FOLLOW(E)
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623144436433.png)
SLR(1) 分析表
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623144505895.png)
- 算一下FOLLOW(A)后面能跟哪些终结符，这些终结符所对应的单元格才填规约，其他的都不规约
分析表和两种冲突
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623162238320.png)
非 SLR(1) 文法举例
指针文法
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623162311620.png)
-
看到=，先移入，=也属于follow®，所以也要规约，所以冲突
-
即使考虑了= ∈ Follow®, 对该文法来说仍然不够
-
因为, 这仅仅说明 = 可能跟在 R 后面, 是一种 “粗糙” 的估计
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623162747639.png)
实际上, 该文法没有以 R = · · · 开头的最右句型
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623163057551.png)
- FIRST(γ)肯定包含在FOLLOW(A)中，所以缩小了范围
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623164005201.png)
- 规约的时候的依据
- 是怎么来的，follow(A)
- 来的时候谁跟在后面，first(γ)
LR(1)
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623164317410.png)
核心是看a怎么计算
每一个项，都要计算 , 后面的部分
- 求闭包closure
- 从一个状态goto到另一个状态
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623164938536.png)
- β有可能是空，所以FIRST(βa) != FIRST(a)
- 这是唯一区别
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623165244815.png)
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623165301238.png)
- 增广的文法，期望输入以S开头，$结束
实例演示
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623165522966.png)
- 先算FIRST和FOLLOW
构造规则：
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623165538722.png)
- 可能的句柄能不能规约只看是不是a，只在a这个位置上规约他
- a可能是集合，比如之前例子里的c/d，那么只在c和d那两个终结符的单元格里规约他
Definition (LR(1) 文法)
如果文法 G 的LR(1) 分析表是无冲突的, 则 G 是 LR(1) 文法
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623171716722.png)
对应的正则表达式：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)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623171816213.png)
LR(1) 虽然强大, 但是生成的 LR(1) 分析表可能过大, 状态过多
LALR(1) : 合并具有相同核心 LR(0)项的状态 (忽略不同的向前看符号)
-
但是合并完并不是完全的LR(0)，比如例子里的0125状态都比LR(0)有更多的信息
-
36状态合并，出边都是相同的C,c,d（ LR(0)相同，决定了出边相同）
-
47合并状态也是一样的，36通过d去往47，同理89状态也可以合并
-
合并时先选没有出边的状态
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623172636378.png)
LALR(1)能力比LR(1)弱，但事实上很多语言的实现都是LALR(1)
关于冲突的证明
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623172840842.png)
- 不可能同时包含下面的两个状态，因为A表示规约，B表示移入
- 还有一段没听懂（
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623173217112.png)
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623173404935.png)
Q: 但是你却通过 LR(1) 自动机构造 LALR(1) 项集族?
第 4.7.5 节 (本科教学版): 高效构造 LALR(1) 语法分析表的方法
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623175153629.png)
与直觉上认知矛盾
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623195442549.png)
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623195453068.png)
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623195500871.png)
-LR(1)%20%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90%E5%99%A8/image-20230623195510420.png)