本文为笔者原创，转载请注明出处
http://blog.csdn.net/xinghongduo
语法分析器
语法分析器(grammar parser)是编译器的核心部分之一，它的作用是检测词法分析器返回的token序列是否符合文法定义的规则。一个完整的语法分析器除了检测语法正确性外还要包含对出错的处理以及错误恢复等功能。
文法和文法类型
文法是定义一个语言的所有规则的集合，形式上定义为四元组G={VT,VN,S,P}，其中：
VT是非空有限符号集合，它的每个符号称为终结符，文法产生的语言由终结符构成。
VN也是非空有限符号集合，它的每个符号称为非终结符，非终结符可以继续推导。
S是一个非终结符，是文法的开始符号。
P是该文法的所有产生式的集合。
在形式语言理论中，乔姆斯基(Chomsky)将文法分为4种类型：0型，1型，2型和3型。
0型文法中每个产生式都是形如α->β，其中α,β∈(VN∪VT)*，α中至少包含一个非终结符。任何0型文法的语言都是可递归枚举的。
1型文法称为上下文有关文法，它的产生式形如αAγ->αβγ，其中α,γ∈(VN∪VT)*，只有A出现在α和γ的上下文中，才能用产生式αAγ->αβγ推导，因此它是上下文有关的。C++的文法就属于该类型，LR分析法不适用于上下文有关文法。
2型文法又称为上下文无关文法，它的产生式形如α->β，其中α∈VN，β∈(VN∪VT)*。只要推导过程中出现了非终结符α，就能用产生式α->β推导，与α的上下文无关。当前绝大多数程序设计语言的文法都属于2型文法。
3型文法又称为正规文法，它的产生式形如A->aB，A->a称为右线性文法，或A->Ba，A->a称为左线性文法。正则表达式的文法属于3型文法。
语法分析方法
目前语法分析的常用方法有自顶向下分析和自底向上分析两类。
自顶向下分析思想是从文法的开始符号出发试图推导出与输入的单词完全匹配的句子。具体分为确定的自顶向下分析和不确定的自顶向下分析。不确定的自顶向下分析在扫描当前符号时无法判断应该用哪个产生式推导，只能依次尝试每种可能，如果中途推导失败可能需要回溯尝试用其他可能的产生式重新推导，过程类似于穷举，效率很低实际几乎不用。使用确定的自顶向下分析要保证文法必须是LL(k)型文法，即向前查看k个符号就能唯一确定用哪个文法规则进行推导。确定的自顶向下分析包括递归下降分析法和预测分析法。递归下降分析法很简单，针对每个产生式手工编写分析它的子程序，然后根据当前扫描符号判断应该调用哪个子程序推导，每个子程序内还可以直接进行对语义的处理，它的优点是对于产生式较少的文法实现起来快速直接易懂，缺点是对文法的限制较多，但对于简单的文法，递归下降分析法是最直接的。确定的自顶向下分析的另一种方法是预测分析法，与递归下降分析法相比，预测分析法不需要针对每个语法规则编写分析程序，通过分析栈和构造的预测分析表，只使用通用的分析程序即可完成语法分析，且分析过程中没有递归调用。
自底向上分析又称移进-归约分析，其基本原理是对输入符号串从左至右扫描，并将输入字符逐个压入栈中(移进)，如果发现栈顶形成某个句型的句柄或可规约串时，就用相应的产生式左部的非终结符替代栈中的右部符号串(归约)。重复这个过程直到栈中只剩下文法开始符号则分析成功。本文重点介绍的是自底向上分析中的LR(k)分析法，它由Knuth(高德纳)于1965年提出，LR(k)分析法的能力强大且对文法的限制很少，k=1时几乎就可以分析任何编程语言的语法，而且LR分析的速度非常快，扫描一遍即可完成分析过程，复杂度是线性的。比较常用的LR类分析法包括SLR(1)，LR(1)，LALR(1)，Yacc就是基于LALR(1)的语法分析器生成器。LR分析同时也是编译原理中的难点之一，下面笔者将从基础的LR(0)讲起，以及进一步扩展为LALR(1)的原理。
首先通过一个例子展示自顶向下分析和自底向上分析的过程：
文法G
S->A
A->aAb
A->a
输入串aaaabbb
产生式A->aAb与A->a在面临符号a时不能确定使用哪个产生式推导，还需要再向前查看一个符号才能确定，因此该文法是LL(2)的，利用确定的自顶向下分析的推导过程为：
而自底向上分析的过程为：
LR(0)分析
LR分析的思想基于DFA，其核心在于每个DFA状态的构造。knuth给出了由文法直接构造出DFA的方法，为深入理解该方法的原理，我们先从NFA开始，尝试自行推导出直接构造DFA的方法。
对于一个右部长度为n的产生式，我们可以把它分为n+1个状态，每个状态表示一个分析进度。例如产生式A->abBc可以分解为如下5个状态：
A->·abBc
A->a·bBc
A->ab·Bc
A->abB·c
A->abBc·
·符号之前表示已经分析的符号，之后的是待分析的符号。如果·符号已经到达产生式末尾则表示该产生式的右部已经分析完毕，可以用该产生式归约。我们可以把产生式右部作为一个特殊的字符串构造出识别它的自动机，而对于串中的终结符其实就是自动机中的一条边，对于非终结符由于可以向下推导因此需要将它作为子自动机的起始。
文法G
S->E
E->aA
E->bB
A->cA
A->d
B->cB
B->d
首先构造识别每个非终结符的ε-NFA，所有·在产生式末尾的状态都是接受状态：
识别文法起始产生式S->E的ε-NFA，接受状态表示分析成功：
识别E->aA和E->bB的ε-NFA：
识别A->cA和A->d的ε-NFA：
识别B->cB和B->d的ε-NFA：
上图ε-NFA中红色标记的N(α)不是一个状态，它表示跳转到识别非终结符α的自动机起始。而NFA在匹配过程中可能同时到达多个状态，也就表示此时的输入对应多种可能的推导，对于这种情况我们可以继续读入符号，直到到达状态唯一。如果自动机读入某个符号后到达了唯一的接受状态，那么就确定了归约产生式，然后我们可以以此产生式归约。
由于有穷状态自动机不能保存之前的分析状态，对于A->·αβ，α∈VN，为使非终结符α分析完毕后状态到达A->α·β，我们需要将有穷状态自动机扩展为能力更强的下推自动机(PDA)，下推自动机在有穷自动机的基础上增加了保存分析过程的栈，每次状态转换不仅要参考有穷自动机，还要参考栈中的状态，并且要将得到的状态集压栈。
利用构造的ε-NFA分析输入串accd的过程：
下推自动机中状态栈中保存了每次转后的状态集，每次利用产生式α->β归约时，先是在状态栈pop出|β|个状态集，然后再用栈顶状态集进行一次符号为α的转换，例如上述分析过程中A->d归约，状态集{15}先出栈，然后对{12,10,11,14}进行符号为A的转换得到{13}。以上的分析是基于不确定型的有穷自动机，我们可以利用子集构造法将该ε-NFA转化为DFA，NFA中的每个可达状态集对应着DFA的一个状态，所以上述分析过程中得到的每个状态集其实就是DFA的一个状态，下面我们列出了几个状态集中的每个状态对应的分析进度和转换关系，看看能有什么发现。
状态集{5,10,11,14}，{12,10,11,14}，{15}，{6}，{13}分别表示的分析进度和之间的转换关系，蓝色为归约状态
上图中可以看出，对于DFA中的两个状态s和t，若s经过符号a转换到t，那么对于s中所有面临符号a的产生式α->γ·aβ经过符号a后α->γa·β都属于t，·符号不在起始位置的产生式称为该状态的核。而对于DFA的每个状态s，若产生式α->γ·β属于s，其中β是非终结符，则以β为左部的所有产生式β->·δ也都属于s，除DFA起始状态，其他状态中·符号在首部的产生式都是由该状态的核扩展的，因此判断DFA中的两个状态是否等价则等于判断这两个状态的核是否相同。根据上述思路，我们可以由文法起始产生式S->·E作为核，首先扩展出DFA的起始状态，然后对于每个已经扩展的状态，扫描每个状态对于每个符号的转换是否能产生新的状态，直到所有状态对于所有符号都不能产生新的状态为止，最终得到完整的DFA，这也是knuth给出的直接构造DFA的方法。
识别文法G的完整DFA
上图构造的DFA又称为文法G的LR(0)项目集规范族，每个DFA状态称为一个项目集，每个项目集中的每个产生式称为一个项目，若某个项目集中包含·符号在末尾的项目，则表示该项目集是待归约的(蓝色标记)，一旦到达该状态则需要用对应项目的产生式归约，归约完成后还需要对栈顶状态进行一次该产生式左部符号的转换。利用DFA分析的过程与上面ε-NFA分析输入串的过程是相似的，只不过由于DFA状态转换是确定的，因此状态栈保存的不是状态集，只保存一个状态即可。
LR分析器结构
实际的分析过程中我们不需要知道每个项目集中的具体项目，只需知道每个状态集对于每个符号的转换动作，因此可以将项目集规范族转化为二维分析表，LR分析器的分析表由ACTION表和GOTO表组成，ACTION表用于描述每个状态对于每个终结符的动作，移进还是归约。例如状态3对于终结符c转换到状态7，则置ACTION(3, c) = S7，其中的S7表示移进到状态7，而状态6为归约状态，则对所有终结符β置ACTION(6,β) = R2，其中R2表示用第2个产生式归约。GOTO表描述每个状态对于每个非终结符的转换，例如状态7对于非终结符B转换到状态10，则置GOTO(7, B) = 1。分析表中添加了输入结束符号#，状态1接受#符号为acc，表示全部分析完毕。
构造文法G的LR(0)分析表，无动作表示分析错误
若文法G的LR(0)项目集规范族中每个待归约的项目都自为一个项目集，则称文法G为LR(0)文法，LR(0)文法中每个构造的LR(0)项目集的动作都是确定的，不需要向前查看符号就能确定转换动作，LR(0)对文法限制较多，多数程序设计语言的文法都不是LR(0)的。
SLR(1)分析
某些文法在构造它的LR(0)项目集时，对于某个项目集中可能同时存在待移进和待归约项目，这样就不能确定该项目集的动作。如果某个项目集中包含多个待归约项目，基于LR(0)分析法是不能判断应该用哪个产生式归约的，此冲突称为归约--归约冲突，如果某个项目集中包含了待移进和待归约的项目，也是无法确定该项目集何时移进何时归约，此冲突称为移进--归约冲突。为解决这两种冲突，SLR(1)通过向前查看一个符号试图使动作确定化，它也是相对实用的分析法，多数程序设计语言存在SLR(1)的文法。
文法G
S->A
A->BC
B->bCb
B->ε
C->cBc
C->ε
构造G的LR(0)项目集规范族如下：
在构造的LR(0)项目集规范族中，黄色标记的项目集0,2,3,5中都存在待移进和待归约的项目，对于LR(0)分析这些项目集中是存在移进--归约冲突的，为描述SLR(1)分析解决冲突的策略，下面介绍两个基本定义。
FIRST集
对于文法中的符号α，FIRST(α)表示以α为起始所能推导的第一个终结符的集合。若α为终结符，则FIRST(α)就等于α。如果α为非终结符，过程则复杂一些，需要反复扫描左部为α的每个产生式α->βγ，根据定义可得FIRST(β)属于FIRST(α)，如果β可以直接或者间接推导出空，那么FIRST(γ)也属于FIRST(α)。FIRST集合的计算过程存在依赖关系，需要反复扫描每个符号的产生式，直到每个非终结符的FIRST集都不再变化为止。
文法G中每个非终结符的FIRST集
FIRST(S) = {b,c}
FIRST(A) = {b,c}
FIRST(B) = {b}
FIRST(C) = {c}
FOLLOW集
FOLLOW(α)表示所有可能在非终结符α后出现的第一个终结符的集合，它的计算过程依赖于FIRST集。对于产生式γ->αβδ，符号β跟在符号α后，因此FIRST(β)属于FOLLOW(α)，若β可以直接或间接推导出空，那么FIRST(δ)也属于FOLLOW(α)。由于有γ符号都可由γ->αβδ向下推导，若α后面的所有符号都可以直接或间接推导出空，那么FOLLOW(γ)也属于FOLLOW(α)。FOLLOW集计算过程也是存在依赖关系的，还是需要反复扫描，直到所有非终结符的FOLLOW集都不再变化为止。
对于文法初始符号S，令符号#属于FOLLOW(S)，#表示输入终止符号。
文法G中每个非终结符的FOLLOW集
FOLLOW(S) = {#}
FOLLOW(A) = {#}
FOLLOW(B) = {c,#}
FOLLOW(C) = {b,#}
若分析到达状态中含有待归约项目α->βγ·，且下一个输入符号属于FOLLOW(α)，则表示当前需要用α->βγ归约。对于一个存在冲突的LR(0)项目集，若该项目集中所有待归约产生式左部符号的FOLLOW集交集均为空，并且与所有待移进终结符的交集也为空，那么该项目集中的冲突是可以通过FOLLOW集解决的。若对于每个存在冲突的LR(0)项目集都可通过FOLLOW集解决冲突，则称该文法是SLR(1)的。
了解了SLR(1)解决冲突的策略，下面我们用FOLLOW集来解决上面构造的LR(0)项目集中的冲突。
项目集0中待移进的终结符集为{b}，待归约项目左部符号B的FOLLOW集为{c,#}，{b}∩{c,#} =φ，对符号b置ACTION(0,b)=S3，对符号c和#置ACTION(0,c)=R3，ACTION(0,#)=R3。
项目集2中待移进终结符集为{c}，待归约项目左部符号C的FOLLOW集为{b,#}，交集也为空，对符号c置ACTION(2,c)=S5，对符号b和#置ACTION(2,b)=R5，ACTION(2,#)=R5。
项目集3和5同理，最后构造的SLR(1)分析表如下。
LR(1)分析
对于产生式δ->αγ，α∈VN，γ∈VT，若以α向下推导，那么在到达包含α->β·的项目集时只有下一个输入符号为γ时才需要以α->β归约，而SLR(1)的做法是下一个输入符号只要属于FOLLOW(α)就归约，对于该推导来说FOLLOW(α)中除γ外其他符号的归约都是无效的。LR(1)分析在构造每个项目集中的项目时标记出了每个项目的归约符号集，到达归约状态时只有下一个输入符号属于该项目的规约符号集才归约，这样确保了LR(1)分析中每个归约都是有效的。由于LR(1)分析中对于项目的归约符号集是该项目左部符号FOLLOW集的子集，项目集中产生冲突的可能性比SLR(1)低，因此能适应更多的文法，实际上LR(1)分析也是这几种LR类分析中能力最强的。
LR(1)与LR(0)分析主要的区别在对于每个项目集的构造，LR(1)项目集的构造过程是：对于初始LR(1)项目集，令输入结束符号#作为文法起始产生式的归约符号集。对于LR(1)项目集中的项目α->·βγ，δ，其中δ表示该项目的归约符号集，如果β是非终结符，则β的所有产生式β->μ，λ都属于该项目集，若γ可以直接或间接推导出空，则λ等于FIRST(γ)与δ的并集，否则λ等于FIRST(γ)。
构造了初始LR(1)项目集后，依次考察每个已经构造的项目集，查看该项目集对于每个符号的转换是否能产生新的项目集，直到构造出所有LR(1)项目集。需要注意的是，LR(1)项目集等价必须同时满足两个条件，包含项目一致且一致项目的归约符号集相同。
文法G
S->A
A->aBd
A->bBc
A->aec
A->bed
B->e
构造文法G的LR(1)项目集规范族：
LR(1)分析表对于待移进项目的构造方法与SLR(1)分析表相同，而对于LR(1)待归约的项目，只有当输入符号属于该项目的归约符号集时才进行归约。根据上图的LR(1)项目集规范族构造的LR(1)分析表如下：
LR(1)虽然能力强大，但对于较为复杂的文法在构造LR(1)项目集规范族时可能会引起项目集数量的急剧增长，例如C99标准文法的LR(0)项目集不到400个，而对应的LR(1)项目集超过1万个，不仅构造时间长，而且更大的分析表将占用更多的内存，因此LR(1)更多的是理论价值，对于规则较少的文法还可以应用，而对于规则很多的文法就不适用了。
LALR(1)分析
LALR(1)是对LR(1)的改进，为解决LR(1)项目集过多的问题，LALR(1)将构造的LR(1)项目集规范族中核心相同的项目集合并，合并后的项目集称为LALR(1)项目集，若合并后的每个LALR(1)项目集内都没有冲突，则称文法为LALR(1)文法。由于LR(1)相同核心的项目集合并时可能会产生归约--归约冲突，因此LALR(1)的能力弱于LR(1)，而对于待归约的项目LALR(1)也是根据该项目的归约符号集归约，因此LALR(1)的能力强于SLR(1)。LALR(1)项目集的数量与SLR(1)相同，且对文法的适应能力并不比LR(1)差很多，因此它是一个实用的方法，目前绝大多数LR类分析器构造工具都是基于LALR(1)的。
文法G
S->A
A->BB
B->aB
B->b
构造文法G的LR(1)项目集规范族
在该LR(1)项目集规范族中，核心相同的项目集有{2,6}，{3,7}，{5,9}，分别将其合并，得到如下LALR(1)项目集规范族
合并后的每个LALR(1)项目集中都没有冲突，因此文法G属于LALR(1)文法，LALR(1)分析表的构造过程与LR(1)相同，因此不再描述。
对于构造LALR(1)项目集规范族的实现，我们不必先构造出全部的LR(1)项目集后再对同心项目集合并，这种方式的效率是很低的，LALR(1)项目集其实就是对应的LR(0)项目集增加了每个项目的归约符号集，因此我们可以先构造出LR(0)项目集规范族，然后再确定每个项目的归约符号集，这种方法可以高效的构造出LALR(1)项目集规范族。
二义性文法
根据上几节介绍的原理，我们已经可以编写出一个较为实用的无二义性语法分析器构造器，而实际应用中，编写一个复杂语言的无二义性文法是较为困难的，为使构造器的能力更强大，我们需要加入对二义性文法的支持。任何一个二义性文法都不属于LR类文法，但对于描述同一种语言的二义性文法和无二义性文法，二义性文法的规则通常更少且更容易理解，而对于二义性文法，我们可以指定冲突项目集中的动作从而消除二义性。
Yacc中通过以下几个关键字设置结合性
%left 左结合
%right 右结合
%nonassoc 无结合性，查看待归约项目与移进符号能否结合，如果不能结合则放弃移进符号的动作转换
%prec 指定产生式优先级，exp : ‘-’ exp %prec UMINUS表示该产生式的优先级与UMINUS相同。
定义文法时我们可以指定终结符的优先级和结合性，每个项目的优先级与其右部最后一个存在优先级的终结符相等。
对于项目集中的移进--归约冲突，Yacc将先比较优先级，如果优先级不同则选择优先级高的符号动作，如果优先级相同则查看待移进符号的结合性，左结合则归约，右结合则移进，否则将选择移进动作并给出警告。
对于项目间的归约--归约冲突，Yacc将选择优先级高的项目归约，若项目优先级相等则默认用最先定义的产生式归约并给出警告。
以一个描述加法和乘法规则的二义性文法为例
S -> E
E -> E + E
E -> E * E
E -> i
构造G的LALR(1)项目集规范族
G的LALR(1)项目集规范族中，项目集5和6内都存在移进归约冲突。对于项目集5，待归约项目E->E+E·，{+,*,#}的优先级等于+的优先级，根据乘法和加法规则的定义，*的优先级大于+，而+与*都是左结合的，因此如果下一个输入符号为+则应该归约，为*应该移进。
对于项目集6，待归约项目E->E*E·，{+,*,#}的优先级等于*的优先级，而待移进符号+的优先级低于*，因此如果下一个输入符号为+则应该归约，对于待移进符号*，虽然优先级相等，但由于*是左结合因此对于输入符号*也应该归约。
根据上述解决冲突的策略，我们可以通过删除归约符号或待移进项目从而消除项目集中的冲突，修改后的LALR(1)项目集规范族如下，红色标记的是删除的项目或符号。
语法制导翻译
LR分析器利用产生式α->β归约时总是先在栈顶pop出|β|个状态，这是因为对于所有符号的状态转换，无论是终结符还是非终结符，在状态栈中都只表示为一个状态，待归约产生式右部每个符号的状态转换在状态栈中的相对位置与产生式中的相对位置总是保持一致，因此我们可以增加一个语义值栈保存分析过程中每个符号的语义值，在归约时根据产生式符号的相对位置来进行语义值的计算。对于每个产生式我们可以在产生式后编写归约时执行的语义子程序，LR分析器执行归约动作时就会执行对应的语义动作子程序，自底向上的计算出最终的语义值，这就是语法制导翻译的基本原理。利用语法制导翻译可以使我们很容易的构造出语法树，以便进行后续的处理。
Yacc中以符号$操作语义值栈，以规则E : E + E { $$=$1+$3; };为例，$$表示归约后语义值栈栈顶的值，$1表示对归约前第一个符号E的语义值引用，$3表示对归约前第三个符号E的语义值引用。如果状态栈栈顶下标为top，待归约产生式长度为len，则$k其实就是语义值栈中下标为top-len+k的元素引用。下面以二义性文法小节中的文法为例，展示分析输入串2+2*3+1过程中语义值栈的变化。
通过语法制导翻译，我们在语法分析结束后就得到了最终的语义值，上图中绿色部分为符号栈，黄色部分为语义值栈，该示例中语义值栈元素类型为整型，而实际应用可以为自定义类型，以便构造出语法树进行后续的处理。
错误恢复
朴素的LR分析器遇到错误后会立即停止分析，而实际中我们希望语法分析器能找出所有语法错误而不仅仅是第一个错误，因此分析器遇到错误时就需要一种错误恢复策略使分析器回到正常的分析中，恢复的原理比较简单，无非是状态栈中弹出若干状态，然后丢弃若干输入符号使分析器能将出错的部分正常归约。例如C语言中;号标记着一个语句的结束，如果分析语句过程中出现错误，我们可以弹出状态栈到该语句对应文法起始状态，并且丢弃输入流符号直到遇到符号;为止，然后像没出过错误一样正常执行归约动作以保证分析过程继续下去。
Yacc中保留了一个名为error的终结符，我们可以利用error符号编写容错的产生式。当遇到语法错误时，分析器将先判断当前栈顶状态能否移进error符号，如果不能则会不断pop状态栈，直到栈顶状态可以移进error符号为止，然后Yacc将移进error符号并标记分析进入错误处理状态，如果状态栈pop到空都不能移进error符号则分析器将终止分析，错误处理状态中必须连续移成功移进三个符号YACC才认为恢复到了正常状态。下面我们以一个例子来展示错误恢复的过程。
文法G
S -> E
E -> E * i
E -> i
该文法描述的语言是n个i(n>0)相乘的表达式，如果我们输入表达式ii*ii**i，分析器肯定是会报告语法错误的，不过我们可以利用error符号使得对于这种输入分析器都能正常工作。
添加如下容错产生式
E -> E * error i
E -> error i
构造G的LALR(1)项目集规范族
分析输入串ii*ii**i
