丽水学院《编译原理》期中独立作业.docVIP

PAGE PAGE 2 《编译原理》期中独立作业 班级： 学号： 姓名： 成绩 一、填空题（20分） 1、扫描器的任务是从 源程序 中识别出一个个 字符 。2、最右推导是指： 对于一个推导序列中的每一直接推导，被替换的总是当前符号串中的最右非终结符号。 3语法分析最常用的两类方法是 自顶向下 和 自底下上 分析法。4、一个上下文无关文法所含四个组成部分是 非终结符集 、 产生式集 、一组终结符号，一个开始符号。 5、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 有二义性的 。6、对于文法G，仅含终结符号的句型称为 G产生的句子 。 7、产生式是用于定义 语言中的语法范畴 的一种书写规则 二、名词解释（20分） 1、遍 对源程序或源程序中间表示的一次扫描，每一遍读入一个文件，执行一个或几个阶段的编译操作，并输出源程序的一个中间表示 2、语法分析 在词法分析的基础上将单词序列组合成各类语法短语 3、短语若 Z加推出xAy 加推出xay 任一子树的树叶全体(具有共同祖先的叶节点符号串)皆为短语。 4、中间代码优化 5、句柄一个句型的最左简单短语称为该句型的句柄。 三、简答题 1、已知文法G(S) S→a|∧|(T)T→T，S|S写出句子((a，a)，a)的规范推导过程 (10分) 解：句型　　　　　归约规则　　　　　句柄 　　　　　　((a，a)，a)　　S→a　　　　　　　a 　　　　　　((S，a)，a)　　T→S　　　　　　　S 　　　　　　((T，a)，a)　　S→a　　　　　　　a 　　　　　　((T，S)，a)　　T→T，S　　　　　 T，S 　　　　　　((S)，a)　　　 T→S　　　　　　　S 　　　　　　((T)，a)　　　 S→S(T)　　　 　　(T) 　　　　　　(S，a)　　　 　T→S　　　　　　　S 　　　　　　(T，a)　　　 　S→a　　　　　　　a 　　　　　　(T，S)　　　 　T→T，S　　　　　 T，S 　　　　　　 (T)　　　 　　 S→(T)　　　　　　(T) 　　 　　　 S　　　　　　　　　　　　 2、已知文法G(E)（10分） E→T|E＋TT→F|T * FF→(E)|i(1) 给出句型(T * F＋i)的语法树；(2) 给出句型(T * F＋i)的短语、句柄。 句型T*F+I的短语为i、T*F、T*F+i; 简单短语为i、T*F;句柄为第一个T*f。 3、设Σ={x,y},Σ上的正规表达式e=yxy*(xy|yx)x*y*,请构造一个NDFA M，使L（M）=L（e）(10分) 4、设文法G(S)：(15分) S→A A→BH H →iBH|ε B →CK K →+CK|ε C→)A*|( 计算每个非终结符的FIRST和FOLLOW；构造LL(1)分析表。 5、设文法G[E] E→E+T|E-T|T T→T*F|T/F|F F→F↑P|P P→（E）|I 请构造该文法的算符优先矩阵（15分）