编译原理7-LR幻灯片.pptVIP

第七章 LR分析 7.1 概述 7.2 LR(0)分析 7.3 SLR(1)分析 7.4 LR(1)分析 7.5 LALR(1)分析 7.6 二义性文法在LR分析中的应用 重点讲解内容 LR分析概述 能力强 几乎所有CFG的语言结构都能用LR分析 不需要对文法附加条件 难点 几乎不可能用手工编写LR分析器 现实 有LR分析器的生成器 LR分析 属于自下而上的分析方法 移进-归约 可归约串及相关概念： 短语；直接短语；最左素短语；句柄；规范归 约——选择“可归约串”为句型的句柄 自下而上分析：通用模型 自下而上的分析：LR分析器模型 LR分析 L 从左到右扫描输入串 R 构造最右推导(最左归约) LR分析表主要包括ACTION表和GOTO表 这两张表的含义分别什么？ LR分析使用两张表 ACTION表的作用 告诉分析器在栈顶状态为S, 当前输入符号是a时做 什麽(下面是几种可能动作) ACTION[S,a]= Sj ACTION[S,a]=rj (第j条产生式为A??) ACTION[S,a]=acc ACTION[S,a]= error GOTO表的作用 告诉分析器在栈顶状态为S，归约之后的非终结符 為A时，要放到栈顶的新状态 自下而上语法分析：例 设有文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 对输入串abbcde使用移进-归约的方法分析它是否为上述文法的句子 先看自上而下的推导过程： S? aAcBe ? aAcde ? aAbcde ? abbcde S aAcBe aAcde aAbcde abbcde 续：普通自下而上分析过程 ACTION表和GOTO表 续：LR分析过程 Step states The rest of input action goto 1 0 abbcde# s2 2 02 bbcde# s4 3 024 bcde# r2 goto(2,A) 4 023 bcde# s6 5 0236 cde# r3 goto(2,A) 6 023 cde# s5 7 0235 de# s8 8 02358 e# r4 goto(5,B) 9 02357 e# s9 10 023579 # r1 goto(0,S) 11 01 # acc LR分析 ACTION表表达如此含义，即栈顶状态为S, 当前输入符号是a的时候采取什麽动作---?有穷狀态自动机 特征 规范的 符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号 分析决策依据――栈顶状态和现行输入符号。识别规范句型特定前缀(就到句柄为止)的 DFA 四种技术 LR(0) SLR(1) LR(1) LALR(1) 前缀相关的几个概念 LR(0)分析表构造思想和方法是其他LR