[03_04)]《编译原理》00本科班A卷(答案).docVIP

——————————————装————————————————订————————————————线————————————————————————————————2003 ——————————————装————————————————订————————————————线———————————————————————————————— 韶关学院计算机系《编译原理》期末考试试卷（A卷答案） 年级：00 专业：计算机科学技术 班级： 学号： 姓名： 题号 一 二 三 四 五 总分 签名 得分 注：1、共120分钟，总分100分 。 2、此试卷适用专业：计算机本科 一 得 分 阅卷教师 判断题：（每小题1分，共5分）? ? 每个文法都能改写为LL(1)文。 （×）2、符号表是上下文语义的合法性检查的依据之一。 （√）3、函数backpatch(p,t)的功能是指将字符p后退t格。 （×）4、算符优先关系表不一定存在对应的优先函。 （√）5、“把所有语言中的符号都组织在一张符号表中”是用得最多的一种对符号表的总体组织方法中。 （×） 二 得 分 阅卷教师 填空题(每空1分，共20分)1、编译过程一般分为：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段。2、词法分析的任务是：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描，从而识别出一个个单词。3、语法分析最常用的两类方法是 自顶向下分析法 和自底向上分析法。4、一个上下文无关文法包含非终结符集、终结符集、产生式集和开始符号四个组成部分是。5、在有穷自动机中，两类状态s和t等价的条件是：一致性条件和蔓延性条件。6、程序设计语言的语义分为：静态语义和动态语义两类。7、乔姆斯把文法分成　0型文法（短语文法）、1型文法（上下文有关文法）、2型文法（上下文无关文法）和3型文法（正规文法）四种类型。 三 得 分 阅卷教师 三、名词解释(每题2分，共10分)1、句柄：令S是文法G的开始符，如果有S??A?且A??则称?是句型???相对于非终结符A的直接短语，其中最左直接短语为句柄。2、规范推导：如果在推导的任何一步???，其中?，?是句型，都是对?中的最右非终结符进行替换，则称这种推导为最右推导，也称为规范推导。?3、语法分析：是编译程序的第二个阶段，其任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”、“语句”、“表达式”等。4、素短语：至少包含一个终结符，且不包含其它短语的短语。5、句型：设G?S?是一文法，如果符号串ｘ是从识别号推导出来的，即有S?ｘ，则称ｘ是文法G?S?的句型。 ? 四 得 分 阅卷教师 ＊四、简述题(每题5分，共25分)1、已知文法G：E→T | E+T | E-T, T→F | T*F | T/F, F→(E) | i 试给出下述表达式的推导及语法树。 ①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) ①和②的语法树如下： EE+TT*FTFFiii①的语法树FTF E E + T T * F T F F i i i ①的语法树 F T F T E T E T * F ( E ) F i i i ②的语法树 + ——————————————装————————————————订————————————————线———————————————————————————————— G[S]: S?AB, A?aAb | ab | ? , B?aBb | ab | ? 3、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。 解：逆波兰:abc*+ab+/d- 三元式:① (* b , c ) ②