第四章 语法分析-自上而下分析

《第四章 语法分析-自上而下分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、程序设计语言编译原理主讲：张永梅课程安排内容讲授课时实验课时第一章引论2第二章高级程序语言及其语法描述2第三章词法分析实验一词法分析器（第6、7、8、9周）108第四章语法分析----自上而下分析8第五章语法分析----自下而上分析实验二语法分析器（第13、14、15、16周）88第六章属性文法和语法制导翻译8第七章语义分析及中间代码产生8第八章优化2合计4816实验时间：实验一词法分析：第6、7、8、9周实验二语法分析：第13、14、15、16周实验地点：计算机系实验中心（5教910、911）指导教师：杨健、张谦

2、实验安排杨健：13488702754张谦：18801041780邮箱：bigjordon@126.com地点：五教8层802图像处理研究室数字媒体制作实验室910计11-12软件开发实验室911计11-34第6、7、8、9周，都是周二1,2节实验一词法分析器（第6、7、8、9周）第四章语法分析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序第四章语法分析-自上而下分析了解：语法分析器的功能。熟悉：预测分析程序、递归下降分析程序的设计方

3、法。掌握：LL(1)分析法的条件，消除左递归的算法，预测分析表的构造。第四章语法分析-自上而下分析作业：4.1，4.24.1考虑下面文法G1:S→a∣∧∣(T)T→T,S∣S（1）消去G1的左递归。然后对每个非终结符，写出不带回溯的递归子程序。（2）经改写后的文法是否是LL(1)的？给出它的预测分析表。第四章语法分析-自上而下分析4.2对下面的文法G：E→TEE→+E∣εT→FTT→T∣εF→PFF→*F∣εP→(E)∣a∣b∣∧（1）计算这个文法的每个非终结符的FIRST和FOLLOW。（2）证明这

4、个文法是LL(1)的。（3）构造它的预测分析表。（4）构造它的递归下降分析程序。第三章词法分析实验一词法分析器每次实验结束都必须写出实验报告，报告内容包括：实验题目、实验目的和要求，实验的实现（包括主要设计思想、实现算法、主要技术问题的处理方法，及实验结果），结论分析。实验二语法分析器实验二语法分析器构造一、目的和要求借助于词法分析程序提供的分析结果，编写一个算符优先语法分析程序，程序能进行语法结构分析和错误检查并产生相应的归约信息。同时给出出错信息和错误类型，从而加深对语法分析的理解。二、实验内容给定文法G和

5、算符优先分析法，构造其算符优先分析程序。文法G：语句→赋值语句｜条件语句｜转移语句｜带标号的赋值语句带标号的赋值语句→<标号><赋值语句>赋值语句→变量=算术表达式条件语句→IF<布尔表达式>THEN语句｜IF<布尔表达式>THEN语句ELSE语句实验二语法分析器构造转移语句→GOTO标号变量→标识符标识符→字母｜<标识符><数字>字母→A｜B｜…｜Z｜a｜b｜…｜z数字→0｜1｜…｜9算术表达式→项｜算术表达式+项｜算术表达式-项项→因子｜项*因子｜项/因子｜因子↑项因子→变量｜常数｜(表达式)布尔表达

6、式→<算术表达式><关系符><算术表达式>关系符→>｜<｜>=｜<=｜=｜<>标号→常数常数→数字｜<常数><数字>实验二语法分析器构造三、说明和提示1.本实验的优先表可以手工先设计好。2.本实验要求中提出的“产生相应的归约信息”意指在语法分析的过程中，一旦产生归约，在程序上产生并最终输出归约产生式序号。3.出错类型的产生可预先对应优先表中出错栏列表说明其出错类型，并分别编序，当分析中产生错误时以字符串输出相应表中错误信息。4.算法采用一个符号栈的数据结构，既用它存放终结符，也用它存放非终结符。第四章语法分

7、析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序中间代码单词符号语法单位中间代码目标代码词法分析器语法分析器语义分析与中间代码产生器优化器源程序表格管理出错处理目标代码生成器编译程序总框本章主要介绍语法分析的处理要进行语法分析，必须对语言的语法结构进行描述。采用正规式和有限自动机可以描述和识别语言的单词符号；用上下文无关文法来描述语法规则。第四章语法分析-自上而下分析形式化定义：一个上下文无关文法是一个四元式（VT,VN,S,Ｐ）V

8、T是一个非空有限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=ф；S是一个非终结符号，称为开始符号；S∈VN。Ｐ是一个产生式集合（有限），每个产生式的形式是P→а。其中，P∈VN，а∈(VT∪VN)＊。开始符号S必须至少在某个产生式的左部出现一次。P→а1

9、а2

10、…

11、аn。其中，аi称为是P的一个候选式。→读作“