- 1、本文档共28页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
武汉理工大学计算机科学系陈天煌 第6章 自底向上优先分析法 【预习思考】 ◇ 什么是自底向上语法分析的策略? ◇ 什么是移进-归约分析? ◇ 移进-归约过程和自顶向下最右推导有何关系? ◇ 自下而上语法分析成功的标志是什么? ◇ 什么是可归约串? ◇ 移进-归约过程的关键问题是什么? ◇ 如何确定可归约串? ◇ 如何决定什么时候移进,什么时候归约? ◇ 什么是简单优先文法?什么是算符优先文法? ◇ 简单优先分析是如何识别可归约串的? ◇ 简单优先分析法的优缺点和局限性有哪些? 【学习目标】 简单优先分析法是自下而上(自底向上)语法分析的一种,特别适合于表达式的语法分析,由于它的算法简单直观易于理解,因此,也是学习其它自下而上语法分析的基础。 通过本章学习大家应掌握: ◇ 对给定的文法能够判断该文法是否是简单优先文法 ◇ 对给定的简单优先文法能够判断该文法是否是简单优先文法 ◇ 对给定的简单优先文法能构造简单优先关系表,并能利用简单优先优先关系表判断该文法是否是简单优先文法。 ◇ 能应用简单优先分析算法对给定的输入串进行移进-归约分析,在分析的每一步能确定当前应移进还是归约,并能判断所给的输入串是否是该文法的句子。 ◇ 了解简单优先分析法的优缺点和实际应用中的局限性。 【学习指南】 简单优先分析法是自下而上语法分析的一种,它的算法简单、直观、易于理解,所以通常作为学习其它自下而上语法分析的基础。 为学好本章内容,同学们应复习有关语法分析的知识,如:什么是语言、文法、句子、句型、短语、简单短语、句柄、最右推导、规范归约基本概念。 【重难点】 ◇ 通过本章学习后,同学们应该能知道简单优先文法的形式。 ◇ 对一个给定的简单优先文法能构造简单优先关系分析表,并能判别所给文法是否为简单优先文法。 ◇ 分清规范句型的句柄和最左素短语的区别,进而分清算符优先归约和规范归约的区别。 6.1 概述 原理:在采用自左向右扫描,自底向上分析的前提下,该类 分析方法是从输入符号串入手,通过反复查找当前句 型的句柄(最左简单短语),并使用文法的产生式把 句柄归约成相应的非终极符来一步步地进行分析的。 最终把输入串归约成文法的开始符号,表明分析成功。 自底向上分析方法的关键就是要找出当前句型的句柄(或是它的变型),然后根据产生式判别将它归约成什么样的非终极符号。 下面,我们结合具体的实现方法,介绍在分析过程中如何来识别句柄的。我们首先介绍自底向上分析的一般过程,再介绍两种常用的分析技术:简单优先分析法和LR分析方法。 第6章 自底向上优先分析法 一、自底向上分析的一般过程: 先设置一个寄存符号的栈(寄存句型前端),称为分析栈。其作用是用来记录分析的历史和指示分析的下一步动作。 分析进行时,把输入符号一个一个地按扫描顺序移进栈中,当栈顶符号形成一个句柄(即为某产生式的右部)时,就进行一次归约,即把栈顶构成句柄的那个符号子串用相应的产生式左部符号来替换。 接着再检查在栈顶是否又出现了新的句柄,则再进行归约,直至整个输入符号串处理完。 最终如果栈顶为文法的开始符号,则所分析的输入符号串为合法的符号串,报告分析成功。 否则,是不合格的符号串,报告错误。 例:给定文法G(E):E→E +T |T T→T*F | F F→i| (E)并假定输入串为(i+i)*i,考察自底向上的分析过程。 二、分析过程图表: 为了具体实现上的方便,我们仍统一约定以“#”作为输入串的左右分界符(开始和结束标志)。作为初始状态,先将符号串的开始标志“#”压入分析栈中,作为栈底符号,则分析过程为: 步骤 分析栈 输入串 动作 # (i+i)*i# 移进 #( i+i)*i# 移进 #(i +i)*i# 归约 #(F +i)*i# 归约 #(T +i)*i# 归约 #(E +i)*i# 移进 #(E+ i)*i# 移进 #(E+i )*i# 归约 #(E+F )*i# 归约 E→E +T |T T→T*F | F F→i| (E
您可能关注的文档
- 文明施工措施概要.docx
- 文明习惯养成教育主题班会概要.ppt
- 腰腿痛诊断分析资料.ppt
- 文明宿舍班会概要.ppt
- 调剖堵水技术简介概要.ppt
- 调试监理细则概要.doc
- 调味品(HS21039090)2015-2016中国(848个)出口商排名概要.docx
- 调心滚子轴承使用说明书1概要.ppt
- 调研材料小流域综合治理实施方案概要.doc
- 调研山东一等奖队长分享的资料:挑战杯学术论文、大学生社会实践调查报告的写作概要.ppt
- [专精特新]金华永和氟化工有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]重庆升光电力印务有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]无锡巨力重工股份有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]江西凯安新材料集团股份有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]浙江永昌电气股份有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]苏州中创铝业有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]杭州汽轮铸锻有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]浙江美声智能系统有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]汕头市虹桥包装实业有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]江西亚中电子科技股份有限公司行业竞争力评级分析报告(2023版).pdf
最近下载
- 2023河南郑州航空港经济综合实验区管委会招聘14人高频笔试、历年难易点考题(共500题含答案解析)模拟试卷.docx
- 2024-2030年中国双皮奶市场专题研究及市场前景预测评估报告.docx
- abaqus中英菜单对照.docx VIP
- AI技术在提高课堂效率中的应用教学研究课题报告.docx
- 10S505柔性接口给水管道支墩图集.docx
- 2023-2024年中医肛肠学(副高)考试高频题库(历年考点版)带答案解析篇.docx VIP
- 2023年中医肛肠学(副高)历年考试高频考点试题带答案解析.docx VIP
- 2023-2024年中医肛肠学(副高)考试高频题库(历年考点版)带答案解析版.docx VIP
- 2023-2024年中医肛肠学(副高)考试参考题库(历年高频考点版)带答案解析篇.docx VIP
- 七年语文《世说新语》二则课内外文言文比较阅读(原卷版+解析版).docx VIP
文档评论(0)