程序设计语言 编译原理(第三版)第1章

程序设计语言

编译原理于静洋 yjy@http://www.77cn.com.cn

第一章 引论1.1 什么叫编译程序 1.2 编译过程概述 1.3 编译程序的结构

1.4 编译程序与程序设计环境(略)1.5 编译程序的生成

1.1 什么叫编译程序1.什么是编译程序？翻译程序：一种语言程序---------->另一种语言程序 源语言 目标语言

编译程序：高级语言程序---------->低级语言程序 汇编程序：汇编语言程序---------->机器语言程序 解释程序：源语言程序---------->边解释边执行

1.1 什么叫编译程序2.“高级语言程序”的执行方式(1)编译方式：先编译后执行。数据 源程序 编译程序 目标程序 计算机 运行 结果

编译阶段

运行阶段

(2)解释方式：以源程序作为输入，但不产生目标代码，而 是边解释边执行源程序本身。数据 源程序 解释程序 结果

编译和解释的主要区别： 是否产生目标代码！

1.1 什么叫编译程序3.

“编译程序”在计算 机系统中的位置较 接近于“硬件”

1.1 什么叫编译程序4.发展20世纪50年代 第一个编译程序—— FORTRAN编译程序

当时普遍认为设计和实 现编译程序是一件十分 困难、令人生畏的事情

目前：编译原理与技术得到迅速发展，现已形成一套比较 成熟的系统化的理论与方法，并开发出了一些好的编译程序 的实现语言、环境与工具。

1.2 编译过程概述一.类比自然语言翻译和编译过程

什么是 语言？

The elephant ate an banana. for K : = 1 to 100 do begin M : = I + 10 * K ; N : = J + 10 * K end

1.2 编译过程概述英→汉 编译的工作过程 1)识别单词……………………………………………词法分析

2)分析句子语法结构…………………………………语法分析3)根据句子含义初步翻译…………语义分析与中间代码产生 4)修饰译文…………………………………………………优化 5)写出最后译文…………………………………目标代码生成

1.2 编译过程概述1.词法分析for K : = 1 to 100 do begin M : = I + 10 * K ; N : = J + 10 * K end

基本字 for 标识符 K 赋值号 := 常数 1 基本字 to 常数 100 基本字 do 基本字 begin ... ...

1.2 编译过程概述词法分析 ——规则： 依循词法规则. 规则描述工具：正规式和有限自动机(FA). 任务：输入源程序，对构成源程序的字符串进行扫描和 分解，识别出一个个的单词符号，如基本字、标 识符、常数、算符、界符等。

1.2 编译过程概述2. 语法分析规则： 依循语法规则. for K : = 1 to 100 do begin M : = I + 10 * K ; N : = J + 10 * K end

规则描述工具： 上下文无关文法. 任务： 在词法分析的基础上，根据语言的语法规则，对单词

符号串进行语法分析，识别出各类语法单位，最终判断输入串是

否构成语法上正确的“程序”。

1.2 编译过程概述3.语义分析和中间代码产生规则：语义规则 规则描述工具： 属性文法 任务： 对语法分析器识别出的各类语法单位，分析 其含义并进行初步翻译(产生中间代码)。 两部分工作： 1.对每种语法范畴进行静态语义检查; 2.若语义正确，则进行中间代码翻译.中间代码：一种独立于 具体硬件的记号系统， 更接近于机器代码

1.2 编译过程概述语义分析后产生的中间代码：for K : = 1 to 100 do begin M : = I + 10 * K ; N : = J + 10 * K end; K:=1 L1: if 100<K goto L2 T1:=10*K M:=I+T1 T2:=10*K N:=J+T2 K:=K+1 goto L1 L2:

三地址代码

具体实现：三元式，四元式，间接三元式

1.2 编译过程概述四元式序列：

序号 OP ARG1 ARG2 RESULTK:=1 L1:if 100<K goto L2 T1:=10*K M:=I+T1 T2:=10*K N:=J+T2 K:=K+1 goto L1 L2 :

(1) (2) (3) (4) (5) (6) (7) (8) (9)

:= j< * + * + + j

1 100 10 I 10 J K

K K T1 K T2 1

K (9) T1 M T2 N K (2)

1.2 编译过程概述4.优化任务：对中间代码进行加工变换，以期在最后阶段能产生出 更为高效(省时间和空间)的目标代码。

包括：公共子表达式的提取、 循环优化、删除无用代码等