第1章编译原理精选文档.ppt

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

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

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

3、式语言逻辑式语言逻辑式语言逻辑式语言 PrologProlog对象式语言对象式语言 C+汇编语言机器语言本讲稿第四页，共三十九页55l什么是解释程序?读入一个可执行的程序并产生执行该程序的结果的一种程序。编译和解释的例子编译和解释的例子lCistypicallycompiledlSchemeistypicallyinterpretedlJavaiscompiledtobytecodes,whicharetheninterpreted 解释程序本讲稿第五页，共三十九页66l编译器的结构Single Pass单遍单遍Multiple Pass多遍多遍Load&Go装入并执行装入并执行Debuggi

4、ng排错排错Optimizing优化优化Construction构造构造Functional功能功能本讲稿第六页，共三十九页77编译程序的分析与综合l编译程序的工作分为两个基本部分:Analysis:分析分析词法、语法、语义分析词法、语法、语义分析把源程序转换成中间表示把源程序转换成中间表示Synthesis:综合综合从中间表示生成目标程序从中间表示生成目标程序本讲稿第七页，共三十九页88编译技术的应用编译技术的应用l编译并不限于程序设计语言的应用TextFormatters正文格式化程序lLATEX&TROFFAreLanguagesWhoseCommandsFormatTextSilico

5、nCompilers硅片编译程序lTextual/Graphical:TakeInputandGenerateCircuitDesignDatabaseQueryProcessors数据库查询处理程序DatabaseQueryLanguagesAreAlsoaProgrammingLanguagelInputiscompiledIntoaSetofOperationsforAccessingtheDatabase本讲稿第八页，共三十九页9编译程序的环境l为了建立一个可执行的程序，除了编译程序本身之外还需要其他一些程序，它们构成编译程序正常工作的环境，如下图所示。本讲稿第九页，共三十九页1010

6、Source ProgramPre-Processor1Compiler2Assembler3RelocatableMachine Code4Loader Link/Editor5ExecutableLibrary,relocatable object files本讲稿第十页，共三十九页111.2 源程序的分析l源程序的分析过程由如下过程组成：词法分析（线性分析过程）从左到右扫描构成源程序的字符流，并分组成有独立含义的token或单词语法分析（分层结构分析过程）将token或单词组合成一种嵌套的层次结构语义分析执行各种检查以确保程序的各部分有意义。本讲稿第十一页，共三十九页1212 编译器的结

7、构框图编译器的结构框图 源程序源程序词法分析词法分析1语法分析语法分析2语义分析语义分析3中间代码生成中间代码生成4代码优化代码优化5目标代码生成目标代码生成6 目标程序目标程序符号表管理符号表管理出错处理出错处理1,2,3:分析阶段分析阶段4,5,6:综合阶段综合阶段本讲稿第十二页，共三十九页1313Phase 1.词法分析词法分析字符流转变为单词流字符流转变为单词流For Example:字符流字符流 All are tokens空格空格,换行符等换行符等.被过滤被过滤Position :=initial +rate *60;_本讲稿第十三页，共三十九页1414Phase 2.语法分析关于

8、上页例子的分析树关于上页例子的分析树（Parse Tree）:identifieridentifierexpressionidentifierexpressionnumberexpressionexpressionexpressionassignment statementposition:=+*60initialrate树的结点是利用该语言的树的结点是利用该语言的文法文法来建造的来建造的本讲稿第十四页，共三十九页1515l文法是规则的集合，它们支配了Tokens中的相互依赖和结构statement是是assignment statement,or while statement,or if

9、statement,or.assignment statementexpressionis anis anidentifier:=expression;(expression),or expression+expression,or expression*expression,or number,or identifier,or.本讲稿第十五页，共三十九页1616l词法分析线性的非递归的仅识别各个“单词”，它们是该语言的Tokensl语法分析-为了识别表达式的构造需要递归，正如在分析树中所见的一般是递归的l语义分析决定该句子是否有且仅有一种无二义的解释本讲稿第十六页，共三十九页1717Phas

10、e 3.语义分析l找复杂的语义错误和支持代码生成l分析树根据语义动作进行扩展positioninitialrate:=+*60Compressed Treepositioninitialrate:=+*inttoreal60Conversion Action本讲稿第十七页，共三十九页1818l类型检查:TypeChecking类型检查-LegalityofOperandslManyDifferentSituations:Real:=int+char;Aint:=Areal+int;while char int do.Etc.本讲稿第十八页，共三十九页191.3编译程序的阶段l整个编译过程从逻辑

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

12、ated/InitializedDuringLexicalAnalysisUtilized/UpdatedDuringLaterAnalysis&SynthesislErrorHandling出错处理DetectionofDifferentErrorsWhichCorrespondtoAllPhasesWhatKindsofErrorsAreFoundDuringtheAnalysisPhase?WhatHappensWhenanErrorIsFound?本讲稿第二十页，共三十九页21符号表管理l记录源程序中使用的名字l收集每个名字的各种属性信息类型、作用域、分配存储信息名名 字字 种种 类类

13、类类 型型层层 次次偏移量偏移量m过程0a变量real1db变量real1d+4c变量real1d+8本讲稿第二十一页，共三十九页22符号表(symbol table)l符号表是一个数据结构，它使得标识符与相关的属性结合在一起。l标识符的类型信息是在程序声明中被获取的.本讲稿第二十二页，共三十九页23出错处理l编译程序在各个阶段应诊断和报告源程序中的错误，包括词法错误，语法错误，语义错误。l编译程序应报告出错地点，并给出简明准确的提示信息。本讲稿第二十三页，共三十九页24出错处理(error handling)(error reporting and error recovery)lTheco

14、mpilershouldreportthelocationofeacherror,togetherwithsomeexplanation.Themajorcategoriesofcompile-timeerror:syntaxerror,scopeerror,typeerror.lAfterdetectingandreportinganerror,thecompilershouldattempterrorrecovery,meansthatthecompilershouldtrytogetitselfintoastatewhereanalysisofthesourceprogramcancon

15、tinueasnormallyaspossible.本讲稿第二十四页，共三十九页2525l三个阶段:Linear/Lexical Analysis线性线性/词法分析词法分析:l从左到右扫描识别Tokens（或单词）token:有独立意义的字符串Hierarchical Analysis分层分析分层分析:l把Tokens组成有意义的结构（句子）Semantic Analysis语义分析语义分析:l对构件进行检查保证构件的正确性（有意义）编译器的分析编译器的分析本讲稿第二十五页，共三十九页2626编译器的综合编译器的综合lIntermediateCodeGeneration中间代码生成代码的抽象机

16、版本-独立于体系结构EasytoProduceandDoFinal,MachineDependentCodeGenerationlCodeOptimization代码优化FindMoreEfficientWaystoExecuteCodeReplaceCodeWithMoreOptimalStatements2-approaches:High-levelLanguage&“Peephole”OptimizationlFinalCodeGeneration目标代码生成GenerateRelocatableMachineDependentCode本讲稿第二十六页，共三十九页2727Reviewin

17、g the Entire ProcessErrorsposition :=initial +rate*60lexical analyzersyntax analyzersemantic analyzerintermediate code generatorid1 :=id2 +id3*60:=id1id2id3+*60:=id1id2id3+*inttoreal60Symbol Tableposition.initial.rate.本讲稿第二十七页，共三十九页2828Reviewing the Entire ProcessErrorsintermediate code generatorcod

18、e 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本讲稿第二十八页，共三十九页29291.4 Compiler Cousins:Preprocessors Provide Input to Compi

19、lers1.Macro Processing宏处理宏处理#define in C:does text substitution before compiling#define X 3#define Y A*B+C#define Z getchar()本讲稿第二十九页，共三十九页30302.File Inclusion#include in C-bring in another file before compilingdefs.h/main.c#include“defs.h”-/-本讲稿第三十页，共三十九页31313.Rational PreprocessorslAugment“Old”Lan

20、guagesWithModernConstructslAddMacrosforIf-Then,While,Etc.l#DefineCanMakeCCodeMorePascal-like#define begin#define end#define then本讲稿第三十一页，共三十九页32324.Language Extensions for a Database SystemEQUEL-Database query language embedded in C#Retrieve(DN=Department.Dnum)where#Department.Dname=Researchis Prepr

21、ocessed into:ingres_system(“Retr.Research”,_,_);a procedure call in a programming language.本讲稿第三十二页，共三十九页3333汇编lAssemblycode:namesareusedforinstructions,andnamesareusedformemoryaddresses.lTwo-passAssembly:FirstPass:allidentifiersareassignedtomemoryaddresses(0-offset)e.g.substitute0fora,and4forbSecon

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

23、iablenamesandcorrespondingaddressesineachpieceofcode.本讲稿第三十四页，共三十九页35351.5 The Grouping of PhasesFront End 前端前端 :分析（词法、语法、语义）分析（词法、语法、语义）+中中间代码生成间代码生成Back End后端后端 :代码生成代码生成+优化优化vs.遍（遍（Passes）数）数:A pass:指需要读指需要读/写中间代码文件一次写中间代码文件一次越少遍数越少遍数:越高的效率越高的效率.但是但是:越少遍数需要更成熟的存储管理和编译程序越少遍数需要更成熟的存储管理和编译程序各个阶段之间的相

24、互作用。各个阶段之间的相互作用。因此，需要综合考虑因此，需要综合考虑.本讲稿第三十五页，共三十九页36361.6 Compiler Construction Tools 语法分析程序的生成程序（语法分析程序的生成程序（Parser Generators）:产生语法分析程序产生语法分析程序扫描程序的生成程序（扫描程序的生成程序（Scanner Generators）:产产生词法分析程序生词法分析程序语法指导的翻译引擎（语法指导的翻译引擎（Syntax-directed Translation Engines）:生成中间代码生成中间代码自动代码生成程序（自动代码生成程序（Automatic Cod

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

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