(完整word版)编译原理课后答案.doc

第二章 高级语言及其语法描述 4．令 +、 * 和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算 1+1*2 ↑2*1 ↑ 2 的值： 1） 优先顺序（从高至低）为 +， * 和↑，同级优先采用左结合。 2） 优先顺序为↑， +， * ，同级优先采用右结合。 解：（ 1） 1+1*2 ↑ 2*1 ↑ 2=2*2 ↑ 1*1 ↑ 2=4↑ 1↑ 2=4↑ 2=16 2） 1+1*2 ↑ 2*1 ↑ 2=1+1*2*1=2*2*1=2*2=4 6．令文法 G6为 N →D|ND D → 0|1|2|3|4|5|6|7|8|9 1） G6 的语言 L（ G6）是什么？ 2） 给出句子 0127、 34 和 568 的最左推导和最右推导。 解：（ 1） L（ G6） =｛a|a ∈ ∑+, ∑ =﹛ 0,1,2,3,4,5,6,7,8,9 ｝｝ 2） N ＝＞ ND＝＞ NDD＝＞ NDDD＝＞ DDDD＝＞ 0DDD＝＞ 01DD＝＞ 012D ＝＞ 0127 N＝＞ ND＝＞ N7 ＝＞ ND7＝＞ N27 ＝＞ ND27＝＞ N127 ＝＞ D127 ＝＞ 0127 N＝＞ ND＝＞ DD＝＞ 3D ＝＞ 34 N＝＞ ND＝＞ N4 ＝＞ D4 ＝＞ 34 N＝＞ ND＝＞ NDD＝＞ DDD＝＞ 5DD＝＞ 56D ＝＞ 568 N＝＞ ND＝＞ N8 ＝＞ ND8＝＞ N68 ＝＞ D68 ＝＞ 568 7．写一个文法，使其语言是奇数集，且每个奇数不以 0 开头。 解： A→SN, S →+|-| ∑, N →D|MD D→ 1|3|5|7|9, M → MB|1|2|3|4|5|6|7|8|9 B → 0|1|2|3|4|5|6|7|8|9 8. 文法： E T|E T|E T F|T*F|T/F F ( E)|i 最左推导 : E E T T T F T i T i T * F i F * F i i * F i i * i E T T * F F * F i * F i *( E ) i *( E T ) i *( T T ) i *( F T ) i *( i T ) i *( i F ) i *( i i ) 最右推导 : E E T E T*F E T * i E F * i E i * i T i * i F i * i i i * i E T F * T F * F F*( E) F*(E T) F*(E F) F *( E i ) F *( T i ) F *( F i ) F *( i i ) i *( i i ) 语法树： /******************************** 1 E E E E + T E + T E - T E + T F T T * F E - T F T F i F F i T F i F i i i F i i i i+i+i i-i-i i+i*i *****************/ 9．证明下面的文法是二义的： S→ iSeS|iS|I 解：因为 iiiiei 有两种最左推导，所以此文法是二义的。 10．把下面文法改写为无二义的： S→ SS|(S)|() 解： S→ ST|T, T → (S)|() 11．给出下面语言的相应文法 L1= ｛ anbnci |n ≥1,i ≥ 0｝ L2= ｛ ai bncn|n ≥1,i ≥ 0｝ L3= ｛ anbnambm|n,m ≥ 0｝ L4= ｛ 1n0m1m0n|n,m ≥ 0｝ 解：（ 1） S→ AB|A → aAb|ab → c|cB S → AB|B A → a|aA B→ bBc|bc S → AB|A|B| ∑ A→ aAb|ab B→ aBb|ab S→ 1S0|0A1 A→ 0A1|01 2 第三章 词法分析 7. 构造下列正规式的相应的 DFA 1(0|1)*101 1(1010*|1(010)*1)*0 0*10*10*10* (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 解答： （1） 1(0|1)*101 I I 0 I 1 {X} Ф {A,B,C} {A,B,C} { B,C} { B,C,D} {B,C} { B,C} { B,C,D} {B,C,D} { B,C,E} { B,C,D} {B,C,E} { B,C} {B,C,D,y} {B,C,D,y} {B,C,E} { B,C,D} S 0 1 A B B C D C C D D E D E C F F E D (2) 1(1010*|1(010)*1)*