[工学]编译原理 之 LR分析程序及其构造.ppt

第7章ＬＲ分析程序及其构造 自下而上分析及其LR分析概述 LR (0) 分析 SLR(1) 分析 LR（1）分析 LALR分析 使用二义文法 自底向上分析方法是一种移进--归约过程. 分析栈的栈顶符号形成句柄时--归约. 自底向上分析方法的关键问题--确定句柄. LR分析的归约过程是规范（最右）推导的逆过程. LR分析过程是一种规范（最左）归约过程. LR分析方法对文法的限制少，速度快. LR分析器的构造工作量大. 7.1 自下而上的语法分析概述 例：文法G： S → cAd A → ab A → a识别输入串w=cabd是否该文法的句子 (1) S → cAd (2) A → ab (3)A → a识别输入串w=cabd是否为该文法的句子自下而上的语法分析 对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在cAbd中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子. 在自下而上的分析方法中如何识别可归约串？ 在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串” c A b d a 刻画“可归约串” 文法G[S] 句型的短语 S αAδ且 A β，则称β是句型αβδ相对于非终结符A的短语 句型的直接短语 若有A ? β，则称β是句型αβδ相对于非终结符A 的直接短语 句型的句柄 一个句型的最左直接短语称为该句型的句柄 例 ：i*i+i 的短语、直接短语和句柄 E E + T T F T * F i3 短语：i1* i2+ i3， i1* i2 ， F i2 i1 ， i2 ， i3 。 i1 直接短语： i1 ， i2 ， i3 。句柄： i1 自下而上的语法分析在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串” 算符优先－选择“可归约串”是最左素短语（至少含有一个终结符的最左边的短语，且这个短语不包含别的短语） 规范归约－选择“可归约串”是句型的句柄 G[E]：E→E+T|T T→T*F|F F→(E)|i 句型 i*i+i 的自下而上分析，总是归约当前句型的句柄形成的规范推导序列： E?E+T?E+F?E+i?T+i?T*F+i?T*i+i?F*i+i? i*i+i 句型 i*i+i 的自下而上分析总是归约当前句型的最左素短语形成的推导： E?T+F?T+i?F*F+i?F*i+i? i*i+i ＬＲ分析器模型  LR分析使用两张表 ACTION表 告诉分析器：栈顶状态为S, 当前输入符号是a时做什么: 1. ACTION[S,a]= Sj 2. ACTION[S,a]=rj (第j条产生式为A??) 3. ACTION[S,a]=acc 4. ACTION[S,a]= error GOTO表 GOTO[S,A]栈顶状态为S，归约之后的非终结符為A时，要放到栈顶的新状态 7.2 LR(0) 分析 构造DFA识别规范句型特定前缀(就到句柄为止). LR(0)项目集规范族的构造 LR(0)分析表的构造 LR(0)语法分析过程 7.2.1可归前缀、活前缀 例: G[S]: S ?aAcBe [1] A ?b[2] A ?Ab[3] B ?d[4] w=abbcde# 推导过程 S ?aAcBe[1] ?aAcd[4]e[1] ?aAb[3]cd[4]e[1] ?ab[2]b[3]cd[4]e[1] 每次归约前句型的前部分依次为: ab[2] aAb[3] aAcd[4] aAcBe[1] 把规范句型的这种前部分串称为可归前缀。 句柄位于可归前