02.编译原理.

1、2.编译原理一、 编译程序1、 编译器是一种翻译程序，它用于将源语言（即用某种程序设计语言写成的）程序翻译为目标语言（即用二进制数表示的伪机器代码写成的）程序。后者在windows操作系统平台下，其文件的扩展名通常为.obj。该文件通常还要经过进一步的连接，生成可执行文件（机器代码写成的程序，文件扩展名为.exe）。通常有两种方式进行这种翻译，一种是编译，另一种是解释。后者并不生成可执行文件，只是翻译一条语句、执行一条语句。这两种方式相编译比解释运行的速度要快得多。2、 编译过程的5个阶段：词法分析；语法分析；语义分析与中间代码产生；优化；目标代码生成。3、 在这五个阶段中，词法分析的任务是识

2、别源程序中的单词是否有误，编译程序中实现这种功能的部分一般称为词法分析器。在编译器中，词法分析器通常仅作为语法分析程序的一个子程序以便在它需要单词符号时调用。在这一编译阶段中发现的源程序错误，称为词法错误。4、 语法分析阶段的目的是识别出源程序的语法结构（即语句或句子）是否错误，所以有时又常为句子分析。编译程序中负责这一功能的程序称为语法分析器或语法分析程序。在这一阶段中发现的错误称为语法错误。5、C语言的（源）程序必须经过编译才能生成目标代码，再经过链接才能运行。PASCAL语言、FORTRAN语言的源程序也要经过这样的过程。通常将C、PASCAL、FORTRAN这样的语言统称为高级语言。而

3、将最终的可执行程序称为机器语言程序。6、 在编译C语言程序的过程中，发现源程序中的一个标识符过长，超过了编译程序允许的范围，这个错误应在词法分析阶段发现，这种错误通常被称作词法错误。 词法分析器的任务是以词法规则为依据对输入的源程序进行单词及其属性的识别，识别出一个个单词符号。 词法分析的输入是源程序，输出是一个个单词的特殊符号，称为Token（标记或符号）。 语法分析器的类型有:自下而上、自上而下。常用的语法分析器有：递归下降分析方法是一种自上而下分析方法, 算符优先分析法属于自下而上分析方法，LR分析法属于自下而上分析方法等等。 通常用正规文法或正规式来描述程序设计语言的词法规则，而使用上

4、下文无关文法来描述程序设计语言的语法规则。 语法分析阶段中，处理的输入数据是来自词法分析阶段的单词符号。它们是词法分析阶段的终结符。7、 编译程序总框8、 在计算机发展的早期阶段，内存较小的不能一次完成程序的编译。这时通常将编译过程分成若干遍来完成。每一遍完成一部分功能，称为多遍编译。与采用高级程序设计语言写的词法分析器相比，用汇编语言写的词法分析通常分析速度要快些。二. 词法与语法1、 程序语言主要由语法和语义两个方面来定义。2、 任何语言的程序都可看成是某字符集上的一个长字符串。3、 语言的语法：是指这样的一组规则（即产生式），用它可以生成和产生一个良定的程序。这些规则的一部分称为词法规则

5、，另一部分称为语法规则。4、 词法规则：单词符号的形成规则；语法规则：语法单位（句子）的形成规则。语义规则：定义程序句子的意义。5、 一个程序语言的基本功能是描述数据和对数据的运算。6、 高级语言的分类：强制式语言；应用式语言；基于规则的语言；面向对象的语言。7、 一个语言的字母表为a,b，则字符串ab的前缀有a、，其中不是真前缀。8、 字符串的连接运算一般不满足交换率。9、 文法G是一个四元组，或者说由四个元素构成，即非终结符集合VN、非终结符号集合VT 、开始符号S、产生式集合P，它可以形式化地表示成G =（VN，VT，S，P）。按照文法的定义，这4个元素中终结符号集合是这个文法所规定的语

6、言的字母表，产生式集合代表文法所规定的语言语法实体的集合。对上下文无关文法，通常我们只需要写出这个文法的产生式集合就可以确定这个文法的其他所有元素。其中，第一条产生式的左部符号为开始符号，而所有产生式的左部符号构成的集合就是该文法的非终结符集合。 文法的例子：设文法G=（VN，VT， S，P），其中P为产生式集合，它的每个元素的形式为产生式。10、如果文法G的一个句子存在两棵不同的最左语法分析树，则这个文法是无二义的。11、如果文法G的一个句子存在两棵不同的最右语法分析树，则这个文法是无二义的。12、如果文法G的一个句子存在两棵不同的语法分析树，则这个文法是无法判断是否是二义的。13、A为非终

7、结符，如果文法存在产生式 ，则称 可以推导出 ；反之，称 可归约为 。14、乔姆斯基（Chomsky）将文法分为四类，即0型文法、1文法、2文法、3文法。按照乔姆斯基对方法的分类，上下文无关文法是2型文法，2型文法的描述能力最强，3型文法又称为正规文法。15、产生式SSa | a产生的语言为L(G) = an | n 1。16、确定有限自动机DFA是非确定有限自动机NFA的特例；对任一非确定有限自动机能找到一个与之等价的确定有限自动机。17、DFA和NFA的主要区别有三点：一、DFA初态唯一，NFA初态不唯一；二、DFA弧标记为上的元素，NFA弧标记为*上的元素；三、DFA的函数为单射，NFA

8、函数不是单射。18、有限自动机中两个状态S1和S2是等价的是指，无论是从S1还是S2出发，停于终态时，所识别的输入字的集合相同。19、自下而上的分析方法，是一个不断归约的过程。20、递归下降分析器：当一个文法满足LL(1)条件时，我们就可以为它构造一个不带回溯的自上而下分析程序。这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这个产生式中含有的左递归是直接左递归。递归下降分析法中，必须要消除所有的左递归。递归下降分析法中的试探分析法之所以要不断用一个产生式的多个候选式进行逐个试探，最根本的原因是这些候选式有公共左因子。21、算符优先分析法是一种自下而上的分析方法，它适合分析

9、各种程序设计语中的表达式，并宜于手工实现。目前最广泛的无回溯的“移进归约”方法是自下而上分析方法。22、在表驱动预测分析器中，1）读入一个终结符a，若该终结符与栈项的终结符相同，并且不是结束标志$，则此时栈顶符号出栈；2）若此时栈项符号是终结符并且是，并且读入的终结符不是，说明源程序有语法错误；3）若此时栈顶符号为，并且读入的终结符也是，则分析成功。23、算符优先分析方法不存在使用形如 这样的产生式进行的归约，即只要求终结符的位置与产生式结构一致，从而使得分析速度比LR分析法更快。24、LR(0)的例子：产生式E E+T对应的LR（0）项目中，待归约的项目是E E+T，移进项目是E E+T，还

10、有两个项目为E E+T和E E+T。当一个LR(0)项目集中含有两个归约项目时，称这个项目集中含有归约-归约冲突。25、LL(1)文法的产生式中一定没有公共左因子，即LL(1)文法中一定没有左递归。为了避免回溯，在LL(1)文法的预测分析表中，一个表项中至多只有一个产生式。预测分析方法（即LL(1)方法），由一个栈，一个总控程序和一个预测分析表组成。其中构造出预测分析表是该分析方法的关键。26、LR(0)与SLR(1)两种分析方法相比，SLR(1)的能力更强。27、静态语义检查一般包括以下四个部分，即类型检查、控制流检查、名字匹配检查、一致性检查。C语言编译过程中下述常见的错误都属于检查的范围

11、：a） 将字符型指针的值赋给结构体类型的指针变量：类型检查。b）switch语句中，有两个case语句中出现了相同的常量：一致性检查。c）break语句在既不是循环体内、又不是break语句出现的地方出现：控制流检查。d）goto语句中的标号在程序的函数中没有找到：一致性检查。e）同一个枚举常量出现在两个枚举类型的定义当中：相关名字检查。28、循环优化中代码外提是指对循环中的有些代码，如果它产生的结果在循环过程中是不变的，就把它提到循环体外来；而强度削弱是指把程序中执行时间较长的运算替换为执行时间较短的运算。 （完）模拟试题一 、单项选择题1把汇编语言程序翻译成机器可执行的目标程序的工作是由_

12、完成的。 A编译器 B解释器C汇编器 D预处理器2编译过程中，语法分析器的任务是_。1) 分析单词是怎样构成的2) 分析单词串是如何构成语句和说明的3) 分析语句和说明是如何构成程序的4) 分析程序的结构A2和3 B3和4 C2，3和4 D1，2，3和43高级语言编译程序常用的语法分析方法中，递归下降分析法属于_分析方法。A自左至右 B自顶向下 C自底向上 D自右向左4算符优先文法是指_的文法。1) 没有形如U-VW的规则 （U，V，WVn）2) 终结符号集Vt中任意两个符号对之间至多有一种优先关系成立。3) 没有相同的规则右部。4) 没有形如U-的规则A1，2 B1，2，3 C1，2，3，4

13、 D1，2，45动态存储分配时，可以采用的分配方法是1) 以过程为单位的栈式动态存储分配2) 堆存储分配3) 最佳分配方法A1 B2C1，2 D1，2，3二、填空题1编译方式和解释方式的根本区别在于_。2LL（1）分析法中，第一个L的含义是_，第二个L的含义是_，“1”的含义是_。3过程调用时，参数的传递方法通常有_、_、_和传名。4一个上下文无关文法所含四个组成部分是_集、_集、_集和_集。三、判断题1算符优先关系表不一定存在对应的优先函数。（）2每个文法都能改写为LL(1)文法。（）3符号表由词法分析程序建立，由语法分析程序使用（ ）4上下文无关文法规则的左部一定是非终结符号（ ）5LL（

14、1）文法有可能是二义性的。（ ）四、简述题1 简述词法分析阶段的任务。 2 什么是语法制导翻译？3 什么是素短语？4 什么是静态存储分配？5 画图说明编译程序的组成结构。五、综合应用题1 设文法G(S)： S(L) | aS | a LL，S | S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST和FOLLOW； (3) 构造预测分析表。2 已知文法G(E)ET|ETTF|T * FF(E)|i (1) 给出句型(T * Fi)的最右推导及画出语法树； (2) 给出句型(T * Fi)的短语、素短语。参考答案一、单项选择题题号12345答案CCBDC二、填空题1是否生成目标代

15、码2从左向右进行分析，每次进行最左推导，向输入串中查看一个输入符号3传值，传地址，传结果 （顺序可互换）4终结符、非终结符、开始符号、产生式 （顺序可互换）三、判断题12345四、名词解释1、答: 词法分析的基本任务是从左向右扫描每行源程序的符号，识别出单词及其属性，把单词换成统一的内部表示送给语法分析程序。同时还要完成在语法分析之前需要做的工作，如删除注解、空格、换行符等非必要信息，把标识符登录到符号表及某些预加工处理等。2、答: 语法制导翻译就是在进行语法分析的同时，完成语义的分析，即在语法分析的过程中，根据语言的语义定义随时翻译已识别的那部分语法成分的全部含义。答: 有以下特征的短语称为素短语：1) 它首先是一个短语。2) 它至少含一个终结符号。3) 除自身外，不再包含其它素短语。3、答: 如果在编译时就能确定一个程序在运行时所需要的存储空间的大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并确定每个数据项的存储单元地址，而这些数据项的存储地址在运行时始终不变，这就是静态