编译原理课程教案.doc

第1章 引论本章内容 什么是编译 编译过程概述 编译阶段的组合：通过描述编译器的各个阶段来介绍编译这个课题 11 什么是编译程序?一、程序设计语言的基础知识1、程序：一系列指令或语句，用来描述计算机依次要执行的一系列工作。2、结构：基本符号(字母、数字、符号等)、单词(符号)、量(语法单位)、表达式、语句、分程序、程序3、程序设计语言的定义（指高级程序设计语言） 分语法、语义和语用三部分。 语法是描述程序的结构，根据它可以产生正确的程序。（词法规则、语法规则） 语义是语言成分的含义，由程序执行的效果来说明。 语用是语言的实际应用。 如： x:=a+b*c二、什么是翻译程序？翻译程序指的是这样一个程序，它能够把某一种语言程序(源语言程序)改造成另一种语言程序(目标语言程序)，而两者在逻辑上是等价的。三、程序设计语言的转换 编译程序源语言是高级语言，目标语言是机器语言/汇编语言，则翻译程序称为编译程序。 汇编程序源语言是汇编语言，目标语言是机器语言，则翻译程序称为汇编程序。 解释程序解释程序是另一类翻译程序，它同时处理源程序和数据,对源程序解释执行而不生成目标程序。四、编译过程可分为两个阶段或三个阶段： 1、 编译执行：按编译方式在计算机上执行用高级语言编写的程序，需经过两个阶段： 编译阶段，把源程序翻译为目标程序； 运行阶段，真正执行此目标程序。 优点：只需分析与翻译源程序一次，不必重新翻译。 缺点：目标程序在运行中发现的错误，只要来源于源程序，必须在源程序中找错。2、 解释执行：源程序的每个语句一经解释就立即执行。 优点：与用户通信方便。 缺点：效率很低。12 编译过程和编译程序的结构 如： 一、 编译程序的组织 编译程序从输入源程序到输出目标程序，可由五部分来组成 :二、 编译程序的各个部分 1、词法分析输入源程序，对构成源程序的字符串从左到右一个字符一个字符地进行扫描和分解，依据词法规则(或构词规则)识别出一个个的单词(单词符号或符号)，转换成机器容易识别的内码形式。内码用二元式(种别码，属性值)表示。输入：字符串 输出：(种别码，属性值)序对属性值单词的机内表示是最初级的语法分析 单词种类：(1) 一类是特殊的单词，如保留字、运算符、分界符等，这些都是源语言所提供的；(2) 另一类是普通单词，如用户在源程序中定义的标识符、常数等。 例如：程序段 int x,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*10 5、代码优化对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生更为高效(省时间和空间)的目标代码。主要依据是等价变换规则优化主要包括：删除公共子表达式、合并已知量、删除无用赋值、循环优化、算符规约等等 例.赋值语句a:=b+c*10优化6、 目标代码生成 。把中间代码变换成指定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码。 与硬件系统功能部件的运用，机器指令的选择，各种数据类型变量的存储空间分配，寄存器和后缓寄存器的调度等等有很大的关系。7、 表格与表格管理。编译程序在工作过程中需要保持系列的表格，用以登记源程序的各类信息和编译各阶段的进展状况。合理的设计和使用表格式编译程序构造的一个重要问题。与编译的头三个阶段有关的表格有：符号表、常数表、标号表、分程序入口表、中间代码表、过程引用表、循环特征表、等价名表、公用链表、格式表。表格的结构大体如下：8、 出错处理错误可发生在编译的各个阶段，错误处理也是贯穿编译全过程。词法：拼写语法：语句结构、表达式结构语义：类型不匹配在编译时查出的，叫Comple-time error，在运行时表现才表现出来的错误叫Run-time error。13 编译阶段的组合 前端包括编译逻辑结构中的分析部分，即词法分析、语法分析、语义分析和中间代码生成，除此还包括符号表建造及相应分析中的错误处理以及与机器无关的优化部分。 后端包括与目标机有关的部分，即综合部分，它包括目标代码生成及生成期间对符号表的相应检索操作和错误处理操作，以及与机器相关的代码优化部分。 将编译系统划分为前后端，有利于移植编译系统和利用后端为同一目标机配置不同语言的编译系统。 遍(Pass)对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。 分遍原则 目标质量高低(高则多遍)。 机器内存大小(小则多遍)。 源语言简繁(繁则多遍)。 设计人员多少(多则多遍)。把前端组织成一遍扫描: 把前端组织成多遍扫描:( 多遍：上一遍的输出是下一遍的输入。) 设计编译程序应首先研究的问题: 要在某机器上为某种语言构造一个编译程序，必须掌握下面的内容：1、 源语言：语法、语义。2、 目标语言：对于机器指令，搞清硬件的系统结构和OS的功能。3、 编译方法：必须掌握一二种。4、 语言选择：编制程序。编译程序的伙伴: 预处理器 产生编译程序的输入,在真正的编译开始之前由编译程序调用的程序。 它可以完成以下的任务： 1. 宏处理(宏扩展):预处理器允许用户使用宏定义,它们是一些较长结构的缩写。 宏处理处理两类语句宏定义和宏调用2. 文件包含:预处理器可以把文件的包含声明扩展为程序正文。例如，当处理的文件有语句include时，C语言的，预处理器会用文件来代替这个语句。3. 汇编程序将汇编语言源程序，翻译为机器语言的目标程序的翻译程序称为汇编程序。4. 装配程序和连接程序将分别在不同的目标文件中编译或汇编的代码收集到一个可执行的文件中。完成连接目标程序和用于标准库函数程序的代码，以及连接目标程序和由计算机的操作系统提供的资源（如存储分配程序及输入与输出设备）。14 构造编译程序的工具 1.扫描仪的生成器：自动生成词法分析器，通常是基于正规式说明，生成的词法分析器的基本组织形式实际上是有限自动机。如：LEX2.分析器的生成器 ：生成语法分析器，通常是基于上下文无关文法。如：YACC3.语法制导的翻译工具：产生一些子程序，这些子程序遍历分析树，产生中间代码。 4.自动的代码生成器： 需要一个规则集合，这些规则定义中间语言的每个操作到目标语言的翻译。这些规则必须足够详细。 5.数据流工具：它收集值是怎样从程序的一点传到其它部分。编译技术在软件工程中的应用语法制导的结构化编辑器: 除了通常的正文编辑和修改功能外，还能对源程序进行语法分析。程序格式化工具: 用更加清晰可读的格式排版程序，如缩进，格式，注释使用专门字体等。程序理解工具: 对程序进行分析，确定模块间的调用关系，程序数据的静态属性和结构属性，变量的交叉引用，程序的控制流程图等， 以帮助用户理解程序。编译技术在软件工程中的应用 软件测试工具 包括静态分析器和动态结构测试器。 静态分析器不运行程序而对程序中的潜在错误和异常进行检查。 动态分析器用一组测试数据实际执行程序，记录并分析执行路径，再与预期结果进行比较，以发现程序中的异常。高级语言的翻译工具 一种高级语言译为另一种高级语言 数据库系统查询 脚本语言 置标语言(HTML.XML)第1章 小结 内容1 什么是编译程序2 编译过程和编译程序的结构3 为什么要学习编译程序（应用） 本章没有难以理解的内容,重点对编译程序的功能和结构做一综述,要说难点的话可能是:了解编译程序各个成分在编译阶段的逻辑关系以及他们怎样作为一个整体完成编译任务的。第2章 文法和语言课程内容 字母表与符号串 文法与语言的关系 文法的概念 文法与语言的形式定义 文法构造与文法简化 由语言构造文法的例子 文法的简化 语法树与文法的二义性文法的概念学习的目的 构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述，根据这种描述，构造出相应的分析加工程序。 语言分语法，语义和语用。程序语言语法的形式描述是很好用的，语义的形式描述不那么好用，但它推动语言理论的发展。21 符号和符号串 一、字母表 字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如:1.机器语言：由符号“0”和“1”组成的字母表, =0，1 2.ASCII字符集； 3.汉语的字母表中包括汉字、数字及标点符号 4. C字母表为： =AZ, az, 09, +, -, *, /, , :, , ; ，.， , (, ), , , , 二、 符号串 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 :xz 子串: 从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=x 2.方幂：符号串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|xA and yB A=ab,bcB=ac,cbAB=abac,abcb,bcac,bccb 2. 合并：ABx|xA or xB AB=ab,bc,ac,cb 3. 空集:f fA=Af=f 4. 方幂：符号串集合的自身乘积。 A0=， A1A， A2AA, ., AnAn-1AAAn-1 A=a,b A0=， A1A=a,b， A2AA=aa,ab,ba,bb A3A2A=AA2=aaa,aab,aba,abb, 5. 集合A的Kleene闭包(星闭包)，记作A*，字母表A的各次方幂之并。其含义是由A上符号组成的所有串的集合（包括空串) A*Ai(i=0) =A0A1A2A3 A=a,b A*,a,b,aa,ab,ba,bb, aaa,aab,aba,abb, 6集合A的正闭包，记作A+，其含义是由字母表A上的符号组成的所有串(不包括空串)的集合。 A+Ai(i =1) =A1A2A3A4 A=a,b A+a,b,aa,ab,ba,bb, aaa,aab,aba,abb, A* A0 A+ A+=AA*A*A n语言是由句子组成的集合,是由一组符号所构成的集合。换言之,字母表S上的一个语言是S上的一些符号串的集合(字母表S上的每个语言是S*的一个子集)。 例如：字母表=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 集合ab,aabb,aaabbb,anbn, 或表示为w|w*且w=anbn,n1 字母表S上的一个语言。 集合a,aa,aaa, 或表示为w|w*且w=an,n1 字母表S上的一个语言。 是一个语言。 F即 是一个语言。 给出语言上的有关运算设L是（S上的）一个语言, M是（S上的）一个语言, 语言L和M的并，交，差，补是一个语言。 语言L和M的并为 LM: LM=w|wL 或 wM 如： L1=a,b,y,z M1=1,28,9 L1M1=a,b, y,z，1,28,9 语言L和M的连接为 LM:LM=st |sL且tM 如： L1M1=a1,b1,y1,z1,a2,b2a9z9 有L = L=L。 L的n次连接Ln=LL.L 如： L12=aa,ab,az,ba,bb, bz, ,za,zbzz语言L的闭包记为 L*， L*= L0 L1 L2 . L0= ， Ln= L Ln-1= Ln-1L,n1 语言L的正闭包记为 L+， L+= L1 L2 L3. L+= LL*= L*LL*= L+ 如： L1=a,b,y,z M1 =1,28,9 （L1M1）=a,b, y,z，1,28,9 （L1M1）*=a,b, y,z，1,28,9 ，aa,1a,xyz,6789st. L1（L1M1）*=所有字母打头的字母和数字符号串 如何来描述一种语言？ (1)枚举法 例:1,11,111,1111 (2)自然语言 (3)省略表示法 例:1,11,111, (4)描述法 例:1i|i0 例如：L=AZ,az D=09 1LD是由所有一个字母后跟一个数字组成的符号串所构成的集合。 2LD=AZ,az ,09 3L4是由所有的四个字母的符号串构成的集合。 4L（LD)* 是由所有的字母打头的字母和数字组成的符号串所构成的集合。 5D+是由所有长度大于等于1的数字串所构成的集合。 如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经： -生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。 -识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。） 文法即是生成方式描述语言的： 语言中的每个句子可以用严格定义的规则来构造。22 文法的类型 乔姆斯基(Chomsky)将文法G=(VN,VT,P,S）分成四种类型:0型、1型、2型、3型 逐渐对产生式施加限制 0型(短语)：产生式形式: ab ,(VNVT)+且至少含有一个非终结符，而(VNVT)* 1型（上下文有关）: 产生式形式:均满足|；仅 S例外，但S不得出现在任何产生式的右部。 2型（上下文无关）：产生式形式 ： ab a VN，b (VTVN)* 3型(正规文法) (右线性) AaB 或 A a ; (左线性) ABa或A a A,BVN,a VTe例：2型（上下文无关） 文法GS： SAB ABS|0 BSA|1 例：3型（正规） GS：S0A|1B|0 A0A|1B|0S B1B|1|0 GI：I lT I l T lT T dT T l T d 四种文法之间的逐级“包含”关系 四种文法之间的关系是将产生式做进一步限制而定义的。 语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。 0型文法强于1型，1型强于2型，2型强于3型 23 上下文无关文法及其语法树 1.语法树的定义 表示一个句型推导的图表称为语法树，它描述的句子的结构。 设G=(VN,VT,P,S),G的一棵语法树满足如下条件： 1.每一个结点有一个标记，此标记是VTVN中的符号。 2.根的标记是S。 3.若一个结点是内部结点，且有标记A,那么A必在VN中。 4.若编号为n的结点有标记A,结点n1,n2,nk是点n的从左到右的儿子,并分别有标记A1,A2, Ak,则AA1A2Ak必须是P中的产生式。 语法树的结果： 从左到右读出叶子的标记而构成的行。用于描述上下文无关文法句型推导的直观方法 例 (例3.7) G=(S,A,a,b,P,S）,其中 PSaASa A SbA SS ba叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记连接成的文法符号串，为GS的句型。也把该推导树称为该句型的语法树。 句子：aabbaa 语法树-句型推导的直观表示给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树) 定理： G为上下文无关文法， 对于，有S =* ，当且仅当文法G有以为结果的一棵语法树(推导树2.如何画出语法树 根据推导序列，对每步推导画相应分枝 P SaASa A SbA SS ba 字符串：aabbaa 注意：语法树的顺序性P SaASa A SbA SS ba 关于语法树的几点说明语法树是推导的图形表示。 1. 一个句型推导或分析用一棵树结构图示 出来，它反映了一个句子的语法结构。 2. 对于一个句子的多种推导(若文法是无二义性的)，采用各种推导过程，画出的语法树是一样的。语法树并未描述推导过程。 3. 在书中，用画语法树的过程解释语法分析过程，用语法树图解语法结构。 S aASaSbASaabASaabbaSaabbaaS aAS aAa aSbAa aSbbaaaabbaa3. 子树语法树中除了叶结点以外的任意一个结点连同它的所有的子孙结点构成一棵子树。例如：简单子树：只含有单层分枝的子树称为简单子树。4.文法的二义性(歧义性)的定义 如果一文法的某个句子存在两棵语法树,那么， 该句子是二义性的。如果一文法包含二义性 的句子，则这个文法是二义性的；否则，该 文法是无二义性的。 若一个文法中存在某个句子，它有两个不同的最左或最右推导（两棵语法树），则这个文法是二义的。 对于一个程序语言来说，常常希望它的文法是无二义的。 考虑表达式下面的文法 GE,其产生式如下 EE+EE*E (E)a 对于句子a+a*a, 有如下两个最左推导： 例1EE+E a+E a+E*E a+a*E a+a*a EE*EE+E*E a+E*Ea+a*E a+a*aB bB|Bb|b 构造字符串bb的语法树 B bB|Bb|b 构造字符串bb的语法树 二义性的几点说明： 1 . 一般来说，程序语言存在无二义性文法 例：简单算术表达式的文法 二义性文法 EE+E|E-E|E*E|E/E|(E)|a 非二义性文法 EE+T|E-T|T TT*F|T/F|F F(E)|a 改造方法：使文法含有更多的信息24 句型的分析-即构造一种算法用以判断给定的符号串是否为某一文法的句型、句子。分析程序：完成句型分析的程序称为分析程序或识别程序。 可以根据文法从分析符号串的语法结构检查一个符号串是否为句子，即通过语法分析方法来进行确定。 根据语法分析方法的特点，可以将其分成两大类，一是自顶向下的分析方法，一是自底向上的分析方法，名称来源与建立语法树的方法有关。 -自顶向下的分析 -自底向上的分析自顶向下的分析基本思路从文法的识别符号开始，建立一个推导序列，使其推得的终结符号串恰好是所给的符号串。若目标能实现，则所给符号串获得识别，其结构符合文法。反之，则不符合文法。自底向上分析基本思路从待分析的符号串本身入手，尝试将它归约为识别符号，即对符号串一步一步进行归缘直至识别符号，若能成功，则符号串被识别为句子，否则，不是。用子树解释短语，直接短语，句柄:句型由树的末端符从左至右连成的串是该文法的一个句型。 短语子树的末端符自左至右连成的串，相对于子树而言称之为短语。直接短语：简单子树的末端符自左至右连成的串，相对于子树而言称之为直接短语。 句柄最左的简单子树的末端符自左至右连成的串。例如，对表达式文法GE和句子a1+a2*a3,挑选出推导过程中产生的句型中的短语，直接短语，句柄。 补充：压缩过的文法（化简了的文法）： 1 无产生式： AA P ； 2 每个非终结符号A必须都有用处。即 S* A 且A + ，VT* 、 (VTVN) * 否则A为无用符号。 方法：删除无用符号和无用产生式 分两步，顺序可颠倒，且可多次使用。 用于：文法的等价变换后的化简。算法1：将文法G=(VN ,VT,P,S),改造成等价的文法G1(VN,VT,P,S),使得对于每个AVN,都有S * A 从左到右看 (1)对产生式中识别符号S加标记； (2)对左部非终结符号加有标记的产生式，将其右部中出现的一切非终结符号加标记； (3)重复（2）直到未再对任何非终结符号加标记为止。 (4)检查产生式，删除那些含有未加标记非终结符号的产生式。 例如(例3.10):文法G=(e,f,S,A,B,C,D,P,S) P: (1) SBe (2)BCe (3) BAf (4) AAe (5)Ae (6) CCf (7) Df 结果集 (1) SBe (2)BCe (3) BAf (4) AAe (5)Ae (6) CCf 算法2：将文法G=(VN ,VT,P,S),改造成等价的文法G1=(VN, VT,P,S),使得对于每个AVN,都有VT*,满足A + 。从右到左看 (1)对uVT*的产生式Au左部非终结符A加标记； (2)对右部仅含有终结符与已加标记的非终结符号的产生式之左部加标记； (3)重复（2）直到未再对任何非终结符号加标记为止。 (4)检查产生式，删除那些含有未加标记非终结符号的产生式。 例如:文法G=(S,A,B,C,D,e,f,P,S) P:SBe AAe Ae BCe BAf CCf结果集 SBe AAe Ae BAf 补充:非上下文无关的语言结构 在我们使用的程序语言中,有些语言结构并不是总能用上下文无关文法描述的。例 L1=wcw|wa,b+。例如,aabcaab就是L1的一个句子。这个语言是检查程序中标识符的声明应先于引用的抽象。例 L2=anbmcndm|n,m0，它是检查过程声明的形参个数和过程引用的参数个数一致问题的抽象。 语言中过程定义和引用的语法并不涉及到参数个数，例如，Pascal的过程语句可描述为s-callid(r-list) r-listr-list, r |r 实参和形参个数的一致性检查也是放在语义分析阶段完成的。上下文无关语言和正则语言的区别定义 如果一个上下文无关文法G中存在具有下列特征的非终结符A: A + A 其中,VTVN+,则称A为自嵌套的, 包含自嵌套非终结符号的文法是上下文无关文法 语言anbn|n0是上下文无关语言，原因是找不到一个非自嵌套的上下文无关文法描述它； 语言anbm|n，m 0是正则语言,原因是存在一个正规文法描述它。 在程序语言中，与词法有关的产生式属于正规文法；与局部语法有关的产生式属于上下文无关文法；而与全局语法和语义有关的部分往往要用上下文有关文法来描述。为什么不用上下文有关文法描述程序语言？用上下文有关文法描述程序语言不仅相当困难，将使语法定义变得烦杂，难懂，而且一般不能构造有效的分析程序，因此，通常用上下文无关文法描述，而把与上下文有关的限制包含在非形式描述的全局语法与语义中。 把描述词法的正规文法从描述语法的上 下文无关文法中分离出来。在分离出正则文法后的上下文无关文法中，这些单词符号是属于终结符号VT中的符号。思考-本章目的为语言的语法描述寻求工具,以便： 对源程序给出精确无二义的语法描述。（严谨、简洁、易读） 根据语言文法的特点来进行语法分析 从描述语言的文法可以自动构造出可用的分析程序 1.什么是文法,什么是它的语言? 2.我们为什么关注上下文无关文法? 3.语法分析方法的分类?第2章小结1.本章出现的概念较多,应重点理解文法,推导,句型句子及语言的定义等概念.语法分析有关内容在后面章节会详细讨论。 2.文法作为程序语言的语法的描述工具,它用规则只能陈述的是:语言的所有句子以什么样的符号串能出现.请记住文法和语言的形式定义中的 “形式”的含义只涉及语言的语法不涉及语言的语义。3.本章内容是形式语言理论的一部分.形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。二义性的几点说明： 1 . 一般来说，程序语言存在无二义性文法 例：简单算术表达式的文法 二义性文法 EE+E|E-E|E*E|E/E|(E)|a 非二义性文法 EE+T|E-T|T TT*F|T/F|F F(E)|a 改造方法：使文法含有更多的信息课后自学练习 再例：If语句 Sif E then S Sif E then S else S 设执行下列语句前b=0, if a0 then if a0 then b=1 else b=-1 当a=1时,b=1;当a=0时，b=0 if a0 then if a0 then b=1 else b=-1 当a=1时,b=1;当a=0时，b=-1一个句子有两棵不同的语法树按照“改造1”构造的语法树按照“改造2”构造的语法树2. 在能驾驭的情况下，使用二义性文法。 3. 文法二义性问题是不可判定的，也就是不存在一种算法，能在有限步内确切的判定一个文法是否是二义性文法。 4. 存在先天二义性语言。例如， aibicji,j1 aibjcji,j1 存在一个二义性的句子akbkck补充：语言文法（不是一一对应的） 在某些情况下，人们以某种形式给出有关语言的描述，如何为此语言构造一个文法使得它生成的语言正好满足这个预言的描述呢？例1：L=an|n1 VT=a 分析：n=1, L=a n=2, L=aa ; 任意个a。 方法：从上到下找 Z最少一个a： Za 在Z上添加若干a: ZaZ 或 ZZa例2：L=a2nb|n1 VT=a,b 分析：n=1, L=aab n=2, L=aaaab ; 偶数个a后跟一个b。 方法：从上到下找 两部分： ZAb A:偶数个a 即a2n A最少两个a: Aaa AaAa ZAb Aaa|aAaZAb Aaa|aaAZAb Aaa|Aaa例3：L=anbn|n1 VT=a,b 分析：n=1, L=ab n=2, L=aabb n=3, L=aaabbb ; a,b个数相同的符号串。 方法：从上到下找 Z最少是ab Zab Z前后分别加一个a,b: ZaZb Zab|aZb 第3章 词法分析 3.1 词法分析程序的设计：词法分析程序的功能，输出，把它组织成单独程序3.2 正规式：单词能用正规式描述，能用DFA识别3.3 词法分析程序的手工构造：用DFA 能识别单词，构造DFA并用程序实现它3.4 有穷自动机：有穷自动机的等价性， 一个FA m , min( DFA m) L(m)=L(m)3.5 正规文法与有穷自动机的等价性31 单词的描述工具 词法 单词符号的文法，用来描述高级语言中的：标识符、常数、运算符、分界符、关键字 单词的描述工具 正规文法 正规集 正规式一、 正规文法（3型文法） 右线性： AaB Aa左线性： ABa Aa aVT如：程序设计语言( l 表示az中的任一英文字母,d表示09中的任一数字。) l|l l|d|l|d d| d +|-|*| / | = | | = if | while | else 在一个正规文法中不允许既用右线性文法又用左线性文法。 由正规文法产生的语言称作正规集。 正规集是一个有穷或者无穷的集合，可用正规式(Regular Expression,Re)来描述。 正规式也称正则表达式,正规表达式是说明单词的模式(pattern)的一种重要的表示法(记号)，是定义正规集的数学工具。正规式描述的集合称作正规集。二. 正规式的定义(递归定义) 是字母表 =, , |, , *,(,) 正规式 正规式表达的语言(正规集) 1.， ， 2.a,a a 3.若 e1,e2 L(e1) , L(e2) 则 (a)e1|e2 (或) L(e1 )L(e2) (b)e1e2(连接)L(e2)L(e2)(c)e1*(闭包) (L(e1)* (d)(e1) L(e1) 4.仅由有限次使用上述三步骤而定义的表达式才是正规式。 注:（1）“*”，“”，“|”运算左结合，优先级由高到低。 （2） 可省略。 （3）不产生混乱的情况下，可将圆括号略去。 如：(r (s*)|r)=rs*|r r *(s*|r)圆括号不可略去 （4）“(”,“)”并非正规式的运算符。例3.3 =a,b(a) a|b 正规集: a,b(b) (a|b )(a|b ) 正规集: aa,ab,ba,bb(c) a* 正规集: ,a,aa,aaa,aaaa, (d)正规式：(a|b)* 正规集:,a,b,aa,ab,ba,bb,aaa, (e)正规式：a|ab* 正规集:a后跟随大于等于0个b的所有符号串。 (f)正规式：(a|b)*(aa|bb)(a|b)* 正规集: 所有含有两个相继a或b的符号串。 (g)正规式：(aa|ba|ab|bb)* 正规集: 空串和任何长度为偶数的a,b符号串。 (h)正规式：(a|b)*abb 正规集:任何以abb结尾的a,b符号串。 例：=A,B,Z,a,b,z,0,1,9 letter=A|B|Z|a|b|z L(A)L(B)L(Z)L(a)L(b).L(z)=A,B,Z,a,b,z digit=0|1|9 L(0)L(1).L(9)= 0,1,9 (A|B|Z|a|b|z) A,B,Z,a,b,z (A|B|Z|a|b|z)|(0|1|9)* (A,B,Z,a,b,z0,1,9)* 标识符 letter(letter|digit)* L(letter)(L(letter)L(digit)* 无符号数： digitdigit*(.digitdigit*|) (e(+|)digitdigit*|) 例如：2、16.8、28.9e2、26.68e-2三.正规式的代数性质 若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。 例如： e1= (a|b)， e2 = b|a 又如： e1= b(ab)* , e2 =(ba)*b e1= (a|b)* , e2 =(a*|b*)*四.正规文法与正规式的等价