《大连海事大学《编译原理》期末总复习》由会员分享，可在线阅读，更多相关《大连海事大学《编译原理》期末总复习（91页珍藏版）》请在金锄头文库上搜索。
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,
8、b(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,
10、b) =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) =
13、q2, 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：,=
14、q2 , 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、构造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,-clos
