大连海事大学《编译原理》期末总复习.ppt

1、编译原理期末总复习,考试题型及分数分布,填空题(10分） 单选题（20分） 判断题（10分） 解析题（60分）,第二章 文法与形式语言简介,（1）给出句型或句子最左推导或最右推导（规范推导）； （2）画出句型或句子的语法树； （3）求句型的短语、简单短语、句柄； （4）判断一个文法是二义性的文法,P28#3,规范推导： aa+a*,S=SS*|SS+|a,S=,aa+a*,Sa+a*=,SS+a*=,Sa*=,SS*=,语法树：,P28#4,只含有4个符号的句子：,Z=U0V1,U=Z11,V=Z00,U0=,Z10=,U010=,1010,Z=,0100,Z=,V1=,U000=,Z00 =

2、,1000,U0=,Z10=,V110=,0110,Z=,Z=,V1=,Z00=,V100=,P28#5,S=AB A=aA B=bBcbc,A=aA描述的语言: an|n=0,B=bBcbc描述的语言:bncn|n=1,L(GS)=anbmcm|n=0,m=1,P28#7,E=TE+TE-T T=FT*FT/F F=(E)i，,句型T+T*F+i的语法树：,E,E,+,T,T,E,+,T,T,*,F,F,i,短语：,T+T*F+i,T+T*F,简单短语：,T*F，,T ，,i,句柄：,T,已知文法GE: E:=E+T|T T:=T*F|F F:=(E)|i 1、试给出句子i*(i+i)的规范

3、推导； 2、画出相应的语法树；(注意：相同的叶子节点用不同的下标加以区分，如：i1、i2、i3) 3、指出该句子所有的短语、简单短语、句柄。,存在的问题,给出的推导不是规范推导； 一次使用多条规则； 没有标明句柄所在的位置； 不是从文法的开始符号进行推导；,句子i*(i+i)的规范推导,ET T*F T*(E) T*(E+T) T*(E+F) T*(E+i) T*(T+ i) T*(F + i) T*(i + i) F* (i + i) i * (i + i),句子i*(i+i)的语法树,短语、简单短语、句柄,为了区分相同的短语，可以采用加下标的方法。 i1、i3是相对于非终结符号F、T的短语

4、、简单短语; i2是相对于非终结符号F、T、E的短语、简单短语; i2+i3是相对于非终结符号E的短语; (i2+i3)是相对于非终结符号F的短语; i1*(i2+i3)是相对于非终结符号T、E的短语; i1是句柄;,P28#8,S=S*S|S+S|(S)|a,给出句子a+a*a 两棵不同的语法树,已知文法GS: S:=iSeS|iS|i 试说明该文法是二义性的文法。,句子iiiei两棵不同的语法树,S:=iSeS|iS|i,第三章 词法分析,1、正规文法和有限自动机的等价性 2、正规式和有限自动机的等价性 3、 NFA到DFA转换的子集法及最小化,正则文法的状态图画法如下：,1、文法中的每个

5、非终结符号对应状态图中的一个结点，即图中的每个结点代表一个非终结符号。,2、增设一个结点代表开始状态S，而文法中的识别符号对应的结点为终结状态,3、对于文法中的每一条形如Ua的规则，画一条从结点S指向结点U的弧线，并在弧上标记a。,4、对于文法中每一条形如U=Wa的规则，画一条从结点W指向结点U的弧线，并在弧上标记a。,S,U,a,开始状态,W,U,a,有正则文法GZ：Z:=Ua|Vb，U:=Zb|b，V:=Za|a ，画出该文法的状态图，并检查句子abba是否合法。,S,U,V,Z,a,a,a,b,b,b,P60#1,句子abba合法。,Z:=Ua|Vb,U:=Zb|b,V:=Za|a,Z:

6、=Ua|Vb， U:=Zb|b， V:=Za|a,从正规式R构造NFA M的步骤1,1、把正规式R表示为：,初态,终态,x,R,从上的正规式R构造NFA M的步骤2,2、把R分裂并加进新的结点,每条弧标记为上的一个字符或,结点分裂规则,加入k结点,1弧变2弧,结点分裂规则,1弧变2弧,结点分裂规则,加入k结点,闭包去掉变闭环,前后各1条空弧,k,R1,子集法的基本思想,NFA,基本思想：,NFA的一组状态,DFA的一个状态,对应,等价的DFA,子集法,转 换,子集法,设已给具有动作的NFA M=（K,f,S0,Z),构造相应的确定的有限自动机: DFA M =（K,f,q0,Z ),构造K 及

7、f 的步骤可递归地描述如下：,（1）给出M的初态 ：,递归描述步骤（1）,K=,q0 ,q0 =,-closure(S0),递归描述步骤（2）,（2）对于K中尚未标记的状态 qi =Si1 ,Si2 ,Sim, Sik K做 ：,标记qi ；,对于每一个a，置：,若qj不在K中,则将qj,f(qi , a)=qj,K,M,J=move(Si1 ,Si2 ,Sim,a)，,qj = -closure(J)= Ia,递归描述步骤（3）,（3）重复（2）直到M中不再有未标记的状态为止。,至少含有一个Z中元素的qi作为M的终态,构造正规式b(ab|bb)*ab的DFA,（1）NFA,初态,终态,x,b

8、(ab|bb)*ab,初态,终态,x,a,1,b,2,3,ab|bb,4,b,初态,终态,x,a,1,b,2,3,4,b,bb,初态,终态,x,a,1,b,2,3,a,4,b,b,5,6,b,b,ab,（2）DFA,1、-closure(x)=x,=q0,K q0 ,2、对K中未标记状态q0做：,move(q0,a)=move(x,a)=,move(q0,b)=move(x,b)= 1,-closure(1)=1,2,3=q1,f(q0,b)= q1,K q0,q1,3、对K中未标记状态q1做：,move(q1,a)=,move(1,2,3,a)=4,6,-closure(4,6)= 4,6

9、=q2,f(q1,a) =q2,move(q1,b)=,move(1,2,3,b)=5,-closure(5)= 5 =q3,f(q1,b) =q3,K q0,q1,q2,q3,4、对K中未标记状态q2做：,move(q2,a)=,move(4,6,a)=,move(q2,b)=,move(4,6,b)=2,y,-closure(2,y)= 2,3,y =q4,f(q2,b) =q4,K q0,q1,q2,q3,q4,5、对K中未标记状态q3做：,move(q3,a)=,move(5,a)=,move(q3,b)=,move(5,b)=2,-closure(2)= 2,3 =q5,f(q3,b

10、) =q5,K q0,q1,q2,q3,q4,q5,6、对K中未标记状态q4做：,move(q4,a)=,move(2,3,y,a)=4,6,-closure(4,6)= 4,6 =q2,f(q4,a) =q2,move(q4,b)=,move(2,3,y,b)=5,-closure(5)= 5 =q3,f(q4,b) =q3,K q0,q1,q2,q3,q4,q5,7、对K中未标记状态q5做：,move(q5,a)=,move(2,3,a)=4,6,-closure(4,6)= 4,6 =q2,f(q5,a) =q2,move(q5,b)=,move(2,3,b)=5,-closure(5)

11、= 5 =q3,f(q5,b) =q3,K q0,q1,q2,q3,q4,q5,等价的DFA M 如下,K q0 , q1 , q2 ,q3 , q4 ,q5,f(q0,a) = , f(q0,b) =q1,f(q1,a) =q2, f(q1,b) =q3,f(q2,a) = , f(q2,b) =q4,f(q3,a) = , f(q3,b) =q5,f(q4,a) =q2, f(q4,b) =q3,Z q4 ,f(q5,a) =q2, f(q5,b) =q3,NFA M转换为DFA M 的过程,q0=x,q1 =1,2,3,q2 =4,6,q3 =5,q4 =2,3,y,q1 =1,2,3,

12、q2 =4,6,q3 =5,q2 =2,3,y,q5=2,3,q3 =5,f(q0,b) =q1,f(q1,a) =q2, f(q1,b) =q3,f(q2,b) =q4,f(q3,b) =q5,f(q4,a) =q2, f(q4,b) =q3,f(q5,a) =q2, f(q5,b) =q3,q5 =2,3,q2 =4,6,q2 =4,6,q3 =5,DFA M 的状态图,f(q0,a) = , f(q0,b) =q1, f(q1,a) =q2, f(q1,b) =q3, f(q2,a) = , f(q2,b) =q4, f(q3,a) = , f(q3,b) =q5, f(q4,a) =q

13、2, f(q4,b) =q3, f(q5,a) =q2, f(q5,b) =q3,b,最小化,1、初始划分由两个子集组成，即：,：,q0,q1,q2,q3，q5(非终态）,q4（终态）,b,2、考查子集q0,q1,q2,q3,q5, q0,q1,q2,q3,q5 a：,=q2 , q0,q1,q2,q3,q5 , q0,q1,q2,q3,q5 b：,=q1,q3,q4,q5 , q0,q1,q2,q3,q5,q4,b, q0,q1,q2,q3,q5 ：, q0,q1,q3,q5 ,q2 ,= q0,q1,q3,q5 ,q2，q4,b,3、考查子集q0,q1,q3,q5, q1,q5 a：,=q

14、2 , q0,q1,q3,q5 b：,=q1,q3,q5 , q0,q1,q3,q5 ,子集 q0,q1,q3,q5 再分割:,f(q0,a) = ,f(q3,a) = , q0,q3,a：,= , q0,q3, q1,q5 ,b,q0,初态,b,q2,a,b, q0,q3, q1,q5 ,q2 ,q4 ,q1,a,b,b,b,考察字符串：bab,左图识别过程：q0-q1-q2-q4,右图识别过程：q0-q1-q2-q4,考察字符串：bbbab,左图识别过程：q0-q1-q3-q5-q2-q4,右图识别过程：q0-q1-q0-q1-q2-q4,b,设字母表a,b上的正规式R=(a|ba)* 1

15、、构造NFA M ,使得L(M )=L(R) ; 2、将NFA M确定化，得到DFA M 使得L(M )=L(M); 3、将DFA M最小化。,构造NFA M,x,1,a,R=(a|ba)*,2,b,a,将NFA M确定化,1、-closure(x)=x,1,y=q0,K q0 ,2、对K中未标记状态q0做：,(1)标记q0,(2)move(q0,a)=move(x,1,y,a)=1,-closure(1)= 1,y=q1,f(q0,a)=q1,move(q0,b)=,move(x,1,y,b)=,2,-closure(2)= 2=q2,q0 =x,1,y， q1 =1,y,f(q0,b)=q

16、2,K q0 , q1 , q2 ,3、对K中未标记状态q1做：,(1)标记q1,(2)move(q1,a)=,move(1,y,a)=,1,-closure(1)= 1,y=q1,f(q1,a)=q1,q0 =x,1,y， q1 =1,y， q2=2,move(q1,b)=,move(1,y,b)=,2,f(q1,b)=q2,K q0 , q1 , q2 ,4、对K中未标记状态q2做：,(1)标记q2,(2)move(q2,a)=,move(2,a)=,1,-closure(1)= 1,y=q1,f(q2,a)=q1,move(q2,b)=,move(2,b)=,等价的DFA M 如下,f(

17、q0,a)=q1,f(q0,b)=q2,f(q1,a)=q1,f(q1,b)=q2,f(q2,a)=q1,NFA M 转换为DFA M 的过程,f(q0,a)=q1,f(q0,b)=q2,f(q1,a)=q1,f(q1,b)=q2,f(q2,a)=q1,DFA M 的状态图,f(q0,a)=q1,f(q0,b)=q2,f(q1,a)=q1,f(q1,b)=q2,f(q2,a)=q1,q2,初态,a,b,a,b,a,将DFA M最小化,1、初始划分由两个子集组成，即：,：,q0,q1(终态）,q2（非终态）,q0,q1a=,q1,q0,q1b=,q2,2、考查子集q0,q1,q0,q1a=,q1

18、,q0,q1b=,q2,子集q0,q2不能再分割，即q0,q1为等价状态进行合并,q2,初态,终态,a,b,a,第四章 自顶向下的语法分析,（1）消除直接左递归 （2）消除间接左递归的算法 （3）First集合和Follow集合的求解方法 （4）避免回溯的判断方法 （5）简单回溯的消除方法 （6）LL(1)分析表的构造算法 （7）LL(1)分析方法,一、消除左递归,消除间接左递归的算法,消除直接左递归,引进新的非终结符,提公因子,1. 引进新的非终结符的方法,U:=Ux1|Ux2|Uxm|y1|y2|yn,左递归规则形如：,U:=x1 U| x2 U| xm U|,左递归规则,不以U开头,方法

19、：,引进新的非终结符号U,改 写,U:= y1 U | y2 U | yn U ,2.提公因子的方法,U:=(y1|y2|yn),U:=Ux1|Ux2|Uxm|y1|y2|yn,左递归规则形如：,左递归规则,不以U开头,改 写,x1|x2|xm,3.消除间接左递归的算法步骤（1）,(1)将文法中所有的非终结符号排序:,U1,U2,Un;,消除间接左递归的算法步骤（2）,i=2,i=n?,j=1,Y,j=i-1?,Y,存在Ui :=Ujy?,Y,如果Uj:= x1 | x2 | | xk 则Ui:= x1 y| x2 y | | xk y,消除Ui 规则中的直接左递归,j=j+1,N,N,i=i

20、+1,N,结束,考查是否存在排在后面的非终结符（ Ui ）定义为（：=）以排在Ui 前面的非终结符号（Uj）开头的规则。,消除间接左递归的算法步骤（3）,(3)消去多余规则(压缩文法),此算法要求,1）文法没有回路(U,2）文法不存在规则U:=,U),FIRST集的定义,符号串x,推导,终结头符号集,FIRST(x)=,a,|x,a ,aVT,x,FIRST(x),文法避免回溯的条件,多选规则：U:=x1|x2|xn,文法避免回溯的条件:,不含空规则,FIRST(xi ),FIRST( xj ) =,(ij),FOLLOW(U)的定义,非终结符号U的后继终结符号集。,FOLLOW(U)= a,

21、|Z,Ua,aVT,识别符号,特别地：,Z,U,# FOLLOW(U),输入结束符,求FOLLOW(U)的算法步骤1),1) #FOLLOW(Z);,识别符号,求FOLLOW(U)的算法步骤2),2) A:=U,FIRST()-,FOLLOW(U),文法满足避免回溯的条件,U:=x1|x2|xn,1)FIRST(xi)FIRST(xj)= (ij),2)若xj,FIRST(xi)FOLLOW(U)= (ij),非空规则,消除回溯的简单方法,U:=xi|xj,FIRST(xi)FIRST(xj) ,=a,U:=xi|xj,改写,U:=aW|aV,提取a,U:=a(W|V),引入X,U:=aX,X

22、:=W|V,LL(1)分析表M的结构,行标题,非终结符号U,列标题,终结符号a,结束符#,MU,a,规则,当U面临输入符号a时应选择的规则,出错标志,构造LL(1)分析表M的算法,(3)其它均置ERROR,规则U:=x,(1)aFIRST(x),U:=x,MU,a,(2)FIRST(x),U:=x,MU,b,MU,#,FOLLOW(U),空,LL(1)分析方法基本思想,从左到右扫描源程序,从识别符号开始生成句子的最左推导,只要向前查看一个输入符号,便能确定当前应选择的规则,LL(1)方法,LL(1)分析方法的实现,LL(1)方法,LL(1)分析表M,符号栈S,K:,符号栈S的栈顶指针,J:,输

23、入串R的指针,实现步骤,(3)栈顶元素=,(1),栈顶元素,当前符号,匹配,k:=k-1,j:=j+1,(2),栈顶元素SkVN,当前输入符号为Rj,查M表,MSk,Rj元素,Sk:=x1x2xn,x1x2xn,代替,Sk,入栈顺序,由右向左,输入符号=,#,成功,S栈,Sk,xn,x2,x1,栈顶元素出栈,输入下一符号,出栈,P78#4,A aABe| B Bb|b,（1）FIRST(A)=a, ,FIRST(B)=b,A aABe,A 为识别符号,FOLLOW(A)=b, #,A aABe,B Bb,FOLLOW(B)=b, e,P78#4(续),（2）不是LL(1)文法，文法中有直接左递

24、归的规则：,B Bb|b,A aABe| B Bb|b,（3）消除直接左递归：,引进新的非终结符号B,B bB,B bB |,改写后的文法：,A aABe|,B bB,B bB |,P78#4(续),（4）构造LL(1)分析表,FOLLOW(A) =b, #,FOLLOW(B)= FOLLOW(B)= e,FOLLOW(B)=e,A aABe,A ,A ,B bB,B bB,B ,对文法GS: S a| |(T) T T,S|S （1）给出(a,(a,a)的最左推导； （2）该文法是LL(1)文法吗？为什么？ （3）改写成与之等价的LL(1)文法，构造LL(1)分析表。 （4）给出输入串(a,

25、a)#的分析过程，并说明该串是否为G的句子。,(1)句子(a,(a,a)的最左推导： S (T) (T,S) (S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S) (a,(a,S) (a,(a,a),S a| |(T) T T,S|S,（2）改写文法： 消除直接左递归T T,S|S引入新的非终结符号T T ST T ,ST| 改写后的文法： S a| |(T) T ST T ,ST| 消除间接左递归后： S a| |(T) T a T | T|(T)T T ,ST|,消除间接左递归,（3）判断改写后的文法是否是LL(1)文法： 求FOLLOW(T)=FOLLOW(T)=)

26、FILLOW(T)First(,ST)=) ,= 改写后的文法是LL(1)文法,S a| |(T) T a T | T|(T)T T ,ST|,（4）LL（1）分析表,(5)给出句子（a,a）的分析过程,#S,（a,a）#,S (T),#）T（,（a,a）#,匹配,#）T,a,a）#,T a T,#）Ta,a,a）#,匹配,#）T,a）#,T ,ST,#）TS,a）#,匹配,#）TS,a）#,S a,#）Ta,a）#,匹配,#）T,）#,T ,#）,）#,匹配,#,#,成功,第5章 LR分析法,1、LR(0)分析法 2、SLR(1)分析法 3、LR（1）分析法 4、LALR（1）分析法,文法G(Z)如下： S S S (SR |a R *SR|) （1）判断该文法是LR(0)还是SLR(1)文法？并说明理由。 （2）构造相应的分析表,S S S (SR |a R *SR|),（1）判断：,S S S (SR S a,I0,S,S:=S,I1,（,S (SR,S (SR S a,I2,a,S:=a,I3,S,S (SR,R *SR R ),（,a,I4,R,S (SR,I5,*,R *SR,S (SR S a,I6,),R