第一章编译概述

1

编译原理与技术2课程内容简介

介绍编译器(编译程序)构造的原理和实现方法理论知识包括：词法分析方法（形式语言和自动机理论）、语法分析方法（自顶向下、自底向上）、语义分析（语法制导的定义和属性文法）、代码优化等强调形式化描述技术（涉及到很多数学定义）最终目的是要求掌握涉及编译器的算法的核心思想，不偏向于某种源语言或某个目标机器3学习意义

理解高级程序语言的运行机制编译器的设计原理和实现技术具有通用性（符号处理技术以及各类分析算法）培养“计算机思维”：计算机怎么解决问题？

如何让计算机帮助我们？计算机专业特有课程其他专业的考研科目4考研试题举例（1）1、试写出一个上下文无关文法G,它能产生配对的圆括号串(例如,(),(()),()(())等,甚至包含0对括号).使用文法G给出输入串(())()#的自上而下分析过程。

5考研试题举例（2）有如下一个C语言程序，实现了m和2的n次方的乘积运算,试给出运行时整个栈的内容。栈内数据区的活动记录结构如图所示.

┌──────┐┌─────┐

│函数f返回值││返回结果值│

├──────┤├─────┤

│局部变量区││局部变量区│

├──────┤├─────┤

│全局变量区││形参单元区│

├──────┤├─────┤

│主程序main││返回地址│

│数据区│├─────┤

└──────┘│

基SP

│

├─────┤

│函数数据区│

└─────┘

考研试题举例（2）续intm;intn;

intf(n)

{intc;

if(n==0)c=m;

elsec=f(n-1)*2;

returnc;

}

voidmain()

{intn=2;

m=5;

printf("%d\n",f(n));

}67学习要求先修课程：

某一门高级程序设计语言、高等数学、数据结构、汇编语言、离散数学本课程学习方法：勤画图既涉及算法，又联系到程序设计语言，注重联想考核方式：平时30%+期末考试70%8编译原理吕映芝张素琴等清华大学出版社

程序设计语言编译原理陈火旺等

国防工业出版社编译原理及编译程序构造秦振松等东南大学出版社参考书籍参考书籍龙书Compilers:Principles,Techniques,andTools作者：AlfredV.Aho,RaviSethi,JeffreyD.Ullman.

鲸书AdvancedCompilerDesignandImplementation作者：StevenS.Muchnick虎书ModernCompilerImplementationinJava/C++/ML,SecondEdition作者：AndrewW.Appel,MaiaGinsburg9教学内容目录编译基本概念形式语言描述词法分析与有限自动机自顶向下的语法分析自底向上的语法分析语义分析与目标代码生成中间代码与代码优化10第一章编译概述1.1编译程序的基本概念1.2编译程序的逻辑结构1.3编译程序的构造1.4编译技术的应用1.5编译技术的发展1.6解释系统的定义11什么是编译程序(compiler)？定义：一个语言翻译程序作用：是把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)书写的等价的程序.12为什么需要编译(compiler)？？？13程序是按一定规则书写的一系列的符号串序列。程序设计语言是人工设计的、用来书写程序的符号语言。程序设计语言：从低级到高级分为三类机器语言汇编语言高级程序设计语言知识回顾：14

机器语言程序100058201020C(1020)=>reg2100459201024C(reg2)～C(1024)100847C01014当<=时goto1014100C50201028C(reg2)=>1028101047F0101Cgoto101C101458201024C(1024)=>reg2101850201028C(reg2)=>1028101C…15

汇编语言程序

L2，xx=>reg2C2，yreg2(x)～yBNGLESS当<=时gotoLESSST2，maxreg2(x)=>maxBEXITgotoEXITLESSL2，yy=>reg2ST2，maxreg2(y)=>maxEXIT高级程序设计语言程序

if(x>y)max=x;elsemax=y;Q：编写好的程序能直接在计算机上执行么？？？A：除非是机器语言编写的程序，否则就是

鸡同鸭讲，对牛弹琴，计算机无法理解、

识别指令，因此无法执行程序。PS：

1）会用机器语言编写程序的程序猿已经

绝种2）没必要使用低级语言编程

1617

编译器汇编器装配连接编辑

源程序

目标汇编程序

可重定位机器代码

绝对机器码可重定位目标文件库语言处理过程18编译器的功能：

担任翻译、纠错角色

高级语言书写的程序编译程序低级语言书写的程序出错信息19专业术语编译程序、编译器(compiler)编译程序接受输入的源语言(源程序)(source

language)(source

program)编译程序输出的目标语言(目标程序)(objectortargetlanguage)(objectortargetprogram)编译程序的实现语言

(implementationlanguage)SOISTI20TheroleofacompilerinasystemKernelOSKernelOSShellDBMSApplicationProgramsACompiler编译器的角色：

21编译器的性质：从软件的角度语言处理软件：

把高级语言书写的各种程序处理成可在计算机上执行的程序系统软件：

居于计算机系统中最靠近硬件的一层，其他应用软件必须要通过系统软件才能发挥作用。编译系统和操作系统与具体的应用领域无关，所以都是系统软件221.2编译过程和编译程序的结构编译逻辑过程词法分析语法分析语义分析中间代码生成代码优化目标代码生成23英译汉与编译的类比1.识别出句子中的一个个单词2.分析句子的语法结构3.分析句子的语义4.初步翻译5.译文修饰6.写出最后译文1.词法分析2.语法分析3.语义分析4.中间代码生成5.优化6.目标代码生成24编译程序总体结构中间代码目标代码生成器代码优化器语义分析中间代码生成器语法分析器表格管理出错处理中间代码目标代码语法单位单词符号词法分析器源程序25一、词法分析从左至程右解析源程序(字符流)识别出单词token词法分析器（扫描器LexicalAnalyzer）：1）从左到右扫描源程序（字符串序列）并将该字符串

转换成单词(记号串—Token）2）查词法错误并进行标识符登记

（符号表格管理）输入：源程序（字符串）输出：二元组(类型码，属性值)26

词法分析举例：

从左往右词法分析pascal语句

输入：position:=initial+rate*60;

单词类型（类型码）单词值标识符1(id1) position运算符(赋值符号):=标识符2(id2) initial运算符(加号) +标识符3(id3) rate运算符(乘号) *整型常量 60分界符 ；输出27词法分析举例：一个C源程序片断：inta;

a=a+2;单词类型

单词值关键字int标识符(变量名)

a分界符；标识符(变量名)

a运算符(赋值号)=标识符(变量名)a运算符(加号) +整型常量 2分界符 ；输出28总结conclusion:词法分析(lexicalanalysisorscanning)--Thestreamofcharactersmakingupasourceprogramisreadfromlefttorightandgroupedintotokens,whicharesequencesofcharactersthathaveacollectivemeaning.单词---token保留字、关键字---reservedword/keyword标识符---identifier(user-definedname)29二、语法分析语法分析器(SyntaxAnalyzer、Parser解析器）：依据源程序语言的语法规则把源程序的单词序列组成语法短语(表示成语法树)，将词组成各类语法成分：表达式、短语、语句、子程序…构造语法分析树指出语法错误指导语义翻译（作为语义分析的基础）输入：Token序列输出：语法成分->表达式、短语、语句、子程序30语法分析举例：position:=initial+rate*60根据pascal语法规则进行语法分析<赋值表达式>::=<标识符>“:=”<表达式>

<表达式>::=<表达式>“+”<表达式><表达式>::=<表达式>“*”<表达式><表达式>::=“(”<表达式>“)”

<表达式>::=<标识符><表达式>::=<整数>

<表达式>::=<实数>

::=可以解释为由。。。组成或者定义成。。。。31

赋值表达式标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*32C语句：res=fact*(term1+term2);根据C语法规则进行语法分析<赋值语句>::=<标识符>“=”<表达式>“；”<表达式>::=<表达式>“+”<表达式>

<表达式>::=<表达式>“*”<表达式><表达式>::=“(”<表达式>“)”<表达式>::=<标识符><表达式>::=<整数>

<表达式>::=<实数>33C语句：res=fact*(term1+term2);*；赋值语句表达式=）（fact表达式res表达式表达式表达式表达式+term1term234总结conclusion:语法分析(syntaxanalysisorparsing)Thepurposeofsyntaxanalysisistodeterminethesourceprogram’sphrasestructure.

Thisprocessisalsocalledparsing.Thesourceprogramisparsedtocheckwhetheritconformstothesourcelanguage’ssyntaxandtoconstructasuitablerepresentationofitsphrasestructure：语法树(推导树)(parsetreeorderivationtree).35三、语义分析功能：分析由语法分析器识别出的语法成分的语义语义审查(静态语义)获取标识符的语义属性：类型、作用域等，填充符号表格语义检查：运算的合法性、取值范围、类型匹配、类型转换、上下文的相关性等子程序的静态绑定：代码的相对地址变量的静态绑定：数据的相对地址36语义分析（基于语法树）

position:=initial+rate*60;

假设initial、rate是double类型

60:=+*Id1positionId2initialId3rate类型转换37总结conclusion:语义分析(semanticanalysis)Theparsedprogramisfurtheranalyzedtodeterminewhetherit

conformstothesourcelanguage’scontextualconstraints:scoperules,typerulese.g.Torelateeachappliedoccurrenceofanidentifierinthesourceprogramtothecorrespondingdeclaration.38四、中间代码生成源程序的另一种表示方式三元式、四元式、波兰式、逆波兰式简单规范与机器无关易于优化与转换成目标代码39例:源代码id1+id2*id3后缀表示(逆波兰Anti-PolishNotation)id1id2id3*

+前缀表示(波兰PolishNotation)+id1*id2id3四元式表示(三地址码)1(*,id2,id3,T1)2(+,id1,T1,T2)

三元式表示1(*,id2,id3)2(+,id1,(1))40四元式中间代码：id1:=id2+id3*60

假设id1，id2，id3都是double类型(1) (inttoreal, 60 - t1 )(2) (* , id3 t1 t2 )(3) (+ , id2 t2 t3 )(4) (:= , t3 - id1 )41总结conclusion:

中间代码生成(intermediatecodegeneration)Wewantthisrepresentationtobeeasytogenerate,easytotranslateintothetargetprogram.Therepresentationcanhaveavarietyofforms,butacommononeiscalledthree-addresscodeor4-tuplecode.42五、代码优化目的：提高运行速度（节省时间）和节省存储空间

43代码优化例子：源代码优化t1=b*ct1=b*ct2=t1+0t2=t1+t1t3=b*ca=t2t4=t2+t3a=t4a=2*b*c44代码优化例子：中间代码优化id1:=id2+id3*60(1) (inttoreal 60 - t1 )(2) (*id3 t1 t2 )(3) (+ id2 t2 t3 )(4) (:= t3 - id1 )

(1)(* id3 60.0 t1 )(2)(+id2 t1 id1 )45与机器无关的优化局部优化常量合并：常数运算在编译期间完成，如8+9*4，包括const符号常量公共子表达式的提取（分支结构、循环结构）:

基本块内循环优化强度削减用较快的操作代替较慢的操作比如+代替*代码外提将循环不变计算移出循环46与机器有关的优化寄存器的利用将常用量放入寄存器，以减少访问内存的次数体系结构MIMD、SIMD、SPMD、向量机、流水机、多核存储策略根据算法访存的要求安排：Cache、并行存储体系——减少访问冲突任务划分按运行的算法及体系结构，划分子任务(MPMD)47总结conclusion:代码优化(Intermediatecodeoptimization）1）Theoptimizeracceptsinputintheintermediaterepresentationandoutputaversionstillintheintermediaterepresentation.2）compilerattemptstoproducethesmallest,fastestandmostefficientrunningresultbyapplyingvarioustechniques.48六、目标代码生成将中间代码转换成目标机上的机器指令代码或汇编代码。目标代码的多种形式具有绝对地址的机器指令模块结构的机器指令（需要链接程序）汇编语言形式的目标汇编程序49目标代码生成举例(* , id3 60.0 t1 )(+ , id2 t1 id1 )movfid3,R2mulf #60.0,R2movfid2,R1addf R2,R1movfR1,id150编译过程：51表处理词法分析源程序目标程序错误处理语法分析语义分析目标代码生成前端后端中间代码优化中间代码生成52Structureofacompiler53前端与后端前端与源语言有关、与目标机器无关的部分词法分析、语法分析、语义分析与中间代码生成、与机器无关的代码优化后端与目标机器有关的部分与机器有关的代码优化、目标代码生成54符号表管理记录源程序中使用的各种符号和名字收集每个名字的各种属性信息类型、作用域、分配存储信息管理各种符号表（常数、标号、变量、函数、结构……），登记、查找源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息。辅助语法检查、语义检查完成静态绑定、管理编译过程Hash表、链表等各种查、填表技术（数据结构）55出错处理

进行各种错误的检查、报告、纠正以及相应的续编译处理（如：错误的定位与局部化）词法：拼写错误……语法：语句结构、表达式结构……语义：类型不匹配……56程序错误语法错误语义错误运行57编译程序结构(components)设计词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序符号表管理程序出错处理程序58根据系统资源的状况、运行目标的要求等，将一个编译程序设计成多遍扫描的形式，在每一遍扫描中，完成不同的任务。每遍的工作由从外存上获得的前一遍的中间结果开始（对于第一遍而言，从外存上获得源程序），完成有关工作之后,把结果记录于外存。既可以将几个不同阶段合为一遍，也可以把一个阶段的工作分为若干遍。遍（Pass）编译程序的架构设计591）一遍的编译程序

即对源程序进行一遍扫描，就完成编译程序的各项任务。该编译程序的核心是不产生中间代码。

工作过程如下：①当语法分析器需要读进一个新的单词符号时，就调用词法分析器，词法分析器从源程序中依次读入字符，并组合成单词符号，把其送回语法分析器；②当语法分析器识别出一个语法短语时，就调用语义分析程序进行语义分析，并生成目标程序；③当源程序处理完后，转善后处理，即整理目标程序（如优化等），并停机。词法分析器语法分析器整理目标程序停机语义分析及代码生成取单词返回单词语法成分返回源程序目标代码编译程序的架构设计602）多遍编译程序把编译的5个阶段应完成的工作分遍来做，每一遍完成一个或相连几个阶段的工作。源程序词法分析程序语法分析程序语义分析程序代码优化程序目标代码生成程序目标程序表格处理程序出错处理程序编译总控程序中间语言1，表中间语言2，表中间语言3，表优化代码，表工作过程如下：编译程序的主程序调用词法分析器扫描源程序，并将它转换成一种内部表示，称为中间语言1，同时产生有关的一些表，然后主程序再调用语法分析器，它以中间代码1为输入，进行语法分析，产生中间语言2……最后主程序调用目标代码生成器，把输入的中间代码转换为等价的目标代码。61编译程序分遍的优缺点优点：1.首先，减少对内存容量的要求，分遍后，在编译时以遍为单位分别调入编译程序，各遍编译程序在内存中可以相互覆盖；2.其次，可使各编译程序功能独立、单纯，相互联系简单，编译程序结构清晰；3.再次，能够实现充分地优化工作，以获得高质量的目标程序；4.最后，通过分遍将编译程序的前端和后端分开，为编译程序的移植创造条件。缺点：增加了不少重复性工作，比如每一遍都有读符号、送符号等工作，这就降低了编译的效率。62编译阶段和运行阶段内存存储结构

编译时运行时符号表中间代码缓冲区目标代码缓冲区目标代码区数据区源程序缓冲区63编译程序选择什么语言来编写？设计目标目标程序小，执行速度快。编译程序小，执行速度快。诊断能力强，可靠性强。可移植性，可扩充性。641.以汇编语言和机器语言为工具来构造优点:可以针对具体的机器，充分发挥计算机的系统功能。生成的目标程序效率高。缺点:程序难读、难写、易出错、难维护、生成编译程序的效率低。652.高级语言书写用已有高级语言实现其它高级语言的编译程序:例如用C写PASCAL语言的编译器，然后编译优点:程序易读、易理解、容易维护、生产编译程序的效率高。缺点:难以充分发挥计算机的系统功能，生成的目标程序效率低。663.利用工具，编译程序自动生成LEX

词法分析程序产生器YACC语法分析程序产生器编译程序自动产生器L语言的语法描述语义描述目标语言或机器描述L语言的编译程序671.4编译技术的发展功能：集成开发环境下实现编译程序实现方式手工机器语言汇编语言高级程序设计语言自动构造工具lexyaccgcc68编译程序的语言范型语言范型(paradigms)命令式(imperativelanguage)应用式(applicative)基于规则的（rule-based）面向对象的（object-oriented）69编译程序的执行环境批处理环境：将源程序作为整体处理排除程序错误不能接受任何外部帮助交互环境：解释增量式编译嵌入式系统环境：交叉编译分布并行环境：并行编译集成式开发环境：独立编译设计时同时考虑编译和调试70集成化的程序开发环境程序开发环境编辑程序编译程序连接程序调试工具。。。它将相互独立的程序设计工具集成起来，以便为程序员提供完整的、一体化的支持，从而进一步提高程序开发效率改善程序质量。如Visualstudio.NetMyEclipse等

711.5

编译技术的应用语法制导的结构化编辑器程序格式化工具软件测试工具程序理解工具高级语言的翻译工具……72编译技术的应用结构化编译器程序分析工具静态分析动态分析度量工具结构度量模块接口复杂度

c分析工具(sourceinsight)广泛的语言领域数据库系统查询脚本语言置标语言(SGML.HTML.XML)73源程序输入数据计算结果解释程序1.6解释系统（解释程序）74高级语言解释系统(interpreter)功能：让计算机执行高级语言与编译程序的不同1）不生成目标代码2）能支持交互环境源程序

初始数据解释程序计算结果75对比编译程序与解释程序编译程序：直接对源程序中的语句进行分析，执行其隐含的操作。如：……

b:=2;a:=b+2;编译程序

writea;……解释程序直接将4的值输出（显示）Int2StbLdbadd2Sta生成代码76解释系统存储结构解释程序源程序符号表缓冲区(输入输出)栈区77编译和解释的区别：目标程序源程序编译程序初始数据计算结果源程序解释程序初始数据计算结果语法的表示方法：78•口语•语法图

•BNF表示法

79语法图：函数定义函数首部函数体函数首部函数值类型函数名（参数表列）

函数体{说明部分控制部分}80巴科斯范式（BackusNourForm或BackusNormalForm，简记为