编译原理复习题答案

编译原理复习题答案

ID:24701577

大小:207.00 KB

页数:16页

时间:2018-11-09

编译原理复习题答案_第1页
编译原理复习题答案_第2页
编译原理复习题答案_第3页
编译原理复习题答案_第4页
编译原理复习题答案_第5页
资源描述:

《编译原理复习题答案》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、.二、概念题1、设有文法:P→P+Q

2、QQ→Q*R

3、RR→(P)

4、i(1)证明Q*R+Q+Q是它的一个句型。(3分)(2)给出Q*R+Q+Q的所有短语,直接短语和句柄。(4分)(3)给出句子i+i*i的最右推导。(4分)(4)给出句子i+i*i的最左推导。(4分)2、设有文法:E→E+T

5、TT→T*F

6、FF→(E)

7、i(1)证明E+T*F是它的一个句型。(3分)答案:(2)给出E+T*F的所有短语,直接短语和句柄。(4分)短语:E+T*F,T*F,直接短语:T*F句柄:T*F(3)给出句子i+i*i的最右推导。(4分)3、写出

8、表达式a+b*(c-d)对应的逆波兰式和三元式序列。答案:逆波兰式:(abcd-*+)...三元式序列:OPARG1ARG2(1)-cd(2)*b(1)(3)+a(2)三、词法分析题给出下面语言的相应文法L1={anbnambm

9、n,m≥0}答案:  S→AB

10、A

11、B

12、∑ A→ aAb

13、ab B→ aBb

14、ab给出下面语言的相应文法L2={anbnci

15、n≥1,i≥0}答案: S→ AB

16、B    A→ a

17、aA B→ bBc

18、bc给出下面语言的相应文法L3={anbncm

19、m,n≥1,n为奇数,m为偶数}。答案:文法G(S)

20、:S→ACA→aaAbb/abC→ccCcc/cc四、词法分析题...1、构造下面正规式相应的DFA((0

21、1)*

22、(11)*)*(要求:先将正规式转化为NFA,再将NFA确定化,最小化)2、构造下面正规式相应的DFA1(0

23、1)*101答案:I       I0       I1 {X}    Ф   {A,B,C}  {A,B,C}   { B,C}     { B,C,D}  {B,C}    { B,C}     { B,C,D}  {B,C,D}    { B,C,E}  { B,C,D} {B,C,E}    { 

24、B,C}     {B,C,D,y} {B,C,D,y}   {B,C,E}     { B,C,D}3、构造一个DFA,它接受S={a,b}上所有包含ab的字符串。(要求:先将正规式转化为NFA,再将NFA确定化,最小化)答案:(一)相应的正规式为(a

25、b)*ab(a

26、b)*(二)①与此正规式对应的NFA为②状态转换矩阵为:...③最小化:{0,1,2}{3,4,5}{0,2},1,{3,4,5}baa01b3ba④所以此等价的DFA为:开始状态为0,终态集为{3},状态集为{0,1,3},输入字母表是{a,b}状态转换图如

27、上。4、构造与正规式b(a

28、b)*ba等价的DFA五、语法分析题1、对下面的文法G:Expr→-ExprExpr→(Expr)

29、VarExprTailExprTail→-Expr

30、εVar→idVarTailVarTail→(Expr)

31、ε...(1)构造LL(1)分析表。(12分)答案:(1)FIRST(Expr)={_,(,id}FIRST(ExprTail)={_,ε}FIRST(Var)={id}FIRST(VarTail)={(,ε}FOLLOW(Expr)={#,)}FOLLOW(ExprTail)={#,)}FO

32、LLOW(Var)={_,#,)}FOLLOW(VarTail)={_,#,)}(2)给出对句子id—id((id))的分析过程。(8分)步骤符号栈输入串所用产生式0#Exprid__id((id))#1#ExprTailVarid__id((id))#Expr→VarExprTail2#ExprTailVarTailidid__id((id))#Var→idVarTail3#ExprTailVarTail__id((id))#4#ExprTail__id((id))#VarTail→ε5#Expr___id((id))#Ex

33、prTail→_Expr6#Expr_id((id))#7#Expr__id((id))#Expr→_Expr8#Exprid((id))#...9#ExprTailVarid((id))#Expr→VarExprTail10#ExprTailVarTailidid((id))#Var→idVarTail11#ExprTailVarTail((id))#12#ExprTail)Expr(((id))#VarTail→(Expr)13#ExprTail)Expr(id))#14#ExprTail))Expr((id))#Expr

34、→(Expr)15#ExprTail))Exprid))#16#ExprTail))ExprTailVarid))#Exp→VarExprTail17#ExprTail))ExprTailVarTailidid))#Var→idVarTail18#ExprTail))Expr

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

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

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