第五章 语法分析——自下而上分析
知识总结与感受：
自下而上分析过程：边输入单词符号，边归约。核心问题：识别可归约串
规范归约的定义：假定a是文法G的一个句子，我们称序列an，an-1，，a0是a的一个规范归约，如果此序列满足： (1) aan= aa (2) aa0为文法的开始符号，即aa0=S (3) 对任何i，0 < i <= n， aai-1是从aai经把句柄替换成为相应产生式左部符号而得到的。句柄:一个句型的最左直接短语称为该句型的句柄。
如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一： a=.b
a>.b
a<.b
则称G是一个算符优先文法(OPG文法)。
构造算符优先关系表
(1)通过检查产生式的每一个候选式可以找出满足a=.b
（即P→…ab…或P→…aQb…的产生式）
(2)为了满足<.和>.，需对G中每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：
(3)构造集合FIRSTVT(P)的算法
按其定义，可用下面两条规则来构造集合FIRSTVT(P)：
① 若有产生式P→a…或P→Qa…，
则aÎFIRSTVT(P)；
② 若aÎFIRSTVT(Q)，且有产生式P→Q…，
则aÎFIRSTVT(P)。
(4)同理构造构造集合LASTVT(P)的算法
按其定义，可用下面两条规则来构造集合LASTVT(P)：
① 若有产生式P→… a或P→… aQ ，
则aÎ LASTVT(P)；
② 若aÎ LASTVT(Q)，且有产生式P→… Q ，
则aÎ LASTVT(P)。
(5)有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系<.和>.的所有终结符对。
(1)假定有个产生式的一个候选形为
…aP…
那么，对任何bÎFIRSTVT(P)，有a <. b。
(2)假定有个产生式的一个候选形为
…Pb…
那么，对任何aÎLASTVT(P)，有a >. b。
素短语：指一个句型的短语，它至少包括有一个终结符号且除去它本身之外不再含任何更小的素短语。
最左素短语：处在句型最左端那个素短语成为最左素短语。
算符优先分析算法和设计
(1)句型的一般表示形式：
#N1a1N2a2…NnanNn+1#
其中，每个ai都是终结符，Ni是可有可无的非终结符
(2)定理：
一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 Njaj…NiaiNi+1， aj-1 <. aj aj =. aj+1，aj+1 =. aj+2，…，ai-1 =. ai ai >. ai+1
注意：
出现在左端或右端的非终结符一定属于这个素短语
LR分析方法
LR分析方法是一种自下而上的分析方法
LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程
LR分析方法是一种适用于一大类上下文无关文法的分析方法
比较复杂，不适于用手工实现，可借助于YACC/bison实现
根据归约过程中向前看输入符号串中字符的个数，定义不同LR(k)分析方法，通常，k=0，1
动作表：
ACTION[s，a]： 当状态s面临输入符号a时，应采取什么动作
状态转换表：
GOTO[s，X]： 状态s面对文法符号X时，下一状态是什么
LR文法
一个文法,如果能构造出一个所有条目都唯一的分析表。
LR(k)文法
最多向前看K个的符号就可以决定动作的LR分析器所分析的文法成为LR(k)文法。
我们最感兴趣的是k=0,1
活前缀：文法G的活前缀是他的规范句型的前缀，该前缀不超过句柄的右端。
规范句型的这种前部分符号串称为可归前缀。
我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀。
活前缀特点:
该前缀加上被分析串中未被分析的终结符，就可以构成一个规范句型
只要输入串的已扫描部分可归约成一个活前缀，意味着扫描过的部分没有错误
(1)活前缀中已含有句柄的全部符号(句柄的符号即为其最右符号)。
(2)活前缀中含句柄的一部分符号(句柄开头的 若干符号与活前缀最右的若干个符号一致)。
(3)活前缀中全然不包含句柄的任何符号 。
构造识别活前缀的NFA
1、构造文法的所有产生式的项目，每个项目都为NFA的一个状态。
2、确定初态、句柄识别态、句子识别态。
由于S′（起始符）仅在第一产生式的左部出现 ，因此规定起始符相关的项目1为初态
其余每个状态都为活前缀的识别态(终态)
圆点在最后的项目为句柄识别态
第一个产生式的句柄识别态为句子识别态
LR(0)项目集规范族不存在移进-归约，或归约-归约冲突，称为LR(0)文法。
只有是LR(０)文法，才能构造相应的LR(0)分析表，才能用LR(0)分析法对句子进行分析。
构造LR(1)项目集的闭包函数
A)I的项目都在CLOSURE(I)中。
B)若[A→a•Bb，a]属于CLOSURE(I)，B→g是文法的产生式，bÎV*，bÎFIRST(ba)，则[B→•g，b]也属于CLOSURE(I)。
C)重复B)直到CLOSURE(I)不再扩大。
LALR分析表的构造
1 构造文法G的LR（1）项目集族
2 合并同心集
3 构造action 表：
a)若项目[A→a•ab,b]属于Ik，且转换函数GO(Ik，a)=Ij，当a为终结符时 ，则置ACTION[k，a]为Sj。
b)若项目[A→a•,a]属于Ik， 则置ACTION[k，a]=rj， j为产生式在文法G′中的编号。
C)若[s’->.s, #]属于Ik,则置ACTION[k，#]接受
4 goto表的构造：
若Jk是I1I2I3…合并后的同心集，GO（I，X）也同心，因此定义GO函数为：GOTO[k，A]=j，其中A为非终结符，j为某一状态号。
同心集合并后心仍相同，只是超前搜索符集合为各同心集超前搜索符的和集合并同心集后转换函数自动合并。
LR(1)文法合并同心集后也只可能出现归约-归约冲突，而没有移进-归约冲突。
二义文法的优点：
1 如果修改运算符的优先级和集合性的话，无须修改文法
这一章学习了自下而上的语法分析，与上一章的自上而下分析的LL文法相反。本章还学习了规约，算符优先分析等内容。本章内容比之前有明显的增加，理解起来更加繁琐。用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，所谓自下而上分析法就是从输入串开始，通过“边输入边规约”逐步进行“规约”，直到规约到文法的开始符号。
课后题总结：