編譯原理(第二版)清華大學(xué)張桂琴呂映芝著答案.ppt

1、1,第3章 作業(yè) P3.8,G=(A,B,S,a,b,c,P,S) P: SAc|aB Aa b Bb c 寫出L(GS)的全部元素。,答： abc,2,2. 文法GN為： ND|ND D0|1|2|3|4|5|6|7|8|9 寫出L(GN)。,答： 非負(fù)整數(shù)的集合,3,3. 為只包含數(shù)字、加號和減號的表達(dá)式，寫文法。,答： LL+D| L-D | D D0|1|2|3|4|5|6|7|8|9,4,4. 已知文法GZ:,Z:=aZb Z:=a b 寫出L(GZ).,答： L(GZ)=anbn|n1,5,5. 寫文法，使其語言是偶正整數(shù)的集合。要求 （1）允許0打頭 （2）不允許0打頭,答： （

2、1） SXYZ | 2 | 4 | 6 | 8|0S X1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Z0 | 2 | 4 | 6 | 8 YYX | Y0 |,答： （2）SXYZ | 2 | 4 | 6 | 8 X1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Z0 | 2 | 4 | 6 | 8 YYX | Y0 |,5.1 允許0打頭的非負(fù)偶數(shù) SDS |0 | 2 | 4 | 6 | 8 D 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,5.2 不允許0打頭的非負(fù)偶數(shù) SD1 A | 2 | 4 | 6 | 8

3、D1 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 AD1A | 0A| 0 | 2 | 4 | 6 | 8,（1）與5.1的區(qū)別在于： 一個沒有0，一個有0。,6,6. 已知文法G： |+|- |*|/ ()|I 給出 i+i*i 的推導(dǎo)和語法樹。 E T |E+T | E-T T F |T*F | T/F F (E) | i,7,6. E T |E+T | E-T T F |T*F | T/F F (E) | i,EE+TT+TF+Ti+Ti+T*F i+F*F i+i*F i+i*i,i+i*i,8,6. E T |E+T | E-T T F |T*F | T/F

4、F (E) | i,i+(i+i),9,7.證明下面的文法是二義的 E i |(E) | EOE O + | - | * | /,i+i*i,對于串i+i*i,有以下兩棵不同的語法樹。（或給出兩個不同的最左推導(dǎo)）,10,8. 下面文法是二義的嗎？,G=(A,B,S,a,b,c,P,S) P: SAc|aB Aa b Bb c,答： 句子abc有兩棵不同的語法樹，所以是二義的。,11,9. 考慮下面的上下文無關(guān)文法，,SSS* |SS+|a （1）表明通過此文如何生成串a(chǎn)a+a*，并構(gòu)造語法樹。 （2）該文法生成的語言是什么？,含有+、*運(yùn)算的表達(dá)式的后綴式（逆波蘭表達(dá)式）。,aa+a* 代表

5、(a+a)*a,12,10. 文法：SS(S)S | （1）該文法生成的語言是什么？ （2）是二義的嗎？,答： L（G）=|為空串或可任意嵌套的配對的左右圓括號序列 ,句子()()有兩棵不同的語法樹,所以該文法是二義的.,13,14. 給出生成下述語言的上下文無關(guān)文法。 （1）anbnambm|n,m 0,或 SAA | A AaAb |,SAB AaAb | BaBb |,14,14. 給出生成下述語言的上下文無關(guān)文法。 （2）1n0m1m0n|n,m 0,(3) WcWr | W(0|a)* , Wr表示W(wǎng)的逆,S1S0| A| A0A1 |,(0|a)*代表的語言是0,a*,S0S0 |

6、 aSa |c,15,16. 給出生成下述語言的三型文法。 （1）an|n 0,SaS | aB BbB |b,SaS| ,（2）anbm|n,m1,（3）anbmck|n,m,k0,SaS | bB| cC| BbB |cC| CcC|,16,19. 刻畫語言的語法有幾種方式？,語法樹（是語法的直觀刻畫） 自然語言 擴(kuò)充的BNF范式（語法的形式刻畫）,17,補(bǔ)充練習(xí) 給出生成下述語言的文法。 （1）anbam|n ,m0,（2）anbm|nm 0,（3）anb2nck|n,k0,(4) WxWr | x,W0,a+ , Wr表示W(wǎng)的逆,(5) 不允許0打頭非負(fù)奇整數(shù)的集合。,() 不能被整除非負(fù)整數(shù)的集合。,18,構(gòu)造文法實例（見第3章課件-p72）,給出生成下述語言的文法。 1.語言L=aibj|ij, i,j0