编译原理5.3.1-LR分析器.ppt

第五章 语法分析,5.1 自下而上分析基本问题 5.2 算符优先分析 5.3 LR分析 5.4 YACC,5.3 LR分析,5.3.1 LR分析器 5.3.2 LR(0)项目集族LR(0)分析表的构造 5.3.3 SLR分析表的构造 5.3.4 规范LR分析表的构造 5.3.5 LALR分析表的构造 5.3.6 二义文法的应用,课前思考,自下而上分析是一种_过程 自下而上分析法的关键问题是在分析过程中_。 算符优先分析法如何确定可归约串？ 什么是规范推导和规范归约？ 它们之间有什么关系？ 规范归约过程是当分析的栈顶符号串形成_时就采取归约动作,移进-归约,句柄,如何确定可归约串,LR(K),L : 自左向右扫描 R : 逆向完成最右推导 (规范归约) K : 向右查看输入串符号的个数 (K省略时, 表示K等于1),LR分析过程是规范归约过程,四种LR分析器,LR(0) SLR(1) LR(1) LALR(1),LR方法的基本思想,LR方法的关键: 确定句柄 历史: 已移进和归约出的整个符号串 展望: 根据所用的产生式推测未来可能 碰到的输入符号 现实: 当前的输入符号 LR分析器的每一步工作都是由栈顶状态和 现行输入符号所唯一决定的。 一个LR分析器实质上是一个DFA,状态,5.3.1 LR分析器 P100,LR分析表,总控程序,输入串：,栈顶,输出,s0,s1,sm,状态栈,分析栈,Goto,Action,图5.4 LR分析器模型,分析表,例： p101,G: (1) E E+T (2) E T (3) T T*F (4) T F (5) F (E) (6) F i,将LR分析器的工作过程看成三元式的变化过程,状态栈 符号栈 输入串 分析开始时的初始三元式为: (s0 , ， ala2.an） 分析过程每步的结果可表示为 (s0s1.sm， X1X2.Xm， aiai+1an） 分析器的下一步动作由sm和 ai所唯一决定,栈顶,栈顶,现行输入符号,Actionsm,ai: 4种可能动作,(1) 移进 sj (2) 归约 rm (3) 接受 acc (4) 报错 空白 / 出错 / error,(1) 移进 sj,push s ; push ai;,s0s1.sm,X1X2.Xm,ai+1an,s = GOTO sm，ai ,= j,s,ai,j,(2) 归约 - rm,pop 文法符号栈 r次 pop 状态栈 r次 push A 查表 s = GOTOsm-r , A push s,用第m条产生式A归约. | =r,s0s1.sm-r,X1X2.Xm-r,aiai+1an,A,s,例5.7 对i*i+i# 进行移进-归约分析 P102,移进 S5,0,#,*i+i#,归约 r6 Fi,G: (1) E E+T (2) E T (3) T T*F (4) T F (5) F (E) (6) F i,0,#,*i+i#,F,3,归约 r4 TF,0,#,*i+i#,T,2,5,i,移进 S7,02,7,#T,*,i+i#,移进 S5,p102,补充：LR分析算法 *,状态栈中放入状态0 ; 文法符号栈中放入 ip指向输入串w的第一个符号 Sm为栈顶状态 ; a是ip指向的符号 Repeat /见下页 end .,Repeat if ACTIONSm,a=Sj begin PUSH j, a ip 前进 end else if ACTIONSm,a=rj / A begin pop | 项 /当前栈顶状态为Sk push GOTOSk, A , A end else if ACTIONSm, a=acc return (成功） else error end .,LR分析器小结,总控程序 - 对所有的LR分析器都是相同的。 根据当前栈顶的状态号和输入符号，去查LR分析表，决定采取什么动作，移进还是归约等。 分析表 - 规定了动作和状态的转换。 不同的文法，分析表将不同 同一个文法采用不同的LR分析器，分析表也将不同。 分析栈 - 文法符号栈和状态栈 它们在移进和归约的过程中是同步的，栈中元素一样多,栈指针用同一个。 在一般的移进归约过程中也有文法符号栈，但没有状态栈。,几个概念,LR文法: 对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则我们将把这个文法称为LR文法。 LR(k)文法: 一个文法如果能用一个每步最多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法。,非LR结构,已知文法 G : S iCtS | iCtSeS 假定一个自下而上分析器，它处于如下情形:,栈,输入,问题: 无法确定iCtS是否为句柄? 或者移进e，或者将iCtS归约为S,结论: 任何二义文法都不是LR(K)文法,已知文法 G : （1）语句 i（参数表） （2）语句 表达式 := 表达式 （3）参数表 参数表，参数 （4）参数表 参数 （5）参数 i （6）表达式 i（表达式表） （7）表达式 i （8）表达式表 表达式表，表达式 （9）表达式表 表达式,数组元素引用和过程调用的表示形式相同,如A(I,J),经词法分析后得到i(i,i),栈,输入,对于串 i (