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

第二章高級語言及其語法描述本章要點1.程序語言的定義；2.高級程序語言一般結(jié)構(gòu)和主要共同特征；3.正確理解上下文無關(guān)文法基本概念，包括：文法的定義、推導(dǎo)、句型、句子、語言、語法樹、二義性等；4.Chomsky文法分類；本章目標(biāo)掌握和理解程序語言的定義、高級語言的一般特征及程序語言的語法描述。本章重點1.語法，詞法規(guī)則與語法規(guī)則；2.語義和語義規(guī)則；3.數(shù)據(jù)類型與操作；4.推導(dǎo)，最左推導(dǎo)和最右推導(dǎo)；5.語法分析樹和二義性；本章難點1.二義性文法；2.Chomsky各個文法類；作業(yè)題一、單項選擇題：（按照組卷方案，至少15道小題）1.Chomsky把文法分成四種類型，0型、1型、2型和3型。3型文法也稱為，2型文法也稱為。a.上下文無關(guān)文法b.上下文相關(guān)文法c.正則文法d.短語文法2.許多廣為使用的語言，如Fortran、C、Pascal等，屬于。a.強制式語言b.應(yīng)用式語言c.基于規(guī)則的語言d.面向?qū)ο蟮恼Z言3.設(shè)G是一個文法，S是開始符號。若S*，(VT∪VN)*，則稱是一個。a.句子b.句型c.推導(dǎo)d.語言4.一個數(shù)據(jù)類型通常包括的三種要素中，沒有下面的。a.用于區(qū)別這種類型的數(shù)據(jù)對象的屬性；b.這種類型的數(shù)據(jù)對象可以具有的值；c.對這種類型的數(shù)據(jù)對象的內(nèi)存分配；d.可以作用于這種類型的數(shù)據(jù)對象的操作；5.Chomsky把文法分成四種類型，其中，也稱正規(guī)文法a.0型b.1型c.2型d.3型6.語言的詞法規(guī)則一般用Chomsky的型文法來描述：a.0 b.1 c.2 d.37.文法S→(L)|aL→L，S|S中，下面 是該文法中的終結(jié)符號。a.Sb.，c.Ld.|8.文法G所描述的語言是的集合。a.文法G的字母表中的所有符號組成的符號串；b.文法G的字母表的閉包*中的所有符號串；c.文法G的識別符號推出的所有符號串；d.文法G的識別符號推出的所有終結(jié)符號串；9.語言L={c|(a|b)*}，該語言是_____________語言。a.3型語言，b.2型語言，c.1型語言，d.0型語言10.設(shè)有文法G：I→I1|I0|Ia|Ic|a|b|c|下面符號串中不是該文法的句子是：a.ab0， b.a0c01， c.aaa， d.bc1011.給定文法A→bA|cc，下面的符號串中，是該文法句子的是________。a.bcbc， b.bbbcc， c.bcbcc， d.bccbcc；12.Chomsky定義的四種形式語言文法中，2型文法可由（G）識別。a.圖靈機；b.確定性有限自動機；c.下推自動機；d.非確定性有限自動機；13.若文法G定義的語言是無限集，則文法必然是。a.上下文無關(guān)的b.遞歸的c.二義性的d.無二義性的14.文法S→aaS|abc定義的語言是。a.{a2kbc|k>0} b.{akbc|k>0}c.{a2k-1bc|k>0} d.{akakbc|k>0}15.文法：G：S→xSx|y所識別的語言是（ ）。 a.xyx b.(xyx)* c.x*yx* d.xnyxn（n≥0）一．答案：1.c.；2.a.；3.b；4.c；5.d；6.d；7.b；8.d；9.d；10.a；11.b；12.c；13.b；14.c；15.d；二、填空題：（按照組卷方案，至少15道小題）1.假設(shè)G是一個文法，是由終結(jié)符和非終結(jié)符組成的串，S是文法的開始符號，如果S=>*，則稱是。2.在賦值語句中，賦值號‘：=’左右兩邊的變量名扮演著兩種不同的角色，為了區(qū)分一個名字的這兩種特征，我們把一個名字所代表的稱為該名的左值，把一個名字的稱為該名字的右值。3.對于文法G，僅含終結(jié)符號的句型稱為。4.設(shè)有文法G[S]，其部分產(chǎn)生式:E→E+T|TT→T*F|FF→(E)|a則VN={},VT={}。5.由文法產(chǎn)生的集合是文法產(chǎn)生的語言。6.Chomsky語法定義的3型文法又可以分為。7.一個上下文文法G的四個組成部分分別是：。8.已知語言：{anbnambm|n，m≥0}，其語法定義為：G=({a，b}，{S，A，B}，S，P)，其中P為：。9.已知某語言的語法定義為：G=({a},{S}S,P)，且P:S→aS|，則該語言為。10.已知某語言為{cwR|∈{a，b}*}，其語法定義為G=({a，b，c}，{S}，S，P)，其中P為：。11.所謂最右推導(dǎo)是指。12.已知文法G(Z):E→ET+|TT→TF*|FF→FP↑|PP→E|i試寫出其識別的一個句子：_____________________。13.文法G[S]：S→aA|a，

A→aS為_______型文法，其確定的語言的為：_______。14.在一棵語法樹生長過程中的任何時刻，就是一個句型。15.我們說G=(VT，VN，S，P)是一個0型文法，如果它的每一個產(chǎn)生式→是這樣一種結(jié)構(gòu)：。二．答案：1.句型；2.單元的地址（或者：單元、存儲單元的地址），值（或者：單元的內(nèi)容）3.句子；4.VN={E，T，F(xiàn)}，VT={+，*，(，)，a}；5.句子；6.右線性文法和左線性文法；7.開始符號，產(chǎn)生式集合，終結(jié)符集合，非終結(jié)符集合；8.S→AB；A→aAb|；B→aBb|；9.{an|n≥0}；10.S→aSa|bSb|；11.任何一步都是對中的最右非終結(jié)符進(jìn)行替換。12.iii↑*+；13.{a2n+1|n≥0}；14.所有那些沒有后代的末端結(jié)點從左到右排列起來；15.∈(VN∪VT)*且至少含有一個非終結(jié)符，而∈(VN∪VT)*。三、判斷題：（按照組卷方案，至少15道小題）1.一棵語法樹表示了一個句型所有的不同推導(dǎo)過程，包括最右推導(dǎo)和最左推導(dǎo)。（）2.可能有兩個不同的文法G和G′，期中一個是二義的而另一個是無二義的，但是卻有L(G)＝L(G′)。（）3.變量既持有左值又持有右值，而常數(shù)和帶有算符的表達(dá)式一般認(rèn)為只持有右值。（）4.文法G:S→bAA→aA|a定義的語言是所有以b開頭的后跟至少一個a的字符串的集合。（）5.設(shè)有文法G：S→S*S|S+S|(S)|a該文法是二義的。（）6.正則文法一定不是二義的。（）7.上下文無關(guān)文法可以產(chǎn)生語言L={anbnci|i>=1,n>=1}。（）8.不存在任何正規(guī)文法能產(chǎn)生語言L={anbn|n>=1}。（）9.對于每一個左線性文法G1，都存在一個右線性文法G2，使得L(G1)=L(G2)。（）10.正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。（）11.上下文無關(guān)文法比正規(guī)文法有更強的描述能力。（）12.文法的二義性和語言的二義性在概念上是相同的，也就是說，對于某個語言，不可能存在兩個以上的文法來描述它。（）13.二義性是可以判定的，也就是說，可以編這么一個程序，輸入該文法后，該程序能確切地給出該文法是否二義的答案。（）14.說明語句旨在定義名字的性質(zhì)。編譯程序把這些性質(zhì)登記在符號表中，并檢查程序中名字的引用和說明是否一致。實際上，許多說明語句并不能翻譯成相應(yīng)的目標(biāo)代碼。（）15.C語言是一個允許子程序嵌套定義的語言。（）三．答案：1.√；2.√；3.√；4.√；5.√；6.×；7.√；8.√；9.√；10.√；11.√；12.×；13.×；14.√；15.×；四、名詞解釋：（按照組卷方案，至少3道小題）1.二義性文法；2.推導(dǎo)和直接推導(dǎo)；3.句型，句子和語言；4.上下文無關(guān)文法；5.語法；6.正規(guī)文法（左線性文法和右線性文法）；四．答案：1.如果一個文法存在某個句子對應(yīng)兩棵以上不同的語法樹，則稱這個文法是是二義性文法。2.設(shè)A→是一個產(chǎn)生式，且、(VTVN)*，若A=>，則稱A直接推出；或者說，是A的一個直接推導(dǎo)。如果1=>2=>……=>n，則稱這個序列是從1到n的一個推導(dǎo)。3.設(shè)G是一個文法，S是它的開始符號。如果S=>*，則稱是一個句型。僅含終結(jié)符的句型叫句子。文法G所產(chǎn)生的句子的全體叫文法G的語言，記為L(G)，L(G)={|S=>*，∈VT*｝。4.上下文無關(guān)文法G是一個四元式(VT，VN，S，P)，其中：VT是一個非空有限集合，其中的每一個元素稱為終結(jié)符；VN是一個非空有限集合，其中的每一個元素稱為非終結(jié)符，VN∩VT=；S是一個非終結(jié)符，稱為開始符號；P是一個產(chǎn)生式有限集合，每個產(chǎn)生式的形式是P→，其中PVN，∈(VTVN)*。開始符號S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。5.若文法G=(VT，VN，S，P)的任何產(chǎn)生式為A→B或A→，其中，VT*，A，B∈VN，則稱G是右線性文法；若文法G=(VT，VN，S，P)的任何產(chǎn)生式為A→B或A→，其中，VT*，A，B∈VN，則稱G是左線性文法；左線性文法和右線性文法均為正規(guī)文法。五、簡答題：（按照組卷方案，至少3道小題）1.作為描述程序語言的上下文無關(guān)文法，對它有哪些限制？答：第一點：文法中不含任何下面形式的產(chǎn)生式：P→P；第二點：每個非終結(jié)符P都必須有用處。也就是說，必須存在含P的句型；或者說，對P不存在永不終結(jié)的回路。2.什么是二義性文法？從輸入串a(chǎn)bab來說明下面文法二義嗎？S→aSbS|bSaS|ε該文法產(chǎn)生的語言是什么？答：如果一個文法存在某個句子對應(yīng)兩棵以上不同的語法樹，則稱這個文法是二義的。例如輸入串a(chǎn)bab，它有兩棵語法樹如下：所以，該文法是二義的。此文法產(chǎn)生的語言是：所有a的個數(shù)與b的個數(shù)相等的由a和b組成的字符串。3.文法G[S]為：S→Ac|aBA→abB→bc該文法是否為二義的？為什么？答：對于串a(chǎn)bc(1)S=>Ac=>abc(2)S=>aB=>abc即存在兩不同的最右推導(dǎo)。所以，該文法是二義的?；蛘撸簩斎胱址產(chǎn)bc，能構(gòu)造兩棵不同的語法樹，所以它是二義的。4已知文法G=({A,B,C}，{a,b,c}，P，A),P由以下產(chǎn)生式組成:A→abcA→aBbcBb→bBBc→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推導(dǎo)得到終結(jié)符號串a(chǎn)bc；由產(chǎn)生式A→aBbc推導(dǎo)得到B后，每當(dāng)使用產(chǎn)生式Bb→bB、Bc→Cbcc、bC→Cb、aC→aaB就會遞歸調(diào)用B一次，所產(chǎn)生的a、b、c的個數(shù)分別增加一個，因此推導(dǎo)所得的終結(jié)符號串為abc、aabbcc、aaabbbccc、…所以文法描述的語言為{anbncn|n>0}.5已知文法G[Z]:Z→0U|1VU→1Z|1V→0Z|0（1）請寫出此文法描述的只含有４個符號的全部句子。（2）G[Z]產(chǎn)生的語言是什么？（3）該文法在Chomsky文法分類中屬于幾型文法？答：（1）0101，0110，1010，1001（2）分析G[Z]所推導(dǎo)出的句子的特點：由Z開始的推導(dǎo)不外乎圖1所示的四種情形。由Z推導(dǎo)出10或01后就終止或進(jìn)入遞歸，而Z的每次遞歸將推導(dǎo)出相同的符號串：10或01。所以G[Z]產(chǎn)生的語言L(G[Z])={x|x∈(10|01)+}(3)該文法屬于3型文法。七、應(yīng)用題：1.試分析下面給出的if-then-else語句的文法，它的提出原本是為了矯正dangling-else(else懸掛)文法的二義性：stmt→ifexprthenstmt|matched-stmtmatched-stmt→ifexprthenmatched-stmtelsestmt|otherexpr→e考慮句子ifethenifethenotherelseifethenotherelseother，試說明此文法仍然是二義性的。答：1.考慮句子ifethenifethenotherelseifethenotherelseother它具有如下所示的兩種分析樹則上面給出的if-then-else文法仍是二義性的。2.考慮文法G[bexpr]：bexpr→bexprorbterm|btermbterm→btermandbfactor|bfactorbfactor→notbfactor|(bexpr)|true|false(a)請指出此文法的終結(jié)符號、非終結(jié)符號和開始符號。(b)試對于句子not(trueorfalse)構(gòu)造一棵分析樹。(c)試說明此文法所產(chǎn)生的語言是全體布爾表達(dá)式。答：(a)終結(jié)符號為：{or,and,not,(,),true,false}非終結(jié)符號為：{bexpr,bterm,bfactor}開始符號為：bexpr(b)句子not(trueorfalse)的分析樹為：(c)用歸納法說明如下：(1)不含運算的布爾表達(dá)式，常數(shù)true和false由此文法產(chǎn)生：bexpr=>bterm=>bfactor=>truebexpr=>bterm=>bfactor=>false(2)設(shè)結(jié)論對于少于n(n≥1)個運算的布爾表達(dá)式成立，即若be1和be2是含有少于n個運算的布爾表達(dá)式，則有：bexpr=>+be1,bexpr=>+be2。(3)對于含有n個運算的布爾表達(dá)式，可表示成下面三種形式：(a)(be1)or(be2)(b)(be1)and(be2)(c)not(be1)對于(a)：bexpr=>bexprorbterm=>btermorbterm=>bfactororbterm=>(bexpr)orbterm=>+(be1)orbterm=>(be1)orbfactor=>(be1)or(bexpr)=>+(be1)or(be2)同理，有：Bexpr=>+(be1)and(be2)Bexpr=>+not(be1)綜上所述，此文法所產(chǎn)生的語言是全體布爾表達(dá)式。3.已知文法G[S],其產(chǎn)生式為：S→(S)|（a）L(G)是什么？（b）對于(a)的結(jié)果，請給出證明。答：(a)解：(b)證明：首先證明對推導(dǎo)次數(shù)進(jìn)行歸納1):當(dāng)推導(dǎo)次數(shù)為1時，使用產(chǎn)生式S→，此時左括號與右括號個數(shù)為02):假設(shè)推導(dǎo)次數(shù)為n時(a)成立,即:則推導(dǎo)次數(shù)為n+1次時，多使用一次產(chǎn)生式S→(S)即:推導(dǎo)次數(shù)為n+1次時(a)成立。根據(jù)(1)(2)可得：其次證明對n進(jìn)行歸納1):當(dāng)n=0時,使用產(chǎn)生式S→即可；2):假設(shè)當(dāng)n=k時,結(jié)論成立，即，下面證n=k+1時結(jié)論成立。由，其推導(dǎo)過程如下：當(dāng)n=k+1時，推導(dǎo)過程如下：故根據(jù)(1)(2)可得：根據(jù)1，2可知：4.試構(gòu)造生成下列語言的上下文無關(guān)文法：(1){anbnci|n≥1,i≥0}(2){w|w∈{a,b}+，且w中a的個數(shù)恰好比b多1}(3){w|w∈{a,b}+，且|a|≤|b|≤2|a|}答：（1）把anbnci分成anbn和ci兩部分，分別由兩個非終結(jié)符號生成，因此，生成此文法的產(chǎn)生式為：S→ABA→aAb|abB→cB|ε（2）令S為開始符號，產(chǎn)生的w中a的個數(shù)恰好比b多一個，令E為一個非終結(jié)符號，產(chǎn)生含相同個數(shù)的a和b的所有串，則產(chǎn)生式如下：S→aE|Ea|bSS|SbS|SSbE→aEbE|bEaE|ε(3)設(shè)文法開始符號為S，產(chǎn)生的w中滿足|a|≤|b|≤2|a|。因此，可想到S有如下的產(chǎn)生式（其中B產(chǎn)生1到2個b）：S→aSBS|BSaS|εB→b|bb5.已知文法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)={ambn|m,n≥1}6.考慮下面上下文無關(guān)文法G[S]：S→SS*|SS+|a(1)對于符號串a(chǎn)a+a*分別給出最左推導(dǎo)和最右推導(dǎo)過程，并為該串構(gòu)造語法樹。(2)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*(2)該文法生成的語言是：*和+的后綴表達(dá)式，即逆波蘭式。7令文法G為N→D|NDD→0|1|2|3|4|5|6|7|8|9(1)G的語言L（G）是什么？(2)給出句子0127、34和568的最左推導(dǎo)和最右推導(dǎo)。答：（1）∵NNNDNDDNDDDNDDDD……DD……D∴L(G)=｛d(n+1)|n≥0,d∈{0,1,…,9}｝允許以0開頭的自然數(shù)（十進(jìn)制無符號整數(shù)）；（2）0127最左推導(dǎo)：NNDNDDNDDDDDDD0DDD01DD012D01270127最右推導(dǎo)：NNDN7ND7N27ND27N127D12701278寫一個文法，使其語言是奇數(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ù)字串，進(jìn)行分解之后，這個文法就很好寫了。）令S表示不以0開始的奇數(shù)集合。S→〈奇數(shù)頭〉〈整數(shù)〉〈奇數(shù)尾〉|〈奇數(shù)頭〉〈奇數(shù)尾〉|〈奇數(shù)尾〉〈奇數(shù)尾〉→1|3|5|7|9〈奇數(shù)頭〉→2|4|6|8|〈奇數(shù)尾〉〈整數(shù)〉→〈整數(shù)〉〈數(shù)字〉|〈數(shù)字〉〈數(shù)字〉→0|〈奇數(shù)頭〉9寫一個上下文無關(guān)文法CFG，使其語言是能被5整除且不以0開頭的無符號整數(shù)的集合。（如｛5,10,15，….｝）答：能被5整除的數(shù)從形式上看，是以0和5結(jié)尾的數(shù)字串。題目要求的不以0開頭，并要注意0不是該語言的句子。所求文法為：G(S)：S→MF｜5 F→5｜0M→MD｜ND→N｜0N→1｜2｜3｜4｜5｜6｜7｜8｜910證明下面的文法是二義的：S→iSeS｜iS｜i答：（根據(jù)文法的二義性的定義，如果要證明該文法是二義的，必須找到一個句子，使得該句子具有兩個不同的最右推導(dǎo)或兩個不同的語法樹。我們首先分析這個文法，根據(jù)我們對程序語言的了解，不難發(fā)現(xiàn)，這個文法應(yīng)