资源描述：
《编译原理期末复习资料(完整版)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、1.给出语言{anbnambm
2、n,m≥0}的一个上下文无关文法。(6分)解：G[S]：S—>ABA—>aAb
3、εB—>aBb
4、ε2.给出语言{1n0m1m0n
5、n,m≥0}的一个上下文无关文法。解： G[S]：S—>1S0
6、A A—>0A1
7、ε3.P48第6题（5）、（6）.画语法树6、已知文法G： <表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i （５）i+(i+i) （６）i+i*i 解：(5)语法树：（6）语法树：4.P48第13题
8、 直接短语等13、一个上下文无关文法生成句子abbaa的推导树如下：(3)求直接短语解：直接短语有：a ε bP102例题6.1及其分析.(后加画语法树)例6.1设文法G[S]为：(1)S—>aAcBe(2)A—>b(3)A—>Ab(4)B—>d对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。解：设一个先进后出的符号符，并把句子左括号“#”号放入栈底，其分析过程如下：步骤符号栈输入符号串动作（1）#abbcde#移进（2）#abbcde#移进（3）#abbcde#归约（A—>b）（4）#aAbcde#移进（5
9、）#aAbcde#归约（A—>Ab）（6）#aAcde#移进（7）#aAcde#移进（8）#aAcde#归约（B—>d）（9）#aAcBe#移进（10）#aAcBe#归约（S—>aAcBe）（11）#S#接受语法树如下：一、计算分析题（60%）1、正规式→NFA→DFA→最简DFAP72第1题（1）、（4）；第一题1、构造下列正规式相应的DFA.（1）1(0
10、1)*101 解：先构造NFA用子集法将NFA确定化 01SAAAABABACABACAABZABZACAB除S，A外，重新命名其他状态，令AB为B、AC为C、ABZ为D
11、，因为D含有Z（NFA的终态），所以D为终态,因此有：01SAAABBCBCADDCB得到DFA如下所示：(4)b((ab)*
12、bb)*ab 解：先构造NFA得到DFA如下所示：P72第4题（a）4、把下图确定化和最小化解：确定化：用子集法将NFA确定化 ab00110101110重新命名，以Ａ、Ｂ、Ｃ代替{0}、{01}、{1}，其中A为初态，A，B为终态，因此有：abABCBBCCA最小化：： 初始分划得终态组{A,B}，非终态组{C} Π0：{A,B}，{C}，对终态组进行审查，判断A和B是等价的，故这是最后的划分。重新
13、命名，以A、C代替{A,B}、{C}，因此有：abAACCA即DFA最小化如下：第7题7、给文法G[S]： S→aA
14、bQ A→aA
15、bB
16、b B→bD
17、aQ Q→aQ
18、bD
19、b D→bB
20、aA E→aB
21、bF F→bD
22、aE
23、b 构造相应的最小的DFA。解：先构造NFA：用子集法将NFA确定化：abSAQAABZBZQDBQDQQDZDZABDAB将S、A、BZ、B、Q、DZ、D重新命名，分别用0、1、2、3、4、5、6表示。因为2、5中含有Z，所以它们为终态。因此有：ab014112246346445513613初始分划得
24、：终态组｛2,5｝，非终态组｛0,1,3,46｝ Π0：｛2,5｝,｛0,1,3,4,6｝ 对｛0,1,3,4,6｝进行审查： {1,4}输入b到达｛2,5｝，而{0,3,6}输入b到达｛3,4,6｝，故得到新分划｛1,4｝,｛0,3,6｝ Π1：｛2,5｝,｛1,4｝,｛0,3,6｝ 对｛0,3,6｝进行审查： {0}经过b到达｛2｝，{3,6}经过b到达｛3,6｝，故得到新分划｛0｝，｛3,6｝Π3：得到最后划分{0}，{1,4}，{2,5}，{3,6} 重新命名，以A，B，C，D分别代替{0}，{1,4}，{
25、2,5}，{3,6},其中A为始态，C为终态，可得到最小DFA如下：2、自顶向下方法(一)设文法G(E)：E→E+T
26、TT→T*F
27、FF→i
28、(E) (1)判断是否为LL(1)文法. (2)构造文法的预测分析表.解：详见P93-96例题。(1)由于文法中含有左递归，所以必须先消除左递归，使文法变为：E→TE`E`→+TE`
29、εT→FT`T`→*FT`
30、εF→i
31、(E)FIRST集合如下：FIRST（E）={(,i}FIRST（E`）={+,ε}FIRST（T）={(,i}FIRST（T`）={*,ε}FIRST（F）={(
32、,i}FOLLOW集合如下：FOLLOW（E）={),#}FOLLOW（E`）={),#}FOLLOW（T）={+,),#}FOLLOW（T`）={+,),#}FOLLOW（F）={+,*,),#}各产生式的SELECT集合如下：SELECT（E→TE`）={(,i}SELE
