编译原理期中测试答案.doc

编译原理期中测试答案.doc

ID:51245304

大小:46.00 KB

页数:7页

时间:2020-03-10

编译原理期中测试答案.doc_第1页
编译原理期中测试答案.doc_第2页
编译原理期中测试答案.doc_第3页
编译原理期中测试答案.doc_第4页
编译原理期中测试答案.doc_第5页
资源描述:

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

1、编译原理期中测试答案三、单项选择题(每题3分,共15分)1.设有文法G[S]:S→(AS)

2、(b)A→(SaA)

3、(a)该文法的句型(((b)a(a))(b))有C个直接短语。A.1B.2C.3D.42.如果一个文法满足D,则称该文法是二义性文法。(1)文法的某一个句子存在两个(包括两个)以上的语法树(2)文法的某一个句子存在两个(包括两个)以上的最左推导(3)文法的某一个句子存在两个(包括两个)以上的最右推导(4)在进行归约时,文法的某些规范句型的句柄不唯一上述描述中的所有正确描述有:A.(1)B.(1)(2)C.(1)(2

4、)(3)D.(1)(2)(3)(4)3.构造一个不带回溯的自顶向下语法分析器,要求文法满足E。A.对每个形如A→x1

5、x2

6、…

7、xn的产生式,要求FIRST(xi)与FIRST(xj)的交集为空集(i≠j)B.对每个形如A→x1

8、x2

9、…

10、xn的产生式,若xiε,则要求FIRST(xj)与FOLLOW(A)的交集为空集(i≠j)C.不含左递归D.A和B同时满足E.A、B和C同时满足4、给定文法A→bA

11、cc,下列符号串中,是该文法的句子的是C。①cc②bcbc③bcbcc④bccbcc⑤bbbccA①B.①③④⑤C.①⑤D.①

12、④⑤5、若一个句型中出现了某一产生式的右部,则此右部B是该句型的句柄。A.一定B.不一定C.一定不D.无法判断四、简述题(每题5分,共20分)1、写一上下文无关文法,它能产生语言。S→A#BA→Aa

13、eB→Bb

14、e2、将文法G[S]改写为等价的G′[S],使G′[S]不含左递归和左公共因子。  G[S]:S→bSAe

15、bA   A→Ab

16、d答:文法G[S]改写为等价的不含左递归和左公共因子的G'[S] S→bB  B→SAe

17、A  A→dA'  A'→bA'

18、ε3、什么是文法的二义性?下面的文法是二义的吗?为什么?G[S]:S

19、→AB

20、ABD  A→aB→CD

21、DC→cD→d答:如果一个文法存在某个句子对应两棵不同的语法树,则该文法是二义的。是,句子acd有两个完全不同的语法树。4、设文法G[A]:A→[BB→X]

22、BAX→Xa

23、Xb

24、a

25、b试求出文法G[A]产生的语言对应的正则式。解:X→X(a

26、b)

27、a

28、bX→(a

29、b)·(a

30、b)*代入B→X]

31、BAB→(a

32、b)·(a

33、b)*]

34、BAB→(a

35、b)(a

36、b)*]·A*代入A→[(a

37、b)(a

38、b)*]·A*[(a

39、b)(a

40、b)*]([(a

41、b)(a

42、b)*])*五、计算题(共41分)1、已知

43、文法G(S):S→a

44、∧

45、(T)T→T,S

46、S⑴给出句子(a,(a,a))的最左推导并画出语法树;⑵给出句型((T,S),a)的短语、直接短语、句柄。(10分)答:最左推导:(2分)S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))语法树:ST()T,SSa(T)T,SSaa3给出与正规式R=(ab)*(a

47、b*)ba等价的NFA。(5分)答案:4将下图的NFA确定化为DFA。(8分)答案: 用子集法确定化如下表IIa

48、Ib状态{X,1,2}{1,2}..{1,2,3}{1,2,Y}{1,2}..{1,2}..{1,2,Y}{1,2}..{1,2,3}{1,2,3}{1,2,3}{1,2,3}X123确定化后如下图5、设文法G(S):S→S+aF

49、aF

50、+aFF→*aF

51、*a⑴消除左递归和回溯;⑵构造相应的FIRST和FOLLOW集合;⑶构造预测分析表(12分)答:⑴(消除左递归2分,提公共左因子2分)S→aFS’

52、+aFS’S'→+aFS’

53、εF→*aF’F’→F

54、ε⑵ (4分)FIRST(S)={a,+}FOLLOW(S)={#}FIRS

55、T(S')={+,ε}FOLLOW(S')={#}FIRST(F)={*}FOLLOW(F)={+,#}FIRST(F')={*,ε)FOLLOW(F')={+,#}⑶ (4分)-a+*#SS→aFS'S→+aFS'--S'-S'→+aFS'-S'→εF--F→*aF'-F'-F'→εF'→FF'→ε

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

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

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