网络学院编译原理平时作业

《网络学院编译原理平时作业》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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的所有串。答：(0

3、10*1)*1(5) 具有偶数个0和奇数个

4、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)*类似的考虑有一个自动机M2接受S2，那么自动机M2如下：和L(M2)等价的正规表达式，即S2为：((00

19、

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整除的符号串的全体。答：假设w的自动机如下：对应的正规表达式：(1(01*0)1

41、0)*1给出接受下列在字母表{0,1}上的语言的DFA。(1) 所有以00结束的符号

42、串的集合。(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}，{q0，q1，q2，q3}，q0，{q3}，δ)其中δ定义如下:δ（q0，0）=q1    δ（q0，1）=q0δ（q1，0）=q2    δ（q1，1）=q1δ（q2，0）=q3    δ（q2，

43、1）=q2δ（q3，1）=q3    3下面是用正规式表示的变量声明：(int

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

45、floatL®L,id

46、id4试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else(悬而未决的-else)文法的二义性：stmt→ifexprthenstmt

47、matched-stmtmatched-stmt→ifexprthenmatched-stmtelsestmt

48、other试说明此文法

49、仍然是二义性的。答：考虑句子ifethenifethenotherelseifethenotherelseother它具有如下所示的两种分析树stmtexprtheneifstmtifmatched-stmtexprthenmatched-stmteotherifeslestmtmatched-stmtexprthenmatched-stmteothereslestmtmatched-stmtotherstmtmatched-stmtifexprthenmatched-stmteifeslestmteslestmtmatched-stmtexp

50、rthenestmtotherexprthenmatched-stmteotherifmatched-stmtother则上面给出的if-then-else文法仍是二义性的。4证明下面文法是SLR(1)文法，并构造其SLR分析表。E→E+T

51、TT→TF

52、FF→F*

53、a

54、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*, 

55、       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