编译原理文档第一章资料.doc

编译原理 第一章 编译程序概论 使用过计算机的人都知道，多数用户是应用高级语言来实现他们所需要的计算的。在计算机上执行高级语言程序一般分为两步：第一步，用一个编译程序把高级语言翻译成机器语言程序；第二步，运行所得的机器语言程序求得计算结果。计算机语言由单一的机器语言发展到现今内容迥异的数千种高级语言，就是因为有了编译技术。因此，对于计算机专业的学生来说，理解编译程序的工作原理显得尤其重要。 本章重点：编译程序概念、编译过程概述、编译程序的结构。 第一节 什么是编译程序 通常所说的翻译程序是指这样的一个程序，它能够把某一种语言（称为源语言）改造为另一种语言（称为目标语言），而后者与前者在逻辑上是等价的。如果源语言是诸如FORTRAN、PASCAL、ALGOL或COBOL这样的“高级语言”，而目标语言是诸如汇编语言或机器语言之类的“低级语言”，这样的一个翻译程序就称为编译程序。 它所执行过程可用图1-1-1来说明 第二节 编译过程概述 第二节 编译过程概述 编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来说，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的，图1-2-1给出了一个编译过程的各个阶段，这是一种典型的划分方法。事实上，某些阶段可能组合在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了。图1-2-1中将编译过程划分成了词法分析、语法分析、中间代码生成，代码优化和目标代码生成六个阶段，我们将分别介绍各阶段的任务。另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作。如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可有小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。 我们从源程序在不同阶段所被转换成的表示形式的不同来介绍各个阶段的任务。 词法分析阶段： 是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号）。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有具体含义。比如标识符是由字母字符开头，后跟字母、数字字符的字符序列组成的一种单词。保留字（关键字或基本字）是一种单词，此外还有算符，界符等等。例如某源程序片断如下： begin var sum, first, count: real; sum :=first + count * 10 end. 词法分析阶段将构成这段程序的字符组成了如下单词序列： 1. 保留字 begin 2. 保留字 var 19. 界 符 · 3. 标识符 sum 4. 逗 号 ， 5. 标识符 first 6. 逗 号 ， 7. 标识符 count 8. 冒 号 ： 9. 保留字 real 10. 分 号 ； 11. 标识符 sum 12. 赋值号 ：= 13. 标识符 first 14. 加 号 + 15. 标识符 fount 16. 乘 号 * 17. 整 数 10 18. 保留字 end 可以看出，五个字符b, e, g, i和n构成一个分类为保留字的单词begin，两个字符即：和=构成了表示赋值运算的符号：=。这些单词间的空格在词法分析阶段都被滤掉了。 我们使?id1,id2和id3分别表示sum, first和count三个标识符的内部形式，那么经过词法分析后上述程序片断中的赋值语句sum ：=firs t+ count * 10则表示为id1：=id2 + id3 * 10 语法分析： 是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称语法单位，可表示成语法树，比如上述程序中的单词序列： id1：=id2 + id3 * 10 经语法分析得知其是PASCAL语言的“赋值语句”，表示成如图1-2-2所示的语法树或是图1-2-3所示的那种形式。 语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。 程序的结构通常是由递归规则表示的，例如，我们可以用下面的规则来定义表达式： （1）任何标识符是表达式。 （2）任何常数（整常数、实常数）是表达式。 （3）若表达式