编译原理第一章.pptx

《编译原理第一章.pptx》由会员分享，可在线阅读，更多相关《编译原理第一章.pptx（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理编译原理Compilers:Principles,Techniques,andTools5/14/2023课程介绍课程介绍programmingPrincipleofcompilerconstructionFoundationofprogramminglanguage课程介绍课程介绍q学习设计与构造程序设计语言编译程序的原理与方法源程序源程序编译编译程序程序目标程序目标程序连接连接可执行程序可执行程序为什么学习编译原理？为什么学习编译原理？q编译程序构造是计算机科学中一个非常成功、成熟的分支，也是最早获得成功的分支之一；q它与文件转换程序关系密切，不仅仅是于编译程序；q包含许多在实际应

2、用中有用的算法。课程内容课程内容q编译器构造的一般原理和基本实现方法强调对编译原理和技术的宏观理解不偏向于某种源语言或目标机器q理论知识形式语言和自动机理论属性文法类型理论等形式化描述技术q预备知识高级程序设计语言高级程序设计语言数据结构、汇编、离散数学内容简介内容简介q第一章 编译器的基本结构q第二章 简单的语法制导翻译器q第三章 词法分析q第四章 语法分析q第五章 语法制导翻译q第六章 中间代码生成q第七章 运行时刻环境q第八章 代码生成重点教材教材q计算机科学丛书计算机科学丛书编译原理编译原理(本科教学版本科教学版)()(第第2 2版版)阿霍(Aho.A.V.)等 赵建华,郑滔,戴新宇(

3、译)第1版第2版中译本课程要求课程要求q课堂q课后习题q实验阅读、查找相关资料编程完成实验提交实验报告q成绩平时成绩：考勤、作业、实验期末考试第一章绪论1.1什么是编译程序什么是编译程序qC7 06 0000 0002C7 06 0000 0002machine languageqmov X,2mov X,2Assembly languageqX=2X=2C languageq程序设计语言高级语言汇编语言机器语言q在计算机上如何执行一个高级语言程序？把高级语言程序翻译成机器语言程序运行所得的机器语言程序求得计算结果Compiler:ABridgeBetweenPLandHardwareOper

4、atingSystemHardware(LowLevelLanguage)CompilerApplications(HighLevelLanguage)a=b+c*dMOVA,dMULA,dADDA,bMOVva,AAssemblyCodesRegister-basedorStack-basedmachinescompilerq编译器是一个程序，读入某一语言写的源程序，并将其翻译成等价的、用另一语言写的目标程序，并且能够向用户报告被编译的源程序中出现的错误。CompilerSourceprogramTargetprogramErrormessageq程序的等价程序的等价：若两个程序P1和P2所

5、允许的输入集合相同，且对相同的输入，均产生相同的输出，则称程序P1和P2等价。q狭义看法：通常，源程序是用某种高级语言编写的，而目标程序是用目标代码或机器代码编写的。q广义看法：程序变换，翻译器翻译器(translator)(translator)C+C;Pascal C；翻译器translatorq翻译翻译：在不改变语义的条件下，把某种语言的源程序转换成另一种语言程序目标语言程序，称为翻译。执行翻译的软件，称为翻译程序。源程序翻译程序目标程序解释和编译q解释器解释器(interpreter)(interpreter)在一种语言的机器上，直接执行直接执行用另一种语言写的程序的过程，称为解释。实

6、现解释的软件，称为解释程序。以源程序作为输入，不产生目标程序，一边解释一边执行。优点：直观易懂，结构简单，易于实现人机对话缺点：效率低q编译编译由高级语言转换为低级语言,然后对编译出来的目标程序目标程序进行运行计算翻译程序与解释程序的区别q二者本质区别是输出不同：翻译程序的输出是与源程序等价的目标程序；解释程序实际是一台虚拟机，其输出是被执行程序所定义的输出结果。Example:JavaCompiler&JavaVMqJava语言结合了编译和解释的过程。JavaBytecodesJavaprogram(app.java)(Javac)(app.class)Thecontextofacompil

7、erPreprocessorSourceProgramModifiedSourceProgramCompilerTargetAssemblyProgramAssemblerRelocatableMachineCodeTargetMachineCodeLibraryfilesand/orRelocatableobjectfilesLinker/LoaderThecontextofacompiler编译过程概述编译过程概述q编译程序的工作，从输入源程序开始，到输出目标程序结束，与自然语言之间的翻译有很多相似之处。q英文翻译成中文的步骤：识别出句子中的单词分析句子的语法结构根据句子的含义进行初步分析

8、对译文进行修饰写出最后的译文词法分析词法分析代码优化代码优化语法分析语法分析语义分析及中间代码生成语义分析及中间代码生成目标代码生成目标代码生成1.2编译器结构编译器结构q分析综合模型（Analysis-Synthesis Model）Two parts of compilation:Analysis:Decompose Source into an intermediate representationSynthesis:Target program generation from representation编译程序的结构框图编译程序的结构框图词法分析器词法分析器语法分析器语法分析器语义分

9、析器语义分析器源程序源程序中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器目标程序目标程序出错管理器出错管理器符号表管理器符号表管理器AnalysisofthesourceprogramqAnalysis consists of three phases词法分析Lexical analysis/Linear analysis/Scanning语法分析Syntax analysis/Hierarchical analysis/Parsing语义分析Semantic analysis词法分析词法分析(Lexicalanalysis)q词法分析程序又称扫描程序。q是编译过程的第一

10、个阶段，其任务是：读源程序的字符流、识别单词（如标识符、整数、界限符等），并转换成内部形式。q输入：源程序中的字符流q输出：词法单元（tokens）词法分析举例Pascal赋值语句position:=initial+rate*60wouldbegroupedintothefollowingtokens:1.Identifierposition2.Assignmentsymbol:=3.Identifierinitial4.Plussign+5.Identifierrate6.Multiplicationsign*7.Number60分隔这些记号的空格被删除。（注释也可以在词法分析中处理。）符符

11、 号号 表表positioninitialrate.123词法分析器词法分析器id1:=id2+id3*60position:=initial+rate*60lexicalanalyzer词法分析举例词法分析举例q一个C源程序片段：int a;a=a+2;词法分析后返回(如右图)：单词类型单词类型 单词值单词值保留字 int标识符 a界符 ;标识符 a算符(赋值)=标识符 a算符(加)+整数 2界符;语法分析（Syntaxanalysis）q语法分析程序又称识别程序(parser)。q功能：读入由词法分析程序识别出的符号，根据给定语法规则，识别出各个语法结构（检查语法的正确性）,并生成另一种内

12、部表示。q输入：由词法分析程序识别出并转换的tokensq输出：内部表示，如语法分析树(syntax tree)assignment statementidentifier:=expressionpositionexpressionexpression+expressionexpression*identifiernumberrate60identifierinitialParsetree语法分析语法分析Syntaxtreeisacompressedrepresentationoftheparsetree.:=position+*rate60initial符符 号号 表表positionini

13、tialrate.123语法分析器语法分析器id1:=id2+id3*60:=+*60id1id2id3SyntaxAnalyzer语义分析语义分析(Semanticanalysis)q对语法分析树或其他内部中间表示进行静态语义检查，并生成目标代码或中间代码。确定类型类型检查识别含义与相应的语义处理其它静态语义检查q为了优化，往往先生成内部中间表示代码：如逆波兰表示、三元式序列、四元式序列，或者抽象语法树。语义分析语义分析错在哪里？例1：intarr2,c;c=arr1*10;例2：Programp(input,output);varrate:real;procedureinitial;pos

14、ition:=initial+rate*60Semanticanalysisinsertsaconversionfromintegertoreal.:=position+*rate60initialinttoreal插入语义处理结点的语法树插入语义处理结点的语法树符符 号号 表表positioninitialrate.123语义分析器语义分析器:=+*60id1id2id3:=+*60id1id2id3inttorealSemanticAnalyzer符符 号号 表表positioninitialrate.123中间代码生成器中间代码生成器temp1:=inttoreal(60)temp2:=

15、id3*temp1temp3:=id2+temp2id1:=temp3:=+*60id1id2id3inttorealIntermediateCodeGenerator符符 号号 表表positioninitialrate.123代码优化器代码优化器temp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3temp1:=id3*60.0id1:=id2+temp1CodeOptimizer符符 号号 表表positioninitialrate.123temp1:=id3*60.0id1:=id2+temp1代码生成器代码生成器M

16、OVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1CodeGeneratorcharacterstreamtokenstreamsyntaxtreesyntaxtreeIntermediaterepresentationIntermediaterepresentationtarget-machinecode分析分析q 将源程序正文转换为内部表示，并收集和确定各结构成分之间的相关信息。（1）词法分析：将字符序列转换为单词序列。（2）语法分析：将单词序列重组为程序结构 （通常表示为分析树）。（3）语义分析：确定各语法成分之间的对应关系和一致性，如标

17、识符的作用域、类型匹配等等。综合综合q根据源程序的语法结构和语义信息，生成目标代码。中间代码生成：中间语言的形式与汇编语言相近，比较简单，且与具体机器无关，便于代码的优化和移植。代码优化：改善代码的时空效率，如常数表达式求值，公共子表达式优化，循环语句中的不变表达式外提，削减运算强度等等。代码生成：生成等价的汇编或机器语言程序。符号表管理符号表管理q符号表存放与单词有关的信息，如标识符的类型、地址，常数的值等等。符号表的管理包括表的生成、填写、查阅、删除等。错误处理错误处理单词错语法错语义错（如多重定义、类型不匹配）环境错（如数组太大、名字太长）溢出外设错误（I/O错）访问内存越界编译错误运行

18、错误逻辑错误错误分类TheGroupingofPhasesq编译各阶段的组合q相关概念：前端、后端遍(pass)源代码前 端中间代码后 端目标代码Front End :Analysis +Intermediate Code GenerationBack End :Code Generation +Optimizationvs.遍遍(pass)q从过程上看，编译是从源程序开始，经过若干中间表示形式，最终变换成目标程序。q所谓一遍一遍是指，编译程序以一种表示形式为输入，经过处理产生下一种表示形式的过程。例如，从源程序（字符序列）到单词序列可以作为一遍，从语法树到中间代码也可以作为一遍。q典型的编译

19、程序一般遍数在二至三遍。遍数多一些，编译程序的逻辑结构会较清晰，对机器资源的要求也较低，然而，编译速度也随之降低。遍遍(pass)q遍：指对源程序或源程序的中间结果从头到尾扫描一次，并做有关的加工处理，生成新的中间结果或目标代码的过程。遍与阶段的含义并无关系q多遍扫描的好处节省内存空间，提高目标代码质量，使编译的逻辑结构清晰q多遍扫描的缺点编译时间较长在内存许可情况下，还是遍数尽可能少些为好CompilerConstructionToolsq编译技术的发展第一个编译程序出现在20世纪50年代早期，多是将算术公式翻译成机器代码20世纪50年代末，提出并研制编译程序的编译程序20世纪60年代起，出现自展技术（用被编译的语言来书写该语言自身的编译程序）编译实现方式的发展q手工编写直接用机器语言编写编译程序用汇编语言编写编译程序注：编译程序核心部分常用汇编语言编写用高级语言编写编译程序（普遍采用的方法）q自动构造工具Lex:Scanner Generators Yacc:Parser Generators(用于自动产生LALR分析表)课后要求q精读教材1.1、1.2q略读1.31.6q问题：1.什么是编译程序?它的功能是什么?2.一个编译程序由哪几个阶段构成?