其它
T 7
*
30
二.语法规则
语法规则规定了如何从单词符号形成更 大的结构（即语法单位），换言之，语法 规则是语法单位的形成规则 一般的程序设计语言的语法单位有： 表达式 、语句 、分程序 、 函数 、 过程和程序等
下推自动机理论和上下 文无关文法是我们讨论语法 分析的理论基础
2016/8/5计算机学院
编译器
目标程序 汇编语 另一种程序 言、机 设计语言、 器语言
6
源程序 Fortran、 Pascal、 Java、 C2016/8/5 ….. 计算机学院
错误信息
辛明影
1.2 编译过程概述
编译程序的工作，从输入源程序开始，到输出目 标程序结束，与自然语言之间的翻译有很多相似之处。 构成编译程 序各个阶段 一段英文翻译成中文，
Elist →E|ε
2016/8/5计算机学院
辛明影
35
类型说明和过程说明语句：
P→ D
D→ D;D
D→ id:T D→id（Elist） D ; S
T →int
T → float
2016/8/5计算机学院
辛明影
36
数组说明语句： L→ id[Elist] Elist→ Elist,E
Elist→ E
2016/8/5计算机学院
辛明影
语法规则
26
一 .词法规则
字母表就是一个有穷字符集。 C语言的字母表为： ∑={a---z 、 A—Z 、 0—9 、(、) 、 [ 、] 、 、. 、! 、~ 、+ 、- 、* 、 / 、 & 、% 、< 、 > 、= 、^ 、 | 、? 、, 、; } 词法规则是指单词符号的形成规则 C语言的标识符的构成规则： 字母、下划线打头的字母、数字和下划线 构成的符号串。如：a1、ave 、_day
2016/8/5计算机学院
辛明影
19
1.4编译各阶段的分组 一、前端和后端
前端包括词法分析、词法分析、语 义分析，以及相关的错误处理和符号表 的建立
前端依赖于源程序并在很大程度上 独立于目标机器。
2016/8/5计算机学院
辛明影
20
后端主要包括代码优化、代码生成和相 关错误处理。
后端依赖于目标机器。
辛明影
31
主要语句的形式描述：
表达式：
E→E+T E→E-T E→T T→T*F T→T/F T→F F→(E) F→ id
2016/8/5计算机学院
辛明影
32
布尔表达式： B→ B or B B→ B and B B→ not B B→(E） B→ id relop id B→ true B→ false
编译原理
自我介绍




姓名：辛明影 电话： 86413213 教研室：计算机软件基础 办公室：综合楼513 xmy63@ xmy63@
单丽丽，新技术楼608
2016/8/5计算机学院
辛明影
助课教师：洪晓鹏，综合楼614
2
开课目的及应用前景：介绍设计与构造程序设计语
后端处理对象是由前端产生的结果，即中 间代码 Java语言的编译采用的是前端后端方式。 前端生成与平台无关的字节码 后端是由与平台有关的解释器对所生成 的字节码文件进行解释执行
2016/8/5计算机学院
辛明影
21
二、编译的遍 编译的若干阶段通常是以一遍来实现 的，每遍读一次输入文件、产生一个输出 文件。
2016/8/5计算机学院
辛明影
18
符号表的实现 固定长标识符：采用前面的结构 不定长标识符：使用单独的数组lexemes 存放标识符的字符串,符号表中存放标识 符在lexemes的起始位臵和相应记号
If(12) Int(13) Id1(25) Id2(25)
i f eos i n t eos p o s i t i o n eos i n i t i a l eos
符号表上的操作： Insert(s,t):将符号串s和记号t插入符号
表，返回相应表项的指针 Lookup(s):在符号表中查找字符串s，查找 成功返回相应指针，否则返回0
2016/8/5计算机学院
辛明影
17
关键字的处理 通常情况下，将关键字存在符号表中， 作为符号表的初值。
当词法分析程序识别出一个标识符s后， 用lookup(s)查找符号表，如果是关键字， 返回相应的记号；如果是变量名，返回 记号id
2016/8/5计算机学院
辛明影
22
1.5错误检测与报告
在编译的各个阶段都会发现源程序中的错误， 为了使编译器能继续运行，以检测出源程序中 更多的错误，在检测到错误后，必须以合适的方式 进行错误处理。
error
2016/8/5计算机学院
辛明影
23
第二章
高级语言 及其语法描述
内容简介：
本章概述程序设计语言的结构 和主要 的共同特征， 并介绍程序设计语言主要语 句的文法描述与形式定义。
文法：S →dA
C →dC
E →dF A →dA A →eD A →.B B →dC
C →eD
F →dF
D → -E
F →d
D →+E
D →dF
12e5 0.1e24
3.14
d S d A
1000
2016/8/5计算机学院
e
10e+3 3.14e-5
d
B d
其它
C
e
其它
– + D d
辛明影
d
E d F
temp2=b+temp1
a=temp2
2016/8/5计算机学院
辛明影
13
代码生成阶段
生成可重定位的机器代码或汇编代码 Movf R2，c
Mulf R2,d
Movf R1,b
Addf R2,R1
Movf a,R2
2016/8/5计算机学院
辛明影
14
1.3符号表管理 int a,b;
float e,f
33
2016/8/5计算机学院
辛明影
赋值、分支、循环语句： S → id=E S → if B then S S → if B then S else S S → while B do S S →{ L } L → L ;S L→S
2016/8/5计算机学院
辛明影
34
调用语句： S→call id(Elist) Elist →Elist,E
2016/8/5计算机学院
辛明影
27
上述的定义是用文字来描述的，当设 计编译程序时，就要把它用形式的方式描 述出来，就要用到形式语言。 在现今多数程序设计语言中，单词符 号一般包括： 标识符、 基本字、 各类型的常数、 算符和界符等 正规式和有穷自动机是描述词法结 构和进行词法分析的有效工具
2016/8/5计算机学院
语法分析
在词法分析的基础上，根据语言的语法规则， 把单词符号串组成各类语法单位. 具体的说，语法分析是在单词流的基础上建立 一个层次结构-----建立语法树
标识符 a
赋值语句 =
表达式 标识符 b
表达式 + 表达式 表达式 * 表达式
标识符 c
辛明影
标识符
d
10
2016/8/5计算机学院
语义分析阶段
辛明影
38
2.2 构造基础 2.2.1 程序结构简介 一个高级语言程序通常由若干子程序段 （过程、函数等）组成， 许多语言还 引入了类、程序包等更高级的结构
2016/8/5计算机学院
辛明影
39
一. FORTRAN 一个FORTRAN 程序由一个主程序 和若干个辅助程序段组成
PROGRAM MAIN . END SUBROUTINE SUB1 . .END FUNCTION FUN1 . END
符号表是一个数据结构。 每个标识符在符号表中都有 一条记录 例：int a,b; 名字 a 记号 id1(25) 类型 int 种属 …… 简变 addr 0
b
id2(25)
int
辛明影
简变
4
16
2016/8/5计算机学院
符号表的接口： 符号表的作用就是存放字符串或词素 当一个字符串或词素被保存时，与之相对 应的记号也被保存
言编译程序的原理与方法 源程序 目标程序 可执行程序
编译 程序
预备知识：
2016/8/5计算机学院
How?
连接
两门以上的高 级程序设计语 言
形式语言与自动机、 汇编语言 数据结构等
辛明影
3
内容简介：
第一章：编译器的基本结构 第二章：高级语言及其语法描述 第三章：词法分析器 第四章：语法分析技术 第五章：语法制导翻译的主要概念及中间代码 第六章：程序运行时的存贮分配问题 第七章：代码优化 第八章：目标代码生成
辛明影
28
例：C语言标识符的文法描述 C语言的标识符的文法和自动机描述： 解：P:I →aB
B →aB
L（G）={w/w为字母或‘-‟打头的字母数字串}
I → -B
I →a
B →d
B →dB B→a a a,d B
识别L（G）的自动机
I
2016/8/5计算机学院
辛明影
其它
T
29
例：C语言实常数的文法描述
2.1 程序语言的定义
任何语言实现的基础是语言定义。
语言的定义决定了该语言 具有什么样的 语言功能、 什么样的数据结构、 什么样 的程序结构、 以及具体的使用形式等细 节问题。
2016/8/5计算机学院
辛明影