編譯原理第三章答案

1、第章文法和語(yǔ)言第1題文法G=(A,B,S,a,b,c,P,S)其中P為：SAclaBAabBbc寫出L(GS)的全部元素。答案：L(GS)=abc第2題文法GN為：NfDINDDf0I1I2I3I4I5I6I7I8I9GN的語(yǔ)言是什么？答案：GN的語(yǔ)言是V+。V=0,1,2,3,4,5,6,7,8,9n=nd=ndd.=NDDDD.D=DD或者：允許0開頭的非負(fù)整數(shù)？第3題為只包含數(shù)字、加號(hào)和減號(hào)的表達(dá)式，例如9-2+5,3-1,7等構(gòu)造一個(gè)文法。答案：GS：S-S+DIS-DIDD-0I1I2I3I4I5I6I7I8I9第4題已知文法GZ：ZfaZbIab寫出L(GZ)的全部元素。答案：Z=

2、aZb=aaZbb=aaa.Z.bbb=aaa.ab.bbbL(GZ)=anbnIn=1第5題寫一文法，使其語(yǔ)言是偶正整數(shù)的集合。要求：(1)允許0打頭；(2)不允許0打頭。答案：(1)允許0開頭的偶正整數(shù)集合的文法NIDNIDNDI1I3I5I7I9D0I2I4I6I8(2)不允許0開頭的偶正整數(shù)集合的文法NIDIGNDI1I3I5I7I9D2I4I6I8NI0GDI0第6題已知文法G：表達(dá)式:二v項(xiàng)I表達(dá)式+v項(xiàng)項(xiàng)因子IV項(xiàng)*V因子因子:二(表達(dá)式,)Ii試給出下述表達(dá)式的推導(dǎo)及語(yǔ)法樹。(5)i+(i+i)(6)i+i*i答案，(5)表達(dá)式=X達(dá)式3+=x表達(dá)式+閑子二X發(fā)達(dá)式+y友達(dá)式)

3、二x表達(dá)式+y表達(dá)式+項(xiàng)=x表達(dá)式+表達(dá)式A+M因子)=xfe達(dá)式+達(dá)式十口=”達(dá)式，1(4I)達(dá)式+y因子+i)=x達(dá)式+(i+i)二：二頁(yè)XIi=x因子+(i+i)Bi達(dá)式)無(wú)因子、L=j+(iIiBi達(dá)式)無(wú)因子、L第7題證明下述文法G（表達(dá)式是二義的，表達(dá)式）：=叫（表達(dá)式）|表達(dá)式）運(yùn)算符（表達(dá)式運(yùn)箕符）：=-1-叩答案：司為句子肝肝罌構(gòu)浩:兩個(gè)不同峋最右推導(dǎo):最右推導(dǎo)1（表達(dá)苴n（表達(dá)式；（運(yùn)算符）表達(dá)式=表達(dá)式運(yùn)算符）a=求送式）*a=表達(dá)式運(yùn)算符）表達(dá)式本虱=（表達(dá)式）運(yùn)算符a*an麥達(dá)式）十目*a=?-a+a*a最右推導(dǎo)2表達(dá)式=衣達(dá)式）（運(yùn)算符）表達(dá)式麥達(dá)式（運(yùn)算符）表達(dá)式

4、（運(yùn)算符（表達(dá)式）=表,達(dá)式）運(yùn)算符）（衣達(dá)式）（運(yùn)算符）a=表達(dá)式）運(yùn)算符）表達(dá)式）J=（表達(dá)式運(yùn)算符表達(dá)式）+a*a第8題文法GS為：S-AclaBAabB-bc該文法是否為二義的？為什么？答案：對(duì)于串a(chǎn)bc（1）S=Ac=abc（2）S=aB=abc即存在兩不同的最右推導(dǎo)。所以，該文法是二義的。或者：對(duì)輸入字符串a(chǎn)bc,能構(gòu)造兩棵不同的語(yǔ)法樹，所以它是二義的。第第10題文法S-S(S)S|e(1)生成的語(yǔ)言是什么？(2)該文法是二義的嗎？說(shuō)明理由。答案：(1)嵌套的括號(hào)(2)是二義的，因?yàn)閷?duì)于()()可以構(gòu)造兩棵不同的語(yǔ)法樹。第11題令文法GE為：e-t|e+t|e-tt-f|t*f|t

5、/fF-(E)|i證明E+T*F是它的一個(gè)句型，指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)和句柄。答案:此句型對(duì)應(yīng)語(yǔ)法捌如為，故為此文法一個(gè)句型.或者:因?yàn)榇嬖谕茖?dǎo)序列：E=E-+|T=E+TF，所以中工文句型此句型相對(duì)E的短語(yǔ)有二E+T*F；相對(duì)于T的蜀語(yǔ)有T*F直接短語(yǔ)為：TW句柄為；T*Fas是相對(duì)S的短語(yǔ)aebbaa是相對(duì)S的口語(yǔ)直接配語(yǔ)有1句柄是：a第14題給出生成下述語(yǔ)言的上下文無(wú)關(guān)文法：(1)anb%mbm|n,m=0(2)lnOmlmOnln,m=0(3)WaWrlW寓于Ola*,W紙示W(wǎng)的逆答案：(1)SI(2)S1S0IOil(3)SOSOIISIIE第16題給出生成下述語(yǔ)言的三型文

6、法：(l)anln=0(2)anbmln,m=l(3)anbmckln,m,k=0答案：1SSIeSIIIII第18題解釋下列術(shù)語(yǔ)和概念：(1)字母表(2)串、字和句子(3)語(yǔ)言、語(yǔ)法和語(yǔ)義答案：(1)字母表：是一個(gè)非空有窮集合。(3)語(yǔ)言：它是由句子組成的集合，是由一組記號(hào)所構(gòu)成的集合。程序設(shè)計(jì)的語(yǔ)言就是所有該語(yǔ)言的程序的全體。語(yǔ)言可以看成在一個(gè)基本符號(hào)集上定義的，按一定規(guī)則構(gòu)成的一切基本符號(hào)串組成的集合。語(yǔ)法：表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的組合規(guī)律。程序的結(jié)構(gòu)或形式。語(yǔ)義：表示按照各種表示方法所表示的各個(gè)記號(hào)的特定含義。語(yǔ)言所代表的含義。附加題問(wèn)題1：給出下述文法所對(duì)應(yīng)的正規(guī)式：S0AI

7、1BA1SI1B0SI0答案：R=(01|10)(01|10)*問(wèn)題2：已知文法GA，寫出它定義的語(yǔ)言描述GA:A0BI1CB1I1AI0BBC0|0A|1CC答案:GA定義的語(yǔ)言由0、1符號(hào)串組成，串中0和1的個(gè)數(shù)相同.問(wèn)題3：給出語(yǔ)言描述，構(gòu)造文法.構(gòu)造一文法，其定義的語(yǔ)言是由算符+,*,(,)和運(yùn)算對(duì)象a構(gòu)成的算術(shù)表達(dá)式的集合.答案一：GEEEI*I(E)la答案二：GEEEEIE*EI(E)Ia問(wèn)題4：已知文法GS:SfdABAfaAlaBiIbB相應(yīng)的正規(guī)式是什么？GS能否改寫成為等價(jià)的正規(guī)文法？答案：正規(guī)式是daa*b*；相應(yīng)的正規(guī)文法為(由自動(dòng)機(jī)化簡(jiǎn)來(lái))：GS:SfdAAfaIaBBfaBIaIbIbCCfbCIb也可為(觀察得來(lái)):GS:SfdAAfalaAIaBBfbBI問(wèn)題5：已知文法G：+TI-TITTT*ITI()li試給出下述表達(dá)式的推導(dǎo)及語(yǔ)法樹i;i*i+ii+i*ii+(i+i)答案：E=T=F=i(2)E=E+T=T+T=T*F+T=F*F+T=i*F+T=i*i+T=i*i+F=i*i+i(3)E=E+T=T+