各章练习题(编译原理)分析.doc

第三章复习重点：1.文法与语言的对应关系 语言L(G)=L(G’) 文法G 文法G’ {bn | n0} B→bB | b B→Bb | b {bn | n≥0} P→bP |ε P→Pb |ε {abn | n0} S→DB D→a B→bB | b S→aB B→Bb | b {bna | n≥0} T→PD D→a P→bP |ε T→Pa P→Pb |ε {(ab)n | n0} U→EU | E E→ab U→Uab | ab {ambn|m0,n0} V→AB A→aA | a B→bB | b V→aV | aB B→bB | b {ambn|m≥0,n0} W→AB A→aA |ε B→bB | b W→aW | B B→bB | b {anbn | n0} X→aXb | ab {(akcd) nbn | k,n0} X→DXH | DH D→Acd A→aA |a H→b {a2n+1bn| n=0} Y→aaYb |a Y→KYH | a K→aa H→b 思路要点：注意结构拆分 技巧：如何将表示语言的通用字符串形式作适当的“切割”？ 例：已知语言：L1 = {axb2xcy | x, y = 0}，给出此语言的文法，并证明此语言是上下文无关语言。 提示：该题实际上要求为相应语言设计上下文无关文法。 一个文法设计好后，严格来说应当证明此文法是否对应于该语言。 解：G[S]： S → AB A → ( | aAbb B → ( | cB 推导过程： S ( AB +( axAb2xB /*使用A → aAbb x次*/ ( axb2xB /*使用A → ( 一次*/ ( axb2xcxB /*使用B → cB x次*/ ( axb2xcx /*使用B →( 一次*/ 举一反三：已知语言L2 = {axb2ycy | x, y = 0}，给出此语言的文法，并证明此语言是上下文无关语言。 解：G[S]： S → AB A → ( | aA B → ( | bBcc 练习：14：写出下列语言对应的文法 (1).{anbnambm|n,m≥0} 2. {1n0m0m0n|n,m≥0} 3. {1n0m0m0n|n≥0,m0} 4. { anbmck|n,m,k≥0} G1: S—AA G2: S—AB A—aAb|ε A—aAb|ε B—aBb|ε G: S—1S0 S—A A—0A1 A—ε G: S(1S0|A S(1S0|0A1 A(0A1|01 A(0A1|ε 2. 给出文法，证明文法符号串是否为文法的句型，若是句型，找出这个句型的所有短语、直接短语、句柄。 1. 令文法G［E］为： Z→bMb M→a|(L L→Ma） ① 符号串b(Ma)b是否为该文法的一个句型，并证明。② 若此符号串是句型，指出这个句型的所有短语、直接短语、句柄短语: Ma)， (Ma)， b(Ma)b 直接短语: Ma) 句柄: Ma) ]： T→T*F | F ；F→F↑P | P ； P→(T) | i （1）用最右推导法证明β：T*P↑(T*F) 是G[T]的一个句型； （2）画出β的语法树； （3）写出β的全部短语、直接短语和句柄。 (1) T=T*F=T*F↑P=T*F↑(T)= T*F↑(T*F) =T*P↑(T*F) 证毕。 (2) 如图 （3）短语：T*P↑(T*F) ；P↑(T*F) ；(T*F) ；T*F ；P 直接短语：T*F ；P 句柄： P 3. 证明一个文法是二义性文法。 证明下述文法G［S］是二义的。 （5分） S-iSeS|iS|i 解： S S i S e S i S i S i S e S 可见，句型iises有两种不同的语法树，所以G[S]是二义的。证明下述文法G： S(aSbS|S|d 是二义性文法。 一个文法，如果存在某个句子有不只一棵分析树与之对应，那么称这个文法是二义性文法。 (