1、第五章 语法分析 -自下而上分析5.1自底向上分析的一般过程： 移进 -归约分析5.1.1 规范归约5.2 算符优先分析5.3 LR分析法5.4 语法分析器的自动产生主要内容若若 Z S 则则 S L(GZ) 否则否则 S L(GZ) +GZ自底向上分析算法的基本思想：自底向上分析算法的基本思想：存在主要问题存在主要问题 : 可归约串的识别问题可归约串的识别问题主要方法主要方法 : 算法优先分析法算法优先分析法 LR分析法分析法5.1 自底向上分析的一般过程v 所谓自顶向上分析法就是从输入串开始，利用有关规则逐步进行 “归约 ”，又称为移进 -归约分析法。v 特点： 边移进边归约。移进 归约分
2、析结构# 分析器#符号 栈输 入串要点 ：建立 符号栈 ，用来纪录分析的历史和现状，并根据所面临的情况，确定下一步动作是 移进 还是 归约 。分析过程分析过程 ：把输入符号串按描述顺序一一地把输入符号串按描述顺序一一地 移进移进 符号栈（一次移一个符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号形成），检查栈中符号，当在栈顶的若干符号形成 当前句型当前句型 的的句柄句柄 时，就根据规则进行时，就根据规则进行 规约规约 ，将句柄从符号栈中弹出，将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形
3、成新的句柄，若有就再进行然后再检查栈内符号串是否形成新的句柄，若有就再进行规约，否则移进符号。分析一直进行到读到输入串的右界规约，否则移进符号。分析一直进行到读到输入串的右界符为止。最后，若栈中仅含有符为止。最后，若栈中仅含有 左界符号和识别符号左界符号和识别符号 ，则表，则表示分析成功，否则失败。示分析成功，否则失败。# 分析器分析器#符号符号 栈栈输输 入串入串归约 （回顾）推导定义1.直接推导 “” 是文法 G的产生式，若有 v,w满足：v=,w= , 其中 V *,V *(V代表字母表 )则 称 v直接 推导 到 w,记作 v w也称 w直接 归约 到 v例 ： G： S 0S1， S
4、 010S1 00S11 00S11 000S111 000S111 00001111 S 0S1v 如果移进归约过程是自顶向下 最右推导 的逆过程，则称为规范归约。v 如对最右推导 S A 来说， 一定有 A 规则存在 ， 将句型 中的 用产生式的左部符号代替便得到新句型 A，这是一次规范归约，恰好与规范推导相反。5.1.1 规范归约*v 对应的规范归约过程 :abbcde AbaAbcde AAbaAcde BdaAcBe SaAcBeS归约为开始符号，是合法句子。Sa A c B cA bbd句子 abbcde的 最右推导过程：S aAcBe aAcde aAbcde abbcde文法G
5、S:SaAcBeAAb|bBd例对应的自下而上分析过程符号 栈 输 入符号串 动 作 abbcde 移 进 a bbcde 移 进 ab bcde 归约 (Ab ) aA bcde 移 进 aAb cde 归约 (AAb ) aA cde 移 进 aAc de 移 进 aAcd e 归约 (Bd ) aAcB e 移 进 aAcBe 归约 (SaAcBe ) S 接受在移进 -归约过程中，何时归约？何时移进？v 不能只看到栈顶出现某一产生式的右部就用相应产生式归约，如在第 5步时，栈中符号是 aAb，栈顶符号串 b,Ab都是产生式的右部符号，这时到底用Ab 还是 AAb 归约不能确定。v 为此引入了 可归约串 的概念。自下而上分析主要问题v 主要问题 识别 “可归约串可归约串 ”。v 对 “可归约串 ”概念的不同定义，就形成了不同的自下而上的分析方法。 在 “规范归约 ”中，则用 “句柄句柄 ”来刻画 “可归约串 ”。 在算符优先分析法中我们用 “最左素短语最左素短语 ”来刻画 “可归约串 ”；
