编译原理作业集-第二章

第二章高级语言及其语法描述本章要点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.0b.1c.2d.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|k0}b.{akbc|k0}c.{a2k-1bc|k0}d.{akakbc|k0}15.文法：G：S→xSx|y所识别的语言是（）。a.xyxb.(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→是一个产生式，且、(VTVN)*，若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→，其中PVN，∈(VTVN)*。开始符号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，它有两棵语法树如下：SaSbSbSaSSaSbSaSbS所以，该文法是二义的。此文法产生的语言是：所有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|n0}.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所示的四种情形。图1文法G[Z]可能的几种推导Z01UZU0Z1Z1V0ZZ10V由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它具有如下所示的两种分析树stmtifexprthenstmtmat