编译原理[890页]课件.ppt

1、2022-8-612022-8-62使用说明使用说明 课程教学需要瞄准所在专业的具体培养目标，需课程教学需要瞄准所在专业的具体培养目标，需要体现教师和学生的特点。本电子讲稿是要体现教师和学生的特点。本电子讲稿是资料性资料性的的，为大家使用我们编著的教材组织教学提供讲，为大家使用我们编著的教材组织教学提供讲稿的制作基础。请读者注意：稿的制作基础。请读者注意：这份资料覆盖教材的全部内容，供大家选用，但由于这份资料覆盖教材的全部内容，供大家选用，但由于学时限制，大家需要根据学生的培养需求选取适当的学时限制，大家需要根据学生的培养需求选取适当的内容内容 在制作中，我们适当考虑了讲课的需要，包含了作者在

2、制作中，我们适当考虑了讲课的需要，包含了作者的一些理解和讲法，但只能参考，由于面对的学生、的一些理解和讲法，但只能参考，由于面对的学生、讲授的环境等不同，直接使用会影响教学效果讲授的环境等不同，直接使用会影响教学效果2022-8-63使用说明使用说明 编译原理课程是计算机专业教育很重要的专业技编译原理课程是计算机专业教育很重要的专业技术基础课，更多地体现在其所含的学生终生受用术基础课，更多地体现在其所含的学生终生受用的计算机问题求解的典型思想和方法，所含的知的计算机问题求解的典型思想和方法，所含的知识是载体，利用好这个载体，还靠大家努力识是载体，利用好这个载体，还靠大家努力 课程教学是与教师和

3、学生紧密相关的，甚至可以课程教学是与教师和学生紧密相关的，甚至可以说大纲、教材只是一个框架和素材，课堂教学这说大纲、教材只是一个框架和素材，课堂教学这部剧如何展开，还依赖于集导演和演员于一身的部剧如何展开，还依赖于集导演和演员于一身的教师，讲课教师，讲课PPT的制作是必不可少的的制作是必不可少的“排练工作排练工作”之一之一 非常希望听到大家的建议和意见，祝大家在编译非常希望听到大家的建议和意见，祝大家在编译课程的教学中做出更多的探索课程的教学中做出更多的探索2022-8-64编译原理编译原理Compiler Principles and Techniques 蒋宗礼蒋宗礼 姜守旭姜守旭2022

4、-8-65课程目的和基本要求课程目的和基本要求 课程性质课程性质技术基础技术基础 基础知识要求基础知识要求 高级程序设计语言，数据结构与算法，形式语高级程序设计语言，数据结构与算法，形式语言与自动机言与自动机 主要特点主要特点 既有理论，又有实践既有理论，又有实践 面向系统设计面向系统设计 涉及程序的自动生成技术涉及程序的自动生成技术2022-8-66课程目的和基本要求课程目的和基本要求本专业人员本专业人员4 4种基本的专业能力种基本的专业能力1.1.计算思维能力计算思维能力2.2.算法的设计与分析能力算法的设计与分析能力3.3.程序设计和实现能力程序设计和实现能力4.4.计算机软硬件系统的认

5、知、分析、设计与应用能力计算机软硬件系统的认知、分析、设计与应用能力计算思维能力计算思维能力1.1.逻辑思维能力和抽象思维能力逻辑思维能力和抽象思维能力2.2.构造模型对问题进行形式化描述构造模型对问题进行形式化描述3.3.理解和处理形式模型理解和处理形式模型2022-8-67课程目的和基本要求课程目的和基本要求 知识知识掌握编译程序的总体结构、编译程序各个组成部分的掌握编译程序的总体结构、编译程序各个组成部分的任务、编译过程各个阶段的工作原理任务、编译过程各个阶段的工作原理、编译过程各、编译过程各个阶段所要解决的问题及其采用的方法和技术个阶段所要解决的问题及其采用的方法和技术 能力能力1.掌

6、握程序变换基本概念、问题描述和处理方法掌握程序变换基本概念、问题描述和处理方法 2.增强理论结合实际能力增强理论结合实际能力3.修养修养“问题、形式化描述、计算机化问题、形式化描述、计算机化”的问题求解的问题求解过程过程 4.使学生在系统级上认识算法和系统的设计，培养系统使学生在系统级上认识算法和系统的设计，培养系统能力能力2022-8-68主要内容主要内容 1.引论引论2.高级语言及其文法高级语言及其文法3.词法分析词法分析4.自顶向下的语法分析自顶向下的语法分析5.自底向上的语法分析自底向上的语法分析6.语法制导翻译与属性文法语法制导翻译与属性文法7.语义分析与中间代码生成语义分析与中间代

7、码生成8.符号表管理符号表管理9.运行时的存储组织运行时的存储组织10.代码优化代码优化11.代码生成代码生成2022-8-69教材及主要参考书目教材及主要参考书目1.蒋宗礼，姜守旭蒋宗礼，姜守旭.编译原理编译原理.北京：高等教育出北京：高等教育出版社，版社，2010年年2月月 2.Alfred Aho ect.，Compilers:Principles,Techniques,and Tools(Second Edition)，北北京京：人民邮电出版社人民邮电出版社，Pearson Education出出版集团版集团，2008.2.3.Alfred Aho ect.，Compilers:Pri

8、nciples,Techniques,and Tools，北京北京：人民邮电出版人民邮电出版社社，Pearson Education出版集团出版集团，2002.2.2022-8-610第第1章章 引论引论1.1 程序设计语言程序设计语言1.2 程序设计语言的翻译程序设计语言的翻译1.3 编译程序的总体结构编译程序的总体结构1.4 编译程序的组织编译程序的组织1.5 编译程序的生成编译程序的生成1.6 本章小结本章小结2022-8-6111.1 程序设计语言程序设计语言 机器语言机器语言(Machine Language)与汇编语言与汇编语言(Assemble Language)0、1代码与助记

9、符：更接近于计算机硬件指令系统的代码与助记符：更接近于计算机硬件指令系统的工作工作 高级语言高级语言(High Level Language)其表示方法更接近于待解问题的表示方法其表示方法更接近于待解问题的表示方法 定义数据、描述运算、控制流程、传输数据定义数据、描述运算、控制流程、传输数据 如：如：C、FORTRAN、PASCAL、C+、JAVA、SQL(数据定数据定义、数据操作义、数据操作)命令语言命令语言(Command Language)控制系统的工作控制系统的工作以功能封装为特征以功能封装为特征 如如UNIX上的上的shell1011 1000 0010 1011 0001 0101

10、(B82B15)1000 1110 1101 1000(8ED8)1010 0001 0000 0000 0000 0000(A10000)1000 1011 0001 1110 0000 0010 0000 0000(8B1E0200)1011 1001 0000 0000 0000 0000(B90000)0000 0011 1100 1000(03C8)0000 0011 1100 1011(03CB)1000 1011 0000 1110 0000 0100 0000 0000(8B0E0400)1011 1000 0000 0000 0100 1100(B8004C)1100 110

11、1 0010 0001(CD21)int mainint a,b,c;a=1234h;b=5678h;c=a+b;return 0;assume cs:code,ds:datadata segmentdw 1234h,5678hdata endscode segmentstart:mov ax,datamov ds,ax mov ax,ds:0mov bx,ds:2mov cx,0add cx,axadd cx,bxmov cx,ds:4mov ax,4c00hint 21h code endsend start 程序设计语言的分类程序设计语言的分类 强制式（命令式）语言强制式（命令式）语言(

12、Imperative Language)通过一系列可执行的运算及运算的次序来描述计通过一系列可执行的运算及运算的次序来描述计算过程的语言算过程的语言 FORTRAN(段结构段结构)、BASIC、Pascal(嵌套结构嵌套结构)、C 程序的层次性和抽象性不高程序的层次性和抽象性不高程序设计语言的分类程序设计语言的分类 申述式语言（申述式语言（Declarative Language）着重描述要处理什么，而非如何处理的非命令式着重描述要处理什么，而非如何处理的非命令式语言语言 函数函数(应用应用)式语言式语言(Functional Language)基本运算单位是函数，如基本运算单位是函数，如LI

13、SP、ML 逻辑式逻辑式(基于规则基于规则)语言语言(Logical Language)基本运算单位是谓词，如基本运算单位是谓词，如Prolog，Yacc程序设计语言的分类程序设计语言的分类 面向对象语言面向对象语言(Object-Oriented Language)以对象为核心，如以对象为核心，如Smalltalk、C+、Java、Ada(程序包程序包)具有识认性（对象）、类别性（类）、多态性和具有识认性（对象）、类别性（类）、多态性和继承性继承性1.2 程序设计语言的翻译程序设计语言的翻译翻译程序翻译程序(Translator)将某一种语言描述的程序将某一种语言描述的程序(源程序源程序So

14、urce Program)翻译成等价的另一种语言描述的程翻译成等价的另一种语言描述的程序序(目标程序目标程序Object Program)的程序的程序翻译程序翻译程序源程序源程序目标程序目标程序(*.C/*.PAS)(*.OBJ/*.EXE)2022-8-6161.2 程序设计语言的翻译程序设计语言的翻译 解释程序解释程序(Interpreter)一边解释一边执行的翻译程序一边解释一边执行的翻译程序 口译与笔译（单句提交与整篇提交）口译与笔译（单句提交与整篇提交）源程序源程序输入数据输入数据计算结果计算结果2022-8-6171.2 程序设计语言的翻译程序设计语言的翻译 编译程序编译程序(Co

15、mpiler)将源程序完整地转换成机器语言程序或汇编将源程序完整地转换成机器语言程序或汇编语言程序，然后再处理、执行的翻译程序语言程序，然后再处理、执行的翻译程序 高级语言程序高级语言程序汇编汇编/机器语言程序机器语言程序源程序源程序目标程序目标程序2022-8-6181.2 程序设计语言的翻译程序设计语言的翻译SPCompilerS-SourceO-ObjectOPP-ProgramInputRSRS-Run Sys.Output2022-8-6191.2 程序设计语言的翻译程序设计语言的翻译 其它翻译程序：其它翻译程序：汇编程序汇编程序(Assembler)交叉汇编程序交叉汇编程序(Cro

16、ss Assembler)反汇编程序（反汇编程序（Disassembler)交叉编译程序（交叉编译程序（Cross Compiler)反编译程序（反编译程序（Decompiler）可变目标编译程序（可变目标编译程序（Retargetable Compiler)并行编译程序（并行编译程序（Parallelizing Compiler）诊断编译程序（诊断编译程序（Diagnostic Compiler)优化编译程序（优化编译程序（Optimizing Compiler)2022-8-6201.2 1.2 程序设计语言的翻译程序设计语言的翻译汇总汇总解释程序数据结果编译系统机器语言程序机器语言程序机

17、器语言程序汇编语言程序高级语言程序汇编语言程序汇编语言程序高级语言程序高级语言程序汇编程序反汇编程序编译程序反编译程序汇编程序反汇编程序编译程序反编译程序汇编程序编译程序交叉汇编程序交叉编译程序可变目标编译程序图1.5 主要翻译程序汇总运行系统2022-8-6211.3 1.3 编译程序总体结构编译程序总体结构2022-8-6221、词法分析、词法分析 例：例：sum=(10+20)*(num+square);结果结果(标识符，标识符，sum)(赋值号，赋值号，=)(左括号，左括号，()(整常数，整常数，10)(加号，加号，+)(整常数，整常数，20)(右括号，右括号，)(乘号，乘号，*)(左

18、括号，左括号，()(标识符，标识符，num)(加号，加号，+)(标识符，标识符，square)(右括号，右括号，)(分号，分号，;)2022-8-6231、词法分析、词法分析 词法分析由词法分析器词法分析由词法分析器(Lexical Analyzer)完完成，词法分析器又称为扫描器成，词法分析器又称为扫描器(Scanner)词法分析器从左到右扫描组成源程序的字符词法分析器从左到右扫描组成源程序的字符串，并将其转换成单词串，并将其转换成单词(记号记号token)串；同串；同时要：查词法错误，进行标识符登记时要：查词法错误，进行标识符登记符符号表管理号表管理 输入：字符串输入：字符串 输出：输出：

19、(种别码，属性值种别码，属性值)序对序对 属性值属性值token的机内表示的机内表示2022-8-6242、语法分析、语法分析 语法分析由语法分析器语法分析由语法分析器(Syntax Analyzer)完成，语完成，语法分析器又叫法分析器又叫Parser。功能：功能：Parser实现实现“组词成句组词成句”将词组成各类语法成分：表达式、因子、项，语句，子程序将词组成各类语法成分：表达式、因子、项，语句，子程序 构造分析树构造分析树 指出语法错误指出语法错误 指导翻译指导翻译 输入：输入：token序列序列 输出：语法成分输出：语法成分2022-8-6252、语法分析、语法分析sum=(10+2

20、0)*(num+square);2022-8-6263、语义分析、语义分析 语义分析语义分析(semantic analysis)一般和语法一般和语法分析同时进行，称为分析同时进行，称为语法制导翻译语法制导翻译(syntax-directed translation)功能：分析由语法分析器识别出来的语功能：分析由语法分析器识别出来的语法成分的语义法成分的语义 获取标识符的属性：类型、作用域等获取标识符的属性：类型、作用域等 语义检查：运算的合法性、取值范围等语义检查：运算的合法性、取值范围等 子程序的静态绑定：代码的相对地址子程序的静态绑定：代码的相对地址 变量的静态绑定：数据的相对地址变量的

21、静态绑定：数据的相对地址2022-8-6274、中间代码生成、中间代码生成中间代码中间代码(intermediate Code)例例:sum=(10+20)*(num+square);2022-8-628波兰表示问题波兰表示问题Lukasiewicz 1929年发明年发明 中缀表示中缀表示(Infix notation):(a+b)*(-c+d)+e/f 波兰表示波兰表示（Polish/Prefix/Parenthesis-free/Lukasiewicz notation）也就是前缀表示也就是前缀表示+*+a b+c d/ef 逆波兰表示逆波兰表示(Reverse Polish/Suffix

22、/Postfix notation)也就是后缀表示也就是后缀表示a b+c d+*ef/+运算顺序从左向右运算顺序从左向右2022-8-6294、中间代码生成、中间代码生成 中间代码的特点中间代码的特点 简单规范简单规范 与机器无关与机器无关 易于优化与转换易于优化与转换三地址码的另一种表示三地址码的另一种表示形式：形式：T1=10+20 T2=num+square T3=T1*T2 sum=T3 2022-8-630 代码优化代码优化(optimization)是指对中间代码进是指对中间代码进行优化处理，使程序运行能够尽量节省存行优化处理，使程序运行能够尽量节省存储空间，更有效地利用机器资源

23、，使得程储空间，更有效地利用机器资源，使得程序的运行速度更快，效率更高。当然这种序的运行速度更快，效率更高。当然这种优化变换必须是等价的。优化变换必须是等价的。与机器无关的优化与机器无关的优化 与机器有关的优化与机器有关的优化5、代码优化、代码优化2022-8-631与机器无关的优化与机器无关的优化 局部优化局部优化 常量合并：常数运算在编译期间完成，如常量合并：常数运算在编译期间完成，如8+9*4 公共子表达式的提取公共子表达式的提取:在基本块内进行的在基本块内进行的 循环优化循环优化 强度削减强度削减 用较快的操作代替较慢的操作用较快的操作代替较慢的操作 代码外提代码外提 将循环不变计算移

24、出循环将循环不变计算移出循环2022-8-632与机器有关的优化与机器有关的优化 寄存器的利用寄存器的利用 将常用量放入寄存器，以减少访问内存的次数将常用量放入寄存器，以减少访问内存的次数 体系结构体系结构 MIMD、SIMD、SPMD、向量机、流水机、向量机、流水机 存储策略存储策略 根据算法访存的要求安排：根据算法访存的要求安排：Cache、并行存储体、并行存储体系系减少访问冲突减少访问冲突 任务划分任务划分 按运行的算法及体系结构，划分子任务按运行的算法及体系结构，划分子任务(MPMD)2022-8-6336 6、目标代码生成、目标代码生成 将中间代码转换成目标机上的机器指令代码将中间代

25、码转换成目标机上的机器指令代码或汇编代码或汇编代码确定源语言的各种语法成分的目标代码结构确定源语言的各种语法成分的目标代码结构（机器指令组（机器指令组/汇编语句组）汇编语句组）制定从中间代码到目标代码的翻译策略或算法制定从中间代码到目标代码的翻译策略或算法 目标代码的形式目标代码的形式具有绝对地址的机器指令具有绝对地址的机器指令汇编语言形式的目标程序汇编语言形式的目标程序模块结构的机器指令（需要链接程序）模块结构的机器指令（需要链接程序）2022-8-6347、表格管理、表格管理 管理各种符号表（常数、标号、变量、过管理各种符号表（常数、标号、变量、过程、结构程、结构），查、填（登记、查找），

26、查、填（登记、查找）源程序中出现的符号和编译程序生成的符源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息。号，为编译的各个阶段提供信息。辅助语法检查、语义检查辅助语法检查、语义检查 完成静态绑定、管理编译过程完成静态绑定、管理编译过程 Hash表、链表等各种表的查、填技术表、链表等各种表的查、填技术“数据结构与算法数据结构与算法”课程的应用课程的应用2022-8-6358 8、错误处理、错误处理进行各种错误的检查、报告、纠正，以及相进行各种错误的检查、报告、纠正，以及相应的续编译处理（如：错误的定位与局部化）应的续编译处理（如：错误的定位与局部化）词法：拼写词法：拼写语法：语句

27、结构、表达式结构语法：语句结构、表达式结构语义：类型不匹配、参数不匹配语义：类型不匹配、参数不匹配2022-8-636模块分类模块分类 分析：词法分析、语法分析、语义分析分析：词法分析、语法分析、语义分析 综合：中间代码生成、代码优化、目标代综合：中间代码生成、代码优化、目标代码生成码生成 辅助：符号表管理、出错处理辅助：符号表管理、出错处理 8项功能对应项功能对应8个模块个模块2022-8-637语句sum=(10+20)*(num+square);的翻译过程2022-8-6381.4 编译程序的组织编译程序的组织 根据系统资源的状况、运行目标的要求根据系统资源的状况、运行目标的要求等，可以

28、将一个编译程序设计成多遍（等，可以将一个编译程序设计成多遍（Pass）扫描的形式，在每一遍扫描中，完成不同的扫描的形式，在每一遍扫描中，完成不同的任务。任务。如：首遍构造语法树，二遍处理中间表示，增加如：首遍构造语法树，二遍处理中间表示，增加信息等。信息等。遍可以和阶段相对应，也可以和阶段无关遍可以和阶段相对应，也可以和阶段无关 单遍代码不太有效单遍代码不太有效2022-8-6391.4 编译程序的组织编译程序的组织 编译程序的设计目标编译程序的设计目标 规模小、速度快、诊断能力强、可靠性高、可规模小、速度快、诊断能力强、可靠性高、可移植性好、可扩充性好移植性好、可扩充性好 目标程序也要规模小

29、、执行速度快目标程序也要规模小、执行速度快 编译系统规模较大，因此可移植性很重要编译系统规模较大，因此可移植性很重要 为了提高可移植性，将编译程序划分为前端和为了提高可移植性，将编译程序划分为前端和后端后端2022-8-6401.4 编译程序的组织编译程序的组织 前端前端 与源语言有关、与目标机无关的部分与源语言有关、与目标机无关的部分 词法分析、语法分析、语义分析与中间代码生词法分析、语法分析、语义分析与中间代码生成、与机器无关的代码优化成、与机器无关的代码优化 后端后端 与目标机有关的部分与目标机有关的部分 与机器有关的代码优化、目标代码生成与机器有关的代码优化、目标代码生成2022-8-

30、6411.5 编译程序的生成编译程序的生成 如何实现编译器？如何实现编译器？直接用可运行的代码编制直接用可运行的代码编制太费力！太费力！自举自举-使用语言提供的功能来编译该语言自使用语言提供的功能来编译该语言自身身“第一个编译器是怎样被编译的？第一个编译器是怎样被编译的？”2022-8-6421.T形图形图 表示语言翻译的表示语言翻译的 T 形图形图2022-8-643 问题一：如何直接在一个机器上实现问题一：如何直接在一个机器上实现C语言编译器？语言编译器？解决：解决：用汇编语言实现一个子集的编译程序用汇编语言实现一个子集的编译程序(P0人人)用汇编程序处理该程序用汇编程序处理该程序,得到得

31、到(P2:可直接运行可直接运行)用子集编制语言的编译程序用子集编制语言的编译程序(P3人人)用用P2编译编译P3，得到，得到P42.自展自展2022-8-6444.用用P2P2编译编译P3P3，得到，得到P4P4语言语言机器语言机器语言机器语言机器语言子集子集机器语言机器语言机器语言机器语言子集子集汇编语言汇编语言机器语言机器语言1.用汇编语言实现一个用汇编语言实现一个 子集的编译程序子集的编译程序(P0(P0人人)汇编语言汇编语言机器语言机器语言机器语言机器语言子集子集机器语言机器语言机器语言机器语言2.用汇编程序用汇编程序(P1)(P1)处理该程序处理该程序,得到得到(P2:(P2:可直接

32、运行可直接运行)语言语言子集子集机器语言机器语言3.用子集编制用子集编制 语言的编译程序语言的编译程序(P3(P3人人)2022-8-6453.3.移植移植 问题二：问题二：A A机上有一个机上有一个C C语言编译器，是否可利用语言编译器，是否可利用此编译器实现此编译器实现B B机上的机上的C C语言编译器？语言编译器？条件：机有条件：机有 语言的编译程序语言的编译程序目的：实现目的：实现机的机的语言的编译语言的编译语言语言语语 言言机器机器语言语言B机器机器机器机器要完成的任务要完成的任务2022-8-646语言语言语言语言机器机器语言语言机器机器机器机器语言语言机器机器机器机器语言语言语语

33、 言言机器机器语言语言机器机器A机器机器语言语言A机器机器机器机器要完成的任务要完成的任务要完成的任务要完成的任务需要一个工具需要一个工具需要一个工具需要一个工具1)1)问题的分析问题的分析2022-8-6471.1.(人人)用语言编制用语言编制B B机的编译程序机的编译程序P0(CP0(C2.2.(机的机的C C编译编译P1)P1)编译编译P0P0，得到在，得到在A A机上可运行的机上可运行的P2(CP2(C语言语言语语 言言机器机器语言语言机器机器A机器机器语言语言A机器机器机器机器2)2)问题的解决办法问题的解决办法2022-8-6483.(3.(机的机的P2)P2)编译编译P0P0，得

34、到在，得到在B B机上可运行的机上可运行的P3(CP3(C语言语言语言语言机器机器语言语言机器机器机器机器语言语言机器机器机器机器语言语言语语 言言机器机器语言语言机器机器A机器机器语言语言A机器机器机器机器2022-8-6494.4.本机编译器的利用本机编译器的利用 问题三：问题三：A A机上有一个机上有一个C C语言编译器，现要实现一语言编译器，现要实现一个新语言个新语言NEWNEW的编译器？能利用交叉编译技术么？的编译器？能利用交叉编译技术么？用用C C编写编写NEWNEW的编译，并用的编译，并用C C编译器编译它编译器编译它NEW语言语言语语 言言A机器机器语言语言机器机器A机器机器N

35、EW语言语言A机器机器A机器机器2022-8-6505.5.编译程序的自动生成编译程序的自动生成1)1)词法分析器的自动生成程序词法分析器的自动生成程序词法规则说明词法规则说明词法分析程序词法分析程序(C(C程序程序)输入：输入：词法（正规表达式）词法（正规表达式）识别动作（程序段）识别动作（程序段）输出：输出：yylexyylex()()函数函数2022-8-6512)2)语法分析器的自动生成程序语法分析器的自动生成程序语法规则说明语法规则说明语法分析程序语法分析程序(C(C程序程序)输入：输入：语法规则（产生式）语法规则（产生式）语义动作（程序段）语义动作（程序段）输出：输出：yypars

36、eyyparse()()函数函数2022-8-652例例1-1DOS 命令命令 date 的输出格式的输出格式例：例：9-3-1993、09-03-1993、9-03-93语法语法date month-day-year词法词法month DIGIT DIGIT|DIGITday DIGIT DIGIT|DIGITyear DIGIT DIGIT|DIGII DIGIT DIGIT DIGIT2022-8-653例例1-1（续）（续）语义语义year(年年)、month(月月)、day(日日)语义约束条件语义约束条件0 month.value 130 day.value 32，31，300 ye

37、ar.value 100002022-8-6541.6 本章小结本章小结 编译原理是一门非常好的课编译原理是一门非常好的课 程序设计语言及其发展程序设计语言及其发展 程序设计语言的翻译程序设计语言的翻译 编译程序的总体结构编译程序的总体结构 编译程序的各个阶段编译程序的各个阶段 编译程序的组织与生成编译程序的组织与生成2022-8-655第第2章章 高级语言及其文法高级语言及其文法2.1 语言概述语言概述2.2 基本定义基本定义2.3 文法的定义文法的定义2.4 文法的分类文法的分类2.5 CFG的语法树的语法树2.6 CFG的二义性的二义性2.7 本章小结本章小结2022-8-6562.1

38、语言概述语言概述什么是语言？什么是语言？语言是一定的群体用来进行语言是一定的群体用来进行信息交流的工具。信息交流的工具。2022-8-6572.1 语言概述语言概述信息交流的基础是什么？信息交流的基础是什么？按照共同约定的生成规则和理解规则去按照共同约定的生成规则和理解规则去生成生成“句子句子”和理解和理解“句子句子”例：例：“今节日上课始开译第一编今节日上课始开译第一编”“今日开始上第一节编译课今日开始上第一节编译课”2022-8-6582.1 语言概述语言概述 语言的特征语言的特征 自然语言自然语言(Natural Language)是人与人的通讯工具是人与人的通讯工具 语义语义(sema

39、ntics):环境、背景知识、语气、二环境、背景知识、语气、二义性义性难以形式化难以形式化 计算机语言计算机语言(Computer Language)计算机系统间、人机间通讯工具计算机系统间、人机间通讯工具 严格的语法严格的语法(Grammar)、语义、语义(semantics)易于形式化：严格易于形式化：严格2022-8-6592.1 语言概述语言概述 语言的描述方法语言的描述方法现状现状自然语言：自然、方便自然语言：自然、方便-非形式化非形式化数学语言（符号）：严格、准确数学语言（符号）：严格、准确-形式形式化化形式化描述形式化描述高度的抽象、严格的理论基础和方便的计高度的抽象、严格的理论

40、基础和方便的计算机表示算机表示2022-8-6602.1 语言概述语言概述 语言语言形式化的内容提取形式化的内容提取 语言语言(Language)：满足一定条件的句子集合：满足一定条件的句子集合 句子句子(Sentence)：满足一定规则的单词序列：满足一定规则的单词序列 单词单词(Token)：满足一定规则的字符：满足一定规则的字符(Character)串串 语言是字和组合字的规则语言是字和组合字的规则 例（自然语言：第译始二天课今开编上节）例（自然语言：第译始二天课今开编上节）今天开始上第二节编译课今天开始上第二节编译课2022-8-6612.1 语言概述语言概述2022-8-6622.1

41、 语言概述语言概述 程序设计语言程序设计语言形式化的内容提取形式化的内容提取 程序设计语言程序设计语言(Programming Language)：组成程序：组成程序的所有语句的集合。的所有语句的集合。程序程序(Program)：满足语法规则的语句序列。：满足语法规则的语句序列。语句语句(Sentence)：满足语法规则的单词序列。：满足语法规则的单词序列。单词单词(Token)：满足词法规则的字符串。：满足词法规则的字符串。例：变量例：变量:=表达式表达式 if 条件表达式条件表达式 then 语句语句 while 条件表达式条件表达式 do 语句语句 call 过程名过程名(参数表参数表)

42、2022-8-6632.1 语言概述语言概述 描述形式描述形式文法文法 语法语法语句语句 语句的组成规则语句的组成规则 描述方法：描述方法：BNF范式、语法范式、语法(描述描述)图图 词法词法单词单词 单词的组成规则单词的组成规则 描述方法：描述方法：BNF范式、正规式范式、正规式2022-8-664形式语言与自动机理论的产生与形式语言与自动机理论的产生与作用作用 语言学家语言学家Chomsky最初从产生语言的角度研究最初从产生语言的角度研究语言语言。1956年，通过抽象，他将语言形式地定义为是由一年，通过抽象，他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合。可以在字个字母表中的

43、字母组成的一些串的集合。可以在字母表上按照一定的规则定义一个文法（母表上按照一定的规则定义一个文法（Grammar），），该文法所能产生的所有句子组成的集合就是该文法该文法所能产生的所有句子组成的集合就是该文法产生的语言。产生的语言。2022-8-665形式语言与自动机理论的产生与形式语言与自动机理论的产生与作用作用 克林（克林（Kleene）在）在1951年到年到1956年间，从识别年间，从识别语言的角度研究语言，给出了语言的另一种描语言的角度研究语言，给出了语言的另一种描述述 克林是在研究神经细胞中，建立了自动机克林是在研究神经细胞中，建立了自动机 对于按照一定的规则构造的任一个自动机，该

44、自动对于按照一定的规则构造的任一个自动机，该自动机就定义了一个语言，这个语言由该自动机所能识机就定义了一个语言，这个语言由该自动机所能识别的所有句子组成别的所有句子组成2022-8-666形式语言与自动机理论的产生与形式语言与自动机理论的产生与作用作用 1959年，年，Chomsky通过深入研究，将他本人的通过深入研究，将他本人的研究成果与克林的研究成果结合了起来，不仅研究成果与克林的研究成果结合了起来，不仅确定了文法和自动机分别从生成和识别的角度确定了文法和自动机分别从生成和识别的角度去表达语言，而且去表达语言，而且证明了文法与自动机的等价证明了文法与自动机的等价性性。2022-8-667形

45、式语言与自动机理论的产生与形式语言与自动机理论的产生与作用作用 20世纪世纪50年代，人们用年代，人们用巴科斯范式巴科斯范式（Backus Nour Form 或或 Backus Normal Form，简记，简记为为BNF）成功地描述）成功地描述ALGOL-60 促进形式语言在促进形式语言在20世纪世纪60年代的大发展年代的大发展 巴科斯范式就是上下文无关文法（巴科斯范式就是上下文无关文法（Context Free Grammar）的一种表示形式）的一种表示形式2022-8-668形式语言与自动机理论的产生与形式语言与自动机理论的产生与作用作用 形式语言与自动机理论除了在计算机科学领域中的直

46、形式语言与自动机理论除了在计算机科学领域中的直接应用外，更在计算学科人才的接应用外，更在计算学科人才的计算思维的培养计算思维的培养中占中占有极其重要的地位有极其重要的地位 计算思维能力的培养，主要是由基础理论系列课程实计算思维能力的培养，主要是由基础理论系列课程实现的，该系列主要由从数学分析开始到形式语言结束现的，该系列主要由从数学分析开始到形式语言结束的一些数学和抽象程度比较高的内容的课程组成的一些数学和抽象程度比较高的内容的课程组成 计算思维能力梯级训练系统：连续数学、离散数学、计算模计算思维能力梯级训练系统：连续数学、离散数学、计算模型型 连续数学、离散数学、计算模型分三个阶段开出，对应

47、与本连续数学、离散数学、计算模型分三个阶段开出，对应与本学科的学生在大学学习期间的思维方式和能力的变化与提高学科的学生在大学学习期间的思维方式和能力的变化与提高过程的三个步骤过程的三个步骤2022-8-6692.2 基本定义基本定义 定义定义2.1 字母表字母表（Alphabet）是一个非空有是一个非空有穷集合，字母表中的元素称为该字母表的一穷集合，字母表中的元素称为该字母表的一个字母（个字母（Letter），也叫字符（），也叫字符（Character）例例 以下是不同的字母表：以下是不同的字母表：a，b，c，d a，b，c，z 0，1 (4)ASCII字母表字母表2022-8-6702.2

48、基本定义基本定义 定义定义2.2 设设1、2是两个字母表，是两个字母表，1与与2 的的乘积乘积(Product)定义为定义为12=ab|a1，b2 例例:1=0,1,2=a,b,12=0a,0b,1a,1b 定义定义2.3 设设是一个字母表，是一个字母表，的的n次幂次幂(Power)递归递归地定义为：地定义为：0=n=n-1 n1 例：例：13=000,001,010,011,100,101,110,1112022-8-6712.2 基本定义基本定义 定义定义2.4 设设是一个字母表，是一个字母表，的的正闭包正闭包(Positive Closure)定义为：定义为：+=234 的的克林闭包克林

49、闭包(Kleene Closure)为：为：*=0+=023 2022-8-6722.2 基本定义基本定义 例例0,1+=0，1，00，01，11，000，001，010，011，100，a，b，c，d+=a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc 2022-8-6732.2 基本定义基本定义 例例0,1*=，0，1，00，01，11，000，001，010，011，100，a，b，c，d*=，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc，202

50、2-8-6742.2 基本定义基本定义定义定义2.5 设设是一个字母表，是一个字母表，x *，x称称为字母表为字母表上的一个上的一个句子句子（sentence），），叫做叫做上的一个上的一个空句子空句子。定义定义2.6 设设是一个字母表，对任意的是一个字母表，对任意的x，y*，a，句子，句子xay中的中的a叫做叫做a在该句子中在该句子中的一个的一个出现出现(occurrence)。定义定义2.7 设设是一个字母表，是一个字母表，x*，句子，句子x中字符出现的总个数叫做该字符串的中字符出现的总个数叫做该字符串的长度长度(length)，记作，记作|x|。2022-8-6752.2 基本定义基本定