资源描述：
《大连海事大学《编译原理》期末总复习.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《编译原理》 期末总复习考试题型及分数分布填空题(10分）单选题（20分）判断题（10分）解析题（60分）第二章文法与形式语言简介（1）给出句型或句子最左推导或最右推导（规范推导）；（2）画出句型或句子的语法树；（3）求句型的短语、简单短语、句柄；（4）判断一个文法是二义性的文法P28#3规范推导：aa+a*S∷=SS*
2、SS+
3、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=
4、>V1=>U000=>Z00=>1000U0=>Z10=>V110=>0110Z=>Z=>V1=>Z00=>V100=>P28#5S∷=ABA∷=aA︱εB∷=bBc︱bcA∷=aA︱ε描述的语言:{an
5、n>=0}B∷=bBc︱bc描述的语言:{bncn
6、n>=1}L(G[S])={anbmcm
7、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
8、TT::=
9、T*F
10、FF::=(E)
11、i1、试给出句子i*(i+i)的规范推导；2、画出相应的语法树；(注意：相同的叶子节点用不同的下标加以区分，如：i1、i2、i3…)3、指出该句子所有的短语、简单短语、句柄。存在的问题给出的推导不是规范推导；一次使用多条规则；没有标明句柄所在的位置；不是从文法的开始符号进行推导；句子i*(i+i)的规范推导ETT*FT*(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)的语法树短语、简单短语、句柄为了区分相同的短语，可以
12、采用加下标的方法。i1、i3是相对于非终结符号F、T的短语、简单短语;i2是相对于非终结符号F、T、E的短语、简单短语;i2+i3是相对于非终结符号E的短语;(i2+i3)是相对于非终结符号F的短语;i1*(i2+i3)是相对于非终结符号T、E的短语;i1是句柄;P28#8S∷=S*S
13、S+S
14、(S)
15、a给出句子a+a*a两棵不同的语法树SSS*S+SaaaSSS+S*Saaa已知文法G[S]:S::=iSeS
16、iS
17、i试说明该文法是二义性的文法。句子iiiei两棵不同的语法树S::=iSeS
18、iS
19、i第三章词法分析1、正规文法和有限自动机的等价性2、
20、正规式和有限自动机的等价性3、NFA到DFA转换的子集法及最小化正则文法的状态图画法如下：1、文法中的每个非终结符号对应状态图中的一个结点，即图中的每个结点代表一个非终结符号。2、增设一个结点代表开始状态S，而文法中的识别符号对应的结点为终结状态3、对于文法中的每一条形如U→a的规则，画一条从结点S指向结点U的弧线，并在弧上标记a。4、对于文法中每一条形如U∷=Wa的规则，画一条从结点W指向结点U的弧线，并在弧上标记a。SUa开始状态WUa有正则文法G[Z]：Z::=Ua
21、Vb，U::=Zb
22、b，V::=Za
23、a，画出该文法的状态图，并检查句子abba
24、是否合法。SUVZaaabbbP60#1句子abba合法。Z::=Ua
25、VbU::=Zb
26、bV::=Za
27、aZ::=Ua
28、Vb，U::=Zb
29、b，V::=Za
30、a从正规式R构造NFAM的步骤11、把正规式R表示为：初态终态xyR从∑上的正规式R构造NFAM的步骤22、把R分裂并加进新的结点每条弧标记为∑上的一个字符或ε结点分裂规则①加入k结点1弧变2弧结点分裂规则②1弧变2弧结点分裂规则③加入k结点闭包去掉变闭环前后各1条空弧kijεεR1子集法的基本思想NFA基本思想：NFA的一组状态DFA的一个状态对应等价的DFA子集法转换子集法设已给具有ε动作的
31、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},SikK做：①标记qi；②对于每一个a∈∑，置：③若qj不在K′中,则将qjf′(qi,a)=qjK′M′J=move({Si1,Si2,…,Sim},a)，qj=ε-closure(J)=Ia递归描述步骤（3）（3）重复（2）直到M′中不再
32、有未标记的状态为止。至少含有一个Z中元素的qi作为M′的终态构造正规式b(ab
33、bb)*ab的
