Compilers_Chapter4总结

唉，好久没看了，周日大概看完了第四章。
第四章是语法分析。还是比较传统的。无非是CFG，LL，LR那一套。没有看到新的东西。
我觉得第四章对于出错处理说得太简略了。

主要内容如下：
1、Parser是什么。Parser将词法分析返回的token作为输入，并把这些token看作是一个上下文无关文法的终结符。Parser原则上会通过构造一棵分析树来分析输入token的语法结构，当然，这个树不一定真的构造出来。
2、上下文无关文法：。任何一本计算理论导引之类的书上都有更详细的介绍。
3、自顶向下和自底向上分析。顾名思义，这两种分析器构造分析树的顺序是由树根->树叶，和由树叶->树根。
4、程序设计语言文法的规定，不要太诡异，要让分析器好过一点。具体来说，LALR语法就好了，最多LR文法。
5、递归下降分析器和LL(1)分析器。这两个东西本质上是一样的。很适合（和后面的LR类分析器相比）手工实现，N.Wirth（好像是这么拼的名字）专门写过一本小册子，大概一百多页，用来讲述如何手工写这两种分析器，那个东西写得很清晰。这两个分析器都属于预测分析器，对可分析的文法有较高的要求。
6、移进/规约分析器。常见的包括LR（0），SLR（1），LALR（1）和LR（1）。分析能力严格递增。它们的区别是
    LR(0)：没有lookahead，只记录栈顶的最后一个handle的信息；
    SLR(1)：在LR(0)的基础上，增加一个符号的lookahead（也就是当前的输入符号）；
    LR(1)：由一个lookahead（当前输入符号），记录栈内已有的所有信息；
    LALR(1)：合并LR(1)状态集合中所有拥有相同“core”的状态，如果出现冲突，则该文法不是LALR文法；
7、可行前缀指的是文法的一个最右句型的一个前缀，并且该前缀不能包含当前handle之后的符号。
8、可行项目指的是用于生成当前handle的生成式对应的项目，并且当前的可行前缀包含所有项目中“点”左边的符号，不包含任何“点”右边的符号。
9、二义性文法是有用的，并且在某些特别的情况下也可以同过额外的规则来北LR类分析器处理。但是需要小心，这个特性不能被滥用，否则得不偿失。主要会用到它的语法结构是表达式结构和if else结构。
10、错误处理只是大概介绍了“panic-mode”和“phrase-level”两种。前者在遇到语法错误时，会跳过若干输入，分析器假装得到了一个正确的规约，然后，从一个“同步点”继续进行下去；后者则试图纠正遇到的错误，比如修改栈或输入等。使用后者的时候，一定要确认不会使分析器陷入无限的循环中。比如，可以通过确保每一步至少消耗一个输入符号，在输入到达结束时，每一步至少减少一个栈符号来保证。
11、LR（1）和LALR(1)，SLR(1)探测到错误的时机不同。在LR(1)遇到错误的输入时，立刻就会探测到错误，而LALR(1)和SLR(1)则可能多做若干个规约操作。但是，它们都保证不会将错误的符号“移进”栈中。
12、yacc是一个分析器生成器，用于生成LALR分析器。（我记得bison可以生成LR分析器，当然，它也主要生成LALR分析器）。