搜索
编译原理及实现任课教师：韦艳艳联系电话：13877160321E-mail：ybwyy2006@yahoo.com.cn编译原理---课前思考为什么有些语言规定标识符不能超过8个字符？而有些语言对标识符的长度无限制？为什么有些语言能实现递归，而有些语言不能？C语言规定数组下界为0，上界为声明的数减1，为什么？嵌套的IF语句规定ELSE与上面最近的IF配对，为什么？为什么有些程序运行一段时间后会导致内存溢出？为什么Java实现了“一次编写，到处运行”？……学习目的了解和掌握设计和构造编译程序的基本原理、基本技术及其实现方法，加深对计算机系统的了解，培养和提高计算（机）思维能力。各章节内容第1章编译概述（2课时）第2章文法和语言（6课时）第3章词法分析（6+4课时）第4章语法分析--自顶向下分析（6+4课时）第5章语法分析--自底向上分析（6课时）第6章语法制导翻译技术（6课时）第7章符号表管理技术（2课时）第8章程序运行时的存储组织及管理（2课时）第9章语义分析和代码生成（6+4课时）第10章代码优化（2课时）学习要求认真听课积极练习课后复习编译原理好难！参考书目张幸儿编，《计算机编译原理—编译程序构造实践》(第二版)，科学出版社，2009年刘磊等编，《编译程序的设计与实现》，高等教育出版社，2004年赵克佳等译，《现代编译原理C语言描述》，人民邮电出版社，2006年张素琴，吕映芝等编，《编译原理》（第2版），清华大学出版社，2005年赵建华等译，《编译原理》(第2版)，机械工业出版社，2009年编译原理(原书第2版)作者：(美)AlfredV.AhoMonicaS.LamRaviSethiJeffreyD.Ullman译者：赵建华郑滔戴新宇出版社：机械工业出版社编译领域里程碑式的经典著作——龙书原版封面中文版封面课程学习网站清华大学北京航空航天大学武汉大学题外话基本：完成课程学习，通过考试，获得学分。提高：能够将所学知识和内容用于解决实际问题。飞跃：通过编译原理的学习，改进思维方式，为将来的工作打好基础，终身受益。考试成绩评定方法平时（30%）☆作业、课堂练习和出勤(25%)☆上机编程(15%)期考（70%）☆考试方式：笔试（闭卷）☆考试题型：①填空题②判断题③选择题④综合应用题Nomanisbornwiseorlearned.没有生而知之者第1章编译概述学习内容：1.1程序设计语言1.2翻译程序1.3编译程序的组成1.4编译程序的结构1.5编译程序的前后处理器1.6TEST语言与编译器第1章编译概述学习重点：1、编译程序2、编译程序与解释程序的根本区别3、典型的编译程序模型及其各组成部分的功能回顾：程序与程序设计语言程序：为实现特定目标或解决特定问题而用计算机语言编写的指令序列的集合。常见的程序设计语言：C++,Java,C,FORTRAN,Pascal,Lisp,Basic,ML等程序输入程序输出高级语言机器语言1.1程序设计语言(p1)1、机器语言（最低形式，属低级语言）特点：程序中的每条指令都是用二进制代码直接表示的，由它构成机器的指令系统，机器能直接识别和直接执行，但机器语言程序难写、难读、难修改，编程的工作量大，对程序员的要求高。机器语言程序示例：001111100001101011111110001001001101001100101111011101102、汇编语言（属低级语言）特点：它是机器语言的符号表示，例如用ADD表示加法，可读性等方面较机器语言有一定的改进，但还依赖于具体的机器，机器不能直接识别和直接执行。汇编语言程序示例：LDA，26//把26送到变量AADDA，36//加上36OUT(48)，A//输出到48号端口HALT//暂停3、高级语言特点：它独立于机器，比较接近自然语言，因而容易学习和掌握，且编写程序效率高，编写出的程序易读、易理解、易修改、易移植，但机器不能直接识别和直接执行。C语言程序示例：inta,c=2;a=16+c*2;printf(〞a=%d〞,a);高汇级编语语言言程程序序翻译程序1.2翻译程序(p2)源程序目标程序翻译翻译程序1、除机器语言程序外，用其它语言编写的程序都必须翻译才能被计算机识别和执行。2、翻译程序的定义：翻译程序是这样的一种程序，它能将用甲语言（源语言）编写的程序（源程序）翻译成与之等价的乙语言（目标语言）编写的程序（目标程序）。3、翻译程序在计算机系统中的所在层翻译程序属于系统软件!4、翻译方式（1）解释方式（相当口译）特点：源程序的翻译到执行只有一个阶段——解释执行阶段，即：解释程序将按源程序中语句的动态顺序，逐句地进行分析解释，并立即予以执行。在这种翻译方式下，不生成目标代码。源程序运行结果边解释边执行解释程序（2）编译方式（相当笔译）特点：源程序的翻译和目标程序的运行是分阶段进行的，它先将高级语言编写的源程序翻译成汇编语言程序或机器语言程序，然后再运行目标程序。源程序目标程序1.编译编译程序初始数据系统子程序结果2.运行编译程序vs.解释程序编译解释源程序（高级语言）编译程序目标代码（机器语言）初始数据目标代码+系统子程序运行结果1.编译阶段2.运行阶段a.当目标程序是机器语言程序时，源程序从编译到被执行的过程分为两个阶段：b.当目标程序是汇编语言程序时，源程序从编译到被执行的过程分为三个阶段：汇编语言程序汇编程序目标代码（机器语言）初始数据目标代码+系统子程序运行结果2.汇编阶段3.运行阶段源程序（高级语言）编译程序汇编语言程序1.编译阶段看起来，编译器似乎完全能代替汇编啊！回答是No。Why?1.高级语言通过编译器转化成的机器语言，受限于高级语言，其效率和功能上都有限制。比如不能过分操作内存。但通过汇编器转化过来的机器语言，效率高，且用汇编语言，可直接和CPU对话！2.汇编可以反汇编（逆向编译），即：程序（二进制机器语言）通过反汇编器（compiler），可转化为汇编代码（文本）但永远不能转化为高级语言的源代码！预处理器源程序标准源程序可重定位机器代码可重定位目标文件库文件编译程序汇编程序目标汇编程序连接加载程序绝对机器代码C语言编译系统（见p9）宏处理文件包含条件编译5、两种翻译方式的比较☺编译方式与解释方式的根本区别在于是否生成目标代码。☺在解释方式下执行源程序，易于查错，在程序执行中可以修改程序(代表有BASIC语言)。但和编译方式相比，执行效率太低。☺现在有些语言的集成开发环境提供了两种方式，如VisualBasic，调试期间可解释执行源程序，而调好的程序可以编译生成目标程序。编译过程自然语言的翻译（如把英文翻译为中文）–识别出句子中的一个个单词；–分析句子的语法结构；–根据句子的含义进行初步翻译；–对译文进行修饰；–写出最后的译文。词法分析语法分析中间代码产生优化目标代码产生例Themonkeyatethebanana.例Acompilerisacomputerprogramthattransformssourcecodewritteninaprogramminglanguageintoanothercomputerlanguage.一个平滑的字符流变成一个单词序列得到语法成分更接近机器语言更高的效率达到目标走向目标1走向目标2走向目标3走向目标4走向目标51.3编译程序的组成(p3)1、词法分析程序（又称扫描器）词法分析依次读入源程序中的每个字符，依据语言的构词规则，识别出一个个具有独立意义的最小语法单位，即“单词”，并用整数码或有意义的记号来表示每个单词的词性是保留字、标识符、分界符、运算符或常数。例如，表达式a=10+c*20的词法分析结果如右表所示。整数码记号单词100IDa21==200NUM1022++100IDc25**200NUM202、语法分析程序依据语言的语法规则，逐一地分析词法分析时得到的单词，以确定它们是怎样组成说明和语句的，以及说明和语句是怎样组成程序的。分析时如发现有不合语法规则的地方，则报告出错位置和性质；如无语法错误，则以另一种内部表示（如语法分析树或其它中间表示）给出正确的语法结构，供下一阶段分析使用。“猴子吃香蕉”的语法分析树a=10+c*20的语法分析树3、语义分析程序依据语言的语义规则对语法分析得到的语法结构进行静态语义检查（即确定类型、类型和运算合法性检查、识别含义与相应的语义处理及其它一些静态语义检查），并用另一种内部形式表示出来，供下一阶段使用。4、中间代码生成程序（可有可无）根据语法成分的语义对其进行翻译，用另一种接近于计算机的指令形式（中间代码）表示出来，供下一阶段使用。语义分析及中间代码生成示例5、中间代码优化程序(可有可无)6、目标代码生成程序将中间代码或优化之后的中间代码转换为等价的目标代码。目标代码的形式可以是绝对指令代码、可重定位的机器指令代码或汇编指令代码。目标代码依赖于具体的计算机的硬件系统结构和指令系统。7、符号表处理程序编译过程中要记录源程序中出现的标识符，并收集每个标识符的各种属性信息。符号表是由若干记录组成的数据结构，每个标识符在表中有一条记录。标识符的各种属性是在编译的不同阶段填入符号表的。词法分析阶段只能分析出标识符名，语法分析阶段只能判断标识符在语句中出现是否合法，语义分析阶段将标识符的各种属性填入符号表并使用这些属性生成中间代码。标识符名标识符类型类型地址aaa1（表示变量）1（表示整型）00018、出错处理程序编译的各个阶段都可能发现源程序中的错误。任意时刻发现错误，都应该报告错误信息，包括错误出现的位置、错误性质等，为程序员调试程序提供方便，从而使编译能继续进行。词法分析可以检测出源程序中的非法符号。语法分析能够发现程序语句中的各种语法错误，如括号不匹配等等。语义分析能判断运算对象的类型是否匹配、变量是否重复声明或没声明就使用等错误。例inta,b;a=2*)12+b);词法分析语法分析语义分析代码生成源程序前缀或后缀表达式汇编码C编译器不同的编译器，其结构也不一定相同！词法分析语法分析语义分析源程序算符-对象元组四元式代码生成中间代码优化目标代码优化的四元式FORTRAN编译器1.4编译程序的结构(p7)1、遍（趟，趟程）所谓一遍是指一个编译程序在编译时把源程序或其中间代码从头到尾扫描一遍并完成相应工作的全过程。在一遍处理中，可完成编译程序六个任务中的一个或几个。2、单遍与多遍编译程序根据编译程序在完成翻译任务的过程中需要对源程序或其中间代码扫描的遍数，可以把编译程序分为单遍编译程序(只需扫描一遍)和多遍编译程序（需扫描多遍）。（1）单遍编译程序举例编译程序对源程序只进行一遍扫描，就完成编译的各项任务，其典型结构是：以语法分析程序为主程序，词法分析程序作为语法分析的一个子程序，当语法分析需要一个新单词时，便调用词法分析程序，当它识别出一个语法成分时，就调用语义分析程序。语法分析程序开始词法分析程序语义分析程序代码生成程序取单词送单词调用返回源程序目标程序具体做法：将整个编译程序划分为若干个相继执行的模块，每一模块都对它前一模块的输出扫描一遍，并完成相应工作，然后将工作结果送给下一模块加工。（2）多遍编译程序举例例如，三遍编译程序：把词法分析作为第一遍，语法分析和语义分析作为第二遍，代码生成作为第三遍。有：词法分析代码生成源程序中间代码1目标代码语法分析语义分析中间代码23、遍的划分依据源语言的繁简宿主机的存储容量的大小编译程序功能的强弱目标程序优化的程度实现工具的先进程度设计人员的素质和数量当源语言较繁、编译程序功能很强、目标程序优化程度较高且宿主机存储容量较小时，宜采用多遍