自动化系编译原理配套全册教学课件.ppt

1、自动化系编译原理配套全册自动化系编译原理配套全册 教学课件教学课件 第第2章章 高级语言及其语法描述高级语言及其语法描述 第第1章章 编译程序概论编译程序概论 第第3章章 词法分析词法分析 第第4章章 自上而下语法自上而下语法分析分析 第第5章章 自下而上语法分析自下而上语法分析 第第6章章 语义分析语义分析 第第7章章 符号表符号表 第第8章章 存储空间组织存储空间组织 第第9章章 优化优化 程程 序序 设设 计计 语语 言言 编编 译译 原原 理理 软件学院软件学院 易萍雯易萍雯 P P 教 材 程序设计语言编译原理程序设计语言编译原理第三版第三版 陈火旺、刘春林等，陈火旺、刘春林等， 国

2、防工业出版社，国防工业出版社，2000 主要参考资料主要参考资料 编译原理及实践编译原理及实践 Kenneth C. Louden，冯博琴 译 机械工业出版社 编译原理习题与解析编译原理习题与解析 伍春香 清华大学出版社 学时情况学时情况 总学时总学时 ： 64 64 学时学时 学学 分分 ： 3.53.5 讲讲 课课 ： 48 48 学时学时 上上 机机 ： 16 16 学时学时 考考 核核 平时作业：平时作业： 10%10% 上上 机：机： 10%10% 期末考试：期末考试： 80%80% 后续课程后续课程 编译原理课程设计专题实验编译原理课程设计专题实验 3232学时，学时，1.51.5

3、学分学分 第第1章章 编译程序概论编译程序概论 1.1 什么是编译程序什么是编译程序 1.2 编译过程概述编译过程概述 1.3 编译程序的结构编译程序的结构 1.4 编译程序的生成编译程序的生成 1.5 课程特征课程特征 1.1 1.1 什么是编译程序什么是编译程序 1.1.1 什么是什么是程序设计语言程序设计语言 计算机的工作体现为执行程序。计算机的工作体现为执行程序。 程序程序：控制计算机完成特定功能的一组：控制计算机完成特定功能的一组 有序命令。有序命令。 对于机器语言来说，命令被称为对于机器语言来说，命令被称为指令指令； 对于高级语言而言，命令被称为对于高级语言而言，命令被称为语句语句

4、。 程序设计语言程序设计语言（Programming Language） 通常泛指一切用于编写计算机程序的语言。通常泛指一切用于编写计算机程序的语言。 它是人与计算机之间进行信息交流的工具。它是人与计算机之间进行信息交流的工具。 包括包括 机器语言：采用二进制来表示机器语言：采用二进制来表示 （低级语言）（低级语言） 汇编语言：采用机器语言的助记符来表示汇编语言：采用机器语言的助记符来表示 (低级语言低级语言) 高级语言：采用完全符号形式化的方式来表示，高级语言：采用完全符号形式化的方式来表示， 它独立于具体的计算机硬件。它独立于具体的计算机硬件。 例：不同语言实现加法运算例：不同语言实现加法

5、运算 机器语言机器语言汇编语言汇编语言C语言语言 00000010 11001111ADD AX，BXc=a+b; 程序设计语言特性程序设计语言特性 语言语言优点优点缺点缺点 机器语言机器语言 处理简单处理简单 执行效率最高执行效率最高 程序不便于识别程序不便于识别 难以调试。难以调试。 汇编语言汇编语言 较易于理解较易于理解 执行效率高执行效率高 与机器相关与机器相关 可移植性差可移植性差 较难调试较难调试 高级语言高级语言 易于理解易于理解 易于调试易于调试 独立于具体的独立于具体的 计算机硬件计算机硬件 需要配套的编译程序需要配套的编译程序 ( (解释程序解释程序) ) 执行效率相对低执

6、行效率相对低 程序语言需要的支持环境程序语言需要的支持环境 计算机程序设计语言计算机程序设计语言 低级语言低级语言 高级高级 语言语言 机器机器 语言语言 汇编汇编 语言语言 计算机计算机 翻译翻译 程序程序 汇编程序汇编程序 编译程序编译程序 解释程序解释程序 1.1.2 高级高级 FORTRAN （FORmula TRANslation） 第一个被正式推广使用的计算机高级语言；第一个被正式推广使用的计算机高级语言； 适合数值计算，如提供了对矩阵数组的直接计算；适合数值计算，如提供了对矩阵数组的直接计算； 最早一批高级语言中，目前仍在使用的少数之一。最早一批高级语言中，目前仍在使用的少数之一

7、。 DO 7, LOOP =1 , 5 READ * , X , Y AVG = (X + Y ) / 2.0 PRINT * , X , Y, AVG 7 CONTINUE END 标识符隐式定义标识符隐式定义 对数学计算支持多对数学计算支持多( (复数复数) ) 存储管理手段多存储管理手段多( (公共公共, ,等价等价) ) 数据类型偏少，无字符串数据类型偏少，无字符串 等类型（早期）等类型（早期） 负面评价比较多负面评价比较多 LISP （LISt Processor） 基于基于演算的函数式编程语言；演算的函数式编程语言； 已经成为人工智能（已经成为人工智能（AIAI）的首选程序语言。）

8、的首选程序语言。 用作某些系统的内嵌语言，如用作某些系统的内嵌语言，如AUTOCADAUTOCAD中的中的AUTOLISPAUTOLISP。 最早一批高级语言中，目前仍在使用的少数之一。最早一批高级语言中，目前仍在使用的少数之一。 Defun length(x) (cond (null x ) 0) (t (+1 (length (cdr x) length (I love computer) 基本语法很简单，基本语法很简单， 但富于变化但富于变化 代码和数据使用相代码和数据使用相 同的结构来表示同的结构来表示 评价基本比较正面评价基本比较正面 x x是一个表是一个表 (cdr x) (cdr

9、 x) 返回返回x x中除第一个元素之外所中除第一个元素之外所 有元素组成的表有元素组成的表 结果：结果：3 3 PASCAL 发源于欧洲；发源于欧洲； 严格的结构化形式；严格的结构化形式； 丰富完备的数据类型；丰富完备的数据类型； 便于描述各种算法与便于描述各种算法与 数据结构；数据结构； 有益于培养初学者良有益于培养初学者良 好的程序设计风格和好的程序设计风格和 习惯。习惯。 Function gcd(m,n:integer):integer; var remainder:integer; begin while n0 do begin remainder:=m mod n; m:=n;

10、n:= remainder; end; gcd:=n end; C 为了为了UNIXUNIX操作系统所设计操作系统所设计 具有高阶的结构化叙述，也具备了类似低级语言具有高阶的结构化叙述，也具备了类似低级语言 控制硬件的能力控制硬件的能力 为目前最常被使用的高级语言为目前最常被使用的高级语言 Void swap(int *x, int *y) int temp; temp=*x ; *x = *y ; *y = temp; C+ 继承了继承了C C语言的全部内容语言的全部内容 增加了面向对象编程的增加了面向对象编程的 内容，引入类、对象和内容，引入类、对象和 方法的机制方法的机制 通过派生、继承

11、、重载通过派生、继承、重载 和多态性等特征，实现和多态性等特征，实现 软件复用。软件复用。 # include class MyClass public: MyClass(int a)x=a; int GetNum () return x; private: int x; ; int main() MyClass my(10); coutmy.GetNum() 1 and a.AccountNum 0 and a.AccountNum = c.AccountNum and a.ChargeID = b.ChargeID order by a.AccountNum, a.ChargeID, b.

12、ItemID; 美国美国SunSun公司于公司于19951995年年 发表发表 具备有面向对象的特性具备有面向对象的特性 提供了跨平台的功能提供了跨平台的功能 import java.awt.*; import java.applet.Applet; public class PointApplet extends Applet public Point p1, p2; public void init() p1 = new Point(); p2 = new Point(Color.blue); public void paint ( Graphics g ) p1.plotPoint(g,

13、 30, 15); p2.plotPoint(g, 100, 15); 源源 语语 言言 程程 序序 编译程序编译程序 词法分析词法分析 语法分析语法分析 语义分析语义分析 优化优化 目标代码生成目标代码生成 输入输入 计计 算算 结结 果果 运行运行 系统系统 目目 标标 语语 言言 程程 序序 源语言程序源语言程序 (高级语言程序高级语言程序) 解释程序解释程序 词法分析词法分析 语法分析语法分析 语句执行语句执行 计计 算算 结结 果果 输入输入 JAVA 源程序源程序 编译程序编译程序 JAVAC.EXEJAVAC.EXE 输入输入 计计 算算 结结 果果 解释程序解释程序 JVMJV

14、M 字节码字节码 程序程序 Java Java 程序执行程序执行 JVM JavaJVM Java虚拟机虚拟机 为不同的硬件平台提供了一种编译为不同的硬件平台提供了一种编译JavaJava代码的方代码的方 法，使法，使JavaJava软件独立于平台；软件独立于平台； JavaJava解释器、解释器、WebWeb浏览器均内置浏览器均内置JVMJVM； 1.1.5 编译编译 不同公司的产品不同公司的产品 对语言的外延对语言的外延( (系统函数，数据类型等系统函数，数据类型等) )定义不同。定义不同。 例如：对例如：对C+C+，目前使用比较广泛的有：，目前使用比较广泛的有： 免免 费费 / / 部分

15、部分 免费免费 Apple C+ Bloodshed Dev-C+ 基于GCC的(Mingw)IDE环境 Borland C+ Cygwin (GNU C+) MINGW - Minimalist GNU for Windows Windows版本的另一个GCC编译 器，包含了免费的w32api(非 GPL许可) GNU CC source Intel C+ for linux Borland C+ Compaq C+ Digital Mars C+ Edison Design Group C+ Front End 被许多C+编译器厂商采用 Green Hills C+ 支持嵌入式系统平台 H

16、P C+ IBM C+ Intel C+ 支持Windows, Linux, 嵌入式系统 Interstron C+ Metrowerks C+ 支持多平台 Microsoft C+ Paradigm C+ 支持x86嵌入式系统 The Portland Group C+ 针对奔腾CPU优化 SGI C+ 优化的编译器 收收 费费 多种版本，特性不同多种版本，特性不同 注重程序开发注重程序开发 带集成调试环境的带集成调试环境的 （即：可以编辑，编译，执行，调试）（即：可以编辑，编译，执行，调试） 注重程序调试注重程序调试 诊断编译程序诊断编译程序 注重提高目标代码效率注重提高目标代码效率 优化

17、编译程序优化编译程序 注重运行环境注重运行环境 注重使用方便性注重使用方便性 提供者提供者 标准化标准化( (与与C+C+标标 准的兼容性准的兼容性) ) 优点优点不足不足 Borland Borland C+C+ Borland Borland C+ Builder 5.5版 92.73% 速度快， 空间效率 高 某些版本 不稳定 Borland C+ Builder X 6.0 100%符合 ANSI/ISO的C+ 以及C99标准。 Visual Visual C+C+ MSVisual Studio 6.0版 83.43% 开发环境 强大 标准化低 7.1版 98.22% GNU C+G

18、NU C+开源Mingw、 Cygwin、 Djgpp 等 GCC3.3 96.15% 移植性好 跨平台 嵌入式 代码规模、 速度略差 Intel Intel C+C+ Intel 对:Intel x86结构的CPU经过特别优化, 数值计算等应用能大幅度提高性能。 特定机型 其他评价指标：其他评价指标：开发环境，库，帮助，调试工具等开发环境，库，帮助，调试工具等 C+ C+ 主要编译器特性主要编译器特性 1.2 编译编译 分析阶段分析阶段 主要工作主要工作 词法分析词法分析 扫描源程序扫描源程序 识别出输入流中的每一个单词；一般用二识别出输入流中的每一个单词；一般用二 元组（单词类别，属性值）

19、来表示。元组（单词类别，属性值）来表示。 不合乎不合乎词法规则词法规则的输入流，报：词法错误的输入流，报：词法错误 语法分析语法分析 分析出句子的语法结构。一般用树分析出句子的语法结构。一般用树 （语法树）来表示。（语法树）来表示。 不合乎不合乎语法规则语法规则的输入流，报：语法错误的输入流，报：语法错误 分析阶段分析阶段主要工作主要工作 语义分析语义分析 根据句子的语法含义，生成中间根据句子的语法含义，生成中间 语言的代码序列语言的代码序列 优化优化 对中间代码加工，以产生高效的对中间代码加工，以产生高效的 中间代码中间代码( (时间，空间时间，空间) ) 目标代码生成目标代码生成 将中间代

20、码转换成（特定机器的）将中间代码转换成（特定机器的） 目标代码目标代码 其中：代码优化不是必须的。其中：代码优化不是必须的。 1.2.1 词法分析工作词法分析工作 识别的标准：词法规则。识别的标准：词法规则。 保留字保留字构成形式：字母打头的字母数字串，如：构成形式：字母打头的字母数字串，如：if if 运算符运算符构成形式：构成形式：* *）单一符号构成，）单一符号构成，如：如：+ + ， ，* * * *）连续的两个符号构成，）连续的两个符号构成，如：如： :=:= 扫描源程序扫描源程序 识别出输入流中的每一个单词；一般用二元组识别出输入流中的每一个单词；一般用二元组 （单词类别，属性值）

21、来表示。（单词类别，属性值）来表示。 不合乎不合乎词法规则词法规则的输入流，报：词法错误的输入流，报：词法错误 例：例： if M+3N then z:=x+10if M+3N then z:=x+10* *y else z:=xy else z:=x* *2020 1. 1. 保留字保留字 ifif 2. 2. 标识符标识符 M M 3. 3. 加号加号 + + 4. 4. 整数整数 3 3 5. 5. 大于号大于号 6. 6. 标识符标识符 N N 7. 7. 保留字保留字 thenthen 8. 8. 标识符标识符 z z 9. 9. 赋值号赋值号 :=:= 10. 10. 标识符标识符

22、 x x 11. 11. 加号加号 + + 12.12. 整数整数 1010 13.13. 乘号乘号 * * 14.14. 标识符标识符 y y 15.15. 保留字保留字 elseelse 16.16. 标识符标识符 z z 17.17. 赋值号赋值号 :=:= 18.18. 标识符标识符 x x 19.19. 乘号乘号 * * 20.20. 整数整数 2020 词法分析结果集合词法分析结果集合 1.2.2 语法分析工作语法分析工作 分析出句子的语法结构。一般用语法树表示；分析出句子的语法结构。一般用语法树表示； 不合乎不合乎语法规则语法规则的输入流，报：语法错误。的输入流，报：语法错误。

23、识别的标准：语言的文法规则。识别的标准：语言的文法规则。 例：文法例：文法GSGS： S A:=E |S A:=E | if E then Sif E then S1 1 else S else S2 2 语句 语句 E E+E | E-E | EE E+E | E-E | E* *E | E/E | E op E |i E | E/E | E op E |i 表达式表达式 op = | |=|= op = | |=| N if M+3 N then z:=x+10 then z:=x+10* *y y else z:=x else z:=x* *2020 GSGS： S A:=ES A:=E

24、 | if E then Sif E then S1 1 else S else S2 2 E E+E | E-E | E E E+E | E-E | E* *E | E/EE | E/E | E op E |i | E op E |i op = | |=|= op = | |=| N then z:=x+10if M+3 N then z:=x+10* *y else z:=xy else z:=x* *2020 100 (+ , M , 3, T1) 101 (j , T1, N, 103) 102 (j , _ , _ , 107) 103 (* , 10, y, T2) 104 (+

25、, x, T2, T3) 105 (:= , T3, _ , z) 106 (j , _ , _ , 109) 107 (* , x, 20, T4) 108 (:= , T4, _ , z) 109 . 1.2.4 优化工作优化工作 对中间代码加工，以产生高效的中间代码对中间代码加工，以产生高效的中间代码 ( (时间，空间时间，空间) ) 优化的依据优化的依据 等价变换规则等价变换规则 T1:=2*3.14 T2:=T1*r l:=T2 2 2* *3.143.14的值在编译时就可以确定的值在编译时就可以确定 T2:=6.28*r l:=T2 例：例：l =2*3.14*r 1.2.5 目标

26、代码生成目标代码生成 任务：任务：把中间代码变换成特定机器上的绝对把中间代码变换成特定机器上的绝对 指令代码、或可重定位的指令代码、指令代码、或可重定位的指令代码、 或汇编指令代码。或汇编指令代码。 特点特点：与硬件系统结构和指令含义有关，涉及与硬件系统结构和指令含义有关，涉及 到硬件系统功能部件的运用、机器指令到硬件系统功能部件的运用、机器指令 的选择、各种数据类型变量的存储空间的选择、各种数据类型变量的存储空间 分配、寄存器和后缓寄存器的调度等。分配、寄存器和后缓寄存器的调度等。 解释程序的工作解释程序的工作 例：例： if M+3 N if M+3 N then z:=x+10 then

27、 z:=x+10* *y y else z:=x else z:=x* *2020 1. 词法分析：词法分析：识别出单词符号；识别出单词符号； 2. 语法分析语法分析：得到语法树；得到语法树； 3. 计算，求出结果；计算，求出结果； 设：设：m=10,n=4,x=5,y=6 m=10,n=4,x=5,y=6 结果为：结果为：Z:=65Z:=65 （ 5+105+10* *6 6 ） 1.3 编译编译 1.3.1 编译程序的总框编译程序的总框 表表 格格 管管 理理 程程 序序 词法分析程序词法分析程序 语法分析程序语法分析程序 语义分析程序语义分析程序 代码优化程序代码优化程序 目标代码生成程

28、序目标代码生成程序 出出 错错 处处 理理 程程 序序 源程序源程序 目标程序目标程序 单词符号集单词符号集 语法单位集语法单位集 中间代码程序中间代码程序 中间代码程序中间代码程序 存放内容存放内容：用户程序的资料。用户程序的资料。 变量变量 定义的模块，类型，相对地址定义的模块，类型，相对地址 数组数组 名字，下标类型及范围，基类型。名字，下标类型及范围，基类型。 函数函数 函数名，返回类型，参数。函数名，返回类型，参数。 处理方式处理方式：编译程序有一组专门的表格管理程序，用于编译程序有一组专门的表格管理程序，用于 完成表格的查找，填写工作。完成表格的查找，填写工作。 使用：使用：编译的

29、各阶段都要使用。但使用的信息种类有所编译的各阶段都要使用。但使用的信息种类有所 不同，使用方式也有所不同（填写不同，使用方式也有所不同（填写/ /查找）。查找）。 词法分析词法分析 构成单词的字符如：构成单词的字符如：x,yx,y、 语法分析语法分析 单词符号的类别单词符号的类别, ,如：是否为标识符如：是否为标识符 （是（是x,x,或或y y没有关系）。没有关系）。 表格管理表格管理 对出错处理的希望：对出错处理的希望： 尽量准确的指出错误的位置，性质。尽量准确的指出错误的位置，性质。 发现错误后，还可以继续编译，以便最大限度的发现错误后，还可以继续编译，以便最大限度的 发现源程序中的错误。

30、发现源程序中的错误。 处理方法：跳过一段源程序再接着分析。处理方法：跳过一段源程序再接着分析。 有些编译程序：发现一个错误就停止编译。有些编译程序：发现一个错误就停止编译。 将错误造成的影响限制在尽量小的范围。将错误造成的影响限制在尽量小的范围。 如：变量未定义，只报一次错。如：变量未定义，只报一次错。 自动校正。（困难，代价高）。自动校正。（困难，代价高）。 出错处理出错处理 1.3.2 1.3.2 编译的编译的“前端前端”，“后后 端端” 前端（前端（front end）： 主要依赖于源语言而与目标机器无关的编译阶段。主要依赖于源语言而与目标机器无关的编译阶段。 如：词法分析、语法分析、语

31、义分析、部分优化工如：词法分析、语法分析、语义分析、部分优化工 作、与前端有关的出错处理工作和符号表管理工作。作、与前端有关的出错处理工作和符号表管理工作。 后端（后端（back end）： 依赖于目标机而一般不依赖于源语言，只与中间代依赖于目标机而一般不依赖于源语言，只与中间代 码有关的编译阶段。如：目标代码生成、部分优化码有关的编译阶段。如：目标代码生成、部分优化 工作、工作、 以及相关出错处理和符号表操作。以及相关出错处理和符号表操作。 1.3.3 1.3.3 遍遍 （趟，（趟，passpass） 对源程序或其等价的中间结果从头到尾扫描并完成对源程序或其等价的中间结果从头到尾扫描并完成

32、规定任务的过程。每一遍扫描可完成上述一个阶段规定任务的过程。每一遍扫描可完成上述一个阶段 或多个阶段的工作。或多个阶段的工作。 分遍的原因：分遍的原因： 编译程序一般较大，运行时需要的系统资源较编译程序一般较大，运行时需要的系统资源较 多（主要是内存。包括：编译程序占用的空间多（主要是内存。包括：编译程序占用的空间 数据空间）。机器满足不了要求。数据空间）。机器满足不了要求。 某些语言，先引用，再定义。多遍编译好处理。某些语言，先引用，再定义。多遍编译好处理。 分遍的原则：分遍的原则： 每一遍的功能相对明确；每一遍的功能相对明确； 各各“遍遍”之间，之间，程序接口尽量简单，交接的数据程序接口尽

33、量简单，交接的数据 尽量尽量少；少； 多遍编译时，一般用多遍编译时，一般用文件文件的方式在各遍之间传递数据。的方式在各遍之间传递数据。 每一遍的工作：每一遍的工作： 从文件中读取前一遍的工作结果从文件中读取前一遍的工作结果 = = 完成本遍的功能完成本遍的功能 = = 将结果写入到文件中，供下一遍使用。将结果写入到文件中，供下一遍使用。 词法分析器词法分析器语法分析器语法分析器 语义分析器语义分析器 代码优化器代码优化器 目标代码生成器目标代码生成器 源程序源程序 目标代码程序目标代码程序 预处理器预处理器 典型的四遍编译过程典型的四遍编译过程 第第1 1遍遍 源程序源程序 第第2 2遍遍 第

34、第4 4遍遍 第第3 3遍遍 中间代码程序中间代码程序 中间代码程序中间代码程序 1.4 编译程序的生成编译程序的生成 1.1.写出全部代码写出全部代码 用机器语言编写；用机器语言编写； 用汇编语言编写；（或编译程序核心部分采用用汇编语言编写；（或编译程序核心部分采用 汇编语言编写，以保证系统的运行效率）汇编语言编写，以保证系统的运行效率） 用高级语言编写；（这是普遍采用的方法）用高级语言编写；（这是普遍采用的方法） 2.2.自编译自编译 用被编译的语言来书写该语言自身的编译程序用被编译的语言来书写该语言自身的编译程序 3.3.移植移植 同种语言的编译程序在不同类型的机器之间移植。同种语言的编

35、译程序在不同类型的机器之间移植。 交叉编译：交叉编译：就是在一种平台上编译出能运行在体就是在一种平台上编译出能运行在体 系结构不同的另一种平台上的目标程序。系结构不同的另一种平台上的目标程序。 如：在如：在PCPC平台上编译出能运行在单片机平台上的程平台上编译出能运行在单片机平台上的程 序（但该程序在序（但该程序在PCPC平台上不能运行）。平台上不能运行）。 在异平台移植开发时普遍使用（如：嵌入式）。在异平台移植开发时普遍使用（如：嵌入式）。 4.4.自动构造工具自动构造工具 LEX (LEX (词法分析词法分析) ) YACC ( YACC (语法分析，用于自动产生语法分析，用于自动产生LA

36、LRLALR分析表分析表) ) 学习要点学习要点 注意理论、概念的理解及应用。注意理论、概念的理解及应用。 定义、公式、适用情况、限制等。定义、公式、适用情况、限制等。 基础知识的使用。基础知识的使用。 离散数学，数据结构等课程的内容，如：离散数学，数据结构等课程的内容，如： 栈，队列，树，图，集合，代数系统等。栈，队列，树，图，集合，代数系统等。 注意各章节之间的关联。注意各章节之间的关联。 注重平时的积累，作业练习等。注重平时的积累，作业练习等。 1.5 课程特征课程特征 课程主要内容课程主要内容： 编译程序的构造原理，构造方法，实现技术。编译程序的构造原理，构造方法，实现技术。 由于编译

37、程序是比较经典的系统程序，因此反映了软由于编译程序是比较经典的系统程序，因此反映了软 件发展的各个阶段中，人们对软件的理解的变迁。件发展的各个阶段中，人们对软件的理解的变迁。 程序设计程序设计 语言语言 离散数学离散数学 数据结构数据结构 编译原理编译原理 操作系统操作系统 系统软件系统软件 数据库数据库 地位地位 为什么学编译原理为什么学编译原理 1. 1. 涉及计算机学科中，许多抽象问题、解决问题涉及计算机学科中，许多抽象问题、解决问题 的思路和方法；的思路和方法； 2.2.掌握程序语言的内部实现机理掌握程序语言的内部实现机理, ,对程序语言的理对程序语言的理 解更加深入全面；解更加深入全

38、面； 3.3.课程中包含了很多软件技术课程中包含了很多软件技术, ,是专业经验积累的是专业经验积累的 一种途径。一种途径。 作作 业业 1.1.编译过程一般分为编译过程一般分为5 5个阶段，分别完个阶段，分别完 成什么分析？每个阶段的输入、输出成什么分析？每个阶段的输入、输出 是什么？是什么？ 2.2.什么是什么是“遍遍”？如果把编译程序分成？如果把编译程序分成3 3 遍，你会如何划分？每一遍，你会如何划分？每一“遍遍”的输的输 入、输出分别是什么？入、输出分别是什么？ 第第2章章 高级语言及其语法描述高级语言及其语法描述 2.1 编译程序需要重点考虑的程序语言特性 2.2 符号和符号串 2.

39、3 上下文无关文法 2.4 语法树和二义性 2.5 形式语言介绍 2.1 2.1 编译程序需要重点考虑的程序语言特性编译程序需要重点考虑的程序语言特性 1. 标识符与名字标识符与名字 标识符：字母打头的字母数字串。 名字：用标识符表示的，带有类型、值域的 程序语言对象。 高级语言之间的差异也是在这里体现的。 例： aa 标识符 real aa 名字，实型变量， 值域、运算确定。 2. 名字的定义名字的定义 影响 - 目标程序的执行效率的高低。 能否静态分配存储空间； 能否作静态语义检查 类型类型 名字定义方式名字定义方式典型语言典型语言 显式定义显式定义名字的类型必须定义名字的类型必须定义C,

40、 PascalC, Pascal 隐式定义隐式定义 名字的类型可以定义或者不定义名字的类型可以定义或者不定义, ,未定未定 义的名字的类型按照缺省定义处理。义的名字的类型按照缺省定义处理。 FORTRANFORTRAN (I-N(I-N规则规则) ) 不定义不定义 名字的类型不必定义。根据运行时名名字的类型不必定义。根据运行时名 字的取值动态确定。字的取值动态确定。 早期的早期的BASIC,BASIC, VFPVFP 例： int aa aa=12.3； 类型错误（静态语义检查） 全程变量：主程序中定义。 局部变量：过程/函数/分程序/对象 中定义。 影响： 3.变量的作用域 存储空间能否复用

41、。 变量重名时的实现方法。 如：采用最小作用域原则。 4.语义 同一语句，在不同的语言中的含义可能不同。 例：数组 A1.3,1.4，访问: A2,3 Pascal：按行分配 a11a11 a12a12 a13a13 a14a141 1 a21a21 a22a22 a23a23 a24a242 2 a31a31 a32a32 a33a33 a34a343 3 a11a11a12a12a13a13a14a14 a21a21a22a22a23a23a24a24 a31a31a32a32a33a33a34a34 1 12 23 34 4 FORTRAN：按列分配 a23地址=a11地址+7访问: a

42、23地址=a11地址+6 5.5.支持的数据类型，类型中允许的运算支持的数据类型，类型中允许的运算 基本数据类型: 整型，实型，布尔，字符，字符串 复杂数据类型： 数组，记录，结构，指针，集合,类 6.支持的语句 分支、循环、过程、函数 7. 存储空间分配方式 静态存储分配 动态存储分配 函数：允许递归调用时，每一次调用 需要一片数据区 动态数组 动态创建对象 用户可动态申请/释放数据空间 2.2 符号和符号串符号和符号串 1.字母表: 元素的非空、有穷集合。 2.符号：字母表中的元素。 例1: V=a,b,c 字母表 V 符号 a ，b , c 例2：单词符号集=if,then,begin,

43、标识符,+,-, 字母表 单词符号集 符号 if,then,begin,标识符,+,-, 3.符号串：符号组成的任何有穷序列。不包括任 何符号的符号串称为空串（空字），记为。 注：符号串中符号的顺序是重要的。 例1: V=a,b,c 符号串：a,b,c,ab,ba,cc,aab 其中：abba 例2:单词符号集=if,then,begin,，标识符，+,-, 程序：由上述符号构成的一个符号串 但：任一符号串不一定是合法的程序。 编译研究：什么样的符号串是合法的程序。 4. 串的长度: 设是字母表V中的符号串， 的长度=中符号的个数。记为：| 5. 串的联结： 设、是字母表V中的符号串，联结是指

44、： 将放在之后形成的符号串，记为： 例: V=a,b,c， 且有：=ab , =bca 则： = abbca ， = bcaab |=2, |=5 特别： , |= 0 6. 符号串集合： 由符号串构成的集合，记为： A= x | xA 7. 符号串集合的乘积: 若A,B是V上的符号串集合，A,B的乘积定义 为： AB= | A ,B 例: 若： A=ab,ba, B=ca,acb 则： AB=abca, abacb, baca, baacb = = A = A = A 8.符号串的方幂： 对任意符号串， 0 = 1 = 2 = n =n-1 (n0) 例: =ab 则：0 =， 1 =ab

45、， 2 = abab ， 3 = ababab 例: V=a,b,c V0 = 长度=0 的符号串的集合 V1 =a,b,c 长度=1 的符号串的集合 V2 =aa,ab,ac,ba,bb,bc,ca,cb,cc长度=2 的符号串的集合 V3 =aaa,aab,aac,aba,abb,abc长度=3 的符号串的集合 V100 长度=100 的符号串的集合 Vn 长度=n 的符号串的集合 9. 集合V的方幂：对任意集合V， V0 = ， V1 = V ， V2 = V V ， V3 = V V V Vn = V Vn-1 (n0) 10. 集合的闭包： 设V为集合， V+ = V1 V2 V3

46、Vn 正闭包 V* = V0 V1 V2 V3 Vn 闭包 两种闭包之间的关系： V* = V0 V+ V+ = V V* = V* V 两个集合的乘积 2.3 上下文无关文法上下文无关文法 1.产生式（产生规则，简称规则）： 一个有序对（A，），通常写作： A= 或 A A：符号，称为产生式左部； ：符号串，称为：产生式右部， 或：产生式的候选式 产生式的书写方式称为：BNF范式 若有产生式： A1 A2 An 写成：A1|2| |n 候选式 元符号 ：定义为 | ：或 2. 文法GS： 产生式的非空有穷集合，S是一个符号，它 至少要在一条产生式中作为左部出现，称为 识别符号或开始符号，出现

47、在产生式左部 和右部中的所有符号形成字母表 V。 例: GE E E + T | T T T * F | F F i | (E) V = E , + , T, *, F, i, ( , ) 产生式 识别符号或开始符号 3. 非终结符号： 给定文法G，把作为产生式左部出现的那些符 号称为非终结符号，或语法实体，所有非终 结符号汇集成：非终结符号集，记为：VN 。 例: GE E E + T | T T T * F | F F i | (E) - V = E , + , T, *, F, i, ( , ) VN = E, T, F 左 部 4. 终结符号： 给定文法G，产生式中不属于VN 的那些符

48、 号称为终结符号，所有终结符号汇集成： 终结符号集，记为：VT 。 由定义知：V = VN VT ，VN VT = 例: GE: E E + T | T T T * F | F F i | (E) V = E , + , T, *, F, i, ( , ) VN = E, T, F ， VT = + , *, i, ( , ) 5. 上下文无关文法的形式定义： 上下文无关文法是一个四元组 GS = (VN , VT , P , S ) 其中：VN 非终结符号集合 VT 终结符号集合 P 产生式集合 S 文法的识别符号（开始符号） 6. 直接推导、直接归约： 令G为文法，、为符号串，若：A 是一

49、个产生式，称：A直接推导出 ，或直接归约为A。 记为：A= 例: GE: E E + E | EE | E * E | (E) | i 推导: E = E + E ( = , = ) E + E = E * E + E ( = , = + E ) i * E + E = i * i + E ( = i* , = + E ) E * E + i = E * i + i ( = E* , = + i ) 7. 推导、归约：若存在一个直接推导序列 1 =2 =3 = =n 称：1 可以出推导n ,或n可归约为1 记为： 1 n （推导步骤0步，读作：+号推导出） = 或 ，表示推导步骤0步， （读作

50、：*号推导出） 即： 例: GE: E E + E | EE | E * E | (E) | i 从 E + E 到 i * i + i 的几种可能推导： E + E =E * E + E =i * E + E =i * i + E =i * i + i E + E =E + i =E * E + i =E * i + i =i * i + i E + E =E * E + E =E * E + i =E * i + i =i * i + i E + E =E * E + E =E * i + E =E * i + i =i * i + i 8. 最左推导、最右推导：推导中若每一步直接推导，