第五章语法分析——自下而上分析语法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序优点：直观、简单和宜于手工实现。语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约G(E)：Ei|E+E|E-E|E*E|E/E|(E)i*i+iE*i+iE*E+iE+iE+EE5.1.1归约例：设文法G(S)：(1)SaAcBe(2)Ab(3)AAb(4)Bd试对abbcde进行“移进－归约”分析。b5.1.2规范归约考虑文法G(E)：ET|E+TTF|T*FF(E)|i和句型i1*i2+i3：EE+TE+FE+i3T+i3T*F+i3T*i2+i3F*i2+i3i1*i2+i3短语：i1，i2，i3，i1*i2，i1*i2+i3直接短语：i1，i2，i3句柄：i1在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。可用句柄来对句子进行归约句型归约规则abbcde(2)AbaAbcde(3)AAbaAcde(4)BdaAcBe(1)SaAcBeS定义：假定是文法G的一个句子，我们称序列n，n-1，，0是的一个规范归约，如果此序列满足：1n=20为文法的开始符号，即0=S3对任何i，0in，i-1是从i经把句柄替换成为相应产生式左部符号而得到的。把上例倒过来写，则得到：SaAcBeaAcdeaAbcdeabbcde显然这是一个最右推导。规范归约是关于是一个最右推导的逆过程最左归约规范推导由规范推导推出的句型称为规范句型。b5.1.3符号栈的使用和分析树的表示步骤符号栈输入串动作0#i1*i2+i3#预备1#i1*i2+i3#进2#F*i2+i3#归，用F→i3#T*i2+i3#归，用T→F4#T*i2+i3#进步骤符号栈输入串动作4#T*i2+i3#进5#T*i2+i3#进6#T*F+i3#归，用F→i7#T+i3#归，用T→T*F8#E+i3#归，用E→T9#E+i3#进步骤符号栈输入串动作9#E+i3#进10#E+i3#进11#E+F#归，用F→i12#E+T#归，用T→F13#E#归，用E→E+T14#E#接受语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。归约规范归约定义：假定是文法G的一个句子，我们称序列n，n-1，，0是的一个规范归约，如果此序列满足：1n=20为文法的开始符号，即0=S3对任何i，0in，i-1是从i经把句柄替换成为相应产生式左部符号而得到的。步骤符号栈输入串动作0#i1*i2+i3#预备1#i1*i2+i3#进2#F*i2+i3#归，用F→i3#T*i2+i3#归，用T→F4#T*i2+i3#进步骤符号栈输入串动作4#T*i2+i3#进5#T*i2+i3#进6#T*F+i3#归，用F→i7#T+i3#归，用T→T*F8#E+i3#归，用E→T9#E+i3#进步骤符号栈输入串动作9#E+i3#进10#E+i3#进11#E+F#归，用F→i12#E+T#归，用T→F13#E#归，用E→E+T14#E#接受5.2算符优先分析例如：句子i+i-i*(i+i)句子i+i-i*(i+i)的归约过程是：(1)i