资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,编译原理课程总复习,贾棋,jiaqi7166,前端:依赖于源语言,独立于目标机器。,词法分析器,语法分析器,语义分析器,源程序,中间代码生成器,代码优化器,代码生成器,目标程序,出错管理器,符号表管理器,前端,后端,后端:依赖于目标机器,独立于源语言。,第二章 词法分析器,词法分析器,记号(,token,)流,源代码,词法分析器工作原理,:,源程序字符流,顺序组合,词法单元,词法记号,模式,非形式化描述,形式化描述,正规式,字母,组合,串,语言,集合,集合,字母表,名字,词法记号的描述与识别,正规式的例子,=,a,b,a,|,b,a,b,(,a,|,b,)(,a,|,b,),aa,ab,ba,bb,aa,|,ab,|,ba,|,bb,aa,ab,ba,bb,a,*,由字母,a,构成的所有串集,(,a,|,b,),*,由,a,和,b,构成的所有串集,复杂的例子,(00|11|(01|10)(00|11),(01|10),句子:,01001101,00,00,10000010,11,1001,正规定义的例子,Pascal,语言的标识符集合,letter,A,|,B,|,Z,|,a,|,b|,|,z,digit,0,|1|9,id,letter,(,letter,|,digit,),*,正规定义的例子,Pascal,无符号数集合,例,1946,11.28,63.6E8,1.99E,6,digit,0,|1|9,digits,digit,digit,*,optional_fraction,.,digits,|,optional_exponent,(E(+|,|,)digits)|,num,digits,optional_fraction,optional_exponent,简化表示,num,digit,+,(,.,digit,+,)?(E(+|,)?digit,+,)?,简化规则:,r,+,=,rr,*,r?=r|,a-z=,a|b|c,|z,abc,=,a|b|c,源程序字符流,顺序组合,词法单元,词法记号,模式,非形式化描述,形式化描述,正规式,字母,组合,串,语言,集合,集合,字母表,名字,连接 指数,和,L,U,M,连接,LM,闭包,L,*,正闭包,L,+,?,计算机实现,状态转换图,状态转换图,转换图,关系算符的转换图,0,5,1,6,2,4,8,3,7,return(relop,LE),return(relop,NE),return(relop,LT),return(relop,GE),return(relop,GT),return(relop,EQ),开始,=,=,*,*,other,other,relop,|,|,=,有 限 自 动 机,正规式,计算机实现,状态转换图,?,有限自动机,不确定有限自动机,确定有限自动机,等价,有 限 自 动 机,不确定的有限自动机(简称,NFA,),一个数学模型,它包括,:,状态集合,S,;,输入符号集合,;,转换函数,move,:,S,(,),P,(,S,),;,状态,s,0,是开始状态;,F,S,是接受状态集合,。,1,2,开始,a,0,a,b,b,识别语言,(,a,|,b,),*,ab,的,NFA,缺点:,1,、输入字符包括,2,、一个状态对于某个字符,可能有多条输出边,有 限 自 动 机,确定的有限自动机(简称,DFA,),一个数学模型,包括:,状态集合,S,;,输入字母表;,转换函数,move,:,S,S,;,唯一的初态,s,S,;,终态集合,F,S,;,1,2,开始,a,0,a,b,b,a,b,识别语言,(,a,|,b,),*,ab,的,DFA,优点:,1,、输入字符不包括,2,、一个状态对于某个字符,只可能存在唯一条输出边,NFA,到,DFA,的转换,子集构造法,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,状态,NFA,到,DFA,的转换,子集构造法,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,状态,A,=0,1,2,4,7,DFA,中第一个状态由,NFA,中的开始状态求,闭包得到,NFA,到,DFA,的转换,子集构造法,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,NFA,到,DFA,的转换,子集构造法,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,B,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,NFA,到,DFA,的转换,子集构造法,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,NFA,到,DFA,的转换,子集构造法,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,C,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,NFA,到,DFA,的转换,子集构造法,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,C,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,NFA,到,DFA,的转换,子集构造法,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,D,=1,2,4,5,6,7,9,NFA,到,DFA,的转换,子集构造法,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,D,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,D,=1,2,4,5,6,7,9,NFA,到,DFA,的转换,子集构造法,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,B,C,D,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,D,=1,2,4,5,6,7,9,NFA,到,DFA,的转换,子集构造法,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,B,C,D,B,C,状态,A,=0,1,2,4,7,B,=1,2,3,4,6,7,8,C,=1,2,4,5,6,7,D,=1,2,4,5,6,7,9,只要含有,NFA,中终结状态就标志为,DFA,的终结状态,NFA,到,DFA,的转换,B,D,开始,a,A,a,b,b,a,b,C,b,a,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,输入符号,a,b,A,B,C,B,B,D,C,B,C,D,B,C,状态,1,2,开始,a,0,a,b,b,a,b,DFA,的化简,B,D,开始,a,A,a,b,b,a,a,b,C,b,a,E,b,死状态,左图无须加死状态,右图加入死状态,E,。,B,D,开始,a,A,a,b,b,a,b,C,b,a,DFA,的化简,可区别的状态,A,和,B,是可区别的状态,A,和,C,是不可区别的状态,B,D,开始,a,A,a,b,b,a,b,C,b,a,DFA,的化简,方法,1.A,B,C,D,move,(A,B,C,a,=B,move,(A,B,C,b,=C,D,2.A,C,B,D,move,(A,C,a,=B,move,(A,C,b,=C,B,D,开始,a,A,a,b,b,a,b,C,b,a,初始划分为接受状态子集和非接收状态子集,划分完毕之后如果有死状态,将其删掉,从开始状态不可及的状态也删除,DFA,的化简,方法,1.A,B,C,D,move,(A,B,C,a,=B,move,(A,B,C,b,=C,D,2.A,C,B,D,move,(A,C,a,=B,move,(A,C,b,=C,B,D,开始,a,A,a,b,b,a,b,C,b,a,1,2,开始,a,0,a,b,b,a,b,将下图的,DFA,极小化。,a,a,start,0,1,2,3,a,b,b,b,b,b,4,DFA,0,1,2,3,a,a,b,b,a,b,b,b,start,4,5,a,a,a,b,加入死状态后的,DFA,1,、加入死状态,2,、合并不可区分状态,先把状态集分成非接受状态集,0,1,2,3,5,和接受状态集,4,这两个子集。,1,集合,4,不能再分解,我们看集合,0,1,2,3,5,。,move,(0,1,2,3,5,a)=1,2,5,move,(0,1,2,3,5,b)=3,4,5,由于,b,转换的结果,3,4,5,不是最初划分的某个集合的子集,因此,0,1,2,3,5,需要再分,由于状态,1,和状态,2,的,b,转换都到状态,4,。因此状态集合的进一步划分是:,1,2,,,0,3,5,和,4,2,由于,move,(1,2,a)=2,5,move,(1,2,b)=4,move,(0,3,5,a)=1,5,move,(0,3,5,b)=3,5,显然,1,2,和,0,3,5,需要再分,分别分成:,1,和,2,以及,0,3,和,5,3,由于,move,(0,3,a)=1,move,(0,3,b)=3,因此不需要再分。这样状态,0,和状态,3,合并成一个状态,我们取,0,为代表,再删去死状态,5,,就得到该题的结果。,正确做法!,0,1,2,b,b,b,b,4,a,a,start,最简,DFA,最初的划分是,0,1,2,3,和,4,。,1,状态集合的进一步划分是:,1,2,,,0,3,和,4,2,忽略了死状态的影响,会认为它们都不需要再分,错误做法!,1,、直接合并不可区分状态,0,1,b,b,a,a,start,a,4,一个不正确的结果,a,a,start,0,1,2,3,a,b,b,b,b,b,4,DFA,从正规式到有限自动机,正规式,计算机实现,状态转换图,有限自动机,不确定有限自动机,确定有限自动机,等价,?,从正规式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,从正规式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,从正规式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,从正规式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,从正规式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,从正规式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,从正规式到有限自动机,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,r,9,r,7,r,8,r,4,r,3,r,5,r,6,*,),(,r,2,r,1,a,|,b,a,b,(,a,|,b,),*,ab,的分解,从正规式到有限自动机,(,a,|,b,),*,ab,的两个,NFA,的比较,1,2,开始,a,0,a,b,b,1,9,开始,0,a,b,a,b,6,7,8,2,3,4,5,从语言到确定的有限自动机,例:识别,=,0,1,上能被,5,整除的二进制数,0,1,2,3,开始,4,方法:,1,、列出全部可能的状态,2,、从各个状态出发,构造边及输入字符记号,例:识别,=,0,1,上能被能,5,整除的二进制数,0,1,2,3,开始,4,0,从语言到确定的有 限 自 动 机,例:识别,=,0,1,上能被能,5,整除的二进制数,0,1,2,3,开始,4,1,0,从语言到确定的有 限 自 动 机,例:识别,=,0,1,上能被能,5,整除的二进制数,0,1,2,3,开始,4,1,0,0,从语言到确定的有 限 自 动 机,例:识别,=,0,1,上能被能,5,整除的二进制数,0,1,2,3,开始,4,1,0,0,1,从语言到确定的有 限 自 动 机,例:识别,=,0,1,上能被能,5,整除的二进制数,0,1,2,3,开始,4,1,0,0,1,0,从语言到确定的有 限 自 动 机,例:识别,=,0,1,上能被能,5,整除的二进制数,0,1,2,3,开始,4,1,0,0,1,0,1,从语言到确定的有 限 自 动 机,例:识别,=,0,1,上能被能,5,整除的二进制数,0,1,2,3,开始,4,1,0,0,1,0,1,0,从语言到确定的有 限 自 动 机,例:识别,=,0,1,上能被能,5,整除的二进制数,0,1,2,3,开始,4,1,0,0,1,0,1,0,1,从语言到确定的有 限 自 动 机,例:识别,=,0,1,上能被能,5,整除的二进制数,0,1,2,3,开始,4,1,0,0,1,0,1,0,1,0,从语言到确定的有 限 自 动 机,例:识别,=,0,1,上能被能,5,整除的二进制数,0,1,2,3,开始,4,1,0,0,1,0,1,0,1,0,1,从语言到确定的有 限 自 动 机,例:识别,=,0,1,上能被能,5,整除的二进制数,0,1,2,3,开始,4,1,0,0,1,0,1,0,1,0,1,从语言到确定的有 限 自 动 机,构造,DFA,接受,0,和,1,的个数都是偶数的字符串,3,1,2,0,1,1,1,1,0,0,0,0,开始,偶,0,偶,1,奇,0,奇,1,奇,0,偶,1,偶,0,奇,1,从语言到确定的有 限 自 动 机,小结,正规式,计算机实现,状态转换图,不确定有限自动机,确定有限自动机,等价,用正规式语法结构来指导构造过程,子集构造法,合并不可区别状态,最简确定有限自动机,等价,语言,确定有限自动机,状态列举法,第三章 语法分析器,主要内容,上下文无关文法,自上而下分析和自下而上分析,上下文无关文法与正规式比较,上下文无关文法,E,E A E|,(,E,),|,E|,id,A,+|,*,正规式定义,letter,A-,Za-z,digit 0-9,id,letter(letter|digit,)*,上下文无关文法是一个四元组,最左推到、最右推导,二义性,语言和文法,消除左递归,文法,左递归,A,+,A,a,直接左递归,A,A,a,|,b,串的特点,ba,.a,消除直接左递归,A,b,A,A,a,A,|,语言和文法,非直接左递归,S,Aa,|,b,A,Sd,|,先变换成直接左递归,S,Aa,|b,A,Aad,|,bd,|,再消除左递归,S,Aa,|b,A,bd,A,|A,A,adA,|,语言和文法,提左因子,有左因子的文法,A,1,|,2,提左因子,A,A,A,1,|,2,正规式,上下文无关文法,功能有限,四元组定义,推导,分析树,图形化表示,最左推导,最右推导,二义性,消除二义性,左递归,消除左递归,左因子,消除左因子,A,1,|,2,A,+,Aa,0,型文法,1,型文法,2,型文法,3,型文法,FIRST,集、,FOLLOW,集,FIRST(,)=,a,|,*,a,a,V,T,特别是,,*,时,规定,FIRST(,),FOLLOW(,A,)=,a,|,S,*,Aa,,,a,V,T,如果,A,是某个句型的最右符号,那么,$,属于,FOLLOW(,A,),FIRST,集合计算方法,若,X,a,.,,则将终结符加入,FIRST(X),中,若,X,,则将加入,FIRST(X),中,若,X,Y,,且,Y,属于非终结符,则将,FIRST(Y),加入到,FIRST(X),中,若,XY1Y2.YK,且,Y1,Y2,.Yi-1,都是非终结符,且,Y1,Y2,.Yi-1,的,FIRST,集合中均包含,,则将,FIRST(Y,j,),的所有非元素加入到,FIRST(X),中,(,j,=1,2,.i,),.,特别地,若,Y1YK,均有产生式,则将加到,FIRST(X),中。,FIRST,集合及,FOLLOW,集合的计算方法,FOLLOW,集合计算方法,对文法开始符号,S,置,$,于,FOLLOW(S),中。,若有,A,B,,则将,FIRST(),加入,FOLLOW(B),中。,(此处,可以为空,),若,A,B,或,A,B,且,*,(即,属于,FIRST(),),则将,FOLLOW(A),加入,FOLLOW(B),中(此处,可以为空,),。,FIRST,集合及,FOLLOW,集合的计算方法,FIRST,集合及,FOLLOW,集合的计算方法,例,E,TE,E,+,TE,|,T,FT,T,*,FT,|,F,(,E,)|id,FIRST,集合及,FOLLOW,集合的计算方法,例,E,TE,E,+,TE,|,T,FT,T,*,FT,|,F,(,E,)|id,FIRST(,E,)=FIRST(,T,)=FIRST(,F,)=(,id,FIRST,集合及,FOLLOW,集合的计算方法,例,E,TE,E,+,TE,|,T,FT,T,*,FT,|,F,(,E,)|id,FIRST(,E,)=FIRST(,T,)=FIRST(,F,)=(,id,FIRST(,E,)=+,FIRST,集合及,FOLLOW,集合的计算方法,例,E,TE,E,+,TE,|,T,FT,T,*,FT,|,F,(,E,)|id,FIRST(,E,)=FIRST(,T,)=FIRST(,F,)=(,id,FIRST(,E,)=+,FRIST(,T,)=,*,FIRST,集合及,FOLLOW,集合的计算方法,例,E,TE,E,+,TE,|,T,FT,T,*,FT,|,F,(,E,)|id,FIRST(,E,)=FIRST(,T,)=FIRST(,F,)=(,id,FIRST(,E,)=+,FRIST(,T,)=,*,FOLLOW(,E,)=FOLLOW(,E,)=),$,FIRST,集合及,FOLLOW,集合的计算方法,例,E,TE,E,+,TE,|,T,FT,T,*,FT,|,F,(,E,)|id,FIRST(,E,)=FIRST(,T,)=FIRST(,F,)=(,id,FIRST(,E,)=+,FRIST(,T,)=,*,FOLLOW(,E,)=FOLLOW(,E,)=),$,FOLLOW(,T,)=FOLLOW(,T,)=+,),$,FIRST,集合及,FOLLOW,集合的计算方法,例,E,TE,E,+,TE,|,T,FT,T,*,FT,|,F,(,E,)|id,FIRST(,E,)=FIRST(,T,)=FIRST(,F,)=(,id,FIRST(,E,)=+,FRIST(,T,)=,*,FOLLOW(,E,)=FOLLOW(,E,)=),$,FOLLOW(,T,)=FOLLOW(,T,)=+,),$,FOLLOW(,F,)=+,*,),$,自上而下分析,LL(1),文法,任何两个产生式,A,|,都满足下列条件:,FIRST(,),FIRST(,)=,若,*,,那么,FIRST(,),FOLLOW(,A,)=,LL(1),文法有一些明显的性质,没有公共左因子,不是二义的,不含左递归,自上而下分析,非递归的预测分析,a,+,b,$,输入,预测分析程序,分析表,M,输出,X,Y,Z,$,栈,自上而下分析,非终,结符,输,入,符,号,id,+,*,.,E,E,TE,E,E,+,TE,T,T,FT,T,T,T,*,FT,F,F,id,自上而下分析,栈,输,入,输,出,$,E,id,*,id+id$,预测,分析器接受输入,id,*,id+id,的动作,自上而下分析,栈,输,入,输,出,$,E,id,*,id+id$,$,E,T,id,*,id+id$,E,TE,预测,分析器接受输入,id,*,id+id,的动作,自上而下分析,栈,输,入,输,出,$,E,id,*,id+id$,$,E,T,id,*,id+id$,E,TE,$,E,T,F,id,*,id+id$,T,FT,预测,分析器接受输入,id,*,id+id,的动作,自上而下分析,栈,输,入,输,出,$,E,id,*,id+id$,$,E,T,id,*,id+id$,E,TE,$,E,T,F,id,*,id+id$,T,FT,$,E,T,id,id,*,id+id$,F,id,预测,分析器接受输入,id,*,id+id,的动作,自上而下分析,构造预测分析表,(,1,),对文法的每个产生式,A,,,执行,(2),和,(3),。,(,2,)对,FIRST(,),的每个终结符,a,,把,A,加入,M,A,a,。,(,3,),如果,在,FIRST(,),中,对,FOLLOW(,A,),的每个终结符,b,(,包括,$,),把,A,加入,M,A,b,。,(,4,),M,的其它没有定义的条目都是,error,。,自上而下分析,非终,结符,输,入,符,号,id,+,*,.,E,E,TE,E,E,+,TE,T,T,FT,T,T,T,*,FT,F,F,id,自下而上,上下文无关文法,自上而下,自下而上,LL(1),文法,2,个函数,递归下降预测分析,非递归的预测分析,最左推导,最右推导,!,自下而上分析,句柄,句型的,句柄,是和某产生式右部匹配的子串,并且,把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步。,S,aABe,A,Abc,|b,B,d,S,rm,aABe,rm,aA,d,e,rm,a,Abc,de,rm,a,b,bcde,句柄与某个产生式的右部符号串相同,句柄是句型的一个子串,把句柄归约成非终结符代表了最右推导逆过程的一步,5/75,LR,分析器,LR,分析算法,输入,LR,分析程序,输出,栈,LR,分析器的模型,action,goto,s,m,X,m,s,m,-1,X,m,-1,s,0,a,1,a,i,a,n,$,LR,分析器,例,E,E+T|T,T,T,*,F|,F,F,(,E,)|id,状态,动,作,转,移,id +,*,()$,E,T F,0,s,5,s,4,1 2 3,1,s,6,acc,2,r,2,s,7,r,2,r,2,3,r,4,r,4,r,4,r,4,4,s,5,s,4,8 2 3,LR,分析器,栈,输,入,动,作,0,id,*,id+id,$,LR,分析器,栈,输,入,动,作,0,id,*,id+id,$,移进,LR,分析器,栈,输,入,动,作,0,id,*,id+id,$,移进,0 id 5,*,id+id,$,40/75,LR,分析器,栈,输,入,动,作,0,id,*,id+id,$,移进,0 id 5,*,id+id,$,按,F,id,归约,LR,分析器,栈,输,入,动,作,0,id,*,id+id,$,移进,0 id 5,*,id+id,$,按,F,id,归约,0,F,3,*,id+id,$,LR,分析器,栈,输,入,动,作,0,id,*,id+id,$,移进,0 id 5,*,id+id,$,按,F,id,归约,0,F,3,*,id+id,$,按,T,F,归约,LR,分析器,栈,输,入,动,作,0,id,*,id+id,$,移进,0 id 5,*,id+id,$,按,F,id,归约,0,F,3,*,id+id,$,按,T,F,归约,0,T,2,*,id+id,$,构造,SLR,分析表,LR(0),项目,(简称,项目,),在右部的某个地方加点的产生式,例:,A,XYZ,对应有四个项目,A,XYZ,A,X,YZ,A,XY,Z,A,XYZ,例:,A,只有一个项目和它对应,A,点的左边代表历史信息,右边代表展望信息。直观地讲,项目表示在分析过程的某一阶段,已经看到了产生式的多大部分,以及希望看到的部分。,从,DFA,构造,SLR,分析表,状态,i,从,I,i,构造,它的,action,函数如下确定:,如果,A,a,在,I,i,中,并且,goto,(,I,i,a,)=,I,j,,,那么置,action,i,a,为,sj,。,如果,A,在,I,i,中,那么对,FOLLOW(,A,),中的所有,a,,置,action,i,a,为,rj,j,是产生式,A,的编号。,如果,S,S,在,I,i,中,那么置,action,i,$,为接受,acc,。,如果出现动作冲突,那么该文法就不是,SLR(1),的。,使用下面规则构造状态,i,的,goto,函数:,对所有的非终结符,A,,,如果,goto,(,I,i,A,)=,I,j,那么,goto,i,A,=,j,。,构造规范的,LR,分析表,基于,LR(1),项目来构造识别,G,活前缀的,DFA,。,2,、构造,LR(1),项目集规范族,I,0,:,S,.,S,$,S,.,BB,$,B,.,b,B,b,/,a,B,.,a,b,/,a,闭包函数,closure(I,),1,、,I,的每个项目均加入,closure(I,),2,、如果,A,B,a,在,closure(I,),中,且,B,是产生式,那么如果项目,B,b,还不在,closure(I,),中的话,那么把它加入,(,其中,b,属于,FIRST(,a,),),。,S,S,S,BB,B,b,B,B,a,构造规范的,LR,分析表,S,V,=,E,S,E,V,*,E,V,id,E,V,I,0,:,S,S,,$,S,V,=,E,$,S,E,$,V,*,E,=/$,V,id,=/$,E,V,$,I,2,:,S,V,=,E,$,E,V,$,V,构造,LR,分析表的一般流程,构造拓广文法,构造,DFA,若是,SLR,直接构造即可,若是,LR,需要求取搜索符,若是,LALR,需要在,LR,的基础上进行合并,根据,DFA,构造分析表,判断文法属于哪类文法,证明文法,SA a|,bAc,|dc|,bda,A d,是,LALR(1,),文法,但不是,SLR(1),文法。,方法一,:通过构造分析表来回答,如果表中不存在冲突则说明属于某文法,否则不属于该文法。,方法二,:当文法很简单时,可通过直观分析。先说明该文法不是,SLR(1),文法。从产生式很容易看出,FoLLow(A,),a,,,c,。若输入句子是,dc,,在,d,进栈后,面临的是,c,,这时出现移进一归约冲突。因为项目,S,d.c,要求移进,而项目,A d.,要求归约,(,这两个项目出现在同一项目集中,),,因为,c,在,FOLLOW(A),中。,而上面的移进一归约冲突在规范,LR(1),情况下不存在,因为只有在面临,a,时才进行,d,到,A,的归约。该文法还有另一个移进,归约冲突,在,bd,进栈后,面临,c,的情况,其冲突的原因和上面的类似。该冲突在规范,LR(1),情况下也不存在。这样,该文法是,LR(1),文法。,显然该文法的规范,LR(1),项目集的集合中没有同心项目集,因此该文法也是,LALR(1),文法。,第四章 语法制导的定义,简单台式计算器的语法制导定义,产,生,式,语,义,规,则,L,E,n,print,(,E,.,val,),E,E,1,+,T,E,.,val,:=,E,1,.,val,+,T.val,E,T,E,.,val,:=,T.val,T,T,1,*,F,T.val,:=,T,1,.,val,*,F.val,T,F,T.val,:=,F.val,F,(,E,),F.val,:=,E.val,F,digit,F.va,l,:=,digit,.lexval,本章要点,语义规则的两种描述方法:语法制导的定义和翻译方案。,设计简单问题的语法制导定义和翻译方案,这是本章的重点和难点。,S,属性的自下而上计算(边分析边计算),。,L,属性的自上而下计算(边分析边计算),。,L,属性的自下而上计算(边分析边计算),。,语法制导的定义,语法制导定义的形式,每个文法符号有一组属性,每个文法产生式,A,有一组形式为,b,:=,f,(,c,1,c,2,c,k,),的语义规则,,,其中,f,是函数,,b,和,c,1,c,2,c,k,是该产生式文法符号的属性,综合属性:,如果,b,是,A,的属性,,c,1,c,2,c,k,是产生式右部文法符号的属性或,A,的其它属性。,继承属性,:如果,b,是产生式右部某个文法符号,X,的属性。,以上两种情况下,都说,b,依赖于属性,c,1,c,2,c,k,。,属性值由分析树中它的子结点属性值来计算,属性值由结点的兄弟结点及父结点的属性值来计算。,句子,real id,1,,,id,2,,,id,3,的带注释的分析树的依赖图,id,1,L,id,2,L,id,3,L,real,T,D,4,type,5,in,6,-,addtype(id.entry,L.in,),7,in,8,addtype,9,in,10,addtype,1,entry,2,entry,3,entry,产 生 式,语 义 规 则,DTL,L.in,:=T.type,Tint,T.type,:=integer,Treal,T.type,:=real,LL,1,id L,1,.in:=L.in,addtype(id.entry,L.in),Lid,addtype(id.entry,L.in),S,属性定义的自下而上计算,将,LR,分析器,增加,一个域来保存综合属性值,。,.,.,X,.,x,X,Y,.,y,Y,Z,.,z,Z,.,.,栈,state,val,top,若产生式,A,XYZ,的语义规则是,A,.,a,:=,f,(,X,.,x,Y,.,y,Z,.,z,),,,那么归约后:,.,.,A,A,.,a,.,.,top,S,属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,.,.,X,.,x,X,Y,.,y,Y,Z,.,z,Z,.,.,栈,state,val,top,产,生,式,语 义 规 则,L,E,n,print,(,E,.,val,),E,E,1,+,T,E,.,val,:=,E,1,.,val,+,T.val,E,T,E,.,val,:=,T.val,T,T,1,*,F,T.val,:=,T,1,.,val,*,F.val,T,F,T.val,:=,F.val,F,(,E,),F.val,:=,E.val,F,digit,F.va,l,:=,digit,.lexval,S,属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,产,生,式,代 码 段,L,E,n,print,(,val,top,1),E,E,1,+,T,E,.,val,:=,E,1,.,val,+,T.val,E,T,E,.,val,:=,T.val,T,T,1,*,F,T.val,:=,T,1,.,val,*,F.val,T,F,T.val,:=,F.val,F,(,E,),F.val,:=,E.val,F,digit,F.va,l,:=,digit,.lexval,.,.,X,.,x,X,Y,.,y,Y,Z,.,z,Z,.,.,栈,state,val,top,S,属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,产,生,式,代 码 段,L,E,n,print,(,val,top,1),E,E,1,+,T,E,.,val,:=,E,1,.,val,+,T.val,E,T,E,.,val,:=,T.val,T,T,1,*,F,T.val,:=,T,1,.,val,*,F.val,T,F,T.val,:=,F.val,F,(,E,),F.val,:=,E.val,F,digit,F.va,l,:=,digit,.lexval,.,.,X,.,x,X,Y,.,y,Y,Z,.,z,Z,.,.,栈,state,val,top,S,属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,产,生,式,代 码 段,L,E,n,print,(,val,top,1),E,E,1,+,T,val,top,2 :=,val,top,2+,val,top,E,T,E,.,val,:=,T.val,T,T,1,*,F,T.val,:=,T,1,.,val,*,F.val,T,F,T.val,:=,F.val,F,(,E,),F.val,:=,E.val,F,digit,F.va,l,:=,digit,.lexval,.,.,X,.,x,X,Y,.,y,Y,Z,.,z,Z,.,.,栈,state,val,top,L,属性定义的自上而下计算,L,属性定义,如果每个产生式,A,X,1,X,2,X,n,的每条语义规则计算的属性是,A,的综合属性;或者是,X,j,的继承属性,,1,j,n,但它仅依赖:,该产生式中,X,j,左边符号,X,1,X,2,X,j,-1,的属性;,A,的继承属性。,S,属性定义属于,L,属性定义,。,L,属性定义的自上而下计算,L,属性定义的例子:变量类型声明的语法制导定义,产 生 式,语,义,规,则,D,TL,L,.,in,:=,T,.,type,T,int,T,.,type,:=,integer,T,real,T,.,type,:=,real,L,L,1,id,L,1,.in,:=,L,.,in,;,addtype,(id.,entry,L,.,in,),L,id,addtype,(id.,entry,L,.,in,),语义规则的执行时刻很重要,翻译方案,语义动作(语义规则)插入到产生式右部的任何,地方,以表达动作的执行时刻。,A,B.C,L,属性定义的翻译方案的三条限制:,产生式右部符号的继承属性必须在先于这个符号的,动作中计算,一个动作不能引用该动作右边符号的综合属性,左部非终结符的综合属性只能在它所引用的所有属,性都计算完后才能计算,建立翻译模式,如果既有,综合属性,又有,继承属性,,在建立翻译模式时就必须保证:,1.,产生式右边的符号的,继承属性,必须在先于这个符号的动作中计算出来。,2.,一个动作不能引用这个动作右边的符号的,综合属性,。,3.,产生式左边非终结符的,综合属性,只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的,末尾,。,SA,1,A,2,A,1,.in:=1;A,2,.in:=2,Aa,print(A.in),L,属性的自下而上计算,L,属性自下而上计算需要解决的问题:,.,.,X,.,x,X,Y,.,y,Y,.,.,栈,state,val,top,A,X Y,Z.i,=,X.x,Z,一个状态(文法符号)对应一个综合属性,该属性的值一般在处理完该文法符号之后得到。那么在,Z,还没有开始处理前,继承属性,Z.i,就没有对应的,val,条目供其使用!,在栈上消除继承属性,L,属性的自下而上计算,特殊情况一:,删除翻译方案中嵌入的动作,E,T R,R,+,T,print,(+),R,1,|,T,print,(,),R,1,|,T,num,print,(,num.,val,),在文法中加入产生,的,标
展开阅读全文