今日主题：LR（1）语法分析器
核心知识点的理解。机械性的操作。由自动机画那一张表。。
三类语法分析器算法。
引入
LR(0)的关键：处于红色框的位置时 ，识别到了句柄，能不能拿它做归约
比如 2号状态，结束状态。E→T. ;不管当前输入是哪一个终结符，都用2号产生式进行归约。松松的判断条件。有冲突的单元格，所以不是lr(0)文法，有移入归约冲突。
问题是：能否消除“移入-归约”冲突？那么应该加强归约的条件，要考虑当前的输入。
例子：我们看2号状态
栈的角度，自动机的角度，弹出T，弹入E。自动机：从该状态回去到I0状态，再加进E到I1状态
与follow集合有关。
*不在里面，所以对应不做归约。
general idea
假设现在发现了一个句柄： 当前符号是小t,在s这个状态上面。
现在考虑的是能不能拿这个句柄在当前看到小t的情况下拿这个句柄做归约
看栈的状态，前面这一串是
语法分析器的状态包含两部分，还有一部分没有处理的输入，以t打头。
a弹出A压进去，语法分析器的状态是一个可能的句型，要求t能够跟在A后面。必要条件
SLR(1)
simple， 1,看当前的这个符号是否满足followa这个条件。
在i这个状态，表的第一栏，如果有这样的一个句柄A→a.,加强条件，只在这一行中满足这个条件的那些终结符列里面填归约，满足的必要条件：
归约：
(SLR(1)文法)
如果文法G的SLR(1)分析表是无冲突的，则G是SLR(1)文法
- 无冲突：action表中每个单元格最多只有一种动作
- 如果有冲突，两类可能的冲突，移入/归约冲突，归约/归约冲突。不会有移入移入冲突，确定性
无法处理
表达c语言当中的指针结构。右边 状态。
自动机是LR(0),但是表不一样了。
看I2状态，移入归约冲突。看到=号
它属于follow集只是一个必要条件，那我到底要不要做归约呢，不是说满足这个条件一定要做归约，把这个必要条件再加强一下？
- q0只有出边没有入边，说明它处于栈底，那么只有R=这样开头的符号，R前面不会有其他的符号，但是 分析文法，该文法没有以R=…开头的最右句型
- 我们希望的是获取一些动态的信息，在某个状态下得到的句柄想知道它是否能做归约，还需要知道它是怎么来到这个状态的，这一路的信息都希望能够分析一下
Question
怎么去获取动态的信息
希望LR语法分析器的每个状态能尽可能精确地指明哪些输入符号可以跟在句柄的后面
LR(1)
在LR(0)自动机中，某个项集中包含则在之前的某个项集中包含
而它是由闭包得到的。
这样一个状态对小t的更强要求，First()
简化一下，前面的不需要了，因为后面的条件蕴含了前面的条件。
但是，做闭包之后，的信息被丢掉了
项
所以 改造lr(0)自动机，入手点，项的定义改造一下。
(LR(1)项（item）)
(a\in T \cup \{\}\gamma$)，数量为1
小a是终结符或者$符号
此项的含义是：在栈顶，期望剩余输入中开头的是可以从推导出的符号串
当发现了一个句柄，归约的条件，
操作
状态内部
闭包操作，一个集合内部。带入beta的信息。
后半部分的小b,满足的条件。
我所期望的符号是从B推导出来的，现在要去追踪大B了
转移
一个状态转移到另一个状态
X可能是终结符可能是非终结符。
直接将后面的带过去
初始状态
于是可以构造一个自动机了
增广文法。增加,跟踪S，期望输入由S和\推导出来。
例子
看I0 和C转移到I2
LR(1)分析表构造规则
只是规约的时候发生了变化
项里面自带了归约的条件，只有在当前对应符号项是小a的情况下，才归约。
LR(1)文法
LALR(1)
合并LR(1)具有相同核心LR(0)项的状态（忽略不同的向前看符号）
谁不是向前看呢。。
动机
三对状态，3和6 项的前半部分是一样的，后面的不一样，即LR(0)项相同。分裂了。
缺点就是状态太多，冗余复杂，分析表过大。想把内存降下来，合起来状态。但是能力不变仍是lr(1)
有入边和出边的状态。先处理没有出边的状态对。一点点往前。
问题
对于 LR（1）文法，合并得到的LALR（1）分析表是否会引入冲突？
Theorem
LALR(1)分析表不会引入移入/归约冲突。
反证法： 简单漂亮！
假设两个具有相同核心项的状态一合并，得到了一个有冲突的状态，假设是: 第一项说明如果当前是小a的话，拿这个句柄做归约；后面的项是说如果是小a的话，那么我就把.往后挪，移入。那么在LR(1)的一个状态里，一定包含某个状态有这两项。原始的LR(1)里面本来就有移入归约冲突，那你就不是LR(1)文法，矛盾。
蓝色箭头如何推出来的？
i和j之所以会合并是因为核心项相同，那么i里面也存在B.
Theorem
LALR(1)分析表可能会引入归约/归约冲突。
两条归约
LALR(1)语法分析器的优点
- 状态数量与SLR（1）语法分析器的状态数量相同。合并状态，只剩下LR(0)项；（LALR(1)与SLR(1)都使用相同的LR(0)核心项）
- 对于LR(1)文法，不会产生移入/归约冲突
但是你却通过LR(1)自动机构造LALR(1)项集族？
消耗内存。4.7.5节
语言与文法的关系
L 可以用 G1 G2 G3来描述。复杂的证明。。
如果一个语言，可以写出LR(1)文法，那么也存在一个等价的SLR(1)文法也能够表达这个语言。
现在的语法分析器
一大串的LALR(1) bison/yacc/lark