平时作业1 对于下列语言分别写出它们的正规表达式。 (1)英文字母组成的所有符号串，要求符号串中顺序包含五个元音。答：令Letter表示除这五个元音外的其它字母。(letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter)*(2)英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。 答： A*B*.Z*(3)=0,1上的含偶数个1的所有串。答：(0|10*1)*(4)=0,1上的含奇数个1的所有串。答：(0|10*1)*1(5)具有偶数个0和奇数个1的有0和1组成的符号串的全体。答：设S是符合要求的串，|S|=2k+1 (k0）。则 SS10|S21，|S1|=2k (k0），|S2|=2k (k0）。且S1是0,1上的串，含有奇数个0和奇数个1。S2是0,1上的串，含有偶数个0和偶数个1。考虑有一个自动机M1接受S1，那么自动机M1如下：和L(M1)等价的正规表达式，即S1为：(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*类似的考虑有一个自动机M2接受S2，那么自动机M2如下：和L(M2)等价的正规表达式，即S2为：(00|11)|(01|10)(00|11)*(01|10)*因此，S为：(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*0|(00|11)|(01|10)(00|11)*(01|10)*1(6)不包含子串011的由0和1组成的符号串的全体。答：1*|1*0(0|10)*(1|)(7)由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。答： 假设w的自动机如下：对应的正规表达式：(1(01*0)1|0)*2 给出接受下列在字母表0,1上的语言的DFA。(1)所有以00结束的符号串的集合。(2)所有具有3个0的符号串的集合。答：(1) DFAM=(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* DFAM=(0，1，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 | float ) id (, id )* ;请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。答：D T L ; T int | floatL L, id | id4 试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else (悬而未决的-else)文法的二义性：stmt if expr then stmt |matched-stmt matched-stmt if expr then matched-stmt else stmt |other 试说明此文法仍然是二义性的。 答：考虑句子if e then if e then other else if e then other else other 它具有如下所示的两种分析树 stmt expr then e if stmt if matched-stmt expr then matched-stmt e other if esle stmt matched-stmt expr then matched-stmt e other esle stmt matched-stmt other stmt matched-stmt if expr then matched-stmt e if esle stmt esle stmt matched-stmt expr then e stmt other expr then matched-stmt e other if matched-stmt other 则上面给出的if-then-else文法仍是二义性的。5 证明下面文法是SLR(1)文法，并构造其SLR分析表。EE+T|T TTF|F FF*|a|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 = EE, EE+T, ET, TTF, TF, FF*,Fa, Fb I1 = EE, EE+TI2 = ET, TTF, FF*, Fa, FbI3 = TF, FF* I4 = Fa I5 = Fb I6 = EE+T, TTF, TF, FF*, Fa, Fb I7 = TTF, FF* I8 = FF*I9 = EE+T, TTF, FF*, Fa, Fb求FOLLOW集：FOLLOW(E)=, FOLLOW(T)=, , a, bFOLLOW(F)=, , a, b, *构造的SLR分析表如下： 显然，此分析表无多重定义入口，所以此文法是SLR文法。6 为下面的文法构造LALR(1)分析表SE EE+T|TT(E)|a答：其拓广文法G： (0) S S(1) S E(2) E E+T(3) E T(4) T (E)(5) T a构造其LR(1)项目集规范族和goto函数(识别活前缀的DFA)如下: I0 = SS, $, SE, $, EE+T, $/+, ET, $/+,T(E), $/+, Ta, $/+ I1 = SS, $ I2 = SE, $, EE+T, $/+ I3 = ET, $/+I4 = T(E), $/+, EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+ I5 = Ta, $/+ I6 = EE+T, $/+, T(E), $/+, Ta, $/+I7 = T(E), $/+, EE+T, )/+ I8 = ET, )/+I9 = T(E), )/+, EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+I10 = Ta, )/+ I11 = EE+T, $/+ I12 = T(E), $/+I13 = EE+T, )/+, T(E), )/+, Ta, )/+ I14 = T(E), )/+, EE+T, )/+I15 = EE+T, )/+ I16 = T(E), )/+合并同心的LR(1)项目集，得到LALR的项目集和转移函数如下： I0 = SS, $, SE, $, EE+T, $/+, ET, $/+, T(E), $/+, Ta, $/+I1 = SS, $ I2 = SE, $, EE+T, $/+ I3,8 = ET, $/+/)I4,9 = T(E), $/+/), EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+I5,10 = Ta, $/+/) I6,13 = EE+T, $/+/), T(E), $/+/), Ta, $/+/)I7,14 = T(E), $/+/), EE+T, )/+ I11,15 = EE+T, $/+/) I12,16 = T(E) , $/+/)LALR分析表如下：7 （1）通过构造识别活前缀的DFA和构造分析表，来证明文法E E + id | id是SLR(1)文法。答：先给出接受该文法活前缀的DFA如下：E EE E + idE idI0E EE E+ idI1E idI2Eid+E E +idI3E E + idI4id再构造SLR分析表如下：状态 动作转移 id + $ E 0 s2 1 1 s3 acc 2 r2 r2 3 s4 4 r1 r1 表中没有多重定义的条目，因此该文法是SLR(1)的。（2）下面左右两个文法都和（1）的文法等价E E + M id | idE M E + id | idM eM e请指出其中有几个文法不是LR(1)文法，并给出它们不是LR(1)文法的理由。答：只有文法E M E + id | idM e不是LR(1)文法。因为对于句子id+id+id来说，分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多，而此时句子中+id的个数是未知的。8根据自上而下的语法分析方法，构造下面文法的LL（1）分析表。D TLT int | realL id RR , id R | e答：先计算FIRST和FOLLOWFIRST(D) = FIRST(T) = int,realFIRST(L) = id FIRST(R) = ,FOLLOW(D) = FOLLOW(L) = $FOLLOW(T) = idFOLLOW(R) = $LL(1)分析表如下：intrealid,$