编译原理课程教案

第1章引论本章内容什么是编译编译过程概述编译阶段的组合：通过描述编译器的各个阶段来介绍编译这个课题1．1什么是编译程序?一、程序设计语言的基础知识1、程序：一系列指令或语句，用来描述计算机依次要执行的一系列工作。2、结构：基本符号(字母、数字、符号等)、单词(符号)、量(语法单位)、表达式、语句、分程序、程序3、程序设计语言的定义（指高级程序设计语言）分语法、语义和语用三部分。语法是描述程序的结构，根据它可以产生正确的程序。（词法规则、语法规则）语义是语言成分的含义，由程序执行的效果来说明。语用是语言的实际应用。如：x:=a+b*c二、什么是翻译程序？翻译程序指的是这样一个程序，它能够把某一种语言程序(源语言程序)改造成另一种语言程序(目标语言程序)，而两者在逻辑上是等价的。三、程序设计语言的转换编译程序源语言是高级语言，目标语言是机器语言/汇编语言，则翻译程序称为编译程序。汇编程序源语言是汇编语言，目标语言是机器语言，则翻译程序称为汇编程序。解释程序解释程序是另一类翻译程序，它同时处理源程序和数据,对源程序解释执行而不生成目标程序。四、编译过程可分为两个阶段或三个阶段：1、编译执行：按编译方式在计算机上执行用高级语言编写的程序，需经过两个阶段：编译阶段，把源程序翻译为目标程序；运行阶段，真正执行此目标程序。优点：只需分析与翻译源程序一次，不必重新翻译。缺点：目标程序在运行中发现的错误，只要来源于源程序，必须在源程序中找错。2、解释执行：源程序的每个语句一经解释就立即执行。优点：与用户通信方便。缺点：效率很低。1．2编译过程和编译程序的结构如：一、编译程序的组织编译程序从输入源程序到输出目标程序，可由五部分来组成:二、编译程序的各个部分1、词法分析输入源程序，对构成源程序的字符串从左到右一个字符一个字符地进行扫描和分解，依据词法规则(或构词规则)识别出一个个的单词(单词符号或符号)，转换成机器容易识别的内码形式。内码用二元式(种别码，属性值)表示。输入：字符串输出：(种别码，属性值)——序对属性值——单词的机内表示是最初级的语法分析单词种类：(1)一类是特殊的单词，如保留字、运算符、分界符等，这些都是源语言所提供的；(2)另一类是普通单词，如用户在源程序中定义的标识符、常数等。例如：程序段intx,a,b;x=a+b*50;词法分析后的结果为(1)保留字int(2)标识符x(3)界限符,(4)标识符a(5)界限符,(6)标识符b(7)界限符；(8)标识符x(9)运算符=(10)标识符a(11)运算符+(12)标识符b(13)运算符*(14)整常数50(15)界限符;3、语法分析根据语言的语法规则(文法规则)，把单词符号串组成各类语法单位(语法范畴)，如：表达式、语句、分程序、程序输入：单词序列输出：语法单位语法规则写成Backus-Naur-Form(BNF)式，形式如下：A::=B|C或A?B|C语法分析有两种方法：推导(Derive)和归约(Reduce)语法分析对说明语句填写符号表，一般语句构造语法树例如：赋值语句a=b+c*10经语法分析生成语法树赋值语句a=b+c*10语法树的另一种形式4、语义分析语义：程序的“意思”。任务：1.分析语法成分的含义和用途，2.应进行的运算和操作，3.同时进行相应的语义检查。如：在说明语句中是否有矛盾的类型说明。表达式中，类型不匹配。过程调用中，实参和形参的配合。依据：语义规则。赋值语句a=b+c*10经语义分析生成语法树（考虑类型问题：a,b,c为实型）中间代码生成根据语义规则产生一种介于源语言与目标代码之间的一种中间代码。中间代码是不依赖于机器但是又便于生成依赖于机器的目标代码的一种结构简单、含义明确的记号系统。中间代码常用四元式来表示：中间代码的特点:简单规范、机器无关、易于优化与转换。例a=b+c*105、代码优化对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生更为高效(省时间和空间)的目标代码。主要依据是等价变换规则优化主要包括：删除公共子表达式、合并已知量、删除无用赋值、循环优化、算符规约等等例.赋值语句a:=b+c*10优化6、目标代码生成。把中间代码变换成指定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码。与硬件系统功能部件的运用，机器指令的选择，各种数据类型变量的存储空间分配，寄存器和后缓寄存器的调度等等有很大的关系。7、表格与表格管理。编译程序在工作过程中需要保持系列的表格，用以登记源程序的各类信息和编译各阶段的进展状况。合理的设计和使用表格式编译程序构造的一个重要问题。与编译的头三个阶段有关的表格有：符号表、常数表、标号表、分程序入口表、中间代码表、过程引用表、循环特征表、等价名表、公用链表、格式表。表格的结构大体如下：8、出错处理错误可发生在编译的各个阶段，错误处理也是贯穿编译全过程。词法：拼写……语法：语句结构、表达式结构……语义：类型不匹配……在编译时查出的，叫Comple-timeerror，在运行时表现才表现出来的错误叫Run-timeerror。1．3编译阶段的组合前端包括编译逻辑结构中的分析部分，即词法分析、语法分析、语义分析和中间代码生成，除此还包括符号表建造及相应分析中的错误处理以及与机器无关的优化部分。后端包括与目标机有关的部分，即综合部分，它包括目标代码生成及生成期间对符号表的相应检索操作和错误处理操作，以及与机器相关的代码优化部分。将编译系统划分为前后端，有利于移植编译系统和利用后端为同一目标机配置不同语言的编译系统。遍(Pass)对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。分遍原则∶①目标质量高低(高则多遍)。②机器内存大小(小则多遍)。③源语言简繁(繁则多遍)。④设计人员多少(多则多遍)。把前端组织成一遍扫描:把前端组织成多遍扫描:(多遍：上一遍的输出是下一遍的输入。)设计编译程序应首先研究的问题:要在某机器上为某种语言构造一个编译程序，必须掌握下面的内容：1、源语言：语法、语义。2、目标语言：对于机器指令，搞清硬件的系统结构和OS的功能。3、编译方法：必须掌握一二种。4、语言选择：编制程序。编译程序的伙伴:预处理器产生编译程序的输入,在真正的编译开始之前由编译程序调用的程序。它可以完成以下的任务：1.宏处理(宏扩展):预处理器允许用户使用宏定义,它们是一些较长结构的缩写。宏处理处理两类语句∶宏定义和宏调用2.文件包含:预处理器可以把文件的包含声明扩展为程序正文。例如，当处理的文件有语句＃include时，C语言的，预处理器会用文件来代替这个语句。3.汇编程序将汇编语言源程序，翻译为机器语言的目标程序的翻译程序称为汇编程序。4.装配程序和连接程序将分别在不同的目标文件中编译或汇编的代码收集到一个可执行的文件中。完成连接目标程序和用于标准库函数程序的代码，以及连接目标程序和由计算机的操作系统提供的资源（如存储分配程序及输入与输出设备）。1．4构造编译程序的工具1.扫描仪的生成器：自动生成词法分析器，通常是基于正规式说明，生成的词法分析器的基本组织形式实际上是有限自动机。如：LEX2.分析器的生成器：生成语法分析器，通常是基于上下文无关文法。如：YACC3.语法制导的翻译工具：产生一些子程序，这些子程序遍历分析树，产生中间代码。4.自动的代码生成器：需要一个规则集合，这些规则定义中间语言的每个操作到目标语言的翻译。这些规则必须足够详细。5.数据流工具：它收集值是怎样从程序的一点传到其它部分。编译技术在软件工程中的应用语法制导的结构化编辑器:除了通常的正文编辑和修改功能外，还能对源程序进行语法分析。程序格式化工具:用更加清晰可读的格式排版程序，如缩进，格式，注释使用专门字体等。程序理解工具:对程序进行分析，确定模块间的调用关系，程序数据的静态属性和结构属性，变量的交叉引用，程序的控制流程图等，以帮助用户理解程序。编译技术在软件工程中的应用软件测试工具包括∶静态分析器和动态结构测试器。静态分析器∶不运行程序而对程序中的潜在错误和异常进行检查。动态分析器∶用一组测试数据实际执行程序，记录并分析执行路径，再与预期结果进行比较，以发现程序中的异常。高级语言的翻译工具一种高级语言译为另一种高级语言数据库系统查询脚本语言置标语言(HTML.XML)第1章小结内容1什么是编译程序2编译过程和编译程序的结构3为什么要学习编译程序（应用）本章没有难以理解的内容,重点对编译程序的功能和结构做一综述,要说难点的话可能是:了解编译程序各个成分在编译阶段的逻辑关系以及他们怎样作为一个整体完成编译任务的。第2章文法和语言课程内容字母表与符号串文法与语言的关系－文法的概念－文法与语言的形式定义文法构造与文法简化－由语言构造文法的例子－文法的简化语法树与文法的二义性文法的概念学习的目的构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述，根据这种描述，构造出相应的分析加工程序。语言分语法，语义和语用。程序语言语法的形式描述是很好用的，语义的形式描述不那么好用，但它推动语言理论的发展。2．1符号和符号串一、字母表字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如:1.机器语言：由符号“0”和“1”组成的字母表,∑={0，1}2.ASCII字符集；3.汉语的字母表中包括汉字、数字及标点符号4.C字母表为：∑={A~Z,a~z,0~9,+,-,*,/,,=,,:,',',;，.，,(,),{,},[,]}二、符号串1.符号一个抽象实体,我们不再形式地定义它(就象几何中的”点”一样).例如字母是符号,数字也是符号2.符号串由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作“字”或“句子”。(1)不包含任何符号的符号串，称为空符号串简称空串，记为ε。(2)若∑={a,b}则a,b,ab,ba,abb,baa...是∑上的符号串。•在符号串中，符号的顺序是很重要的，符号串ab就不同于ba,abca和aabc也不同。3.术语设z是符号串长度:是该符号串中的符号的数目。例如|aab|=3,|ε|=0。前缀(头):删去z尾部的若干个(包括0个)符号所得的。表示:z=x……后缀(尾):删去z头部的若干个(包括0个)符号所得的。表示:z=……x真前缀(固有头)x，真后缀(固有尾)x:x≠z子串:从z中删去一个前缀和一个后缀逆转（用z表示）：将z中的符号按相反次序写出而得到的符号串。例：符号串z=banana长度：banana=6前缀：e,b,ba,ban,bana,banan,banana真前缀:e,b,ba,ban,bana,banan后缀：banana,anana,nana,ana,na,a,e真后缀:anana,nana,ana,na,a,e子串:banana,anana,banan,anan,…,e逆转（用z表示）：ananab三.符号串的运算1.连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=bananaεx=xε=x2.方幂：符号串x自身连接n次得到的。x0=e;x1=x;x2=xx;……;xn=xn-1x=xxn-1;例如,x=ba,x1=ba,x2=baba,x3=bababa,xn=(ba)n四.符号串集合(语言）的运算定义:集合中的一切元素都是某字母表上的符号串。设A和B是两个符号串集合，则1.乘积(连接)：AB＝｛xy|xÎAandyÎB}A={ab,bc}B={ac,cb}AB=｛abac,abcb,bcac,bccb}2.合并：A∪B＝｛x|xÎAorxÎB}A∪B={ab,bc,ac,cb}3.空集:ffA=Af=f4.方幂：符号串集合的自身乘积。A0={ε}，A1＝A，A2＝AA,...,An＝An-1A＝AAn-1A={a,b}A0={ε}，A1＝A={a,b}，A2＝AA={aa,ab,ba,bb}A3＝