编译原理作业集-第二章

第二章高级语言及其语法描述本章要点1.程序语言的定义；2.高级程序语言一般结构和主要共同特征；3.正确理解上下文无关文法基本概念，包括：文法的定义、推导、句型、句子、语言、语法树、二义性等；4.Chomsky文法分类；本章目标掌握和理解程序语言的定义、高级语言的一般特征及程序语言的语法描述。本章重点1.语法，词法规则与语法规则；2.语义和语义规则；3.数据类型与操作；4.推导，最左推导和最右推导；5.语法分析树和二义性；本章难点1.二义性文法；2.Chomsky各个文法类；作业题一、单项选择题：（按照组卷方案，至少15道小题）1.Chomsky把文法分成四种类型，0型、1型、2型和3型。3型文法也称为，2型文法也称为。a.上下文无关文法b.上下文相关文法c.正则文法d.短语文法2.许多广为使用的语言，如Fortran、C、Pascal等，属于。a.强制式语言b.应用式语言c.基于规则的语言d.面向对象的语言3.设G是一个文法，S是开始符号。若S*，(VT∪VN)*，则称是一个。a.句子b.句型c.推导d.语言4.一个数据类型通常包括的三种要素中，没有下面的。a.用于区别这种类型的数据对象的属性；b.这种类型的数据对象可以具有的值；c.对这种类型的数据对象的内存分配；d.可以作用于这种类型的数据对象的操作；5.Chomsky把文法分成四种类型，其中，也称正规文法a.0型b.1型c.2型d.3型6.语言的词法规则一般用Chomsky的型文法来描述：a.0 b.1 c.2 d.37.文法S→(L)|aL→L，S|S中，下面 是该文法中的终结符号。a.Sb.，c.Ld.|8.文法G所描述的语言是的集合。a.文法G的字母表中的所有符号组成的符号串；b.文法G的字母表的闭包*中的所有符号串；c.文法G的识别符号推出的所有符号串；d.文法G的识别符号推出的所有终结符号串；9.语言L={c|(a|b)*}，该语言是_____________语言。a.3型语言，b.2型语言，c.1型语言，d.0型语言10.设有文法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.上下文无关的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.假设G是一个文法，是由终结符和非终结符组成的串，S是文法的开始符号，如果S=>*，则称是。2.在赋值语句中，赋值号‘：=’左右两边的变量名扮演着两种不同的角色，为了区分一个名字的这两种特征，我们把一个名字所代表的称为该名的左值，把一个名字的称为该名字的右值。3.对于文法G，仅含终结符号的句型称为。4.设有文法G[S]，其部分产生式:E→E+T|TT→T*F|FF→(E)|a则VN={},VT={}。5.由文法产生的集合是文法产生的语言。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.所谓最右推导是指。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型文法，如果它的每一个产生式→是这样一种结构：。二．答案：1.句型；2.单元的地址（或者：单元、存储单元的地址），值（或者：单元的内容）3.句子；4.VN={E，T，F}，VT={+，*，(，)，a}；5.句子；6.右线性文法和左线性文法；7.开始符号，产生式集合，终结符集合，非终结符集合；8.S→AB；A→aAb|；B→aBb|；9.{an|n≥0}；10.S→aSa|bSb|；11.任何一步都是对中的最右非终结符进行替换。12.iii↑*+；13.{a2n+1|n≥0}；14.所有那些没有后代的末端结点从左到右排列起来；15.∈(VN∪VT)*且至少含有一个非终结符，而∈(VN∪VT)*。三、判断题：（按照组卷方案，至少15道小题）1.一棵语法树表示了一个句型所有的不同推导过程，包括最右推导和最左推导。（）2.可能有两个不同的文法G和G′，期中一个是二义的而另一个是无二义的，但是却有L(G)＝L(G′)。（）3.变量既持有左值又持有右值，而常数和带有算符的表达式一般认为只持有右值。（）4.文法G:S→bAA→aA|a定义的语言是所有以b开头的后跟至少一个a的字符串的集合。（）5.设有文法G：S→S*S|S+S|(S)|a该文法是二义的。（）6.正则文法一定不是二义的。（）7.上下文无关文法可以产生语言L={anbnci|i>=1,n>=1}。（）8.不存在任何正规文法能产生语言L={anbn|n>=1}。（）9.对于每一个左线性文法G1，都存在一个右线性文法G2，使得L(G1)=L(G2)。（）10.正规文法产生的语言都可以用上下文无关文法来描述。（）11.上下文无关文法比正规文法有更强的描述能力。（）12.文法的二义性和语言的二义性在概念上是相同的，也就是说，对于某个语言，不可能存在两个以上的文法来描述它。（）13.二义性是可以判定的，也就是说，可以编这么一个程序，输入该文法后，该程序能确切地给出该文法是否二义的答案。（）14.说明语句旨在定义名字的性质。编译程序把这些性质登记在符号表中，并检查程序中名字的引用和说明是否一致。实际上，许多说明语句并不能翻译成相应的目标代码。（）15.C语言是一个允许子程序嵌套定义的语言。（）三．答案：1.√；2.√；3.√；4.√；5.√；6.×；7.√；8.√；9.√；10.√；11.√；12.×；13.×；14.√；15.×；四、名词解释：（按照组卷方案，至少3道小题）1.二义性文法；2.推导和直接推导；3.句型，句子和语言；4.上下文无关文法；5.语法；6.正规文法（左线性文法和右线性文法）；四．答案：1.如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是是二义性文法。2.设A→是一个产生式，且、(VTVN)*，若A=>，则称A直接推出；或者说，是A的一个直接推导。如果1=>2=>……=>n，则称这个序列是从1到n的一个推导。3.设G是一个文法，S是它的开始符号。如果S=>*，则称是一个句型。仅含终结符的句型叫句子。文法G所产生的句子的全体叫文法G的语言，记为L(G)，L(G)={|S=>*，∈VT*｝。4.上下文无关文法G是一个四元式(VT，VN，S，P)，其中：VT是一个非空有限集合，其中的每一个元素称为终结符；VN是一个非空有限集合，其中的每一个元素称为非终结符，VN∩VT=；S是一个非终结符，称为开始符号；P是一个产生式有限集合，每个产生式的形式是P→，其中PVN，∈(VTVN)*。开始符号S至少必须在某个产生式的左部出现一次。5.若文法G=(VT，VN，S，P)的任何产生式为A→B或A→，其中，VT*，A，B∈VN，则称G是右线性文法；若文法G=(VT，VN，S，P)的任何产生式为A→B或A→，其中，VT*，A，B∈VN，则称G是左线性文法；左线性文法和右线性文法均为正规文法。五、简答题：（按照组卷方案，至少3道小题）1.作为描述程序语言的上下文无关文法，对它有哪些限制？答：第一点：文法中不含任何下面形式的产生式：P→P；第二点：每个非终结符P都必须有用处。也就是说，必须存在含P的句型；或者说，对P不存在永不终结的回路。2.什么是二义性文法？从输入串abab来说明下面文法二义吗？S→aSbS|bSaS|ε该文法产生的语言是什么？答：如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是二义的。例如输入串abab，它有两棵语法树如下：所以，该文法是二义的。此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。3.文法G[S]为：S→Ac|aBA→abB→bc该文法是否为二义的？为什么？答：对于串abc(1)S=>Ac=>abc(2)S=>aB=>abc即存在两不同的最右推导。所以，该文法是二义的。或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。4已知文法G=({A,B,C}，{a,b,c}，P，A),P由以下产生式组成:A→abcA→aBbcBb→bBBc→CbccbC→CbaC→aaBaC→aa此文法所表示的语言是什么？答：分析文法的规则：每使用一次Bc→Cbcc，b、c的个数各增加一个；每使用一次aC→aaB或aC→aa,a的个数就增加一个；产生式Bb→bB、bC→Cb起连接转换作用。由于A是开始符号，由产生式A→abc推导得到终结符号串abc；由产生式A→aBbc推导得到B后，每当使用产生式Bb→bB、Bc→Cbcc、bC→Cb、aC→aaB就会递归调用B一次，所产生的a、b、c的个数分别增加一个，因此推导所得的终结符号串为abc、aabbcc、aaabbbccc、…所以文法描述的语言为{anbncn|n>0}.5已知文法G[Z]:Z→0U|1VU→1Z|1V→0Z|0（1）请写出此文法描述的只含有４个符号的全部句子。（2）G[Z]产生的语言是什么？（3）该文法在Chomsky文法分类中属于几型文法？答：（1）0101，0110，1010，1001（2）分析G[Z]所推导出的句子的特点：由Z开始的推导不外乎图1所示的四种情形。由Z推导出10或01后就终止或进入递归，而Z的每次递归将推导出相同的符号串：10或01。所以G[Z]产生的语言L(G[Z])={x|x∈(10|01)+}(3)该文法属于3型文法。七、应用题：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)请指出此文法的终结符号、非终结符号和开始符号。(b)试对于句子not(trueorfalse)构造一棵分析树。(c)试说明此文法所产生的语言是全体布尔表达式。答：(a)终结符号为：{or,and,not,(,),true,false}非终结符号为：{bexpr,bterm,bfactor}开始符号为：bexpr(b)句子not(trueorfalse)的分析树为：(c)用归纳法说明如下：(1)不含运算的布尔表达式，常数true和false由此文法产生：bexpr=>bterm=>bfactor=>truebexpr=>bterm=>bfactor=>false(2)设结论对于少于n(n≥1)个运算的布尔表达式成立，即若be1和be2是含有少于n个运算的布尔表达式，则有：bexpr=>+be1,bexpr=>+be2。(3)对于含有n个运算的布尔表达式，可表示成下面三种形式：(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)综上所述，此文法所产生的语言是全体布尔表达式。3.已知文法G[S],其产生式为：S→(S)|（a）L(G)是什么？（b）对于(a)的结果，请给出证明。答：(a)解：(b)证明：首先证明对推导次数进行归纳1):当推导次数为1时，使用产生式S→，此时左括号与右括号个数为02):假设推导次数为n时(a)成立,即:则推导次数为n+1次时，多使用一次产生式S→(S)即:推导次数为n+1次时(a)成立。根据(1)(2)可得：其次证明对n进行归纳1):当n=0时,使用产生式S→即可；2):假设当n=k时,结论成立，即，下面证n=k+1时结论成立。由，其推导过程如下：当n=k+1时，推导过程如下：故根据(1)(2)可得：根据1，2可知：4.试构造生成下列语言的上下文无关文法：(1){anbnci|n≥1,i≥0}(2){w|w∈{a,b}+，且w中a的个数恰好比b多1}(3){w|w∈{a,b}+，且|a|≤|b|≤2|a|}答：（1）把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：S→ABA→aAb|abB→cB|ε（2）令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：S→aE|Ea|bSS|SbS|SSbE→aEbE|bEaE|ε(3)设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。因此，可想到S有如下的产生式（其中B产生1到2个b）：S→aSBS|BSaS|εB→b|bb5.已知文法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)={ambn|m,n≥1}6.考虑下面上下文无关文法G[S]：S→SS*|SS+|a(1)对于符号串aa+a*分别给出最左推导和最右推导过程，并为该串构造语法树。(2)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*(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。7令文法G为N→D|NDD→0|1|2|3|4|5|6|7|8|9(1)G的语言L（G）是什么？(2)给出句子0127、34和568的最左推导和最右推导。答：（1）∵NNNDNDDNDDDNDDDD……DD……D∴L(G)=｛d(n+1)|n≥0,d∈{0,1,…,9}｝允许以0开头的自然数（十进制无符号整数）；（2）0127最左推导：NNDNDDNDDDDDDD0DDD01DD012D01270127最右推导：NNDN7ND7N27ND27N127D12701278写一个文法，使其语言是奇数集，且每个奇数不以0开头。答：（首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。分别用3个非终结符来产生句子的第1位、中间部分和最后一位。引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0；一个用来产生句子的结尾，为奇数；另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。）令S表示不以0开始的奇数集合。S→〈奇数头〉〈整数〉〈奇数尾〉|〈奇数头〉〈奇数尾〉|〈奇数尾〉〈奇数尾〉→1|3|5|7|9〈奇数头〉→2|4|6|8|〈奇数尾〉〈整数〉→〈整数〉〈数字〉|〈数字〉〈数字〉→0|〈奇数头〉9写一个上下文无关文法CFG，使其语言是能被5整除且不以0开头的无符号整数的集合。（如｛5,10,15，….｝）答：能被5整除的数从形式上看，是以0和5结尾的数字串。题目要求的不以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答：（根据文法的二义性的定义，如果要证明该文法是二义的，必须找到一个句子，使得该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法，根据我们对程序语言的了解，不难发现，这个文法应