期末复习——填空题.doc

填空题第一章1解释程序和编译程序的区别在于（是否生成目标代码）。2编译过程通常可分为5个阶段，分别是词法分析、语法分析、语义分析与中间代码产生、代码优化和目标代码生成。3编译程序工作过程中，第一阶段输入是（源程序），最后阶段的输出为（目标代码）程序。4源程序中的错误通常分为（语法错误）和（语义错误）两大类。5（编译程序）是将源程序翻译成目标程序的程序。6高级程序设计语言的翻译主要有两种方式： 编译 和 解释 ，二者的根本区别在于 是否生成目标代码 。7.编译过程的各阶段都需要进行（表格）管理和（ 出错）处理，所以在典型编译程序框图中，各阶段对应的程序都和上述管理或处理操作程序相联系。8.若将A语言的源程序翻译成B语言的程序，翻译的实现语言为Y语言，则称A语言是翻译的 源语言 ,B语言是 目标语言 ，Y语言是 宿主语言 9.编译程序从源语言类型或实现机制不同角度一般可分为 汇编程序 、 编译程序 、 解释程序 10. 构造一个编译程序的三要素是 源语言 、 目标语言与目标机 和 编译方法与工具 第二章1、产生式是用于定义_语法范畴_的一种书写规则。2一个上下文无关文法G包括四个部分：（终结符号）、（非终结符号）、（开始符号）和一组（产生式）。3若，则称这个序列是从到的一个（推导）。4对于正规文法G和有限自动机M，若L(G)=L(M)，则称G和M是（等价）的。5若两个正规式所表示的正规集相等，则认为二者是（等价）的。6. 假设GS是一个文法,如有Sx,则称x是该文法G的（句型）；文法G产生的（句子）的全体称为该文法所描述的语言。7.用四元组G =（VN，VT，P，S）表示文法，则其元素VN表示（非终结符 ）集；元素VT表示（ 终结符）集；元素P表示规则集；元素S表示开始符号，它必须是一个（非终结）符号.8. 规范推导是指 最右推导 ，其逆过程即 最左规约 ，称为规范归约。 9所谓最右推导是指任何一步都是对最右非终结符进行替换 。10设G是一个给定的文法，S是文法的开始符号，如果S-x( 其中 xVT*), 则称 x是文法的一个_句子_。 11.语言的核心皆由 语法 和 语义 两部分构成，其中 语法 是语言的形式， 语义 是语言的内容。语言的实质是以 语法 为媒介来说明语义。12.设有字母表=xy,a,b,字母表上的符号串=xyabbaxyaa，则|= 8 。13. 设有字母表=0,1上的符号串集合为A=01，0，101，则A2= 0101,010,01101,001,00,0101,10101,1010,10110114. 目前最常用的文法表示方法为 BNF 表示法。15文法G所产生的句子的全体是文法G所定义的（语言）。16若一个文法存在某个句子对应的两棵不同的语法树，则称这个文法是（二义文法）。17设文法G的开始符号为S，如果则称是L(G)的一个（句型）。18. 设有字母表=a,bb,c,字母表上的符号串=abbc、，则|3|= 9 19. 一个确定有穷自动机可以通过消除 无关状态 和合并等价状态而转换成一个最小的与之等价的有穷自动机。20. Chomsky把文法分为四种形式，它们分别是0型文法、1型文法、2型文法和 3型文法（正则文法） 第三章1、扫描器的任务是从_源程序_中识别出一个个_单词符号_。 2扫描器是_词法分析器_，它接受输入的_源程序_，对源程序进行_词法分析_并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。3词法分析基于_正则_文法进行，即识别的单词是该类文法的句子。 4. 单词 语言中具有独立意义的最小语法单位。5.属性字式扫描器对源程序中各单词处理后的输出形式，其中，单词 属性 表示单词的类别6. 词法分析的单词可以分为常量、运算符、界限符、关键字和 标识符 7. 系统的关键字和系统定义的运算符、分隔符都各自单独定义为一个词类，那么词类定义中除了常量和 标识符 以外，别的词类就一般不需附加信息。第四章1、语法分析最常用的两类方法是_自上而下_和_自下而上_分析法。 2. 自顶向下语法分析方法会遇到的主要问题有 左递归 和 回溯 。3.LL（1）分析法中，第一个L的含义是_指输入字符串从左向右扫描_，第二个L的含义是_最左推导_，“1”的含义是_最多只向左看一个输入字符_。4. 将非LL(1)文法转换为等价的LL(1)文法所采用的两种方法是（ 提取左公共因子 ）和（ 消除左递归 ）。但这两种方法并不能保证所有的非LL(1)文法都能转换为等价的LL(1)文法。5进行确定的自上而下语法分析要求语言的文法是无 左递归和无公共左因子 的。6递归下降法不允许任一非终极符是直接_左_递归的。7自顶向下的语法分析方法的基本思想是：从文法的_开始符号_开始，根据给定的输入串并按照文法的产生式一步一步的向下进行_直接推导_，试图推导出文法的_句子_，使之与给定的输入串_匹配_。 8语法分析基于_上下文无关_文法进行，即识别的是该类文法的句子。语法分析的有效工具是_语法树_。9. 设有文法 G(S)： SPab | bP Pb | 根据文法G(S)，填写如下LL(1)分析表的内容。 a b $ PP Pb P10. 设有文法GS为：SAB | BcA| bB| aDCAD | b DaS | c则FOLLOW(A) = a，$，c ，FIRST(S) = b，a，c ；。第五章1LR分析法是一种自下而上 的语法分析方法。2、 LR（0）分析法的名字中，“L”的含义是_指输入字符串从左向右扫描_，“R”的含义是_最右推导的逆过程最左规约_,“0”的含义是_最多向前查看0个字符_。3自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行_直接归约_ ，力求归约到文法的_开始符号_。 4规范归约中的可归约串是指（句柄）。5自下而上分析法采用_移进_、归约、错误处理、_接受_等四种操作。6. 已知文法GS：S*A，A*0A1。 则FIRSTVT(A)= 0，* ，LASTVT(A)= 1，* 7. LR(K)方法可以分为LR(0)、SLR(1)、 LR(1) 和LALR(1)四种。8. 自底向上语法分析方法的基本思想是：由输入的符号串出发，利用文法的规则一步步进行 规约 ，试图归约到文法的开始符号。9. LR分析器有三个部份组成，它们总控程序、 LR分析表 和分析栈。10.LR分析表包括 Action 表和 goto 表两部分第六章1、从功能上说，程序语言的语句大体可分为_执行性_语句和_ 说明性_语句两大类。 2、所谓语法制导翻译方法是_为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序_。 3把语法范畴翻译成中间代码所依据的是（语义规则）。4. 编译过程中，每当扫描识别出一个名字后，编译程序就查阅 符号表 ，看该名字是否在其中，如果该名字是一个新名字就将它填进 符号表 里。5过程调用时，参数的传递方法通常有_传值_、_传址_和传名。6. 现代编译系统多采用 语法制导翻译 方法，即在语法分析过程中根据各个规则所相联的语义动作或所对应的语义子程序进行翻译的办法。该方法使用 属性文法为工具来说明程序设计语言的语义。 7. 过程(函数)是结构化程序设计的主要手段。调用与被调用过程两者之间的信息主要通过 全局变量 或参数来传递。参数分为 形参和实参，常用的参数传递方式有传地址、传值、传名等。8（ YACC ）是一种语法分析程序的自动构造工具，用它可以直接构造各种语言的语法分析器；而（ LEX ）是一种词法分析程序的自动构造工具，用它可以直接构造各种语言的词法分析器。9. 在语法分析过程中，随着分析的步步进展，根据每个规则所对应的语义子程序或语义动作进行翻译的办法，称为（语法制导 ）翻译方法，它被现代很多编译程序所采用。10、 编译过程中，常见的中间语言形式有 三元式 、 四元式 、 间接三元式 和 逆波兰式 等11语法分析是依据语言的_语法_规则进行的，中间代码产生是依据语言的_语义_规进行的。12逆波兰式 ab+c+ d*e- 所表达的表达式为_（a+b+c)*d-e_ 。13后缀式abc-/所代表的表达式是_ a/(b-c)_。14. 从功能上说，程序语言的语句大体可分为执行性语句和 说明性 语句两大类15. 可用属性文法来说明源语言语义。属性文法由一个 文法 和一系列附加在文法上的语义规则构成。16. 引入中间语言的目的是便于目标代码的生成和 代码优化 17. 符号表表的内容包括两部份：标识符的名字和 信息 18. 在目标代码生成阶段，符号表是 地址分配_的依据。19. 在语义分析阶段的语义检查包括 静态语义检查 和 静态语义检查20. 静态语义检查实在编译时进行的，动态语义检查是在运行时进行的21.文法符号的属性有两种，一种称为 继承属性_，另一种称为_综合属性_ 第七章1、常用的两种动态存贮分配办法是_栈式_动态分配和_堆式_动态分配。 2. 编译程序中常用的存储分配策略包括 静态存储分配 、 栈式动态存储分配 和堆式动态存储分配策略。3. 编译时能确定其所需占用空间的数据存放在 静态 数据区；对在程序运行时才能确定所需占用空间大小的可变数据及管理过程的控制信息，其空间分配一般采用 堆式 或栈式 动态存储分配方式。4.存储分配的基本单元是 过程的活动记录 5.数据空间的分配，实质上是将源程序中的名字与相应的存储位置关联起来，这种关联具有两种属性，即 环境 和 状态 ，环境表示了从名字到 存储位置 的映射函数，状态表示了存储位置到 值 的映射第八章1. 在循环中可采用 代码外提 、 强度削弱 和删除归纳变量三种优化措施。2. 基本块的定义：一个基本块是指程序中一个 顺序执行的语句序列，其中只有一个入口和一个出口。入口是程序第一个语句或转移语句的目标语句，或转移语句的后继第一个语句。出口是程序最后一个语句或转移语句。3. 在基本块范围内的优化称为 局部优化4. 通常局部优化是指基本块内的优化，所谓基本块是指程序中一顺序执行的语句序列，其中只有一个（ 入口 ）语句和一个（ 出口 ）语句。5. 所谓优化实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前的代码运行结果相同，但运行速度加大或占用的（空间）减少。常用的优化技术有删除多余运算、（代码外提）、强度削弱、变换循环控制条件、合并已知变量与复写传播及 删除无用赋值。6根据优化对象所涉及的程序范围，代码优化分为 局部优化 、 全局优化和 循环优化 等。7局部优化是在_基本块_范围内进行的一种优化。8. 局部优化采用的工具是 DAG 9.有代码为 a=5; a=7; 可以采用的优