编译原理 习题课.ppt

1、编译原理习题课,第二章,2.2 (1) L(GN) = (0|1|2|3|4|5|6|7|8|9)+ L(GN) = 可带前导0的正整数,2.3 (1) L1 = ambn|m,n=1 S - AB A - a|aA B - b|bB,2.3 (2) L2 = anbnci|n=1,i=0 S - Ac|A A - ab|aAb,2.3 (3) L3 = anbncmdm|m,n=1 S - AB A - aAb|ab B - cBd|cd,2.3 (4) L4 = 0n|n=0 A - A0|,2.3 (5) L5 = a2n+1|n=0 S - aA A - aaA| 或 A - aAa|

2、a,2.3 (6) L6 = 1n0m1m0m|n,m=0 S - 1S0|oA1| A - 0A1|,2.4 写一个文法，不以0开头的奇数 N - 1|3|5|7|9|BN B - 1|2|3|4|5|6|7|8|9|B0,2.6 短语：E+T*F,T*F 直接短语：T*F 句柄：T*F,E E+T T*F,2.7G1：S - AB A - aA | B - bc | bBc L(G1S)=aibncn|i=0,n=1,G2：S - aA|a A - aS L(G2S)=a2n+1|n=0,2.9 短语：T*P(T*F), P(T*F), (T*F), T*F, P 直接短语：T*F, P

3、句柄：P,T T*F F P P(T) T*F,2.11 短语: (SaA)(b), (SaA)(b), (SaA), (b) 直接短语: (SaA), (b) 句柄: (SaA),S (AS) ( A S ) ( S a A ) ( b ),第三章,3.1 (3) (0|1)*|(11)*,3.1 (4) (0|11*0)*,初始划分：X,1; 2,3,3.2 (a),初始划分：A,B; C,3.2 (b),初始划分：0,1; 2,3,4,5,0,1a=1;0,1b=2,4 2,3,4,5a=1,3,0,5;2,3,4,5b=3,2,5,4,再次划分：0,1; 2,4; 3,5,0,1a=1

4、;0,1b=2,4 2,4a=1,0;2,4b=3,5 3,5a=3,5;3,5b=2,4,3.3 构造一个DFA，它接受=0，1上所有满足如下条件的字符串，每个1都有0直接跟在后边。,0*(0|10)*0*,初始划分：1,2,4; 3,3.9 试证明正规式（a|b）*与正规式（a*|b*）*是等价的。,3.11 设字母表=a,b,给出上的正规式R=b*ab(b|ab)*,3.11,初始划分：1,2,3,5; 4,6,再次划分：1,3; 2,5; 4,6,3.11,（2）对应的右线性文法G=（X,W,Y,a,b,P,X） P:XaW|bX WbY|b YaW|bY|b,第四章,4.1,因此该文

5、法是LL(1)文法,4.2,SELECT(E-+TE) SELECT(E-) = FIRST(+TE) FOLLOW(E)= SELECT(T-*FT) SELECT(T-) = FIRST(*FT) FOLLOW(T)= SELECT(F-(E) SELECT(F-id) = FIRST(E) FIRST(id)= ,因此该文法是LL(1)文法,4.3,4.3,SELECT(A-iBA) SELECT(A-) = FIRST(iBA) FOLLOW(A)= SELECT(B-+CB) SELECT(B-) = FIRST(+CB) FOLLOW(B)= SELECT(C-)A*) SELEC

6、T(C-() = FIRST()A*) FIRST()= ,4.5 设有表格结构文法GS： S- a|(T) T- T,S|S,4.5 设有表格结构文法GS： S- a|(T) T- T,S|S,4.5 设有表格结构文法GS： S- a|(T) T- T,S|S,4.8 0. S - S S - AS S - b A - SA A - a,(2). I1,I5,I6存在“移进-归约”冲突。不是LR(0)文法。 (3). 对于abab有两棵不同的语法树，任何二义性文法不是SLR(1)文法， 也不是LALR(1)或LR(1)文法。,S AS aA S SA b ba,S A S S A b A S b a b,4.9 0. S - S S - rD D - D,i D - i,(2). I3中有“移进-归约”冲突，不是LR(0)文法,(3). FOLLOW(S) , = $ , = ,可以用SLR(1)文法解决,4.9 0. S - S S - rD D - D,i D - i,4.13,不含有冲突，因此