编译原理试题(网工最终).doc

1 填空题。1. 将源语言代码等价转换为目标代码的软件统称为（编译器）。2. 上下文无关文法由（终结符）（非终结符）（开始符号）和（产生式）组成。3. 动态存储分配包括（队列式）存储分配和堆栈式存储分配两种形式。4. 正规表达式表示的语言称为（正规集）。5. 产生相同语言的两个不同的文法称为（等价）文法。6. 语法分析器的输入是（记号流），输出是（语法分析树）。7. 语法分析最常用的两类方法是（自底向上分析）和（自顶向下分析）。8. 句型的最左直接短语称为该句句型的（句柄）。9. X：-（a+b）/(c-d）的后缀式是（ab+cd-/-）。10. 文法的符号的属性有综合属性和（继承属性）。11. 描述语法分析树中属性实例求值顺序的图称为（依赖图）。设二维数组按行存放，每个元素占用4个字节，则数组a1.15.1.20某个元素ai,j的地址计算公式为（a+(i-1)*20+(j-1)）*4 ）。12. 常用的中间代码表示形式包括后缀式、（静态单赋值）、（三地址代码）和（DAG图）。二、大选题。1. 程序中各个语法成分含义的描述称为（C）A .词法 B .语法 C .语义 D .语用2. 正规式M1和M2等价是指（A）A. 两者识别的语言集相等 B.两者的又向弧条数相等C.两者的状态数相等 D.两者的状态数和有向弧数相等3. （D）不是编译器的组成部分。A 扫描器B分析器 C优化器 D链接器4. 中间代码生成时所依据的是（C）规则。A语法B词法C语义D等价代换5. LL（K）分析的方法中第二个L表示(B).A自左向右分析B每次最左推导C自右向左分析D每次最左归约6. A-a*是（B）项目。A归约B移进C待约D接受7. 语法分析中FIRST，FORLOW集合均是（B）。A非终结符集B终结符集C字母表D状态集8. 若项目集Ik含有A-a,则在状态K时，仅当面临的输入符号属于FOLLOW（A）时，才采取A-a动作的一定是（D）。A 。LALR B 。LR（0）C 。LR（1）D 。SLR（1）9. 语义分析中S-属性文法（A）。A只涉及综合属性 B只涉及集成属性C既有综合属性又有集成属性 D无综合属性和集成属性10. 编译器产生的目标汇编代码由（A）处理生成可重定位代码。A汇编器B loader Clink-editor D 交叉汇编器3 简答题。1. 描述编译器的各个组成部分及每个部分的主要任务。词法分析器：读入组成源程序的字符流，并且将它们组织成为有意义的词素的序列。语法分析功能：使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示，该中间表示给出了词法分析产生的词法单元流的语法结构。语义分析：使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。它同时也收集类型信息，并把这些信息存放在语法树或字符表中，以便在随后的中间代码生成过程中使用；中间代码生成：为源程序产生更低级的显示中间表示；代码优化：改进中间代码，以便产生较好的目标代码；代码生成：代码生成取源程序的一种中间表示作为输入并把它映射到一种目标语言；符号表：符号表是为每个变量名字保存一个记录的数据结构，记录的域是该名字的属性。2.说明预测分析程序的工作过程（分析表和栈的结合产生的动作）1）构造文法2）改造文法：消除二义性、消除左递归、提取左因子3）求每个变量的FIRST集和变量的FOLLOW集，从而求得每个候选式的SELECT集4）检查是不是LL(1)文法5）构造预测分析表6） 实现预测分析器3说明语法制导定义SDD的组成部分。上下文无关文法和属性及规则4.说明活动记录的作用及其组成。实参返回值控制链：指向调用者的活动记录访问链：用来访问存于其它活动记录中的非局部数据保存的机器状态局部数据临时数据4 词法分析题。给定正规集：以0、1构成的所有以1开头，以101结尾的字符串，完成下列操作：（1） 给出对应的正规式。（2） 构造对应的NFA。（3） 用子集法将上述NFA转化为DFA。（4） 将上述DFA化简。（5） 5 语法分析题。1. 给定文法G为： S-a|(T) T-T,S|S给出句子（a,（a,a）和(a,a),(a),a)的最左推导。