编译原理第一章.

说明教材《编译技术》第2版清华大学出版社张素琴等。参考书《编译原理》机械工业出版社出版赵建华，郑滔，戴新宇翻译。电子课堂校园网主页中“教学天地”栏目中“电子课堂”中的“计算机系”第一章引论2015年9月第一章引论1.0语言处理器1.1什么是编译程序?1.2编译过程概述1.3编译程序的结构1.4编译阶段的组合1.5编译技术和软件工具1.0语言处理器编译器编译器就是一个程序；编译器可以阅读某种语言（源语言）编写的程序，并且把这个程序翻译为一个等价的、用另外一种语言（目标语言）描述的程序；编译器还有另外一个重要任务就是报告编译过程中出现的错误。解释器解释器不通过翻译的方式生成目标程序。直接利用输入信息，执行源程序中指定的操作，输入一句，执行一句，不保存中间结果。编译器目标程序解释器输出目标程序输出输入输入源程序1.0语言处理器编译器与解释器编译器产生的机器语言目标程序通常比一个解释器快得多；解释器的错误诊断效果要比编译器更好。JAVA语言处理过程——编译与解释的结合首先，JAVA源程序被编译为一个称为字节码的（bytecode）中间表示形式；然后，虚拟机对字节码进行解释执行。编译和解释可以在不同的机器上进行，有利于网络应用和跨平台运行。翻译器虚拟机源程序输出输入字节码需要处理的源程序预处理程序源程序编译器目标汇编程序汇编器可重定位的机器代码链接器—加载器目标（绝对）机器代码一个源程序可能被分割成多个模块，并且存放在独立的文件中；预处理程序完成这些文件的合并、宏展开等工作，将需要处理的源程序汇集在一起。经过预处理的源程序作为输入传递给编译程序，并且产生一个汇编程序作为输出。大型程序经常被分成多个部分进行编译，因此，可重定位的机器代码有必要和其他可重定位的目标文件以及库文件连接在一起，形成最终的机器代码。语言处理过程系统汇编语言程序由汇编器进行处理，并生成可重定位的机器代码。库文件/可重定位的对象文件链接器能够解决外部内存地址的问题，因为，有时一个文件代码可能指向另一个文件中的位置；加载器把所有的可执行目标文件放在内存中执行。1.1什么是编译程序?一个编译程序就是一个语言翻译程序。它把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价程序。编译程序是计算机系统的基本组成部分之一，一个计算机系统可以有多个高级语言的编译程序。有的高级程序设计语言甚至配置了几个不同性能的编译程序编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员和程序设计者独立于机器。适合机器种类和数量的增长.编译程序高级语言程序（源程序）低级语言程序（目标程序）1.源语言种类成千上万，目标语言也是成千上万，编译程序根据它们的构造不同，所执行的具体功能的差异又分成了各种类型。2.尽管存在各种类型的编译程序，但是各种编译程序所必须执行的主要任务基本是一样的，通过理解这些任务，使用同样的基本技术，我们可以为各种各样的源语言和目标语言设计和构造编译程序。3.也就是说编译程序的构成是有规律可循的，是值得分析和总结的。编译程序有规律可循全局角度认识编译程序编译过程就是将源程序映射到语义上等价的目标程序；映射过程分为两个部分：1.分析把源程序分解成为多个组成要素，并在这些要素上加语法结构；利用这个语法结构创建该源程序的一个中间表示；分析源程序是否按照语法构成，或者语义是否一致，并且提供相关信息；将分析过程产生的相关信息存贮在一个符号表数据结构中。将符号表和中间表示形式一同传递给综合部分。2.综合根据符号表和中间表示形式的信息来构造目标程序。3.分析部分通常被称为编译器前端；综合部分通常被称为编译器的后端细节角度认识编译程序实际上，编译过程是一组顺序执行的步骤；每个步骤把源程序的一种表示方式转换成另一种表示方式，一步一步接近最终的目标程序；实践过程中，往往将多个步骤组合在一起，构成一个阶段，在这个阶段过程中，不需要将每个步骤中间结果表示出来，只需要将这个阶段的中间结果表示出来，传递给下一阶段；机器无关代码往往作为编译过程前端和后端的分水岭，只是将前一阶段中间代码表示转换为另外一种形式。字符流词法分析器语法分析语义分析中间代码生成器机器无关代码优化器代码生成器机器相关代码优化器目标机器语言符号流语法树语法树中间表示形式中间表示形式目标机器语言1.2编译过程概述（一）编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。编译过程通常划分成词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段。另外有两个重要工作：表格管理和出错处理与上述六项阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格中，编译各阶段的工作都涉及到构造、查找和更新有关表格，因此，需要表格的管理工作。如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制到最小的范围内。使得编译工作得以继续。1.2编译过程概述（二）词法分析阶段：编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。逻辑上紧密相连的一组字符，这些字符具有集体含义。单词：标识符，保留字，算符，界符等。对于每个单词要素，词法分析产生（输出）如下的表示形式：（单词类型，单词有效值）；包括两个分量。也就是说经过词法分析，输出中间表示代码形式将传递给下一阶段，语法分析。描述词法规则的有效工具是正规式和有限自动机。beginvarsum,first,count:real;sum:=first+count*10end.用id1,id2和id3分别表示sum，first和count三个标识符的内部形式，经过词法分析，上述赋值语句变为：id1:=id2+id3*10保留字标识符运算符界符一个C源程序片断：inta;a=a+2;词法分析后可能返回:单词类型单词值保留字int标识符a界符;标识符a算符(赋值)=标识符a算符(加)+整数2界符；1.2编译过程概述（三）语法分析：编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如：“程序”、“语句”、“表达式”等等。语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。程序的结构通常是由递规规则表示的。递规规则反映出语法单位的层次结构。语法规则通常用上下文无关文法描述。例：sum:=first+count*10;规则赋值语句::=标识符“:=”表达式表达式::=表达式“+”表达式表达式::=表达式“*”表达式表达式::=“(”表达式“)”表达式::=标识符表达式::=整数表达式::=实数语法分析的一种表示方法一组递归语法规则描述“赋值语句”这个语法单元。整数（10）赋值语句标识符：=表达式表达式+表达式表达式*表达式标识符id2(first)标识符id3(count)id1(sum)语法树表示方法从上向下的分析方法。1.2编译过程概述（四）词法分析和语法分析本质上都对源程序的结构进行分析。词法分析的任务仅对源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和数字串，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符。语法分析识别递归定义的语法成分（单元）。1.2编译过程概述（五）语义分析阶段：使用语法树和符号表中的信息来检查源程序是否和语言定义一致；审查源程序有无语义错误，为代码生成阶段收集类型信息。语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。比如使用了没有声明的变量；或者给一个过程名赋值；或者调用函数时参数类型不合适或者参加运算的两个变量类型不匹配等等。：=Id1(sum)Id2(first)Id3(count)+*Inttoreal（整型转实型）10比如下边的程序片段：intarr[2],c;c=arr1*10;其中的赋值语句是符合语法规则的，但是因为没有声明变量arr1，而存在语义错。语义分析主要的任务完成静态语义审查和处理上下文相关性审查类型匹配审查类型转换1.2编译过程概述（六）将一个源程序翻译为目标代码的过程中，可能会构造出一个或者多个中间表示形式。语法树就是其中的一种，它在语法分析和语义分析中使用；中间代码生成：在进行了上述的语法分析和语义分析阶段的工作以后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。这种中间代码是一种明确的低级的或者类机器语言的中间表示。可以看作是某种抽象机器的程序；所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样形式，重要的设计原则是两点：一是容易生成，二是容易将它翻译成目标代码。中间代码的形式很多。主要有四元式、三元式、间接三元式、逆波兰式、树等形式。sum:=first+count*10中间代码的形式：(intoreal10-t1)(*id3t1t2)(+id2t2t3)(:=t3-id1)1.2编译过程概述（七）代码优化：此阶段的任务是对前阶段产生的中间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。优化分与机器相关和机器无关。编译所产生的目标程序，其执行的次数和编译次数无关。可以多次运行，编译产生的代码质量越高，运行时间和占用空间越少。删除公共因子、强度消弱、循环优化等。1.2编译过程概述（八）目标代码生成：这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译的最后阶段，它的工作与硬件系统结构和指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存贮空间分配以及寄存器和后缓冲器的调度等。1.2编译过程概述（九）上述编译过程的阶段划分是一种典型的处理模式，事实上并非所有的编译程序都包括这样几个阶段。有些编译程序并不要中间代码，即不存在中间代码生成阶段；有些编译程序不进行优化，优化阶段即可省去;有些最简单的编译程序只有词法分析，语法分析；语义分析和目标代码生成。1.2编译过程概述（十）编译程序的另外两个重要的工作是表格管理和出错处理.他们与上述六个阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。最重要的一种表格是符号表。符号表中记录源程序中使用的名字和收集到的每个名字的各种属性信息，诸如类型、作用域、分配存储信息。在第二章你会看到一种符号表，在第九章你会对符号表的组织和管理了解的更深入。出错处理程序的任务包括检查错误、报告出错信息、排错、恢复编译工作。1.3编译程序的结构源程序词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成程序目标程序出错处理程序表格管理程序1.4编译阶段的组合（一）编译过程除了用六个阶段划分,也可以用其他的角度描述编译过程。编译过程分成前端和后端；编译过程也可以看成是分成一遍、两遍或多遍。前端的主要工作依赖于源语言而与目标机无关。包括词法分析、语法分析、语