编译原理讲义

编译(biānyì)原理讲义第一页，共19页。第一章 绪论(xùlùn)程序设计语言(yǔyán)分低级语言(yǔyán)和高级语言(yǔyán)两类低级语言(yǔyán):机器语言(yǔyán)、汇编语言(yǔyán)及其它面向机器的程序设计语言(yǔyán)；其特点对计算机的依赖性强、直观性差、编写程序的工作量大，对程序设计人员要求较高。高级语言(yǔyán)：有几百种之多，常用的有BASIC、FORTRAN、PASCAL、C、JAVA等，高级语言(yǔyán)在算法描述能力、编写和调试效率上均比低级语言(yǔyán)优越。但高级语言(yǔyán)与机器之间有一“鸿沟”：机器不能理解高级语言(yǔyán)！因此，要在计算机上实现高级语言(yǔyán)，需使该语言(yǔyán)能让计算机所理解。方法：对程序进行翻译或进行解释。翻译：在计算机中放置一能由计算机直接执行的翻译程序，它将某程序设计语言(yǔyán)（源语言(yǔyán)）所编写的程序（源程序）作为加工对象，将其翻译成为与之等价的另一种语言(yǔyán)（目标语言(yǔyán)）的程序（目标程序）可见，计算机执行某高级语言(yǔyán)程序，需经两个阶段，即编译阶段和运行阶段。在执行时，一般应有一些辅助子程序配合。如：数据格式转换子程序、标准函数、动态存储分配子程序等等，由它们构成的子程序库称为运行系统。编译系统=编译程序+运行系统第二页，共19页。计算机执行高级语言(yǔyán)程序的步骤源程序P目标程序(mùbiāochénɡxù)P’运行(yùnxíng)结果S编译程序数据运行程序计算机A计算机B编译阶段运行阶段第三页，共19页。编译程序(biānyìchénɡxù)与解释程序高级语言程序也可通过解释程序来执行解释程序：以源程序为输入，在执行过程中不再产生目标程序，而是边解释边执行。解释程序运行效率不高目前，纯粹的解释程序已不多见，通常是将编译和解释作某种程度的结合。编译程序是现今任何计算机系统的最重要的系统程序。本课程的目的，在于向大家介绍设计(shèjì)和构造编译程序的基本原理和基本方法，其中许多方法也适用于构造解释程序或汇编程序。第四页，共19页。编译(biānyì)过程概述翻译外文书刊与编译工作(gōngzuò)比较第五页，共19页。编译程序(biānyìchénɡxù)的构成编译程序主要由八个部分构成(gòuchéng)：1.词法分析程序（扫描器scanner）2.语法分析程序（分析器parser）3.语义分析程序4.中间代码生成程序5.代码优化程序6.目标代码生成程序7.错误检查和处理程序8.各种信息表格的管理程序第六页，共19页。1.2编译程序(biānyìchénɡxù)的逻辑结构词法(cífǎ)分析程序语法分析程序(chéngxù)语义分析程序中间代码生成代码优化程序目标代码生成信息表管理程序错误检查和处理程序源程序目标代码第七页，共19页。一个(yīɡè)微型PASCAL语言的定义为了便于说明，我们引入一个微型(wēixíng)PASCAL语言（PASCAL/M）的定义。它只有如下四种语句：1）PROGRAM语句；2）说明语句；3）BEGIN-END语句；4）赋值语句；每个PASCAL/M语句都以PROGRAM语句开头，后跟说明语句，再跟以一个BEGIN-END语句，在其内部可以有若干赋值语句。右边是一个该语言程序的例子。程序(chéngxù)1-1一个PASCAL源程序(chéngxù)sourcePROGRAMsource;{Thislittlesourceprogramisusedtoillustratecompilingprocedure}VARx,y,z:integer; a:integer;BEGIN{Thisprogramhasonly4statement}x:=23+5;z:=xDIV-3;y:=z+18*3;a:=x+(y-2)DIV4;END.第八页，共19页。1.2.1词法(cífǎ)分析程序（扫描器）词法分析程序的任务是：1）识别出源程序的各个基本语法单位（单词或语法符号）2）删除无用的空白字符及其它与输入介质相关的非实质性字符（空格、回车等）3）删除注释4）进行词法检查，报告所发现的错误扫描(sǎomiáo)器依次查看缓冲区中源程序的各字符，根据当前正查看的字符之种类，并参考扫描(sǎomiáo)过程中已得到的信息，就能判断出该字符在源程序中所处地位。一般它是下述几种情况之一：1）正处理的注释中的一个字符；2）无用字符；3）下一个单词的首字符；4）正识别(shíbié)的单词中的一个字符；5）不合法的字符。扫描器输出以单词为单位的单词流例如，以特殊符号“#”分隔的单词流：#PROGRAM#source#;#VAR#x#,#y#,#z#:#integer#;#a#:#integer#;#BEGIN#x#:=#23#+#5#;#z#:=#x#DIV#-#3#;#y#:=#z#+#18#*#3#;#a#:=#x#+#(#y#-#2#)#DIV#4#;#END#.#第九页，共19页。单词流的内部(nèibù)表示注意，前面的单词流形式(xíngshì)只是我们为说明原理便于阅读而假定的形式(xíngshì)。为了让计算机能够方便地识别和使用，在实际中的常用方法是将单词计算机内部表示为一个有序对(Class,Value)。Class为一整型数，用于标识该单词的类别；Value用于存放单词的值。例如对于source程序，可将其单词分为四类：（1）保留字（2）专用符号（3）标识符（4）整数。这样，source程序相应的单词流为：(1,‘PAROGRAM’)(3,’source’)(2,’;’)(1,’VAR’)(...)……(2,’;’)(1,’END’)(2,‘.’)第十页，共19页。(store,T,,’z’){Thislittlesourceprogramisusedtoillustratecompilingprocedure}(div,T,’4’,T)如：数据格式转换子程序、标准函数、动态存储分配子程序等等，由它们构成的子程序库称为运行系统。一般它是下述几种情况之一：在执行时，一般应有一些辅助子程序配合。当前较通用的方法是半机械化的“语法制导翻译”方法。(store,T,,’x’)除报错外，编译程序还可生成一些另外的注释信息，它有助于程序设计(chénɡxùshèjì)人员调试程序。（3）模块(mókuài)结构的机器指令（浮动地址）。各种信息表格的管理程序在执行时，一般应有一些辅助子程序配合。常见的~有：逆波兰式、三元式、四元式及树形结构等。4）正识别(shíbié)的单词中的一个字符；语义分析(fēnxī)及(1,‘PAROGRAM’)(3,’source’)(2,’;’)(1,’VAR’)(.1.2.2语法分析程序(chéngxù)（分析器）语法分析程序以词法(cífǎ)分析程序输出的单词流为输入，分析源程序的结构，判断它是否为相应程序设计语言的合法程序。方法：试图为源程序构造一个语法树。分析工作是在相应程序设计语言的语法规则指导下进行的。语法规则描述了该语言的各种语成份的组成结构。所谓语法树只是逻辑概念上的，并不是在机器内真要存储一个树形结构。第十一页，共19页。1.2.3语义分析程序一程序设计语言具有语法和语义两个特征。语法特征描述各成份的形式或结构；语义特征描述各语法成份的含义与功能，即规定它们的属性或在执行应进行的运算或操作。因此，只有进行了语义分析，才能让计算机知道，应进行何操作或运算。在进行语义分析时还应进行相应的语义检查(jiǎnchá)（类型匹配、矛盾说明、参数匹配等）。语义处理尚无公认的方法来系统地描述。当前较通用的方法是半机械化的“语法制导翻译”方法。第十二页，共19页。中间(zhōngjiān)代码生成为了处理方便和便于代码(dàimǎ)优化，在语义分析后通常并不直接产生目标代码(dàimǎ)，而是生成介于二者之间的中间代码(dàimǎ)。常见的~有：逆波兰式、三元式、四元式及树形结构等。例如，source程序中的第四条赋值语句相应的逆波兰式可写成：axy2-div+:=source程序相应的四元式表示为：(prologue,’source’)(add,’23’,’5’,T)(store,T,,’x’)(div,’x’,’-3’,T)(store,T,,’z’)(mult,‘18’,’3’,T)(add,’z’,T,T)(store,T,,’y’)(sub,’y’,’2’,T)(div,T,’4’,T)(add,’x’,T,T)(store,T,,’a’)(epilogue)第十三页，共19页。1.2.5代码优化程序(chéngxù)代码优化的目的是生成质量较高的目标代码衡量质量的标准：空间指标和时间指标优化方法分类(fēnlèi)：与机器有关和无关两类优化指标有时是相互矛盾的，应根据具体情况进行取舍和侧重source程序优化后结果：(prologue,’source’)(store,28,,’x’)(div,’x’,’-3’,T)(store,T,,’z’)(add,’z’,54,T)(store,T,,’y’)(sub,’y’,’2’,T)(div,T,’4’,T)(add,’x’,T,T)(store,T,,’a’)(epilogue)第十四页，共19页。1.2.6目标(mùbiāo)代码生成程序任务：将中间代码翻译成为目标程序(chéngxù)首先确定源语言各种语法成份的目标代码结构；再根据需要制定中间代码到目标代码的翻译策略这部分程序(chéngxù)对具体机器的依赖性很强，需具体情况具体分析通常，目标代码的三种形式：（1）具有绝对地址的机器指令代码；（2）汇编语言形式的目标程序；（3）模块(mókuài)结构的机器指令（浮动地址）。Source程序对应的80386汇编程序见书中P9第十五页，共19页。1.2.7错误(cuòwù)检查和处理程序程序中出现错误是难免的。一完善的编译程序应具有很强的查错能力，并能准确地报告源程序中错误的种类及位置。除报错外，编译程序还可生成一些另外的注释信息，它有助于程序设计(chénɡxùshèjì)人员调试程序。常见的辅助手段根据请求输出“对照图”和各变量的值。Source程序的对照图，见P10表1-2第十六页，共19页。1.2.8信息(xìnxī)表管理程序编译(biānyì)过程中，需经常收集、记录或查询程序中所出现的各种量的有关属性（信息）。为此，编译(biānyì)程序需要建立一批不同用途的表格（常数表