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

《编译原理》期末总复习考试题型及分数分布填空题(10分）单选题（20分）判断题（10分）解析题（60分）第二章文法与形式语言简介（1）给出句型或句子最左推导或最右推导（规范推导）；（2）画出句型或句子的语法树；（3）求句型的短语、简单短语、句柄；（4）判断一个文法是二义性的文法P28#3规范推导：aa+a*S∷=SS*|SS+|aS=aa+a*Sa+a*=SS+a*=Sa*=SS*=语法树：SSS*SS+aaaP28#4只含有4个符号的句子：Z∷=U0∣V1U∷=Z1∣1V∷=Z0∣0U0=Z10=U010=1010Z=0100Z=V1=U000=Z00=1000U0=Z10=V110=0110Z=Z=V1=Z00=V100=P28#5S∷=ABA∷=aA︱εB∷=bBc︱bcA∷=aA︱ε描述的语言:{an|n=0}B∷=bBc︱bc描述的语言:{bncn|n=1}L(G[S])={anbmcm|n=0,m=1}P28#7E∷=T∣E+T∣E-TT∷=F∣T*F∣T/FF∷=(E)∣i，句型T+T*F+i的语法树：EE+TTE+TT*FFi短语：T+T*F+i,T+T*F简单短语：T*F，T，i句柄：T已知文法G[E]:E::=E+T|TT::=T*F|FF::=(E)|i1、试给出句子i*(i+i)的规范推导；2、画出相应的语法树；(注意：相同的叶子节点用不同的下标加以区分，如：i1、i2、i3…)3、指出该句子所有的短语、简单短语、句柄。存在的问题给出的推导不是规范推导；一次使用多条规则；没有标明句柄所在的位置；不是从文法的开始符号进行推导；句子i*(i+i)的规范推导ET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的短语、简单短语;i2是相对于非终结符号F、T、E的短语、简单短语;i2+i3是相对于非终结符号E的短语;(i2+i3)是相对于非终结符号F的短语;i1*(i2+i3)是相对于非终结符号T、E的短语;i1是句柄;P28#8S∷=S*S|S+S|(S)|a给出句子a+a*a两棵不同的语法树SSS*S+SaaaSSS+S*Saaa已知文法G[S]:S::=iSeS|iS|i试说明该文法是二义性的文法。句子iiiei两棵不同的语法树S::=iSeS|iS|i第三章词法分析1、正规文法和有限自动机的等价性2、正规式和有限自动机的等价性3、NFA到DFA转换的子集法及最小化正则文法的状态图画法如下：1、文法中的每个非终结符号对应状态图中的一个结点，即图中的每个结点代表一个非终结符号。2、增设一个结点代表开始状态S，而文法中的识别符号对应的结点为终结状态3、对于文法中的每一条形如U→a的规则，画一条从结点S指向结点U的弧线，并在弧上标记a。4、对于文法中每一条形如U∷=Wa的规则，画一条从结点W指向结点U的弧线，并在弧上标记a。SUa开始状态WUa有正则文法G[Z]：Z::=Ua|Vb，U::=Zb|b，V::=Za|a，画出该文法的状态图，并检查句子abba是否合法。SUVZaaabbbP60#1句子abba合法。Z::=Ua|VbU::=Zb|bV::=Za|aZ::=Ua|Vb，U::=Zb|b，V::=Za|a从正规式R构造NFAM的步骤11、把正规式R表示为：初态终态xyR从∑上的正规式R构造NFAM的步骤22、把R分裂并加进新的结点每条弧标记为∑上的一个字符或ε结点分裂规则①加入k结点1弧变2弧结点分裂规则②1弧变2弧结点分裂规则③加入k结点闭包去掉变闭环前后各1条空弧kijεεR1子集法的基本思想NFA基本思想：NFA的一组状态DFA的一个状态对应等价的DFA子集法转换子集法设已给具有ε动作的NFAM=（K,∑,f,S0,Z)构造相应的确定的有限自动机:DFAM′=（K′,∑,f′,q0,Z′)构造K′及f′的步骤可递归地描述如下：（1）给出M′的初态：递归描述步骤（1）K′={q0}q0=ε-closure(S0)递归描述步骤（2）（2）对于K′中尚未标记的状态qi={Si1,Si2,…,Sim},SikK做：①标记qi；②对于每一个a∈∑，置：③若qj不在K′中,则将qjf′(qi,a)=qjK′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初态终态xyb(ab|bb)*ab初态终态xya1b2ε3εab|bb4b初态终态xya1b2ε3ε4bbb初态终态xya1b2ε3εa4bb56bbab（2）DFA1、ε-closure(x)={x}=q0初态终态xya1b2ε3εa4bb56bbK′＝｛q0｝2、对K′中未标记状态q0做：move(q0,a)=move({x},a)=Φmove(q0,b)=move({x},b)={1}ε-closure({1})={1,2,3}=q1f′(q0,b)=q1K′＝｛q0,q1｝3、对K′中未标记状态q1做：初态终态xya1b2ε3εa4bb56bbmove(q1,a)=move({1,2,3},a)={4,6}ε-closure({4,6})={4,6}=q2f′(q1,a)=q2move(q1,b)=move({1,2,3},b)={5}ε-closure({5})={5}=q3f′(q1,b)=q3K′＝｛q0,q1,q2,q3｝4、对K′中未标记状态q2做：move(q2,a)=初态终态xya1b2ε3εa4bb56bbmove({4,6},a)=Φmove(q2,b)=move({4,6},b)={2,y}ε-closure({2,y})={2,3,y}=q4f′(q2,b)=q4K′＝｛q0,q1,q2,q3,q4｝初态终态xya1b2ε3εa4bb56bb5、对K′中未标记状态q3做：move(q3,a)=move({5},a)=Φmove(q3,b)=move({5},b)={2}ε-closure({2})={2,3}=q5f′(q3,b)=q5K′＝｛q0,q1,q2,q3,q4,q5｝初态终态xya1b2ε3εa4bb56bb6、对K′中未标记状态q4做：move(q4,a)=move({2,3,y},a)={4,6}ε-closure({4,6})={4,6}=q2f′(q4,a)=q2move(q4,b)=move({2,3,y},b)={5}ε-closure({5})={5}=q3f′(q4,b)=q3K′＝｛q0,q1,q2,q3,q4,q5｝初态终态xya1b2ε3εa4bb56bb7、对K′中未标记状态q5做：move(q5,a)=move({2,3},a)={4,6}ε-closure({4,6})={4,6}=q2f′(q5,a)=q2move(q5,b)=move({2,3},b)={5}ε-closure({5})={5}=q3f′(q5,b)=q3K′＝｛q0,q1,q2,q3,q4,q5｝等价的DFAM′如下K′＝｛q0,q1,q2,q3,q4,q5｝f′(q0,a)=Φ,f′(q0,b)=q1f′(q1,a)=q2,f′(q1,b)=q3f′(q2,a)=Φ,f′(q2,b)=q4f′(q3,a)=Φ,f′(q3,b)=q5f′(q4,a)=q2,f′(q4,b)=q3Z′＝｛q4｝f′(q5,a)=q2,f′(q5,b)=q3NFAM转换为DFAM′的过程IIaIbq0={x}q1={1,2,3}q2={4,6}q3={5}q4={2,3,y}q1={1,2,3}q2={4,6}q3={5}q2={2,3,y}q5={2,3}q3={5}f′(q0,b)=q1f′(q1,a)=q2,f′(q1,b)=q3f′(q2,b)=q4f′(q3,b)=q5f′(q4,a)=q2,f′(q4,b)=q3f′(q5,a)=q2,f′(q5,b)=q3q5={2,3}q2={4,6}q2={4,6}q3={5}DFAM′的状态图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,f′(q5,a)=q2,f′(q5,b)=q3bq0初态bq1q2aq3b0q4终态q5babab最小化q0初态bq1q2aq3b0q4终态q5babab1、初始划分由两个子集组成，即：∏：｛q0,q1,q2,q3，q5｝(非终态）｛q4｝（终态）b2、考查子集｛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｝q0初态bq1q2aq3b0q4终态q5bababb｛q0,q1,q2,q3,q5｝：｛q0,q1,q3,q5｝{q2｝∏={｛q0,q1,q3,q5｝,｛q2｝，｛q4｝}q0初态bq1q2aq3b0q4终态q5bababb3、考查子集｛q0,q1,q3,q5｝｛q1,q5｝a：={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｝q0初态bq1q2aq3b0q4终态q5bababbq0初态bq1q2aq3b0q4终态q5bababq0初态bq20q4ab｛q0,q3,｝｛q1,q5｝{q2｝{q4｝q1abbb考察字符串：bab左图识别过程：q0---q1---q2---q4右图识别过程：q0---q1---q2---q4考察字符串：bbbab左图识别过程：q0---q1---q3---q5---q2---q4右图识别过程：q0---q1---q0---q1---q2---q4q0初态bq20q4abq1abbq0初态bq1q2aq3b0q4终态q5bababb设字母表∑＝{a,b}上的正规式R=(a|ba)*1、构造NFAM′,使得L(M′)=L(R);2、将NFAM′确定化，得到DFAM使得L(M′)=L(M);3、将DFAM最小化。构造NFAM′xy1εεaR=(a|ba)*2ba将NFAM′确定化xy1εε2baa1、ε-closure({x})={x,1,y}=q0K′＝｛q0｝2、对K′中未标记状态q0做：(1)标记q0(2)move(q0,a)=move({x,1,y},a)={1}ε-closure({1})={1,y}=q1f′(q0,a)=q1xy1εε2baamove(q0,b)=move({x,1,y},b)={2}ε-closure({2})={2}=q2q0={x,1,y}，q1={1,y}f′(q0,b)=q2K′＝｛q0,q1,q2｝3、对K′中未标记状态q1做：(1)标记q1(2)move(q1,a)=move({1,y},a)={1}ε-closure({1})={1,y}=q1f′(q1,a)=q1q0={x,1,y}，q1={1,y}，q2={2}xy1εε2baamove(q1,b)=move({1,y},b)={2}f′(q1,b)=q2K′＝｛q0,q1,q2｝4、对K′中未标记状态q2做：(1)标记q2(2)move(q2,a)=move({2},a)={1}ε-clo