编译原理教材配套课件---哈尔滨工业大学独立博客服务.ppt

《编译原理教材配套课件---哈尔滨工业大学独立博客服务.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、SchoolofComputerScience&TechnologyHarbinInstituteofTechnology重点：自底向上分析的基本思想，算符优先分析法的基本思想，简单算符优先分析法。LR分析器的基本构造思想，LR分析算法，规范句型活前缀及其识别器——DFA，LR(0)分析表的构造，SLR(1)分析表的构造,LR(1)分析表的构造。难点：求FIRSTOP和LASTOP，算符优先关系的确定，算符优先分析表的构造，素短语与最左素短语的概念。规范句型活前缀，LR(0)项目集闭包与项目集规范族，它们与句柄识别的关系，活前缀与句柄的关系,LR(1)项目集闭包与项目

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

3、bB→d句子分析：abbcdeaAbcd

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

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

6、E*E

7、(E)

8、id2021/8/2211动作栈输入缓冲区1)#id1+id2*id3#i

9、d+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)接受E2021/8/2212分析器的四种动作1)移进：将下一输入符号移入栈2)归约：用产生式左侧的非终结符替换栈顶的句柄（某产生式右部）3)接受：分析成功4)出错：出错处理？？决定移进和归约的依据是什么—回头看是否可以找到答案

10、2021/8/2213移进-归约分析中的问题1)移进归约冲突例5.2中的6)可以移进*或按产生式E→E+E归约2021/8/221412)接受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#E动作栈输入缓冲区2021/8/2215移进-归约分析中的

11、问题1)移进归约冲突例5.2中的6)可以移进*或按产生式E→E+E归约2)归约归约冲突存在两个可用的产生式各种分析方法处理冲突的方法不同如何识别句柄？如何保证找到的直接短语是最左的?利用栈如何确定句柄的开始处与结束处？2021/8/22165.1.2优先法根据归约的先后次序为句型中相邻的文法符号规定优先关系句柄内相邻符号同时归约，是同优先的句柄两端符号的优先级要高于句柄外与之相邻的符号a1…ai-1≮ai≡ai+1≡…≡aj-1≡aj≯aj+1…an定义了这种优先关系之后，语法分析程序就可以通过ai-1≮ai和aj≯aj+1这两个关系来确定句柄的头和