编译原理 第1章 概述 - 副本

编译原理参考书编译技术，重庆大学出版社，王力红，霍林编译原理与技术，北京邮电大学出版社，李劲华，丁洁玉编译原理及实现，清华大学出版社，孙悦红关于学习编译原理构造编译程序的前提:掌握源语言掌握目标语言掌握编译方法意义:学习编译程序构造原理，相关技术更好地理解高级语言编译的原理和方法有助于构造一些实用的工具，如词法分析器自动生成器LEX，语法分析器自动生成器YACC；关于学习编译原理课程特点:理解性技术性考核：作业、考勤、上机实验：40%笔试：60%1.介绍了程序设计语言的发展1.机器语言；2.汇编语言；3.高级程序设计语言；第1章编译引论1.1程序设计语言和编译程序2.什么叫编译程序源语言程序目标语言程序翻译程序翻译翻译程序把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序。1.解释程序解释程序是一种将源程序按动态顺序逐句进行分析解释执行，其间并不产生目标程序。解释程序源程序输入数据计算结果编译程序高级语言程序（源程序）低级语言程序（目标程序）2.编译程序如果源语言是诸如FORTRAN、C语言、Java这样的“高级语言”，而目标语言是诸如汇编语言、机器语言之类的“低级语言”，则这样的翻译程序就被称为“编译程序”。其间源程序的编译和目标程序的执行是分成两个阶段完成的（即先产生目标代码再执行之）。编译程序vs解释程序编译解释目标程序1.2编译过程概述把英文翻译为中文识别出句子中的一个个单词；分析句子的语法结构；根据句子的含义进行初步翻译；对译文进行修饰；写出最后的译文。词法分析语法分析中间代码产生优化目标代码产生1.2编译过程编译程序的工作一般分为五个阶段:词法分析语法分析语义分析及中间代码生成代码优化目标代码生成1.词法分析任务:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。依循的原则：构词规则描述工具：正规式、有限自动机FORI:=1TO100DO保留字标识符算符整常数保留字整常数保留字2.语法分析任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。依循的原则：语法规则描述工具：上下文无关文法Z:=X+0.618*Y算术表达式3.语义分析及中间代码产生生成任务:对各类不同语法范畴按语言的语义进行初步翻译。依循的原则：语义规则中间代码:四元式Z:=X+0.618*Y翻译成四元式为：(1)*0.618YT1(2)+XT1T2(3):=T2_Z4.代码优化任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。依循的原则：程序的等价变换规则FORK:=1TO100DOBEGINM:=I+10*K;N:=J+10*K;END5.目标代码生成任务:把中间代码变换成特定机器上的目标代码。依赖于硬件系统结构和机器指令的含义目标代码三种形式:绝对指令代码:可直接运行可重新定位指令代码:需要连接装配汇编指令代码:需要进行汇编例:b=a+2汇编语言代码MOVR1,aADDR1,2MOVb,R1机器代码0001010000000000001101100000001001000100000001001.3.1编译程序的总体结构源程序词法分析器语法分析器语义分析及中间代码生成器代码优化器目标代码生成器目标程序表格处理程序出错处理程序分析综合1.3编译程序的结构1.词法分析：词法分析是编译过程的基础，其任务是扫描源程序，根据语言的词法规则，分解和识别出每个单词符号，并指出它们的属性，把它们组成词法记号流。2.语法分析：语法分析是在词法分析的基础上进行，根据语言的语法规则把词法记号流分解成各类语法短语。3.语义分析：语义分析进一步检查合法程序结构的语义正确性，其目的是保证标识符和常数的正确使用，把必要的信息收集、保存到符号表或中间代码程序中，并进行相应的处理。如：类型检查。4.代码优化：对前面产生的中间代码进行加工变换，以最终产生更加高效的目标代码.5.目标代码生成：这是编译程序的最后阶段。如果编译程序采用了中间代码，那么，目标代码生成阶段的任务则是将优化之后的中间代码转换为等价的目标代码，即机器指令或汇编指令。6.表格管理程序：完成编译过程中的建表、查表、更新数据等有关表格的工作。7.错误处理程序：用来发现编译过程中源程序的错误，准确报告错误种类及错误的位置。所谓“一遍”是指：对源程序或中间程序从头到尾扫描一次，并作相关加工处理，生成新的中间程序或目标代码。1）一遍的编译程序即对源程序进行一遍扫描，就完成编译程序的各项任务。该编译程序的核心是语法反系程序，不必产生中间代码。1、“遍”的概念工作过程如下：①当语法分析器需要读进一个新的单词符号时，就调用词法分析器，词法分析器则从源程序中依次读入字符，并组合成单词符号，把其记号送回语法分析器；②当语法分析器识别出一个语法短语时，就调用语义分析程序进行语义分析，并生成目标程序；③当源程序处理完后，转善后处理，即整理目标程序（如优化等），并停机。词法分析器语法分析器整理目标程序停机语义分析及代码生成取单词返回单词语法成分返回源程序目标代码相关概念2）多遍编译程序即：把编译的5个阶段应完成的工作分遍来做，每一遍完成一个或相连几个阶段的工作。源程序词法分析程序语法分析程序语义分析程序代码优化程序目标代码生成程序目标程序表格处理程序出错处理程序编译程序总控中间语言1，表中间语言2，表中间语言3，表优化代码，表工作过程如下：编译程序的主程序调用词法分析器扫描源程序，并将它转换成一种内部表示，称为中间语言1，同时产生有关的一些表，然后主程序再调用语法分析器，它以中间代码1为输入，进行语法分析，产生中间语言2……最后主程序调用目标代码生成器，把输入的中间代码转换为等价的目标代码。编译程序分遍的优缺点：优点：1.首先可以减少对内存容量的要求，分遍后，在编译时以遍为单位分别调入编译程序，各遍编译程序在内存中可以相互覆盖；2.其次，可使各编译程序功能独立、单纯，相互联系简单，编译程序结构清晰；3.再次，能够实现充分地优化工作，以获得高质量的目标程序；4.最后，通过分遍将编译程序的前端和后端分开，为编译程序的移植创造条件。缺点：增加了不少重复性工作，比如每一遍都有读符号、送符号等工作，这就降低了编译的效率。2、前端和后端前端：包括词法分析、语法分析、语义分析及中间代码生成、部分代码优化，主要依赖于源程序，与目标机无关；后端：包括部分代码优化、目标代码生成，依赖于中间代码、计算机的硬件系统和机器指令系统。这种组织方式便于编译程序的移植，若要将编译程序移植到不同类型的机器只需修改编译程序的后端来完成。改写后端以生成不同目标机上的相同语言的编译程序。1.4编译程序与程序设计环境程序设计环境编辑程序编译程序:它是实现高级语言的一个最重要的工具；连接程序调试工具集成化的程序设计环境它将相互独立的程序设计工具集成起来，以便为程序员提供完整的、一体化的支持，从而进一步提高程序开发效率，改善程序质量。如TurboC,c++等；1.5编译程序的生成1.以汇编语言和机器语言为工具来构造优点:可以针对具体的机器，充分发挥计算机的系统功能。生成的程序效率高。缺点:程序难读、难写、易出错、难维护、生产的效率低。1.5编译程序的生成2.高级语言书写STIS源程序T目标程序I实现语言优点:程序易读、易理解、容易维护、生产的效率高。缺点:难以充分发挥计算机的系统功能，生成的程序效率低。1.5编译程序的生成A.高级语言书写利用已有的某种语言的编译程序实现另一语言的编译程序。即用高级语言L1编写高级语言L2的编译程序，然后把写好的L2编译程序（源程序）经过L1的编译程序编译后就可以得到L2的编译程序。L1语言A代码A代码L2语言A代码L1语言L2语言A代码A代码同一台机器不同的语言B.移植方法把一种机器上的编译程序移植到另一种机器上。L语言A代码②A代码L语言B代码①L语言L语言B代码③A代码L语言B代码①L语言L语言B代码④B代码同一种语言不同的机器1.5编译程序的生成L1+L2+...+Ln…L1+L2C.自展技术按照自展技术，需要把源语言L分解成一个核心部分L0与扩充部分L1，L2，…，Ln。分解源语言之后，先用汇编语言或机器语言编写L0的编译程序，然后再用L0编写L1的编译程序，用Li编写Li+1的编译程序（i=1,2,…,n–1），像滚雪球一样，愈滚愈大，最后得到源语言L的编译程序。L13.利用工具，编译程序自动生成LEX词法分析程序产生器YACC语法分析程序产生器编译程序自动产生器L语言的语法描述语义描述目标语言或机器描述L语言的编译程序Theend.