编译原理(引论)

1、编译原理编译原理陈晓明陈晓明 电电 话：话-mail：minny-先修课程先修课程v高级程序设计语言高级程序设计语言v计算机组成原理计算机组成原理v操作系统操作系统v数据结构数据结构课程内容课程内容v介绍编译器构造的一般原理和基本实现方法介绍编译器构造的一般原理和基本实现方法v介绍的理论知识：形式语言和自动机理论、语法制介绍的理论知识：形式语言和自动机理论、语法制导的定义和属性文法、类型论、程序分析原理等导的定义和属性文法、类型论、程序分析原理等v强调形式描述技术和自动生成技术强调形式描述技术和自动生成技术v强调对编译原理和技术的宏观理解，不把注意力分强调对编译原理和

2、技术的宏观理解，不把注意力分散到枝节算法，不偏向于任何源语言或目标机器散到枝节算法，不偏向于任何源语言或目标机器课程特点课程特点v编译原理编译原理是理论性较强的课程是理论性较强的课程 。v概念多、内容抽象。尤其是文法、形式语言概念多、内容抽象。尤其是文法、形式语言及自动机的概念是计算机专业理论学习和研及自动机的概念是计算机专业理论学习和研究的基础究的基础 。教学目的教学目的编译原理编译原理是一门非常好的课程是一门非常好的课程vAlfred V.AhoAlfred V.Aho：编写编译器的原理和技术具有十分：编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科学家的研究生普遍的意义，以

3、至于在每个计算机科学家的研究生涯中，本课程中的原理和技术都会反复用到涯中，本课程中的原理和技术都会反复用到v本课程将兼顾语言的描述方法、设计与应用本课程将兼顾语言的描述方法、设计与应用( (形式化形式化) )能形式化就能自动化（抽象能形式化就能自动化（抽象符号化符号化机械化）机械化）可以使学生对程序设计语言具有更加深刻的理解可以使学生对程序设计语言具有更加深刻的理解体验实现自动计算的乐趣体验实现自动计算的乐趣v涉及的是一个比较适当的抽象层面上的数据变换涉及的是一个比较适当的抽象层面上的数据变换（既抽象又实际，既有理论又有实践）（既抽象又实际，既有理论又有实践）v一个相当规模的系统的设计一个相当

4、规模的系统的设计总体结构总体结构若干具体的表示和变换算法若干具体的表示和变换算法2022-5-75教学目的教学目的(续续)v在在系统级系统级上认识算法、系统的设计上认识算法、系统的设计具有把握系统的能力具有把握系统的能力局部最优局部最优vs.vs.全局最优全局最优( (木桶效用木桶效用) )“自顶向下自顶向下”和和“自底向上自底向上”的系统设计方法的系统设计方法v对其思想、方法、实现的全方位讨论对其思想、方法、实现的全方位讨论v进一步培养进一步培养“计算思维能力计算思维能力”深入理解软件系统的非物理性质深入理解软件系统的非物理性质培养抽象思维能力和逻辑思维能力培养抽象思维能力和逻辑思维能力训练

5、对复杂数据结构的设计和操纵能力训练对复杂数据结构的设计和操纵能力2022-5-76教学目的教学目的(续续)v计算机专业最为恰当、有效的知识载体之一计算机专业最为恰当、有效的知识载体之一v综合运用下列课程所学知识综合运用下列课程所学知识高级程序设计语言高级程序设计语言汇编语言汇编语言集合论与图论集合论与图论数据结构与算法数据结构与算法计算机组成原理计算机组成原理算法设计与分析算法设计与分析形式语言与自动机形式语言与自动机2022-5-772022-5-78教学要求教学要求课程要求课程要求v知识要求知识要求掌握编译程序的总体结构、编译程序各个组成掌握编译程序的总体结构、编译程序各个组成部分的任务、

6、编译过程各个阶段的工作原理部分的任务、编译过程各个阶段的工作原理 、编译过程各个阶段所要解决的问题及其采用的编译过程各个阶段所要解决的问题及其采用的方法和技术方法和技术 v能力要求能力要求1.1.掌握程序变换基本概念、问题描述和处理方法掌握程序变换基本概念、问题描述和处理方法 2.2.增强理论结合实际能力增强理论结合实际能力3.3.探索探索“问题、形式化描述、计算机化问题、形式化描述、计算机化” ” 的问的问题求解过程题求解过程 4.4.使学生在系统级上认识算法和系统的设计，培使学生在系统级上认识算法和系统的设计，培养系统能力养系统能力教学要求教学要求实验要求实验要求v实验形式实验形式分析、设

7、计、编写、调试、测试程序分析、设计、编写、调试、测试程序撰写实验报告撰写实验报告答辩答辩v实验内容实验内容词法分析器的设计与实现词法分析器的设计与实现语法分析器的设计与实现语法分析器的设计与实现语义分析与中间代码生成语义分析与中间代码生成2022-5-79教学要求教学要求实验目的实验目的v实验贯穿于理论、抽象和设计过程；实验贯穿于理论、抽象和设计过程；v实验对软件的设计和实现、测试原理和方法实验对软件的设计和实现、测试原理和方法起示范作用；起示范作用；v实验不仅仅是对理论的验证，重要的是技术实验不仅仅是对理论的验证，重要的是技术训练和能力培养，包括动手能力、分析问题训练和能力培养，包括动手能力

8、、分析问题解决问题能力、表达能力、写作能力等的培解决问题能力、表达能力、写作能力等的培养；养；v实验可以弥补课堂教学的不足，加深对理论实验可以弥补课堂教学的不足，加深对理论过程的理解，启发学生深入思考，敢于创新，过程的理解，启发学生深入思考，敢于创新，达到良好的理论联系实际的教学效果。达到良好的理论联系实际的教学效果。2022-5-710教学要求教学要求考试要求考试要求v题型题型选择、填空、计算、综合等选择、填空、计算、综合等v重点和难点重点和难点会在各章的开始点明会在各章的开始点明v考试权重考试权重出勤占出勤占5%5%作业占作业占15%15%期末考试占期末考试占80%80%v考前答疑考前答疑

9、2022-5-711教学方法教学方法v围绕一条主线展开围绕一条主线展开编译过程的各个阶段编译过程的各个阶段v面向系统面向系统从系统的角度，引导大家逐步建立系统观和工程观，从系统的角度，引导大家逐步建立系统观和工程观，并学会折衷并学会折衷v启发式启发式问题驱动，引导大家理解问题和方法的直观背景问题驱动，引导大家理解问题和方法的直观背景以学生为中心，注重课堂交互，鼓励大家多发问以学生为中心，注重课堂交互，鼓励大家多发问v面向应用面向应用引导大家了解技术、方法的应用背景引导大家了解技术、方法的应用背景v注重实践注重实践以编写一个小型语言编译器为目标以编写一个小型语言编译器为目标2022-5-7122

10、022-5-713教材及主要参考书目1.蒋宗礼，姜守旭. 编译原理. 北京：高等教育出版社，2010年2月 2.Alfred Aho ect.，Compilers: Principles, Techniques, and Tools，北京：人民邮电出版社，Pearson Education出版集团，2002.2. 3.Alfred Aho ect.，Compilers: Principles, Techniques, and Tools(Second Edition)，北京：人民邮电出版社，Pearson Education出版集团，2008.2. 2022-5-714Alfred V. Ah

11、o Alfred V. Aho博士是哥伦比亚大学的劳伦斯科斯曼计算机科学教授，于普林斯顿大学获得博士学位，IEEE、ACM Fellow，美国科学与艺术学院及国家工程学院院士，曾获得IEEE的冯诺伊曼奖。“龙书”的第一作者，AWK的发明者之一。他目前的研究方向为量子计算、程序设计语言、编译器和算法等。他还赢得了2003年大学毕业生社群的最佳教师奖 参考网站参考网站v济南大学信息学院精品课程：济南大学信息学院精品课程：http:/ 1章章 引论引论v第第2 2章章 高级语言及其文法高级语言及其文法v第第3 3章章 词法分析词法分析v第第4 4章章 自顶向下语法分析自顶向下语法分析v第第5 5章章

12、 自底向上语法分析自底向上语法分析v第第6 6章章 语法制导翻译与属性文法语法制导翻译与属性文法v第第7 7章章 语义分析与中间代码生成语义分析与中间代码生成v第第9 9章章 运行时的存储组织运行时的存储组织v第第1111章章 代码生成代码生成第一章第一章 引论引论v要点：本章通过简要介绍编译程序的各个逻辑阶段，要点：本章通过简要介绍编译程序的各个逻辑阶段，对全书的内容进行简要概述。本章出现的大部分概对全书的内容进行简要概述。本章出现的大部分概念在以后各章会详细介绍，因此不要求在学习本章念在以后各章会详细介绍，因此不要求在学习本章时就都能理解这些概念。主要掌握以下时就都能理解这些概念。主要掌握

13、以下两点两点： 1 1、基本概念：源语言、目标语言、翻译程序、编、基本概念：源语言、目标语言、翻译程序、编译程序、解释程序。译程序、解释程序。 2 2、编译程序的各个逻辑阶段及各阶段的主要功能。、编译程序的各个逻辑阶段及各阶段的主要功能。2022-5-718第第1 1章章 引论引论1.1 1.1 程序设计语言程序设计语言1.2 1.2 程序设计语言的翻译程序设计语言的翻译1.3 1.3 编译程序的总体结构编译程序的总体结构1.4 1.4 编译程序的组织编译程序的组织1.5 1.5 编译程序的生成编译程序的生成第一章第一章 引论引论概念概念功能设计结构设计建档详细设计编辑输入输出执行链接编译调试

14、需求分析修改一般编程过程编辑输入1.2 程序设计语言的翻译1.2 程序设计语言的翻译程序设计语言的翻译v翻译程序(Translator)将某种语言描述的程序(源程序Source Program)翻译成等价的另一种语言描述的程序(目标程序Object Program)的程序。翻译程序翻译程序源程序源程序目标程序目标程序(*.C / *.PAS)(*.OBJ / *.EXE)2022-5-721编译程序与解释程序编译程序与解释程序v编译器编译器（编译程序）：如果源语言是某种高级语言，（编译程序）：如果源语言是某种高级语言，而目标语言是某种低级语言（汇编语言或机器语而目标语言是某种低级语言（汇编语言

15、或机器语言），这样的一个翻译程序就称为编译程序。言），这样的一个翻译程序就称为编译程序。v解释器解释器（解释程序）：这是另外一种类型的翻译程（解释程序）：这是另外一种类型的翻译程序，在翻译过程中它按照高级语言源程序在计算机序，在翻译过程中它按照高级语言源程序在计算机上执行的动态顺序对源程序的语句逐条翻译（解上执行的动态顺序对源程序的语句逐条翻译（解释），边解释边执行直至结束，它不产生目标程序，释），边解释边执行直至结束，它不产生目标程序，它的工作结果就是源程序的执行结果，这样的一个它的工作结果就是源程序的执行结果，这样的一个翻译程序就称为解释程序。（口译与笔译）（单句翻译程序就称为解释程序。（

16、口译与笔译）（单句提交与整篇提交）提交与整篇提交）编译程序与解释程序编译程序与解释程序例5 假设有源程序：read(x); write(x=, x);read(x);write(“x=”,x);目标程序目标程序3x=3编译器解释器read(x);write(“x=”,x);3x=3编译程序与解释程序编译程序与解释程序v特点：特点：1 1编译器：工作效率高，即时间快、空间省；交互编译器：工作效率高，即时间快、空间省；交互性与动态特性差、可移植性差。大多数性与动态特性差、可移植性差。大多数PLPL采用此种方采用此种方法翻译；法翻译；2 2解释器：工作效率低，即时间慢、空间费；交互解释器：工作效率低

17、，即时间慢、空间费；交互性与动态特性好、可移植性好。早期的性与动态特性好、可移植性好。早期的BasicBasic和现在和现在的的JavaJava等。等。v基本功能基本功能：二者相同；：二者相同；v所采用的技术所采用的技术：从翻译的角度来讲，两种方式所涉：从翻译的角度来讲，两种方式所涉及的原理、方法、技术相似。及的原理、方法、技术相似。2022-5-7251.2 程序设计语言的翻译程序设计语言的翻译SPCompilerS-SourceO-ObjectOPP-ProgramInputRS RS-Run Sys. Output2022-5-7261.2 程序设计语言的翻译程序设计语言的翻译v其它翻译

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

19、语言程序机器语言程序汇编语言程汇编语言程序序高级语言程序高级语言程序汇编语言程序汇编语言程序汇编语言程序汇编语言程序高级语言程序高级语言程序高级语言程序高级语言程序汇编程序汇编程序反汇编程序反汇编程序编译程序编译程序反编译程序反编译程序汇编程序汇编程序反汇编程序反汇编程序编译程序编译程序反编译程序反编译程序汇编程序汇编程序编译程序编译程序交叉汇编程序交叉汇编程序交叉编译程序交叉编译程序可变目标编译程序可变目标编译程序图图1.5 主要翻译程序汇总主要翻译程序汇总运行系统运行系统编译程序的发展编译程序的发展 2020世纪世纪5050年代早期出现编译技术。年代早期出现编译技术。 5050年代中期随着

20、高级语言的出现，相应的编年代中期随着高级语言的出现，相应的编译系统开发成功。译系统开发成功。 5050年代末期出现编译程序自动生成工具。年代末期出现编译程序自动生成工具。 6060年代起利用自展技术构造编译程序。年代起利用自展技术构造编译程序。 7070年代开始并行编译技术得到深入研究，同年代开始并行编译技术得到深入研究，同时面向对象语言、函数式语言的编译技术得到时面向对象语言、函数式语言的编译技术得到研究。研究。2022-5-7291.3 编译程序总体结构编译程序总体结构编译的阶段编译的阶段v把英文翻译为中文把英文翻译为中文 识别出句子中的一个个单词；识别出句子中的一个个单词；分析句子的语法

21、结构；分析句子的语法结构；根据句子的含义进行初步翻译；根据句子的含义进行初步翻译；对译文进行修饰；对译文进行修饰；写出最后的译文。写出最后的译文。 词法分析词法分析语法分析语法分析中间代码中间代码产生产生优化优化目标代码目标代码产生产生1、词法分析、词法分析v任务任务: : 输入源程序，对构成源程序的字符串进行从输入源程序，对构成源程序的字符串进行从左到右的扫描和分解，识别出一个个单词符号（记左到右的扫描和分解，识别出一个个单词符号（记号号tokentoken）。）。v依循的原则：构词规则依循的原则：构词规则v描述工具：正规式和有限自动机描述工具：正规式和有限自动机v输出：输出：( (种别码，

22、属性值种别码，属性值) )序对序对属性值属性值tokentoken的机内表示的机内表示。同时还要进行标识符登记同时还要进行标识符登记符号表管理。符号表管理。2022-5-7321、词法分析、词法分析v例：例：sum=(10+20)*(num+square); 结果结果(标识符，标识符，sum)(赋值号，赋值号，=)(左括号，左括号， ( )(整常数，整常数，10)(加号，加号，+ )(整常数，整常数，20)(右括号，右括号， ) )(乘号，乘号，* )(左括号，左括号， ( )(标识符，标识符，num)(加号，加号，+ )(标识符，标识符，square)(右括号，右括号， ) )(分号，分号，

23、; )2、语法分析、语法分析v任务任务: :在词法分析的基础上，根据语言的语法规则在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。把单词符号串分解成各类语法单位。如程序、语句、如程序、语句、表达式等。（组词成句）表达式等。（组词成句）v依循的原则：语法规则依循的原则：语法规则v描述工具：上下文无关文法描述工具：上下文无关文法v词法分析是一种线性分析，而语法分析是一种层次词法分析是一种线性分析，而语法分析是一种层次结构分析。结构分析。 2022-5-7342、语法分析、语法分析sum=(10+20)*(num+square);3、语义分析、语义分析v任务：任务：一般和语法分

24、析同时进行，一般和语法分析同时进行，称为称为语法制导翻译语法制导翻译(syntax-directed translation)v依循的原则：语义规则依循的原则：语义规则v语义分析的一个重要部分是类型检查，编译器检查语义分析的一个重要部分是类型检查，编译器检查每个算符的运算对象，看它们的类型是否适当。如：每个算符的运算对象，看它们的类型是否适当。如：实数作为数组下标，报错；整数和实数进行运算时，实数作为数组下标，报错；整数和实数进行运算时，将整数转变为实数。将整数转变为实数。4、中间代码生成、中间代码生成v任务：任务：“翻译翻译”仅仅在这里才仅仅在这里才开始涉及到。开始涉及到。简单规范简单规范与

25、机器无关与机器无关易于优化与转换易于优化与转换2022-5-7374、中间代码生成、中间代码生成v例:sum=(10+20)*(num+square); 5、代码优化、代码优化v任务：对于前阶段产生的中间代码进行加工变换，任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。以期在最后阶段产生更高效的目标代码。v依循的原则：程序的等价变换规则依循的原则：程序的等价变换规则v优化的主要方面有：公共子表达式的提取、循环优优化的主要方面有：公共子表达式的提取、循环优化、删除无用代码等等。化、删除无用代码等等。6、代码生成、代码生成v任务任务: : 把中间代码变换成特定机器上

26、的目标代码。把中间代码变换成特定机器上的目标代码。v特点：特点： v目标代码三种形式目标代码三种形式: :绝对指令代码绝对指令代码: : 可直接运行可直接运行 可重定位指令代码可重定位指令代码: : 需要连接装配（多数）需要连接装配（多数）汇编指令代码汇编指令代码: : 需要进行汇编需要进行汇编7、符号表管理、符号表管理v符号表：用来登记源程序中出现的每个名字以及名字的各种符号表：用来登记源程序中出现的每个名字以及名字的各种属性。例如，一个名字是常量名、变量名，还是过程名等等；属性。例如，一个名字是常量名、变量名，还是过程名等等；若是变量名，它的类型、所占内存、地址等等。若是变量名，它的类型、

27、所占内存、地址等等。v通常，编译程序在处理到名字的定义性出现时，要把名字的通常，编译程序在处理到名字的定义性出现时，要把名字的各种属性填入到符号表中；当处理到名字的使用性出现时，各种属性填入到符号表中；当处理到名字的使用性出现时，要对名字的属性进行查证。要对名字的属性进行查证。v当扫描器识别出一个名字（标识符）后，它把该名字填入到当扫描器识别出一个名字（标识符）后，它把该名字填入到符号表中。但这时不能完全确定名字的属性，它的各种属性符号表中。但这时不能完全确定名字的属性，它的各种属性要在后续的各阶段才能填入。例如，名字的类型等要在语义要在后续的各阶段才能填入。例如，名字的类型等要在语义分析时才

28、能确定，而名字的地址可能要到目标代码生成才能分析时才能确定，而名字的地址可能要到目标代码生成才能确定。确定。v“数据结构与算法数据结构与算法”课程的应用课程的应用8、错误处理、错误处理v出错处理程序：发现源程序中的错误，把有关错误出错处理程序：发现源程序中的错误，把有关错误信息报告给用户。信息报告给用户。语法错误语法错误语义错误语义错误v好的编译程序应能最大限度地发现源程序中的各种好的编译程序应能最大限度地发现源程序中的各种错误，准确地指出错误的性质和发生错误的地点，错误，准确地指出错误的性质和发生错误的地点，并且能将错误所造成的影响限制在尽可能小的范围并且能将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，以内，使得源程序的其余部分能继续被编译下去，以便进一步发现其它可能的错误。便进一步发现其它可能的错误。2022-5-742语句语句sum=(10+20)*(num+square);的翻译过程的翻译过程2022-5-7431.4 编译程序的组织编译程序的组织v根据系统资源的状况、运行目标的要求根据系统资源的状况、运行目标的要求等，可等，可以将一个编译程序设计成多遍（以将一个编译程序设计成多遍（PassPass）扫描的形式，）扫描的形式，