1-为什么要学习编译原理

2020年5月18日编译原理高级语言汇编语言SOURCEPROGRAMAssemblePROGRAM？翻译程序？TRANSLATER为什么要学习编译原理•程序设计语言是计算机软件专业的重要核心•学习编程的历程：–C语言－－汇编语言－－数据结构2020年5月18日编译原理为什么要学习编译原理•必修主干课程，操作系统和编译系统构成程序设计者与计算机之间的基本界面。•通过学习该课程，掌握编译的基本理论、常用的编译技术，了解编译过程及编译系统结构和机理。能运用所学技术解决实际问题，能独立编写一个小型编译系统。•此外，通过学习编译原理可以更好地理解程序语言的内部机制,从而更好地理解和运用程序设计语言。能运用编译程序构造的原理和技术完成相关软件工具的设计和开发工作。2020年5月18日编译原理为什么要学习编译原理•计算机软件学科理论与实践相结合的典范。•在学习过程中既要注重该领域在理论上取得的完美结论，也要注重这些理论在实际中的应用。2020年5月18日编译原理先修课程•要求先学习以下课程1.程序设计语言2.算法与数据结构：栈分配、堆分配、静态分配等各种存储分配方式。线性表、二叉查找树、哈希表等多种数据结构。3.离散数学：集合论与数理逻辑是进一步学习形式语言与自动机理论的数学基础。•最好学习过或同时学习以下课程1.软件工程：掌握大型程序设计以及工程化的软件生产方法。2.形式语言与自动机：相当于本课程中词法分析与语法分析的理论基础。2020年5月18日编译原理•胡元义，邓亚玲，《编译原理教程》，西安电子科技大学出版社教材参考书•李建中译，《编译原理》（龙书），机械工业出版社•陈火旺刘春林等，《程序设计语言编译原理》，国防工业出版社•吕映芝，张素琴等，《编译原理》，清华大学出版社•李冬梅，施海虎，《编译原理》，人民邮电出版社2020年5月18日编译原理要求及学习方法•平时（30%）•无故旷课：－5•一本教材，认真听课：以讲义为主，板书为辅---做适当的笔记•认真完成课堂和课后作业•完成要求的课外实验内容•期末（70%）:闭卷笔试课程特点：理论性强，算法复杂2020年5月18日编译原理第1章编译概述1.掌握编译程序中所涉及的有关名词术语2.理解编译程序总的框架，明确编译程序工作的基本过程及各阶段的基本任务教学目标2020年5月18日编译原理1.1.程序的翻译1.2.编译程序的组成1.3.编译程序构造1.4.编译技术的应用及发展教学内容2020年5月18日编译原理•低级语言（LowlevelLanguage)–字位码、机器语言、汇编语言–特点：与特定的机器有关，功效高，但使用复杂、繁琐、费时、易出错•高级语言--Fortran、Pascal、C语言等–特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。1.1程序的翻译2020年5月18日编译原理•源程序用汇编语言或高级语言编写的程序称为源程序•目标程序用目标语言所表示的程序目标语言：可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言。•翻译程序将源程序转换为目标程序的程序称为翻译程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。2020年5月18日编译原理源程序、翻译程序、目标程序三者关系：源程序翻译程序目标程序SOURCEPROGRAMTRANSLATEROBJECTPROGRAM即源程序是翻译程序的输入，目标程序是翻译程序的输出SOI2020年5月18日编译原理•汇编程序若源程序用汇编语言书写，经过翻译程序得到用机器语言表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过程称为“汇编”(Assemble）•编译程序若源程序是用高级语言书写，经加工后得到目标程序，上述翻译过程称“编译”（Compile)汇编程序与编译程序都是翻译程序，主要区别是加工对象的不同。由于汇编语言格式简单，常与机器语言之间有一一对应的关系。汇编程序所要做的翻译工作比编译程序简单的多。2020年5月18日编译原理源程序的编译和运行•编译或汇编阶段•运行阶段源程序目标程序编译程序或汇编程序输出数据目标程序+运行子程序输入数据2020年5月18日编译原理•工作过程解释程序（Interpreter）类似于口译,不生成目标代码对源程序进行解释执行的程序。输出数据解释程序输入数据源程序•特点：与编译系统比较，解释系统较简单、可移植性好，易于查错，但速度慢2020年5月18日编译原理“编译-解释执行”系统源程序编译程序源程序的中间形式输出数据解释程序输入数据2020年5月18日编译原理.javajava源程序文件.class二进制字节码文件Java虚拟机（JVM)本地计算机系统编译例如Java语言2020年5月18日编译原理所谓编译过程是指将高级语言程序翻译为等价的目标程序的过程。翻译外文资料：1、能识别出句子中的一个单词；2、分析句子的语法结构；3、根据句子的含义进行初步翻译；4、对译文进行修饰；5、写出最后的译文。1.2编译程序的组成2020年5月18日编译原理•翻译和编译工作的比较翻译外文编译程序分析识别单词分析句子根据语义进行初步翻译词法分析语法分析语义分析、生成中间代码综合修辞加工写出译文代码优化目标代码生成编译过程2020年5月18日编译原理词法分析语法分析语义分析及中间代码生成代码优化目标代码生成习惯上是将编译过程划分为5个基本阶段：编译过程2020年5月18日编译原理单词：是语言的基本语法单位1保留字（如:if、else、while）2标识符（如:max、min、str）3常数（如:12、6.8、’a’）4分界符（如:+、-、*、/、;、（、））字符序列任务：根据词法规则分析和识别单词一、词法分析编码形式2020年5月18日编译原理词法分析程序的结果-----二元式y=x+r*6单词值单词类别y标识符=分界符（赋值）x标识符+分界符（加号）r标识符*分界符（乘号）6常数2020年5月18日编译原理有关术语•词法分析(lexicalanalysisorscanning)--Thestreamofcharactersmakingupasourceprogramisreadfromlefttorightandgroupedintotokens,whicharesequencesofcharactersthathaveacollectivemeaning.•单词---token•保留字---reservedword•标识符---identifier(user-definedname)2020年5月18日编译原理任务：根据语法规则（即语言的文法），分析并识别出各种语法成分（如表达式、语句、函数等），并进行语法正确性检查。二、语法分析（编译程序的核心）文法赋值语句::=标识符“=”表达式表达式::=表达式“+”表达式|表达式“*”表达式表达式::=“(”表达式“)”|标识符|整数|实数2020年5月18日编译原理赋值语句标识符标识符整数标识符表达式=yx表达式表达式+r6表达式表达式*赋值语句::=标识符“=”表达式表达式::=表达式“+”表达式|表达式“*”表达式表达式::=“(”表达式“)”|标识符|整数|实数y=x+r*62020年5月18日编译原理赋值语句标识符表达式表达式表达式表达式标识符整数标识符表达式y=x+r*6语法分析的结果-----语法树2020年5月18日编译原理有关术语•语法分析(syntaxanalysisorparsing)Thepurposeofsyntaxanalysisistodeterminethesourceprogram’sphrasestructure.Thisprocessisalsocalledparsing.Thesourceprogramisparsedtocheckwhetheritconformstothesourcelanguage’ssyntax,andtoconstructasuitablerepresentationofitsphrasestructure.2020年5月18日编译原理任务：依据语义规则对识别出的各种语法成分析其含义，并进行初步翻译，生成中间代码。三、语义分析及中间代码生成•静态：分析语法成份的含义，进行语义上的正确性检查•动态：根据相应语义，生成中间代码（介于源语言和目标语言之间的中间语言形式）2020年5月18日编译原理生成中间代码的目的：•1、利于代码优化•2、利于目标代码的移植中间代码的形式：•四元式、三元式、逆波兰表示2020年5月18日编译原理四元式其中t1、t2、t3为编译程序引入的临时工作单元例：y=x+r*6运算符左运算对象右运算对象结果(1)inttoreal6--t1(2)*rt1t2(3)+t2xt3(4)=t3y2020年5月18日编译原理有关术语•语义分析(semanticanalysis)Theparsedprogramisfurtheranalyzedtodeterminewhetheritconformstothesourcelanguage’scontextualconstraints:scoperules,typerulese.g.Torelateeachappliedoccurrenceofanidentifierinthesourceprogramtothecorrespondingdeclaration.2020年5月18日编译原理有关术语•中间代码生成(intermediatecodegeneration)Thisiswheretheintermediaterepresentationofthesourceprogramiscreated.Wewantthisrepresentationtobeeasytogenerate,andeasytotranslateintothetargetprogram.Therepresentationcanhaveavarietyofforms,butacommononeiscalledthree-addresscodeor4-tuplecode.2020年5月18日编译原理任务：对中间代码进行加工变换，以得到高质量的目标代码四、代码优化运算符左运算对象右运算对象结果(1)Inttoreal6--t1(2)*rt1t2(3)+t2xt3(4)=t3y运算符左运算对象右运算对象结果(1)*r6.0t1(2)+t1xy(1)inttoreal6--t1(4)=t3y例：y=x+r*62020年5月18日编译原理有关术语•代码优化(Intermediatecodeoptimization)Theoptimizeracceptsinputintheintermediaterepresentationandoutputaversionstillintheintermediaterepresentation.Inthisphase,thecompilerattemptstoproducethesmallest,fastestandmostefficientrunningresultbyapplyingvarioustechniques.2020年5月18日编译原理五、目标代码生成任务：把中间代码变换成特定机器上的低级语言代码movr,R1mul#6.0,R1movx,R2addR1,R2movR2,y运算符左运算对象右运算对象结果(1)*r6.0t1(2)+t1xy2020年5月18日编译原理目标代码生成程序代码优化程序语义分析生成中间代码语法分析程序词法分析程序编译过程小结S.PO.P2020年5月18日编译原理按逻辑功能不同，可将编译过程划分为五个基本阶段，与此相对应，我们将实现整个编译过程的编译程序划分为五个逻辑阶段（即五