




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、编译原理和技术,大连理工软件学院 胡 彦 ,本讲纲要,自下而上分析概述 自下而上分析方法 LR分析器,自下而上分析概述,重要概念 归约 句柄,归约,归约,是自下而上分析中的重要动作 归约,对应着最右推导的逆过程,a,b,b,c,d,e,A,A,B,S,S aABe A Abc | b B d,文法:,abbcde,aAbcde,aAde,aABe,S,rm,rm,rm,rm,句柄,句柄的非形式定义 句型的句柄,是该句型中与一个产生式右部匹配的字符串,文法: S aABe A Abc | b B d,可能在最右推导的过程中出现的句柄有那些呢?,aABe Abc b d,句柄,句柄的精确定义 右句
2、型的句柄是一个产生式的右部,并且该句柄在用A替换中的句柄之后,得到的是最右推导中的前一个句型 令=,则可以通过产生式A- 归约为句型A,abbcde,aAbcde,rm,aAAcde,rm,aAAcde不是文法的右句型,b是不是句柄?,所以aAbcde中的b不是句柄!,如果b是句柄,那么意味着存在这一步推导,所有能够在最右推导中出现的句型,称为右句型,文法: S aABe A Abc | b B d,句柄,句柄的特性 句柄的右边都是终结符(或者句柄右边没有任何符号),假设,存在句型B,并且是句柄,可以通过产生式A-进行归约,这意味着什么?,存在下面的推导 A B =rmB,问题何在?,不是最右
3、推导!,结论:句型的右边不可能 出现非终结符,句柄,句柄的特性 句柄的右边都是终结符(或者句柄右边没有任何符号) 在文法有二义的时候,句柄可能不唯一(因为对某个句子,可能存在两个最右推导),本讲纲要,自下而上分析概述 自下而上分析方法 LR分析器,分析的方法,处理的对象:句子(由终结符组成的串),id1 * id2 + id3,句子中符号的扫描方向是从左到右,分析的过程,所有的步骤与动作,id1,id2,id3,*,+,$,初始状态:栈里面只有一个$,动作:,移进一个终结符,E E + E | E * E | (E ) | E | id,栈,句子,分析的过程,所有的步骤与动作,id1,id2,
4、id3,*,+,$,目前状态:栈里面已经识别的串是id1,扫视一下表达式文法,看看有没有形成句柄,E E + E | E * E | (E ) | E | id,E id,id是一个句柄,动作:,利用E id进行归约,分析的过程,所有的步骤与动作,E,id2,id3,*,+,$,目前状态:栈里面已经识别的串是E,归约之后,E不是句柄,E E + E | E * E | (E ) | E | id,动作:,移进下一个终结符*,分析的过程,所有的步骤与动作,E,id2,id3,*,+,$,目前状态:栈里面已经识别的串是E*,E*不是句柄,E E + E | E * E | (E ) | E | i
5、d,动作:,移进下一个终结符id2,分析的过程,所有的步骤与动作,E,id2,id3,*,+,$,目前状态:栈里面已经识别的串是E*id2,有没有句柄出现?,E E + E | E * E | (E ) | E | id,动作:,利用产生式E id进行归约,id2是句柄,分析的过程,所有的步骤与动作,E,E,id3,*,+,$,目前状态:栈里面已经识别的串是E*E,有没有句柄出现?,E E + E | E * E | (E ) | E | id,动作:,移进终结符+,E*E是产生式E E *E 的句柄, 但同时我们也可以选择继续移进,当栈顶出现句柄的时候, 可以选择归约动作,也可以 选择移进动
6、作,怎么选择?暂且留着疑问, 等后面将具体的分析技术时 再讨论一下,分析的过程,所有的步骤与动作,E,E,id3,*,+,$,目前状态:栈里面已经识别的串是E*E+,有没有句柄出现?,E E + E | E * E | (E ) | E | id,动作:,移进终结符id3,没有!,分析的过程,所有的步骤与动作,E,E,id3,*,+,$,目前状态:栈里面已经识别的串是E*E+id3,有没有句柄出现?,E E + E | E * E | (E ) | E | id,动作:,利用产生式E id进行归约,有!,分析的过程,所有的步骤与动作,E,E,E,*,+,$,目前状态:栈里面已经识别的串是E*E
7、+E,有没有句柄出现?,E E + E | E * E | (E ) | E | id,动作:,利用产生式E E + E进行归约,有!,分析的过程,所有的步骤与动作,E,E,*,$,归约后状态:栈里面已经识别的串是E*E,有没有句柄出现?,E E + E | E * E | (E ) | E | id,动作:,利用产生式E E * E进行归约,有!,分析的过程,所有的步骤与动作,E,$,归约后状态:栈里面已经识别的串是E,E E + E | E * E | (E ) | E | id,串已经归约到开始符号E,并且 输入的终结符在这个过程中已经被消耗完毕,3.4 自下而上分析,3.4.3 用栈实
8、现移进归约分析 分析器的四种动作: 移进动作 把下一个输入符号压栈。 归约动作 分析器知道整个句柄已经完全出现在栈顶,它确定句柄的左端在栈中的位置,再决定采用哪个非终结符来代替句柄(即确定使用哪个产生式)。 接受动作 分析器宣告分析成功。 报错动作 分析器发现了语法错误,调用错误恢复例程。,分析表的作用是:确定分析的下一步动作是移进还是归约,如果是归约,那么应用使用那个产生式进行归约,3.4 自下而上分析,使用移进归约方式,即使知道了应该进行归约,也还有两个问题必须解决,他们是 确定右句型中将要归约的子串 如何确定选择哪一个产生式,3.4 自下而上分析,3.4.4 移进归约分析的冲突 移进归约
9、冲突,归约乎?,移进乎?,如果移进归约分析器处于格局 栈 输入 if expr then stmtelse $,例 stmt if expr then stmt | if expr then stmt else stmt | other,两难啊!,3.4 自下而上分析,归约归约冲突 stmt id (parameter_list) | expr := expr parameter_list parameter_list, parameter | parameter parameter id expr id (expr_list) | id expr_list expr_list, expr |
10、 expr,用paramter id归约?,用expr id归约?,不容易抉择呢!,由A(I, J)开始的语句 栈输入 id ( id, id ),本讲纲要,自下而上分析概述 自下而上分析方法 LR分析器,LR分析器,LR分析器处理的是一类LR(k)文法 k指的是决定分析动作的时候向前看的符号个数 k=1时可以省略,表示分析的时候只要往前看1个符号 LR分析器采用的方法称为LR分析方法 LR分析方法是自下而上分析的一种,也是最为有效的一种,在深入LR分析方法的探讨之前,我们需要引入一个新的概念,活前缀,活前缀,文法例子,S aABe A Abc | b B d,自下而上分析时,栈中可能出现的串
11、: a ab aA aAb aAbc aAd aAB aABe S,活前缀定义: 对于任一文法GS,若S =*A=, 若 是的前缀,则称是G的一个活前缀,活前缀与句柄的关系,文法例子,S aABe A Abc | b B d,栈中可能出现的串: a ab aA aAb aAbc aAd aAB aABe S, 活前缀已含有句柄的全部符号,表明产生式A的 右部已出现在栈顶。,出现句柄(对应A-b),出现句柄(对应A-Abc),出现句柄(对应B-d),出现句柄(对应S-aABe),活前缀与句柄的关系,文法例子,S aABe A Abc | b B d,栈中可能出现的串: a ab aA aAb a
12、Abc aAd aAB aABe S, 活前缀已含有句柄的全部符号,表明产生式A的 右部已出现在栈顶。,出现产生式A-Abc右端的一部分, 期望从输入串中看到bc,出现产生式S-aABe的右端一部分, 期望从输入串中看到e, 活前缀只含句柄的一部分符号如1表明A12的右部子串1 已出现在栈顶,当前期待从输入串中看到2推出的符号。,出现产生式A-Abc右端的一部分, 期望从输入串中看到c,活前缀与句柄的关系,文法例子,S aABe A Abc | b B d,栈中可能出现的串: a ab aA aAb aAbc aAd aAB aABe S, 活前缀已含有句柄的全部符号,表明产生式A的 右部已出现在栈顶。,出现符号A推出的符号串,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- “醉驾”型危险驾驶罪综合治理模式的实践探索与反思
- 农村供水绩效管理办法
- 标准化管理下的消毒供应中心质量控制体系构建与实践
- 民政小区车辆管理办法
- 小学篮球社团活动方案
- 220kV变电站工程试运行流程与解析
- 古代文学专题:经典文本与思想传承研究
- 公共平台建设管理办法
- 大豆籽粒营养成分与豆乳品质的关系分析
- 高考期间食堂食品安全保障措施
- 2024年江苏三支一扶真题
- 《危险货物港口作业重大事故隐患判定指南》解读与培训
- 主、被动防护网施工方案-图文
- 2025年初中语文文学常识:常考100题汇编
- 君易和文化课件
- 药食同源106种25年4月更新
- 2025年江苏省南通市中考英语适应性试卷(A卷)
- 无机盐在化妆品行业的应用研究考核试卷
- 猪场生产安全
- 2025年度苗圃土地承包合同-观光树种植与生态旅游产业链投资合作框架
- 《城市供水》课件
评论
0/150
提交评论