编译原理复习陆筱霞

1、编译原理复习课陆筱霞陆筱霞公共邮箱：公共邮箱：zzti_密码：密码：soft_zzti第一章第一章 引引 论论源语言程序源语言程序目标语言程序目标语言程序翻译翻译程序程序翻译翻译一一. 什么是编译程序什么是编译程序q翻译程序翻译程序 把某一种语言程序把某一种语言程序( (称为称为源语言程序源语言程序) )等价地转等价地转换成另一种语言程序换成另一种语言程序( (称为称为目标语言程序目标语言程序) )的程序的程序高级语言程高级语言程序序机器语言机器语言程序程序结果结果编译编译程序程序翻译翻译运行运行一一. 什么是编译程序什么是编译程序q编译程序编译程序(compiler)(compiler) 把

2、某一种把某一种高级语言程序高级语言程序等价地转换成另一种等价地转换成另一种低级低级语言程序语言程序( (如汇编语言或机器语言程序如汇编语言或机器语言程序) )的程序的程序诊断编译程序诊断编译程序优化编译程序优化编译程序交叉编译程序交叉编译程序可变目标编译程序可变目标编译程序一一. 什么是编译程序什么是编译程序q解释程序解释程序 把源语言写的源程序作为输入，但不产生目标程序，把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身而是边解释边执行源程序本身源程序源程序结果结果解释解释程序程序解释执行解释执行二二. . 编译过程编译过程n编译程序的工作一般分为五个阶段编译程序的工作

3、一般分为五个阶段: :q词法分析词法分析q语法分析语法分析q中间代码产生中间代码产生q优化优化q目标代码产生目标代码产生1. 1. 词法分析词法分析n任务任务: : 输入源程序，对构成源程序的字符输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符串进行扫描和分解，识别出一个个单词符号。号。n依循的原则：构词规则依循的原则：构词规则n描述工具：有限自动机描述工具：有限自动机nfor i := 1 to 100 dofor i := 1 to 100 do 保留字保留字 标识符标识符 等符等符 整常数整常数 保留字保留字 整常数整常数 保留字保留字2. 2. 语法分析语法分析n任务

4、任务: :在词法分析的基础上，根据语言的语法在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。规则把单词符号串分解成各类语法单位。n依循的原则：语法规则依循的原则：语法规则n描述工具：上下文无关文法描述工具：上下文无关文法nz := x + 0.618 z := x + 0.618 * * y y 算术表达式，赋值语句算术表达式，赋值语句3. 3. 中间代码产生中间代码产生n任务任务: :对各类不同语法范畴按语言的语义进对各类不同语法范畴按语言的语义进行初步翻译。行初步翻译。n依循的原则：语义规则依循的原则：语义规则n中间代码中间代码: :三元式，四元式，树形结构等三元式，

5、四元式，树形结构等nz:=x + 0.618 z:=x + 0.618 * * y y 翻译成四元式为翻译成四元式为(1) (1) * * 0.618 y t1 0.618 y t1(2) + x t1 t2(2) + x t1 t2(3) := t2 _ z(3) := t2 _ z4. 4. 优化优化n任务：对于前阶段产生的中间代码进行加任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目工变换，以期在最后阶段产生更高效的目标代码。标代码。n依循的原则：程序的等价变换规则依循的原则：程序的等价变换规则5. 5. 目标代码产生目标代码产生n任务任务: : 把中间代码变换成

6、特定机器上的目标代把中间代码变换成特定机器上的目标代码。码。n依赖于硬件系统结构和机器指令的含义依赖于硬件系统结构和机器指令的含义n目标代码三种形式目标代码三种形式: :q绝对指令代码绝对指令代码: : 可直接运行可直接运行 q可重新定位指令代码可重新定位指令代码: : 需要连接装配需要连接装配q汇编指令代码汇编指令代码: : 需要进行汇编需要进行汇编三三. . 编译程序结构编译程序结构n编译程序总框编译程序总框四元式四元式单词符号单词符号语法单位语法单位四元式四元式目标代码目标代码词法分析器词法分析器语法分析器语法分析器语义分析与中间代码语义分析与中间代码生成器生成器优化段优化段源程序源程序

7、表表格格管管理理出出错错处处理理目标代码生成器目标代码生成器2. 2. 表格和表格管理表格和表格管理n常见的表格常见的表格: :符号名表，常数表，标号表，入符号名表，常数表，标号表，入口名表，过程引用表。口名表，过程引用表。n格式格式: : 名字信息3. 3. 出错处理出错处理n出错处理程序：出错处理程序：发现发现源程序中的源程序中的错误，把有关错误，把有关错误信息报告给用户错误信息报告给用户q语法错误语法错误q语义错误语义错误 4. 4. 遍遍(pass)(pass)n所谓所谓 遍遍 ， 就是对源程序或源程序的中间表就是对源程序或源程序的中间表示从头到尾扫描一次。示从头到尾扫描一次。n阶段与

8、遍是不同的概念。一遍可以由若干段组阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。成，一个阶段也可以分若干遍来完成。5. 编译前端与后端编译前端与后端n编译前端编译前端：与源语言有关，如词法分析，语法分：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优析，语义分析与中间代码产生，与机器无关的优化化n编译后端编译后端：与目标机有关，与目标机有关的优化，：与目标机有关，与目标机有关的优化，目标代码产生目标代码产生q优点：减少对内存容量的要求，程序逻辑结构清晰优点：减少对内存容量的要求，程序逻辑结构清晰; ; 优优化更充分，有利于移植。化更充分，有

9、利于移植。q不足不足: : 编译程序运行的效率低编译程序运行的效率低源语言源语言中间语言中间语言目标语言目标语言前端前端后端后端第二章第二章 高级语言及其语法描述高级语言及其语法描述 一一. 语法语法n程序本质上是一定字符集（称为字母表）上的字符串程序本质上是一定字符集（称为字母表）上的字符串（有限序列）。（有限序列）。n语法语法：一组规则：一组规则，用它可以形成和产生一个用它可以形成和产生一个合式合式(well-formed)的程序的程序。规则的一部分称为词法规则词法规则，另一部分称为语法规则语法规则（或产生式规则）。语语 法法n词法规则词法规则：单词符号的形成规则：单词符号的形成规则。q单

10、词符号是语言中具有独立意义的最基本结构单词符号是语言中具有独立意义的最基本结构。一般一般包括：常数、标识符、基本字、算符、界符等。包括：常数、标识符、基本字、算符、界符等。q描述工具：有限自动机描述工具：有限自动机n语法规则语法规则：语法单位的形成规则：语法单位的形成规则。q语法单位通常包括：表达式、语句、分程序、过程、语法单位通常包括：表达式、语句、分程序、过程、函数、程序等函数、程序等; ;q描述工具：上下文无关文法描述工具：上下文无关文法语义语义n语义语义：一组规则：一组规则，用它可以定义一个程序的意用它可以定义一个程序的意义义。n描述方法：描述方法：q自然语言描述：隐藏错误、二义性和不

11、完整性自然语言描述：隐藏错误、二义性和不完整性q形式描述：形式描述：f 操作语义操作语义(pl/1)(pl/1)f 指称语义指称语义(ada)(ada)f 代数语义代数语义(pascal)(pascal)2.32.3 程序语言的语法描述程序语言的语法描述 n几个概念几个概念:q考虑一个考虑一个有穷有穷 字母表字母表 字符集字符集q其中每一个元素称为一个其中每一个元素称为一个字符字符q上的上的字字(也叫也叫字符串字符串) 是指由是指由中的字符所构成的一中的字符所构成的一个有穷序列个有穷序列q不包含任何字符的序列称为不包含任何字符的序列称为空字空字，记为，记为q用用*表示表示上的所有字的全体上的所

12、有字的全体,包含空字包含空字例如: 设 =a， b，则 *=,a,b,aa,ab,ba,bb,aaa,.q 即即 是是空集空集，表示一个不含任何元素的集合。，表示一个不含任何元素的集合。n*的子集的子集u和和v的的连接连接（积积）定义为）定义为uv | u & v n设：设：u a, aa v b, bb n那么：那么：uv= ab, abb, aab, aabb nv自身的自身的 n次积记为次积记为vn=vvvn规定规定v0= ，令，令 v*=v0v1v2v3 称称v*是是v的的闭包闭包;n记记 vvv* ，称，称v+是是v的的正规闭包正规闭包。n闭包闭包v*中每个符号串都是由中每个符号串都

13、是由v中的符号串经中的符号串经有限次连接而成的。有限次连接而成的。2.3.1 2.3.1 上下文无关文法上下文无关文法n文法文法： 描述语言的语法结构的形式规则描述语言的语法结构的形式规则n上下文无关文法的定义：上下文无关文法的定义： 一个上下文无关文法一个上下文无关文法g g是一个四元式是一个四元式 g=(vg=(vt t，v vn n，s s，p)p)，其中，其中qv vt t：终结符集合：终结符集合( (非空非空) )qv vn n：非终结符集合：非终结符集合( (非空非空) )，且，且v vt t v vn n= =qs s：文法的开始符号，：文法的开始符号，s s v vn nqp

14、p：产生式集合：产生式集合( (有限有限) )，每个产生式形式为，每个产生式形式为p p， p p v vn n， ( (v vt t v vn n) )* *q开始符开始符s s至少必须在某个产生式的左部出现一次。至少必须在某个产生式的左部出现一次。n定义：称定义：称 a 直接推出直接推出，即，即 a 仅当仅当a 是一个产生式，是一个产生式， 且且 ， (vt vn)* 。n如果如果 1 2 n，则我们称这个序列，则我们称这个序列是从是从 1到到 n的一个的一个推导推导。若存在一个从。若存在一个从 1到到 n的推导，则称的推导，则称 1可以可以推导推导出出 n 。n对文法对文法g(e)： e

15、 i | e+e | e*e | (e)e (e) (e+e) (i+e) (i+i)n通常，用通常，用 表示：从表示：从 1 1出发，经过一出发，经过一步或若干步，可以推出步或若干步，可以推出 n n。n1n*1 用用 表示：从表示：从 1 1出发，经过出发，经过0 0步或步或若干步，可以推出若干步，可以推出 n n。q定义：假定定义：假定g g是一个文法，是一个文法，s s 是它的开始符号。是它的开始符号。如果如果 ，则，则 称是一个称是一个句型句型。仅含终结符。仅含终结符号的句型是一个号的句型是一个句子句子。文法。文法g g所产生的句子的全所产生的句子的全体是一个体是一个语言语言，将它记

16、为，将它记为 l(g)l(g)。*s ,|)(*tv sgl* 所以所以 ： 即即 或或n从一个句型到另一个句型的推导往往不唯一。从一个句型到另一个句型的推导往往不唯一。 e+ei+ei+i e+ee+ii+in最左推导最左推导：任何一步：任何一步 都是对都是对 中的中的最左最左非终结符非终结符进行替换。进行替换。 最右推导最右推导：任何一步：任何一步 都是对都是对 中的中的最右最右非终结符非终结符进行替换。进行替换。 规范推导、规范规约规范推导、规范规约n定义定义：如果一个文法存在某个句子对应两颗如果一个文法存在某个句子对应两颗不同的语法树不同的语法树，则说这个则说这个文法是二义的文法是二义

17、的。g(e)： e i|e+e|e*e|(e) 是二义文法。是二义文法。n语言的二义性：一个语言的二义性：一个语言是二义性的语言是二义性的，如果，如果对它不存在无二义性的文法。对它不存在无二义性的文法。q可能存在可能存在g和和g，一个为二义的，一个为无二义，一个为二义的，一个为无二义的。但的。但l(g)=l(g)n二义性问题是不可判定问题，即不存在一个二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。文法是否是二义的。n可以找到一组无二义文法的充分条件。可以找到一组无二义文法的充分条件。2.3.3 2.3.3 形

18、式语言鸟瞰形式语言鸟瞰nchomsky于于1956年建立形式语言体系，年建立形式语言体系，他把文法分成四种类型：他把文法分成四种类型：0，1，2，3型。型。0型型(短语文法，图灵机短语文法，图灵机)： 产生式形如：产生式形如： 其中：其中： (vt vn)*且至少含有一个非终结符；且至少含有一个非终结符； (vt vn)*1型型(上下文有关文法，线性界限自动机上下文有关文法，线性界限自动机)： 产生式形如：产生式形如： 其中：其中：| | | |，仅，仅 s 例外。例外。2型型(上下文无关文法，非确定下推自动机上下文无关文法，非确定下推自动机)： 产生式形如：产生式形如： a 其中：其中：a

19、vn； (vt vn)*。3型型(正规文法，有限自动机正规文法，有限自动机)： 产生式形如：产生式形如： a b 或或 a 其中：其中： vt*；a，b vn 产生式形如：产生式形如： a b 或或 a 其中：其中： vt*；a，b vn右线性文法右线性文法左线性文法左线性文法第三章第三章 词法分析词法分析n词法分析的任务：从左至右逐个字符地对词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。源程序进行扫描，产生一个个单词符号。n词法分析器词法分析器(lexical analyzer) 又称扫描器又称扫描器(scanner)：执行词法分析的程序：执行词法分析的程序3.13

20、.1 对于词法分析器的要求对于词法分析器的要求一、词法分析器的功能和输出形式一、词法分析器的功能和输出形式n功能功能: :输入源程序、输出单词符号输入源程序、输出单词符号n单词符号的种类：单词符号的种类：q基本字基本字( (保留字保留字) )：如：如 beginbegin，repeatrepeat，q标识符标识符表示各种名字：如变量名、数组名表示各种名字：如变量名、数组名和过程名和过程名q常数常数：各种类型的常数：各种类型的常数q运算符运算符：+ +，- -，* *，/ /，q界符界符：逗号、分号、括号和空白：逗号、分号、括号和空白n输出的单词符号的表示形式输出的单词符号的表示形式: :( (

21、单词种别单词种别，单词自身的值单词自身的值) )n单词种别通常用整数编码表示。单词种别通常用整数编码表示。q若一个种别只有一个单词符号，则种别编码就若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符代表该单词符号。假定基本字、运算符和界符都是一符一种。都是一符一种。q若一个种别有多个单词符号，则对于每个单词若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值符号，给出种别编码和自身的值( (单词符号的属单词符号的属性信息性信息) )。n标识符单列一种；标识符自身的值表示成按机器标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。字节划分的内

22、部码。n常数按类型分种；常数的值则表示成标准的二进常数按类型分种；常数的值则表示成标准的二进制形式。制形式。三三、状态转换图状态转换图1 1 概念概念n状态转换图是一张有限方向图。状态转换图是一张有限方向图。213xy结点代表状态，用圆圈表示结点代表状态，用圆圈表示。状态之间用箭弧连结，箭弧状态之间用箭弧连结，箭弧上的标记上的标记( (字符字符) )代表射出结代表射出结状态下可能出现的输入字符状态下可能出现的输入字符或字符类。或字符类。一张转换图只包含有限个状态，其中一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。有一个为初态，至少要有一个终态。识别标识符的状态转换图识别标识符

23、的状态转换图123字母字母其他其他字母或数字字母或数字*识别识别整常数整常数的状态转换图的状态转换图123数字数字其他其他数字数字*n一个状态转换图可用于识别一个状态转换图可用于识别( (或接受或接受) )一定的一定的字符串。字符串。单词的描述工具单词的描述工具 程序设计语言中的单词是基本语法程序设计语言中的单词是基本语法成分。单词符号的语法可以用有效的工成分。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造。实现词法分析程序的自动构造。 正规表达式是典型的词法规则描述正规表达式是典型的词法规则描述工具。工具。3.3.1

24、 正规式和正规集正规式和正规集n正规集正规集可以用可以用正规表达式正规表达式（简称（简称正规式正规式）表）表示。示。n正规表达式正规表达式是表示是表示正规集正规集一种方法。一个字一种方法。一个字集合是集合是正规集正规集当且仅当它能用当且仅当它能用正规式正规式表示。表示。正规式也称正则表达式（正规式也称正则表达式（regular expression），），是说明单词的模式是说明单词的模式(pattern)的一种重要的表示法的一种重要的表示法（记号），是定义正规集的数学工具。我们用（记号），是定义正规集的数学工具。我们用以描述单词符号。以描述单词符号。n正规式和正规集的递归定义：正规式和正规集的

25、递归定义：对给定的字母表对给定的字母表 1) 和和都是都是 上的正规式，它们所表示的正规集为上的正规式，它们所表示的正规集为 和和;2) 任何任何a ，a是是 上的正规式，它所表示的正规上的正规式，它所表示的正规集为集为a ;3) 假定假定e1和和e2都是都是 上的正规式，它们所表示的正规上的正规式，它们所表示的正规集为集为l(e1)和和l(e2)，则，则i) (e1|e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为l(e1) l(e2)，ii) (e1.e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为l(e1)l(e2)，iii) (e1)*为正规式，它所表示的正

26、规集为为正规式，它所表示的正规集为(l(e1)*，仅由仅由有限次有限次使用上述三步骤而定义的表达式才是使用上述三步骤而定义的表达式才是 上的正规式，仅由这些正规式表示的字集才是上的正规式，仅由这些正规式表示的字集才是 上的正规集。上的正规集。n所有词法结构一般都可以用正规式描述。所有词法结构一般都可以用正规式描述。n若两个正规式所表示的正规集相同，则称这若两个正规式所表示的正规集相同，则称这两个正规式等价。如两个正规式等价。如b(ab)*=(ba)*b(a*b*)*=(a|b)* l( (ba)*b) = l(ba)*) l(b)= (l(ba)*l(b) = (l(b)l(a)* l(b)

27、= ba* b = , ba, baba, bababa, b= b, bab, babab, bababab, l(b(ab)*) = l(b)l(ab)*) = l(b) (l(ab)*= l(b) (l(a)l(b)*=b ab* = b , ab, abab, ababab, = b, bab, babab, bababab, l(b(ab)*)= l( (ba)*b) b(ab)*=(ba)*b3.3.2 确定有限自动机确定有限自动机(dfa)n对状态图进行形式化，则可以下定义：对状态图进行形式化，则可以下定义：自动机自动机m是一个五元式是一个五元式m=(s, , f, s0, f)

28、,其中：其中：1. s: 有穷状态集，有穷状态集，2. ：输入字母表：输入字母表(有穷有穷)，3. f: 状态转换函数，为状态转换函数，为ss的的单值单值部分映射，部分映射，f(s，a)=s表示：当现行状态为表示：当现行状态为s，输入字符为输入字符为a时，将时，将状态转换到下一状态状态转换到下一状态s。我们把。我们把s称为称为s的一个后继的一个后继状态。状态。4. s0 s是唯一的一个初态；是唯一的一个初态； 5 f s ：终态集：终态集(可空可空)。ndfa可以表示为状态转换图。假定可以表示为状态转换图。假定dfa m含含有有m个状态和个状态和n个输入字符，那么，这个图含个输入字符，那么，这

29、个图含有有m个状态结点，每个结点顶多含有个状态结点，每个结点顶多含有n条箭弧条箭弧射出，且每条箭弧用射出，且每条箭弧用上的不同的输入字符上的不同的输入字符来作标记。来作标记。n对于对于 * *中的任何字中的任何字 ，若存在一条从初态到，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标某一终态的道路，且这条路上所有弧上的标记符连接成的字等于记符连接成的字等于 ，则称，则称 为为dfa m所所识识别别(接收接收)ndfa m所识别的字的全体记为所识别的字的全体记为l(m)。n可以证明：可以证明： 上的字集上的字集v v* *是正规集，当且是正规集，当且仅当存在上的仅当存在上的dfa m，使

30、得，使得vl(m)。3.3.3 3.3.3 非确定有限自动机非确定有限自动机(nfa) n定义：一个非确定有限自动机定义：一个非确定有限自动机(nfa) m是一是一个五元式个五元式m=(s, m=(s, , , f, s, s0 0, f), f)，其中：，其中：1 s: 有穷状态集；有穷状态集；2 ：输入字母表：输入字母表(有穷有穷)；3 f: 状态转换函数，为状态转换函数，为s*2s的部分映射的部分映射(非单值非单值)；4 s s0 0 s s是非空的初态集；是非空的初态集；5 f s s ：终态集：终态集(可空可空)。n从状态图中看从状态图中看nfa 和和dfa的区别：的区别： 1 弧上

31、的标记可以是弧上的标记可以是 *中的一个字，而不一中的一个字，而不一定是单个字符；定是单个字符； 2 同一个字可能出现在同状态射出的多条弧同一个字可能出现在同状态射出的多条弧上。上。ndfa是是nfa的特例。的特例。1. 假定假定nfa m=，我们对，我们对m的状的状态转换图进行以下改造：态转换图进行以下改造： 1) 引进新的初态结点引进新的初态结点x和终态结点和终态结点y，x,y s， 从从x到到s0中中任意任意状态结点连一条状态结点连一条 箭弧箭弧， 从从f中中任任意意状态结点连一条状态结点连一条 箭弧到箭弧到y。 2) 对对m的状态转换图进一步施行的状态转换图进一步施行替换替换，其中，其

32、中k是新引是新引入的状态。入的状态。证明证明:加入新初态和新终态的目的是让转换图中初态和终态唯一。任意表示状态集合中的所有节点都应该与新加入节点间有 弧相连。代之为代之为ikabjijab代之为代之为ija|bijba代之为代之为ija*ik ja按下面的三条规则对按下面的三条规则对v进行分裂进行分裂:n逐步把这个图转变为每条弧只标记为逐步把这个图转变为每条弧只标记为 上的一上的一个字符或个字符或 ，最后得到一个，最后得到一个nfa m，显然，显然l(m)=l(m)2. 把上述把上述nfa确定化确定化采用子集法采用子集法.设设i是的状态集的一个子集，定义是的状态集的一个子集，定义i的的 -闭包

33、闭包 -closure(i)为为: i) 若若s i，则，则s-closure(i)； ii) 若若s i，则从则从s出发经过出发经过任意条任意条 弧弧而能到而能到达的任何状态达的任何状态s都属于都属于 -closure(i) 即即 -closure(i)=i s|从某个从某个s i出发经过出发经过任意任意条条 弧弧能到达能到达sn设设a是是 中的一个字符，定义中的一个字符，定义ia= -closure(j) 其中，其中，j为为i中的某个状态出发经过中的某个状态出发经过一条一条a弧弧而到达的状态集合。而到达的状态集合。n确定化的过程确定化的过程: : 不失一般性，设字母表只包含两个不失一般性，

34、设字母表只包含两个a a和和b b，我们构造一张表我们构造一张表: :iiaib -closure(x)首先，置首先，置第第1行第行第1列为列为 -closure(x)求出求出这一列的这一列的ia，ib；然后，检查这两个然后，检查这两个ia，ib，看它们是否已在，看它们是否已在表中的第一列中出现，把未曾出现的填入表中的第一列中出现，把未曾出现的填入后面的空行的第后面的空行的第1列上，求出每行第列上，求出每行第2，3列列上的集合上的集合.重复上述过程，知道所有第重复上述过程，知道所有第2，3列子集全列子集全部出现在第一列为止。部出现在第一列为止。n现在把这张表看成一个状态转换矩阵，把其现在把这张

35、表看成一个状态转换矩阵，把其中的中的每个子集看成一个状态每个子集看成一个状态。n这张表唯一刻划了一个确定的有限自动机这张表唯一刻划了一个确定的有限自动机m，它的初态是它的初态是 -closure(x) ，它的终态是含，它的终态是含有原终态有原终态y的子集。的子集。n不难看出，这个不难看出，这个dfa m与与m等价。等价。3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性n定理：定理： 1.对每一个右线性正规文法对每一个右线性正规文法g或左线性正规或左线性正规文法文法g，都存在一个有限自动机，都存在一个有限自动机(fa) m，使，使得得l(m)l(g)。 2.对每一个对每一个f

36、a m，都存在一个右线性正规文，都存在一个右线性正规文法法gr和左线性正规文法和左线性正规文法gl，使得，使得l(m)l(gr)l(gl)。n 了解转换过程了解转换过程 ： 1. 1. 对每一个右线性正规文法对每一个右线性正规文法g或左线性正规或左线性正规文法文法g，都构造一个有限自动机（，都构造一个有限自动机（fa） m，使得使得l(m)l(g)。(1) 设右线性正规文法设右线性正规文法g=。将。将vn中的每一非终结符号视为状态符号，并中的每一非终结符号视为状态符号，并增加增加一个新的终结状态符号一个新的终结状态符号f，f vn。 令令m=，其中，其中状态转换状态转换函数函数 由以下规则定义

37、：由以下规则定义：(a) 若对某个若对某个a vn及及a vt ，p中有产生中有产生式式aa，则令，则令 (a,a)=f(b) 对任意的对任意的a vn及及a vt ，设，设p中左端中左端为为a，右端第一符号为，右端第一符号为a的所有产生式为：的所有产生式为：aaa1|aak （不包括（不包括aa），）， 则令则令 (a,a)=a1,ak。 显然，上述显然，上述m是一个是一个nfa。对于右线性正规文法对于右线性正规文法g，在，在s w的最左推导过的最左推导过程中程中:利用利用aab一次就相当于在一次就相当于在m中从状态中从状态a经过标经过标记为记为a的箭弧到达状态的箭弧到达状态b（包括（包括a

38、= 的情形）的情形）;在推导的最后，利用在推导的最后，利用aa一次则相当于在一次则相当于在m中中从状态从状态a经过标记为经过标记为a的箭弧到达终结状态的箭弧到达终结状态f（包（包括括a= 的情形）。的情形）。综上，在正规文法综上，在正规文法g中，中，s w的充要条件是：的充要条件是：在在m中，从状态中，从状态s到状态到状态f有一条通路，其上所有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于有箭弧的标记符号依次连接起来恰好等于w，这就是说，这就是说，w l(g)当且仅当当且仅当w l(m)，故，故l(g)l(m)。(2) 设左线性正规文法设左线性正规文法g=。将。将vn中中的每一符号视为状

39、态符号，并增加一个初始的每一符号视为状态符号，并增加一个初始状态符号状态符号q0，q0 vn。 令令m=，其中，其中状态转状态转换函数换函数 由以下规则定义由以下规则定义：(a) 若对某个若对某个a vn及及a vt ，若，若p中有产生中有产生式式aa，则令，则令 (q0,a)=a(b) 对任意的对任意的a vn及及a vt ，若，若p中所有右中所有右端第一符号为端第一符号为a，第二个符号为，第二个符号为a的产生式为：的产生式为：a1aa, , akaa， 则令则令 (a,a)=a1,ak。与与(1)类似，可以证明类似，可以证明l(g)l(m)。3.3.5 3.3.5 正规式与有限自动机的等价

40、性正规式与有限自动机的等价性n定理：定理： 1. 对任何对任何fa m，都存在一个正规式，都存在一个正规式r，使得，使得l(r)=l(m)。 2. 对任何正规式对任何正规式r，都存在一个，都存在一个fa m，使得，使得l(m)=l(r)。2对转换图概念拓广，令每条弧可用一个正对转换图概念拓广，令每条弧可用一个正规式作标记。规式作标记。(对一类输入符号对一类输入符号)n证明：证明： 1 1 对对 上任一上任一nfa m，构造一个，构造一个 上的正规式上的正规式r，使得使得l(r)=l(m)。q首先，在首先，在m的转换图上加进两个状态的转换图上加进两个状态x和和y，从，从x用用 弧连接到弧连接到m

41、的所有初态结点，从的所有初态结点，从m的所有终态的所有终态结点用结点用 弧连接到弧连接到y，从而形成一个新的，从而形成一个新的nfa，记，记为为m，它只有一个初态，它只有一个初态x和一个终态和一个终态y，显然，显然l(m)=l(m)。q然后，反复使用下面的一条规则，逐步消去的所然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下有结点，直到只剩下x和和y为止；为止；代之为代之为ijr1r2kikr1r2代之为代之为ijr1|r2ijr2r1代之为代之为ikr1r2*r3ijr1r3kr2n对一个对一个dfa m最少化的基本思想最少化的基本思想: 把把m的状态集划分为一些不相交的子集，使

42、的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状让每个子集选出一个代表，同时消去其他状态。态。n具体做法具体做法: 对对m的状态集进行划分的状态集进行划分q首先，把首先，把s划分为终态和非终态两个子集，形成划分为终态和非终态两个子集，形成基本划分基本划分 。 q假定到某个时候，假定到某个时候， 已含已含m个子集，记为个子集，记为 =i(1)，i(2)，i(m)，检查，检查 中的每个子集看是否能进中的每个子集看是否能进一步

43、划分一步划分:n对某个对某个i(i)，令，令i(i)=s1,s2, ,sk，若存在一个，若存在一个输入字符输入字符a使得使得ia(i) 不会包含在现行不会包含在现行 的某个子的某个子集集i(j)中，则至少应把中，则至少应把i(i)分为两个部分。分为两个部分。自上而下分析自上而下分析第四章第四章 语法分析语法分析4.1 语法分析器的功能语法分析器的功能n语法分析的任务是分析一个文法的语法分析的任务是分析一个文法的句子结句子结构构。n语法分析器的功能：按照文法的产生式语法分析器的功能：按照文法的产生式( (语语言的语法规则言的语法规则) )，识别输入符号串是否为一识别输入符号串是否为一个句子个句子

44、( (合式程序合式程序) )。4.2 自上而下分析面临的问题自上而下分析面临的问题n自上而下就是从文法的开始符号出发，向下自上而下就是从文法的开始符号出发，向下推导推导，推出句子。，推出句子。q带带“回溯回溯”的的q不带回溯的递归子程序不带回溯的递归子程序( (递归下降递归下降) )分析方法。分析方法。n自上而下分析的主旨：对任何输入串，试图自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号用一切可能的办法，从文法开始符号( (根结点根结点) )出发，自上而下地为输入串建立一棵出发，自上而下地为输入串建立一棵语法语法树树。或者说，为输入串寻找一个最左推导。或者说，为输入串寻

45、找一个最左推导。n当某个非终结符有多个产生式候选时，可能当某个非终结符有多个产生式候选时，可能带来如下问题带来如下问题: :1. 1. 分析过程中，当一个非终结符用某一个候选匹配分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的成功时，这种匹配可能是暂时的。出错出错时，不得时，不得不不“回溯回溯”。2. 2. 文法左递归问题文法左递归问题。一个文法是含有左递归的，如一个文法是含有左递归的，如果存在非终结符果存在非终结符p ppp 含有左递归的文法将使自上而下的分含有左递归的文法将使自上而下的分析陷入无限循环。析陷入无限循环。n结论结论n左递归和回溯问题的产生直接与描述语言左

46、递归和回溯问题的产生直接与描述语言的文法有关。的文法有关。n因此，要对文法进行确定的自顶向下分析因此，要对文法进行确定的自顶向下分析应该改造文法，使其不含左递归和回溯。应该改造文法，使其不含左递归和回溯。4.3.1 左递归的消除左递归的消除n直接消除见诸于产生式中的左递归：假定直接消除见诸于产生式中的左递归：假定关于非终结符关于非终结符p的规则为的规则为pp | 其中其中 不以不以p开头。开头。 我们可以把我们可以把p的规则等价地改写为如下的非的规则等价地改写为如下的非直接左递归形式：直接左递归形式：p p p p | 左递归变右递归n一般而言，假定一般而言，假定p关于的全部产生式是关于的全部

47、产生式是pp 1 | p 2 | | p m | 1 | 2| n其中，每个其中，每个 都不等于都不等于 ，每个，每个 都不以都不以p开头开头 那么，消除那么，消除p的直接左递归性就是把这些规则的直接左递归性就是把这些规则改写成：改写成： p 1p | 2p | | np p 1p | 2p | | mp | 左递归变右递归n消除左递归的算法消除左递归的算法:1. 把文法把文法g的所有非终结符按任一种顺序排列成的所有非终结符按任一种顺序排列成p1，p2，pn；按此顺序执行；按此顺序执行；2. for i:=1 to n do begin for j:=1 to i-1 do 把形如把形如pip

48、j 的规则改写成的规则改写成 pi 1 | 2 | k ; (其中其中pj 1| 2| k是关于是关于pj的所有规则的所有规则) 消除关于消除关于pi规则的直接左递归性规则的直接左递归性 end3. 化简由化简由2所得的文法。去除那些从开始符号出发永远无法所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。到达的非终结符的产生规则。4.3.2 消除回溯、提左因子消除回溯、提左因子n为了消除回溯就必须保证：对文法的任何为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的根据它所面临的输入符

49、号准确地指派它的一个候选去执行任务，并且此候选的工作一个候选去执行任务，并且此候选的工作结果应是确信无疑的。结果应是确信无疑的。na 1 | 2 | | nsa.ipa.n令令g是一个不含左递归的文法，对是一个不含左递归的文法，对g的所有非终的所有非终结符的每个候选结符的每个候选 定义它的终结首符集定义它的终结首符集first( )为：为：.,|=)(*tvaaafirst 特别是，若特别是，若 ，则规定，则规定first( )。* 如果非终结符如果非终结符a的所有候选首符集两两不相交，即的所有候选首符集两两不相交，即a的任何两个不同候选的任何两个不同候选 i和和 jfirst( i)firs

50、t( j) 当要求当要求a匹配输入串时，匹配输入串时，a就能根据它所面临的第一就能根据它所面临的第一个输入符号个输入符号a，准确地指派某一个候选前去执行任，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含务。这个候选就是那个终结首符集含a的的 。n提取公共左因子提取公共左因子: 假定关于假定关于a的规则是的规则是 a 1 | 2 | | n | 1 | 2 | | m (其中，每个其中，每个 不以不以 开头开头) 那么，可以把这些规则改写成那么，可以把这些规则改写成a a | 1 | 2 | | ma 1 | 2 | | nn经过反复提取左因子，就能够把每个非终结经过反复提取左因

51、子，就能够把每个非终结符符(包括新引进者包括新引进者)的所有候选首符集变成为的所有候选首符集变成为两两不相交。两两不相交。n当当a a面临输入符面临输入符a a时时, , 若若a a first(a)first(a)且且first(a), first(a), 则则考虑考虑自动匹配问题自动匹配问题。n 对于上述算术表达式文法对于上述算术表达式文法, ,若输入串为若输入串为i/i, i/i, 即使让即使让tt自动匹配自动匹配, “/”, “/”仍不能与后面符仍不能与后面符号匹配号匹配, , 此时没必要让此时没必要让tt自动匹配。自动匹配。 结论结论: : 只有在只有在当前输入符当前输入符能与能与a

52、 a后的第后的第一个终结符一个终结符匹配成功时匹配成功时, ,才让才让a a自动得到自动得到匹配。这就要求分析前先求出紧跟在匹配。这就要求分析前先求出紧跟在a a后的终结符后的终结符, , 即即follow(a)follow(a)。 n假定假定s是文法是文法g的开始符号，对于的开始符号，对于g的任何非的任何非终结符终结符a，我们定义，我们定义.,.|)(*tvaaasaafollowas*特别是，若特别是，若 ，则规定，则规定 follow(a)4.3.3 ll(1)分析条件分析条件即即follow(a)是是所有句型所有句型中紧跟在中紧跟在a之后的之后的终结符终结符 或或 # 。自动匹配条件自

53、动匹配条件 当当 a 面 临 输 入 符面 临 输 入 符 a 时时 , 若若 a f i r s t ( a ) 且且first(a), 则只有当则只有当a follow(a)时时,才使才使a自自动得到匹配。缺少任一条件动得到匹配。缺少任一条件,均不自动匹配。均不自动匹配。 若输入符若输入符a first(a)且且a follow(a), 则当则当first(a)时仍可能需进行试探时仍可能需进行试探(回溯回溯)。因此。因此,对对于于存在存在 -生成式生成式的非终结符的非终结符a,若要进行不带回溯的若要进行不带回溯的自上而下分析自上而下分析,则则first(a)与与follow(a)应互不应互

54、不相交相交。n构造不带回溯的自上而下分析的文法条件构造不带回溯的自上而下分析的文法条件1. 文法不含左递归，文法不含左递归，2. 对于文法中每一个非终结符对于文法中每一个非终结符a的各个产生式的的各个产生式的候选首符集两两不相交。即，若候选首符集两两不相交。即，若a 1| 2| n 则则 first( i)first( j) (i j)3. 对文法中的每个非终结符对文法中的每个非终结符a，若它存在某个候，若它存在某个候选首符集包含选首符集包含 ，则，则first( i)follow(a)= i=1,2,.,n如果一个文法如果一个文法g满足以上条件，则称该文法满足以上条件，则称该文法g为为ll(

55、1)ll(1)文法文法。n对于一个满足上述条件的文法，可以对其输入对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要串进行有效的无回溯的自上而下分析。假设要用非终结符用非终结符a进行匹配，面临的输入符号为进行匹配，面临的输入符号为a，a的所有产生式为的所有产生式为a 1 | 2 | | n1. 若若a first( i)，则指派，则指派 i执行匹配任务；执行匹配任务；2. 若若a不属于任何一个候选首符集，则：不属于任何一个候选首符集，则： (1) 若若 属于某个属于某个first( i )且且 a follow(a)， 则让则让a与与 自动匹配。自动匹配。 (2)

56、 否则，否则，a的出现是一种语法错误。的出现是一种语法错误。n对每一文法符号对每一文法符号x vtvn构造构造first(x) 连续使用下面的规则连续使用下面的规则，直至每个集合，直至每个集合first不不再增大为止：再增大为止：1. 若若x vt，则，则first(x)x。2. 若若x vn，且有产生式，且有产生式xa，则把，则把a加入到加入到first(x)中；若中；若x 也是一条产生式，则把也是一条产生式，则把 也加也加到到first(x)中。中。3. l若若xy是一个产生式且是一个产生式且y vn，则把，则把first(y)中的所有非中的所有非 -元素都加到元素都加到first(x)中

57、；中；l若若xy1y2yk是一个产生式，是一个产生式，y1，yi-1都是都是非终结符，而且，对于任何非终结符，而且，对于任何j，1 j i-1，first(yj)都含有都含有 (即即y1yi-1 )， 则把则把first(yi)中的所有非中的所有非 -元素都加到元素都加到first(x)中；特别是，中；特别是，若所有的若所有的first(yj)均含有均含有 ，j1，2，k，则把则把 加到加到first(x)中。中。n对于文法对于文法g的每个非终结符的每个非终结符a构造构造follow(a)的办法的办法是，连续使用下面的规是，连续使用下面的规则，直至每个则，直至每个follow不再增大为止：不再

58、增大为止：1. 对于文法的开始符号对于文法的开始符号s，置于，置于follow(s)中；中；2. 若若a b 是一个产生式，则把是一个产生式，则把first( ) 加加至至follow(b)中；中；3. 若若a b是一个产生式，或是一个产生式，或ab 是一个产生是一个产生式而式而 (即即first( )， 则把则把follow(a)加至加至follow(b)中。中。4.4 4.4 递归下降分析程序构造递归下降分析程序构造n递归下降分析法也称递归子程序法，是一种直递归下降分析法也称递归子程序法，是一种直观易于构造的自顶向下分析方法。分析过程则观易于构造的自顶向下分析方法。分析过程则通过自上而下一

59、级一级地调用子程序来实现，通过自上而下一级一级地调用子程序来实现，所以称为所以称为递归下降分析法递归下降分析法n思想思想: :对文法中的每个对文法中的每个非终结符非终结符编写一个处理编写一个处理子程序，处理子程序的代码结构由相应的非终子程序，处理子程序的代码结构由相应的非终结符的规则结符的规则右部右部来决定：规则右部的终结符号来决定：规则右部的终结符号与输入符号相匹配，非终结符与相应的子程序与输入符号相匹配，非终结符与相应的子程序调用相对应，非终结符对应的各个候选式与分调用相对应，非终结符对应的各个候选式与分支结构相对应。支结构相对应。n构造不带回溯的自上而下分析器构造不带回溯的自上而下分析器

60、n分析程序由一组递归过程组成，文法中每个分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。序称为递归下降分析器。( (因为文法的定义因为文法的定义通常是递归的通常是递归的) )n几个全局过程和变量：几个全局过程和变量：qadvance，把输入串指示器，把输入串指示器ip指向下一个输入指向下一个输入符号，即读入一个单字符号符号，即读入一个单字符号qsym，ip当前所指的输入符号当前所指的输入符号qerror，出错处理子程序，出错处理子程序n每个非终结符有对应的子程序的定义，首每个非终结符有对应的子程序的定义，首