编译原理平时作业-答案.doc

编译原理平时作业-答案.doc

ID:51958772

大小:286.00 KB

页数:21页

时间:2020-03-20

编译原理平时作业-答案.doc_第1页
编译原理平时作业-答案.doc_第2页
编译原理平时作业-答案.doc_第3页
编译原理平时作业-答案.doc_第4页
编译原理平时作业-答案.doc_第5页
资源描述:

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

1、平时作业1对于下列语言分别写出它们的正规表达式。(1) 英文字母组成的所有符号串,要求符号串中顺序包含五个元音。答: 令Letter表示除这五个元音外的其它字母。  ((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))*(2) 英文字母组成的所有符号串,要求符号串中的字母依照词典顺序排列。答:A*B*....Z*(3) Σ={0,1}上的含偶数个1的所有串。答: (0

2、10*1)*(4) Σ={0,1}上的含奇数个1的所有串。答

3、:(0

4、10*1)*1(5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。答:设S是符合要求的串,

5、S

6、=2k+1(k≥0)。则S→S10

7、S21,

8、S1

9、=2k(k>0),

10、S2

11、=2k(k≥0)。且S1是{0,1}上的串,含有奇数个0和奇数个1。 S2是{0,1}上的串,含有偶数个0和偶数个1。考虑有一个自动机M1接受S1,那么自动机M1如下:和L(M1)等价的正规表达式,即S1为:((00

12、11)

13、(01

14、10)(00

15、11)*(01

16、10))*(01

17、10)(00

18、11)*类似的

19、考虑有一个自动机M2接受S2,那么自动机M2如下:和L(M2)等价的正规表达式,即S2为:((00

20、11)

21、(01

22、10)(00

23、11)*(01

24、10))*因此,S为:((00

25、11)

26、(01

27、10)(00

28、11)*(01

29、10))*(01

30、10)(00

31、11)*0

32、((00

33、11)

34、(01

35、10)(00

36、11)*(01

37、10))*1(6) 不包含子串011的由0和1组成的符号串的全体。答:1*

38、1*0(0

39、10)*(1

40、ε)(7) 由0和1组成的符号串,把它看成二进制数,能被3整除的符号串的全

41、体。答:假设w的自动机如下:对应的正规表达式:(1(01*0)1

42、0)*2给出接受下列在字母表{0,1}上的语言的DFA。(1) 所有以00结束的符号串的集合。(2) 所有具有3个0的符号串的集合。答:(1)DFA M=({0,1},{q0,q1,q2},q0,{q2},δ)其中δ定义如下:δ(q0,0)=q1    δ(q0,1)=q0δ(q1,0)=q2    δ(q1,1)=q0δ(q2,0)=q2    δ(q2,1)=q0(2)正则表达式:1*01*01*01*DFA M=({0,1}

43、,{q0,q1,q2,q3},q0,{q3},δ)其中δ定义如下:δ(q0,0)=q1    δ(q0,1)=q0δ(q1,0)=q2    δ(q1,1)=q1δ(q2,0)=q3    δ(q2,1)=q2δ(q3,1)=q3    3下面是用正规式表示的变量声明:(int

44、float)id(,id)*;请改用上下文无关文法表示,也就是写一个上下文无关文法,它和该正规式等价。答:D®TL;T®int

45、floatL®L,id

46、id4试分析下面给出的if-then-else语句的文法,它的提出原

47、本是为了矫正dangling-else(悬而未决的-else)文法的二义性:stmt→ifexprthenstmt

48、matched-stmtmatched-stmt→ifexprthenmatched-stmtelsestmt

49、other试说明此文法仍然是二义性的。答:考虑句子ifethenifethenotherelseifethenotherelseother它具有如下所示的两种分析树stmtexprtheneifstmtifmatched-stmtexprthenmatched-stmte

50、otherifeslestmtmatched-stmtexprthenmatched-stmteothereslestmtmatched-stmtotherstmtmatched-stmtifexprthenmatched-stmteifeslestmteslestmtmatched-stmtexprthenestmtotherexprthenmatched-stmteotherifmatched-stmtother则上面给出的if-then-else文法仍是二义性的。4证明下面文法是SLR(1

51、)文法,并构造其SLR分析表。E→E+T

52、TT→TF

53、FF→F*

54、a

55、b答:该文法的拓广文法G'为(0)E'→E(1)E→E+T(2)E→T(3)T→TF(4)T→F(5)F→F*(6)F→a(7)F→b其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0={E'→·E,E→·E+T,E→·T,T→·TF,T→·F,F→·F*,        F→·a,F→·b}I1={E'→E·,E→E·+T}I2={E→T·,T→T·F,F→·F*,F→·a,F→·b}I3={T→F·,F

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

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

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