編譯原理作業(yè)集-第二章

--#?/16第二章高級(jí)語言及其語法描述本章要點(diǎn)程序語言的泄義：高級(jí)程序語言一般結(jié)構(gòu)和主要共同特征：正確理解上下文無關(guān)文法基本槪念，包括：文法的泄義、推導(dǎo)、句型、句子、語言、語法樹、二義性等：Chomsky文法分類：本章目標(biāo)掌握和理解程序語言的宦義、高級(jí)語言的一般特征及程序語言的語法描述。本章重點(diǎn)語法，詞法規(guī)則與語法規(guī)則：語義和語義規(guī)則：數(shù)據(jù)類型與操作：推導(dǎo)，最左推導(dǎo)和最右推導(dǎo)；語法分析樹和二義性：本章難點(diǎn)二義性文法：Chomsky各個(gè)文法類：作業(yè)題一、單項(xiàng)選擇題：（按照組卷方案，至少15道小題）Chomsky把文法分成四種類型，0型、1型、2型和3型。3型文法也稱為 ，2型文法也稱為 U上下文無關(guān)文法b.上下文相關(guān)文法c.正則文法d.短語文法TOC\o"1-5"\h\z許多廣為使用的語言，如Fortran、C^Pascal等，屬于 。a.強(qiáng)制式語言b.應(yīng)用式語言c.基于規(guī)則的語言 d.面向?qū)ο蟮恼Z言設(shè)G是一個(gè)文法，S是開始符號(hào)。若S=>9,ae(VTUVN)\則稱a是一個(gè) 。a.句子b.句型c.推導(dǎo)d.語言一個(gè)數(shù)據(jù)類型通常包括的三種要素中，沒有下面的 -a.用于區(qū)別這種類型的數(shù)據(jù)對(duì)象的屬性：b.這種類型的數(shù)據(jù)對(duì)象可以具有的值；c.對(duì)這種類型的數(shù)據(jù)對(duì)象的內(nèi)存分配：d.可以作用于這種類型的數(shù)據(jù)對(duì)象的操作:Chomsky把文法分成四種類型，其中， 也稱正規(guī)文法a.0型b.1型c.2型d.3型語言的詞法規(guī)則一般用Chomsky的 型文法來描述：a.0b.1c.2d.3文法S—(L)|aL—L,SIS中，下而—是該文法中的終結(jié)符號(hào)。a.Sb.,c.Ld.I文法G所描述的語言是 的集合。文法G的字母表為中的所有符號(hào)組成的符號(hào)串：文法G的字母表工的閉包工中的所有符號(hào)串；文法G的識(shí)別符號(hào)推出的所有符號(hào)串；文法G的識(shí)別符號(hào)推出的所有終結(jié)符號(hào)串；語言L={acaIae(alb)4},該語言是 語言。a.3型語言,b.2型語言,C.1型語言,d.O型語言設(shè)有文法G：I-*I1110IlaIIcIaIbIcI下面符號(hào)串中不是該文法的句子是： a.abO, b.aOcOl,c.aaa,d.bclO給泄文法A-bAlcc,下而的符號(hào)串中，是該文法句子的是 。a.bcbc,b.bbbcc,c.bcbcc,d.bccbcc：

Chomsky義的四種形式語言文法中，2型文法可由(G)識(shí)別。a.圖靈機(jī)：b.確泄性有限自動(dòng)機(jī)；c.下推自動(dòng)機(jī)：d.非確左性有限自動(dòng)機(jī):若文法G立義的語言是無限集，則文法必然是 a.上下文無關(guān)的b.遞歸的c.二義性的 d.無二義性的文法S-aaSlabc定義的語言是 。a.{a2kbclk>0) b.{akbclk>0}c.{a'kJbcIloO} d.{akakbclk>0})od.xnyxn(n^O)文法：)od.xnyxn(n^O)a.xyx b.(xyx)*c. x*yx*答案：1.c.：2.a.；3.b；4.c：5.d：6.d：7.b：&d：9.d；10.a；11.b；12.c：13.b：c：15.d；填空丿填空丿(按照組卷方案，至少15道小題)假設(shè)G是一個(gè)文法,a是由終結(jié)符和非終結(jié)符組成的串，S是文法的開始符號(hào)，如果S=>a,TOC\o"1-5"\h\z則稱a是 。在賦值語句中，賦值號(hào)'：='左右兩邊的變量劣扮演著兩種不同的角色，為了區(qū)分一個(gè)劃字的這兩種特征，我們把一個(gè)名字所代表的 稱為該名的左值，把一個(gè)名字的 稱為該名字的右值。對(duì)于文法G,僅含終結(jié)符號(hào)的句型稱為 。設(shè)有文法G[S],其部分產(chǎn)生式：E-E+TITT-*T*FIFF-*(E)laTOC\o"1-5"\h\z則％={ }.Vt={ }。由文法產(chǎn)生的 集合是文法產(chǎn)生的語言。Chomsky語法定義的3型文法又可以分為 ,一個(gè)上下文文法G的四個(gè)組成部分分別是： 已知語言:{a"b"ambmln,m^O}，其語法定義為:G=({a,b},{S,A,B},S,P),其中P為： o已知某語言的語法定義為：G=({a},{S}S.P),且P:S-aSI￡,則該語言TOC\o"1-5"\h\z為 °已知某語言為{3cwRloe(a,b}?},其語法定義為G=({a,b,c},{S},S,P),其中P為： “所謂最右推導(dǎo)是指 O已知文法G(Z):E-ET+ITT-*TF*IFF-FPtIPP-*Eli試寫出其識(shí)別的一個(gè)句子： 3文法G[S]：S-aAla,A-aS為 型文法，其確定的語言的為： 。在一棵語法樹生長(zhǎng)過程中的任何時(shí)刻， 就是一個(gè)句型。我們說G=(Vt,Vn,S,P)是一個(gè)0型文法，如果它的每一個(gè)產(chǎn)生式a-卩是這樣一種結(jié)構(gòu)： 答案：1.句型；2.單元的地址(或者：?jiǎn)卧⒋鎯?chǔ)單元的地址)，值(或者：?jiǎn)卧膬?nèi)容)3.句子：4.Vn={E,T,F},Vi={+,*,(,),a)：5.句子：6.右線性文法和左線性文法:7.開始符號(hào)，產(chǎn)生式集合，終結(jié)符集合，非終結(jié)符集合：&S-AB：A—aAbb：B-aBbb：9.{anln^0};10.S—aSalbSble：11.任何一步an卩都是對(duì)a中的最右非終結(jié)符進(jìn)行替換。12.13.{a2n+,ln>0}；14.所有那些沒有后代的末端結(jié)點(diǎn)從左到右排列起來;15.a￡(VNUVt)?且至少含有一個(gè)非終結(jié)符，而0G(VnUVT)\三、 判斷題：(按照組卷方案，至少15道小題)一棵語?法樹表示了一個(gè)句型所有的不同推導(dǎo)過程，包括最右推導(dǎo)和最左推導(dǎo)。()可能有兩個(gè)不同的文法G和G,期中一個(gè)是二義的而另一個(gè)是無二義的，但是卻有L(G)=L(Gf)0()變量既持有左值又持有右值，而常數(shù)和帶有算符的表達(dá)式一般認(rèn)為只持有右值。()文法G:S-*bAA-*aAla泄義的語言是所有以b開頭的后跟至少一個(gè)a的字符串的集合。()

設(shè)有文法G：S-*S*SIS+SI（S）la該文法是二義的。（）正則文法一定不是二義的。（）上下文無關(guān)文法可以產(chǎn)生語言L={anbnc'li>=l,n>=l}o（）不存在任何正規(guī)文法能產(chǎn)生語言L={anbnIn>=l}o（）對(duì)于每一個(gè)左線性文法Gi,都存在一個(gè)右線性文法G2,使得L（Gi）=L（G2）6（）正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。（）上下文無關(guān)文法比正規(guī)文法有更強(qiáng)的描述能力。（）文法的二義性和語言的二義性在概念上是相同的，也就是說，對(duì)于某個(gè)語言，不可能存在兩個(gè)以上的文法來描述它。（）二義性是可以判泄的，也就是說，可以編這么一個(gè)程序，輸入該文法后，該程序能確切地給出該文法是否二義的答案。（）14?說明語句旨在左義名字的性質(zhì)。編譯程序把這些性質(zhì)登記在符號(hào)表中，并檢查程序中名字的引用和說明是否一致。實(shí)際上，許多說明語句并不能翻譯成相應(yīng)的目標(biāo)代碼。（）C語言是一個(gè)允許子程序嵌套定義的語言。（）答案：1.7：2.7：3.7：4.7：5.7：6.X；7.Q：&7：9.Q：10.7：11.7：12.X；13.X；14.>1：15.X；四、名詞解q-r?四、名詞解q-r?（按照組卷方案，至少3道小題）二義性文法：2.推導(dǎo)和直接推導(dǎo)：3.句型，句子和語言；4.上下文無關(guān)文法；語法；6.正規(guī)文法（左線性文法和右線性文法）：答案：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵以上不同的語法樹，則稱這個(gè)文法是是二義性文法。設(shè)A-y是一個(gè)產(chǎn)生式，且cc、pe（VToVN）*,若aAp=>ayp,則稱aA卩直接推出。祁：或者說，旳卩是aA0的一個(gè)直接推導(dǎo)。如果ai=>a2=>……=>an,則稱這個(gè)序列是從a】到*的一個(gè)推導(dǎo)。設(shè)G是一個(gè)文法，S是它的開始符號(hào)。如果S=>*a,則稱a是一個(gè)句型。僅含終結(jié)符的句型叫句子。文法G所產(chǎn)生的句子的全體叫文法G的語言，記為L(zhǎng)(G),L(G)={alS=>a,aGVT*)o上下文無關(guān)文法G是一個(gè)四元式(Vt，Vn,S,P),其中：Vt是一個(gè)非空有限集合，其中的每一個(gè)元素稱為終結(jié)符：Vn是一個(gè)非空有限集合，其中的每一個(gè)元素稱為非終結(jié)符，vNnv-^0：S是一個(gè)非終結(jié)符，稱為開始符號(hào)：P是一個(gè)產(chǎn)生式有限集合，每個(gè)產(chǎn)生式的形式是P-*a,英中PgVn，<xG(V2Vn)*。開始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。若文法G=(Vt,Vn.S,P)的任何產(chǎn)生式為A-aB或A-a，其中，aeVT\A,BGVn,則稱G是右線性文法：若文法G=(Vr,Vn,S,P)的任何產(chǎn)生式為A-*Ba或A-a,其中，aeVT\A,BGVN,則稱G是左線性文法：左線性文法和右線性文法均為正規(guī)文法。五、簡(jiǎn)答題：(按照組卷方案，至少3逍小題)作為描述程序i馬言的上下文無關(guān)文法，對(duì)它有哪些限制？答：第一點(diǎn)：文法中不含任何下而形式的產(chǎn)生式：P-P;第二點(diǎn)：每個(gè)非終結(jié)符P都必須有用處。也就是說，必須存在含P的句型；或者說，對(duì)P不存在永不終結(jié)的回路。什么是二義性文法？從輸入串a(chǎn)bab來說明下而文法二義嗎？S—>aSbS[bSaS|￡該文法產(chǎn)生的語言是什么？答：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵以上不同的語法樹，則稱這個(gè)文法是二義的。例如輸入串a(chǎn)bab,它有兩棵語法樹如下：

所以，該文法是二義的。此文法產(chǎn)生的語言是：所有a的個(gè)數(shù)與b的個(gè)數(shù)相等的由a和所以，該文法是二義的。此文法產(chǎn)生的語言是：所有a的個(gè)數(shù)與b的個(gè)數(shù)相等的由a和b組成的字符串。文法G[S]為：S-*AclaBA—abB-*bc該文法是否為二義的？為什么？答：對(duì)于串a(chǎn)bc(1)S=>Ac=>abc(2)S=>aB=>abc即存在兩不同的最右推導(dǎo)。所以，該文法是二義的。或者：對(duì)輸入字符串a(chǎn)bc,能構(gòu)造兩棵不同的語法樹，所以它是二義的。4已知文法G=({A,B,C},{abc},P,A),P由以下產(chǎn)生式組成:A—abcA-*aBbcBb-bBBe—CbccbC-CbaC-*aaBaC-*aa此文法所表示的語言是什么？答：分析文法的規(guī)則：每使用一次Bc-Cbcc,b、c的個(gè)數(shù)各增加一個(gè)：每使用一次aC-*aaB或aC-*aa,a的個(gè)數(shù)就增加一個(gè)：產(chǎn)生式Bb-bB、bC-Cb起連接轉(zhuǎn)換作用。由于A是開始符號(hào)，由產(chǎn)生式A-abc推導(dǎo)得到終結(jié)符號(hào)串a(chǎn)bc；由產(chǎn)生式A-aBbe推導(dǎo)得到B后，每當(dāng)使用產(chǎn)生式Bb-bB、Be-Cbcc、bC-Cb、aC-aaB就會(huì)遞歸調(diào)用B一次，所產(chǎn)生的a、b、c的個(gè)數(shù)分別增加一個(gè)，因此推導(dǎo)所得的終結(jié)符號(hào)串為abc、aabbcc、aaabbbccc^…所以文法描述的語言為{anbncnln>0}.5已知文法G[Z]:Z-0UI1VU-1ZI1V-OZIO請(qǐng)寫出此文法描述的只含有4個(gè)符號(hào)的全部句子。G[Z]產(chǎn)生的語言是什么？該文法在Chomsky文法分類中屬于幾型文法？答：0101,0110,1010,1001分析G[Z]所推導(dǎo)出的句子的特點(diǎn)：由Z開始的推導(dǎo)不外乎圖1所示的四種情形。rI圖1文法G[Z]可能的兒種推導(dǎo)由Z推導(dǎo)出10或01后就終止或進(jìn)入遞歸，而Z的每次遞歸將推導(dǎo)岀相同的符號(hào)串：10或01.所以G[Z]產(chǎn)生的語言L(G[Z])={xlxE(10l01)+}該文法屬于3型文法。

七、應(yīng)用題:1.試分析下面給出的if-then-else語句的文法，它的提出原本是為了矯正dangling-else（else懸掛）文法的二義性：stmt—>ifexprthenstmtImatched-stmtmatched-stmt—^ifexprthenmatched-stmtelsestmtIotherexpr—^c考慮句子ifethenifethenotherelseifethenotherelseother,試說明此文法仍然是二義性的。答：1?考慮句子ifethenifethenotherelseifethenotherelseother它具有如下所示的兩種分析樹matchcd-stmtmatchcd-stmtcslcstmtotherothereslestmtmatchcd-stmtifothermatchcd-stmtothercslcstmtotherothereslestmtmatchcd-stmtifothermatchcd-stmtotherifexprthenmatched-stmtstmtmatchcd-stmtifexprthenmatchcd-stmteslestmtifexprthenmatchcd-stmtother則上而給出的if-then-else文法仍是二義性的。2.考慮文法G[bexpr]：bexpr—^hexprorhtennIbtennbtenn—^btennandhfactorIbfactorbfactor—^noxbfactori(bexpr)ItrueIfalse請(qǐng)指出此文法的終結(jié)符號(hào)、非終結(jié)符號(hào)和開始符號(hào)。試對(duì)于句子not(trueorfalse)構(gòu)造一棵分析樹a(C)試說明此文法所產(chǎn)生的語言是全體布爾表達(dá)式。答：終結(jié)符號(hào)為:{or,and.not,(,),true,false}非終結(jié)符號(hào)為：{bexpr,btenn.bfactor)開始符號(hào)為：bexpr句子not(irucorfalse)的分析樹為：用歸納法說明如下：不含運(yùn)算的布爾表達(dá)式，常數(shù)true和false由此文法產(chǎn)生：bexpr=>bterm=>bfactor=>tniebexpr=>bterm=>bfactor=>false設(shè)結(jié)論對(duì)于少于n(n>l)個(gè)運(yùn)算的布爾表達(dá)式成立，即若be,和bc2是含有少于n個(gè)運(yùn)算的布爾表達(dá)式，則有：bcxpr=>+bei,bexpr=>+be2。對(duì)于含有n個(gè)運(yùn)算的布爾表達(dá)式，可表示成下而三種形式：(bei)or(bez)(bef)and(be?)not(bei)對(duì)于(a)：bexpr=>bexprorbterm=>btermorbterm=>bfactororbtermbexprbtermbtermbfactorbfactortruefalse=>(bexpr)orbterm=>+(bC])orbterm=>(beDorbfactor=>(beJor(bexpr)=>*(bejor(be2)同理，有：Bcxpr=>+(bef)and(be2)Bcxpr=>4not(bef)綜上所述，此文法所產(chǎn)生的語言是全體布爾表達(dá)式。已知文法G[S],其產(chǎn)生式為：St(S)|￡L(G)是什么？對(duì)于(a)的結(jié)果，請(qǐng)給岀證明。答：解:L(G)={(")"ln>0}證明：首先證明L(G)c{(n)nln>0}對(duì)推導(dǎo)次數(shù)進(jìn)行歸納：當(dāng)推導(dǎo)次數(shù)為1時(shí)，使用產(chǎn)生式S-￡,此時(shí)左括號(hào)與右括號(hào)個(gè)數(shù)為0:假設(shè)推導(dǎo)次數(shù)為n時(shí)(a)成立，即：S=(((..S...)))=>(((..…)))n-1n-l n-1n—1則推導(dǎo)次數(shù)為n+l次時(shí)，多使用一次產(chǎn)生式S-(S)即：S厶(((..S...)))=>(((..S...)))=((()))n-ln-l n n nn推導(dǎo)次數(shù)為n+l次時(shí)(a)成立。根據(jù)⑴⑵可得：L(G)c{(n)nln>0)其次證明{(n)nln>0}cL(G)對(duì)n進(jìn)行歸納:當(dāng)n=0時(shí)，使用產(chǎn)生式S-￡即可；:假設(shè)當(dāng)n=k時(shí)，結(jié)論成立，即(k)keL(G),下而證n=k+l時(shí)結(jié)論成立。由(k)keL(G),其推導(dǎo)過程如下：Sd(((??S…)))=(((??…)))k k kk當(dāng)n=k+l時(shí)，推導(dǎo)過程如下：S二(((??S…)))亠(((??$??)))=(((??…)))k k k+1 k+1 k+lk+1故(3)3eL(G)根據(jù)⑴⑵可得:{(n)nln>O)cL(G)根據(jù)1，2可知：L(G)={(n)nl>0|試構(gòu)造生成下列語言的上下文無關(guān)文法：(1){anbncj11^1,1>0}⑵{wIwG{a.b}+,且w中a的個(gè)數(shù)恰好比b多1}(3){wlwG{a,b}+,jl|a|<|b|<2|a|}答：把a(bǔ)"b叩分成護(hù)7和(?兩部分，分別由兩個(gè)非終結(jié)符號(hào)生成，因此，生成此文法的產(chǎn)生式為：S—ABA—>aAbjabB—?cB|e令S為開始符號(hào)，產(chǎn)生的w中a的個(gè)數(shù)恰好比b多一個(gè)，令E為一個(gè)非終結(jié)符號(hào)，產(chǎn)生含相同個(gè)數(shù)的a和b的所有串，則產(chǎn)生式如下：S->aE|Ea|bSS|SbS|SSbE—>aEbE|bEaE|e⑶設(shè)文法開始符號(hào)為S,產(chǎn)生的w中滿足|a|<|b|<2|a|o因此可想到S有如下的產(chǎn)生式(苴中B產(chǎn)生1到2個(gè)b)：S—>aSBSpBSaSleB->b|bb已知文法G[S]:S—>ABA—>aA|aB->bB|b求該文法所定義的語言。答：從規(guī)則2可推出:a,aa,aaa, 從規(guī)則3可推出：b,bb.bbb,……再?gòu)囊?guī)則1可推出句子：ab,aab.aabb.aaab,abbb. 即，從S出發(fā)可推出多個(gè)a后跟多個(gè)b的字符串，且a的個(gè)數(shù)與b的個(gè)數(shù)不盡相冋。故：L(G)={ambnlnin^l}考慮下而上下文無關(guān)文法G[S]：S-SS*ISS+la(1)對(duì)于符號(hào)串a(chǎn)a+a*分別給岀最左推導(dǎo)和最右推導(dǎo)過程，并為該串構(gòu)造語法樹。⑵G[S]的語言是什么？答：(1)此文法生成串a(chǎn)a+a*的最右推導(dǎo)：S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*此文法生成串a(chǎn)a+a*的最左推導(dǎo)：S=>SS*=>SS+S*=>*=>aS+S*=>aa+S*=>aa+a*aa(2)該文法生成的語言是：左和+的后綴表達(dá)式，即逆波蘭式。7令文法G為N-*DINDD-0111213141516171819(DG的語言L(G)是什么？⑵給岀句子0127、34和568的最左推導(dǎo)和最右推導(dǎo)。答：(1)VNN=>ND=>NDD=>NDDD=>NDDDD……=>DD……Dr.L(G)={d(n+1)ln^o,de(o,1,…,9}}允許以0開頭的自然數(shù)(十進(jìn)制無符號(hào)整數(shù))：(2)0127最左推導(dǎo)：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=O1270127最右推導(dǎo)：N=>ND=>N7=>ND7=>N27=>ND27=>N127nD127=>01278寫一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。答：(首先分析題意，本題是希望構(gòu)造一個(gè)文法，由它產(chǎn)生的句子是奇數(shù)，并且不以0開頭,也就是說它的每個(gè)句子都是以1、3、5、7、9中的某個(gè)數(shù)結(jié)尾。如果數(shù)字只有一位，則1、3、5、7、9就滿足要求，如果有多位，則要求第1位不能是0,而中間有多少位，每位是什么數(shù)字(必須是數(shù)字)則沒什么要求，因此，我們可以把這個(gè)文法分3部分來完成。分別用3個(gè)非終結(jié)符來產(chǎn)生句子的第1位、中間部分和最后一位。引入幾個(gè)非終結(jié)符，其中，一個(gè)用作產(chǎn)生句子的開頭，可以是1一9之間的數(shù)，不包括0；一個(gè)用來產(chǎn)生句子的結(jié)尾，為奇數(shù)：另一個(gè)則用來產(chǎn)生以非0整數(shù)開頭后而跟任意多個(gè)數(shù)字的數(shù)字串，進(jìn)行分解之后，這個(gè)文法就很好寫了。)令S表示不以0開始的奇數(shù)集合。S-〈奇數(shù)頭〉〈整數(shù)〉〈奇數(shù)尾〉I〈奇數(shù)頭〉〈奇數(shù)尾〉I〈奇數(shù)尾〉倚數(shù)尾〉-1|3|5|7|9〈奇數(shù)頭〉一2|4冋8|〈奇數(shù)尾〉〈整數(shù)〉-〈整數(shù)〉〈數(shù)字〉I〈數(shù)字〉〈數(shù)字〉-0|〈奇數(shù)頭〉9寫一個(gè)上下文無關(guān)文法CFG,使其語言是能被5整除且不以0開頭的無符號(hào)整數(shù)的集合。(如{5,10,15,???.})答:能被5整除的數(shù)從形式上看，是以0和5結(jié)尾的數(shù)字串。題目要求的不以0開頭，并要注意0不是該語言的句子。所求文法為：G（S）：S-*MFI5F—5I0M-MDIND-NI0N-l|2|3|4|5|6|7|8|910證明下而的文法是二義的：STScSIiSIi答：（根據(jù)文法的二義性的左義，如果要證明該文法是二義的，必須找到一個(gè)句子，使得該句子具有兩個(gè)不同的最右推導(dǎo)或兩個(gè)不同的語法樹。我們首先分析這個(gè)文法，根據(jù)我們對(duì)程序語言的了解，不難發(fā)現(xiàn)，這個(gè)文法應(yīng)該是用來表示if….else….結(jié)構(gòu)的（用“i”代表“if