实验三 LL(1)语法分析程序的构造
更新时间:2023-10-30 10:16:01 阅读量: 综合文库 文档下载
- 实验三中推荐度:
- 相关推荐
LL(1)语法分析器的构造
实验目的
1 掌握LL(1)分析法的基本原理 2 掌握LL(1)分析表的构造方法 3 掌握LL(1)驱动程序的构造方法
实验任务
已知文法G[E]: E→E+T|T T→T*F|F F→(E)|i
说明:终结符号i为用户定义的简单变量, 即标识符的定义。 1、 消除文法的左递归,构造对应文法的预测分析表; 2、 根据构造的预测分析表,实现LL(1)分析中控制程序(表驱动程序),并完成整个的LL(1)
分析程序的界面设计、运行;
3.P104中,3.36写一个Yacc程序,把输入的算术表达式翻译成对应的后缀表达式输出。 要求转换正确,同时对于简单错误能够识别。
4.P104中,3.37,写一个Yacc“台式计算器”程序,它计算布尔表达式,其中的词法分析器用Lex写。要求转换正确,同时对于简单错误能够识别。
实验学时
6学时
实验要求
1、输入串应是词法分析的输出二元式序列,即某算术表达式“实验项目一”的输出结果。输出为输入串是否为该文法定义的算术表达式的判断结果。 2、LL(1)分析过程应能发现输入串中的错误。
3、设计至少两个测试用例(尽可能完备,正确和出错),并给出测试结果。
实验原理
1. 对文法要求
LL(1)分析法属于自顶向下分析方法,因此需要预测匹配的产生式。即在LL(1)分析法中,每当在符号栈的栈顶出现非终结符时,要预测用哪个产生式的右部去替换该非终结符。LL(1)分析方法要求文法满足如下条件:对于任一非终结符A,其任意两个产生式A??,A??,都要满足下面条件:First(A??)∩First(A??)=?
2. 分析表构造
LL(1)分析表的作用是对当前非终结符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终结符,列对应终结符,表中的值有两种:一是产生式的编号,一是错误编号。若用T表示LL(1)分析表,则T可表示如下: T: VN×VT?P∪{Error} T(A, t) = A?α,当t?First(A?α) T(A, t) = Error,否则
其中P表示所有产生式的集合。显然,一个文法G是LL(1)文法,当且仅当T的元素包含唯一的一个产生式或Error。
3. 驱动程序构造
LL(1)分析主要包括以下四个动作,其中X为符号栈栈顶元素,a为输入流当前字符。 ? 替换:当X?VN时选相应产生式的右部?去替换X。
? 匹配:当X?VT时它与a进行匹配,其结果可能成功,也可能失败,如果成功则符号栈中将X退栈并将输入流指针向前移动一位,否则报错。 ? 成功:当格局为(空,空)时报告分析成功。 ? 报错:出错后,停止分析。
实验步骤
1.构造LL(1)分析表
采用手工操作构造LL(1)分析表。LL(1)分析表用一个二维矩阵表示,其中每个非终结符对应一行,每个终结符对应一列,一个非终结符和一个终结符可以确定矩阵中的一个元素,元素的值表示该非终结符和该终结符对应的产生式。每个矩阵元素都是一个符号串,所有元素初始化为””;构造LL(1)表时,根据文法和各个产生式的First集,填写LL(1)分析表的内容。各产生式只要降右端填入到对应的表项中即可,用空串表示Error。在根据LL(1)分析表选择产生式进行推导时,若查到的产生式为空串表示无相应的产生式可选,不匹配错误;否则根据符号串得到相应的产生式进行推导,即进行压栈操作。
2.数据结构
LL(1)语法分析程序共用到个栈,分别称为:符号栈,语法树栈,操作符栈和操作数栈。其中,符号栈用于进行LL(1)语法分析;其它的栈是为了在语法分析的过程中同时生成与源程序结构对应的语法树而设。语法树栈用于生成声明部分和语句部分的语法树;操作符栈和操作数栈用于生成表达式部分的语法树。
3. 构造驱动程序
构造LL(1)驱动程序的算法: (1). 分析开始时,首先将标志符号#和文法开始符号S依次压入符号栈;输入流指针指向第一个输入符号,即由符号栈和输入流构成的初始格局为: (#S, a1a2...an#)
然后,反复执行第2步所列的工作。 (2). 设在分析的某一步,符号栈及剩余的输入流处于如下的格局 (#X1X2...Xm-1Xm, aiai+1...an#)
其中,X1X2...Xm-1Xm为分析过程中所得的文法符号,此时,可视栈顶符号Xm的不同情况,分别作如下动作:
? 若Xm?VN,则以Xm及ai组成的符号对(Xm,ai)查分析表T。设T(Xm,ai)为一产生式,假设是Xm?UVW,此时将Xm从分析栈中退出,并将UVW压入栈中,从而得到新的格局 (#X1X2...Xm-1WVU, aiai+1...an#) 但若T(Xm,ai)=Error,则调用出错处理程序进行处理;
? 若Xm=ai?#,则表明栈顶符号已经与当前扫描的输入符号得到匹配,此时应将Xm(即ai)从栈中退出,并将输入流指针向前移动一个位置。 ? 若Xm=ai=#,则表明输入串已经完全得到匹配,此时即可宣告分析成功而结束分析。 其它情形,转错误处理程序。
4.实验成果提交
(1)非终结符的FIRST集合 (2)、非终结符的FOLLOW集合 (3)、预测分析表 (4)、程序流程图
(5)、源代码 (要通过验收) (6)、程序运行说明及测试数据
正在阅读:
实验三 LL(1)语法分析程序的构造10-30
2016年北大金融学考研10-30
蔡英文败选感言02-16
中小学教师职称讲课答辩:微型课09-20
《环境化学》(戴树桂 第二版)课后部分习题解答和重要知识点05-18
系辞传上册注释09-22
西安交大概率论上机实验报告matlab08-06
我国高收入家庭理财方案设计研究05-21
- 小学生造句大全
- 增压泵投资项目可行性研究报告(模板)
- 高中语文人教版粤教版必修1-5全部文言文知识点归纳
- 两学一做专题民主生活会组织生活会批评与自我批评环节个人发言提
- 管理处环境保洁工作操作标准作业指导书
- 2012六一儿童节活动议程 - 图文
- 移树申请报告
- 《贵州省市政工程计价定额》2016定额说明及计算规则
- 计算机长期没有向WSUS报告状态
- 汉语拼音教学策略研究
- 发展西部领先的航空货运枢纽
- 司法所上半年工作总结4篇
- 如何提高银行服务水平
- 发电厂各级人员岗位职责
- 丰田汽车的外部环境分析
- 2017—2018年最新冀教版四年级数学下册《混合运算》教案精品优质
- 中建八局样板策划 - 图文
- 戚安邦《项目管理学》电子书
- 2015年高级项目经理笔记
- 弯桥的设计要点
- 构造
- 语法
- 实验
- 程序
- 分析
- LL
- 我国女性就业歧视的现状
- 江苏省三级妇科内镜诊疗技术管理规范
- 超市清仓甩卖广告词(共9篇)
- 五年级上册数学教案-因数和倍数 - 青岛版(2014秋)
- 2020年集团公司后勤工作计划范文
- 怀化池黔公路外业验收汇报材料 - 图文
- 4.6微生物标本采集运送标准规程
- 景区市场营销中心绩效考核方案-段丽伟
- 中国速冻食品制造中小企业生存状况市场最新调研及战略研究报告(2012-2016年)
- 最新江苏省建设工程现场用表说明(第五版)
- 辅机生产管理考核细则
- 践行数学新课标理念 培养学生应用意识
- 材料耐腐蚀性能参考表
- 2016年北大金融学考研
- 浙江选考2019届高考历史学业水平考试专题十九中外历史人物评说第46讲无产阶级革命家和杰出的科学家
- 小城镇户籍制度改革试点存在的主要问题及对策(达阅)
- 如何培养小学生语感
- 6KV低压配电系统及车间变电设计
- c2c网站方案 - 图文
- 浙江省瑞安中学2014-2015学年高二上学期期中考试历史(文) Word版含答案