1、为什么要学习编译原理n必修主干课程，操作系统和编译系统构成程序设计者必修主干课程，操作系统和编译系统构成程序设计者与计算机之间的根本界面。与计算机之间的根本界面。n通过学习该课程，掌握编译的根本理论、常用的编译通过学习该课程，掌握编译的根本理论、常用的编译技术，了解编译过程及编译系统构造和机理。能运用技术，了解编译过程及编译系统构造和机理。能运用所学技术解决实际问题，能独立编写一个小型编译系所学技术解决实际问题，能独立编写一个小型编译系统。统。n此外，通过学习编译原理可以更好地理解程序语言的此外，通过学习编译原理可以更好地理解程序语言的内部机制内部机制,从而更好地理解和运用程序设计语言。能从而
2、更好地理解和运用程序设计语言。能运用编译程序构造的原理和技术完成相关软件工具的运用编译程序构造的原理和技术完成相关软件工具的设计和开发工作。设计和开发工作。课程内容课程内容介绍编译器构造的一般原理和根本实现方法介绍编译器构造的一般原理和根本实现方法介绍的理论知识：形式语言和自动机理论、语法制导介绍的理论知识：形式语言和自动机理论、语法制导的定义和属性文法、类型论等的定义和属性文法、类型论等强调形式描述技术和自动生成技术强调形式描述技术和自动生成技术课课 程程 简简 介介先行课程先行课程 高等数学、离散数学、汇编语言、数据构高等数学、离散数学、汇编语言、数据构造造n 参考资料参考资料n国外编译原
3、理领域内的国外编译原理领域内的3本权威书籍：当代编译技术三大圣经！本权威书籍：当代编译技术三大圣经！n1、龙书、龙书Dragon book2、鲸书Whale book3、虎书、虎书Tiger book国内编译原理领域内的权威书籍：国内编译原理领域内的权威书籍：1.陈意云陈意云?编译原理编译原理?高等教育出版社高等教育出版社2.吕映芝吕映芝?编译原理编译原理?清华大学教育出版社；清华大学教育出版社；3.陈英陈英?编译原理编译原理?清华工大学出版社清华工大学出版社4.蒋宗礼蒋宗礼?编译原理编译原理?高等教育出版社高等教育出版社5.刘磊刘磊?编译原理及实现编译原理及实现?机械工业出版社机械工业出版社
4、 课程特点：理论性强，算法复杂课程特点：理论性强，算法复杂平时平时20%无故旷课：无故旷课：5一本教材，认真听课：以讲义为主，做适当的笔一本教材，认真听课：以讲义为主，做适当的笔记记认真完成课堂和课后作业认真完成课堂和课后作业期末期末80%:闭卷笔试闭卷笔试第一章第一章 编译概述编译概述掌握编译程序中所涉及的有关名词术语掌握编译程序中所涉及的有关名词术语2.2.理解编译程序总的框架，明确编译程序理解编译程序总的框架，明确编译程序工作的根本过程及各阶段的根本任务工作的根本过程及各阶段的根本任务教学目标教学目标1.2.编译的过程编译的过程1.3.编译程序的逻辑构造编译程序的逻辑构造1.4.编译程序
5、的生成编译程序的生成 1.5.编译技术的应用及开展编译技术的应用及开展教学内容 程序的翻译程序的翻译n语言和翻译语言和翻译：语言是人类交流思想和信息的工具。如自然语言，世界上存在着许多种语言，各国之间要交流信息,就要有各种语言之间的翻译。计算机语言同样是丰富多彩的。1/30/2023第16页n机器语言机器语言(machine language)C7 06 0000 0002n汇编语言汇编语言(assembler language)MOV X,2n高级语言高级语言(high-level language)X=2为什么要使用编译程序？为什么要使用编译程序？程序语言的分类n低级语言低级语言Low l
6、evel Language)n机器语言、汇编语言机器语言、汇编语言n特点：与特定的机器有关，成效高，但使用复杂、特点：与特定的机器有关，成效高，但使用复杂、繁琐、费时、易出错。繁琐、费时、易出错。n高级语言高级语言 n -Fortran、Pascal、C 语言等语言等n特点：不依赖具体机器，移植性好、对用户要求低、特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。易使用、易维护等。n计算机硬件只懂自己的指令系统，那么它是如何识别除机器语言以外的另一种语言呢？n解决这一问题的方法：翻译程序！翻译程序！翻译程序n翻译程序：能够把某一种语言程序称为源语言程序转换成另一种语言程序称为目标
7、语言程序的一个程序，而后者与前者在逻辑上是等价的。n程序翻译的方式通常有两种，一种是编译方式，另一种是解释方式。源程序翻译程序目标程序编译程序n编译程序：如果一个翻译程序的源语言是某种高级语言，编译程序：如果一个翻译程序的源语言是某种高级语言，其目标语言是相对于某一计算机的汇编语言或机器语言，其目标语言是相对于某一计算机的汇编语言或机器语言，那么称这种翻译程序为编译程序或称为编译器。那么称这种翻译程序为编译程序或称为编译器。n假设编译生成的目标程序不是机器代码，而是汇编语言假设编译生成的目标程序不是机器代码，而是汇编语言程序，那么还要增加一个会变程序将其会变为机器代码。程序，那么还要增加一个会
8、变程序将其会变为机器代码。源程序（高级语言编写）编译程序目标程序（机器语言或汇编语言编写）汇编程序n如果一个翻译程序的源语言是某种汇编语言，其目标语言是某一计算机的机器语言，那么称这种翻译程序为汇编程序。源程序（汇编语言编写）汇编程序目标程序（机器语言编写）解释程序n解释程序解释程序:是一种语言处理程序，它以源程序是一种语言处理程序，它以源程序作为输入，但不产生目标代码，它将源程序中作为输入，但不产生目标代码，它将源程序中的语句按动态顺序，逐句翻译成课执行代码，的语句按动态顺序，逐句翻译成课执行代码，一旦具备执行条件，那么立即执行这一阶段代一旦具备执行条件，那么立即执行这一阶段代码得到局部结果
9、。码得到局部结果。源程序（高级语言编写）解释程序计算结果 特点：与编译系统比较，解释系统较简单、特点：与编译系统比较，解释系统较简单、可移植性好，易于查错，但速度慢可移植性好，易于查错，但速度慢n编译和解释程序编译和解释程序n编译程序的工作相当于载翻译一本原著，编译程序的工作相当于载翻译一本原著，计算机运行编译后的目标程序，相当于阅计算机运行编译后的目标程序，相当于阅读一本译著；而解释程序的工作相当于在读一本译著；而解释程序的工作相当于在进展同声翻译，计算机运行解释程序，相进展同声翻译，计算机运行解释程序，相当于我们直接通过翻译听外宾讲话。当于我们直接通过翻译听外宾讲话。n程序的编译执行：程序
10、的编译执行：输入数据输入数据源程序源程序编译程序编译程序运行系统运行系统目标程序目标程序n程序的解释执行：q如：BASIC、Prolog，问题：效率低下解释程序解释程序源程序源程序输入数据输入数据计算结果计算结果为什么解释运行的工作效率低于编译方式？为什么解释运行的工作效率低于编译方式？编译程序与解释程序的差异n根本区别：是否生成目标代码！功能功能工作结果工作结果实现技术上实现技术上解释解释程序程序源程序的一个执执行行系统源程序的执行结果执行结果执行中间代码编译编译程序程序源程序的一个转转换换系统源程序的目标代码目标代码把中间代码转换成目标程序“编译+解释执行系统源程序源程序编译程序编译程序源
11、程序的中间形式输出数据输出数据解释程序解释程序输入数据输入数据例如例如Java语言语言.java java源程序文件.class 二进制字节码文件Java虚拟机（JVM)本地计算机系统编译编译程序在计算机系统中的位置n编译程序是一种软件，是系统软件。通常认为系统软件是居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。翻译程序所处的层次翻译程序所处的层次高级语言语言处理程序操作系统汇编语言计算机硬件C编译程序C语言Basic解释程序Basic语言Fortran编译程序Fortran语言.几个概念几个概念n宿主机：运行编译程序的计算机n目标机：运行编译程序所产生的目标代码的计算
12、机n穿插编译程序：一个编译程序产生不同于其宿主机的机器代码n可变目标编译程序：不需要重写编译程序中与机器无关的局部就能改变目标机对编译程序的一些说明对编译程序的一些说明n编译程序实质上是一个翻译程序，要注意等价变换n本课程的任务就是讲解在这个转换过程中所涉及到的一些理论和方法，最后，使用这些理论和方法，自己编写一个小的编译器n转换是一个总体的功能，要抓住总体构造，逐层细分，写编译器时要表达软件工程中软件设计的原那么，自顶向下，逐层分解。n编译器要完成的转换任务相当复杂，实现编译器时必须分步骤分阶段实现。分阶段实现的好处是能够简化程序的设计，当然也可以不分阶段实现。编译原理是讨论编译程序设计的根
13、本理论、根本概念、根本方法 什么是编译原理什么是编译原理1/30/202334编译器和集成开发环境n编译器：即编译程序，把高级语言经分析翻译为低级语言。编译器：即编译程序，把高级语言经分析翻译为低级语言。n集成开发环境：简称集成开发环境：简称IDEIntegrated Develop Environment，是用于提供程序开发环境的应用程序，一般包括代码编辑器、编译是用于提供程序开发环境的应用程序，一般包括代码编辑器、编译器、调试器和图形用户界面工具。器、调试器和图形用户界面工具。n背景：早期程序设计的各个阶段都要用不同的软件来进展处理背景：早期程序设计的各个阶段都要用不同的软件来进展处理,如
14、如先用字处理软件编辑源程序，再用编译程序进展编译，然后用链接先用字处理软件编辑源程序，再用编译程序进展编译，然后用链接程序进展函数、模块连接程序进展函数、模块连接,开发者必须在几种软件间来回切换操作。开发者必须在几种软件间来回切换操作。n人们习惯上经常把人们习惯上经常把IDE称为编译器。称为编译器。编译原理引论35常见语言及其IDE语言IDECTC2.0C+C+Builder,VC+6.0,TC3.0C#VS.NETPascalTurbo PascalOOPascalDelphiVBVB6.0 (解释器)JavaEclipse,JBuilder1.2 编译的过程编译的过程n1.编译程序的工作过
15、程编译程序的工作过程n编译过程本身是一种语言的翻译过程，类似于外文的翻译。n将英文句子“I wish you success I wish you success 翻译成中文。n两阶段完成翻译 分析：分析：分析单词：I，wish，you，success 分析语法：主语，谓语，宾语，宾补 分析语义：我希望你成功 综合：综合：综合英语的意思、上下文环境和汉语的表达习惯，完成翻译：祝你成功n翻译外文资料：n1、能识别出句子中的一个单词；n2、分析句子的语法构造；n3、根据句子的含义进展初步翻译；n4、对译文进展修饰；n5、写出最后的译文。翻译外文资料与编译源程序进展类比翻译外文翻译外文编译程序编译程
16、序分析分析识别单词识别单词分析句子分析句子根据语义进行根据语义进行初步翻译初步翻译词法分析词法分析语法分析语法分析语义分析、生成中间代码语义分析、生成中间代码综合综合修辞加工修辞加工写出译文写出译文代码优化代码优化目标代码生成目标代码生成将编译过程划分为将编译过程划分为5个根本阶段个根本阶段词法分析词法分析语法分析语法分析语义分析及中间代码生成语义分析及中间代码生成代码优化代码优化目标代码生成目标代码生成n从概念上来讲，一个编译程序的整个工作过程是划分成阶段进展的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进展的操作在逻辑上是严密连接在一起的。n事实上，某些阶段可能组合在一起
17、，这些阶段间的源程序的中间表示形式就没必要构造出来了。1.2 编译的过程编译的过程n1.编译程序的工作过程编译程序的工作过程(1)(1)词法分析词法分析词法分析阶段是编译过程的第一个阶段。词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的个字符地读入源程序，对构成源程序的字符流进展扫描和分解，根据语言的词字符流进展扫描和分解，根据语言的词法规那么识别出一个个具有独立意义的法规那么识别出一个个具有独立意义的最小语法单位，即单词。最小语法单位，即单词。n根据词法规那么分析和识别单词。根据词法规那么分析和识别单词
18、。n把需要存放的单词放到符号表中，如变量名，把需要存放的单词放到符号表中，如变量名，标号，常量等。标号，常量等。n工作依据工作依据:源语言的构词规那么源语言的构词规那么(即词法即词法)，也称，也称为模式为模式(pattern)。n标识符的模式是：以字母开头的字母数字序列。标识符的模式是：以字母开头的字母数字序列。n例：例：sum=(10+20)*(num+square);结果结果q(标识符，标识符，sum)q(赋值号，赋值号，=)q(左括号，左括号，()q(整常数，整常数，10)q(加号，加号，+)q(整常数，整常数，20)q(右括号，右括号，)q(乘号，乘号，*)q(左括号，左括号，()q(
19、标识符，标识符，num)q(加号，加号，+)q(标识符，标识符，square)q(右括号，右括号，)q(分号，分号，;)n词法分析的功能如下：n识别出源程序中意义独立的最小词法单位单词。n删除无用的空格、回车和其他与输入介质有关的符号n删除程序员为了提高程序可读性所加的注释n如果发现错误那么报告出错n(2)(2)语法分析语法分析n根据语法规那么即语言的文法，分析根据语法规那么即语言的文法，分析并识别出各种语法成分如表达式、语句、并识别出各种语法成分如表达式、语句、函数等，并进展语法正确性检查。函数等，并进展语法正确性检查。n通常将语法分析的结果表示为语法树。通常将语法分析的结果表示为语法树。s
20、um=(10+20)*(num+square);n语法分析的功能是进展层次分析，把源程序的单词序列组成语法短语(表示成语法树)。依据的是语法规那么。C语言的赋值语句的规那么为：nn单词序列sum=(10+20)*(num+square);之所以能表示成上图的语法树，依据的是赋值语句和表达式的语法规那么。:=“=:=“+|“*:=“(“)|n(3)语义分析及中间代码生成n语义分析阶段的任务是审查源程序有无语义错误。n工作依据：源语言的语义规那么n一个重要任务：类型检查n根据规那么检查每个运算符及其运算对象是否符合要求；n数组的下标是否合法；n过程调用时，形参与实参个数、类型是否匹配等n(3)语义
21、分析及中间代码生成n源程序中有些语法成分，按照语法规那么去判断，它是正确的，但它不符合语义规那么。比方使用了没有声明的变量；或者给一个过程名赋值；或者调用函数时参数类型不适宜或者参加运算的两个变量类型不匹配等等。n比方下边的程序片段：int arr2,c;c=arr1*10;n其中的赋值语句是符合语法规那么的，但是因为没有声明变量arr1，而存在语义错。n中间代码生成中间代码生成(可选可选n所谓所谓“中间代码是一种构造简单、中间代码是一种构造简单、含义明确的记号系统，这种记号系统含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的可以设计为多种多样的形式，重要的设计原那么为两点：一
22、是容易生成；设计原那么为两点：一是容易生成；二是容易将它翻译成目标代码。二是容易将它翻译成目标代码。n中间代码的形式：中间代码的形式：n四元式、三元式、逆波兰表示四元式、三元式、逆波兰表示n中间代码中间代码(intermediate Code)n例例:sum=(10+20)*(num+square);n(4)中间代码优化(可选n代码优化阶段的任务是对前阶段产生的中间代码进展变换或进展改造，目的是使生成的目标代码更为高效，即省时间和省空间。例：例：sum=(10+20)*(num+square)得到的四元式得到的四元式nT1=10+20nT2=num+squarenT3=T1*T2nsum=T3
23、 优化后优化后nT1=num+squarenSum=30*T1n这只是优化工作的两个方面，此外诸如公共子表达式的删除、强度削弱、循环优化等优化工作将在后面的章节详细介绍。n代码优化工作会降低编译程序的编译速度，因此编译优化阶段常常作为可选择阶段，编译程序具有控制机制以允许用户在编译速度和目标代码的质量间进展权衡。n思考：代码优化能提高编译程序的运行效率吗？n(5)(5)目标代码生成目标代码生成n目标代码生成阶段的任务是把中间代码变目标代码生成阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译位的指令代码或汇编指令
24、代码。这是编译的最后阶段，它的工作与硬件系统构造和的最后阶段，它的工作与硬件系统构造和指令含义有关，这个阶段的工作很复杂，指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运用、机器指涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间令的选择、各种数据类型变量的存储空间分配以及存放器和后缓存放器的调度等。分配以及存放器和后缓存放器的调度等。n涉及到的两个重要问题：涉及到的两个重要问题：n对程序中使用的每个变量要指定存储单元对程序中使用的每个变量要指定存储单元n对变量进展存放器分配对变量进展存放器分配例：例：sum=(10+20)*(num+square)得到的优
25、化后四元式得到的优化后四元式nT1=num+squarenSum=30*T1生成如下指令序列：生成如下指令序列：nMOV num,R1nMOV square,R2nADD R2,R1nMUL 30,R1nMOV R1,sum目标代码可采用如下三种形式之一：(1)具有绝对地址的机器指令代码。(2)汇编语言形式的目标程序。需要经过汇编程序汇编，以产生机器代码。(3)可重定位的指令代码。多数编译程序所产生的目标代码都是这种类型。语句sum=(10+20)*(num+square);的翻译过程编译过程小结编译过程小结目标代码生成程序代码优化程序语义分析生成中间代码语法分析程序词法分析程序S.PO.Pn
26、上述编译过程的阶段划分是一种典型的处理模式，上述编译过程的阶段划分是一种典型的处理模式，事实上并非所有的编译程序都包括这样几个阶段。事实上并非所有的编译程序都包括这样几个阶段。有些编译程序并不要中间代码，即不存在中间代有些编译程序并不要中间代码，即不存在中间代码生成阶段；有些编译程序不进展优化，优化阶码生成阶段；有些编译程序不进展优化，优化阶段即可省去段即可省去;有些最简单的编译程序只有词法分析，有些最简单的编译程序只有词法分析，语法分析；语义分析和目标代码生成。语法分析；语义分析和目标代码生成。1.3 编译程序的逻辑构造编译程序的逻辑构造 按逻辑功能不同，可将编译过程划分为五个根本阶 段，与
27、此相对应，我们将实现整个编译过程的编译程序划 分为五个逻辑阶段即五个逻辑子过程。每个阶段中都要有：符号表管理符号表管理和错误处理错误处理典型的编译程序具有典型的编译程序具有7个逻辑局部个逻辑局部语义分析及语义分析及生成中间代码生成中间代码程序程序代码生成程序代码生成程序代码优化代码优化程序程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理 词法分析：识别单词，至少分以下几大类：关键字保存字、标识符、字面量、特殊符号；语法分析：得到语言构造并以树的形式表示 语义分析：考察构造正确的句子是否语义合法，可修改树构造；中间代码生成可选：生成一种既接近目标语言，又与
28、具体机器无关的表示，便于优化与代码生成；到目前为止，编译器与解释器可以一致 中间代码优化可选：局部优化、循环优化、全局优化等；优化实际上是一个等价变换，变换前后的指令序列完成同样的功能，但是，在占用的空间上和程序执行的时间上都更省、更有效。目标代码生成：不同形式的目标代码汇编、可重定位、绝对机器指令;符号表管理：合理组织符号，便于各阶段查找、填写等；出错处理：错误的种类词法错、语法错、静态语义错、动态语义错。符号表管理n编译程序的一项重要工作：n记录源程序中使用的标识符n收集每个标识符的各种属性信息n符号表是由假设干记录组成的数据构造n每个标识符在表中有一条记录n记录的域是标识符的属性n对符号
29、表构造的要求：n应允许快速地找到标识符的记录n可在其中存取数据n标识符的各种属性是在编译的各个不同阶段填入符号表的。声明语句：float total,rate;n词法分析器：nfloat是关键字ntotal、rate是标识符n在符号表中创立这两个标识符的记录n语义分析器：ntotal、rate都表示变量nfloat表示这两个变量的类型n可以把这两种属性及存储分配信息填入符号表。n在语义分析和生成中间代码时，还要在符号表中填入对这个float型变量进展存储分配的信息。错误处理n在编译的每个阶段都可能检测到源程序中存在的错误n词法分析程序可以检测出非法字符错误。n语法分析程序能够发现记号流不符合语
30、法规那么的错误。n语义分析程序试图检测出具有正确的语法构造，但对所涉及的操作无意义的构造。n代码生成程序可能发现目标程序区超出了允许范围的错误。n处理与恢复n判断位置和性质n适当的恢复n出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标。编译有关的其他概念n“遍n前端和后端编译器扫描的遍数n遍趟：是对源程序或源程序的中间结果从头遍趟：是对源程序或源程序的中间结果从头到尾扫描一遍，并作有关加工处理，生成新的中到尾扫描一遍，并作有关加工处理，生成新的中间结果或目标程序。间结果或目标程序。n例如：词法分析器对输入源程序进展第一遍扫描，例如：词法分析器对输入源程序进展第一遍扫描，语法分析进展第二遍
31、扫描语法分析进展第二遍扫描n但一个阶段对应一遍扫描的工作方式是逻辑上的，但一个阶段对应一遍扫描的工作方式是逻辑上的，由于屡次扫描的方式需要大量的存储空间存放中由于屡次扫描的方式需要大量的存储空间存放中间表示，并且会增加一些不必要的输入输出操作，间表示，并且会增加一些不必要的输入输出操作，因此编译器往往把假设干个阶段的工作结合起来，因此编译器往往把假设干个阶段的工作结合起来，对应一遍扫描，从而减少对程序的扫描遍数。对应一遍扫描，从而减少对程序的扫描遍数。n一个编译程序应分成几遍，如何划分，是与源程序、设计要求、硬件设备等诸因素有关的，因地难于统一划定。n在主存可能的前提下，一般遍数尽可能少一点为
32、好。但并不是每种语言都可以用单遍编译程序实现。一遍扫描的编译程序语法分析器语法分析器取记号取记号词法分析器词法分析器源程序源程序记号记号语法成分语法成分语义分析及代码生成语义分析及代码生成目标程序目标程序返回返回控制流控制流信息流信息流开场开场完毕完毕整理目标程序整理目标程序多遍编译程序编译程序总控词法分析器语法分析器语义分析器中间代码生成代码优化目标代码生成源程序中间语言1，表中间语言2，表中间语言3，表中间语言4，表优化代码，表目标代码符号表管理错误处理编译阶段的组合n在前面所讨论的编译过程中阶段的划分是编译程序的逻辑组织。有时，常常把编译的过程分为前端前端(front end)和后端后端
33、(back end)，前端的工作主要依赖于源语言而与目标机无关,后端工作依赖于目标机而一般不依赖源语言。根据编译程序各局部功能，将编译程序分成前端和后端根据编译程序各局部功能，将编译程序分成前端和后端 前端：通常将与源程序有关的编译局部称为前端。前端：通常将与源程序有关的编译局部称为前端。词法分析、语法分析、语义分析、中间代码生成词法分析、语法分析、语义分析、中间代码生成 -分析局部分析局部 特点：与源语言有关特点：与源语言有关 后端：与目标机有关的局部称为后端。后端：与目标机有关的局部称为后端。代码优化、代码生成代码优化、代码生成-综合局部综合局部 特点：与目标机有关特点：与目标机有关编译程
34、序的前端和后端编译程序的前端和后端编译阶段的组合编译阶段的组合为什么生成中间代码为什么生成中间代码.java java源程序文件源程序文件.class 二进制字节码文件二进制字节码文件JavaJava虚拟机（虚拟机（JVM)JVM)本地计算机系统本地计算机系统编译编译同一前端同一前端+不同后端不同后端 不同机器构成同一语言的编译程序不同机器构成同一语言的编译程序例如例如JavaJava语言语言 不同前端不同前端+同一后端同一后端 同一机器生成几个语言的编译程序同一机器生成几个语言的编译程序例如例如GCCGCC 编译程序集合编译程序集合编译程序中的主要数据构造编译程序中的主要数据构造(续续)To
35、ken表符号表常数表错误信息语法树中间代码表临时文件目标代码表1/30/2023第83页1.4 1.4 编译程序的设计编译程序的设计n构造编译程序要掌握以下几方面的内容：n源语言：理解其构造和含义n目标语言：必须清楚硬件的系统构造和指令的格式等n编译方法1/30/2023第84页1.4 1.4 编译程序的设计编译程序的设计n一般实现编译程序的方法有：n注：编译程序核心局部常用汇编语言编写n注：这是普遍采用的方法n5.用编译工具自动生成:LEX(词法分析)与YACC(用于自动产生LALR分析表)n6.移植同种语言的编译程序在不同类型的机器之间移植1.4 编译程序的生成编译程序的生成n早期人们用汇
36、编语言编写编译程序，但其效率低，实现困难，比方FORTRAN语言编译器18年才完成。n专门的编译编译工具，可以支持编译程序某些局部的自动生成。比方：LEX和YACC等。n说到一个编译程序，一定要知道它的源语言是什麽，目标语言是什麽，还有它的实现语言是什麽。常使用T型图来表示一个编译程序所涉及的三个语言。S：源语言 O：目标语言 T：编译程序实现语言S OTn开发编译程序的途径开发编译程序的途径:n自展法自展法n工具法工具法n自动生成法自动生成法n移植法移植法自展法自展法n利用A机器上已有的用A代码编写的L1语言的编译程序，把用L1语言编写的L2语言的编译程序进展编译，得到A机器代码实现的L2语
37、言的编译程序。表示为：L 2 语言A代码L1语言L 1 语言A代码A代码L 2 语言A代码A代码n或者表示为：L 2 语言A代码L1语言L 1 语言A代码A代码L 2 语言A代码A代码n问题一：如何直接在一个机器上实现问题一：如何直接在一个机器上实现C语言编译器？语言编译器？n解决：解决：q用汇编语言实现一个子集的编译程序用汇编语言实现一个子集的编译程序(P0人人)q用汇编程序处理该程序用汇编程序处理该程序,得到得到(P2:可直接运行可直接运行)q用子集编制语言的编译程序用子集编制语言的编译程序(P3人人)q用用P2编译编译P3，得到，得到P4自展4.用用P2P2编译编译P3P3，得到，得到P
38、4P4语言语言机器语言机器语言机器语言机器语言子集子集机器语言机器语言机器语言机器语言子集子集汇编语言汇编语言机器语言机器语言1.用汇编语言实现一个用汇编语言实现一个 子集的编译程序子集的编译程序(P0(P0人人)汇编语言汇编语言机器语言机器语言机器语言机器语言子集子集机器语言机器语言机器语言机器语言2.用汇编程序用汇编程序(P1)(P1)处理该程序处理该程序,得到得到(P2:(P2:可直接运行可直接运行)语言语言子集子集机器语言机器语言3.用子集编制用子集编制 语言的编译程序语言的编译程序(P3(P3人人)移植n问题二：问题二：A A机上有一个机上有一个C C语言编译器，是否可利用此编语言编
39、译器，是否可利用此编译器实现译器实现B B机上的机上的C C语言编译器？语言编译器？q条件：机有条件：机有 语言的编译程序语言的编译程序q目的：实现机的语言的编译目的：实现机的语言的编译语言语言A机器机器A机器机器语言语言B机器机器机器机器要完成的任务要完成的任务语言语言语言语言机器机器语言语言机器机器机器机器语言语言机器机器机器机器语言语言语语 言言机器机器语言语言机器机器A机器机器语言语言A机器机器机器机器需要编写的程序需要编写的程序1)问题的分析1.1.(人人)用语言编制用语言编制B B机的编译程序机的编译程序P0(CP0(C2.2.(机的机的C C编译编译P1)P1)编译编译P0P0，
40、得到在，得到在A A机上可运行的机上可运行的P2(CP2(C语言语言语语 言言机器机器语言语言机器机器A机器机器语言语言A机器机器机器机器2)问题的解决方法3.(3.(机的机的P2)P2)编译编译P0P0，得到在，得到在B B机上可运行的机上可运行的P3(CP3(C语言语言语言语言机器机器语言语言机器机器机器机器语言语言机器机器机器机器语言语言语语 言言机器机器语言语言机器机器A机器机器语言语言A机器机器机器机器n编译程序移植：编译程序移植：用A机器上的L语言编写能在机器B上运行的L语言的编译程序n先用L语言编写出在A机器上运行的产生B机器代码的L编译程序源程序，然后把该程序经过A机器上的L编
41、译程序编译后得到能在A机器上运行的产生B机器代码的编译程序，用这个编译程序再一次编译上述源程序。LBLLBLLAALBALBBLBLLAALBALBLLBALBB本机编译器的利用n问题三：问题三：A A机上有一个机上有一个C C语言编译器，现要实现一个新语言编译器，现要实现一个新语言语言NEWNEW的编译器？能利用穿插编译技术么？的编译器？能利用穿插编译技术么？n用用C C编写编写NEWNEW的编译，并用的编译，并用C C编译器编译它编译器编译它NEW语言语言语语 言言A机器机器语言语言机器机器A机器机器NEW语言语言A机器机器A机器机器1.5 编译技术的应用及开展编译技术的应用及开展应用：大
42、局部软件工具的开发，都要使用编译技应用：大局部软件工具的开发，都要使用编译技术和方法术和方法语法制导的构造化编辑器语法制导的构造化编辑器Turbo-Edit、editplus和和Ultraedit等等程序格式化工具程序格式化工具软件测试工具软件测试工具静态分析器：不可能执行的代码、定义后未引用的变量静态分析器：不可能执行的代码、定义后未引用的变量动态测试工具：运行后与期望结果比较动态测试工具：运行后与期望结果比较程序理解工具：确定调用关系，画出流程图程序理解工具：确定调用关系，画出流程图高级语言的翻译工具高级语言的翻译工具语法制导的构造化编辑器n具有通常的正文编辑和修改功能n能象编译程序那样对
43、源程序进展分析，把恰当的层次构造加在程序上。n可以保证源程序n无语法错误n有统一的可读性好的程序格式n构造化编辑器能够执行一些对编制源程序有用的附加任务，如：n检查用户的输入是否正确n自动提供关键字n从BEGIN或左括号跳到与其相匹配的END或右括号程序格式化工具n读入并分析源程序n使程序构造变得清晰可读，如：n用缩排方式表示语句的嵌套层次构造n用一种专门的字型表示注释等软件测试工具静态测试动态测试动态测试器动态测试器静态测试器静态测试器读入源程序读入源程序在不运行该程序的情况下对其进展分析，以发现程序中潜在的错在不运行该程序的情况下对其进展分析，以发现程序中潜在的错误或异常。误或异常。不可能
44、执行到的死代码不可能执行到的死代码未定义就引用的变量未定义就引用的变量试图使用一个实型变量作为指针等。试图使用一个实型变量作为指针等。利用测试用例实际执行程序利用测试用例实际执行程序记录程序的实际执行路线记录程序的实际执行路线将实际运行结果与期望结果进展比较，以发现程序中的错误或异将实际运行结果与期望结果进展比较，以发现程序中的错误或异常。常。程序理解工具n对源程序进展分析n确定各模块间的调用关系n记录程序数据的静态属性和构造属性n画出控制流程图练 习n1、判断正误n(1)编译程序的五个组成局部缺一不可。n(2)高级语言程序到低级语言程序的转换是基于语义的等价变换。n(3)含有优化局部的编译程序的执行效率高。n(4)因为编译程序和解释程序具有不同的功能，所以他们的实现技术也完全不同。n(5)编译程序和解释程序的根本区别在于解释程序对源程序并没有真正的进展翻译。n(6)无论一遍扫描的编译器还是多遍扫描的编译器都要对源程序扫描一遍。练 习n2、对以下错误信息，请指出可能是编译的哪个阶段词法分析、语法分析、语义分析、n代码生成报告的。n1 else 没有匹配的ifn2 数组下标越界n3 使用的函数没有定义n4 在数中出现非数字字符n5 零作除数谢谢大家！
