编译原理作业集-第二章

1、第二章 高级语言及其语法描述本章要点1. 程序语言的定义；2. 高级程序语言一般结构和主要共同特征；3. 正确理解上下文无关文法基本概念，包括：文法的定义、推导、句型、句子、语言、语法树、二义性等；4. Chomsky文法分类；本章目标掌握和理解程序语言的定义、高级语言的一般特征及程序语言的语法描述。本章重点1. 语法，词法规则与语法规则；2. 语义和语义规则；3. 数据类型与操作；4. 推导，最左推导和最右推导；5. 语法分析树和二义性；本章难点1. 二义性文法；2. Chomsky各个文法类；作业题一、单项选择题：（按照组卷方案，至少15道小题）1. Chomsky把文法分成四种类型，0型

2、、1型、2型和3型。3型文法也称为 ，2型文法也称为 。a.上下文无关文法 b.上下文相关文法 c.正则文法 d.短语文法2. 许多广为使用的语言，如Fortran、C、Pascal等，属于 。a. 强制式语言 b. 应用式语言 c. 基于规则的语言 d. 面向对象的语言3. 设G是一个文法，S是开始符号。若SÞ*a，aÎ(VTVN)*，则称a是一个 。a. 句子 b. 句型 c. 推导 d. 语言4. 一个数据类型通常包括的三种要素中，没有下面的 。a. 用于区别这种类型的数据对象的属性；b. 这种类型的数据对象可以具有的值；c. 对这种类型的数据对象的内存分配；d. 可

3、以作用于这种类型的数据对象的操作；5. Chomsky把文法分成四种类型，其中， 也称正规文法a. 0型 b. 1型 c. 2型 d. 3型6. 语言的词法规则一般用Chomsky的 型文法来描述：a. 0b. 1c. 2d. 37. 文法S(L)|aLL，S|S中，下面是该文法中的终结符号。a. S b. ， c. L d. |8. 文法G所描述的语言是 的集合。a. 文法G的字母表å中的所有符号组成的符号串；b. 文法G的字母表å的闭包å*中的所有符号串；c. 文法G的识别符号推出的所有符号串；d. 文法G的识别符号推出的所有终结符号串；9. 语言L=aca

4、| aÎ(a|b)*，该语言是_语言。a. 3型语言，b. 2型语言，c. 1型语言，d. 0型语言10. 设有文法G：II1 | I0 | Ia | Ic | a | b | c | 下面符号串中不是该文法的句子是： a. ab0， b. a0c01，c. aaa，d. bc1011. 给定文法AbA|cc，下面的符号串中，是该文法句子的是_。a. bcbc，b. bbbcc，c. bcbcc， d. bccbcc；12. Chomsky定义的四种形式语言文法中，2型文法可由（ G ）识别。a. 图灵机；b. 确定性有限自动机；c. 下推自动机；d. 非确定性有限自动机； 13.

5、若文法G定义的语言是无限集，则文法必然是 。a. 上下文无关的 b. 递归的 c. 二义性的 d. 无二义性的14. 文法 SaaS|abc 定义的语言是 。a. a2kbc|k>0 b. akbc|k>0 c. a2k-1bc|k>0 d. akakbc|k>015. 文法：G：SxSx | y所识别的语言是（）。a. xyxb. (xyx)*c. x*yx*d. xnyxn（n0）一答案：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；二、填空题：（

6、按照组卷方案，至少15道小题）1. 假设G是一个文法，a是由终结符和非终结符组成的串，S是文法的开始符号，如果S=>*a，则称a是 。2. 在赋值语句中，赋值号：=左右两边的变量名扮演着两种不同的角色，为了区分一个名字的这两种特征，我们把一个名字所代表的 称为该名的左值，把一个名字的 称为该名字的右值。3. 对于文法G，仅含终结符号的句型称为 。4. 设有文法GS，其部分产生式: EE+T | T TT*F | F F(E) | a 则VN = ,VT= 。 5. 由文法产生的 集合是文法产生的语言。6. Chomsky语法定义的3型文法又可以分为 。7. 一个上下文文法G的四个组成部分

7、分别是： 。8. 已知语言：anbnambm|n，m0，其语法定义为：G=(a，b，S，A，B，S，P)，其中P为： 。9. 已知某语言的语法定义为：G=(a,SS, P )，且P: SaS | e，则该语言为 。 10. 已知某语言为wcwR|wa，b*，其语法定义为G=(a，b，c，S，S，P)，其中P为： 。11. 所谓最右推导是指 。12. 已知文法G(Z): EET+|TTTF*|FFFP|P *a;S-|.q 八公山下PE|i 试写出其识别的一个句子：_。13. 文法GS：SaA|a， AaS为_型文法，其确定的语言的为：_ 。14. 在一棵语法树生长过程中的任何时刻，

8、就是一个句型。15. 我们说G=(VT，VN，S，P)是一个0型文法，如果它的每一个产生式ab是这样一种结构： 。二答案：1. 句型；2. 单元的地址（或者：单元、存储单元的地址），值（或者：单元的内容）3. 句子；4. VN=E，T，F，VT=+，*，(，)，a；5. 句子；6. 右线性文法和左线性文法；7. 开始符号，产生式集合，终结符集合，非终结符集合；8. SAB；AaAb|e；BaBb|e；9. an|n0；10. SaSa|bSb|e；11. 任何一步aÞb都是对a中的最右非终结符进行替换。12. iii*+；13. a2n+1|n0；14. 所有那些没有后代的末端结点从

9、左到右排列起来；15. a(VNVT)*且至少含有一个非终结符，而b(VNVT)*。三、判断题：（按照组卷方案，至少15道小题）1. 一棵语法树表示了一个句型所有的不同推导过程，包括最右推导和最左推导。 （ ）2. 可能有两个不同的文法G和G，期中一个是二义的而另一个是无二义的，但是却有L(G)L(G)。（ ）3. 变量既持有左值又持有右值，而常数和带有算符的表达式一般认为只持有右值。（ ）4. 文法G:SbA AaA|a定义的语言是所有以b开头的后跟至少一个a的字符串的集合。（ ）5. 设有文法G：SS*S | S+S | (S) | a该文法是二义的。（ ）6. 正则文法一定不是二义的。（

10、 ）7. 上下文无关文法可以产生语言L= anbnci | i>=1,n>=1 。（ ）8. 不存在任何正规文法能产生语言L=anbn | n>=1。（ ）9. 对于每一个左线性文法G1，都存在一个右线性文法G2，使得L(G1)=L(G2)。（ ）10. 正规文法产生的语言都可以用上下文无关文法来描述。（ ）11. 上下文无关文法比正规文法有更强的描述能力。（ ）12. 文法的二义性和语言的二义性在概念上是相同的，也就是说，对于某个语言，不可能存在两个以上的文法来描述它。（ ）13. 二义性是可以判定的，也就是说，可以编这么一个程序，输入该文法后，该程序能确切地给出该文法是否

11、二义的答案。（ ）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. 正规文法（左线性文法和右线性文法

12、）；四答案：1. 如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是是二义性文法。2. 设Ag是一个产生式，且a、bÎ(VTÈVN)*，若aAb=>agb，则称aAb直接推出agb；或者说，agb是aAb的一个直接推导。如果a1=>a2=>=>an，则称这个序列是从a1到an的一个推导。3. 设G是一个文法，S是它的开始符号。如果S=>*a，则称a是一个句型。仅含终结符的句型叫句子。文法G所产生的句子的全体叫文法G的语言，记为L(G)，L(G)=a| S=>*a，aVT*。4. 上下文无关文法G是一个四元式(VT，VN，S，

13、P)，其中：VT是一个非空有限集合，其中的每一个元素称为终结符；VN是一个非空有限集合，其中的每一个元素称为非终结符，VNVT=Æ；S是一个非终结符，称为开始符号；P是一个产生式有限集合，每个产生式的形式是Pa，其中PÎVN，a(VTÈVN)*。开始符号S至少必须在某个产生式的左部出现一次。5. 若文法G= (VT，VN，S，P)的任何产生式为AaB或Aa，其中，aÎVT*，A，BVN，则称G是右线性文法；若文法G= (VT，VN，S，P)的任何产生式为ABa或Aa，其中，aÎVT*，A，BVN，则称G是左线性文法；左线性文法和右线性文法均为正

14、规文法。五、简答题：（按照组卷方案，至少3道小题）1. 作为描述程序语言的上下文无关文法，对它有哪些限制？答：第一点：文法中不含任何下面形式的产生式：PP；第二点：每个非终结符P都必须有用处。也就是说，必须存在含P的句型；或者说，对P不存在永不终结的回路。2. 什么是二义性文法？从输入串abab来说明下面文法二义吗？SaSbS|bSaS|该文法产生的语言是什么？答：如果一个文法存在某个句子对应两棵以上不同的语法树，则称这个文法是二义的。例如输入串abab，它有两棵语法树如下： 所以，该文法是二义的。此文法产生的语言是：所有a的个数与b的个数相等的由a和b组成的字符串。3. 文法 GS为： SA

15、c|aB Aab Bbc 该文法是否为二义的？为什么？ 答：对于串 abc (1)S=>Ac=>abc (2)S=>aB=>abc 即存在两不同的最右推导。所以，该文法是二义的。 或者： 对输入字符串 abc，能构造两棵不同的语法树，所以它是二义的。4已知文法G=(A,B,C，a,b,c，P，A), P由以下产生式组成: AabcAaBbcBbbBBcCbccbCCbaCaaBaCaa此文法所表示的语言是什么？答：分析文法的规则：每使用一次BcCbcc，b、c的个数各增加一个；每使用一次aCaaB或aCaa, a的个数就增加一个；产生式BbbB、 bCCb起连接转换作用

16、。由于A是开始符号，由产生式Aabc推导得到终结符号串abc；由产生式AaBbc推导得到B后，每当使用产生式BbbB、BcCbcc、bCCb、aCaaB就会递归调用B一次，所产生的a、b、c的个数分别增加一个，因此推导所得的终结符号串为abc、aabbcc、aaabbbccc、所以文法描述的语言为 anbncn|n>0.5已知文法GZ:Z0U|1VU1Z|1V0Z|0（1）请写出此文法描述的只含有个符号的全部句子。（2）GZ产生的语言是什么？ （3）该文法在Chomsky文法分类中属于几型文法？答：（1）0101，0110，1010， 1001（2）分析GZ所推导出的句子的特点：由Z开始

17、的推导不外乎图1所示的四种情形。由Z推导出10或01后就终止或进入递归，而Z的每次递归将推导出相同的符号串：10或01。所以GZ产生的语言L(GZ)=x|x(10|01)+ (3)该文法属于3型文法。七、应用题：1. 试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else(else悬挂)文法的二义性：stmt if expr then stmt | matched-stmt matched-stmt if expr then matched-stmt else stmt | other expre考虑句子if e then if e then ot

18、her else if e then other else other，试说明此文法仍然是二义性的。答：1. 考虑句子if e then if e then other else if e then other else other它具有如下所示的两种分析树则上面给出的if-then-else文法仍是二义性的。2. 考虑文法Gbexpr：bexprbexpr or bterm | btermbtermbterm and bfactor | bfactorbfactornot bfactor| ( bexpr ) | true | false(a) 请指出此文法的终结符号、非终结符号和开始符号。

19、(b) 试对于句子not(true or false)构造一棵分析树。(c) 试说明此文法所产生的语言是全体布尔表达式。答：(a) 终结符号为：or, and, not, (, ), true, false非终结符号为：bexpr, bterm, bfactor开始符号为：bexpr(b) 句子not(true or false)的分析树为：(c) 用归纳法说明如下：(1) 不含运算的布尔表达式，常数true和false由此文法产生：bexpr => bterm => bfactor => truebexpr => bterm => bfactor => f

20、alse(2) 设结论对于少于n(n1)个运算的布尔表达式成立，即若be1和be2是含有少于n个运算的布尔表达式，则有：bexpr=>+be1,bexpr=>+be2。 (3) 对于含有n个运算的布尔表达式，可表示成下面三种形式：(a) (be1) or (be2)(b) (be1) and (be2)(c) not (be1)对于(a)：bexpr => bexpr or bterm=> bterm or bterm => bfactor or bterm=> (bexpr) or bterm =>+(be1) or bterm=> (be1)

21、 or bfactor => (be1) or (bexpr)=>+ (be1) or (be2)同理，有：Bexpr=>+ (be1) and (be2)Bexpr=>+ not (be1)综上所述，此文法所产生的语言是全体布尔表达式。3. 已知文法GS,其产生式为：S(S)| e（a）L(G)是什么？（b）对于(a)的结果，请给出证明。答：(a) 解：(b)证明：首先证明对推导次数进行归纳1):当推导次数为1时，使用产生式Se，此时左括号与右括号个数为02):假设推导次数为n时(a)成立,即: 则推导次数为n+1次时，多使用一次产生式S(S)即: 推导次数为n+1次

22、时(a)成立。根据(1)(2)可得： 其次证明对n进行归纳1):当n=0时,使用产生式Se 即可；2):假设当n=k时,结论成立，即，下面证n=k+1时结论成立。由，其推导过程如下：当n=k+1时，推导过程如下：故根据(1)(2)可得：根据1，2可知：4. 试构造生成下列语言的上下文无关文法：(1) anbnci | n1, i0 (2) w | wa,b+，且w中a的个数恰好比b多1 (3) w | wa,b+，且|a|b|2|a| 答：（1）把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：S ABA aAb|abB cB|（2）令S为开始符号，

23、产生的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. 已知文法GS:SABAaA|aBbB|b求该文法所定义的语言。答：从规则2可推出:a,aa,aaa,从规则3可推出:b,bb,bbb,再从规则1可推出句子：ab, aab, aabb, aaab, abbb,即，从S出发可推出多个a后跟多个b的字符串，且a的个数与b的个数不尽

24、相同。故： L(G)=ambn| m,n16. 考虑下面上下文无关文法GS： SSS*|SS+|a (1) 对于符号串aa+a*分别给出最左推导和最右推导过程，并为该串构造语法树。 (2)GS的语言是什么？ 答：(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 |

25、 ND D 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 9 (1) G的语言L（G）是什么？(2) 给出句子0127、34和568的最左推导和最右推导。答：（1）N NÞNDÞNDDÞNDDDÞNDDDDÞDDDL(G)=d(n+1)|n0, d0, 1, , 9允许以0开头的自然数（十进制无符号整数）；（2）0127最左推导：NÞNDÞNDDÞNDDDÞDDDDÞ0DDDÞ01DDÞ012DÞ01270127最右推导：NÞND&

26、#222;N7ÞND7ÞN27ÞND27ÞN127ÞD127Þ01278 写一个文法，使其语言是奇数集，且每个奇数不以0开头。答：（首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。分别用3个非终结符来产生句子的第1位、中间部分和最后一位。引入几个非终结符，其中，一个用作

27、产生句子的开头，可以是19之间的数，不包括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)：SMF5F50MMDNDN0N12345678910证明下面的文法是二义的：SiSeSiSi答：（根据文法的二义性的定义，如果要证明该文法是二义的，必须找到一个句子，使得该句子具有两个不同的最右推导或两个不同的语法树。我们首先