编译原理期末复习题

1、3.2 是非判断，对下面的陈述，正确的在陈述后的括号内写T，否则写F。(1)有穷自动机接受的语言是正则语言。（）(2)若r1和r2是上的正规式，则r1|r2也是。（）(3)设M是一个NFA，并且L(M)x,y,z，则M的状态数至少为4个。（） (4)令a,b，则上所有以b为首的字构成的正规集的正规式为b*(a|b)*。（）(5)对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。（）(6)对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（）答案(1)  T   

2、; (2)  T   (3)  F(4)  F    (5)  T    (6) T3.3 描述下列各正规表达式所表示的语言。(1) 0(0|1)*0(2) (|0)1*)*(3) (0|1)*0(0|1)(0|1)(4) 0*10*10*10*(5) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*答案(1) 以0开头并且以0结尾的，由0和1组成的符号串

3、。(2) |0,1*(3) 由0和1组成的符号串，且从右边开始数第3位为0。(4) 含3个1的由0和1组成的符号串。  |0,1+，且中含有3个1 (5) |0,1*,中0和1为偶数3.4 对于下列语言分别写出它们的正规表达式。 (1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。(2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。 (3) =0,1上的含偶数个1的所有串。(4) =0,1上的含奇数个1的所有串。(5) 具有偶数个0和奇数个1的有0和1组成

4、的符号串的全体。(6) 不包含子串011的由0和1组成的符号串的全体。(7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。答案(1) 令Letter表示除这五个元音外的其它字母。   (letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter)*(2) A*B*.Z*(3) (0|10*1)*(4) (0|10*1)*1(5) 分析设S是符合要求的串，|S|=2k+1 (k0）。则 SS10|S21，|S1|=2k (

5、k>0），|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|

6、11)|(01|10)(00|11)*(01|10)*1(6)1*|1*0(0|10)*(1|)(7)接受w的自动机如下：对应的正规表达式：(1(01*0)1|0)*3.6 给出接受下列在字母表0,1上的语言的DFA。(1) 所有以00结束的符号串的集合。(2) 所有具有3个0的符号串的集合。答案(a) DFA M=(0，1，q0，q1，q2，q0，q2，)其中定义如下:（q0，0）=q1     （q0，1）=q0（q1，0）=q2     （q1，1）=q0（q2，0）=

7、q2     （q2，1）=q0(b)正则表达式: 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，1）=q2（q3，1）=q3     3.7构造等价于下列正规表达式的有限自动机。(1)10|（0|11）0*1

8、(2)(0|1)*|(11)*答案(1) DFA M=(0，1，q0，q1，q2，q3，q0，q3，)其中定义如下:(2) （q0，0）=q1     （q0，1）=q2(3) （q1，0）=q1     （q1，1）=q3(4) （q2，0）=q3     （q2，1）=q1(5) (6) (2) DFA M=(0，1，q0，q0，q0，)(7) 其中定义如下:(8) （q0，0）=q0     （q0，1）=q0

9、(9)3.8 给定右线性文法G：S->0S|1S|1A|0BA->1C|1B->0C|0C->0C|1C|0|1试求一个于G等价的左线性文法G'3.9 试对于下列正规表达式使用证明定理3。5的构造算法构造非确定的有限自动机。请给出每个自动机在处理输入符号串ababbab的过程中的动作序列。(1) (a|b)*(2) (a*|b*)*(3) (|a)b*)* 3.10 转换练习3.9中的每个 NFA 为 DFA 。并给出每个DFA在处理输入符号串ababbab的过程中的动作序列。3.11 试把练习3.10中得到的DFA的状态给以最小化。答案(1),(2),(3)的

10、DFA M相同，化简结果为：(4)3.12 我们可以证明两个正规表达式是等价的，如果它们的最小状态DFA是相同的（除了状态的名字以外）。利用这一结论，请说明下列正规表达式都是等价的。(1) (a|b)*(2) (a*|b*)*(3) (|a)b*)*答案根据3.11的结果知这几个正规表达式是等价的。3.13 对于下列正规表达式构造最小状态的DFA。(1) (a|b)*a(a|b)(2) (a)b)*a(a|b)(a|b)5对如下文法：GS ：S à a b S | a a B | a d B à b b B | b 分别给出句子abaabbb和ad的句柄 句子ad的语法分析

11、树为：S a d句子abaabbb的语法分析树为:SabSaaB b b B b所以句子abaabbb的句柄是b；句子ad的句柄是ad .二、（10分）说明如下文法是否是LL（1）文法，若不是，将其转换为LL（1）文法。最后给出该文法的LL（1）分析表。 GA：A à B e B à B b | a 文法中有左递归，不是LL(1)文法。 转换为 G ： Aà B e Bà a B Bàb B | Predict(Aà B e) = a Predict(Bà a B) = a Predict(Bàb B) = b P

12、redict(Bà ) = e LL(1)分析表: a b e A à B e B à a B B à b Bà 4. 给出识别正则表达式(（a|bc）*d)+的NFA 。 5已知文法GS：S S；GG G G(T) HH a (S)T T+S S找出句型：a(T+S)；H；(S)的短语、简单短语和句柄。 短语: a, T+S, a(T+S) , H , a(T+S);H , (S) 简单短语：a , T+S , H , (S) 句柄是 a . 6已知文法GS为：SAB | bC Ab | BaD | CAD | b DaS | c 对其每一个

13、非终级符求First集和Follow集。 First (S) = b , a , First (A) = b , First (B) = a , First (C) = b , a , c First (D) = a , c Follow (S) = # Follow (A) = a , c , # Follow (B) = # Follow (C) = # Follow (D) = # 二、（10分）设有文法GA: A ® iB*e B ® SB|e S ® eC|.i C ® eC|e判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否

14、则说明理由。 先计算各个产生式的Predict集： Predict (A-> iB*e)= i ; Predict (B-> SB) = , . Predict (B->e ) = * Predict (S->eC) = Predict (S->. i) = . Predict (C-> eC) = e Predict (C->e ) = 因为Predict集没有冲突，所以是LL(1)文法。 LL(1)分析表如下： i * e . A-> iB*e -> e B ->S B ->S B S ->e C ->. i C

15、 ->eC -> e1、证明下面文法是LL(1)的但不是SLR(1)文法SAaAb|BbBa A B解：对于产生式SAaAb|BbBa 来说FIRST(AaAb)FIRST(BbBa)=ab=而A，BVN仅有一条候选式。因此，这个文法是LL(1)的。 下面构造这个文法的识别活前缀的DFA。系 专业 班级 学号 姓名 密封线I0 = S'·S, S·AaAb, S·BbBa, A·, B· I1 = S'S·I2 = SA·aAbI3 = SB·bBaI4 = SAa·Ab, A

16、·I5 = SBb·Ba, B·I6 = SAaA·bI7 = SBbB·aI8 = SAaAb·I9 = SBbBa·由于FOLLOW(A)=FOLLOW(B)=a, b因此项目集I0中存在归约归约冲突。在I0状态下，当输入符号是a或是b时，不知用A还是B进行归约。故此文法不是SLR(1)的。但是，此文法是LR(1)的。 五、已知文法GS，其产生式如下： S(L)|a L L，S|S 从GS中消除左递归，并为之构造一个非递归预测分析器LL(1)分析表。请说明在句子(a，(a，a)上的分析器的动作。（20分）解：将所给文法消

17、除左递归得G'： S (L)|a L SL' L' ，SL' | 实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法G'有FIRST(s) = ( , a )FOLLOW(S) = , ', ' , $ FIRST(L) = ( , a )FOLLOW(L) = FIRST(L) = ', ' FOLLOW(L) = 按以上结果，构造预测分析表M如下： 文法G是LL(1)的，因为它的LL(1)分析表不含多重定义入口。 预测分析器对输入符号串(a, (a, a)做出的

18、分析动作如下： 例5.3的文法G3S 为：SaASdAbASA不难看出由定义5.3可得：SELECT(SaA)=aSELECT(Sd)=dSELECT(AbAS)=bSELECT(A)=a,d,# 所以 SELECT(SaA)SELECT(Sd)=ad= SELECT(AbAS)SELECT(A)=ba,d,# =由定义5.4知例5.3文法是LL(1)文法，所以可用确定的自顶向下分析。而对例5.5 文法G5S为：SaASSbAbAA则 SELECT(SaAS)=aSELECT(Sb)=bSELECT(AbA)=bSELECT(A)=a,b所以 SELECT(SaAS)SELECT(Sb)=ab

19、= SELECT(AbA)SELECT(A)=ba,b因此，例5.5文法不是LL(1)文法，因而也就不可能用确定的自顶向下表达式文法为：EE+T|TTT*F|FFi|(E)构造步骤：(1) 判断文法是否为LL(1)文法4.5 已知文法GS，其产生式如下： S(L)|a L L，S|S 从GS中消除左递归，并为之构造一个非递归预测分析器LL(1)分析表。请说明在句子(a，(a，a)上的分析器的动作。解：将所给文法消除左递归得G'：        S (L)|a    &

20、#160;   L SL'         L' ，SL' | 实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法G'有FIRST(s) = ( , a )FOLLOW(S) = ) , ', ' , $ FIRST(L) = ( , a )FOLLOW(L) = ) FIRST(L) = ', ' FOLLOW(L) = ) 按以上结果，构造预测分析表M如下：文法

21、G是LL(1)的，因为它的LL(1)分析表不含多重定义入口。预测分析器对输入符号串(a, (a, a)做出的分析动作如下：4.6 对于练习4.1的文法，构造它的LL(1)分析表。解：从练习4.1得到文法的产生式如下：        R R '|' T | T        T TF | F        F F* | C  

22、0;      C (R)| a | b 消除上面文法中的左递归R TR' R' '|' TR' | T FT' T' FT' | F CF' F *F' | C (R) | a | b计算FIRST()和FOLLOW(A)构造LL(1)分析表。4.9 对于文法GS，其产生式如下S(L)|a (4.22) LL,S|S (1)给出句子(a，(a，a)，(a，a)的一个最右推导，并指出右句型的句柄。 (2)按照(a)的最右推导，说明移进-归约分析器的工作步骤

23、。解：(1)S =>(L)=>(L, S)=>(L,(L)=>(L,(L,S)=>(L,(L,(L)=>(L,(L,(L,S)  =>(L,(L,(L,a)=>(L,(L,(S,a)=>(L,(L,(a,a)=>(L,(S,(a,a)  =>(L,(L),(a,a)=>(L,(L,S),(a,a)=>(L,(L,a),(a,a)=>(L,(S,a),(a,a)  =>(L,(a,a),(a,a)=>(S,(a,a),(a,a)=>(a

24、,(a,a),(a,a)右句型的句柄为每个右句型中用下划线标识出的部分。(2) 对于(a)的最右推导，移进规约分析器的工作步骤如下：4.11 下列文法是否为SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。(a)SSab|bR RS|a解：该文法的拓广文法G'为 (0) S' S(1) S Sab(2) S bR(3) R S(4) R a其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0 = S'·S, S·Sab, S·bRI1 = S'S·, SS·abI2 = Sb

25、83;R, R·S, R·a, S·Sab, S·bRI3 = SSa·b I4 = SbR·I5 = RS·, SS·ab I6 = Ra· I7 = SSab·求FOLLOW集：    FOLLOW(S')=    FOLLOW(R)=FOLLOW(S)=a,在I5中，出现移进归约冲突，且FOLLOW(R)a=a因此，此文法不是SLR(1)文法。b)SaSAB|BA AaA|B Bb 解：该文法的拓广文法

26、G'为 (0) S' S(1) S aSAB(2) S BA(3) A aA(4) A B(5) B b其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0 = S'·S, S·aSAB, S·BA, B·b I1 = S'S· I2 = Bb· I3 = Sa·SAB, S·aSAB, S·BA, B·b I4 = SB·A, A·aA, A·B, B·bI5 = SaS·AB, A·

27、aA, A·B, B·b I6 = SaSA·B, B·b I7 = Aa·A, A·aA, A·B, B·b I8 = AB· I9 = SBA· I10 = SaSAB·I11 = AaA·求FOLLOW集：    FOLLOW(S')=    FOLLOW(S)=a,b,    FOLLOW(A)=a,b,   &

28、#160;FOLLOW(B)=a,b,4.12 证明下面文法是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 = E'·E, E·E+T, E·T, T·TF, T·F, F·F*,      

29、0; F·a, F·b I1 = E'E·, EE·+TI2 = ET·, TT·F, F·F*, F·a, F·bI3 = TF·, FF·* I4 = Fa· I5 = Fb· I6 = EE+·T, T·TF, T·F, F·F*, F·a, F·b I7 = TTF·, FF·* I8 = FF*·I9 = EE+T·, TT·F,

30、 F·F*, F·a, F·b求FOLLOW集：    FOLLOW(E)=,     FOLLOW(T)=, , a, bFOLLOW(F)=, , a, b, *构造的SLR分析表如下： 显然，此分析表无多重定义入口，所以此文法是SLR文法。4.13 下面文法属于哪类LR文法？试构造其分析表。S(SR|a R,SR|)解：该文法的拓广文法G'为 (0) S' S(1) S (SR(2) S a(3) R ,SR(4) R )构造其LR(0)项目集规范族和goto函数

31、(识别活前缀的DFA)如下:I0 = S'·S, S·(SR, S·aI1 = S'S· I2 = S(·SR, S·(SR, S·a I3 = Sa· I4 = S(S·R, R·,SR, R·)I5 = S(SR· I6 = R)· I7 = R,·SR, S·(SR, S·a I8 = R,S·R, R·,SR, R·) I9 = R,SR·每个LR(0)项目集中没有冲突。因

32、此，此文法是LR(0)文法。其分析表如下：4.14 设文法G为 SA ABA|BaB|b (1)证明它是LR(1)文法。 (2)构造它的LR(1)分析表。 (3)给出输入符号串abab的分析过程。解：(1) 构造其拓广文法G'的产生式为 (0) S' S(1) S A(2) A BA(3) A (4) B aB(5) B b构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0 = S'·S, $, S·A, $, A·BA, $, A·, $,     

33、60;   B·aB, a/b/$, B·b, a/b/$ I1 = S'S·, $ I2 = SA·, $I3 = AB·A, $, A·BA, $, A·, $,        B·aB, a/b/$, B·b, a/b/$I4 = Bb·, a/b/$I5 = Ba·B, a/b/$, B·aB, a/b/$,    B·b

34、, a/b/$I6 = ABA·, $ I7 = BaB·, a/b/$该文法的LR(1)项目集规范族中没有冲突，所以该文法是LR(1)文法。(2)构造LR(1)分析表如下：以上分析表无多的定义入口，所以该文法为LR(1)文法。(3)对于输入串abab，其分析过程如下： 4.15 为下面的文法构造LALR(1)分析表SE EE+T|T T(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 = S·S

35、, $, S·E, $, E·E+T, $/+, E·T, $/+, T·(E), $/+, T·a, $/+ I1 = SS·, $ I2 = SE·, $, EE·+T, $/+ I3 = ET·, $/+I4 = T(·E), $/+, E·E+T, )/+, E·T, )/+,  T·(E), )/+, T·a, )/+ I5 = Ta·, $/+ I6 = EE+·T, $/+, T·(E), $

36、/+, T·a, $/+I7 = T(E·), $/+, EE·+T, )/+ I8 = ET·, )/+I9 = T(·E), )/+, E·E+T, )/+, E·T, )/+, T·(E), )/+, T·a, )/+I10 = Ta·, )/+ I11 = EE+T·, $/+ I12 = T(E)·, $/+I13 = EE+·T, )/+, T·(E), )/+, T·a, )/+ I14 = T(E·), )/+, EE&

37、#183;+T, )/+I15 = EE+T·, )/+ I16 = T(E)·, )/+合并同心的LR(1)项目集，得到LALR的项目集和转移函数如下： I0 = S·S, $, S·E, $, E·E+T, $/+, E·T, $/+, T··(E), $/+, T·a, $/+I1 = SS·, $ I2 = SE·, $, EE·+T, $/+ I3,8 = ET·, $/+/)I4,9 = T(·E), $/+/), E·E+T, )/

38、+, E·T, )/+,  T·(E), )/+, T·a, )/+I5,10 = Ta·, $/+/) I6,13 = EE+·T, $/+/), T·(E), $/+/), T·a, $/+/)I7,14 = T(E·), $/+/), EE·+T, )/+ I11,15 = EE+T·, $/+/) I12,16 = T(E) ·, $/+/)LALR分析表如下：br> 4.16 考虑文法GS，其产生式如下SAS | b ASA | a(1)构造文法GS的LR(0

39、)项目集规范族及相应的DFA。(2)如果把每一个LR(0)项目看成一个状态，并从每一个形如B·X的状态出发画一条标识为X的箭弧到状态BX·,而且从每一个形如B·A的状态出发画标记为的箭弧到所有形如A·的状态。这样就得到了一个NFA。说明这个NFA与(a)的DFA是等价的。(3)构造文法的SLR分析表。(4)对于输入串bab，给出SLR分析器所作出的动作。(5)构造文法的LR(1)分析表和LALR分析表。解：(1)其拓广文法G'： (0) S' S(1) S AS(2) S b(3) A SA(4) A a构造其LR(0)项目集规范族和go

40、to函数(识别活前缀的DFA)如下:I0 = S'·S, S·AS, S·b, A·SA, A·a I1 = S'S·, AS·A, A·SA, A·a, S·AS, S·b I2 = SA·S, S·AS, S·b, A·SA, A·a I3 = A a· I4 = Sb·I5 = ASA·, SA·S, S·AS, S·b, A·SA, A

41、3;a I6 = AS·A, A·SA, A·a, S·AS, S·bI7 = SAS·, AS·A, A·SA, A·a, S·AS, S·b(2) 文法GS的LR(0)项目如下： (0) S' ·S(1) S' S·(2) S ·AS(3) S A·S(4) S AS·(5) S ·b(6) S b·(7) A ·SA(8) A S·A(9) A SA·(10)A &

42、#183;a(11)A a·对上面的NFA通过求-cloasure确定化，得到与(1)相同的识别文法GS活前缀的DFA。因此，此NFA与(1)的DFA等价。(3) 求FOLLOW集：FOLLOW(S) = a, b,     FOLLOW(A) = a, b GS的SLR分析表：(4) 注：GS的SLR分析表中有移进归约冲突，因此它不是一个SLR文法。其实，GS是一个二义性文法，对于句子abab有下面两棵不同的分析树。因此，GS不是任何LR文法。(5) 文法GS的LR(1)项目集规范族及转移函数为：I0 = S'·S, $,

43、S·AS, $/a, S·b, $/a, A·SA, a/b, A·a, a/bI1 = S'S·, $, AS·A, a/b, A·SA,a/b, A·a, a/b, S·AS, a/b, S·b, a/bI2 = SA·S, $/a/b, S·AS, $/a/b, S·b, $/a/b, A·SA, a/b, A·a, a/b,I3 = Aa·, a/b I4 = Sb·, a/b/$I5 = AS·A,

44、 a/b, A·SA, a/b, A·a, a/b, S·AS, a/b, S·b, a/b6 = ASA·, a/b, SA·S, a/b, S·AS, a/b, S·b, a/b, A·SA, a/b, A·a, a/bI7 = SAS·, a/b/$, AS·A, a/b, A·SA, a/b, A·a, a/b, S·AS, a/b, S·b, a/bI8 = SA·S, a/b, S·AS, a/b, S·b, a/b, A·SA, a/b, a·a, a/bI9 = SAS·, a/b/$, AS·A, a/b, A·SA, a/b, A·a, a/b, S·AS, a/b, S·b, a/b, I10 = Sb·, a/b合并同心项目集(I2和I8，I7和I9，I4和I10)：I0 =