北方工业大学《编译原理》期中试卷2017

1、北方工业大学试卷答案 第 1 页 共 7 页 北方工业大学北方工业大学 编译原理编译原理课程课程期中期中试卷试卷答案答案 a 卷卷 2017 年年春春季季学期学期 开课学院：开课学院： 计算机计算机 考试方式：闭卷考试方式：闭卷 考试时间：考试时间：95 分钟分钟 班班级级 姓名姓名 学号学号 题题 号号 一一 二二 三三 四四 五五 六六 七七 八八 九九 十十 总总 分分 得得 分分 阅卷人阅卷人 一、一、 判断题判断题（每个小题每个小题 1 分分，共，共 10 分分） 1. 汇编程序与编译程序都是翻译程序，主要区别是加工对象的不同。 （ ） 2. 解释程序同时处理源程序和数据。 （ ）

2、3. 编译各阶段都涉及到构造、查找或更新有关的表格。 （ ） 4. 上下文有关文法所定义的语法范畴是完全独立于这种范畴可能出现的环境的。 （ ） 5. 乔姆斯基把文法分为 0 型、1 型、2 型和 3 型，0 型文法的描述能力弱于 1型。 （ ） 6. 词法分析器不断地从输入缓冲区读入字符串，并进行识别。 （ ） 7. 超前搜索是为了得到某一个单词符号的确切性质，需要超前扫描若干个字符。 （ ） 8. 一张转换图只包含有限个状态，其中有一个为初态，一个为终态。 （ ） 9. lr 分析法不是规范归约方法。 （ ） 10. 程序设计语言的单词都能用正规式来定义。 （ ） 解： 1. 2. 3.

3、4. 5. 6. 7. 8. 9. 10. 二、二、 选择题（每个选择题（每个小题小题 1 分，共分，共 20 分）分） 1. 自下而上语法分析的工作原理是_。 a. 移进-推导法 b. 最左推导法 c. 移进-规约法 d. 推导-规约法 2. lr 分析法每次都是对当前句型的_进行规约。 a. 素短语 b. 句柄 c.短语 d. 最左素短语 序号 订 线 装 北方工业大学试卷答案 第 2 页 共 7 页 3. 如果文法 g 是无二义的，则对于它的任何句子_。 a. 最左推导和最右推导对应的语法树必定相同 b. 最左推导和最右推导对应的语法树可能不同 c. 最左推导和最右推导必定相同 d. 可

4、能存在两个不同的最左推导，但它们对应的语法树相同 4. 消除间接左递归时，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是_。 a. 等价的 b. 不等价的 c. 形式上不一样 d. 形式上完全一样 5. 语法制导翻译法直观上说就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时_这些语义规则。 a. 考虑 b. 不考虑 c. 不执行 d. 执行 6. 若一个文法是递归的，则它产生的句子个数是_。 a. 有限个 b. 无穷个 c. 可能有限个 d. 以上均不对 7. 下面哪种不是自下而上的语法分析方法_。 a. slr(1) b. lr(1) c. ll

5、(1) d. 算符优先分析法 8. 一个上下文无关文法消除了左递归，提取了公共左因子后是满足 ll(1) 文法的 _。 a. 没有关系 b. 充分必要条件 c. 必要条件 d. 充分条件 9. 正规式 m1和 m2等价是指_。 a. m1和 m2的有向边条数相等 b. m1和 m2的状态数相等 c. m1和 m2的状态数和有向边条数相等 d. m1和 m2所识别的语言集相等 10. 字母表a,b上以 aa 开头任何符号串的集合，可用正规式表示为_。 a. aa(a*|b*) b. a、b、 c 均不正确 c. aa(a|b)* d. (a|b)*aa 11. 文法 g 所描述的语言是_的集合。

6、 a. 文法 g 的字母表 的闭包 *中的所有符号串 b. 由文法的开始符号推出的所有终结符号串 c. 由文法的开始符号推出的所有符号串 d. 文法 g 的字母表 中所有符号组成的符号串 12. 经过编译所得到的目标程序是_。 a. 四元式序列 b. 间接三元式序列 c. 三元式序列 d. 机器语言程序或汇编语言程序 13. _和代码优化部分不是每个编译程序都必需的。 a语法分析 b中间代码生成 c词法分析 d目标代码生成 北方工业大学试卷答案 第 3 页 共 7 页 14. 不可能是目标代码的是_。 a中间代码 b可重定位的指令代码 c绝对指令代码 d汇编指令代码 15. 语言是_。 a句子

7、的集合 b产生式的集合 c符号串的集合 d句型的集合 16. 一个句型的最左素短语是指处于句型最左边的_。 a非终结符号 b短语 c素短语 d直接短语 17. 自上而下分析法是从文法开始符号出发，反复使用各种产生式，寻找匹配的 _。 a终结符号 b规约 c推导 d非终结符号 18. 自下而上分析的核心问题是识别_。 a最左素短语 b可归约串 c句柄 d非终结符号 19. 规范归约是一个_的逆过程。 a规范句型 b最左归约 c最左推导 d规范推导 20. 在正规式中运算符的优先级从高到低的顺序是_。 a ，*，| b |， ，*， c*， ， | d*，| ， 解： 1. c 2. b 3. a

8、 4. a 5. d 6. b 7. c 8. d 9. d 10. c 11. b 12.d 13.b 14. a 15. a 16. c 17. c 18. b 19. d 20. c 三、三、填填 空题（每空空题（每空 1 分，共分，共 10 分）分） 1. 有些编译程序对优化没有要求， 阶段即可省去。 2. 是语言中具有独立意义的最基本结构。 3. 语法分析的描述工具是 。 4. 自下而上分析法基本思想是从输入串开始，逐步进行 ，直到文法的开始符号。即从树末端开始，构造语法树。 5. 消除左递归前后，文法的 不变。 6. 由源程序的语法结构所驱动的处理办法就是 。 7. 项目 sb.b

9、b 是 。 8. 综合属性是 传递信息。 9. 仅仅使用综合属性的属性文法称为 文法。 10. lr(k)分析法中的 r 是指 对应的最左归约。 解：1. 优化 2. 单词符号 3. 上下文无关文法 4. 归约 5. 开始符号 6. 语法制导翻译法 7. 待约项目 8. 自下而上 9. s-属性 10. 最右推导 四、四、简答题（简答题（60 分）分） 北方工业大学试卷答案 第 4 页 共 7 页 1. 请给出一个上下文无关文法，使其语言是能被 5 整除且不以 0 开头的无符号整数的集合。 （5 分） 解：文法 gs为： smf| 5 f5 | 0 n1 | 2 | 3 | 4 | 5 | 6

10、 | 7 | 8 | 9 dn | 0 mmd | n 2. 请给出一个上下文无关文法 g， 使得 l(g)=anbmcmdn | n0, m1 （3 分） 解：文法 gs为： sasd| a abac | bc 3. 语言 l 是所有由偶数个 0 和偶数个 1 组成的句子的集合，请给出定义 l 的右线性正规文法。 （5 分） 解：构造状态转换图为： l 的右线性正规文法为： 4. 请证明下面的文法 ge是二义文法。 eeit | t t t+f | if | f fe* | ( （3 分） 北方工业大学试卷答案 第 5 页 共 7 页 5. 请构造正规式(a|b)*abb 相应的最小化的 d

11、fa。 （12 分） 北方工业大学试卷答案 第 6 页 共 7 页 6. 对于文法 gs： ss*atat*at t+at+a （1）请给出句型 a+a*a+at 的最左推导，并给出语法树； （2）给出上述句型的所有短语、直接短语、句柄和最左素短语。 （10 分） 7. 对于文法 gs： s iets | ietses | a e b （1）请给出消除 gs的左递归和回溯后的文法； （2）计算消除 gs左递归和回溯后文法的每个非终结符的 first 和 follow； （3）构造它的预测分析表；证明这个文法是否是 ll(1)文法； （4）请改造文法，并为之构造满足 ll(1)文法的 ll(1)

12、分析表。 （12 分） 解：（1）gs不存在左递归，存在回溯。提取公共左因子，消除 gs的左递归和回溯后的文法 gs : s ietss | a s es | e b （2） 计算消除 gs左递归和回溯后文法 gs的每个非终结符的 first 和 follow； first(s)=i, a follow(s)=e, # first(s)=e, follow(s)=e, # first(e)=b follow(e) =t （3）构造它的预测分析表为： 北方工业大学试卷答案 第 7 页 共 7 页 a b e i t # s sa sictss s s ses s e eb 由于 first(es)follow(s)=ee, #=e ，所以证明了 gs不是 ll(1)文法。 （4） 根据最近匹配原则， 在嵌套 if-then-else 语句中， else 和 if 按照最近匹配原则配对，即相距最近且还没有配对的一对 if 和 else 首先配对。 改造后的文法 gs