编译原理第1章 概论

1、2022-2-2莆田学院许振和1许振和 网络中心2013.02版2022-2-2莆田学院许振和2答疑联系方式1. 天空教室2. 手3. E-mail: 4. QQ：7456277875. 课后时间：教室或办公室2022-2-2莆田学院许振和3编译原理编译原理教材及主要参考书教材及主要参考书教材：教材：编译原理编译原理，陈英等，清华大学出版社，陈英等，清华大学出版社旧教材：旧教材： 编译原理编译原理，张雪峰等，研究出版社，张雪峰等，研究出版社，2008.042008.04 编译原理编译原理，吕映芝等，清华大学出版社，吕映芝等，清华大学出版社课程特点：课程特点：综合性、抽

2、象性、逻辑性、实践性综合性、抽象性、逻辑性、实践性教学重点：重点介绍文法分析、词法分析和语法分析。教学重点：重点介绍文法分析、词法分析和语法分析。教学要求教学要求：认真听课；不讲话、不旷课、不迟到；认真完成：认真听课；不讲话、不旷课、不迟到；认真完成作业、做好课堂笔记。作业、做好课堂笔记。考核方式：平时的考勤、作业、课堂提问、期中测验占考核方式：平时的考勤、作业、课堂提问、期中测验占30%30%，期末笔试考试占期末笔试考试占70%70%。2022-2-2莆田学院许振和4编译原理编译原理主要参考书主要参考书参考书：参考书：1.1.编译原理，陈火旺，国防工业出版社编译原理，陈火旺，国防工业出版社2

3、.2.编译原理学习指导与习题解析，陈英等，清华大学出版社编译原理学习指导与习题解析，陈英等，清华大学出版社3.3.编译原理学习辅导张伟清华大学出版社编译原理学习辅导张伟清华大学出版社200200.0.04.4.编译原理习题与解析伍春香清华大学出版编译原理习题与解析伍春香清华大学出版2001.082001.085.5.编译原理习题精选分析与解答杨宗源清华大学出版编译原理习题精选分析与解答杨宗源清华大学出版社社2003.072003.072022-2-2莆田学院许振和5为什么要学习编译原理？为什么要学习编译原理？1、有助于深刻理解和正确使用程序设计语言，加深对高级语言程序执行过程的理解2、有助于加

4、深对整个计算机系统的理解。 3、设计开发编译程序的软件技术同样可以用于其他软件的设计开发。4、随着微处理器技术的飞速发展，处理器性能在很大程度上取决于编译器的质量、编译技术成为计算机的核心技术，地位变得越来越重要。 2022-2-2莆田学院许振和6编译原理编译原理课程课程在计算机科学中的在计算机科学中的地位地位高级语言程序设计离散数学数据结构编译原理编译原理操作系统系统软件应用软件软件工程信息系统电子商务汇编语言计算机组成原理2022-2-2莆田学院许振和7编译原理编译原理课程课程在计算机科学中的在计算机科学中的重要地位重要地位 (1) 学习编程最初是学习一门高级语言高级语言，C或Pascal

5、，掌握编写一些简单程序的方法；(2) 学习数据结构数据结构，建立“算法”的概念，对编程有更深入的理解。遇到问题的时候，能够寻找相应的数据结构模型，设计适当的算法来解决问题；(3) 学习汇编语言汇编语言，这门课程是我们真正深入了解计算机内部工作的第一门课程。通过学习了解汇编语言如何变为机器语言，如何对应于一条指令；(4) 计算机组成原理计算机组成原理课程的学习使我们了解到计算机的硬件组成，以及机器指令程序如何在计算机中运行的过程。 (5) 编译原理编译原理课程帮助我们了解高级语言程序转换成机器指令程序的过程。可以帮助我们更深刻地理解高级语言程序运行的内部机制。2022-2-2莆田学院许振和8开设

6、开设编译原理编译原理目的目的系统地向学生讲述编译系统的系统地向学生讲述编译系统的结构结构、工作流程工作流程及编译程序各组成部分的及编译程序各组成部分的设计原理和实现技术设计原理和实现技术，使，使学生通过本课程的学习之后，既掌握编译理论和方学生通过本课程的学习之后，既掌握编译理论和方法方面的法方面的基本知识基本知识，也具有设计、实现、分析和维，也具有设计、实现、分析和维护编译程序等方面的护编译程序等方面的初步能力，初步能力，也达到提高也达到提高应用程应用程序设计能力和解决实际问题能力序设计能力和解决实际问题能力的目的。的目的。 加深对编程语言设计和实现的理解，对和编程加深对编程语言设计和实现的理

7、解，对和编程语言有关的理论有所了解，对宏观上把握编程语言语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用，提升自身的编程能力。来说，起一个奠基的作用，提升自身的编程能力。 掌握掌握编译程序的基本结构，编译程序的基本结构，掌握掌握常用的编译技常用的编译技术和方法，将编译原理的理论和方法应用于一般的术和方法，将编译原理的理论和方法应用于一般的软件设计软件设计中。中。2022-2-2莆田学院许振和9本课程的本课程的特点特点(1) 本课程理论性很强，学习时需要很强的逻辑思维能力(2) 涉及的算法复杂，要深入地理解这些算法很困难(3) 整个编译程序的构造方法非常精妙，就像一部走时精确的

8、时钟，很多齿轮、部件协调地运转，以驱动指针准确地旋转；编译程序也是如此，一边扫描源程序，一边经过各个部件的运算，准确地输出为目标语言。(4) 编译原理课程各个部分之间的独立性很强，包括词法分析、语法分析、存储的组织与分配、中间语言、语法制导翻译、代码生成与优化这几大部分。词法分析和语法分析是其中的重点，语言分析也是难点，需要掌握比较复杂的算法逻辑；其他部分相对来说知识性更强一些。各部分之间的方法也互相独立，在学习时，便于逐个击破。(5) 考试考查的内容相对来说是很稳定的，绝大多数题目的解法都非常机械。2022-2-2莆田学院许振和10学习学习方法方法(1) 尽可能地掌握编译原理的思想，要站得高

9、一点，尽可能理解算法的思想，而不是背固定的算法。应该尽力理解为什么要这样做，逐渐在头脑中建立起编译器的整体概念，而不是零零散散的一些算法。(2) 很多题目的解法比较固定，要熟练掌握相应的具体方法。(3) 多做习题, 对于编译这样的学科，题目的规模很大，步骤繁多，而且前面的步骤一旦出错，后面都错。 (4) 要扎扎实实地牢记重要算法，配合大量的习题进行练习，达到拿到题目就可以动手做的地步。 (5) 一边学习，一边总结，关键是找差异：同一问题可以用多种方法来求解，不同方法适用于不同的文法，对文法的限制和要求，相应的表格的构造、使用等，各个方面的差异都要关注。(6) 亲自动手实现书上的一些算法,完成实

10、验指导书上给出的一个简单的编译程序，或者编译程序的一部分，这样能更灵活地掌握编译程序构造的精髓。 2022-2-2莆田学院许振和11编译技术的编译技术的发展发展1954年至1957年间，FORTRAN语言及其编译器的开发。花了18个人年。几乎与此同时，Noam Chomsky开始研究语言文法(grammar，结构规则)的难易程度以及识别它们所需的算法来为语言分类。在6 0年代和7 0年代进行的分析问题(parsing problem，用于限定上下文无关语言的识别的有效算法)的研究。有穷自动机(finite automata)和正规式(regular expression) 的研究与乔姆斯基的研

11、究几乎同时开始，引出了表示程序设计语言的单词的符号方式。接着又深化了生成有效的目标代码的方法，这就是最初的编译器，实际上应称作代码改进技术(code improvement technique)。当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编译器的自动构造。Lex与Yacc。在70年代后期和80年代早期，大量的项目都关注于编译器其他部分的生成自动化，这其中就包括了代码生成。这些尝试并未取得多少成功。 2022-2-2莆田学院许振和12编译器设计的发展编译器设计的发展 与复杂的程序设计语言的发展结合在一起。如用于函数语言编译的Hindley-Milner类型检查的

12、统一算法。编译器已成为基于窗口的交互开发环境(IDE)的一部分，IDE的标准并没有多少，但已对标准的窗口环境进行了开发。近年来对此进行了大量研究，但是基本的编译器设计近20年来没有多大的改变，现在正迅速地成为计算机科学课程中的中心一环。由多处理机的发展以及对并行处理的要求，最近的研究方向是并行编译。随着嵌入式应用的迅速增长，推动了交叉编译技术的发展；对系统芯片设计方法和关键EDA技术的研究，也带动了专用语言VHDL等及其编译技术的不断深化。 2022-2-2莆田学院许振和13第一章第一章 编译程序引论编译程序引论一、编译方法的定义一、编译方法的定义二、编译过程的概述二、编译过程的概述三、编译程

13、序的结构三、编译程序的结构四、编译阶段的组合四、编译阶段的组合五、编译技术和软件工具的介绍五、编译技术和软件工具的介绍2022-2-2莆田学院许振和14本章要求本章要求主要内容主要内容：各种翻译程序的概念，编译各种翻译程序的概念，编译过程和阶段划分，编译程序的组成和结过程和阶段划分，编译程序的组成和结构，编译程序的构造方法构，编译程序的构造方法重点掌握：重点掌握：编译程序工作的基本过程及编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。其各阶段的基本任务，编译程序总框。2022-2-2莆田学院许振和15机器语言机器语言 (machine language) C7 06 0000 000

14、2汇编语言汇编语言 (assembler language) MOV X , 2高级语言高级语言 (high-level language) X = 2为什么要使用编译器？为什么要使用编译器？2022-2-2莆田学院许振和16计算机中的语言层次和转换关系计算机中的语言层次和转换关系2022-2-2莆田学院许振和17高级语言语言处理程序操作系统汇编语言编译程序所处的层次编译程序所处的层次计算机硬件C编译程序C语言Basic解释程序Basic语言Fortran编译程序Fortran语言.2022-2-2莆田学院许振和18 编译原理是讨论编译程序设计的基本理论、基本概念、基本方法 。 编译器编译器是

15、将一种语言翻译为另一种语言的计算机程序。编译器将源程序编写的程序作为输入，而产生用目标语言编写的等价程序。通常地，源程序为高级语言，如C或C + +，而目标语言则是目标机器的目标代码（object code，有时也称作机器代码（machine code），也就是写在计算机机器指令中的用于运行的代码。这一过程可以用下图表示： 一、一、 什么叫编译程序什么叫编译程序2022-2-2莆田学院许振和19 “源源”和和“目标目标”的术语总是相对于的术语总是相对于一类特定的翻译程序和翻译过程而言的。一类特定的翻译程序和翻译过程而言的。如果一个翻译程序的源程序是某种高级如果一个翻译程序的源程序是某种高级语言

16、，其目标语言是相对于一计算机的语言，其目标语言是相对于一计算机的汇编语言或机器语言，则称这种翻译程汇编语言或机器语言，则称这种翻译程序为序为编译程序。编译程序。源程序源程序 编译器编译器 目标程序目标程序2022-2-2莆田学院许振和20 一般的程序设计语言的定义都涉及语法、语义和语用三方面。 程序语言的发展经历了机器语言、汇编语言和高级语言三个阶段。 语法语法：指如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则。 语义语义：程序设计语言中按语法规则所构成的各个语法成分的意义。 语用语用：表示语言符号及其使用者之间的关系，涉及符号的来源、使用和影响。2022-2-2莆田学院许振和

17、21编译方法的定义： 计算机只能执行机器语言程序。 汇编语言、高级语言都要经过翻译成等效的机器语言。 程序的翻译两种方式：“编译方式”和“解释方式” 。常用翻译工具汇编程序：汇编语言编译程序：Pascal、C 先翻译后执行 笔译解释程序：BASIC 边翻译边执行 口译2022-2-2莆田学院许振和22 解释方式：解释方式：边翻译边执行。完成翻译工作的程序边翻译边执行。完成翻译工作的程序称为解释程序。称为解释程序。 定义：定义：就是对于源程序的一个语句，把它翻译成相应就是对于源程序的一个语句，把它翻译成相应的机器语言的机器语言, , 并让计算机立即执行。并让计算机立即执行。 编译方式：编译方式：

18、源程序翻译成目标程序，后执行目标程源程序翻译成目标程序，后执行目标程序。执行翻译工作的程序称为编译程序。序。执行翻译工作的程序称为编译程序。 定义：定义：将一份源程序从头至尾翻译成某台计算机上的将一份源程序从头至尾翻译成某台计算机上的机器语言，让机器接受，然后执行之，并允许重复执行若机器语言，让机器接受，然后执行之，并允许重复执行若干次。干次。 编译程序编译程序是一个翻译程序，它能够把是一个翻译程序，它能够把源程序源程序翻译成等翻译成等价的价的目标程序目标程序。编译和运行阶段：编译和运行阶段：编译程序计算机目标程序计算机结果源程序原始数据调入运行调入运行输出输出解释执行程序：解释执行程序：计算

19、机解释程序结果提示源程序原始数据调入运行输出输入2022-2-2莆田学院许振和25对编译程序的一些说明对编译程序的一些说明编译程序实质上是一个翻译程序翻译程序，要注意等价等价变换本课程的任务任务就是讲解在这个转换过程中所涉及到的一些理论和方法。转换是一个总体的功能，要抓住总体结构，逐层细分，写编译器时要体现软件工程中软件设计的软件设计的原则原则，自顶向下，逐层分解。编译器要完成的转换任务相当复杂，实现编译器时必须分步骤分阶段分步骤分阶段实现。分阶段实现的好处是能够简化程序的设计简化程序的设计，当然也可以不分阶段实现。2022-2-2莆田学院许振和26解释程序与编译程序的主要区别：解释程序与编译

20、程序的主要区别： 在解释程序的执行过程中不产生目标不产生目标代码代码。翻译程序执行的工作效率很低，但结构比编译程序简单、占用内存少，适用一些规模较小的语言。编译程序是现在计算机系统最重要的系统程序之一。程序的正确性： 一个程序是正确的，包括两层含义：一是书写书写正确正确，即合乎语法规则；二是含义正确含义正确，能够正确理解与应用程序中各种语法成分的语义定义。2022-2-2莆田学院许振和27二、编译过程的概述二、编译过程的概述编译工作的基本过程：逻辑上分编译工作的基本过程：逻辑上分5 5个阶段。个阶段。 词法分析、语法分析、语义分析与中间代码生成、词法分析、语法分析、语义分析与中间代码生成、代码

21、优化和目标代码生成等。代码优化和目标代码生成等。源 程 序编 译 器目 标 程 序词法分析语法分析语义分析与中间代码生成代码优化目标代码生成2022-2-2莆田学院许振和28 每个阶段都有表格管理和出错处理部分。每个阶段都有表格管理和出错处理部分。 编译过程可由一遍或多遍完成（见下图）编译过程可由一遍或多遍完成（见下图）2022-2-2莆田学院许振和29 信信 息息 表表 管管 理理 程程 序序 错错 误误 检检 查查 和和 处处 理理 程程 序序源源程程序序 词法词法 分析分析 程序程序 语法语法 分析分析 程序程序 语义语义 分析分析 程序程序 中间中间 代码代码 生成生成 代码代码 优化

22、优化 程序程序 目标目标 代码代码 生成生成目目标标代代码码编译器是分编译器是分阶段执行的。阶段执行的。每个阶段将源程序从每个阶段将源程序从一种表示转换成另一一种表示转换成另一种表示。种表示。2022-2-2莆田学院许振和30 编译程序就是把高级语言编写的源程序翻译为等价的目标程序。 如何翻译呢？要做两方面的工作：分析与综合。 类似外文翻译。比较如下：外文翻译编译源程序分析阅读原文识别单词分析句子输入并扫描源程序词法分析语法分析综合修辞加工写出译文代码优化目标代码生成2022-2-2莆田学院许振和31一段英文翻译成中文，一段英文翻译成中文，需经下列步骤：需经下列步骤：识别出句子中的单词识别出句

23、子中的单词分析句子的语法结构分析句子的语法结构根据句子的含义进行初步分析根据句子的含义进行初步分析对译文进行修饰对译文进行修饰写出最后的译文写出最后的译文编译程序编译程序词法分析词法分析代码优化代码优化语法分析语法分析语义分析及中语义分析及中间代码生成间代码生成目标代码生成目标代码生成构成编译程构成编译程序各个阶段序各个阶段I am a experienced teacher.2022-2-2莆田学院许振和32按照词法分析、语法分析、语义分析等这种方式来划分阶段的原因是：每个阶段的复杂程度不同，所依据的理论基础不同理论基础不同，实现时采用的方法也不同方法也不同。主要是方便理解和实现。划分阶段的

24、依据是什么？每个阶段所实现的功能相对独立功能相对独立。2022-2-2莆田学院许振和331、词法分析阶段分析单词、词法分析阶段分析单词 主要任务：主要任务：依据语言的依据语言的词法规则，词法规则，从左到右一个从左到右一个字符一个字符地读入字符一个字符地读入源程序源程序，对构成，对构成源程序源程序的字符的字符流进行扫描和分解，从而识别出一个个流进行扫描和分解，从而识别出一个个单词单词。 单词包括：保留字、标识符、运算符、分界符等。单词包括：保留字、标识符、运算符、分界符等。 词法分析的工作主要依据语言的词法规则，描述词法规则的有效工具是正规式和有限自动机。例如在下面的代码行（它可以是C程序的一部

25、分）中： a index = 4 + 2a index = 4 + 2 这个代码包括了1 2个非空字符，但只有8个记号： 像翻译英文句子一样，先要分析单词，弄清各单词的意像翻译英文句子一样，先要分析单词，弄清各单词的意义和句中的作用，才能对句子进行翻译。义和句中的作用，才能对句子进行翻译。2022-2-2莆田学院许振和34 a a 标识符 左括号 i n d e x i n d e x 标识符 右括号 = 赋值 4 数字 + 加号 2 数字以以a=b+c a=b+c * *d d为例词法分析完成的为例词法分析完成的任务：任务：（1 1）读入源程序）读入源程序（2 2）识别出单词（）识别出单词（

26、关键字、标识关键字、标识符、常数、算符和界符符、常数、算符和界符）：）： a a、= =、b b、+ +、c c 、 * *、 d d（3 3）并用记号方式（）并用记号方式（表示逻辑上表示逻辑上相关的字符序列，常用整数来表相关的字符序列，常用整数来表示示）表示识别出的单词）表示识别出的单词例：例：2525表示表示a a、b b、c c、d d；3636：；：；2 2：；：；3131：* *上述单词表示为：上述单词表示为：(25,a),(36,_),(25,b),(32,_),(25,a),(36,_),(25,b),(32,_),(25,c),(31,_),(25,d)(25,c),(31,_

27、),(25,d)2022-2-2莆田学院许振和352、语法分析：、语法分析： 主要任务主要任务：依据语言的：依据语言的语法规则语法规则，逐一地分析，逐一地分析词法分析时得到的词法分析时得到的单词单词，以确定它们是如何组成语，以确定它们是如何组成语句，以及语句是如何组成句，以及语句是如何组成程序程序的。如无语法错误，的。如无语法错误，则给出正确的则给出正确的语法结构语法结构。 在词法分析的基础上，将单词分解成各类语法在词法分析的基础上，将单词分解成各类语法短语（语句）。一般语法短语可表示成短语（语句）。一般语法短语可表示成语法树。语法树。 确定整个输入串是否构成语法上正确的程序。确定整个输入串是

28、否构成语法上正确的程序。 根据规则判定：根据规则判定： 赋值语句：标识符：表达式赋值语句：标识符：表达式 表达式：标识符、常数是表达式；表达式：标识符、常数是表达式； 表达式的运算也是表达式表达式的运算也是表达式2022-2-2莆田学院许振和36语法分析所依据的是语言的语法规则，语法分析所依据的是语言的语法规则， 表示语法规则的工具是上下文无关文法表示语法规则的工具是上下文无关文法, ,用下推自动机实现。用下推自动机实现。例：识别符号串例：识别符号串id1:=id2 + id3 id1:=id2 + id3 * * 10 10是一个是一个赋值语句，而赋值语句，而id2 + id3 id2 +

29、id3 * * 10 10是一个表达式。是一个表达式。2022-2-2莆田学院许振和373、语义分析阶段：、语义分析阶段： 程序的语义就是它的程序的语义就是它的“意思意思”，它与语法或结，它与语法或结构不同。程序的语义确定程序的运行，但是大多数构不同。程序的语义确定程序的运行，但是大多数的程序设计语言都具有在执行之前被确定而不易由的程序设计语言都具有在执行之前被确定而不易由语法表示和由分析程序分析的特征。这些特征被称语法表示和由分析程序分析的特征。这些特征被称作作静态语义静态语义，而语义分析程序的任务就是分析这样，而语义分析程序的任务就是分析这样的语义（程序的的语义（程序的“动态动态”语义具有

30、只有在程序执行语义具有只有在程序执行时才能确定的特性，由于编译器不能执行程序，所时才能确定的特性，由于编译器不能执行程序，所以它不能由编译器来确定）。一般的程序设计语言以它不能由编译器来确定）。一般的程序设计语言的典型静态语义包括的典型静态语义包括声明和类型检查声明和类型检查。2022-2-2莆田学院许振和38 按照语法树的层次关系和先后次序，逐个语句地进行语义按照语法树的层次关系和先后次序，逐个语句地进行语义处理。处理。 主要任务主要任务：依据语言的：依据语言的语义规则语义规则，对语法分析得到的，对语法分析得到的语法语法结构结构进行进行语义语义检查，并用另一种内部形式表示出来。检查，并用另一

31、种内部形式表示出来。 静态语义审查静态语义审查: 变量定义 类型匹配 类型转换 例：C:=A*B (检查C与、类型) 方法方法：对每种语句，都设计好其功能相同的目标序列，存：对每种语句，都设计好其功能相同的目标序列，存放在一个表中。当翻译某个语句时，只要从表中取出与其对应放在一个表中。当翻译某个语句时，只要从表中取出与其对应的目标序列，依次存放在目标程序文件中，就产生目标程序。的目标序列，依次存放在目标程序文件中，就产生目标程序。这过程还要经过二个阶段（中间代码生成和优化代码）这过程还要经过二个阶段（中间代码生成和优化代码）2022-2-2莆田学院许振和39temp1=c*d= + a b*c

32、 dtemp2=b+temp1 temp1 temp2a=temp22022-2-2莆田学院许振和404、中间代码生成：、中间代码生成： 如：sum：firstcount10 生成四元式序列：（inttoreal 10 t1 ） （ id3 t1 t2） （ id2 t2 t3） （： t3 id1）运算符运算对象1运算对象2结果 语法分析和语义分析之后，要将源程序变成一种内部表语法分析和语义分析之后，要将源程序变成一种内部表示形式，这种内部表示形式叫示形式，这种内部表示形式叫中间代码中间代码。使用中间代码的好。使用中间代码的好处是使编译算法更加清晰，便于优化，还使编译程序的更多处是使编译算法

33、更加清晰，便于优化，还使编译程序的更多部分不依赖于目标机器。部分不依赖于目标机器。 常见的中间代码形式常见的中间代码形式: :逆波兰表示、三元式、四元式及树逆波兰表示、三元式、四元式及树形结构形结构等等。等等。id1id2id3t1，t2，t3是临时变量2022-2-2莆田学院许振和415、代码优化阶段、代码优化阶段 主要任务：试图改进中间代码，以产生执行速度较快主要任务：试图改进中间代码，以产生执行速度较快的机器代码（节省时间和空间）的机器代码（节省时间和空间） 优化方法包括：公共子表达式的提取、循环优化、删优化方法包括：公共子表达式的提取、循环优化、删除无用代码等。除无用代码等。 代码的优

34、化依据的是程序的等价变换规则。代码的优化依据的是程序的等价变换规则。对上面中间代码进行优化处理后，产生对上面中间代码进行优化处理后，产生如下的代码：如下的代码：temp1=c*da=b+temp1temp1=c*dtemp2=b+temp1a=temp22022-2-2莆田学院许振和426、目标代码生成：、目标代码生成： 任务任务：把中间代码：把中间代码( (或经优化的中间代码或经优化的中间代码) )变换成变换成特定特定机器上的低级语言代码。机器上的低级语言代码。 依赖于机器的硬件系统结构和机器指令的含义依赖于机器的硬件系统结构和机器指令的含义 目标代码可以是：绝对指令代码、可重定位的指令代目

35、标代码可以是：绝对指令代码、可重定位的指令代码、汇编指令代码。码、汇编指令代码。序号 四元式1(*, id2, id3, T1)2 (+, int1, T1, T2)3(+, T2, T1, id1)（1）mov AX, id2（2）mul AX, id3（3）mov BX, AX（4）add AX, int1（5）add AX, BX（6）mov id1, AX2022-2-2莆田学院许振和437、符号表管理、符号表管理int a,b;float e,fchar ch1,ch2;为什么要先说明为什么要先说明? 定义了变量的类型，也就规定了变量在内存中的存定义了变量的类型，也就规定了变量在内存

36、中的存放形式，在其上所能进行的运算。放形式，在其上所能进行的运算。 解决符号地址到存贮地址上的映射。解决符号地址到存贮地址上的映射。主要任务：建立一批不同用途的表格主要任务：建立一批不同用途的表格, ,保持一些专用的表保持一些专用的表格格, ,一般信息表的登记项由关键字和与之相关联的信息组一般信息表的登记项由关键字和与之相关联的信息组成。成。2022-2-2莆田学院许振和44编译器的一个基本功能是编译器的一个基本功能是记录源程序中使记录源程序中使用的标识符用的标识符并将它们并将它们记载到符号表中记载到符号表中。符号表是一个数据结构。符号表是一个数据结构。每个标识符在符号表中都每个标识符在符号表

37、中都有一条记录有一条记录名字名字记号记号类型类型种属种属 addrid1(25)id2(25) b a例：例：int a, b;int简变简变 0 4 并并收集与每个标识符相关的各种收集与每个标识符相关的各种属性信息，属性信息，int简变简变2022-2-2莆田学院许振和45 词法分析阶段可以检测出当前被扫描的字符串词法分析阶段可以检测出当前被扫描的字符串不能组成语言的有效单词这类错误。语法分析阶段不能组成语言的有效单词这类错误。语法分析阶段处理语言的语法错误；语义分析阶段则应发现语法处理语言的语法错误；语义分析阶段则应发现语法上正确但是一个无意义的结构。通常，语法分析和上正确但是一个无意义的

38、结构。通常，语法分析和语义分析处理由编译器发现的绝大部分错误。语义分析处理由编译器发现的绝大部分错误。8 8、错误检查和处理程序：、错误检查和处理程序：主要任务：查错和纠错主要任务：查错和纠错 在编译的各个阶段都会发现源程序中的错误，在编译的各个阶段都会发现源程序中的错误，为了使编译器能继续运行，以检测出源程序中更为了使编译器能继续运行，以检测出源程序中更多的错误，在检测到错误后，必须以合适的方式多的错误，在检测到错误后，必须以合适的方式进行错误处理。进行错误处理。2022-2-2莆田学院许振和46例如求半径为例如求半径为 r 的圆面积和周长的问题，的圆面积和周长的问题，用用PASCAL语言编

39、写的程序是：语言编写的程序是：9 9、编译程序的简单模型、编译程序的简单模型Program scr ( input , output ) ; 程序首部程序首部 var s, c, r : real ; 说明说明 r, s, c 是实型变量是实型变量 begin s : = pi * sqr ( r ) ; 计算圆的面积计算圆的面积 s c : = 2 * pi * r ; 计算圆的周长计算圆的周长 c End. 程序结束程序结束 2022-2-2莆田学院许振和47(1) 词法分析：词法分析： Program scr ( input , output ) ; var s , c , r : re

40、al ; begin s : = 3.14 * sqr ( r ) ; c : = 2 * 3.14 * r ; End . 2022-2-2莆田学院许振和48(2) 语法分析：语法分析： r c: =2*3.14* 2022-2-2莆田学院许振和49（1）( *, 3.14, r ) （2）(*, (1), r) （3）(:=, (2), s) （4）(*, 2, 3.14)（5）(*, (4) , r )（6）(:=, (5) , c)（1）( *, 3.14, r ) （2）(*, (1), r) （3）(:=, (2), s) （4）(*, 6.28, r)（5）(:=, (4) ,

41、c )（3） 语义分析：语义分析：（4） 代码优化：代码优化：2022-2-2莆田学院许振和50（1）( *, 3.14, r ) （2）(*, (1), r) （3）(:=, (2), s) （4）(*, 2, (1) )（5）(:=, (4) , c)（5） 目标代码生成：目标代码生成：2022-2-2莆田学院许振和51三、编译程序的结构三、编译程序的结构 表表 格格 管管 理理 源程序源程序 词法分析词法分析 语法分析语法分析 语义分析语义分析 综综 合合 错错 误误 处处 理理 优优 化化 代码生成代码生成目标程序目标程序 分分 析析2022-2-2莆田学院许振和52 由左图可以看出，

42、由左图可以看出，词法分析是实现词法分析是实现编译器的基础，编译器的基础，语法分析是实现语法分析是实现编译器的关键。编译器的关键。 因此按照这个顺因此按照这个顺序来实现编译器序来实现编译器 每一步的实现都每一步的实现都依赖于一定的理依赖于一定的理论基础。论基础。 数学，尤其是离数学，尤其是离散数学是程序设散数学是程序设计方法学的理论计方法学的理论基础基础2022-2-2莆田学院许振和53三、编译程序的结构三、编译程序的结构(续续)(1) 记号记号( (token) ) 当扫描程序将字符收集到一个记号中时，它通常是以符号表示这个记号；这也就是说，作为一个枚举数据类型的值来表示源程序的记号集。(2)

43、 语法树（语法树（syntax tree） 如果分析程序确实生成了语法树，它的构造通常为基于指针的标准结构，在进行分析时动态分配该结构，则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个节点都是一个记录，它的域表示由分析程序和之后的语义分析程序收集的信息。编译程序中的主要数据结构编译程序中的主要数据结构: :2022-2-2莆田学院许振和54(3) 符号表（符号表（symbol table） 这个数据结构中的信息与标识符有关：函数、变量、常量以及数据类型。符号表几乎与编译器的所有阶段交互：扫描程序、分析程序或将标识符输入到表格中的语义分析程序；语义分析程序将增加数据类型和其他信息；优化

44、阶段和代码生成阶段也将利用由符号表提供的信息选出恰当的代码。因为对符号表的访问如此频繁，所以插入、删除和访问操作都必须比常规操作更有效。尽管可以使用各种树的结构，但杂凑表却是达到这一要求的标准数据结构。有时在一个列表或栈中可使用若干个表格。编译程序中的主要数据结构编译程序中的主要数据结构: :2022-2-2莆田学院许振和55(4) 常数表（常数表（literal table） 常数表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常数表中也十分重要。但是，在其中却无需删除，这是因为它的数据全程应用于程序而且常量或字符串在该表中只出现一次。(5) 中间代码（中间代码（interme

45、diate code） 根据中间代码的类型（例如三元式代码）和优化的类型，该代码可以是文本串的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器，应特别注意选择允许简单重组的表示。(6) 临时文件（临时文件（t e m p o r a ry file） 计算机过去一直未能在编译器时将整个程序保留在存储器中。这一问题已经通过使用临时文件来保存翻译时中间步骤的结果或通过“匆忙地”编译（也就是只保留源程序早期部分的足够信息用以处理翻译）解决了。编译程序中的主要数据结构编译程序中的主要数据结构: :2022-2-2莆田学院许振和56四、编译阶段的组合：四、编译阶段的组合：编译过程分为编译过程分为前端和后端前端和后端: : 前端：前端：主要指与源语言有关，与目标语言无关的部分，主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，通常包括词法分析、语法分析、语义分析和中间代码生成，以及相关的错误处理和符号表的建立，与机器无关部分的代以及相关的错误处理和符号表的建立，与机器无关部分的代码优化。码优化。 后端：后端：指与目标机器有关的部分。如与机器有关的优化、指与目标机器有关的部分。如与机器有关的优化、目标代码生成。目标代码生成。 后端主要包括代码优化、代码生成和相关错误处理。后端主要