编译原理531-LR分析器

单击此处编辑母版标题,单击此处编辑母版文本样式,第二级,第三级,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五章 语法分析,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,a,1,a,2,a,i,a,n,#,LR,分析表,总控程序,输入串,：,栈顶,输出,s,0,s,1,s,m,状态栈,#,x,1,x,m,符号栈,分析栈,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,3,.,.,.,3,.,310,2,.,.,.,2,.,9,1,.,.,.,8,.,acc,r2,.,r4r6,.,.,.,r1r3r5,.,.,r2r4,.,r6,.,.,S11r1r3r5,S4,.,.,.,S4,.,S4S4,.,.,S7r4,.,r6,.,.,.,S7r3r5,.,S6r2r4,.,r6,.,S6r1r3r5,S5,.,.,.,S5,.,S5S5,01234567891011,F,T,E,#,),(,*,+,i,状态,GOTOs,A,ACTIONs,a,表达式文法的,LR,分析表,p101,将,LR,分析器的工作过程看成三元式的变化过程,状态栈符号栈输入串,分析开始时的初始三元式为:,(s0,，ala2.an,分析过程每步的结果可表示为,(s0s1.sm，X1X2.Xm，aiai+1an,分析器的下一步动作由sm和 ai所唯一决定,栈顶,栈顶,现行输入符号,Actions,m,a,i,:,4,种可能动作,(1),移进,s,j,(2),归约,r,m,(3),接受,acc,(4),报错,空白,/,出错,/error,(1),移进,s,j,push s;,push a,i,;,状态栈,符号栈,输入串,s,0,s,1,.s,m,X,1,X,2,.X,m,a,i,a,i+1,a,n,s,0,s,1,.s,m,X,1,X,2,.X,m,a,i+1,a,n,s=GOTO s,m,，,a,i,=,j,s,a,i,j,(2),归约,-,r,m,pop,文法符号栈,r,次,pop,状态栈,r,次,push A,查表,s,=GOTOs,m-r,A,push s,用第,m,条产生式,A,归约,.|=r,状态栈,符号栈,输入串,s,0,s,1,.s,m-r,s,m,X,1,X,2,.X,m-r,X,m,a,i,a,i+1,a,n,s,0,s,1,.,s,m-r,X,1,X,2,.,X,m-r,a,i,a,i+1,a,n,A,s,步骤,状态栈,符号栈,剩余输入串,动作,1,0,#,i,*i+i#,2,3,4,5,例,5.7,对,i*i+i#,进行移进,-,归约分析,P102,移进,S5,0,#,*,i+i#,归约,r6,F,i,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,T,F,0,#,*,i+i#,T,2,5,i,移进,S7,02,7,#T,*,i+i#,移进,S5,步骤,状态栈,符号栈,剩余输入串,动作,1,0,#,i,*i+i#,移进,S5,2,0,5,#,i,*i+i#,归约,r6,F,i,3,0,3,#,F,*i+i#,归约,r4 T,F,4,02,#T,*i+i#,移进,S7,5,027,#T*,i+i#,移进,S5,6,0275,#T*i,+i#,归约,r6 F,i,7,0,27 10,#,T*F,+i#,归约,r3,T,T*,F,8,0,2,#,T,+i#,归约,r2 E,T,9,01,#E,+i#,移进,S6,10,016,#E+,i#,移进,S5,11,0165,#E+i,#,归约,r6 F,i,12,0163,#E+F,#,归约,r4 T,F,13,0,169,#,E+T,#,归约,r1,E,E+T,14,0,1,#,E,#,接受,acc,p102,补充：,LR,分析算法,*,状态栈中放入状态,0;,文法符号栈中放入,ip,指向输入串,w,的第一个符号,S,m,为栈顶状态,;a,是,ip,指向的符号,Repeat,/,见下页,end.,Repeat,if ACTIONSm,a=Sj,begin,PUSH j,a ip 前进 end,else if ACTIONSm,a=rj /A,begin,pop|项/当前栈顶状态为Skpush GOTOSk,A,A,end,else if ACTIONSm,a=accreturn (成功,else error,end.,LR,分析器小结,总控程序,-,对所有的,LR,分析器都是相同的。,根据当前栈顶的状态号和输入符号，去查,LR,分析表，决定采取什么动作，移进还是归约等。,分析表,-,规定了动作和状态的转换。,不同的文法，分析表将不同,同一个文法采用不同的,LR,分析器，分析表也将不同。,分析栈,-,文法符号栈和状态栈,它们在移进和归约的过程中是同步的，栈中元素一样多,栈指针用同一个。,在一般的移进归约过程中也有文法符号栈，但没有状态栈。,几个概念,LR文法:对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，那么我们将把这个文法称为LR文法。,LR(k)文法:一个文法如果能用一个每步最多向前检查k个输入符号的LR分析器进行分析，那么这个文法就称为LR(k)文法。,非,LR,结构,文法 G:S iCtS|iCtSeS,假定一个自下而上分析器，它处于如下情形:,栈,输入,iCtS,e#,问题,:,无法确定,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(,i,i)#,对于串,i(i,i),，,当它处于如下情形:,那么栈顶的 i 应该按照 产生式(5)归约,还是按照产生式(7)归约,一种解决方法:将产生式(1)中的 i 改为proci，让词法分析查询符号表,识别i是过程名还是数组名。当为过程名时，变成,proci(,i,i)#,