关于parser的语法树生成算法（实现）
Week 5 and Week 6
首先是提出算法实现前的一些铺垫，主要包括以下知识：
1.Top-Down and Bottom-Up
2.Shift-Reduce Parsing
3.一些notation为了算法实现做铺垫
1.Top-Down and Bottom-Up
Top-Down对应先前讲的leftmost，而Bottom-Up则对应先前讲的rightmost，Week 4是从易于理解的角度讲解，而本周则是从实现的角度讲解。主要涉及到了如何shift，如何reduce，以及如何生成树，但是没有讲什么时候。
2.Shift-Reduce Parsing
基于Top-Down and Bottom-Up引出的语法解析实现的简单模型，初步引入了一些notation，如
主要解决了在哪reduce的问题
期间讲了一个插曲，也就是冲突（conflict）的解决方法：
一个为：shift和reduce的冲突，可被precedence and associativity declaration修复，类似于leftmost 或者rightmost，如加法和乘法的优先级。
另一个： reduce-reduce conflict，不知道该选择哪一个规则，说明： There is ambiguity in the grammar ，Might be fixed by additional lookahead，这个类似于两个规则冲突
3.When to shift/reduce?
接着讲什么时候解决冲突，主要引入了prefix and handle
然后将了语法规范（specific）和parser的关系，核心在这张图：基本观点是，规范越简单解析器越简单，解析器无法准确识别所用的上下文无关语法（CFG），解析器的实现也需要效率和功能的trade-off
3.When to shift/reduce?realize
algorithm 1（LR0）
关键在于构造action和goto两张表格
构造上述两张表格需要知道Configuration set
构造configuration set需要知道如何计算Closure property
action和goto表格的状态转移可看下表：
只需要注意一点的就是其状态转移只和stack头的元素有关，当弹出元素之后的状态转移也是如此
closure的构造
把所有的非终结符递归的转换即可
Successor(I, X)的构造
类似于状态转移后的状态的构造，状态转移需要移动圆点
configuration set的构造
action和goto的表格获得
需要注意的地方
1.状态不要重复，状态也不能少
2.若出现冲突说明grammar定义的不好
如此例子：则出现了reduce和shift冲突和reduce和reduce冲突，注意有的并非冲突，可以一个状态多次操作
algorithm 2（SLR1）
关键在于知道first（X）和follow（X）的定义，进而shift操作和reduce操作以及reduce-reduce的conflict都可以从follow（X）的定义解决，当然也有语法不满足的情况。
总结就是通过可以观察即将输入的terminal来判断是否执行push操作，或者直接执行reduce操作，因此称为SLR1，然后再根据执行操作后入栈的元素来实现状态转移，也就是说在入栈的那一刻状态也转移了，栈顶存储的就是此时的state
需注意一次状态一次操作，即state->action->new_state(根据action后的栈顶元素决定)
例子：在reduce阶段可以认为是（pop+push）然后进入新状态。
algorithm 3（SLR）
讲看follow来构造configuration set改为根据看lookahead，更加细粒化，其他没有什么不一样的
5.优先级precedence
不是通过更改语法来实现，而是给算法增加额外规则，也就是人为增加何时reduce or shift，以减少此类冲突情形。