编译原理试卷.doc

河北科技师范学院装订线系（部）班 级学 号姓 名2010 2011学年第二学期 计算机科学与技术08专业 编译原理 试卷（A）卷 题 号一二三四五合计得 分阅卷人 得 分阅卷人一、填空题（每空1分，10个空，共10分，请将正确的答案填写在题中的横线上）1. 编译程序从源程序执行的角度不同，可分为 和 的翻译程序。2. 设A=ab,c,d,则A2= 。3. 设字母表A=ab,x,y，字母表A上的符号串=abxyabxy，则|= 。4. BNF表示法是目前最常用的 表示方法5. 如果确定的有限自动机M既没有无关状态，有没有彼此等价的状态，则称确定的有限自动机M是 6.词法分析程序的功能是：读入字符串形式的源程序；识别具有独立意义的最小语法单位 。7. LL(1)分析法是一种 (填自上而下还是自下而上)分析法。8. 常见的中间语言表示形式有逆波兰表示、N-元式表示、 。9. 存储分配的基本单元是过程的 。第 12 页 共 12 页得 分阅卷人二、选择题（每题2分，10题，共20分）（在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填在题后的括号内。错选、多选或未选均无分。）1. 编译程序是一种常用的_软件（ ）A. 应用 B. 系统 C. 工具 D. 测试2. 语言的核心是由语法和语义两部分构成，下列叙述正确的是（ ） A. 语法是语言的形式，语义是语言的内容 B. 语法是语言的内容，语义是语言的形式 C. 语言的实质是以语义为媒介来说明语言的 D. 语言是具有独立意义的单词根据一定的词法规则构成的表达一定意义的句子组成的。 3. 语言L=abna的上下文无关文法描述是 （ ）A. S-aBa B-bB| B. S-aSaC. S-aSb|Sb| D. S-AB B-bBa|ba A-Aa|4. 一个语言的文法是 （ ）A惟一的 B不惟一的 C. 个数有限的 D. 无限的5. 下面哪个不是预处理程序完成的功能是（ ） A. 滤掉源程序中的注释 B. 查找源程序中无用字符 C. 进行宏替换 D. 实现文件包含的嵌入和条件编译的嵌入6. 下列文法中 是LL(1)文法（ ） A. SaSb|ab B. SaS|b C. Sab|Sab D. SaS|a7. 自下而上语法分析的主要分析动作是（ ） A. 移进 B. 推导 C. 规约 D. 分析8. 句子(a+b)*(c+d)的逆波兰表示为（ ）Aa+bc+d* B. abc*+d+C. ab+cd+* D. A、B、C都不正确9. 有关静态存储分配策略的描述正确的是（ ）A. 静态存储分配是指在编译时进行的存储分配B. 静态存储分配适用于允许递归过程或递归调用C. 静态存储分配的特点是在编译时不能确定目标程序运行中所需的数据空间的大小。D. 静态存储分配产生的数据区称为固定数据区10. 将下面代码a=x+y+cb=x+y+d优化为t=x+ya=t+cb=t+d采用的优化技术为（ ）A. 公共子表达式删除 B. 死代码删除C. 常量合并与传播 D. 无用赋值的删除得 分阅卷人三、判断题（每题2分，10题，共20分）（对的在后面的括号内打“”号 错误的打“”）1. 包含左递归的文法肯定不能直接用LL分析法来分析（ ）2. 最右推导是最右规约的逆过程，最左推导是最左规约的逆过程（ ）3. 程序基本块是指一个仅有一个入口和一个出口的子程序（ ）4. 高级语言编译程序常用的语法分析器中，递归下降分析法属于自顶向下分析方法（ ）5. “遍”是指对源程序或源程序的中间形式从头到尾扫描一遍，并做相应的加工处理（ ）6逆波兰表示法表示表达式时无需使用括号（ ）7.词法分析器输出结果中的单词属性名是进行语法分析的文法的终结符 （ ）8.局部优化中使用的DAG图反映了基本块之间的关系（ ）9语法分析识别出来的是具有独立意义的最小语法范畴（ ）10动态存储分配是指编译程序运行时才能确定其全部数据空间的大小 （ ）得 分阅卷人四、简答题（共15分）（1题8分，2题2分.3题5分）1. 设有文法： SaSbS|bSaS|(1)判断符号串ababba是否为文法G(S)的句子，如果是画出其分析树。(2)给出G(S)的元语言符号集、文法符号集、终结符集、非终结符集2. 设有文法 SPab | bP Pb | 求First(S) 和Follow(P) 3. 设有确定的有限自动机M:（0,1,2,3,a,b,，0，3）（0，a）=1 （0，b）=2（1，a）=3 （1，b）=2（2，a）=1 （2，b）=3（3，a）=3 （3，b）=3画出其状态转换图和状态转换矩阵得 分阅卷人五、分析题（共35分）（第1、2题10分，3题15分）1. 给定非确定的有限自动机M如下图所示4f35621ieeeeaaaabbbb将M确定化，并画出确定化后的状态转换图（要求：写出步骤）2. 将下面程序划分成基本块并作出其程序控制流图（1）read c（2）A = 0（3）B = 1（4）L1：A= A+b（5）if B= C goto L2（6）B = B+1（7）goto L1（8）L2：write A（9）halt3 设有文法GS: (1) S E (2) E aA (3) E bB (4) A cA (5) A d (6) B cB (7) B d其LR(0)分析表如下状态ActionGotoabcd#EAB0s2s411acc2s6s833r2r2r2r2