编译原理题库

编译原理题库

ID:39547183

大小:502.39 KB

页数:24页

时间:2019-07-06

编译原理题库_第1页
编译原理题库_第2页
编译原理题库_第3页
编译原理题库_第4页
编译原理题库_第5页
资源描述:

《编译原理题库》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、Tiange'sreference第一章§什么是编译器?§编译程序的结构分为几个阶段,各阶段的任务是什么?§遍、编译前端及编译后端的含义?§编译程序的生成方式有哪些?第二章§1.写一文法,使其语言是偶正整数的集合。§要求:(1)允许0打头(2) 不允许0打头解:(1)允许0开头的偶正整数集合的文法E→NT

2、DT→NT

3、DN→D

4、1

5、3

6、5

7、7

8、9D→0

9、2

10、4

11、6

12、8(2)不允许0开头的偶正整数集合的文法E→NT

13、DT→FT

14、GN→D

15、1

16、3

17、5

18、7

19、9D→2

20、4

21、6

22、8F→N

23、0G→D

24、02.证明下述文

25、法G[〈表达式〉]是二义的。〈表达式〉∷=a

26、(〈表达式〉)

27、〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+

28、-

29、*

30、/解:可为句子a+a*a构造两个不同的最右推导:最右推导1〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉aÞ〈表达式〉*aÞ〈表达式〉〈运算符〉〈表达式〉*aÞ〈表达式〉〈运算符〉a*aÞ〈表达式〉+a*aÞa+a*a最右推导2〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉〈运算符〉aÞ〈表达

31、式〉〈运算符〉〈表达式〉*aÞ〈表达式〉〈运算符〉a*aÞ〈表达式〉+a*aÞa+a*a3.给出生成下述语言的上下文无关文法:(1){anbnambm

32、n,m>=0}(2){1n0m1m0n

33、n,m>=0}解:(1){anbnambm

34、n,m>=0}S→AAA→aAb

35、ε24Tiange'sreference(2){1n0m1m0n

36、n,m>=0}S→1S0

37、AA→0A1

38、ε第三章1、构造一个DFA,它接收∑={a,b}上所有满足下述条件的字符串:字符串中的每个a都有至少一个b直接跟在其右边。解:已知∑=

39、{a,b},根据题意得出相应的的正规式为:(b*abb*)*根据正规式画出相应的DFAM,如下图所示用子集法将其确定化XY(b*abb*)*XYb*abb*1eeXYb123456bbaeeeeeeIIaIb{X,1,2,3,Y}{4}{2,3}{4}—{5,6,1,2,3,Y}{2,3}{4}{2,3}{5,6,1,2,3,Y}{4}{6,1,2,3,Y}{6,1,2,3,Y}{4}{6,1,2,3,Y}IIaIb0121—3212314414由DFA得状态图用最小化方法化简得:{0},{1},{2},

40、{3,4},按顺序重新命名DFAM’24Tiange'sreference10243aaaabbbbb0312aaabbb第四章练习1:文法G[V]:V→N

41、N[E]E→V

42、V+EN→i是否为LL(1)文法,如不是,如何将其改造成LL(1)文法。解:LL(1)文法的基本条件是不含左递归和回溯(公共左因子),而G[V]中含有回溯,所以先消除回溯得到文法G’[V]:G’[V]:V→NV’V’→ε

43、[E]E→VE’E’→ε

44、+EN→i由LL(1)文法的充要条件可证G’[V]是LL(1)文法练习2:有文法G[s]

45、:S→BAA→BS

46、dB→aA

47、bS

48、c(1)证明文法G是LL(1)文法。(2)构造LL(1)分析表。(3)写出句子adccd的分析过程解:(1)一个LL(1)文法的充要条件是:对每一个非终结符A的任何两个不同产生式A→α

49、β,有下面的条件成立:①FIRST(α)∩FIRST(β)=Φ;②若β*Þε,则有FIRST(α)∩FOLLOW(A)=Φ对于文法G[s]:S→BAA→BS

50、dB→aA

51、bS

52、c其FIRST集如下:FIRST(B)={a,b,c};FIRST(A)={a,b,c,d};FIRST(S)

53、={a,b,c}。其FOLLOW集如下:首先,FOLLOW(S)={#};对S→BA有:FIRST(A){ε}加入FOLLOW(B),即FOLLOW(B)={a,b,c,d};对A→BS有:FIRST(S){ε}加入FOLLOW(B),即FOLLOW(B)={a,b,c,d};对B→aA有:FOLLOW(B)加入FOLLOW(A),即FOLLOW(A)={a,b,c,d};对B→bS有:FOLLOW(B)加入FOLLOW(S),即FOLLOW(S)={#,a,b,c,d};由A→BS

54、d得:FIRST

55、(BS)∩FIRST(d)={a,b,c}∩{d}=Φ;由B→aA

56、bS

57、c得:FIRST(aA)∩FIRST(bS)∩FIRST(c)={a}∩{b}∩{c}=Φ。由于文法G[s]不存在形如β→ε的产生式,故无需求解形如FIRST(α)∩FOLLOW(A)24Tiange'sreference的值。也即,文法G[S]是一个LL(1)文法。(2)由G[s]:S→BAA→BS

58、dB→aA

59、bS

60、c的FIRST(B)={a,b,c

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

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

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