编译原理-习题

第2章习题及解答：试构造下述语言L的文法：

L={ambn|m≥0,n≥1};【解1】G1(S):S->ABA->Aa|

B->Bb|bS->ABA->aA|

B->bB|b或G2(S):【解】分析：※产生式形式：1.此语言仅有一种句型：ambn

；2.

ambn

中包含有两个短语：am和

bn

；于是：设：S(句子)，A（短语1），B（短语2）第2章习题及解答：试求下述文法G(Z)所定义的语言：

G(Z):Z->b|bB,B->bZ【解】⒈推导运算法：L(G)={x|Zx,x∈VT*

}=>

+文法所定义的语言Z=>bB=>bbZ=>bbbZ=>bB=>bbZ=>bbbB=>bbbbZ=>bbbbbZ=>b∴∵Z=>b2n-1,

n≥1⒉正规方程式法：∵Z=b|bB,B=bZ即Z=b|bbZ※递推求解Z=b|bbZ

可得：Z=b2n-1n≥1∴L(G)={b2n-1|n≥1}…第2章习题及解答：【解】根据文法G[S]:S->(AS)|(b);A->(SaA)|(a)⑵从语法述上，看(A((SaA)(b)))的短语、直接短语和句柄：S(AS)(AS)(SaA)(b)短语：①(A((SaA)(b)))②((SaA)(b))③(SaA)④(b)

直接短语：③(SaA)④(b)句柄：③(SaA)⑴因为(a)不是句子，所以没有短语问题。已知文法G[S]:S->(AS)|(b);A->(SaA)|(a)试找出符号串(a)和(A((SaA)(b)))的短语、直接短语(即简单短语)和句柄。SSAS第2章习题及解答：证明下面文法是二义性文法S->iSeS|iS|i【证】因为句型iiSeS

有下述两棵不同的语法树：SiSeSiSSiSiSeS和所以所属文法是二义性文法！【习题

】G(S):S->aAcBe;A->Ab|b;B->d⑴证明

=aAbcde

是一个句型；⑵画出句型

的语法树；⑶指出句型

的短语、简单短语和句柄。第2章习题及解答：已知文法G(S):E->E+T|E-T|T【解】∵消除直接左递归公式：整理:E->E+T|E–T|T∴有G`(S):E->T{T}A->A|≡A->{

}A->A`,A`->A`|ε或G`(S):E->TE`E`->TE`|ε令：

=+|-E->ET|T第2章习题及解答：已知文法

G(S):S->aSab|bAB;A->bB|a;B->aA|bC->abB|baA;D->Cbc|abc;【解】删除无用产生式：自定己；不终结；不可达。⑴找自定己产生式（如A->A）

无自定己者！⑵构造可终结非终结符集

Vvt={},⑶构造可达非终结符集

VAR={},G`(S):S->aSab|bAB;A->bB|a;B->aA|b∴删除不可达非终结符：C,D后得：无不终结者！A,B,C,D,SS,A,B第3章习题及解答：试构造确定自动机DFA:⑴e=1(0|1)*101①+011-②1③④⑤01⑵e=(a|b)*(aa|bb)(a|b)*①+ab-②③④aabbabA{1}ba+DFA变换表DFA状态图ABCDE+--aaabbbbabaE{1,3,4}D{1,2,4}E{1,3,4}D{1,2,4}E{1,3,4}B{1,2}C{1,3}D{1,2,4}C{1,3}B{1,2}D{1,2,4}E{1,3,4}C{1,3}B{1,2}--确定化第3章习题及解答：试构造一个DFA,它接收∑={0,1}上所有满足如下条件的字符串：每一个1都有0直接跟在右边。【解】①+01-②0③1-0①+-②010或给定正规语言，构造有限自动机：

A={an,ban|n≥0}【解】①+-②baa-①+-②baa-第3章习题及解答：把下述NFA转换为DFA:①②③abab+-FA1:①②③abab+-FA2:ab+-DFA2:ABA{1}ba+B{2,3}B{2,3}B{2,3}-aab+-DFA1:ABCbC{2,3}B{2}C{2,3}B{2}C{2,3}B{2}-A{1}ba+第3章习题及解答消除

NFA的

边：②③①+a-

ab③④-①+②ba

b

aFA3:FA4:【算法】⑶逆序删

边,并补充新边。⑴

闭路合而为一；⑵标记隐含初态和终态；②①+-abaDFA1③④-①+②bab

aab③-①+②aabbaDFA2无用状态第3章习题及解答：已知符号串集合，构造正规式、自动机和正规文法：A={,an,ban|n≥1}【解】

正规式:e=|a+|ba+或e=a*|ba+

自动机DFA:

aa+-12b-3a

正规文法:

SABS->aA|bB|

A->aA|

B->aA已知自动机DFA:②ab③⑤bcc①④bb-+-⑴扩展DFA(加入结束标记#),构造压缩变换表；⑵根据实现算法，写出识别abbc#的过程。⑵输入串abbc#识别过程：第3章习题及解答：【解】⑴扩展DFA:压缩变换表④⑤③②①

no④b②a

no④b索引表

no⑤c③b

no⑤c③b

nook#1备注变换剩余chstate②ab③⑤bcc①④bb+--#-#2bbc#a接受ok#5#c3c#b3bc#b5332#b构造下述文法的递归子程序：

G(S):S->aASb|Bd;A->cS|;B->bB|d

【解】入口出口aerr2NEXT(w)Aerr1NEXT(w)S子程序nnnyySbBdNEXT(w)y第5章习题及解答入口cNEXT(w)出口遇时nySA子程序bNEXT(w)出口nyBdNEXT(w)err3yn入口B子程序已知文法：S->aASb①|Bd②A->cS③|④B->bB⑤|d⑥（1）求选择集合；证明是LL(1)文法；G(S):⑴select(①)={}select(②)={}⑶select(⑤)={}select(⑥)={}⑵select(③)={}select(④)={}【解】（1）求选择集合（2）LL(1)分析表:∵三对选择集合两两不相交!∴G(S)是LL(1)文法!dBAS＃cbaab,dc=follow(A)a,b,dbd⑥④②⑤③④④②①（2）构造LL(1)分析表。∵三对选择集合中，两两不相交！∴G`(S)是LL(1)文法！

把下述文法化为LL(1)文法！S->A;A->B|AiB;B->C|B+C;C->)A*|(※文法变换，消除左递归：

A->B|AiB=>A->B{iB}则A->BA`;A`->iBA`|

B->C|B+C=>B->C{+C}则B->CB`;B`->+CB`|

※整理并附加产生是序号后得：G`(S):S->A①；A->BA`②;A`->iBA`③|

④B->CB`⑤;B`->+CB`⑥|

⑦;C->)A*⑧|(⑨select(③)={i};select(④)={*,#};select(⑥)={+};select(⑦)={i,*,#};select(⑧)={)};select(⑨)={(};⑴⑵⑶G(S):Z->S1(0)S->a2A3(1)|b4B5(2)A->06A7(3)|18(4)B->09B10(5)|111(6)

考虑文法：G(S)S->aA|bB;A->0A|1;B->0B|1⑴构造活前缀的DFA(即句柄识别器)【解】※扩展文法，编码：①②③⑥⑦⑧⑨⑩0+SaA0OKr(1)r(3)r(4)r(2)bA1B0④0Br(5)r(6)111011※活前缀的DFA(即句柄识别器):∵句柄识别器(DFA)中无冲突状态！∴G(S)是LR(0)文法!⑵是LR(0)文法吗？⑤B1011109

9r(5)r(5)r(5)r(6)r(5)10

S1

SA7

A3

AOK1r(2)r(2)r(2)r(2)r(2)5b4a20B5111094r(4)r(4)r(4)r(4)r(4)8r(6)r(3)18r(1)18

1r(6)r(3)r(1)

#066r(3)r(3)r(3)7r(6)r(6)r(6)11r(1)r(1)r(1)3

2

B

0

b

a06⑶G(S)的LR(0)分析表：第5章习题及解答

设有文法G(S):S->rD;D->D,i|i【解】⑴构造活前缀的DFA(即句柄识别器)※扩展文法，编码：Z->S1(0)S->r2D3(1)D->D3,4i5(2)|i6(3)0+SrDOKr(1)r(2)r(3)，ii②③④⑤⑥①#∵在状态③处出现(移进、归约)冲突！∴G(S)不是LR(0)文法！

⑵∵follow(S)={#},可以解决冲突：即若当前单词为“，”,则移进,4当前单词为“#”,则归约

r(1)∴G(S)是SLR(1)文法！！第5章习题及解答：r,i#SD0r2S11ok2i6D33,4r(1)4i55r(2)r(2)r(2)r(2)6r(3)r(3)r(3)r(3)⑶文法G(S)的SLR(1)分析表：第5章习题解答：G(E):E->E+T|TT->(E)|iE`->E1(0)E->E2+3T4(1)|T5(2)T->(6E7)8(3)|i9(4)G`(E`)1.构造句柄识别器：-Ti0E①-OKE②+③T④-r(1)T⑤-r(2)(⑥E⑦)⑧-r(3)i⑨r(4)E((i【解】+第7章习题及解答：试

写出逆波兰式：⑴a*(-b+c)=>abc+*或a0b-c+*-⑵a+b*(c+d/e)=>abcde/+*+⑶-a+b*(-c+d)=>abcd+*+或0a-b0c-d+*+--⑷

A(CD)=>ACD⑸(AB)(CD)=>ABCD【快速写出要点】变元顺序不变，算符先算在前！※验证：pos((AB)(CD))=pos((AB))pos((CD))

=pos(AB)pos(CD)

=AB

pos(C)pos(D)

=ABCD第7章习题及解答2：写出下述语句的四元式序列：

(1)if(x>0)x=(a-b/2)*c；

(2)while(a∨b)b=2*a/5;⑴⑴(>x0t1)⑵(ift1__)⑶(/b2t2)⑷(-at2t3)⑸(*t3ct4)⑹(=t4_x)⑺(ie___)⑴(wh___)⑵(∨abt1)⑶(dot1__)⑷(*2at3)⑸(/t35t4)⑹(=t4_b)⑺(we___)⑵【解】第7章习题及解答3：G`(E)：E->T|E+T{+}|E-T{-}T->F|T*F{*}|T/F{/}F->i{i}|(E)

※试用分别用最左推导法和最左归约法分析(翻译)符号串a*(b-c+d)的逆波兰式生成过程。已知算术表达式的逆波兰翻译文法：【解】最左推导：Z=>T=>T*F{*}=>F*F{*}=>a{a}*F{*}=>a{a}*(E){*}=>a{a}*(E+T{+}){*}=>a{a}*(E-T{-}+T{+}){*}=>+a{a}*(b{b}-c{c}{-}+d{d}{+}){*}导出序列※分离导出序列：删除动作符号：a*(b-c+d)……源表达式删除文法符号：abc-d+*……逆波兰式⑴t2=B/C⑶B=A⑴t1=2*3

⑵t2=B/C

⑶t3=t1+t2⑷A=t3

⑸t4=2*3

⑹t5=B/C⑺t6=t4+t5

⑻B=t6

⑼t7=2*3⑽t8=B/C

⑾t9=t7+t8(12)C=t9第8章习题及解答求下述语句片断的DAG优化过程：

A=2*3+B/C;B=2*3+B/C;C=2*3+B/C;ⅰ.根据四元式序列构造优化的DAG:16|t12B3C4/t27+,t7|t5,t4|A|C/t86ⅱ.根据优化的DAG重组四元式:+t3A|t35,t6⑵A=6+t2⑷t8=A/C,Bt9C|t9⑸

C=6+t8⑴t1