工学编译原理-第一章课件

编译原理

第一章引论王金伟计算机与信息工程学院天津师范大学7/21/20231TJNU-COCIE-WJW编译原理课程类别：专业选修课适用专业：计算机科学与技术、计算机软件总学时：51（平均每周3学时）总学分：3先修课：C语言、数据结构、离散数学各班选一位同学担任课代表（收发作业）考核方法考勤5%（随机点名5次，每次1分）课后作业5%（5次，每次1分）上机作业20%（4个，试验报告，每个5分）期末70%7/21/20232TJNU-COCIE-WJW主要内容编译程序的基本构造原理和基本实现技术形式语言基础知识词法分析语法分析语法制导翻译程序优化代码生成7/21/20233TJNU-COCIE-WJW主要章节第1章．引论第2章．高级语言的定义和一般特征第3章．词法分析第4章．语法分析——自上而下分析第5章．语法分析——自下而上分析第6章．属性文法和语法制导翻译第7章．语义分析和中间代码生成第8章．符号表第9章．运行时存储空间组织第10章．优化第11章．目标代码生成7/21/20234TJNU-COCIE-WJW教材和参考书1. 教材： 陈火旺等：程序设计语言编译原理（第三版），国防工业出版社，2000年2. 参考书：编译原理和技术（第二版，陈意云编著，中国科学技术大学出版社，1997）吕映芝、张素琴、蒋维杜：编译原理；清华大学出版社1998杜淑敏、王永宁：编译程序设计原理；北京大学出版社19867/21/20235TJNU-COCIE-WJW第一章引论1.1什么叫编译程序1.2编译过程概述1.3编译程序的结构1.4编译程序与程序设计环境1.5编译程序的生成1.6学习“编译原理”课的注意事项7/21/20236TJNU-COCIE-WJW1.1什么叫编译程序多数用户用高级语言（C，C++，Pascal）编写程序，以实现他们所需要的应用但目前的计算机执行的是非常低级的语言：机器语言。问题：高级语言写出的程序最终是怎样在计算机上执行的呢？答案：编译程序7/21/20237TJNU-COCIE-WJW1.现实例子

一、编译程序的概念英文书中文书翻译7/21/20238TJNU-COCIE-WJW2.翻译程序 能够把某一种语言程序转换成另一种语言程序，并且，后者与前者在逻辑上是等价的。源语言程序目标语言程序翻译程序Main(){

int

i,j;…}…PROCEDURE

MAIN;

Var

I,J:Integer;

Begin…End…输入输出c程序pascal程序7/21/20239TJNU-COCIE-WJW3.编译程序是翻译程序的一种特点：目标语言比源语言低级源语言程序目标语言程序翻译程序

….

int

a,b,c;a=1;b=2;c=a+b;……Mova,1Movb,2Addc,a,b…输入输出c程序汇编语言程序编译程序7/21/202310TJNU-COCIE-WJW4.解释程序特点：以源语言程序作为输入，但不产生目标语言程序，而是边解释边执行源语言程序

….public

class

student

{

public

static

void

main(String

args[]){

StringBuffer

string[]=

new

StringBuffer[10];

….

}

}…输入执行JAVA程序解释程序JVM（JAVA虚拟机）输入编译程序字节流输入JAVA字节流javac（JAVA编译器）7/21/202311TJNU-COCIE-WJW按编译目的不同分类：1.诊断编译程序专门用于帮助程序开发和调试的编译程序2.优化编译程序着重于提高目标代码运行效率的编译程序二、编译程序的分类7/21/202312TJNU-COCIE-WJW按编译目标不同分类：目标机：运行编译程序所产生目标代码的计算机宿主机：运行编译程序的计算机1.交叉编译程序产生不同于其宿主机的机器代码2.可变目标编译程序不需重写编译程序中与机器代码无关的部分就能改变目标机二、编译程序的分类（续）7/21/202313TJNU-COCIE-WJW1.机器语言计算机能够直接执行的机器指令系统例如某种计算机的指令为1011011000000000 加法操作1011010100000000 减法操作2.汇编语言用一些助记符号来表示机器指令例如A+BLD R AADD R B三、几个概念7/21/202314TJNU-COCIE-WJW3.高级语言其语法和结构类似于自然语言，容易记忆和书写例如C语言，Java等4.源语言把被翻译（或编译）的语言称为源语言5.目标语言把翻译（或编译）之后得到的语言称为目标语言6.源程序用源语言编写的程序7.目标程序用目标语言编写的程序7/21/202315TJNU-COCIE-WJW1.2编译过程概述过程复杂，可与自然语言翻译作类比翻译自然语言识别句子中的单词分析句子的语法结构进行初步翻译对译文进行修饰写出最后的译文编译程序词法分析语法分析语义分析与中间代码生成中间代码优化目标代码成成7/21/202316TJNU-COCIE-WJW任务：输入源程序，根据词法规则，对构源程序的字符串进行扫描和分解，识别出一个个单词符号单词符号是程序语言的基本成分例：A=B*C

由5个单词构成：A，等号，B，乘号，C

forI:=1to100do

单词符号：for,I,:=,1,to,100,do实现方法： 构造词法分析程序（扫描器）一、词法分析阶段7/21/202317TJNU-COCIE-WJW任务： 在词法分析的基础上，根据语言的语法规则把识别出的单词符号串，分解成各类语法单位（语法范畴，如表达式、语句、程序段、过程、函数、程序等），以确定整个输入串是否构成语法上正确的“程序”。

例：A=B*CB*C是表达式，A=B*C是赋值语句实现方法： 构造语法分析程序（语法分析器）二、语法分析阶段7/21/202318TJNU-COCIE-WJW任务： 对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）静态语义检查：变量是否定义、类型是否正确等进行中间代码翻译例：C语言中，变量需要在使用前声明实现方法： 构造语义分析程序三、语义分析和中间代码生成阶段7/21/202319TJNU-COCIE-WJW中间代码： 是一种含义明确，便于记忆的记号系统，独立于硬件，与机器指令在形式上有所接近，容易替换成机器指令。

表示形式：后缀式：表示表达式，把运算量（操作数）写在前面，把运算符写在后面（后缀）例：A+B写成AB+7/21/202320TJNU-COCIE-WJW三元式：算符第一操作对象第二操作对象表示二地址指令：四元式： 算符第一操作对象第二操作对象结果表示三地址指令：操作码第一地址第二地址操作码第一地址第二地址第三地址7/21/202321TJNU-COCIE-WJW任务： 对中间代码进行等价变换，使生成目标代码更高效。

例：实现方法： 构造代码优化程序优化fork:=1to100dobeginM:=i+10*kN:=j+10*kend递归加法M:=iN:=jfork:=1to100dobeginM:=M+10N:=N+10end四、代码优化阶段7/21/202322TJNU-COCIE-WJW任务： 把中间代码变换成特定机器上的低级语言代码。 目标代码：机器语言代码、汇编语言代码

例：A+B LD R A ADD R B实现方法： 构造生成目标代码程序五、目标代码生成阶段7/21/202323TJNU-COCIE-WJW1.3编译程序的结构由上述5个阶段的实现程序组成7/21/202324TJNU-COCIE-WJW

源程序语义分析和中间代码生成器语法分析器词法分析器代码优化器目标代码生成器

目标程序表格管理出错处理(字符串)单词符号语法单位中间代码中间代码一、编译程序总框架7/21/202325TJNU-COCIE-WJW 编译程序在工作过程中需要建立一系列表格，以登记源程序中所提供的或在编译过程中所产生的一些信息，编译各个阶段的工作都涉及到构造、查找、修改或存取有关表格中的信息。

例

符号表 用来登记源程序中出现的每个名字以及名字的属性（常量名、变量名（什么类型）、过程名）名字信息二、表格管理7/21/202326TJNU-COCIE-WJW 在翻译各阶段把原程序错误性质和地点通知用户。

语法错误：源程序中不符合语法（词法）规则的错误

例如：拼写错误，括号不匹配，非法字符等

语义错误：源程序中不符合语义规则的错误

例如：说明错误，作用域错误，类型不一致等三、出错处理7/21/202327TJNU-COCIE-WJW编译五个过程是逻辑上划分，具体实现组织成“遍”

遍（pass）： 对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。例如：词法分析单独一遍

词法分析和语法分析合为一遍语法分析和语义分析合为一遍 词法分析、语法分析、语义分析合为一遍（三个不同阶段，语法分析为核心）四、遍7/21/202328TJNU-COCIE-WJW前端： 主要由与源语言有关但与目标语言无关的那些部分组成

例如：词法分析、语法分析、中间代码产生、（代码优化）后端：

由与目标机有关的那些部分组成，不依赖于源语言而仅仅依赖于中间语言。

例如：（代码优化）、目标代码生成等五、编译前端和后端7/21/202329TJNU-COCIE-WJW

源程序语义分析和中间代码生成器语法分析器词法分析器代码优化器目标代码生成器

目标程序(字符串)单词符号语法单位中间代码中间代码五、编译前端和后端（续1）

前端

后端7/21/202330TJNU-COCIE-WJW五、编译前端和后端（续2）C语言编译器前端中间代码C语言编译器后端（X86）C语言编译器后端（ARM）中间代码X86代码ARM代码7/21/202331TJNU-COCIE-WJW1.4编译程序与程序设计环境程序开发过程程序设计环境编辑程序编译程序链接程序库代码源代码目标代码可执行代码UEVI等Linkld等Windbggdb等调试程序Masmas等程序设计环境7/21/202332TJNU-COCIE-WJW1.4编译程序与程序设计环境（续）传统的程序设计环境编辑、编译、链接、调试各自独立集成化的程序设计环境（IDE）TurboCVisualC++PowerBuilderJBuilder等等7/21/202333TJNU-COCIE-WJW1.5编译程序的生成早期用机器或汇编语言现在用高级语言编写7/21/202334TJNU-COCIE-WJW1.直接编写机器语言、汇编语言、高级语言2.自举的方法先对语言的核心部分用机器语言编写核心部分：程序语言的三个支柱：条件、循环、调用返回然后以此为基础，再编写更多的语言成分3.移植的方法将一个已有的A机器上的编译器移植到B机器上一、编译程序的构造方法7/21/202335TJNU-COCIE-WJW二、T形图描述源语言S、目标语言T和编译程序实现语言I间的关系7/21/202336TJNU-COCIE-WJW三、T形图的组合方式1.将第一个T形图的输出作为第二个T形图的输入已有将语言A编译为语言B的编译器和将语言B到语言C的编译器，用上述方法得到A到C的编译器7/21/202337TJNU-COCIE-WJW三、T形图的组合方式（续）2.编译器实现语言的变换例：我们用C语言开发了一个将FORTRAN语言程序编译为JAVA程序的编译器FOR2J，如果我们已经有一个将C语言编译为X86代码的编译器，利用上述的方式可以得到一个在X86机器上执行的FOR2J编译器编译7/21/202338TJNU-COCIE-WJW四、编译器的自举的开发方式没有高级语言可以用来写编译器，怎么办？用汇编语言开发一个完整的编译器？太繁琐用自举的方式：首先用汇编语言M开发一个实现源语言A的一个子集A’的编译器，这个编译器只要正确即可用这个子集语言A’开发语言全集的编译器上述过程可以重复多次，直至得到性能良好的、正确的对语言全集有效的编译器编译7/21/202339TJNU-COCIE-WJW五、编译器的移植的开发方式以PC机为工具开发M芯片的C