编译原理 第一章课件

编译原理

Compilers:Principles,Techniques,andTools11/22/20232023/11/221编译原理第一章课程介绍programmingPrincipleofcompilerconstructionFoundationofprogramminglanguage2023/11/222编译原理第一章课程介绍学习设计与构造程序设计语言编译程序的原理与方法源程序编译程序目标程序连接可执行程序2023/11/223编译原理第一章为什么学习编译原理？编译程序构造是计算机科学中一个非常成功、成熟的分支，也是最早获得成功的分支之一；它与文件转换程序关系密切，不仅仅是于编译程序；包含许多在实际应用中有用的算法。2023/11/224编译原理第一章课程内容编译器构造的一般原理和基本实现方法强调对编译原理和技术的宏观理解不偏向于某种源语言或目标机器理论知识形式语言和自动机理论属性文法类型理论等形式化描述技术预备知识高级程序设计语言数据结构、汇编、离散数学2023/11/225编译原理第一章内容简介第一章编译器的基本结构第二章简单的语法制导翻译器第三章词法分析第四章语法分析第五章语法制导翻译第六章中间代码生成第七章运行时刻环境第八章代码生成重点2023/11/226编译原理第一章教材计算机科学丛书•编译原理(本科教学版)(第2版)

阿霍(Aho.A.V.)

等

赵建华

,

郑滔,

戴新宇

(译)

2023/11/227编译原理第一章第1版第2版中译本2023/11/228编译原理第一章课程要求课堂课后习题实验阅读、查找相关资料编程完成实验提交实验报告成绩平时成绩：考勤、作业、实验期末考试2023/11/229编译原理第一章第一章绪论

1.1什么是编译程序C70600000002machinelanguagemovX,2AssemblylanguageX=2Clanguage程序设计语言高级语言汇编语言机器语言在计算机上如何执行一个高级语言程序？把高级语言程序翻译成机器语言程序运行所得的机器语言程序求得计算结果2023/11/2210编译原理第一章Compiler:ABridgeBetweenPLandHardwareOperatingSystemHardware(LowLevelLanguage)CompilerApplications(HighLevelLanguage)a=b+c*dMOVA,dMULA,dADDA,bMOVva,AAssemblyCodesRegister-basedorStack-basedmachines2023/11/2211编译原理第一章compiler编译器是一个程序，读入某一语言写的源程序，并将其翻译成等价的、用另一语言写的目标程序，并且能够向用户报告被编译的源程序中出现的错误。CompilerSourceprogramTargetprogramErrormessage2023/11/2212编译原理第一章程序的等价：若两个程序P1和P2所允许的输入集合相同，且对相同的输入，均产生相同的输出，则称程序P1和P2等价。狭义看法：通常，源程序是用某种高级语言编写的，而目标程序是用目标代码或机器代码编写的。广义看法：程序变换，翻译器(translator) C++

C;Pascal

C；2023/11/2213编译原理第一章Compiler-CompilationCompilerSourceProgram/Code(C,Pascaletc.)TargetProgram/Code(Assembly,MachineCode)ErrorMessagea=b+c*dT1:=c*dT2:=b+T1a:=T2MOVA,cMULA,dADDA,bMOVva,A2023/11/2214编译原理第一章翻译器translator翻译：在不改变语义的条件下，把某种语言的源程序转换成另一种语言程序—目标语言程序，称为翻译。执行翻译的软件，称为翻译程序。

源程序翻译程序目标程序2023/11/2215编译原理第一章解释和编译解释器(interpreter)在一种语言的机器上，直接执行用另一种语言写的程序的过程，称为解释。实现解释的软件，称为解释程序。以源程序作为输入，不产生目标程序，一边解释一边执行。优点：直观易懂，结构简单，易于实现人机对话缺点：效率低编译由高级语言转换为低级语言,然后对编译出来的目标程序进行运行计算2023/11/2216编译原理第一章翻译程序与解释程序的区别二者本质区别是输出不同：翻译程序的输出是与源程序等价的目标程序；解释程序实际是一台虚拟机，其输出是被执行程序所定义的输出结果。2023/11/2217编译原理第一章Example:JavaCompiler&JavaVMJava语言结合了编译和解释的过程。JavaBytecodesJavaprogram(app.java)(Javac)(app.class)2023/11/2218编译原理第一章Thecontextofacompiler2023/11/2219编译原理第一章PreprocessorSourceProgramModifiedSourceProgramCompilerTargetAssemblyProgramAssemblerRelocatableMachineCodeTargetMachineCodeLibraryfilesand/orRelocatableobjectfilesLinker/LoaderThecontextof

acompiler2023/11/2220编译原理第一章编译过程概述编译程序的工作，从输入源程序开始，到输出目标程序结束，与自然语言之间的翻译有很多相似之处。英文翻译成中文的步骤：识别出句子中的单词分析句子的语法结构根据句子的含义进行初步分析对译文进行修饰写出最后的译文词法分析代码优化语法分析语义分析及中间代码生成目标代码生成2023/11/2221编译原理第一章1.2编译器结构分析－综合模型（Analysis-SynthesisModel）Twopartsofcompilation:Analysis:DecomposeSourceintoanintermediaterepresentationSynthesis:Targetprogramgenerationfromrepresentation2023/11/2222编译原理第一章编译程序的结构框图词法分析器语法分析器语义分析器源程序中间代码生成器代码优化器代码生成器目标程序出错管理器符号表管理器2023/11/2223编译原理第一章AnalysisofthesourceprogramAnalysisconsistsofthreephases词法分析Lexicalanalysis/Linearanalysis/Scanning语法分析Syntaxanalysis/Hierarchicalanalysis/Parsing语义分析Semanticanalysis2023/11/2224编译原理第一章词法分析(Lexicalanalysis)词法分析程序又称扫描程序。是编译过程的第一个阶段，其任务是：读源程序的字符流、识别单词（如标识符、整数、界限符等），并转换成内部形式。输入：源程序中的字符流输出：词法单元（tokens）

<token-name,attribute-value>2023/11/2225编译原理第一章词法分析举例Pascal赋值语句position:=initial+rate*60wouldbegroupedintothefollowingtokens:Identifierposition <id,1>Assignmentsymbol:= <:=,>Identifierinitial

<id,2>Plussign+ <+,>Identifierrate <id,3>Multiplicationsign* <*,>Number60 <number,60>分隔这些记号的空格被删除。（注释也可以在词法分析中处理。）2023/11/2226编译原理第一章符号表

positioninitialrate.........123词法分析器id1:=id2+id3

*60position:=initial+rate*60lexicalanalyzer

2023/11/2227编译原理第一章词法分析举例一个C源程序片段：inta;a=a+2;词法分析后返回(如右图)：

单词类型

单词值保留字 int标识符 a界符 ;标识符 a算符(赋值)=标识符 a算符(加)+整数 2界符 ;2023/11/2228编译原理第一章语法分析（Syntaxanalysis）语法分析程序又称识别程序(parser)。功能：读入由词法分析程序识别出的符号，根据给定语法规则，识别出各个语法结构（检查语法的正确性）,并生成另一种内部表示。输入：由词法分析程序识别出并转换的tokens输出：内部表示，如语法分析树(syntaxtree)2023/11/2229编译原理第一章assignmentstatementidentifier:=expressionpositionexpressionexpression+expressionexpression*identifiernumberrate60identifierinitialParsetree语法分析2023/11/2230编译原理第一章Syntaxtree

isacompressedrepresentationoftheparsetree.:=position+*rate60initial2023/11/2231编译原理第一章符号表

positioninitialrate.........123语法分析器id1:=id2+id3

*60

:=+*60id1id2id3SyntaxAnalyzer2023/11/2232编译原理第一章语义分析(Semanticanalysis)对语法分析树或其他内部中间表示进行静态语义检查，并生成目标代码或中间代码。确定类型类型检查识别含义与相应的语义处理其它静态语义检查为了优化，往往先生成内部中间表示代码：如逆波兰表示、三元式序列、四元式序列，或者抽象语法树。2023/11/2233编译原理第一章语义分析错在哪里？例1：

intarr[2],c;c=arr1*10;例2：

Programp(input,output);varrate:real;procedureinitial;

…position:=initial+rate*602023/11/2234编译原理第一章Semanticanalysisinsertsaconversionfromintegertoreal.:=position+*rate60initialinttoreal插入语义处理结点的语法树2023/11/2235编译原理第一章符号表

positioninitialrate.........123语义分析器:=+*60id1id2id3:=+*60id1id2id3inttorealSemanticAnalyzer2023/11/2236编译原理第一章符号表

positioninitialrate.........123中间代码生成器temp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3:=+*60id1id2id3inttorealIntermediateCodeGenerator

2023/11/2237编译原理第一章符号表

positioninitialrate.........123代码优化器temp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3temp1:=id3*60.0id1:=id2+temp1CodeOptimizer2023/11/2238编译原理第一章符号表

positioninitialrate.........123temp1:=id3*60.0id1:=id2+temp1代码生成器MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1CodeGenerator

2023/11/2239编译原理第一章2023/11/2240编译原理第一章characterstreamtokenstreamsyntaxtreesyntaxtreeIntermediaterepresentationIntermediaterepresentationtarget-machinecode2023/11/2241编译原理第一章分析将源程序正文转换为内部表示，并收集和确定各结构成分之间的相关信息。

（1）词法分析：将字符序列转换为单词序列。

（2）语法分析：将单词序列重组为程序结构（通常表示为分析树）。

（3）语义分析：确定各语法成分之间的对应关系和一致性，如标识符的作用域、类型匹配等等。2023/11/2242编译原理第一章综合根据源程序的语法结构和语义信息，生成目标代码。中间代码生成：中间语言的形式与汇编语言相近，比较简单，且与具体机器无关，便于代码的优化和移植。代码优化：改善代码的时空效率，如常数表达式求值，公共子表达式优化，循环语句中的不变表达式外提，削减运算强度等等。代码生成：生成等价的汇编或机器语言程序。

2023/11/2243编译原理第一章符号表管理符号表存放与单词有关的信息，如标识符的类型、地址，常数的值等等。符号表的管理包括表的生成、填写、查阅、删除等。2023/11/2244编译原理第一章错误处理单词错语法错语义错（如多重定义、类型不匹配）环境错（如数组太大、名字太长）溢出外设错误（I/O错）访问内存越界编译错误运行错误逻辑错误错误分类2023/11/2245编译原理第一章TheGroupingofPhases编译各阶段的组合相关概念：前端、后端遍(pass)源代码前端中间代码后端目标代码FrontEnd:Analysis+IntermediateCodeGenerationBackEnd:CodeGeneration+Optimizationvs.2023/11/2246编译原理第一章遍(pass)从过程上看，编译是从源程序开始，经过若干