3.4自下而上语法分析【例】回顾：一个简单的归约过程3.4.1自下而上语法分析的原理“移进-归约”分析法３、“移进-归约”分析法的栈实现“移进–归约”分析器使用一个栈和一个存放输入符号串w的缓冲器。分析器的初始状态为:栈输入＃w＃工作过程：自左至右把串w的符号一一移进栈里，一旦栈顶形成可归约的串（如句柄）时，就进行归约。这种归约可能持续多次，直至栈顶不再呈现句柄为止。然后，继续向栈里移进符号，重复这个过程，直至最终形成如下格局：栈输入＃S＃小结分析器的四种动作修剪语法树实现归约的演示“移进—归约”语法分析小结从输入串的开始依次读入单词(移进栈中)。一旦发现可归约串(某个产生式的右端)就立即归约。归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进。若最终能归约成文法的开始符号，则分析成功（接受）；否则出错。由于总是将句型的最左边的可归约串替换成非终结符，该方法通常得到是最右推导。关键：如何识别可归约的符号串？通过不同的自下而上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。自下而上语法分析主要有以下三种方法①简单优先分析法(规范归约)——文法按一定原则规定文法符号的优先关系。②算符优先分析法(非规范归约)——规定算符之间的优先关系。③LR分析法（规范归约）——LR(0)、LR(1)、SLR(1)和LALR(1)。规范归约相关概念复习练习有文法如下:E→E+T|TT→T*F|FF→(E)|id分析输入串id+id*id，给出对该句子进行“移进-归约”语法分析的过程。栈输入缓冲区动作#id+id*id#移进#id+id*id#归约F→id#F+id*id#归约T→F#T+id*id#归约E→T#E+id*id#移进#E+id*id#移进#E+id*id#归约F→id#E+F*id#归约T→F#E+T*id#移进#E+T*id#移进#E+T*id#归约F→id#E+T*F#归约T→T*F#E+T#归约E→E+T#E#接受E→E+T|TT→T*F|FF→(E)|id移进归约分析过程中存在的问题3.4.2算符优先分析法1、算符文法:一个上下无关文法G,如果没有P→,且没有P→...QR...(P,Q,R属于非终结符),则G是一个算符文法。2、算符优先关系的定义：假定G[S]是一个不含产生式的算符文法，对于任何一对终结符a和b，有：①ab，当且仅当G[S]中有P→...ab...或P→...aQb...的产生式(在同一产生式中)②ab，当且仅当G[S]中有P→...aR...的产生式,且R=>b...或R=>Qb...(注意ab相邻)③ab,G中有P→...Rb...的产生式,且R=>...a或R=>...aQ(注意ab相邻)【例】有文法G[E]:E→E+E|E*E|(E)|i证明该文法不是算符优先文法。因为：E→E+E，EE*E则有+*又因为：E→E*E,EE+E则有+*所以不是算符优先文法。算符优先关系表的构造由F→(E)得(=)G[E]的算符优先关系表：在优先表中，空白部分是一种错误关系。相同的终结符之间的优先关系不一定是。如果有ab,不一定有ba(不具传递性)，因为算符优先只定义了相邻运算符之间的优先关系。当a,b相邻时，不一定b,a相邻。a,b之间未必有优先关系、和。1、FIRSTVT集合定义：对每个非终结符P,FIRSTVT(P)={a|P=>a...或P=>Qa...,a∈VT,Q∈VN}2、LASTVT集合定义：LASTVT(P)={a|P=>...a或P=>...aQ,a∈VT,Q∈VN}3、构造优先关系表如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。若产生式右部有...aR...的形式,则对于每个b∈FIRSTVT(R)都有ab。若产生式右部有...Rb的形式,则对于每个a∈LASTVT(R)集,都有ab。若产生式形如P→…ab…或P→…aQb…形式，则有ab。【例3.11】文法G[E]:E→E+T|TT→T*F|FF→(E)|i试构造其算符优先表。２、构造LASTVT集。(1)根据规则①可知：由E→…+T得LASTVT(E)={+};由T→…*F得LASTVT(T)={*};由F→…)和F→i得LASTVT(F)={),i};(2)根据规则②可知：由LASTVT(F)={),i}和T→F得LASTVT(T)={*,),i};由LASTVT(T)={*,),i}和E→T得LASTVT(E)={+,*,),i}。3、构造优先关系表。(1)根据规则①可知,由“(E)”得（）。