绪论

什么是编译

翻译程序 由一种语言转换成另一种语言的程序

编译程序 由高级语言程序转换成低级语言的程序

解释程序 不产生中间程序，执行代码的程序

五个阶段

词法分析

任务：输入源程序，对源程序的字符串扫描成一个个单词

依循的规则：构词规则

描述工具：正规是有限自动机

语法分析

任务：将单词分解成语法单位

依循规则：语法规则

描述工具：上下文无关文法

语义分析和中间代码生成中间代码

仍无：按语言的语义初步翻译

依循的规则：语义规则

中间代码：三元式、四元式、。。。

代码优化

任务：对中间代码惊醒加工变换：提取公共子表达式、合并已知量、删除无用语句等

遵循的原则：程序的等价变换原则

目标代码生成

任务：把中间代码转换成特定机器上的目标代码，依赖于硬件系统结构和机器指令的含义

目标代码类型：

绝对指令代码：可直接运行

可重新定位的指令代码：需要连接装配

汇编指令代码：需要汇编

编译程序结构

顺序结构

源程序-》单词-》语法单位-》四元式-》四元式’-》目标代码

词法分析器-》语法分析器-》语义分析与中间代码生成器-》代码优化段-》目标代码生成器

表格管理：

符号名表：储存变量

入口名表：储存函数

常数表：存储常数

标号表：goto语句

出错处理：

发现源程序中的错误：语法错误、语义错误

遍 Pass

编译前端和后端

前端：与元语言有关 词法分析、语法分析、语义分析、中间代码生成、与机器无关的优化

后端：与目标及有关 与目标及有关的优化、目标代码生成

优缺点：

• 编译效率低
• 优化好，利于移植，结构清晰、内存需求小

高级语言机器语法描述

上下文无关文法的定义

文法：

描述语言的语法结构的形式规则，上下文无关文法G是一个四元式

G=（V_t、V_n、S、P）

V_t 终结符结合

V_n非终结符集合 和终结符没有交集

S：文法开始符号 属于非终结符集合

P：产生式集合，

开始符号S必须在某个产生式P左部出现一次

推导、语言的概念

程序语言

语法：一组规则，可以形成和产生一个合式的程序

词法规则：单词符号的形成规则 常数、标识符、基本字、算符、界符 最基本结构

描述工具：有限自动机 FA

语法规则：语法单位的形成规则，如何从单词符号形成语法单位 表达式、语句、分程序、过程、函数等

描述工具：上下文无关文法 四元式

语义：一组规则，可以定义一个程序的意义

基于属性文法的语法制导翻译（语义）方法来分析语义

程序语言的基本功能和层次结构

基本功能：描述数据、数据运算

程序语言的语法描述

概念一个字可由多个字符组成，for为一个字

推导

最左推导，最右推导 只能选择一种

文法二义性判定

文法分类及应用

0型 无限制 左边至少有一个非终结符

1型 上下文有关 右边长度大于等于左边长度

2型 上下文无关 左边只有一个非终结符

3型 正规文法

词法分析

词法分析阶段的主要任务

在单词级别上分析和翻译源程序

例题：