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

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

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

所以，該文法是二義的。此文法產(chǎn)生的語言是：所有a的個數(shù)與b的個數(shù)相等的由a和所以，該文法是二義的。此文法產(chǎn)生的語言是：所有a的個數(shù)與b的個數(shù)相等的由a和b組成的字符串。文法G[S]為：S-*AclaBA—abB-*bc該文法是否為二義的？為什么？答：對于串a(chǎn)bc(1)S=>Ac=>abc(2)S=>aB=>abc即存在兩不同的最右推導。所以，該文法是二義的?；蛘撸簩斎胱址產(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的個數(shù)各增加一個：每使用一次aC-*aaB或aC-*aa,a的個數(shù)就增加一個：產(chǎn)生式Bb-bB、bC-Cb起連接轉(zhuǎn)換作用。由于A是開始符號，由產(chǎn)生式A-abc推導得到終結(jié)符號串a(chǎn)bc；由產(chǎn)生式A-aBbe推導得到B后，每當使用產(chǎn)生式Bb-bB、Be-Cbcc、bC-Cb、aC-aaB就會遞歸調(diào)用B一次，所產(chǎn)生的a、b、c的個數(shù)分別增加一個，因此推導所得的終結(jié)符號串為abc、aabbcc、aaabbbccc^…所以文法描述的語言為{anbncnln>0}.5已知文法G[Z]:Z-0UI1VU-1ZI1V-OZIO請寫出此文法描述的只含有4個符號的全部句子。G[Z]產(chǎn)生的語言是什么？該文法在Chomsky文法分類中屬于幾型文法？答：0101,0110,1010,1001分析G[Z]所推導出的句子的特點：由Z開始的推導不外乎圖1所示的四種情形。rI圖1文法G[Z]可能的兒種推導由Z推導出10或01后就終止或進入遞歸，而Z的每次遞歸將推導岀相同的符號串：10或01.所以G[Z]產(chǎn)生的語言L(G[Z])={xlxE(10l01)+}該文法屬于3型文法。

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