编译原理 第1讲(第一章)

《编译原理 第1讲(第一章)》由会员分享，可在线阅读，更多相关《编译原理 第1讲(第一章)（35页珍藏版）》请在金锄头文库上搜索。

1、第一章 编译原理概述,预备概念 什么是编译 编译的基本过程 几个有关的概念 解释程序,预备概念,低级语言(Low Level Language)机器语言、汇编语言特点：与特定的机器有关，功效高，但使用复杂、繁琐、费时、易出错高级语言(High Level Language)Fortran、Pascal、C 语言等特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。,源程序用汇编语言或高级语言编写的程序称为源程序目标程序用目标语言所表示的程序目标语言：可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言。,预备概念,词法，语法，语义 自然语

2、言的的例子：a boy eats an apple. N +V+ N（主谓宾） 词法：规定什么是正确的单词，boy 不能写成byo等等。 语法：规定什么样的语法成分组合是正确的。 语法错误但词法正确的情况： a boy an apple eats. （作为一个完整句子，通常没有这样的语法结构N+N+V） 语义：规定句子在意义上正确否。 语义错误但语法正确的情况：an apple eats a boy. （语法正确，含义是错误的） 语用：言外之意。（我们是在非常恶劣的条件下进行比赛的） 编译原理不涉及语用问题。（广义上，词法可以包括在语法范畴之内。）,预备概念,什么是编译？,从功能上看，一个编译

3、程序就是一个语言翻译程序,它把一种语言(称作源语言，一般是高级语言)书写的源程序翻译成另一种语言(称作目标语言，一般是低级语言)书写的等价的目标程序. 编译 ：编译程序的翻译过程。,源程序,编译程序,目标程序,SOURCE PROGRAM,TRANSLATER,OBJECT PROGRAM,即源程序是编译程序的输入，目标程序是编译程序的输出(注意：1目标程序不一定是可执行文件。2 编译程序编译器编译软件。）,源程序、编译程序、目标程序 三者关系：,信 息 表 格 管 理 程 序,词法分析器,语法分析器,语义分析程序,中间代码生成器,代码优化程序,目标代码生成器,错 误 检 查 和 处 理 程

4、序,源程序,目标程序,单词符号,语法单位,四元式,四元式,编译基本过程,词法分析：又称扫描，任务是输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词符号。 语法分析：以词法分析输出的单词序列为输入，根据语言的语法规则，把单词符号串分解成各类语法单位，如短语、句子、序列段等。如“X+0.6*Y”，在工程计算语言中被识别属于”算术表达式“。（短语，句子，算术表达式都是语法成分） 语义分析：判定各语法成分的含义和功能，确定它们的属性或执行时应运行的运算或操作。（保存运算的中间结果，判断变量是否已经定义，类型是否一致） 中间代码生成：中间代码是一种结构简单、含义明确的记号系统，是介于源

5、语言和目标语言之间的语言代码，一般独立于具体硬件。常用逆波兰式、三元式、四元式及树型结构等。 代码优化：对中间代码进行等价变换，以期最终产生更高效（省时间、省空间）的目标代码，优化策略主要有公共子表达式提取，循环优化等等。（功能要等价） 目标代码生成：接受中间代码（或经优化处理之后），变换为机器语言或汇编语言形式的目标程序。,编译的六个阶段（各部分的大致课时分配）,一个简单的例子,已知：pascal语言片段position:=initial +rate*60要求：将其翻译成目标代码（机器代码）,(1)词法分析,从左至右读字符流的源程序、识别单词（通常滤掉空格，换行等字符）。 position

6、:= initial + rate * 60; 单词类型 单词值标识符1(id1) position算符(赋值) :=标识符2(id2) initial算符(加) +标识符3(id3) rate算符(乘) *整数 60分号 ；,有关术语,保留字-reserved word 标识符-identifier(user-defined name)单词-就是指逻辑上紧密相连的一组字符，这些字符具有集体含义。如保留字（begin、end、if、for、while等）、标识符、常数、算符和界符（标点符号、左右括号等）。,(2)语法分析,功能:层次分析.依据源程序的语法规则把源程序的单词序列组成语法短语(比如

7、：表示成语法树). position := initial + rate * 60 ; 规则:=“:=”:=“+”:=“*”:=“(”“)”:=:=:=,赋值语句的语法树,赋值语句的语法树另一种表达形式,id1:=id2+id3*N,(3)语义分析,变量声明 类型匹配 类型转换例: Program p();Var rate:real;procedure initial;position := initial + rate * 60/* error */ /* error */ /* warning */;,(3)语义分析,Program p();Var rate:real;Var initia

8、l :real;Var position :real ;position := initial + rate * 60（警告，60应该是实数）修改方法：添加一个节点，负责类型转换,(3)语义分析,(4)中间代码生成,源程序的内部(中间)表示：逆波兰式、三元式、四元式及树型结构四元式举例：( *，id3，t1，t2 ) 含义：t2 := id3 * t1,(4)中间代码生成,id1:= id2 + id3 * 60 (1) (inttoreal, 60 - t1 ) (2) (* , id3 t1 t2 ) (3) (+ , id2 t2 t3 ) (4) (:= , t3 - id1 ),(5

9、)代码优化,id1:= id2 + id3 * 60 (1) (inttoreal 60 - t1 ) (2) ( * id3 t1 t2 ) (3) ( + id2 t2 t3 ) (4) ( := t3 - id1 )变换 （1） ( * id3 60.0 t1 )( 2）（ + id2 t1 id1 ),(5)代码优化（单独的例子）,t1 = b* c t1 = b* c t2 = t1+ 0 t2 = t1 + t1 t3 = b* c a = t2 t4 = t2 + t3 a = t4 t*是临时变量，a不能少。还可以优化a=t1+t1,(6)目标代码生成,(* , id3 60.

10、0 t1 ) (+ , id2 t1 id1 ),movf id3,R2 mulf #60.0,R2 movf id2,R1 addf R2,R1 movf R1,id1,汇编代码到机器代码就是一一对应的翻译过程了，比较简单。R*：寄存器；Id*：变量，在内存#60：立即数,(7)符号表管理,Program CONST c100；VARprocedurevarprocedurevar x:real;/层次为2.endend End.,记录源程序中使用的名字 收集每个名字的各种属性信息类型、作用域、分配存储信息,(8)出错处理,检查错误、报告出错信息、排错、恢复编译工作 词法：（标识符，关键字的

11、拼写错误） 语法：（复杂表达式的漏括号） 语义：（类型不相容，变量未定义） 逻辑：功能与预期不一致（比如：a+b写成a-b。这种错误编译器没办法发现，需要人工排除）错误处理方法： 停下来（不负责任） 提示纠正（尽可能准确发现错误，尽可能纠正错误且不改变程序的本意。）,其它有关概念,前端、后端 预处理器 连接装配 编译程序与解释程序,前端与后端,前端：完成分析工作（机器无关）词法分析：识别各个最小语法单位。语法分析：识别出各个语法结构。语义分析：确定类型，类型/运算合法性检查，识别含义和相应处理。 后端：完成综合工作（机器相关）优化：改善目标代码质量。目标代码生成,（以C语言为例）： 宏处理：对

12、较长结构的缩写。编译前要用原结构展开。 文件包含：include 语言扩充：在C语言程序中插入访问数据库的语句，这些语句不是C语言。由预处理将其翻译成C，然后再一起提交给编译器进行编译。（举例）,预处理,main() EXEC SQL BEGIN DECLARE SECTION; char first_name50; char last_name = “White“; EXEC SQL END DECLARE SECTION; EXEC SQL CONNECT TO my_server.pubs USER my_login.my_password; EXEC SQL SELECT au_fna

13、me INTO :first_name from authors where au_lname = :last_name; return (0); ,编译程序：源程序是高级语言，目标语言是某种汇编语言或机器语言的翻译程序。 解释程序：将某种高级语言程序作为输入接受并解释执行，不产生能被执行的结果目标代码。,编译程序与解释程序,解释方式：使用解释程序，对程序逐个语句进行分析，根据语句的含义进行执行。 编译方式：首先由编译程序将程序翻译成为机器语言（或者虚拟机的语言，如java），然后执行。 比较： 编译的方式可以使得一次翻译过后，多次运行。适于花较大的精力进行优化工作。,程序设计语言的执行基本有

14、两种方式：,解释执行和编译执行的区别,Int 2 St b Ld b add 2 St a,生成代码,如： b := 2 ;a := b+2 ; 编译程序write a ; 解释程序直接将4的值输出（显示）。有些象单步调试,1）遍：指对源程序或其内部表示从头到尾扫视一遍，并进行有关的加工处理。 2）一遍扫描：以语法分析程序为中心。编译一次完成，但是运行效果不是很好。 3）多遍扫描：每遍扫描完成不同的任务。优点： 功能独立；结构清晰；利于优化；节省空间。 28遍。,编,本章小结,什么是编译？为什么要编译？ 编译过程的六个阶段： 词法分析：识别单词 语法分析：语法树 语义分析： 什么是中间代码？常

15、用的中间代码种类 代码优化：基本原则 目标代码生成： 符号表管理和错误处理（错误的种类） 遍(一遍扫描，多遍扫描) 前端、后端： 解释方式/翻译方式：,几个希腊字母的读音,大写 小写 英文读音 意义 alpha 角度；系数 beta 磁通系数；角度；系数 gamma 电导系数（小写） delta 变动；密度；屈光度 ,e epsilon 对数之基数 zeta 系数；方位角；阻抗；相对粘度；原子序数 eta 磁滞系数；效率（小写） , theta 温度；相位角 iota 微小，一点儿 kappa 介质常数 lambda 波长（小写）；体积 mu 磁导系数；微（千分之一）；放大因数（小写） nu 磁阻系数 xi omicron pi 圆周直径=3.1416 , rho 电阻系数（小写） ,s sigma 总和（大写），表面密度；跨导（小写） tau 时间常数 upsilon 位移 phi 磁通；角 ch i psi 角速；介质电通量（静电力线）；角 omega 欧姆（大写）；角速（小写）；角,