编译原理作业集-第二章

--#・/16第二章高级语言及其语法描述本章要点程序语言的泄义：高级程序语言一般结构和主要共同特征：正确理解上下文无关文法基本槪念，包括：文法的泄义、推导、句型、句子、语言、语法树、二义性等：Chomsky文法分类：本章目标掌握和理解程序语言的宦义、高级语言的一般特征及程序语言的语法描述。本章重点语法，词法规则与语法规则：语义和语义规则：数据类型与操作：推导，最左推导和最右推导；语法分析树和二义性：本章难点二义性文法：Chomsky各个文法类：作业题一、单项选择题：（按照组卷方案，至少15道小题）Chomsky把文法分成四种类型，0型、1型、2型和3型。3型文法也称为 ，2型文法也称为 U上下文无关文法b.上下文相关文法c.正则文法d.短语文法TOC\o"1-5"\h\z许多广为使用的语言，如Fortran、C^Pascal等，属于 。a.强制式语言b.应用式语言c.基于规则的语言 d.面向对象的语言设G是一个文法，S是开始符号。若S=>9,ae(VTUVN)\则称a是一个 。a.句子b.句型c.推导d.语言一个数据类型通常包括的三种要素中，没有下面的 -a.用于区别这种类型的数据对象的属性：b.这种类型的数据对象可以具有的值；c.对这种类型的数据对象的内存分配：d.可以作用于这种类型的数据对象的操作:Chomsky把文法分成四种类型，其中， 也称正规文法a.0型b.1型c.2型d.3型语言的词法规则一般用Chomsky的 型文法来描述：a.0b.1c.2d.3文法S—(L)|aL—L,SIS中，下而—是该文法中的终结符号。a.Sb.,c.Ld.I文法G所描述的语言是 的集合。文法G的字母表为中的所有符号组成的符号串：文法G的字母表工的闭包工中的所有符号串；文法G的识别符号推出的所有符号串；文法G的识别符号推出的所有终结符号串；语言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是由终结符和非终结符组成的串，S是文法的开始符号，如果S=>a,TOC\o"1-5"\h\z则称a是 。在赋值语句中，赋值号'：='左右两边的变量劣扮演着两种不同的角色，为了区分一个划字的这两种特征，我们把一个名字所代表的 称为该名的左值，把一个名字的 称为该名字的右值。对于文法G,仅含终结符号的句型称为 。设有文法G[S],其部分产生式：E-E+TITT-*T*FIFF-*(E)laTOC\o"1-5"\h\z则％={ }.Vt={ }。由文法产生的 集合是文法产生的语言。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型文法，如果它的每一个产生式a-卩是这样一种结构： 答案：1.句型；2.单元的地址(或者：单元、存储单元的地址)，值(或者：单元的内容)3.句子：4.Vn={E,T,F},Vi={+,*,(,),a)：5.句子：6.右线性文法和左线性文法:7.开始符号，产生式集合，终结符集合，非终结符集合：&S-AB：A—aAbb：B-aBbb：9.{anln^0};10.S—aSalbSble：11.任何一步an卩都是对a中的最右非终结符进行替换。12.13.{a2n+,ln>0}；14.所有那些没有后代的末端结点从左到右排列起来;15.a£(VNUVt)♦且至少含有一个非终结符，而0G(VnUVT)\三、 判断题：(按照组卷方案，至少15道小题)一棵语•法树表示了一个句型所有的不同推导过程，包括最右推导和最左推导。()可能有两个不同的文法G和G,期中一个是二义的而另一个是无二义的，但是却有L(G)=L(Gf)0()变量既持有左值又持有右值，而常数和带有算符的表达式一般认为只持有右值。()文法G:S-*bAA-*aAla泄义的语言是所有以b开头的后跟至少一个a的字符串的集合。()

设有文法G：S-*S*SIS+SI（S）la该文法是二义的。（）正则文法一定不是二义的。（）上下文无关文法可以产生语言L={anbnc'li>=l,n>=l}o（）不存在任何正规文法能产生语言L={anbnIn>=l}o（）对于每一个左线性文法Gi,都存在一个右线性文法G2,使得L（Gi）=L（G2）6（）正规文法产生的语言都可以用上下文无关文法来描述。（）上下文无关文法比正规文法有更强的描述能力。（）文法的二义性和语言的二义性在概念上是相同的，也就是说，对于某个语言，不可能存在两个以上的文法来描述它。（）二义性是可以判泄的，也就是说，可以编这么一个程序，输入该文法后，该程序能确切地给出该文法是否二义的答案。（）14•说明语句旨在左义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否一致。实际上，许多说明语句并不能翻译成相应的目标代码。（）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.正规文法（左线性文法和右线性文法）：答案：如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是是二义性文法。设A-y是一个产生式，且cc、pe（VToVN）*,若aAp=>ayp,则称aA卩直接推出。祁：或者说，旳卩是aA0的一个直接推导。如果ai=>a2=>……=>an,则称这个序列是从a】到*的一个推导。设G是一个文法，S是它的开始符号。如果S=>*a,则称a是一个句型。仅含终结符的句型叫句子。文法G所产生的句子的全体叫文法G的语言，记为L(G),L(G)={alS=>a,aGVT*)o上下文无关文法G是一个四元式(Vt，Vn,S,P),其中：Vt是一个非空有限集合，其中的每一个元素称为终结符：Vn是一个非空有限集合，其中的每一个元素称为非终结符，vNnv-^0：S是一个非终结符，称为开始符号：P是一个产生式有限集合，每个产生式的形式是P-*a,英中PgVn，<xG(V2Vn)*。开始符号S至少必须在某个产生式的左部出现一次。若文法G=(Vt,Vn.S,P)的任何产生式为A-aB或A-a，其中，aeVT\A,BGVn,则称G是右线性文法：若文法G=(Vr,Vn,S,P)的任何产生式为A-*Ba或A-a,其中，aeVT\A,BGVN,则称G是左线性文法：左线性文法和右线性文法均为正规文法。五、简答题：(按照组卷方案，至少3逍小题)作为描述程序i马言的上下文无关文法，对它有哪些限制？答：第一点：文法中不含任何下而形式的产生式：P-P;第二点：每个非终结符P都必须有用处。也就是说，必须存在含P的句型；或者说，对P不存在永不终结的回路。什么是二义性文法？从输入串abab来说明下而文法二义吗？S—>aSbS[bSaS|£该文法产生的语言是什么？答：如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是二义的。例如输入串abab,它有两棵语法树如下：

所以，该文法是二义的。此文法产生的语言是：所有a的个数与b的个数相等的由a和所以，该文法是二义的。此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。文法G[S]为：S-*AclaBA—abB-*bc该文法是否为二义的？为什么？答：对于串abc(1)S=>Ac=>abc(2)S=>aB=>abc即存在两不同的最右推导。所以，该文法是二义的。或者：对输入字符串abc,能构造两棵不同的语法树，所以它是二义的。4已知文法G=({A,B,C},{abc},P,A),P由以下产生式组成:A—abcA-*aBbcBb-bBBe—CbccbC-CbaC-*aaBaC-*aa此文法所表示的语言是什么？答：分析文法的规则：每使用一次Bc-Cbcc,b、c的个数各增加一个：每使用一次aC-*aaB或aC-*aa,a的个数就增加一个：产生式Bb-bB、bC-Cb起连接转换作用。由于A是开始符号，由产生式A-abc推导得到终结符号串abc；由产生式A-aBbe推导得到B后，每当使用产生式Bb-bB、Be-Cbcc、bC-Cb、aC-aaB就会递归调用B一次，所产生的a、b、c的个数分别增加一个，因此推导所得的终结符号串为abc、aabbcc、aaabbbccc^…所以文法描述的语言为{anbncnln>0}.5已知文法G[Z]:Z-0UI1VU-1ZI1V-OZIO请写出此文法描述的只含有4个符号的全部句子。G[Z]产生的语言是什么？该文法在Chomsky文法分类中属于几型文法？答：0101,0110,1010,1001分析G[Z]所推导出的句子的特点：由Z开始的推导不外乎图1所示的四种情形。rI图1文法G[Z]可能的儿种推导由Z推导出10或01后就终止或进入递归，而Z的每次递归将推导岀相同的符号串：10或01.所以G[Z]产生的语言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请指出此文法的终结符号、非终结符号和开始符号。试对于句子not(trueorfalse)构造一棵分析树a(C)试说明此文法所产生的语言是全体布尔表达式。答：终结符号为:{or,and.not,(,),true,false}非终结符号为：{bexpr,btenn.bfactor)开始符号为：bexpr句子not(irucorfalse)的分析树为：用归纳法说明如下：不含运算的布尔表达式，常数true和false由此文法产生：bexpr=>bterm=>bfactor=>tniebexpr=>bterm=>bfactor=>false设结论对于少于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)综上所述，此文法所产生的语言是全体布尔表达式。已知文法G[S],其产生式为：St(S)|£L(G)是什么？对于(a)的结果，请给岀证明。答：解:L(G)={(")"ln>0}证明：首先证明L(G)c{(n)nln>0}对推导次数进行归纳：当推导次数为1时，使用产生式S-£,此时左括号与右括号个数为0:假设推导次数为n时(a)成立，即：S=(((..S...)))=>(((..…)))n-1n-l n-1n—1则推导次数为n+l次时，多使用一次产生式S-(S)即：S厶(((..S...)))=>(((..S...)))=((()))n-ln-l n n nn推导次数为n+l次时(a)成立。根据⑴⑵可得：L(G)c{(n)nln>0)其次证明{(n)nln>0}cL(G)对n进行归纳:当n=0时，使用产生式S-£即可；:假设当n=k时，结论成立，即(k)keL(G),下而证n=k+l时结论成立。由(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)根据⑴⑵可得:{(n)nln>O)cL(G)根据1，2可知：L(G)={(n)nl>0|试构造生成下列语言的上下文无关文法：(1){anbncj11^1,1>0}⑵{wIwG{a.b}+,且w中a的个数恰好比b多1}(3){wlwG{a,b}+,jl|a|<|b|<2|a|}答：把a"b叩分成护7和(?两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：S—ABA—>aAbjabB—►cB|e令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：S->aE|Ea|bSS|SbS|SSbE—>aEbE|bEaE|e⑶设文法开始符号为S,产生的w中满足|a|<|b|<2|a|o因此可想到S有如下的产生式(苴中B产生1到2个b)：S—>aSBSpBSaSleB->b|bb已知文法G[S]:S—>ABA—>aA|aB->bB|b求该文法所定义的语言。答：从规则2可推出:a,aa,aaa, 从规则3可推出：b,bb.bbb,……再从规则1可推出句子：ab,aab.aabb.aaab,abbb. 即，从S出发可推出多个a后跟多个b的字符串，且a的个数与b的个数不尽相冋。故：L(G)={ambnlnin^l}考虑下而上下文无关文法G[S]：S-SS*ISS+la(1)对于符号串aa+a*分别给岀最左推导和最右推导过程，并为该串构造语法树。⑵G[S]的语言是什么？答：(1)此文法生成串aa+a*的最右推导：S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*此文法生成串aa+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开头的自然数(十进制无符号整数)：(2)0127最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=O1270127最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127nD127=>01278写一个文法，使其语言是奇数集，且每个奇数不以0开头。答：(首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头,也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0,而中间有多少位，每位是什么数字(必须是数字)则没什么要求，因此，我们可以把这个文法分3部分来完成。分别用3个非终结符来产生句子的第1位、中间部分和最后一位。引入几个非终结符，其中，一个用作产生句子的开头，可以是1一9之间的数，不包括0；一个用来产生句子的结尾，为奇数：另一个则用来产生以非0整数开头后而跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。)令S表示不以0开始的奇数集合。S-〈奇数头〉〈整数〉〈奇数尾〉I〈奇数头〉〈奇数尾〉I〈奇数尾〉倚数尾〉-1|3|5|7|9〈奇数头〉一2|4冋8|〈奇数尾〉〈整数〉-〈整数〉〈数字〉I〈数字〉〈数字〉-0|〈奇数头〉9写一个上下文无关文法CFG,使其语言是能被5整除且不以0开头的无符号整数的集合。(如{5,10,15,•••.})答:能被5整除的数从形式上看，是以0和5结尾的数字串。题目要求的不以0开头，并要注意0不是该语言的句子。所求文法为：G（S）：S-*MFI5F—5I0M-MDIND-NI0N-l|2|3|4|5|6|7|8|910证明下而的文法是二义的：STScSIiSIi答：（根据文法的二义性的左义，如果要证明该文法是二义的，必须找到一个句子，使得该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法，根据我们对程序语言的了解，不难发现，这个文法应该是用来表示if….else….结构的（用“i”代表“if