编译原理作业集-第二章

《编译原理作业集-第二章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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Î(VT∪VN)*，则称a是一个。a.句子b.句型c.推导d.语言4.一个数据类型通常包括的三种要素中，没有下面的。a.用于区别这种类型的数据对象的属性；b.这种类型的数据对象可以具有的值；c.对这种类型的数据对象的内存分配；d.可以作用于这种类型的数据对象的操作；5.Chomsky把

3、文法分成四种类型，其中，也称正规文法a.0型b.1型c.2型d.3型6.语言的词法规则一般用Chomsky的型文法来描述：a.0b.1c.2d.37.文法S→(L)

4、aL→L，S

5、S中，下面是该文法中的终结符号。a.Sb.，c.Ld.

6、8.文法G所描述的语言是的集合。a.文法G的字母表å中的所有符号组成的符号串；b.文法G的字母表å的闭包å*中的所有符号串；c.文法G的识别符号推出的所有符号串；d.文法G的识别符号推出的所有终结符号串；9.语言L={aca

7、aÎ(a

8、b)*}，该语言是_____________语言。a.3型语言，b.2型语言，c.1型语言，d.0型语言

9、10.设有文法G：I→I1

10、I0

11、Ia

12、Ic

13、a

14、b

15、c

16、下面符号串中不是该文法的句子是：a.ab0，b.a0c01，c.aaa，d.bc1011.给定文法A→bA

17、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

18、abc定义的语言是。a.

19、{a2kbc

20、k>0}b.{akbc

21、k>0}c.{a2k-1bc

22、k>0}d.{akakbc

23、k>0}15.文法：G：S→xSx

24、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是一个文法，a是由终结符和非终结符组成的串，S是文法的开始符号，如果S=>*a，则称a是。2.在赋值语句中，赋值号‘：=’左右两边的变量名扮演着两种不同的角色

25、，为了区分一个名字的这两种特征，我们把一个名字所代表的称为该名的左值，把一个名字的称为该名字的右值。3.对于文法G，仅含终结符号的句型称为。4.设有文法G[S]，其部分产生式:E→E+T

26、TT→T*F

27、FF→(E)

28、a则VN={},VT={}。5.由文法产生的集合是文法产生的语言。6.Chomsky语法定义的3型文法又可以分为。7.一个上下文文法G的四个组成部分分别是：。8.已知语言：{anbnambm

29、n，m≥0}，其语法定义为：G=({a，b}，{S，A，B}，S，P)，其中P为：。9.已知某语言的语法定义为：G=({a},{S}S,P)，且P:S→aS

30、e，则该语

31、言为。10.已知某语言为{wcwR

32、w∈{a，b}*}，其语法定义为G=({a，b，c}，{S}，S，P)，其中P为：。11.所谓最右推导是指。12.已知文法G(Z):E→ET+

33、TT→TF*

34、FF→FP↑

35、P*a;S-

36、.q[八公山下P→E

37、i试写出其识别的一个句子：_____________________。13.文法G[S]：S→aA

38、a， A→aS为_______型文法，其确定的语言的为：_______。14.在一棵语法树生长过程中的任何时刻，就是一个句型。15.我们说G=(VT，VN，S，P)是一个0型文法，如果它的每一个产生式