- 1、本文档共66页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
编译原理 第六章 算符优先分析法【优质】
第章 算符优先分析法
课前索引
【课前思考】 ◇ 什么是自下而上语法分析的策略? ◇ 什么是移进-归约分析? ◇ 移进-归约过程和自顶向下最右推导有何关系? ◇ 自下而上语法分析成功的标志是什么? ◇ 什么是可归约串? ◇ 移进-归约过程的关键问题是什么? ◇ 如何确定可归约串? ◇ 如何决定什么时候移进,什么时候归约? ◇ 什么是算符文法?什么是算符优先文法? ◇ 算符优先分析是如何识别可归约串的? ◇ 算符优先分析法的优缺点和局限性有哪些? 【学习目标】 算符优先分析法是自下而上(自底向上)语法分析的一种,尤其适应于表达式的语法分析,由于它的算法简单直观易于理解,因此,也是学习其它自下而上语法分析的基础。通过本章学习学员应掌握: ◇ 对给定的文法能够判断该文法是否是算符文法 ◇ 对给定的算符文法能够判断该文法是否是算符优先文法 ◇ 对给定的算符文法能构造算符优先关系表,并能利用算符优先关系表判断该文法是否是算符优先文法。 ◇ 能应用算符优先分析算法对给定的输入串进行移进-归约分析,在分析的每一步能确定当前应移进还是归约,并能判断所给的输入串是否是该文法的句子。 ◇ 了解算符优先分析法的优缺点和实际应用中的局限性。【学习指南】 算符优先分析法是自下而上语法分析的一种,它的算法简单、直观、易于理解,所以通常作为学习其它自下而上语法分析的基础。为学好本章内容,学员应复习有关语法分析的知识,如:什么是语言、文法、句子、句型、短语、简单短语、句柄、最右推导、规范归约基本概念。【难 重 点】 ◇ 通过本章学习后,学员应该能知道算符文法的形式。 ◇ 对一个给定的算符文法能构造算符优先关系分析表,并能判别所给文法是否为 算符优先文法。 ◇ 分清规范句型的句柄和最左素短语的区别,进而分清算符优先归约和规范归约的区别。 ◇ 算符优先分析的可归约串是句型的最左素短语,在分析过程中如何寻找可归约串是算符优先分析的关键问题。对一个给定的输入串能应用算符优先关系分析表给出分析(归约)步骤,并最终判断所给输入串是否为该文法的句子。 ◇ 深入理解算符优先分析法的优缺点和实际应用中的局限性。【知 识 点】
短语、直接短语、句柄的定义: 文法G[S], S αAδ且A β则称β是句型α β δ相对于非终结符A的短语。 若有Aβ则称β是句型α β δ相对于A或规则A → β的直接短语。 一个句型的最左直接短语称为该句型的句柄。 算符优先分析法是一种自底向上分析方法,也称移进-归约分析法,粗略地说它的实现思想是对输入符号串自左向右进行扫描,并将输入符逐个移入一个后进先出栈中,边移入边分析,一旦栈顶符号串形成某个句型的句柄时,(该句柄对应某产生式的右部),就用该产生式的左部非终结符代替相应右部的文法符号串,这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功,也就确认输入串是文法的句子。本章将在介绍自底向上分析思想基础上,着重介绍算符优先分析法。 栈顶符号串是指该符号串包含栈顶符号在内,并由栈中某个符号为该符号串的头,栈顶符号为该符号串的尾,也可以只有一个栈顶符号。
6.1 自底向上分析概述自底向上分析法,也称移进-归约分析法,或自下而上分析。现举例说明。
例6.1
?
设文法G[S]为: (1) S→aAcBe (2) A→b (3) A→Ab (4) B→d 对输入串abbcde#进行分析,检查该符号串是否是G[S]的句子。 由于自底向上分析的移进-归约过程是自顶向下最右推导的逆过程,而最右推导为规范推导,自左向右的归约过程也称规范归约。 容易看出对输入串abbcde的最右推导是: SaAcBeaAcdeaAbcdeabbcde 由此我们可以构造它的逆过程即归约过程。 先设一个先进后出的符号栈,并把句子左括号#号放入栈底,其分析过程如表6.1。
表6.1 用移进-归约对输入串abbcde#的分析过程
f6-1-1.swf
图6.1 自底向上构造语法树的过程
推倒的逆过程为:SaAcBeaAcdeaAbcdeabbcde
对上述分析过程也可看成自底向上构造语法树的过程,每步归约都是构造一棵子树,最后当输入串结束时刚好构造出整个语法树,图6.1(a)(b)(c)(d)给出构造过程,可与表中相应分析步骤对照。 在上述移进-归约或自底向上构造语法树的过程中,我们怎么知道何时移进,何时归约,不能只简单地看成栈顶出现某一产生式的右部就可用相应产生式归约,例如在表6.1分析到第5)步时栈中的符号串是#aAb,栈顶符号串b和Ab分别是产生式(2),(3)的
您可能关注的文档
- 编译原理课程设计_算符优先分析法研究__附源程序.doc
- 网上书店电子商务系统规划分析设计报告毕业设计(论文)word格式.doc
- 网络团购的发展现状与问题探究[任务书 文献综述 开题报告 毕业论文].doc
- 网络时代的企业管理新模式供应链管理.ppt
- 网络广告的特点研究[任务书 文献综述 开题报告 毕业论文].doc
- 网上书店电子商务系统规划分析设计报告毕业设计(论文).pdf
- 网上支付与结算 教学课件 ppt 作者 王生辉 王俊杰 主编 第四章 网络银行与网上支付.pdf
- 网络谣言.ppt.ppt
- 网页设计与制作——dreamweaver8教学课件配套课件马书群第1章网站策划与分析.pdf
- 网页设计与制作——dreamweaver8教学课件配套课件马书群第8章静态网站综合实例.pdf
文档评论(0)