《编译原理》第一章 cha1 引论

1第一章引论1.1编译程序和解释程序1.2编译过程和编译程序的结构（重点）1.2.1编译过程概述1.2.2编译程序结构1.2.3编译阶段的组合1.3编译程序在其他软件中的应用1.4程序设计语言范型1.5编译程序实现途径（可略）本章练习作业课程目录21.1什么是编译程序p1编译程序的必要性计算机是当代科学发展的重要工具，已渗入到各个行业乃至家庭生活中要让计算机为人类工作服务，就必须建立人与计算机之间的信息交流但计算机只认识由“0”和“1”构成的机器语言，每台机器都有自己独特的指令系统，即机器语言最早的程序就是用8进制和16进制码的机器语言书写的3编译程序的必要性（续）用机器语言书写程序，不仅不易学，而且可调试性、可读性、可维护性和结构性都很差，开发时间也很长因此，先后出现了用于源程序设计的语言：基于助记符的汇编语言接近人类自然语言的高级程序设计语言编译程序最初的定义是把一种高级语言设计的源程序(面向人的)翻译成另一种等价的低级程序设计语言(面向硬件的)即机器语言或汇编语言4程序设计语言源程序的执行方式程序设计语言源程序的执行基本有两种方式翻译使用翻译程序，将源程序翻译成为低级语言目标程序，然后执行目标程序解释

使用解释程序，对源程序逐个语句边解释边执行可比喻为译文—目标程序翻译—笔译(产生译文，可进行优化，一次翻译过后，多次使用)解释—口译(不产生译文，交互方便，节省空间，对重复部分要反复解释，效率低）5翻译程序和解释程序图解源程序(源语言)翻译程序目标程序(目标语言)源程序(源语言)解释程序输入输出共同点：都需进行词法、语法和语义分析6程序设计语言源程序的执行方式例假设有源程序：read(x);write("x=",x);read(x);write("x=",x);目标程序目标程序3X=3read(x);write("x=",x);翻译程序解释程序3X=37翻译程序的分类翻译程序按所处理源语言不同分为两种

编译程序

汇编程序高级语言源程序(*.C/*.PAS)编译程序汇编或机器语言目标程序(*.OBJ/*.EXE)汇编语言源程序(*.ASM)汇编程序机器语言目标程序(*.EXE)8编译程序和解释程序p8最主要区别是否生成目标程序运行时的存储分配源程序缓冲区名字表目标代码缓冲区编译程序用中间表示及各种表格目标代码区数据区解释系统源程序工作单元及名字表标号表缓冲区（输入输出）栈区编译程序编译时和运行时存储区内容解释程序存储区内容9编译程序和解释程序Basic、Lisp、Sql解释程序、Unix命令语言解释程序及很多脚本语言Javascript等都解释执行的。C、C++、Pascal等语言是编译执行的。Java语言的处理环境既有编译程序，也有解释程序，见图1.5(p9)Java→编译程序→Bytecode→解释程序10高级语言程序

的处理过程P1需预处理的源程序预处理程序源程序编译程序目标汇编程序汇编程序可再装配的机器代码装配/连接-编译程序可再装配目标文件绝对机器代码章节目录111.2.1编译过程概述p2编译过程可分为下面5个阶段词法分析语法分析语义分析和中间代码生成优化目标代码生成表格管理和错误处理12第一阶段词法分析p2任务输入源程序(字符串)根据语言的词法规则对构成源程序的字符串进行扫描和分解识别出一个个的单词单词内部表示形式二元式(class,value)

单词类型单词值例某C语言源程序main(){floatsum,first,count;

…sum=first+count*10;…}输出结果

classvalue

保留字main界符-左括号(界符-右括号)界符-左花括号{保留字float标识符1-id1sum…

算符-乘号*整数10…

13第二阶段语法分析p3

任务输入单词符号串根据语言的语法规则对单词符号串进行扫描和分解识别出各类语法单位程序语言的语法单位表达式、语句和程序等例X1=Y+10*Z;C语言赋值语句构成规则<赋值语句>→<标识符>=<表达式>;定义为<表达式>→<表达式>+<表达式><表达式>→<表达式>*<表达式><表达式>→<标识符>X1,Y,Z<表达式>→<常数>10可以构成语法单位的单词符号语法单位表达式Y,10,Z,10*Z

赋值语句X1=Y+10*Z;语法单位内部表示语法树

14语法单位的内部表示：语法树例某C语言源程序main(){floatsum,first,count;

…sum=first+count*10;…}<赋值语句>→<标识符>=<表达式>;<表达式>→<表达式>+<表达式><表达式>→<表达式>*<表达式><表达式>→<标识符><表达式>→<常数>赋值语句的语法树<赋值语句><标识符>=<表达式>;sum<表达式>+<表达式><标识符>first<表达式>*<表达式><标识符>count<常数>1015第三阶段语义分析与中间代码产生p4任务输入各类语法范畴根据语言的语义规则，分析其含义，并进行初步翻译产生中间代码结构简单、含义明确的记号系统介于高级语言与低级语言之间，与目标机无关便于优化、移植，容易生成目标代码形式有：三元式、四元式、树结构等。16中间代码生成举例中间代码生成（四元式）

例：语义分析将

sum=first+count*10；翻译成如下的四元式序列：(1)(inttofloat,10,_，T1)(2)(*,count，T1，T2)(3)(+,first，T2，T3)(4)(=,T3,_,sum)其中，Ti为语义分析程序为存放中间结果而生成的临时变量例某C语言源程序main(){floatsum,first,count;

…sum=first+count*10;

…}17第四阶段优化p5任务输入中间代码进行等价变换输出更高效的中间代码目的用以提高目标代码的时、空效率也就是希望完成同样功能的程序，代码优化后比优化前运行的时间短，占用的存储空间少有时二者不能同时达到，需根据实际情况取舍18优化举例优化前

(1)(inttofloat,10,_，T1)(2)(*,count，T1，T2)(3)(+,first，T2，T3)(4)(=,T3,-,sum)优化后

常数直接代入(*,count,10.0,T1)节省临时变量(+,first,T1,sum)

优化后有两条代码整数转换成实数在编译时完成临时变量只用了一个T119第五阶段目标代码生成p5任务输入优化后的中间代码变换成特定机器上的低级语言代码，实现最后的翻译产生目标代码特点依赖与机器硬件系统通常使用汇编语言作为目标程序的实现语言20目标代码生成举例为了生成高效的目标代码，需要了解机器指令系统和可用计算机资源，假设有两个可用寄存器R0和R1优化后中间代码(1)(*,count,10.0,T1)(2)(+,first,T1,sum）生成的目标代码序列(1)LDR0,count

count值送R0(2)MULR0,#10.0

计算count*10.0存于R0(3)LDR1,first

first值送R1(4)ADDR1，R0

计算first+T1存于R121表格管理(符号表管理)任务在完成以上5个过程的同时必须随时对符号表进行管理记录源程序中使用的名字收集每个名字的各种属性信息如类型、作用域、存储分配信息等例count变量类型float

first变量类型float地址22出错处理任务发现源程序中的错误检查词法、语法和语义中的错误(静态)编译程序的处理能力，如存储空间越界(动态)报告出错信息和位置处理和恢复章节目录231.2.2编译程序的结构p6词法分析程序语法分析程序语义分析程序与中间代码产生器优化器目标代码生成器表格管理出错处理7个或8个部分组成24编译程序

结构框图P6源程序字符串词法分析器单词符号语法分析器语法单位语义分析程序语法树中间代码生成器四元式代码优化程序四元式目标代码生成器汇编语言或机器语言目标程序信息表格管理程序错误检查和处理程序章节目录251.2.3编译阶段的组合p6

前端完成分析工作(与机器无关)词法分析语法分析语义分析后端完成综合工作(与机器相关)优化：改善目标代码质量目标代码生成前端源程序中间代码后端目标代码目的便于移植前端和后端的概念26遍的概念p6遍从头到尾对源程序及其内部表示扫描一次，并作有关的加工处理遍输入文件输出文件从源程序扫描是第一遍输入每前一遍的输出是后一遍的输入分遍的原则按实际情况而定多遍（结构清晰、少占内存、读写次数多，耗时）一遍（多占内存，速度快）章节目录271.3编译程序在其它软件中的应用p8语言的结构化编辑器（提示输入关键字、完成括号匹配等）语言程序的调试工具程序格式化工具（以清晰可读方式打印程序）软件测试工具：如FORTRAN，C的静态和动态测试工具（可测试程序语句的覆盖率、路径覆盖率等，都需要编译技术）高级程序设计语言的转换工具程序理解工具（OlinkC\C++数据流分析

、EclipseTptp性能分析工具）网络中的协议数据库系统中各种命令语言的翻译28

编译程序在系统软件中的所在层裸机操作系统语言处理系统应用软件层章节目录1.4程序设计语言范型p1029强制式语言ImperativeFORTRAN、BASIC、Pascal、C函数式语言

FunctionalLISP、ML逻辑式语言LogicalProlog面向对象语言

Object-OrientedSmalltalk、C++、Java、Ada章节目录301.5编译程序的实现途径p302应考虑开发周期、目标程序的效率、可移植性、可调试性、可维护性和可扩充性等构造方式手工构造用机器语言、汇编语言或高级程序设计语言书写自动构造工具Lex，Yacc分别是词法和语法分析器的生成器移植方式目标程序用中间语言自展方式(自编译方式)用T型图表示31T型图STI源语言目标语言编译程序实现语言含义S语言源程序I语言实现编译程序

T语言目标程序32编译程序设计举例已知A机器上C语言编译程序CAAC语言编译程序要求用C语言编写PASCAL语言A机器编译程序PLAAPASCAL语言编译程序最初用C语言编写PLACC语言编写的PASCAL语言编译程序CAAAPLA所求PASCAL语言编译程序33编译程序设计L1AA已知A机器上有L1

语言编译程序要求用L1语言编写L2语言的A机器编译程序L2AAL2AL1L1AAL2AA所求L2语言编译程序34PC机器上C语言编译程序自展设计实现目标CPCPC步骤1(1)先对C语言核心部分C1构造

PC编译程序，用低级语言实现C1PCPC(2)再用C1编写含C更多语言成分的C2的PC编译程序C2PCC1(3)最后用C2编写

C语言的PC编译程序CPCC2其中C1是C2的子集，C2是C的子集35PC机器上C语言编译程序自展设计实现目标CPCPC步骤2构造C2的PC编译程序C2PCC1C1PCPCC2PCPC步骤3构造C的PC编译程序CPCC2C2PCPCCPCPC合并步骤2，3C2PCC1C1PCPC①②③④⑤36L语言编译程序移植设计已知A机器高级语言L编译程序要求B机器高级语言L的编译程序已知LAA实现目标LBB①LAA②LBL用L语言编写的L→B的编译程序③LBA用A机器语言实现的L→B的编译程序④LBL用L语言编写的L→B编译程序翻译⑤LBB用B机器语言实现的L→B的编译程序章节目录37编译程序的分类p1诊断型编译程序(DiagnosticCompiler)专门用于帮助程序开发和调试着重提高目标代码效率优化型编译程序(OptimizingCompiler)提供调试、优化等功能，用户进行选择使用交叉型编译程序(CrossCompiler)产生不同于其宿主机的目标机机器代码运行编译程序的机器运行所产生目标代码的机器可变目标型编译程序(RetargetableCompiler)不需重写编译程序中与机器无关的部分就能改变目标机章节目录38本章练习

1、编译程序的结构可以分成以下7个模块