编译原理期末复习资料(完整版)

编译原理期末复习资料(完整版)

ID:12876695

大小:510.00 KB

页数:14页

时间:2018-07-19

编译原理期末复习资料(完整版)_第1页
编译原理期末复习资料(完整版)_第2页
编译原理期末复习资料(完整版)_第3页
编译原理期末复习资料(完整版)_第4页
编译原理期末复习资料(完整版)_第5页
资源描述:

《编译原理期末复习资料(完整版)》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

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  (5)i+(i+i) (6)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重新命名,以A、B、C代替{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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。