编译原理课件第5章.ppt

《编译原理课件第5章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章自底向上的语法分析5.1自底向上的语法分析概述5.2算符优先分析法5.3LR分析法5.4语法分析程序的自动生成工具Yacc5.5本章小结8/27/202115.1自底向上的语法分析概述思想从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误。核心寻找句型中的当前归约对象——“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法8/27/20212例5.1一个简单的归约过程设文法G为：S→aABeA→Abc

2、bB→d句子分析：abbcdeaA

3、bcdeaAdeaABeS语法树的形成过程8/27/20213语法分析树的生成演示abbcdeAABSA→bA→AbcB→dS→aAcBe8/27/202145.1.1移进-归约分析系统框架采用表驱动的方式实现输入缓冲区：保存输入符号串分析栈：保存语法符号—已经得到的那部分分析结果控制程序：控制分析过程，输出分析结果——产生式序列格局：栈+输入缓冲区剩余内容=“句型”8/27/20215移进-归约语法分析器的总体结构id+id＊id#＋Ｅ#移进-归约控制程序输出产生式序列栈内容+输入缓冲区内容＝#“当

4、前句型”#栈输入缓冲区分析表M8/27/20216与LL(1)的体系结构比较输入缓冲区(符号序列)栈控制程序P132预测分析表M输出产生式序列8/27/20217移进-归约分析的工作过程系统运行开始格局栈：#；输入缓冲区：w#存放已经分析出来的结果,并将读入的符号送入栈，一旦句柄在栈顶形成，就将其弹出进行归约，并将结果压入栈问题：系统如何发现句柄在栈顶形成？正常结束:栈中为#S，输入缓冲区只有#8/27/20218输出结果表示：用产生式序列表示语法分析树E→idid+id*idEEEEEE→idE→idE

5、→E*EE→E+E例5.2E→E+E

6、E*E

7、(E)

8、id8/27/20219动作栈输入缓冲区1)#id1+id2*id3#id+id*id2)移进#id1+id2*id3#例5.2分析过程3)归约E→id#E+id2*id3#E4)移进#E+id2*id3#5)移进#E+id2*id3#6)归约E→id#E+E*id3#EE7)移进#E+E*id3#8)移进#E+E*id3#9)归约E→id#E+E*E#10)归约E→E*E#E+E#E11)归约E→E+E#E#12)接受E8/27/202110分析器的四

9、种动作1)移进：将下一输入符号移入栈2)归约：用产生式左侧的非终结符替换栈顶的句柄（某产生式右部）3)接受：分析成功4)出错：出错处理？？决定移进和归约的依据是什么—回头看是否可以找到答案8/27/202111移进-归约分析中的问题1)移进归约冲突例5.2中的6)可以移进*或按产生式E→E+E归约8/27/202112动作栈输入缓冲区1)#id1+id2*id3#id+id*id2)移进#id1+id2*id3#例5.2分析过程3)归约E→id#E+id2*id3#E4)移进#E+id2*id3#5)移进#

10、E+id2*id3#6)归约E→id#E+E*id3#EE7)移进#E+E*id3#8)移进#E+E*id3#9)归约E→id#E+E*E#10)归约E→E*E#E+E#E11)归约E→E+E#E#12)接受E8/27/202113移进-归约分析中的问题1)移进归约冲突例5.2中的6)可以移进*或按产生式E→E+E归约2)归约归约冲突存在两个可用的产生式各种分析方法处理冲突的方法不同如何识别句柄？如何保证找到的直接短语是最左的?利用栈如何确定句柄的开始处与结束处？8/27/2021145.1.2优先法根据归

11、约的先后次序为句型中相邻的文法符号规定优先关系句柄内相邻符号同时归约，是同优先的句柄两端符号的优先级要高于句柄外与之相邻的符号a1…ai-1≮ai≡ai+1≡…≡aj-1≡aj≯aj+1…an定义了这种优先关系之后，语法分析程序就可以通过ai-1≮ai和aj≯aj+1这两个关系来确定句柄的头和尾了8/27/2021155.1.3状态法根据句柄的识别状态（句柄是逐步形成的）用状态来描述不同时刻下形成的那部分句柄因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态例如：S→bBB可分解为如下识别状态S→.

12、bBB移进bS→b.BB等待归约出BS→bB.B等待归约出BS→bBB.归约采用这种方法，语法分析程序根据当前的分析状态就可以确定句柄的头和尾，并进行正确的归约。8/27/2021165.2算符优先分析法算术表达式分析的启示算符优先关系的直观意义+≮*+的优先级低于*(≡)(的优先级等于)+≯++的优先级高于+方法将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定句柄8/27/202117算术表达式文法