编译原理期末复习题

1、.3.2是非判断，对下面的陈述，正确的在陈述后的括号内写T，否则写 F。(1) 有穷自动机接受的语言是正则语言。 （）(2) 若 r 1 和 r 2 是上的正规式，则r 1|r 2 也是。（）(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') ，反之亦

2、然。（）答案(1) T(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 组成的符号串。(2) |0,1 * (3)由0和1组成的符号串，且从右边开始数第3 位为0。(4)含3个1的由 0 和 1 组成的符号串。 |0,1+，且 中含有 3 个 1 (5) |0,1 *

3、 , 中 0 和 1 为偶数 3.4对于下列语言分别写出它们的正规表达式。(1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。(2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。(3) =0,1 上的含偶数个 1 的所有串。(4) =0,1 上的含奇数个 1 的所有串。(5) 具有偶数个 0 和奇数个 1 的有 0 和 1 组成的符号串的全体。(6) 不包含子串 011 的由 0 和 1 组成的符号串的全体。(7)由 0 和 1 组成的符号串 , 把它看成二进制数，能被3 整除的符号串的全体。答案(1) 令 Letter 表示除这五个元音外的其它字母。(lette

4、r) * 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）。则 SS1 2120）。0|S 1，|S |=2k (k>0 ），|S |=2k (k且 S1 是 0,1 上的串，含有奇数个0 和奇数个 1。S 是 0,1 上的串，含有偶数个0 和偶数个 1。2考虑有一个自动机M 1 接受 S1，那么自动机M1如下：和 L(M 1)等价的正规表达式，即S1 为：(00

5、|11)|(01|10)(00|11) * (01|10) * (01|10)(00|11) *类似的考虑有一个自动机M 2 接受 S2，那么自动机M 2 如下：和 L(M 2)等价的正规表达式，即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)1* |1* 0(0|10)* (1| )(7) 接受 w 的自动机如下：对应的正规表达式：(1(01* 0)1|0)*3

6、.6给出接受下列在字母表0,1 上的语言的DFA。(1) 所有以 00 结束的符号串的集合。(2) 所有具有 3 个 0 的符号串的集合。.答案(a) DFA M=(0 ， 1 ， q 0， q1 ，q2 ， q0， q 2 ， ) 其中 定义如下 :（ q0， 0） =q1（ q0， 1） =q0（ q1， 0） =q2（ q1， 1） =q0（ q2， 0） =q2（ q2， 1） =q0(b) 正则表达式 : 1* 01* 01* 01*DFA M=(0 ，1 ， q 0， q1， q2， q3 ， q0， q 3 ， )其中 定义如下 :（ q0， 0） =q1（ q0， 1） =q0

7、（ q1， 0） =q2（ q1， 1） =q1（ q2， 0） =q3（ q2， 1） =q2（ q3， 1） =q33.7 构造等价于下列正规表达式的有限自动机。(1)10| （ 0|11 ）0* 1(2)(0|1)* |(11)*答案(1) DFA M=(0 ， 1 ， q 0 ， q1 ，q2， q3 ， q0， q 3 ， ) 其中 定义如下 :.(2)（ q0， 0） =q（ q ， 1） =q102(3)（ q1， 0） =q（ q ， 1） =q113(4)（ q2， 0） =q（ q ， 1） =q321(5)(6) (2) DFA M=(0 ， 1 ， q 0 ， q0，

8、q 0 ， )(7) 其中 定义如下 :(8)（ q0， 0） =q（ q， 1） =q000(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在处理输入符号串ababba

9、b 的过程中的动作序列。3.11试把练习 3.10 中得到的DFA的状态给以最小化。答案(1),(2),(3) 的 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 ： Sa b S |

10、a a B | a dBb b B | b分别给出句子abaabbb 和 ad 的句柄句子 ad 的语法分析树为：.Sad句子 abaabbb的语法分析树为:SabSaBabbBb所以句子 abaabbb 的句柄是b；句子 ad 的句柄是 ad .二、（10 分）说明如下文法是否是LL （1）文法，若不是，将其转换为LL （ 1）文法。最后给出该文法的LL （1）分析表。GA ：AB eBB b | a文法中有左递归，不是LL(1) 文法。转换为G：AB eBa BB b B |Predict(AB e) = a Predict(Ba B)= a Predict(B b B )= b Pred

11、ict(B ) = e LL(1) 分析表 :abeAB eBa BB b B.4. 给出识别正则表达式 (（a|bc） * d)+ 的 NFA 。5 已知文法 GS ：S S； GGGG(T) HH a (S)TT+SS找出句型： 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 为：S AB | bCAb | B aD | C AD | bD aS | c对其每一个非终级符求First 集和 Follow 集。First (S) = b

12、, 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:AiB*eBSB|SeC|.iCeC|判定该文法是否为LL(1) 文法？若是则给出它的LL(1) 分析表，否则说明理由。先计算各个产生式的Predict集：Predict (A-> iB*e)= i ;Predict (B-> SB) =

13、, .Predict (B->)= * .Predict (S->eC) = Predict (S->. i) = . Predict (C-> eC) = e Predict (C->)= 因为 Predict集没有冲突，所以是LL(1) 文法。LL(1)分析表如下：i*e.A-> iB*e->B->S B->S BS->e C->. iC->eC->1、证明下面文法是LL(1)的但不是 SLR(1) 文法SAaAb|BbBaAB解：对于产生式 SAaAb|BbBa来说FIRST(AaAb) FIRST(BbBa)

14、=a b= 而 A ， BV N 仅有一条候选式。因此，这个文法是 LL(1) 的。DFA 。下面构造这个文法的识别活前缀的I0 = S'· S, S · AaAb, S · BbBa, A · , B · I1 = S' S·I 2 = S A· aAbI 3 = S B· bBaI 4 = S Aa· Ab, A ·I 5 = S Bb· Ba, B ·I 6= S AaA· bI 7= S BbB· aI 8= S AaAb·

15、;I 9= S BbBa·由于 FOLLOW (A)= FOLLOW(B)=a, b因此项目集I0 中存在归约归约冲突。在I0 状态下，当输入符号是a 或是 b 时，不知用A 还是 B进行归约。故此文法不是SLR(1) 的。但是，此文法是LR(1) 的。五、 已知文法 GS ，其产生式如下：S (L)|aL L ， S|S.从 GS 中消除左递归，并为之构造一个非递归预测分析器LL(1) 分析表。请说明在句子(a，(a， a)上的分析器的动作。（20 分） 解：将所给文法消除左递归得G'：S (L)|aL SL'L' ，SL' | 实现预测分析器的不含

16、递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法 G'有FIRST(s) = ( , a )FOLLOW(S) = , ', ' , $ FIRST(L) = ( , a )FOLLOW(L) = FIRST(L ) = ', ' FOLLOW(L ) = 按以上结果，构造预测分析表M 如下：文法 G是 LL(1) 的，因为它的LL(1) 分析表不含多重定义入口。预测分析器对输入符号串(a, (a, a)做出的分析动作如下：例 5.3 的文法 G3S 为：S aAS dA bASA 不难看出由定义5.3 可得：.S

17、ELECT(S aA)=aSELECT(S d)=dSELECT(A bAS)=bSELECT(A )=a,d,# 所以 SELECT(S aA) SELECT(S d)=a d=SELECT(A bAS) SELECT(A )=b a,d,# =由定义 5.4 知例 5.3 文法是 LL(1) 文法，所以可用确定的自顶向下分析。而对 例 5.5 文法 G5S 为：S aASS bA bAA 则 SELECT(S aAS)=aSELECT(S b)=bSELECT(A bA)=bSELECT(A )=a,b所以 SELECT(S aAS) SELECT(S b)=a b=SELECT(A bA

18、) SELECT(A )=b a,b 因此，例 5.5 文法不是 LL(1) 文法，因而也就不可能用确定的自顶向下表达式文法为：EE+T|TTT*F|FF i|(E)构造步骤：(1) 判断文法是否为 LL(1) 文法4.5已知文法GS ，其产生式如下：S(L)|aL L ， S|S 从 GS 中消除左递归，并为之构造一个非递归预测分析器LL(1) 分析表。请说明在句子(a ， (a ， a) 上的分析器的动作。解：将所给文法消除左递归得G'：S (L)|aL SL'L' ， SL' |实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制

19、，下面构造预测分析表：根据文法 G'有FIRST(s) = ( , a )FOLLOW(S) = ) , ', ' , $ FIRST(L) = ( , a )FOLLOW(L) = ) FIRST(L )=','FOLLO W(L)=)按以上结果，构造预测分析表M 如下：文法 G是 LL(1) 的，因为它的LL(1) 分析表不含多重定义入口。预测分析器对输入符号串(a,(a, a)做出的分析动作如下：.4.6对于练习 4.1 的文法，构造它的LL(1) 分析表。解：从练习4.1 得到文法的产生式如下：R R '|' T | TT TF

20、| FF F* | CC (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) 的最右推导，说明移进 - 归约分析器的工作步骤。解： (1)S =>(L

21、)=>(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,(a,a),(a,a)右句型的句柄为每个右句型中用下划线标识出的部分。(2) 对于 (a) 的最右推

22、导，移进规约分析器的工作步骤如下：.4.11下列文法是否为SLR(1) 文法？若是，请构造相应的分析表。若不是，请说明理由。(a)S Sab|bRRS|a解：该文法的拓广文法G'为(0) S' S(1) S Sab(2) S bR(3) R S.(4) R a其 LR(0) 项目集规范族和 goto 函数 (识别活前缀的 DFA) 如下 :I 0= S' · S, S · Sab, S · bRI1 = S' S· , S S· abI= S b· R, R · S, R · a,

23、S · Sab, S I·=SbR Sa· bI= S bR·234I 5= R S· , S S· ab I6 = R a· I 7 = S Sab·求 FOLLOW集： FOLLOW (S')= FOLLOW (R)= FOLLOW(S)=a, 在 I5 中，出现移进归约冲突，且FOLLOW (R) a=a 因此，此文法不是SLR(1) 文法。b)S aSAB|BAA aA|BB b解：该文法的拓广文法G'为(0)S' S(1) S aSAB(2)S BA(3) A aA(4)A B(5

24、) B b其 LR(0) 项目集规范族和goto 函数 (识别活前缀的DFA) 如下 :I= S' · S, S · aSAB, S · BA, B ·I= S'b S· I2= B b·01I 3= S a· SAB, S · aSAB, S · BA, B ·I4= bS B· A, A · aA, A · B, B · bI 5= S aS· AB, A · aA, A · B, B ·I6=b

25、S aSA· B, B · bI 7= A a· A,A· aA, A· B, B· bI 8= AB·I9 = S BA· I10 =S aSAB·I 11 = A aA·求 FOLLOW集：FOLLOW(S')= FOLLOW(S)=a,b, FOLLOW(A)=a,b, FOLLOW(B)=a,b, .4.12证明下面文法是SLR(1) 文法，并构造其SLR分析表。EE+T|T T TF|FFF*|a|b解：该文法的拓广文法G'为(0)E' E(1) E E+T(2

26、)E T(3) T TF(4)T F(5)FF*(6)F a(7) F b其 LR(0) 项目集规范族和 goto 函数 (识别活前缀的 DFA) 如下 :I0= E'· E,E · E+T,E · T,T· TF, T · F·,F·a,F F*,· bI1= E'E·,E E·+TI=E T·,TT·F,F · F*,F· a, F · b2I 3 = T F· , F F· * I 4 = F a

27、3; I 5 = F b·I6= E E+· T,T· TF,T· F,F· F*, F· a,F· bI7 = TTF·,FF·* I8 =FF*·I 9=E E+T·,T T·F,F · F*,F· a, F · b求 FOLLOW集：FOLLOW(E)= , FOLLOW(T)= , , a, bFOLLOW(F)= , , a, b, *.构造的 SLR 分析表如下：显然，此分析表无多重定义入口，所以此文法是SLR 文法。4.13下面文法

28、属于哪类LR 文法？试构造其分析表。S(SR|aR,SR|)解：该文法的拓广文法G'为(0)S' S(1)S (SR(2) S a(3) R ,SR(4)R )构造其LR(0) 项目集规范族和 goto函数 (识别活前缀的DFA) 如下 :I 0 = S' · S,· (SR,S· aI 1= S' S· I2 = S ( · SR,· (SR,S· a I 3 = S a·I4 = S (S · R,· ,SR,R· )I 5= S (SR·

29、 I6 = R ) · I7 = R , · SR, S · (SR, S · aI=R ,S·R,R · ,SR,R ·I)= R ,SR ·89每个 LR(0) 项目集中没有冲突。因此，此文法是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 a

30、B(5) B b构造其LR(0) 项目集规范族和 goto 函数 (识别活前缀的 DFA) 如下 :I0=S'· S, $, S· A, $, A· BA, $, AB ··aB, a/b/$, B· b, a/b/$I 1= S' S· , $I2 = S A· , $I 3= A B· A, $, A· BA, $, A·B·,$, aB, a/b/$, B· b, a/b/$I 4= B b· , a/b/$I 5 = B a

31、3; B, a/b/$, B· aB, a/b/B$·,b, a/b/$I 6= A BA· , $ I 7 = B aB· , a/b/$该文法的LR(1) 项目集规范族中没有冲突，所以该文法是LR(1) 文法。(2) 构造 LR(1) 分析表如下：.以上分析表无多的定义入口，所以该文法为LR(1) 文法。(3) 对于输入串 abab ，其分析过程如下：4.15 为下面的文法构造LALR(1) 分析表 S EE E+T|TT (E)|a解：其拓广文法G'：(0)S' S(1) S E(2)E E+T(3) E T(4)T (E)(5)

32、T a构造其 LR(1) 项目集规范族和goto 函数 (识别活前缀的 DFA) 如下 :I0 = S· S, $, S· E, $, E· E+T, $/+,T E· (E),·$/+,T, T$/+,·a, $/+I1 = S S·, $ I2= SE·,$,E E· +T, $/+I 3 = E T· , $/+I4 = T ( · E), $/+, E· E+T, )/+, ET · T,(E),)/+, T· a, )/+I5 = T a

33、3; , $/+ I6= E E+· T, $/+, T· (E), $/+, T· a, $/+I7 = T (E · ), $/+, E E· +T, )/+I8= E T· , )/+I9 = T ( · E), )/+, E· E+T, )/+, E· T, )/+, T· (E), )/+, T· a, )/+I10 = T a· , )/+ I11= E E+T· , $/+ I 12 = T (E) · , $/+.I13= E E+

34、3; T, )/+, T· (E), )/+, T·I=a,T)/+ (E · ), )/+, E E· +T, )/+14I 15= E E+T· , )/+I16 = T (E) · , )/+合并同心的 LR(1) 项目集，得到 LALR 的项目集和转移函数如下：I0 = S· S, $, S· E, $, EE··E+T, $/+, T·· (E), $/+, T· a, $/+I1 = S S· , $I2 = SE·,$,E E

35、83; +T, $/+I 3,8 = E T· , $/+/)I 4,9 = T ( · E), $/+/), E· E+T, )/+, E T ·(E),T, )/+, T· a, )/+I 5,10= T a· , $/+/) I6,13 = E E+· T, $/+/), T· (E), $/+/), T· a, $/+/)I7,14= T (E · ), $/+/), E E· +T,I )/+= E E+T· , $/+/)11,15I 12,16 = T (E)

36、· , $/+/)LALR分析表如下： br>.4.16考虑文法 GS ，其产生式如下SAS | b A SA | a(1) 构造文法 GS 的 LR(0) 项目集规范族及相应的DFA。(2) 如果把每一个LR(0) 项目看成一个状态，并从每一个形如B· X的状态出发画一条标识为X 的箭弧到状态 BX·, 而且从每一个形如B· A 的状态出发画标记为 的箭弧到所有形如A· 的状态。这样就得到了一个NFA。说明这个NFA与 (a) 的 DFA是等价的。 (3) 构造文法的SLR分析表。(4) 对于输入串 bab，给出 SLR分析器所作出的动

37、作。(5) 构造文法的 LR(1) 分析表和 LALR分析表。解： (1) 其拓广文法G'：(0)S' S(1) S AS(2)S b(3) A SA(4)A a构造其LR(0) 项目集规范族和 goto 函数 (识别活前缀的 DFA) 如下 :I 0= S'· S, S · AS, S · b, A · SA, A · aI1 = S' S· , A S· A, A · SA, A · a, S · AS, S · b I2=S A· S,

38、S · AS, S · b, A · SA, A ·I3 =a A a· I4 = S b·I 5= A SA· , S A· S, S · AS, S · b, A · SA, A · a I 6= A S· A, A · SA, A · a, S · AS, S · bI 7= S AS· , A S· A, A · SA, A · a, S · AS, S ·

39、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)AS·A(9)A SA·(10)A ·a(11)A a ·对上面的 NFA 通过求 -cloasure 确定化，得到与 (1) 相同的识别文法 GS 活前缀的 DFA 。因此，此 NFA 与 (1)的 DFA 等价。(3) 求 FOLLOW集：FOLLOW(S) = a, b,

40、FOLLOW(A) = a, b GS 的 SLR 分析表：.(4)注： GS 的 SLR 分析表中有移进归约冲突，因此它不是一个SLR 文法。其实，GS 是一个二义性文法，对于句子abab 有下面两棵不同的分析树。因此，GS 不是任何LR 文法。(5) 文法 GS 的 LR(1) 项目集规范族及转移函数为：I 0= S'· S, $, S· AS, $/a, S· b, $/a, A· SA, a/b, A· a, a/bI 1= S'S·,$,A S· A, a/b, A· SA,a/b, A&

41、#183; a, a/b, S· AS, a/b, S· b, a/I 2= S A· S, $/a/b, S· AS, $/a/b, S· b, $/a/b, A· SA, a/b, A· a, a/b,.I3= A a· , a/bI4= S b·a/b/,$I5 = A S· A, a/b, A· SA, a/b, A· a, a/b, S· AS, a/b, S· b, a/b6= A SA· , a/b, S A· S, a/b, S· AS, a/b, S· b, a/b, A· SA, a/b, A· aI7= S AS· , a/b/$, A S· A, a/b, A· SA, a/b, A· a, a/b, S · AS, a/