第1章编译原理精选PPT.ppt

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

1、第1章编译原理第1页，此课件共39页哦2Topics lOverviewofcompilers编译概述lLexicalanalysis(Scanning)词法分析lSyntacticanalysis(Parsing)语法分析lContext-sensitiveanalysis语义分析lTypechecking类型检查lRuntimeenvironments运行环境lSymboltables符号表lIntermediaterepresentations中间表示lIntermediatecodegeneration中间代码生成lCodeoptimization代码优化l代码生成第2页，此课件共39

2、页哦331.1编译程序l编译器是什么?翻译一种语言（源语言）的程序成为等价的另一种语言（目标语言）的程序，并能报告源语言中错误的一种程序。Target Program目目标程序标程序编译器编译器Source program 源程序源程序Error messages出错信息出错信息Diverse&Varied第3页，此课件共39页哦4程序设计语言l程序设计语言：程序设计语言：用来编写计算机程序的语言。程序设程序设程序设程序设计语言计语言计语言计语言 高级语言高级语言低级语言：面向机器的语言低级语言：面向机器的语言过程式语言过程式语言 Fortran,Pascal,CFortran,Pascal,

3、C函数式语言函数式语言函数式语言函数式语言 Lisp逻辑式语言逻辑式语言逻辑式语言逻辑式语言 PrologProlog对象式语言对象式语言对象式语言对象式语言 C+汇编语言机器语言第4页，此课件共39页哦55l什么是解释程序?读入一个可执行的程序并产生执行该程序的结果的一种程序。编译和解释的例子编译和解释的例子lCistypicallycompiledlSchemeistypicallyinterpretedlJavaiscompiledtobytecodes,whicharetheninterpreted 解释程序第5页，此课件共39页哦6 6l编译器的结构Single Pass单遍单遍Mu

4、ltiple Pass多遍多遍Load&Go装入并执行装入并执行Debugging排错排错Optimizing优化优化Construction构造构造Functional功能功能第6页，此课件共39页哦7 7编译程序的分析与综合l编译程序的工作分为两个基本部分:Analysis:分析分析词法、语法、语义分析词法、语法、语义分析把源程序转换成中间表示把源程序转换成中间表示Synthesis:综合综合从中间表示生成目标程序从中间表示生成目标程序第7页，此课件共39页哦88编译技术的应用编译技术的应用l编译并不限于程序设计语言的应用TextFormatters正文格式化程序lLATEX&TROFFA

5、reLanguagesWhoseCommandsFormatTextSiliconCompilers硅片编译程序lTextual/Graphical:TakeInputandGenerateCircuitDesignDatabaseQueryProcessors数据库查询处理程序DatabaseQueryLanguagesAreAlsoaProgrammingLanguagelInputiscompiledIntoaSetofOperationsforAccessingtheDatabase第8页，此课件共39页哦9编译程序的环境l为了建立一个可执行的程序，除了编译程序本身之外还需要其他一些程

6、序，它们构成编译程序正常工作的环境，如下图所示。第9页，此课件共39页哦1010Source ProgramPre-Processor1Compiler2Assembler3RelocatableMachine Code4Loader Link/Editor5ExecutableLibrary,relocatable object files第10页，此课件共39页哦111.2 源程序的分析l源程序的分析过程由如下过程组成：词法分析（线性分析过程）从左到右扫描构成源程序的字符流，并分组成有独立含义的token或单词语法分析（分层结构分析过程）将token或单词组合成一种嵌套的层次结构语义分析执

7、行各种检查以确保程序的各部分有意义。第11页，此课件共39页哦1212 编译器的结构框图编译器的结构框图 源程序源程序词法分析词法分析1语法分析语法分析2语义分析语义分析3中间代码生成中间代码生成4代码优化代码优化5目标代码生成目标代码生成6 目标程序目标程序符号表管理符号表管理出错处理出错处理1,2,3:分析阶段分析阶段4,5,6:综合阶段综合阶段第12页，此课件共39页哦1313Phase 1.词法分析词法分析字符流转变为单词流字符流转变为单词流For Example:字符流字符流 All are tokens空格空格,换行符等换行符等.被过滤被过滤Position :=initial +

8、rate *60;_第13页，此课件共39页哦1414Phase 2.语法分析关于上页例子的分析树关于上页例子的分析树（Parse Tree）:identifieridentifierexpressionidentifierexpressionnumberexpressionexpressionexpressionassignment statementposition:=+*60initialrate树的结点是利用该语言的树的结点是利用该语言的文法文法来建造的来建造的第14页，此课件共39页哦1515l文法是规则的集合，它们支配了Tokens中的相互依赖和结构statement是是assig

9、nment statement,or while statement,or if statement,or.assignment statementexpressionis anis anidentifier:=expression;(expression),or expression+expression,or expression*expression,or number,or identifier,or.第15页，此课件共39页哦1616l词法分析线性的非递归的仅识别各个“单词”，它们是该语言的Tokensl语法分析-为了识别表达式的构造需要递归，正如在分析树中所见的一般是递归的l语义分

10、析决定该句子是否有且仅有一种无二义的解释第16页，此课件共39页哦1717Phase 3.语义分析l找复杂的语义错误和支持代码生成l分析树根据语义动作进行扩展positioninitialrate:=+*60Compressed Treepositioninitialrate:=+*inttoreal60Conversion Action第17页，此课件共39页哦1818l类型检查:TypeChecking类型检查-LegalityofOperandslManyDifferentSituations:Real:=int+char;Aint:=Areal+int;while char int d

11、o.Etc.第18页，此课件共39页哦191.3编译程序的阶段l整个编译过程从逻辑上来说可以划分为各自独立的若干阶段，一个阶段的输出成为下一个阶段的输入。l形式上构成管道和滤波器结构。l但在实现时，为了提高编译效率通常采用语法制导的方法。整个编译过程以语法分析为中心，整合词法分析、语义分析和中间代码生成成为一个高效、有机连接的整体。第19页，此课件共39页哦2020程序分析中提供的支持程序分析中提供的支持lSymbolTableCreation/Maintenance符号表建立/维护ContainsInfo(storage,type,scope,args)onEach“Meaningful”T

12、oken,TypicallyIdentifiersDataStructureCreated/InitializedDuringLexicalAnalysisUtilized/UpdatedDuringLaterAnalysis&SynthesislErrorHandling出错处理DetectionofDifferentErrorsWhichCorrespondtoAllPhasesWhatKindsofErrorsAreFoundDuringtheAnalysisPhase?WhatHappensWhenanErrorIsFound?第20页，此课件共39页哦21符号表管理l记录源程序中使用

13、的名字l收集每个名字的各种属性信息类型、作用域、分配存储信息名名 字字 种种 类类类类 型型层层 次次偏移量偏移量m过程0a变量real1db变量real1d+4c变量real1d+8第21页，此课件共39页哦22符号表(symbol table)l符号表是一个数据结构，它使得标识符与相关的属性结合在一起。l标识符的类型信息是在程序声明中被获取的.第22页，此课件共39页哦23出错处理l编译程序在各个阶段应诊断和报告源程序中的错误，包括词法错误，语法错误，语义错误。l编译程序应报告出错地点，并给出简明准确的提示信息。第23页，此课件共39页哦24出错处理(error handling)(err

14、or reporting and error recovery)lThecompilershouldreportthelocationofeacherror,togetherwithsomeexplanation.Themajorcategoriesofcompile-timeerror:syntaxerror,scopeerror,typeerror.lAfterdetectingandreportinganerror,thecompilershouldattempterrorrecovery,meansthatthecompilershouldtrytogetitselfintoastat

15、ewhereanalysisofthesourceprogramcancontinueasnormallyaspossible.第24页，此课件共39页哦2525l三个阶段:Linear/Lexical Analysis线性线性/词法分析词法分析:l从左到右扫描识别Tokens（或单词）token:有独立意义的字符串Hierarchical Analysis分层分析分层分析:l把Tokens组成有意义的结构（句子）Semantic Analysis语义分析语义分析:l对构件进行检查保证构件的正确性（有意义）编译器的分析编译器的分析第25页，此课件共39页哦2626编译器的综合编译器的综合lIn

16、termediateCodeGeneration中间代码生成代码的抽象机版本-独立于体系结构EasytoProduceandDoFinal,MachineDependentCodeGenerationlCodeOptimization代码优化FindMoreEfficientWaystoExecuteCodeReplaceCodeWithMoreOptimalStatements2-approaches:High-levelLanguage&“Peephole”OptimizationlFinalCodeGeneration目标代码生成GenerateRelocatableMachineDep

17、endentCode第26页，此课件共39页哦2727Reviewing the Entire ProcessErrorsposition :=initial +rate*60lexical analyzersyntax analyzersemantic analyzerintermediate code generatorid1 :=id2 +id3*60:=id1id2id3+*60:=id1id2id3+*inttoreal60Symbol Tableposition.initial.rate.第27页，此课件共39页哦2828Reviewing the Entire ProcessEr

18、rorsintermediate code generatorcode optimizerfinal code generatortemp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3temp1:=id3*60.0id1:=id2+temp1MOVF id3,R2MULF#60.0,R2MOVF id2,R1ADDF R1,R2MOVF R1,id1position.initial.rate.Symbol Table3 address code第28页，此课件共39页哦29291.4 Compiler Cousins:Pre

19、processors Provide Input to Compilers1.Macro Processing宏处理宏处理#define in C:does text substitution before compiling#define X 3#define Y A*B+C#define Z getchar()第29页，此课件共39页哦30302.File Inclusion#include in C-bring in another file before compilingdefs.h/main.c#include“defs.h”-/-第30页，此课件共39页哦31313.Ration

20、al PreprocessorslAugment“Old”LanguagesWithModernConstructslAddMacrosforIf-Then,While,Etc.l#DefineCanMakeCCodeMorePascal-like#define begin#define end#define then第31页，此课件共39页哦32324.Language Extensions for a Database SystemEQUEL-Database query language embedded in C#Retrieve(DN=Department.Dnum)where#De

21、partment.Dname=Researchis Preprocessed into:ingres_system(“Retr.Research”,_,_);a procedure call in a programming language.第32页，此课件共39页哦3333汇编lAssemblycode:namesareusedforinstructions,andnamesareusedformemoryaddresses.lTwo-passAssembly:FirstPass:allidentifiersareassignedtomemoryaddresses(0-offset)e.g

22、.substitute0fora,and4forbSecondPass:producerelocatablemachinecode:MOV a,R1ADD#2,R1MOV R1,b0001 01 00 00000000*0011 01 10 000000100010 01 00 00000100*第33页，此课件共39页哦3434Loaders and Link-Editorsl装入程序Loader:使可重定位的（relocatable）机器代码改变其地址并把改变的指令放入内存。l连接编辑程序Link-editor:使多个可重定位机器码程序（带有交叉引用）产生单个程序。Needtokeeptr

23、ackofcorrespondencebetweenvariablenamesandcorrespondingaddressesineachpieceofcode.第34页，此课件共39页哦35351.5 The Grouping of PhasesFront End 前端前端 :分析（词法、语法、语义）分析（词法、语法、语义）+中间中间代码生成代码生成Back End后端后端 :代码生成代码生成+优化优化vs.遍（遍（Passes）数）数:A pass:指需要读指需要读/写中间代码文件一次写中间代码文件一次越少遍数越少遍数:越高的效率越高的效率.但是但是:越少遍数需要更成熟的存储管理和编译程

24、越少遍数需要更成熟的存储管理和编译程序各个阶段之间的相互作用。序各个阶段之间的相互作用。因此，需要综合考虑因此，需要综合考虑.第35页，此课件共39页哦36361.6 Compiler Construction Tools 语法分析程序的生成程序（语法分析程序的生成程序（Parser Generators）:产生语法分析程序产生语法分析程序扫描程序的生成程序（扫描程序的生成程序（Scanner Generators）:产生产生词法分析程序词法分析程序语法指导的翻译引擎（语法指导的翻译引擎（Syntax-directed Translation Engines）:生成中间代码生成中间代码自动代码

25、生成程序（自动代码生成程序（Automatic Code Generators）:生成实际代码生成实际代码数据流引擎（数据流引擎（Data-Flow Engines）:支持优化支持优化第36页，此课件共39页哦3737本章要点l翻译程序、编译程序、解释程序翻译程序：把一种语言的程序（称为源程序）转换成与之等价的另一种语言的程序（称为目标程序）的程序。编译程序：把一种语言（通常是高级语言）的程序（称为源程序）转换成与之等价的另一种语言（通常是低级语言）的程序（称为目标程序）的程序。解释程序：把一种语言的程序连同数据作为输入直接产生结果作为输出的程序。l编译的两个阶段分析阶段：词法分析,语法分析,

26、语义分析综合阶段：中间代码生成,代码优化,代码生成l编译的遍指需要读写中间文件一次第37页，此课件共39页哦38l编译的前端和后端前端：分析（词法、语法、语义）分析（词法、语法、语义）+中间代码生成中间代码生成后端：代码生成代码生成+优化优化l语法树和分析树的区别：分析树(parsingtree)：说明输入的语法结构，其中内节点是文法的非终结符，叶子节点是文法的终结符。语法树(syntaxtree)：则是该语法结构更一般的内部表示，可以说语法树是分析树的一种紧缩表示，其中内节点是运算符，运算符的运算对象是该节点的儿子38第38页，此课件共39页哦3939本章术语编译程序,源程序,目标程序,分析阶段,词法分析,语法分析,语义分析,综合阶段,中间代码生成,代码优化,代码生成编译程序的阶段,符号表管理,出错处理,预处理程序,汇编程序,两遍汇编,装入和连接-编辑程序,编译的前端和后端,编译的遍,编译程序的构造工具第39页，此课件共39页哦