【精品】【考研计算机专业课】天津大学 编译原理讲义 ch1编译原理（可编辑.ppt

《【精品】【考研计算机专业课】天津大学 编译原理讲义 ch1编译原理（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】天津大学 编译原理讲义 ch1编译原理（可编辑.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【考研计算机专业课】天津大学 编译原理讲义 ch1编译原理引子n你用编程语言（例如你用编程语言（例如C C）写的程序是）写的程序是怎样被计算机运行的？怎样被计算机运行的？通常使用的编程语言n我们通常使用的编程语言（例如C）是高级语言（high-level language）：n语义清晰，贴近自然语言（即人类使用的语言），易于理解，编程方便。n其程序无法被计算机理解和直接执行。计算机使用什么语言？n计算机使用机器语言（machine language）：n机器语言程序本质上是一串0，1串，它可以被计算机理解并执行。n人类理解机器语言比较困难，因而直接使用机器语言编程是困难而效率低下的。编译器的作

2、用n我们用高级语言编写的程序只有被转换成机器语言程序后才能被计算机理解和执行。n这种转换是由编译器进行的。n在这一过程中，被转换程序称为源程序，其编程语言（通常是高级语言）称为源语言（source language），而转换后的程序称为目标程序，其语言称为目标语言（target language）。教材和参考书n教材：n编译原理，陈意云、张昱，第2版，高教出版社，2009。n英文参考书：nCompilers:Principles,Techniques,and Tools.A.V.Aho,M.S.Lam,R.Sethi,and J.D.Ullman,2nd edition,Addison-Wes

3、ley,2007.（Dragon book）nModern Compiler Implementation in C/Java/ML.Andrew W.Appel with Jens Palsberg.第2版影印版，高教出版社。（Tiger book）nAdvanced compiler design and implementation.Steven S.Muchnick.影印版，机械工业出版社，2003。（Whale book）教材和参考书（续）n中文参考书：n编译原理，蒋立源、康慕宁，第3版，西北工业大学出版社，2005。n上述英文参考书的中文翻译版本。n程序设计语言编译原理，陈火旺等，

4、第3版，国防工业出版社，2000。授课内容：n编译器概述n词法分析n上下文无关文法和语法分析n语法制导翻译n中间代码生成n符号表管理n运行时存储管理n查错纠错课程要求：n本课程共68学时，其中讲授51学时，实验17学时。n由于概念较多，因此要求大家：n认真听，理解并牢记各种概念n课后复习并加深理解，多看书和课件。n独立认真完成作业。n课程设计：自己动手第一章 绪论n什么是编译器？n为什么要学习编译原理？n编译过程可以如何划分？各阶段的作用？n编译器是如何组织的？n编译器是如何产生的？n如何构造一个编译器？什么是编译器？n翻译器（translator）：n能够将一种语言编写的程序翻译成语义等价的

5、另外一种语言的程序的软件系统。n这里的语义通常指操作语义，即程序做什么事（见例0.1）。n编译器（compiler）：n翻译器的一种，其特点是目标语言比源语言低级（低级语言：编程语言越接近机器语言，我们就说这种语言越低级。）什么是编译器？n直观上理解的编译器就是这样一种程序：编译器源程序目标程序编译器目标程序（机器语言程序）输入输出目标程序的运行关于解释器n解释器（Interpreter）：不产生目标代码，而是解释执行源程序解释器输入输出源程序编译器和解释器的综合应用nJava语言将编译器和解释器综合使用：n先用编译器把源程序翻译成一种叫做字节码（bytecode）的中间语言程序n再用一个虚拟

6、机对字节码程序进行解释执行编译器源程序中间语言程序虚拟机输入输出源程序如何成为可执行程序？n除编译器外，源程序要想成为可执行程序还需要经过下列一些程序的处理：n预处理器（preprocessor）：先于编译器执行，负责收集处于不同文件中的源程序，处理宏等等。n汇编器（assembler）：如果编译器的目标程序不是机器语言程序而是汇编程序，则需要汇编器将汇编语言程序翻译成可重定位的机器语言程序。n链接器和装载器（linker&loader）：链接器负责将处于不同模块的可重定位机器语言程序以及库文件等链接在一起。装载器负责把链接后的程序装入内存准备执行。源程序预处理器编译器汇编器链接/装载器经过修

7、改的源程序目标汇编程序可重定位的机器程序目标机器程序关于交叉编译源程序P目标程序P编译器C运行系统原始数据D运行结果S计算机A计算机B编译阶段运行阶段A,B是不同类型计算机为什么要学习编译原理？n你们中的大部分人在今后的职业生涯中都不会去进行编译器的设计工作，但是学习编译原理至少有下列一些好处：n能够确切地知道你所编写的程序是如何从高级语言程序变成可执行程序的，从而对编程有更深入的理解；n编译器设计中的一些原理和技术足以应用到你今后职业生涯中的很多领域。例如，我们将涉及到编程语言、体系结构、算法、语言理论、软件工程等知识。1.1 编译器的划分语法分析器语义分析器源程序中间代码生成器代码优化器代

8、码生成器目标程序出错管理器符号表管理器 词法分析器1.1.1 词法分析（lexical analysis）n词法分析（又称扫描scanning）：字符流 记号流（token，即课本中所称的内部格式）n记号：二元组词法规则共用名称，表示类别词法单元的专属特征值1.1.1 词法分析（续）n词法分析的主要任务：n将正确的单词（lexeme）识别为记号n删除分隔单词的空格（或制表符、回车符等分隔符）。n删除注释。n词法检查，报告错误。n词法分析将在课本第三章详细介绍。1.1.1 词法分析（续）符 号 表 positioninitialrate.123词法分析器 position=initial+rat

9、e*60标识符的总称position在符号表中的条目只有一个实例，因而省略属性值本应为，简化1.1.2 语法分析（parsing）n语法分析（syntax analysis），简称分析（parsing）。记号流 树型抽象中间表示n语法分析能够展示各种语言“构造”（construct，如函数、语句、表达式等）的层次性。语法规则1.1.2 语法分析（续）n典型的中间表示是语法树符 号 表 positioninitialrate.1231.1.2 语法分析（续）n语法分析中使用的语法规则可以用上下文无关文法CFG（Context-Free Grammars，也称前后文无关文法）或Backus-Nau

10、r范式（BNF）来描述。n课本第二章介绍上下文无关文法，第四章介绍语法分析。1.1.2 语法分析（续）符 号 表 positioninitialrate.123语法分析器 语法树1.1.3 语义分析n语义分析：分析语法结构的含义和功能；检查程序语义正确性，为代码生成阶段收集信息。n语义分析的一个重要部分是类型检查。n类型是否合法：例，数组下标为整数（实数）n隐式类型转换（coercion）n目前较流行的是使用“语法制导翻译”的方法将语法分析和语义分析有机地组织起来。n课本第五章介绍语法制导翻译。1.1.3 语义分析（续）语义分析器符 号 表 positioninitialrate.1231.1

11、.4 中间代码生成n在对源程序进行过语法和语义分析之后，很多编译器会显式的生成一种比较低级的中间表示，即中间代码。n中间表示必须具备特点：n易于产生。n易于翻译成目标程序。1.1.4 中间代码生成n中间表示有多种形式：逆波兰表示（后缀表示）、三地址码（三元式、四元式等）、树型结构等。nposition=initial+rate*60的逆波兰表示为：position initial rate 60*+=n一种很常用的中间表示是三地址码。1.1.4 中间代码生成（续）中间代码生成器t1=inttofloat(60)t2=id3*t1t3=id2+t2id1=t3符 号 表 positioninit

12、ialrate.123特点：必须先决定运算次序 临时变量 不一定有三个运算对象1.1.4 中间代码生成（续）n中间代码的产生与语义分析紧密相连，课本在第五章介绍中间代码生成。语法分析器语义分析器源程序中间代码生成器代码优化器代码生成器目标程序出错管理器符号表管理器 词法分析器前四阶段完成对源程序的分析，它们与源语言密切相关，因此也称为前端（front-end）1.1.5 代码优化n为了产生质量较高的目标代码，通常在中间代码生成和目标代码生成两个阶段之间，插入一个代码优化阶段。n目标程序的质量：时间指标和空间指标。1.1.5 代码优化（续）代码优化器t1=id3*60.0id1=id2+t1t1

13、=inttofloat(60)t2=id3*t1t3=id2+t2id1=t3符 号 表 positioninitialrate.1231.1.5 代码优化（续）n能够完成大多数优化的编译器叫做“优化编译器”。（编译时空复杂度增加，可靠性下降）n简单优化也可使目标程序运行时间大大缩短，而编译速度并未降低太多。n优化在课本第八章介绍，不作为本课程授课内容。1.1.6 目标代码生成n代码生成阶段：由中间代码生成目标代码（机器指令或汇编码）n目标代码的种类：n不可重定位的机器指令代码（具有绝对地址，直接可运行）n可重定位的机器指令代码（模块化，具有相对地址，需链接运行）n汇编代码（需经汇编阶段）1.

14、1.6 目标代码生成（续）n目标代码生成阶段所做的工作：n为变量选择存储单元n把中间代码翻译成等价的机器指令序列。n此阶段的关键问题是：寄存器分配n代码生成主要在课本第九章介绍，不作为本课程授课内容。1.1.6 目标代码生成（续）代码生成器t1=id3*60.0id1=id2+t1LDF R2,id3MULF R2,R2,#60.0LDF R1,id2ADDF R1,R1,R2STF id1,R1符 号 表 positioninitialrate.123语法分析器语义分析器源程序中间代码生成器代码优化器代码生成器目标程序出错管理器符号表管理器 词法分析器后两阶段完成对源程序的综合，由于与目标机

15、器更相关，故也称后端（back-end）1.1.7 符号表管理语法分析器语义分析器源程序中间代码生成器代码优化器代码生成器目标程序出错管理器符号表管理器 词法分析器1.1.7 符号表管理（续）n编译器的一项重要工作是记录并收集标识符及其各种属性，以提供标识符存储分配、类型、作用域等信息。n符号表为每个标识符保存一个记录数据结构，其中的域是标识符的各个属性。n该数据结构应允许编译器迅速找到一个名字的记录并读取和存储数据。1.1.7 符号表管理（续）n课本第六章介绍符号表的组织和管理。符 号 表 positioninitialrate.1231.1.8 错误诊断和报告语法分析器语义分析器源程序中间

16、代码生成器代码优化器代码生成器目标程序出错管理器信息表管理器 词法分析器1.1.8 错误诊断和报告n编译器的每个阶段都可能发现程序的错误并做相应处理。n词法分析阶段：单词不能形成正确词法记号n语法分析阶段：记号流违反语法规则n语义分析阶段：语法正确但操作无意义n每个阶段的错误处理将在与该阶段相关的章节介绍。（课本中集中在第十章介绍）1.2 编译程序的组织n上述对编译器进行的阶段划分是一种逻辑组织上的划分。n在编译器实现时，几个阶段的活动可能被组合起来形成一“遍”（pass）n每一“遍”都会读一个输入文件（例如源程序或源程序的中间表示），并写一个输出文件。n例：前端的四个阶段：词法分析、语法分析

17、、语义分析、中间代码生成可以组合形成一“遍”。1.2 编译程序的组织（续）n现代高级语言大都不能通过一遍扫描就完成从源程序到目标代码的转换，因此一般都需要多遍扫描。1.2 编译程序的组织（续）n多遍扫描的优点：n模块化结构，各遍扫描功能相对独立，编译程序结构清晰n由于对源程序及其内部结构多次扫视加工，故有利于细致充分的代码优化n编译程序可按模块逐次调入内容，有利于采用覆盖技术以减少编译所占内存。1.2 编译程序的组织（续）语法分析器语义分析器源程序中间代码生成器代码优化器代码生成器目标程序出错管理器符号表管理器 词法分析器阶段分组：前端（front-end）后端（back-end）1.2 编译

18、程序的组织（续）n编译器划分前端后端有利于移植操作系统平台Java虚拟机(解释器)Java编译器Java源程序(.java)Java虚拟机代码(.class)解释执行1.3 编译器的生成nX86机器上原有一个C编译器(CX86)，如何得到一个X86机器上的C+编译器(C+X86)？n写一个(C+X86)编译器的C源程序，在X86机器上用(CX86)编译器编译即可。1.3 编译器的生成（续）nX86机器上原有一个C编译器(CX86)，如何得到一个MIPS机器上的C编译器(CMIPS)？n先写一个(CMIPS)的C源程序n在X86机器上用(CX86)编译器编译该源程序得到X86机器上的(CMIPS

19、)编译器。n在X86机器上用刚生成的(CMIPS)编译器再编译C源程序一次，即得到MIPS机器上的(CMIPS)编译器。1.3 编译器的生成（续）nX86机器上没有任何编译器，如何得到一个C编译器？（自编译过程）n先对C语言的核心部分构造一个很小的编译器（用低级语言构造）n用生成的这个编译器作为工具，继续构造一个稍大一些的编译器。n如此扩展下去，直到得到一个完整的C编译器。1.4 如何构造编译器？n深刻理解源语言的语法和语义n深入理解目标语言所在机器的硬件系统结构和操作系统功能n掌握编译方法本节小结n翻译器、源语言、目标语言、编译器、解释器的概念。n高级语言、低级语言、机器语言、操作语义的概念

20、n编译器的几个基本阶段，及各阶段的功能。n编译器组织方式：前端、后端；遍。n编译器的生成和构造本节小结（续）语法分析器语义分析器源程序中间代码生成器代码优化器代码生成器目标程序出错管理器符号表管理器 词法分析器作业n本章无书面作业。n课后请注意理解本章所提及的所有概念（翻译器、源语言、目标语言、编译器、解释器、高级语言、低级语言、机器语言、操作语义、前端、后端、遍、编译器的各阶段等），这些概念将在后续课程中起重要作用。n 返回例 0.1：解释语义的例子n操作语义：读入a，b两个整数，比较其大小，如果a大于等于b则打印a，否则打印b。程序：int a,b;scanf(“%d,%d”,&a,&b);if(a=b)printf(“max=%d”,a);else printf(“max=%d”,b);返回