第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

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

3、CFortran,Pascal,C函数式语言函数式语言函数式语言函数式语言 LispLisp逻辑式语言逻辑式语言逻辑式语言逻辑式语言 PrologProlog对象式语言对象式语言对象式语言对象式语言 C+C+汇编语言机器语言现在学习的是第4页，共39页5 5l什么是解释程序?读入一个可执行的程序并产生执行该程序的结果的一种程序。编译和解释的例子编译和解释的例子lCistypicallycompiledlSchemeistypicallyinterpretedlJavaiscompiledtobytecodes,whicharetheninterpreted 解释程序现在学习的是第5页，共39页

4、66l编译器的结构Single Pass单遍单遍Multiple Pass多遍多遍Load&Go装入并执行装入并执行Debugging排错排错Optimizing优化优化Construction构造构造Functional功能功能现在学习的是第6页，共39页77编译程序的分析与综合l编译程序的工作分为两个基本部分:Analysis:分析分析词法、语法、语义分析词法、语法、语义分析把源程序转换成中间表示把源程序转换成中间表示Synthesis:综合综合从中间表示生成目标程序从中间表示生成目标程序现在学习的是第7页，共39页8 8编译技术的应用编译技术的应用l编译并不限于程序设计语言的应用Text

5、Formatters正文格式化程序lLATEX&TROFFAreLanguagesWhoseCommandsFormatTextSiliconCompilers硅片编译程序lTextual/Graphical:TakeInputandGenerateCircuitDesignDatabaseQueryProcessors数据库查询处理程序DatabaseQueryLanguagesAreAlsoaProgrammingLanguagelInputiscompiledIntoaSetofOperationsforAccessingtheDatabase现在学习的是第8页，共39页9编译程序的环境

6、l为了建立一个可执行的程序，除了编译程序本身之外还需要其他一些程序，它们构成编译程序正常工作的环境，如下图所示。现在学习的是第9页，共39页1010Source ProgramPre-Processor1Compiler2Assembler3RelocatableMachine Code4Loader Link/Editor5ExecutableLibrary,relocatable object files现在学习的是第10页，共39页111.2 源程序的分析l源程序的分析过程由如下过程组成：词法分析（线性分析过程）从左到右扫描构成源程序的字符流，并分组成有独立含义的token或单词语法分析

7、（分层结构分析过程）将token或单词组合成一种嵌套的层次结构语义分析执行各种检查以确保程序的各部分有意义。现在学习的是第11页，共39页1212 编译器的结构框图编译器的结构框图 源程序源程序词法分析词法分析1语法分析语法分析2语义分析语义分析3中间代码生成中间代码生成4代码优化代码优化5目标代码生成目标代码生成6 目标程序目标程序符号表管理符号表管理出错处理出错处理1,2,3:分析阶段分析阶段4,5,6:综合阶段综合阶段现在学习的是第12页，共39页1313Phase 1.词法分析词法分析字符流转变为单词流字符流转变为单词流For Example:字符流字符流 All are tokens

8、空格空格,换行符等换行符等.被过滤被过滤Position :=initial +rate *60;_现在学习的是第13页，共39页1414Phase 2.语法分析关于上页例子的分析树关于上页例子的分析树（Parse Tree）:identifieridentifierexpressionidentifierexpressionnumberexpressionexpressionexpressionassignment statementposition:=+*60initialrate树的结点是利用该语言的树的结点是利用该语言的文法文法来建造的来建造的现在学习的是第14页，共39页1515l文

9、法是规则的集合，它们支配了Tokens中的相互依赖和结构statement是是assignment 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词法分析线性的非递归的仅识别各个“单词”，它们是该语言的T

10、okensl语法分析-为了识别表达式的构造需要递归，正如在分析树中所见的一般是递归的l语义分析决定该句子是否有且仅有一种无二义的解释现在学习的是第16页，共39页1717Phase 3.语义分析l找复杂的语义错误和支持代码生成l分析树根据语义动作进行扩展positioninitialrate:=+*60Compressed Treepositioninitialrate:=+*inttoreal60Conversion Action现在学习的是第17页，共39页1818l类型检查:TypeChecking类型检查-LegalityofOperandslManyDifferentSituatio

11、ns:Real:=int+char;Aint:=Areal+int;while char int do.Etc.现在学习的是第18页，共39页191.3编译程序的阶段l整个编译过程从逻辑上来说可以划分为各自独立的若干阶段，一个阶段的输出成为下一个阶段的输入。l形式上构成管道和滤波器结构。l但在实现时，为了提高编译效率通常采用语法制导的方法。整个编译过程以语法分析为中心，整合词法分析、语义分析和中间代码生成成为一个高效、有机连接的整体。现在学习的是第19页，共39页2020程序分析中提供的支持程序分析中提供的支持lSymbolTableCreation/Maintenance符号表建立/维护Co

12、ntainsInfo(storage,type,scope,args)onEach“Meaningful”Token,TypicallyIdentifiersDataStructureCreated/InitializedDuringLexicalAnalysisUtilized/UpdatedDuringLaterAnalysis&SynthesislErrorHandling出错处理DetectionofDifferentErrorsWhichCorrespondtoAllPhasesWhatKindsofErrorsAreFoundDuringtheAnalysisPhase?WhatH

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

14、应报告出错地点，并给出简明准确的提示信息。现在学习的是第23页，共39页24出错处理(error handling)(error reporting and error recovery)lThecompilershouldreportthelocationofeacherror,togetherwithsomeexplanation.Themajorcategoriesofcompile-timeerror:syntaxerror,scopeerror,typeerror.lAfterdetectingandreportinganerror,thecompilershouldattempte

15、rrorrecovery,meansthatthecompilershouldtrytogetitselfintoastatewhereanalysisofthesourceprogramcancontinueasnormallyaspossible.现在学习的是第24页，共39页2525l三个阶段:Linear/Lexical Analysis线性线性/词法分析词法分析:l从左到右扫描识别Tokens（或单词）token:有独立意义的字符串Hierarchical Analysis分层分析分层分析:l把Tokens组成有意义的结构（句子）Semantic Analysis语义分析语义分析:l

16、对构件进行检查保证构件的正确性（有意义）编译器的分析编译器的分析现在学习的是第25页，共39页2626编译器的综合编译器的综合lIntermediateCodeGeneration中间代码生成代码的抽象机版本-独立于体系结构EasytoProduceandDoFinal,MachineDependentCodeGenerationlCodeOptimization代码优化FindMoreEfficientWaystoExecuteCodeReplaceCodeWithMoreOptimalStatements2-approaches:High-levelLanguage&“Peephole”O

17、ptimizationlFinalCodeGeneration目标代码生成GenerateRelocatableMachineDependentCode现在学习的是第26页，共39页2727Reviewing the Entire ProcessErrorsposition :=initial +rate*60lexical analyzersyntax analyzersemantic analyzerintermediate code generatorid1 :=id2 +id3*60:=id1id2id3+*60:=id1id2id3+*inttoreal60Symbol Tablep

18、osition.initial.rate.现在学习的是第27页，共39页2828Reviewing the Entire ProcessErrorsintermediate 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.ra

19、te.Symbol Table3 address code现在学习的是第28页，共39页29291.4 Compiler Cousins:Preprocessors 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

20、 before compilingdefs.h/main.c#include“defs.h”-/-现在学习的是第30页，共39页31313.Rational PreprocessorslAugment“Old”LanguagesWithModernConstructslAddMacrosforIf-Then,While,Etc.l#DefineCanMakeCCodeMorePascal-like#define begin#define end#define then现在学习的是第31页，共39页32324.Language Extensions for a Database SystemEQ

21、UEL-Database query language embedded in C#Retrieve(DN=Department.Dnum)where#Department.Dname=Researchis Preprocessed into:ingres_system(“Retr.Research”,_,_);a procedure call in a programming language.现在学习的是第32页，共39页3333汇编lAssemblycode:namesareusedforinstructions,andnamesareusedformemoryaddresses.lTw

22、o-passAssembly:FirstPass:allidentifiersareassignedtomemoryaddresses(0-offset)e.g.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:使可重定位的（relocatab

23、le）机器代码改变其地址并把改变的指令放入内存。l连接编辑程序Link-editor:使多个可重定位机器码程序（带有交叉引用）产生单个程序。Needtokeeptrackofcorrespondencebetweenvariablenamesandcorrespondingaddressesineachpieceofcode.现在学习的是第34页，共39页35351.5 The Grouping of PhasesFront End 前端前端 :分析（词法、语法、语义）分析（词法、语法、语义）+中间中间代码生成代码生成Back End后端后端 :代码生成代码生成+优化优化vs.遍（遍（Pass

24、es）数）数:A pass:指需要读指需要读/写中间代码文件一次写中间代码文件一次越少遍数越少遍数:越高的效率越高的效率.但是但是:越少遍数需要更成熟的存储管理和编译程序越少遍数需要更成熟的存储管理和编译程序各个阶段之间的相互作用。各个阶段之间的相互作用。因此，需要综合考虑因此，需要综合考虑.现在学习的是第35页，共39页36361.6 Compiler Construction Tools 语法分析程序的生成程序（语法分析程序的生成程序（Parser Generators）:产生语法分析程序产生语法分析程序扫描程序的生成程序（扫描程序的生成程序（Scanner Generators）:产产生

25、词法分析程序生词法分析程序语法指导的翻译引擎（语法指导的翻译引擎（Syntax-directed Translation Engines）:生成中间代码生成中间代码自动代码生成程序（自动代码生成程序（Automatic Code Generators）:生成实际代码生成实际代码数据流引擎（数据流引擎（Data-Flow Engines）:支持优化支持优化现在学习的是第36页，共39页3737本章要点l翻译程序、编译程序、解释程序翻译程序：把一种语言的程序（称为源程序）转换成与之等价的另一种语言的程序（称为目标程序）的程序。编译程序：把一种语言（通常是高级语言）的程序（称为源程序）转换成与之等价

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