编译原理全册配套完整课件.ppt

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

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

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

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

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

6、级语言语言机器机器语言语言 汇编汇编语言语言计算机计算机翻译翻译程序程序 汇编程序汇编程序 编译程序编译程序解释程序解释程序 1.1.2 高级高级FORTRAN （FORmula TRANslation） 第一个被正式推广使用的计算机高级语言；第一个被正式推广使用的计算机高级语言； 适合数值计算，如提供了对矩阵数组的直接计算；适合数值计算，如提供了对矩阵数组的直接计算； 最早一批高级语言中，目前仍在使用的少数之一。最早一批高级语言中，目前仍在使用的少数之一。DO 7, LOOP =1 , 5 READ * , X , Y AVG = (X + Y ) / 2.0 PRINT * , X , Y

7、, AVG7 CONTINUE END标识符隐式定义标识符隐式定义对数学计算支持多对数学计算支持多( (复数复数) )存储管理手段多存储管理手段多( (公共公共, ,等价等价) )数据类型偏少，无字符串数据类型偏少，无字符串 等类型（早期）等类型（早期）负面评价比较多负面评价比较多LISP （LISt Processor） 基于基于演算的函数式编程语言；演算的函数式编程语言； 已经成为人工智能（已经成为人工智能（AIAI）的首选程序语言。）的首选程序语言。 用作某些系统的内嵌语言，如用作某些系统的内嵌语言，如AUTOCADAUTOCAD中的中的AUTOLISPAUTOLISP。 最早一批高级语

8、言中，目前仍在使用的少数之一。最早一批高级语言中，目前仍在使用的少数之一。 Defun length(x) (cond (null x ) 0) (t (+1 (length (cdr x) length (I love computer) 基本语法很简单，基本语法很简单， 但富于变化但富于变化 代码和数据使用相代码和数据使用相 同的结构来表示同的结构来表示 评价基本比较正面评价基本比较正面 x x是一个表是一个表(cdr x) (cdr x) 返回返回x x中除第一个元素之外所中除第一个元素之外所有元素组成的表有元素组成的表结果：结果：3 3PASCAL 发源于欧洲；发源于欧洲； 严格的结构

9、化形式；严格的结构化形式； 丰富完备的数据类型；丰富完备的数据类型； 便于描述各种算法与便于描述各种算法与数据结构；数据结构； 有益于培养初学者良有益于培养初学者良好的程序设计风格和好的程序设计风格和习惯。习惯。 Function gcd(m,n:integer):integer; var remainder:integer; begin while n0 do begin remainder:=m mod n; m:=n; n:= remainder; end; gcd:=n end;C 为了为了UNIXUNIX操作系统所设计操作系统所设计 具有高阶的结构化叙述，也具备了类似低级语言具有高阶

10、的结构化叙述，也具备了类似低级语言控制硬件的能力控制硬件的能力 为目前最常被使用的高级语言为目前最常被使用的高级语言 Void swap(int *x, int *y) int temp; temp=*x ; *x = *y ; *y = temp; C+ 继承了继承了C C语言的全部内容语言的全部内容 增加了面向对象编程的增加了面向对象编程的内容，引入类、对象和内容，引入类、对象和方法的机制方法的机制 通过派生、继承、重载通过派生、继承、重载和多态性等特征，实现和多态性等特征，实现软件复用。软件复用。# include class MyClasspublic: MyClass(int a)x

11、=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.ItemID; 美国美国SunSun公司于公司于19951995年年发表发表 具备有面向对象的特性具备有面向对象的特性 提供了跨平台的功能提供了跨平台的功能import java.awt.*;i

12、mport 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, 30, 15); p2.plotPoint(g, 100, 15); 源源语语言言程程序序编译程序编译程序词法分析词法分析语法分析语法分析语义分析语义分析优化优化目标代码生成目标代码生成输入输入计计算

13、算结结果果运行运行系统系统目目标标语语言言程程序序源语言程序源语言程序(高级语言程序高级语言程序)解释程序解释程序词法分析词法分析语法分析语法分析语句执行语句执行计计算算结结果果输入输入JAVA源程序源程序编译程序编译程序JAVAC.EXEJAVAC.EXE输入输入计计算算结结果果解释程序解释程序JVMJVM字节码字节码程序程序Java Java 程序执行程序执行JVM JavaJVM Java虚拟机虚拟机 为不同的硬件平台提供了一种编译为不同的硬件平台提供了一种编译JavaJava代码的方代码的方法，使法，使JavaJava软件独立于平台；软件独立于平台； JavaJava解释器、解释器、W

14、ebWeb浏览器均内置浏览器均内置JVMJVM；1.1.5 编译编译不同公司的产品不同公司的产品 对语言的外延对语言的外延( (系统函数，数据类型等系统函数，数据类型等) )定义不同。定义不同。 例如：对例如：对C+C+，目前使用比较广泛的有：，目前使用比较广泛的有： 免免费费/ / 部分部分免费免费Apple C+ Bloodshed Dev-C+ 基于GCC的(Mingw)IDE环境Borland C+Cygwin (GNU C+) MINGW - Minimalist GNU for WindowsWindows版本的另一个GCC编译器，包含了免费的w32api(非GPL许可)GNU C

15、C sourceIntel C+ for linuxBorland C+Compaq C+Digital Mars C+Edison Design Group C+ Front End 被许多C+编译器厂商采用Green Hills C+ 支持嵌入式系统平台HP C+IBM C+Intel C+ 支持Windows, Linux, 嵌入式系统Interstron C+Metrowerks C+ 支持多平台Microsoft C+Paradigm C+ 支持x86嵌入式系统The Portland Group C+ 针对奔腾CPU优化SGI C+ 优化的编译器 收收费费多种版本，特性不同多种版本

16、，特性不同 注重程序开发注重程序开发 带集成调试环境的带集成调试环境的 （即：可以编辑，编译，执行，调试）（即：可以编辑，编译，执行，调试） 注重程序调试注重程序调试 诊断编译程序诊断编译程序 注重提高目标代码效率注重提高目标代码效率 优化编译程序优化编译程序 注重运行环境注重运行环境 注重使用方便性注重使用方便性提供者提供者标准化标准化( (与与C+C+标标准的兼容性准的兼容性) )优点优点不足不足Borland Borland C+C+Borland Borland C+ Builder5.5版 92.73%速度快，空间效率高某些版本不稳定Borland C+Builder X6.0 10

17、0%符合ANSI/ISO的C+以及C99标准。Visual Visual C+C+MSVisual Studio6.0版 83.43%开发环境强大标准化低7.1版 98.22%GNU C+GNU C+开源Mingw、Cygwin、 Djgpp 等GCC3.3 96.15% 移植性好跨平台嵌入式代码规模、速度略差Intel Intel C+C+Intel 对:Intel x86结构的CPU经过特别优化, 数值计算等应用能大幅度提高性能。特定机型其他评价指标：其他评价指标：开发环境，库，帮助，调试工具等开发环境，库，帮助，调试工具等 C+ C+ 主要编译器特性主要编译器特性1.2 编译编译分析阶段

18、分析阶段主要工作主要工作 词法分析词法分析 扫描源程序扫描源程序 识别出输入流中的每一个单词；一般用二识别出输入流中的每一个单词；一般用二 元组（单词类别，属性值）来表示。元组（单词类别，属性值）来表示。 不合乎不合乎词法规则词法规则的输入流，报：词法错误的输入流，报：词法错误语法分析语法分析 分析出句子的语法结构。一般用树分析出句子的语法结构。一般用树 （语法树）来表示。（语法树）来表示。 不合乎不合乎语法规则语法规则的输入流，报：语法错误的输入流，报：语法错误分析阶段分析阶段主要工作主要工作 语义分析语义分析根据句子的语法含义，生成中间根据句子的语法含义，生成中间语言的代码序列语言的代码序

19、列 优化优化 对中间代码加工，以产生高效的对中间代码加工，以产生高效的中间代码中间代码( (时间，空间时间，空间) )目标代码生成目标代码生成 将中间代码转换成（特定机器的）将中间代码转换成（特定机器的）目标代码目标代码 其中：代码优化不是必须的。其中：代码优化不是必须的。1.2.1 词法分析工作词法分析工作识别的标准：词法规则。识别的标准：词法规则。 保留字保留字构成形式：字母打头的字母数字串，如：构成形式：字母打头的字母数字串，如：if if 运算符运算符构成形式：构成形式：* *）单一符号构成，）单一符号构成，如：如：+ + ， ，* * * *）连续的两个符号构成，）连续的两个符号构成

20、，如：如： :=:= 扫描源程序扫描源程序 识别出输入流中的每一个单词；一般用二元组识别出输入流中的每一个单词；一般用二元组 （单词类别，属性值）来表示。（单词类别，属性值）来表示。 不合乎不合乎词法规则词法规则的输入流，报：词法错误的输入流，报：词法错误例：例： if M+3N then z:=x+10if M+3N then z:=x+10* *y else z:=xy else z:=x* *20201. 1. 保留字保留字 ifif2. 2. 标识符标识符 M M3. 3. 加号加号 + +4. 4. 整数整数 3 35. 5. 大于号大于号 6. 6. 标识符标识符 N N7. 7.

21、 保留字保留字 thenthen8. 8. 标识符标识符 z z9. 9. 赋值号赋值号 :=:=10. 10. 标识符标识符 x x11. 11. 加号加号 + +12.12. 整数整数 101013.13. 乘号乘号 * *14.14. 标识符标识符 y y15.15. 保留字保留字 elseelse16.16. 标识符标识符 z z17.17. 赋值号赋值号 :=:=18.18. 标识符标识符 x x19.19. 乘号乘号 * *20.20. 整数整数 2020词法分析结果集合词法分析结果集合1.2.2 语法分析工作语法分析工作 分析出句子的语法结构。一般用语法树表示；分析出句子的语法结

22、构。一般用语法树表示； 不合乎不合乎语法规则语法规则的输入流，报：语法错误。的输入流，报：语法错误。识别的标准：语言的文法规则。识别的标准：语言的文法规则。例：文法例：文法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

23、 y else z:=x else z:=x* *2020 GSGS： S A:=ES A:=E | 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

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

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

26、 N then z:=x+10 then z:=x+10* *y y else z:=x else z:=x* *20201. 词法分析：词法分析：识别出单词符号；识别出单词符号；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 编译程序的总框编译程序的总框 表表 格格 管管 理理 程程 序序词法分析程序词法分析程序语法分析程序语法分析程序语义分析程序语义分析程序代码优化程序代码优化

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

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

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

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

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

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

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

34、是在一种平台上编译出能运行在体系结构不同的另一种平台上的目标程序。系结构不同的另一种平台上的目标程序。如：在如：在PCPC平台上编译出能运行在单片机平台上的程平台上编译出能运行在单片机平台上的程序（但该程序在序（但该程序在PCPC平台上不能运行）。平台上不能运行）。在异平台移植开发时普遍使用（如：嵌入式）。在异平台移植开发时普遍使用（如：嵌入式）。4.4.自动构造工具自动构造工具 LEX (LEX (词法分析词法分析) ) YACC ( YACC (语法分析，用于自动产生语法分析，用于自动产生LALRLALR分析表分析表) )学习要点学习要点 注意理论、概念的理解及应用。注意理论、概念的理解及

35、应用。 定义、公式、适用情况、限制等。定义、公式、适用情况、限制等。 基础知识的使用。基础知识的使用。离散数学，数据结构等课程的内容，如：离散数学，数据结构等课程的内容，如：栈，队列，树，图，集合，代数系统等。栈，队列，树，图，集合，代数系统等。 注意各章节之间的关联。注意各章节之间的关联。 注重平时的积累，作业练习等。注重平时的积累，作业练习等。1.5 课程特征课程特征课程主要内容课程主要内容： 编译程序的构造原理，构造方法，实现技术。编译程序的构造原理，构造方法，实现技术。由于编译程序是比较经典的系统程序，因此反映了软由于编译程序是比较经典的系统程序，因此反映了软件发展的各个阶段中，人们对

36、软件的理解的变迁。件发展的各个阶段中，人们对软件的理解的变迁。 程序设计程序设计语言语言离散数学离散数学数据结构数据结构编译原理编译原理操作系统操作系统系统软件系统软件数据库数据库地位地位为什么学编译原理为什么学编译原理1. 1. 涉及计算机学科中，许多抽象问题、解决问题涉及计算机学科中，许多抽象问题、解决问题的思路和方法；的思路和方法；2.2.掌握程序语言的内部实现机理掌握程序语言的内部实现机理, ,对程序语言的理对程序语言的理解更加深入全面；解更加深入全面；3.3.课程中包含了很多软件技术课程中包含了很多软件技术, ,是专业经验积累的是专业经验积累的一种途径。一种途径。 作作 业业1.1.

37、编译过程一般分为编译过程一般分为5 5个阶段，分别完个阶段，分别完成什么分析？每个阶段的输入、输出成什么分析？每个阶段的输入、输出是什么？是什么？2.2.什么是什么是“遍遍”？如果把编译程序分成？如果把编译程序分成3 3遍，你会如何划分？每一遍，你会如何划分？每一“遍遍”的输的输入、输出分别是什么？入、输出分别是什么？第第2章章 高级语言及其语法描述高级语言及其语法描述2.1 编译程序需要重点考虑的程序语言特性2.2 符号和符号串2.3 上下文无关文法2.4 语法树和二义性2.5 形式语言介绍2.1 2.1 编译程序需要重点考虑的程序语言特性编译程序需要重点考虑的程序语言特性1. 标识符与名字

38、标识符与名字 标识符：字母打头的字母数字串。 名字：用标识符表示的，带有类型、值域的 程序语言对象。高级语言之间的差异也是在这里体现的。例： aa 标识符 real aa 名字，实型变量， 值域、运算确定。2. 名字的定义名字的定义影响 - 目标程序的执行效率的高低。 能否静态分配存储空间； 能否作静态语义检查类型类型名字定义方式名字定义方式典型语言典型语言显式定义显式定义名字的类型必须定义名字的类型必须定义C, PascalC, Pascal隐式定义隐式定义名字的类型可以定义或者不定义名字的类型可以定义或者不定义, ,未定未定义的名字的类型按照缺省定义处理。义的名字的类型按照缺省定义处理。F

39、ORTRANFORTRAN(I-N(I-N规则规则) )不定义不定义名字的类型不必定义。根据运行时名名字的类型不必定义。根据运行时名字的取值动态确定。字的取值动态确定。早期的早期的BASIC,BASIC,VFPVFP例： int aa aa=12.3； 类型错误（静态语义检查）全程变量：主程序中定义。局部变量：过程/函数/分程序/对象 中定义。影响：3.变量的作用域 存储空间能否复用。 变量重名时的实现方法。 如：采用最小作用域原则。4.语义同一语句，在不同的语言中的含义可能不同。例：数组 A1.3,1.4，访问: A2,3 Pascal：按行分配a11a11 a12a12 a13a13 a1

40、4a141 1a21a21 a22a22 a23a23 a24a242 2a31a31 a32a32 a33a33 a34a343 3a11a11a12a12a13a13a14a14a21a21a22a22a23a23a24a24a31a31a32a32a33a33a34a341 12 23 34 4FORTRAN：按列分配a23地址=a11地址+7访问: a23地址=a11地址+65.5.支持的数据类型，类型中允许的运算支持的数据类型，类型中允许的运算 基本数据类型: 整型，实型，布尔，字符，字符串 复杂数据类型： 数组，记录，结构，指针，集合,类 6.支持的语句分支、循环、过程、函数7.

41、存储空间分配方式 静态存储分配 动态存储分配 函数：允许递归调用时，每一次调用 需要一片数据区 动态数组 动态创建对象 用户可动态申请/释放数据空间2.2 符号和符号串符号和符号串1.字母表: 元素的非空、有穷集合。2.符号：字母表中的元素。例1: V=a,b,c 字母表 V 符号 a ，b , c例2：单词符号集=if,then,begin,标识符,+,-, 字母表 单词符号集 符号 if,then,begin,标识符,+,-, 3.符号串：符号组成的任何有穷序列。不包括任何符号的符号串称为空串（空字），记为。 注：符号串中符号的顺序是重要的。例1: V=a,b,c 符号串：a,b,c,ab

42、,ba,cc,aab 其中：abba例2:单词符号集=if,then,begin,，标识符，+,-, 程序：由上述符号构成的一个符号串 但：任一符号串不一定是合法的程序。 编译研究：什么样的符号串是合法的程序。4. 串的长度: 设是字母表V中的符号串， 的长度=中符号的个数。记为：| 5. 串的联结： 设、是字母表V中的符号串，联结是指： 将放在之后形成的符号串，记为：例: V=a,b,c， 且有：=ab , =bca 则： = abbca ， = bcaab |=2, |=5 特别： , |= 0 6. 符号串集合： 由符号串构成的集合，记为： A= x | xA 7. 符号串集合的乘积:

43、若A,B是V上的符号串集合，A,B的乘积定义 为： AB= | A ,B 例: 若： A=ab,ba, B=ca,acb 则： AB=abca, abacb, baca, baacb = = A = A = A8.符号串的方幂： 对任意符号串，0 = 1 = 2 = n =n-1 (n0) 例: =ab 则：0 =， 1 =ab ， 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,a

44、ba,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 Vn 正闭包 V* = V0 V1 V2 V3 Vn 闭包 两种闭包之间的关系： V* = V0 V+ V+ = V V* = V* V 两个集合的乘积2.3 上下文无关文法上下文无关文法1.产生式（产生规则，简称规则）： 一个有序对（A，），通常写作： A= 或 A A：符号

45、，称为产生式左部； ：符号串，称为：产生式右部， 或：产生式的候选式产生式的书写方式称为：BNF范式 若有产生式： A1 A2 An 写成：A1|2| |n候选式元符号 ：定义为 | ：或2. 文法GS：产生式的非空有穷集合，S是一个符号，它至少要在一条产生式中作为左部出现，称为识别符号或开始符号，出现在产生式左部和右部中的所有符号形成字母表 V。 例: GE E E + T | T T T * F | F F i | (E) V = E , + , T, *, F, i, ( , ) 产生式识别符号或开始符号3. 非终结符号：给定文法G，把作为产生式左部出现的那些符号称为非终结符号，或语法实

46、体，所有非终结符号汇集成：非终结符号集，记为：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 的那些符号称为终结符号，所有终结符号汇集成：终结符号集，记为：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, (

47、, ) 5. 上下文无关文法的形式定义： 上下文无关文法是一个四元组 GS = (VN , VT , P , S )其中：VN 非终结符号集合 VT 终结符号集合 P 产生式集合 S 文法的识别符号（开始符号）6. 直接推导、直接归约：令G为文法，、为符号串，若：A是一个产生式，称：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

48、 + i = E * i + i ( = E* , = + i )7. 推导、归约：若存在一个直接推导序列 1 =2 =3 = =n 称：1 可以出推导n ,或n可归约为1 记为： 1 n （推导步骤0步，读作：+号推导出） = 或 ，表示推导步骤0步， （读作：*号推导出）即：例: 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 + iE + E =E + i =E * E + i =E * i + i =i * i + i

49、E + E =E * E + E =E * E + i =E * i + i =i * i + iE + E =E * E + E =E * i + E =E * i + i =i * i + i8. 最左推导、最右推导：推导中若每一步直接推导， 替换的都是符号串的最左非终结符，称为最左推导； 替换的都是符号串的最右非终结符，称为最右推导。说明：说明：例: GE: E E + E | E E | E * E | (E) | i E =E + E =E * E + E =i * E + E =i * i + E =i * i + i 只要符号串中有产生式的左部符号，就能从该符号串 推导出新的符号

50、串，即：推导过程未结束(非终结)， 所以左部符号称为非终结符号 Non-terminal symbol 符号串中没有产生式的左部符号了，那么推导过程就 必须终结。所以不在产生式的左部出现的符号称为 终结符号 Terminal symbol 故：非终结符集 VN 终结符集 VT9. 句型、句子： 令GS为一文法，如果符号串是由文法的开始 符号推导出来的，即：S ，则称是句型。 若 S ，且 VT* ， 则称是句子。 （即：仅由终结符号构成的句型称为句子）例: GE: E E + E | EE | E * E |(E)| i E = E + E = E * E + E = i * E + E =