资源描述：
《编译原理平时作业-答案.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
