编译编译原理原理及及实现实现技术技术课程内容课程内容介绍编译器介绍编译器基本构造原理基本构造原理基本实现方法基本实现方法基本处理技术基本处理技术介绍理论知识介绍理论知识形式语言形式语言自动机理论自动机理论强调强调形式化描述形式化描述技术技术抽象思想抽象思想强调强调对编译原理对编译原理宏观理解宏观理解对编译处理技术的对编译处理技术的宏观宏观理解理解课程意义课程意义掌握编译程序的构造原理和实现技术。掌握编译程序的构造原理和实现技术。深入对程序设计语言的理解；（片面深入对程序设计语言的理解；（片面vsvs全面）全面）提高软件开发能力；（同一功能的不同实现）提高软件开发能力；（同一功能的不同实现）提高元级程序设计能力；（编译器的设计实现）提高元级程序设计能力；（编译器的设计实现）增强形式化、抽象化能力；（问题形式化）增强形式化、抽象化能力；（问题形式化）编译技术的广泛的应用。编译技术的广泛的应用。嵌入式系统（受限资源利用）嵌入式系统（受限资源利用）ERPERP二次开发（三分之一需要修改）二次开发（三分之一需要修改）冗余代码分析（变量调用、闲置函数）冗余代码分析（变量调用、闲置函数）第一章第一章 编译引论编译引论程序设计语言程序设计语言程序设计环境中的编译器程序设计环境中的编译器编译程序的结构编译程序的结构编译程序的设计与实现编译程序的设计与实现1 1 程序设计语言与编译程序程序设计语言与编译程序程序语言的发展程序语言的发展高级语言的实现方式高级语言的实现方式1.11.1 程序设计语言的发展程序设计语言的发展机器语言机器语言：能够被计算机的硬件系统直接执行的：能够被计算机的硬件系统直接执行的指令程序，如指令程序，如“00010001010001000101”。汇编语言汇编语言：将硬件指令用一些助记符表示，即符：将硬件指令用一些助记符表示，即符号化的机器语言，如号化的机器语言，如“ADDADD，MOVMOV”。高级语言高级语言：从程序员的角度出发，对汇编语言进：从程序员的角度出发，对汇编语言进一步抽象，使用便于理解的一步抽象，使用便于理解的“自然语言自然语言”表述。表述。 机器语言机器语言 汇编语言汇编语言 高级语言高级语言 翻译程序翻译程序TranslatorTranslator1.21.2 高级语言的实现方式高级语言的实现方式汇编程序汇编程序AssemblerAssembler编译程序编译程序CompilerCompiler1.2.11.2.1 解释方式解释方式解解释释方方式式：接接受受用用程程序序语语言言（源源语语言言）编编写写的的程程序序（源源程程序序），然然后后直直接接解解释释执执行行源源程程序序。解解释释器器相相当当于于源源程程序序的的抽抽象象执执行行机机，是是语语言言的的实现系统。实现系统。 解释程序解释程序源程序源程序输入数据输入数据计算结果计算结果(*.(*.bas/*.java)bas/*.java)1.2.21.2.2 编译方式编译方式编编译译方方式式：源源语语言言为为高高级级语语言言，目目标标语语言言是是低低级语言（汇编或机器语言）的翻译程序。级语言（汇编或机器语言）的翻译程序。 源程序源程序目标程序目标程序(*.(*.C/*.PAS)C/*.PAS)(*.(*.OBJ/*.EXE)OBJ/*.EXE)编译程序编译程序1.2.3 1.2.3 转换方式转换方式转转换换方方式式：将将A A语语言言程程序序转转换换为为B B语语言言程程序序，用用B B语语言言已已有有的的编编译译器器去去编编译译执执行行。（同同级级程程序序设计语言）设计语言） 编译、解释编译、解释A A语言程序语言程序转换程序转换程序B B语言程序语言程序源程序源程序目标程序目标程序(*.(*.C/*.PAS)C/*.PAS)(*.(*.OBJ/*.EXE)OBJ/*.EXE)解释程序解释程序源程序源程序输入数据输入数据计算结果计算结果(*.(*.bas/*.java)bas/*.java)A A语言程序语言程序转换程序转换程序编译程序编译程序B B语言程序语言程序2 2 编译程序和程序设计环境编译程序和程序设计环境典型典型IDEIDE编译器在编译器在IDEIDE中的位置中的位置编辑器编辑器：除了一般文本编辑器的功能外，还可具除了一般文本编辑器的功能外，还可具有对正在编辑的文本进行分析、提示，能自动地有对正在编辑的文本进行分析、提示，能自动地提供关键字和与其匹配的关键字提供关键字和与其匹配的关键字 等功能。等功能。预处理器预处理器：工作包括删除源程序中的注释、执行：工作包括删除源程序中的注释、执行宏替换以及包含文件的嵌入等。宏替换以及包含文件的嵌入等。编译器编译器简约而不简单简约而不简单连接程序连接程序：将不同的目标文件中编译或汇编的代：将不同的目标文件中编译或汇编的代码集中到一个可执行文件中，并将目标和标准库码集中到一个可执行文件中，并将目标和标准库函数的代码以及计算机的操作系统提供的资源连函数的代码以及计算机的操作系统提供的资源连接在一起。接在一起。装入程序装入程序：把程序加载到内存储器中，以便执行。：把程序加载到内存储器中，以便执行。 调试程序调试程序：检查编译了的程序中的错误。：检查编译了的程序中的错误。 3 3 编译程序的逻辑结构编译程序的逻辑结构编译器的结构编译器的结构各组成部分的功用各组成部分的功用实例实例编译器 3.1 3.1 编译程序的逻辑结构图编译程序的逻辑结构图词法分析词法分析语法分析语法分析语义分析语义分析源程序源程序中间代码生成中间代码生成中间代码优化中间代码优化目标代码生成目标代码生成目标程序目标程序出错处理出错处理表格管理表格管理 词法分析词法分析Lexical Analysis(Scanner/Tokenizer)Lexical Analysis(Scanner/Tokenizer) 扫描源程序的字符串，依循语言的词法规则，识扫描源程序的字符串，依循语言的词法规则，识别每一个有集体含义的子串，并将其表示成所谓别每一个有集体含义的子串，并将其表示成所谓的机内表示记号形式（的机内表示记号形式（TokenToken）。语法分析语法分析 Syntax Analysis(Parser)Syntax Analysis(Parser)依据语言的依据语言的语法规则，将单词的语法规则，将单词的TokenToken序列分解成各类序列分解成各类语法短语法短语（可表示为语法树）语（可表示为语法树），确定整个输入串是否构，确定整个输入串是否构成一个语法上正确的程序。成一个语法上正确的程序。语义分析语义分析 Semantic AnalysisSemantic Analysis 检查检查源程序有无源程序有无语语义错误义错误，为为代代码码生成生成阶阶段收集信息。（段收集信息。（类类型型检查检查、强强制制类类型型转换转换、下、下标标越界越界检查检查等）等）中间代码生成中间代码生成 Intermediate Code Generation Intermediate Code Generation 将源程序转换成一种称为中间代码的内部表示形将源程序转换成一种称为中间代码的内部表示形式。中间代码是一种式。中间代码是一种简单的、含义明确的记号系简单的、含义明确的记号系统，统，例如四元式（运算符，对象例如四元式（运算符，对象1 1，对象，对象2 2，结果）。，结果）。中间代码优化中间代码优化 Code OptimizationCode Optimization 变换或改造中变换或改造中间代码，生成的目标代码更为间代码，生成的目标代码更为高效高效，即节省时间，即节省时间和空间。和空间。目标代码生成目标代码生成 Target Code GenerationTarget Code Generation 中中间间代代码变换为码变换为特定机器上的特定机器上的绝对绝对指令代指令代码码，或可重定，或可重定位的指令代位的指令代码码或或汇编汇编指令代指令代码码。 表格管理表格管理 Table ManagementTable Management 为了合理的管理为了合理的管理（构造、查找、更新（构造、查找、更新）表格（符号表、类型）表格（符号表、类型信息表信息表），设立一些专门子程序称为表格管），设立一些专门子程序称为表格管理程序。理程序。 错误处理错误处理 Error HandlerError Handler 各个阶段还存在着错误各个阶段还存在着错误处理模块，当有错误出现时，由相应的错误处理处理模块，当有错误出现时，由相应的错误处理模块给出解决方案，使得编译器能够继续进行下模块给出解决方案，使得编译器能够继续进行下去。去。3.2 Example of a piece of C code: 3.2 Example of a piece of C code: realreal sum, first; sum, first;intint count; count;sum = first + count * 10;sum = first + count * 10;Out of the Out of the scannerscannerrealrealReservedReservedsumsumIdentifierIdentifierfirstfirstIdentifierIdentifier; ;SemicolonSemicolonintintReservedReservedcountcountIdentifierIdentifiersumsumIdentifierIdentifier= =EqualEqualfirst first IdentifierIdentifier+ +AddAddOut of the Out of the parserparserAssignmentAssignmentIdentifierIdentifierEqualEqualExpressionExpressionsumsum= =ExpressionExpressionAddAddExpressionExpressionIdentifierIdentifier+ +IdentifierIdentifierMulMulVariableVariablefirstfirstcountcount* *1010Out of the Out of the semantic analyzersemantic analyzer= =Id1Id1+ +Id2Id2* *Id3Id3int_to_realint_to_real1010Out of the Out of the intermediate code intermediate code generatorgenerator1.1.(int_to_real,10,-,t1)(int_to_real,10,-,t1)2.2.(*,id3,t1,t2)(*,id3,t1,t2)3.3.(+,id2,t2,t3)(+,id2,t2,t3)4.4.(=,t3,-,id1)(=,t3,-,id1)Out of the Out of the optimizeroptimizer1.1.(*,10.0,id3,t1)(*,10.0,id3,t1)2.2.(+,t1,id2,id1)(+,t1,id2,id1)Out of the Out of the target code generatortarget code generator1.1.MOVMOVid3,id3,R1R12.2.MULMUL#10.0,#10.0,R1R13.3.MOVMOVid2,id2,R2R24.4.ADDADDR2,R2,R1R15.5.MOVMOVR1,R1,id1 id1 4 4 编译程序的设计与实现编译程序的设计与实现4.1 4.1 编译程序设计编译程序设计分遍分遍 根据需求一至几十遍都有根据需求一至几十遍都有要点要点准确理解源语言准确理解源语言确定对编译的要求（可能导致过程差异）确定对编译的要求（可能导致过程差异）理解目标机（即目标程序的细节）理解目标机（即目标程序的细节）形式化描述（正则表达式、自动机）形式化描述（正则表达式、自动机）具体设计具体设计4.2 4.2 实现方法实现方法转换法转换法：将：将A A语言程序转换成语言程序转换成B B语言的程序，再利语言的程序，再利用用B B语言的编译器实现语言的编译器实现A A语言。语言。移植法移植法：修改目标代码或者修改编译程序的后端。：修改目标代码或者修改编译程序的后端。 自展法自展法：先用机器语言编写源语言的一个子集的：先用机器语言编写源语言的一个子集的编译程序，然后再用这个子集作为书写语言，实编译程序，然后再用这个子集作为书写语言，实现源语言的编译程序。现源语言的编译程序。 工具法工具法：LexLex、YaccYacc、AccentAccent、BisonBison等工具生成等工具生成语法分析程序。（软件自动化研究成果）语法分析程序。（软件自动化研究成果）小结小结编译器结构编译器结构三个三个“不容易不容易”