第5章自底向上的语法分析5.1自底向上的语法分析概述例5.1一个简单的归约过程语法分析树的生成演示5.1.1移进-归约分析移进-归约语法分析器的总体结构与LL(1)的体系结构比较移进-归约分析的工作过程输出结果表示：用产生式序列表示语法分析树动作栈输入缓冲区分析器的四种动作移进-归约分析中的问题动作栈输入缓冲区移进-归约分析中的问题5.1.2优先法5.1.3状态法5.2算符优先分析法算术表达式文法的再分析算符文法5.2.1算符优先文法5.2.1算符优先文法例：E→E+E|E-E|E*E|E/E|(E)|id证明不是OPG文法。因为：E→E+E，EE*E则有+≮*又因为：E→E*E,EE+E则有+≯*所以不是算符优先文法。5.2.2算符优先矩阵的构造算符优先关系矩阵的构造构造FIRSTOP(B)和LASTOP(B)的算法文法Ge：(1)E→T(2)E→E+T(3)E→E-T(4)T→F(5)T→T*F(6)T→T/F(7)F→(E)(8)F→id例5.6表达式文法的算符优先关系5.2.3算符优先分析算法问题素短语与最左素短语例素短语与最左素短语算符优先分析的实现算符优先分析算法文法G[E]：E→T|E+T|E-T|E*E|E/E|EE|(E)|id5.2.4优先函数表5.2对应的优先函数：优先函数的构造例5.10Ges:E→E+T|TT→T*F|FF→id5.2.5算符优先分析的出错处理算符优先分析法小结5.3LR分析法5.3.1LR分析算法LR语法分析器的总体结构LR分析表：action[s,a]；goto[s,X]LR分析器的工作过程LR分析器的工作过程s0s1…sm#X1…Xmaiai+1…an#LR分析算法10．elseifaction[S,a]=rkthen/*ri表示按第k个产生式A→β归约*/11．begin12．从栈顶弹出2*|β|个符号；13．令S'是现在的栈顶状态；14．把A和goto[S',A]先后压入栈中；15．输出产生式A→β16．end17．elseifaction[S,a]=accthen18．return19．else20．error();例5.12bab的分析过程:1)S→BB2)B→aB3)B→b规范句型活前缀规范句型活前缀5.3.2LR(0)分析表的构造项目的意义拓广(Augmented)文法构造识别G的所有规范句型活前缀的DFA项目集I的闭包（Closure）CLOSURE(I)=I∪{B→.γ|A→α.Bβ∈I,B→γ∈P}算法J:=I;repeatJ=J∪{B→.η|A→α.Bβ∈J,B→η∈P}untilJ不再扩大闭包之间的转移状态转移的计算识别拓广文法所有规范句型活前缀的DFA计算LR(0)项目集规范族Ｃ即：分析器状态集合例4-13S→BBB→aBB→bLR(0)分析表的构造算法LR(0)不是总有效的I0:S’→.SS→.AS→.BA→.aAcA→.aB→.bBdB→.b项目集I的相容I0:S’→.SS→.AS→.BA→.aAcA→.aB→.bBdB→.b5.3.3SLR(1)分析表的构造算法识别表达式文法的所有活前缀的DFAI0:E’→.EE→.E+TE→.TT→.T*FT→.FF→.(E)F→.id表达式文法的LR(0)分析表含有冲突表达式文法的SLR(1)分析表si表示移进到状态i,ri表示用i号产生式归约SLR(1)分析的特点SLR(1)分析的局限性I0:S’→.SS→.L=RS→.RL→.*RL→.idR→.LSLR分析中的冲突——需要更强的分析方法SLR分析中存在冲突的原因5.3.4LR(1)分析表的构造后继符(搜索符)的概念LR(k)项目LR(1)项目的有效性识别文法全部活前缀的DFA闭包的计算闭包的计算闭包的计算状态I和文法符号X的转移函数计算LR(1)项目集规范族Ｃ即：分析器状态集合识别活前缀的关于LR(1)的DFALR(1)分析表的构造LR(1)分析表的构造2024/10/35.3.5LALR(1)分析表的构造LALR(1)的分析能力5.3.6二义性文法的应用5.3.6二义性文法的应用5.3.7LR分析中的出错处理LR分析的基本步骤5.4语法分析程序的自动生成工具Yacc用Yacc和Lex合建编译程序本章小结