《编译原理Lecture 1 前言和引论.》由会员分享，可在线阅读，更多相关《编译原理Lecture 1 前言和引论.（54页珍藏版）》请在金锄头文库上搜索。
1、本讲主要内容 一、课程准备和成绩评定 二、编译概貌速揽 课程准备和成绩评定 一、预备知识和前序课程 预备知识：形式语言与自动机理论、数据结构及 算法设计、高级程序设计语言、计算 机体系结构和汇编语言等知识。 前序课程：形式语言学、离散数学、PASCAL/C 程序设计语言、算法基础、数据结 构、计算机原理、汇编语言等。 二、编译课程与计算机学科课程体系（ 知识框架、知识体系、知识结构） 在China Computing Curricula （CCC）中将计 算机学科分为抽象、理论和设计三个学科形态 ，14个知识领域，共132个知识单元。 1、三个学科形态（过程） 理论：源于数学。主要要素为定义和
2、公理、定理、证明、结果的解释。 用这一过程来建立和理解计算学科所依据的数学原理。其研究内容的基本特 征是构造性数学特征；本门课程中的体现：形式语言和自动机理论等。 抽象：即模型化。源于实验科学，主要要素为数据采集方法和假设的形 式说明、模型的构造与预测、实验和结果分析。在为可能的算法、数据结构 和系统结构等构造模型时采用此过程，然后对所建立模型的假设、设计策 略、理论依据等进行试验。试验研究包括：分析计算的局限性、有效性、新 计算模型的特性、新理论或假设的验证等。抽象的结果是概念、符号和模 型。 设计：源于工程学。用来开发那些求解给定问题的系统和设备。主要要 素为需求说明、规格说明、设计和实现
3、方法、测试和分析；本课程中体现为 ：语法分析、语义分析、代码生成及优化等编译器设计和实现过程。 2、课程(计算机学科)中的学科方法论 三个学科形态对应于计算机学科中求解问题的三种典型过程，是 学科方法论最基本的内容。其中，“认识”指的是学科中的“抽象过 程”（感性认识）和“理论过程”（理性认识），“实践”指的是学科 中的“设计过程”。认识过程以数学方法为主，实践过程以系统方 法为主。 3、课程(计算机学科)中的典型研究方法 数学方法：用数学语言表达事物的状态、关系和过程 ，经过推导形成解释和判断，包括问题的描述与变 换。如公理化方法、构造性方法（以递归、归纳和迭 代为代表）、模型化等。其基本特
4、征是高度抽象、严 谨精确、具有普遍意义。 系统科学方法：核心是将研究对象看成一个整体，使 思维对应于适当的抽象级别上，力求系统的整体优 化。系统科学方法一般遵循的原则：整体性、动态 性、最优化、模型化。具体方法有：系统分析法（如 结构化方法、原型法、OO方法等）、黑箱方法、功能 模拟方法等。 4、14个主领域 离散结构（DS) 程序设计基础（PF) 算法与复杂性（AL） 体系结构（AR） 操作系统（OS） 网络计算（NC） 程序设计语言（PL）（54个核心学时） PL2：虚拟机（2个核心学时）、PL3：语言翻译简介（6）、PL5：抽象机制（6 ）、PL8：语言翻译系统、PL10：程序设计语言的
5、语义 人机交互（HC） 图形学和可视化计算（GV） 智能系统（IS） 信息管理（IM） 软件工程（SE） 社会和职业问题（SP） 科学计算（CN） 三、教材和参考资料 主讲教材： 编译原理（第二版）张素琴等编著 清华大学出版社 参考书籍： （1）Compilers：Principles,Techniques, x=a+b*50; 关键字int 标识符x，a，b 整常数50 运算符+，*，= 分界符, ，; 编译程序各阶段任务 词法分析 输入源程序，对构成源程序的字符串进行扫描和分 解，依据词法规则(或构词规则)识别出一个个的单 词(单词符号或符号)，转换成机器容易识别的内码 形式，是最初级的语
6、法分析。 内码用二元式(类号，内码)表示。 编译程序各阶段任务 语法分析 根据语言的语法规则(文法规则)，把单词符号串组 成各类语法单位(语法成分、语法范畴)，如：说明 语句、表达式、赋值语句、循环语句、分（子）程 序、程序等，同时进行语法检查。 语法规则一般用Backus-Naur-Form(BNF)式描述， 形式如下： A:=B|C或AB|C 语法分析有两种方法： 自上而下的推导(Derive)和自下而上的归约(Reduce) 语法分析对说明语句填写符号表，一般语句构造语 法树（P3图1.5） 编译程序各阶段任务 语义分析和中间代码生成 对语法分析所识别的各种语法成分的意义(即语义)进行确
7、定 并加以处理。语义分析要对操作数是否已定义，是否类型相 同等进行检查，并根据检查的情况作出相应处理。生成的中 间代码应保证与源程序的语义等价性。 根据语义规则产生一种介于源语言与目标代码之间的一 种中间代码。 中间代码是不依赖于机器但是又便于生成依赖于机器的 目标代码的一种结构简单、含义明确的记号系统。 中间代码常用逆波兰式、三元式、四元式、抽象机代 码来表示。 编译程序各阶段任务 中间代码常用的形式 1 1、（逆）波兰表示、（逆）波兰表示idid 1 1 idid 2 2 idid 3 3 * * + + 2 2、三元组表示三元组表示 1.(1.(*,*,idid 2 2 , id, id
8、 3 3 ) ) 2.(2.(+ +, ,idid 1 1 ,(1,(1式式) ) E E E + E E + E id E * E id E * E id id id id 4 4、语法树、语法树 例1：id1+id2*id3 3 3、四元组表示四元组表示 (*(*, ,idid 1 1 ,id,id 2 2 ,T,T 1 1) ) (+,id(+,id 3 3 ,T,T 1 1 ,T ,T 2 2) ) 例2：Z=(X+0.418)*Y/W 序号算符左操作数右操作数结果 (1)+X0.418T1 (2)*T1YT2 (3)/T2WZ 编译程序各阶段任务 编译程序各阶段任务 代码优化 对前阶
9、段产生的中间代码进行等价的加工变换，生成 更为高效(省时间和空间)的目标代码。 依据是等价变换原则。 优化主要包括： 与机器无关：利用操作符的结合性、交换性及分配性等性质 实施常数合并，在处理表达式时利用冗余子表达式的消除技 术。在处理循环时，可利用循环展开、频度削弱、强度削弱 等技术； 与机器有关：寄存器分配算法、累加器优化算法；与体系结 构（MIMD、SIMD、SPMD、向量机、流水机）有关的优化 ；与存储策略有关的优化，如，根据算法访问的特征安排： Cache、并行存储体系减少访问冲突。 编译程序各阶段任务 FOR K:=1 TO 100 DO BEGIN M:=I+10*K N:=J+
10、10*K END; (1) ( :=,1, ,K )(1) ( :=,1, ,K ) (2) ( j,100,K,(9) ) (2) ( :=,I, ,M ) (3) ( *,10,K,T1 )(3) ( :=,J, ,N ) (4) ( +,I,T1,M )(4) ( j,100,K,(9) ) (5) ( *,10,k,T2 )(5) ( +,M,10,M ) (6) ( +,J,T2,N )(6) ( +,N,10,N ) (7) ( +,K,1,K )(7) ( +,K,1,K ) (8) ( j, , ,(2) )(8) ( j, , ,(4) ) (9) (9) 代码优化示例（中间
11、代码用四元式表示）： 代码优化前代码优化后 编译程序各阶段任务 目标代码生成 把中间代码变换成指定机器上的绝对指令代码或可 重定位指令代码或汇编指令代码 与硬件系统的功能部件的运用、机器指令的选择、 寻址方式、各种数据类型变量的存储空间分配，累 加器和寄存器的使用和调度等有很大的关系。 NAME(名字)INFORMATION(信息) 编译程序各阶段任务 表格管理 表格管理是一个贯穿编译全过程的工作。编译程序在分析源程序时， 需要记录标识符的各种属性信息；在语义分析和代码生成阶段，要对 建立的符号表进行检索，提取相应的属性信息。 编译程序在工作过程中需要建立多种表格，用以登记源程序的 各类信息和
12、编译各阶段的进展状况。 设计高效的符号表管理程序是编译程序设计中的一个重要问 题。 编译程序中常见的符号表有： 名字特性表、常数表、标号表、分程序入口表、中间代码 表、过程引用表、循环特征表、等价名表、公用链表等 表格的结构大体如下： 编译程序各阶段任务 错误检测及处理 错误可发生在编译的各个阶段，错误处理也是贯穿 编译全过程的一件工作。 词法分析阶段可查出的错误，如标识符的组成不符 合词法规则；语句结构错误是在语法分析中可查出 的错误；还有语义分析阶段可查出的错误，即结构 正确，但所涉及的操作无意义或错误。 在编译时查出的错误，称为Compile-time error；在 运行时表现出来的错
13、误称为Run-time error。 前端和后端 前端包括编译逻辑结构中的分析部分。即词法分 析、语法分析、语义分析和中间代码生成，除此还包括符 号表建造及相应分析中的错误处理以及与机器无关的优化 部分。 后端包括与目标机有关的部分，即综合部分。它包 括目标代码生成及生成期间对符号表的相应检索操作和错 误处理操作，以及与机器相关的代码优化部分。 意义： 将编译系统划分为前后端，有利于移植编译系统和 利用后端为同一目标机配置不同语言的编译系统。 编译程序各阶段任务编译程序各阶段任务 语法分析 扫描器语义分析 和代码生成 源程序 目标代码 取单词 (类型,内码) 返回 归约 一遍扫描编译程序 编译
14、程序各阶段任务 遍(pass) 对源程序(或其中间形式)从头至尾扫描一次并进行 有关加工处理，生成新的中间形式或最终目标程序 ，称为一遍。以下是语法制导翻译程序的结构示意 图（一遍扫描结构）： 分遍原则： 目标质量高低(高则多遍) 机器内存大小(小则多遍) 源语言简繁(繁则多遍) 设计人员多少(多则多遍) 优缺点： 有利于降低对运行环境（如：内存）的要求 有利于建立结构清晰的编译程序 有利于编译优化工作 有利于编译程序的移植 增加了符号的读取和查找工作，降低了编译效率 编译程序各阶段任务 编译程序的生成 编译程序的生成方式有以下几种： 用汇编语言编写编译程序 高级语言编写 编译程序自动生成器
15、自展和移植 编译程序构造 要在某机器上为某种语言构造一个编译 程序，必须掌握以下三方面的知识： 源语言 目标语言 编译方法及开发环境 1.4 编译程序的前后处理器 1.4.1 预处理器 1.4.2 汇编程序 1.4.3 两遍汇编 1.4.4 加载器和连接编辑器 1.4.1 预处理器 任务：产生编译程序的输入 功能：1. 宏处理(宏扩展) 2. 文件包含 3. “合法的”预处理器 4. 语言扩充 宏处理包含两类语句：宏定义和宏调用； “合法的”预处理器：在原语言中增加更先进的控制结构和 数据结构设施，增强语言的功能。如Ansi C 中增加面向对 象的支持，Pascal 5.5在v5.0中增加面向对象的支持等。 1.5 处理源程序的软件工具1 1.语法制导的结构化编辑器 2.符号调试器（DEBUG程序） 3. 程序格式化工具 4. 软件测试工具 5. 程序理解工具 6. 高级语言的翻译工具 1 梅宏,王千祥等. 软件分析技术进展J. 计算机学报, 2009年9期, P1697-1710 1. 语法制导的结构化编辑器 特点：除了通常的正文编辑和修改功 能外，还能对源程序进行语法 分析。 2. 符号调试器 特点：可以根据源程序进行逐行跟踪 调试，提供变量跟踪、
