[03_04(2)]《编译原理》00本科班a卷(答案)

《[03_04(2)]《编译原理》00本科班a卷(答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、——————————————装————————————————订————————————————线————————————————————————————————2003－2004学年第二学期韶关学院计算机系《编译原理》期末考试试卷（A卷答案）年级：00专业：计算机科学技术班级：学号：姓名：题号一二三四五总分签名得分注：1、共120分钟，总分100分。2、此试卷适用专业：计算机本科一得分阅卷教师一、判断题：（每小题1分，共5分）*1、每个文法都能改写为LL(1)文。（×）2、符号表是上下文语义的合法性检查的依据之一。（√）3、函

2、数backpatch(p,t)的功能是指将字符p后退t格。（×）4、算符优先关系表不一定存在对应的优先函。（√）5、“把所有语言中的符号都组织在一张符号表中”是用得最多的一种对符号表的总体组织方法中。（×）二得分阅卷教师二、填空题(每空1分，共20分)1、编译过程一般分为：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段。2、词法分析的任务是：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描，从而识别出一个个单词。3、语法分析最常用的两类方法是自顶向下分析法和自底向上分析法。4、一个上

3、下文无关文法包含非终结符集、终结符集、产生式集和开始符号四个组成部分是。5、在有穷自动机中，两类状态s和t等价的条件是：一致性条件和蔓延性条件。6、程序设计语言的语义分为：静态语义和动态语义两类。7、乔姆斯把文法分成　0型文法（短语文法）、1型文法（上下文有关文法）、2型文法（上下文无关文法）和3型文法（正规文法）四种类型。10三得分阅卷教师三、名词解释(每题2分，共10分)1、句柄：令S是文法G的开始符，如果有SÞaAd且AÞb则称b是句型abd相对于非终结符A的直接短语，其中最左直接短语为句柄。2、规范推导：如果在推导的任何

4、一步aÞb，其中a，b是句型，都是对a中的最右非终结符进行替换，则称这种推导为最右推导，也称为规范推导。*3、语法分析：是编译程序的第二个阶段，其任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”、“语句”、“表达式”等。4、素短语：至少包含一个终结符，且不包含其它短语的短语。5、句型：设G[S]是一文法，如果符号串ｘ是从识别号推导出来的，即有SÞｘ，则称ｘ是文法G[S]的句型。四得分阅卷教师＊四、简述题(每题5分，共25分)1、已知文法G：E→T

5、E+T

6、E-T,T→F

7、T*F

8、T/F,F→(E)

9、i试给出下述表

10、达式的推导及语法树。①i+i*i②i*(i+i)解：①推导过程如下：EÞE+TÞE+T*FÞE+T*iÞE+F*iÞE+i*IÞT+i*IÞF+i*iÞi+i*i②推导过程如下：EÞTÞT*FÞT*(E)ÞT*(E+T)ÞT*(E+F)ÞT*(E+i)ÞT*(T+i)ÞT*(F+i)ÞT*(i+i)ÞF*(i+i)Þi*(i+i)①和②的语法树如下：10EE+TT*FTFFiii①的语法树FTFTETET*F(E)Fiii②的语法树+——————————————装————————————————订————————————————

11、线————————————————————————————————2、给出语言{anbnambm

12、n,m≥0}的上下无关文法。解：上下无关文法如下：G[S]:S®AB,A®aAb

13、ab

14、e,B®aBb

15、ab

16、e3、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。解：逆波兰:abc*+ab+/d-三元式:①(*b,c)②(+a,①)③(+a,b)④(/②,③)⑤(-④,d)4、文法G[N]为：N→D

17、NDD→0

18、1

19、2

20、3

21、4

22、5

23、6

24、7

25、8

26、9G[N]的语言是什么？解：G[N]的语言是:{(0

27、1

28、2

29、3

30、4

31、

32、5

33、6

34、7

35、8

36、9)n

37、n≥1}即为非负整数。105、构造正规式b((ab)*

38、bb)*ab的NFA。解：a,beebbebae4235106a五得分阅卷教师五、综合题(每题10分，共40分)1、已知文法G[S]：S→MH

39、aH→LSo

40、eK→dML

41、eL→eHfM→K

42、bLM判断G是否是LL(1)文法，如果是，构造LL(1)分析表。解：（1）求出能推出e的非结符为：S、H、K、M（2）计算FIRST集FIRST(S)=FIRST(MH)U｛a｝={a,b,d,e,e}FIRST(H)=FIRST(L)U｛e｝={e,e}FIR

43、ST(K)={d,e}FIRST(L)={e}FIRST(M)=FIRST(K)U｛b｝={b,d,e}（3）计算FOLLOW集FOLLOW(S)={o,#}FOLLOW(H)=FOLLOW(S)U｛f｝={f,o,#}FOLLOW(K)=FOLLOW(M)={