1、编译原理编译原理简介 编译程序(Compiler)是计算机的重要系统软件，是高级程序设计语言的支撑基础。本书主要介绍设计和构造编译程序的基本原理和方法。本书共分14章。第1章讲述编译程序的功能、结构、工作过程、组织方式、编译程序与高级语言的关系以及编译自动化方面的基本知识。第2章介绍形式语言理论，我们仅仅给出了便于理解、有助于研究各种分析方法和设计构造编译程序的形式语言理论，并着重介绍了上下文无关文法。有穷自动机是描述词法的有效工具，也是进行词法分析的主要理论基础。因此，第3章专门讨论有穷自动机，它与正规文法、正规表达式之间的对应关系以及它的确定化和最小化方面的知识，略去了像Turing机及可
2、计算性理论方面的内容。第4章讨论词法分析的功能和词法分析程序的设计方法。上下文无关文法可用于描述现今大多数高级程序设计语言的语法，也是语法分析的主要理论支柱。为此，在接下来的几章里，主要讨论了与上下文无关文法相关的各类语法分析方法。第5章介绍自上而下分析方法，包括LL(k)文法、LL(1)分析方法和应用十分广泛的递归下降分析方法。第6章讨论自下而上分析方法的一般原理和优先分析方法，包括简单优先分析技术和算符优先分析方法。第7章专门讨论自下而上的LR(k)分析方法，包括LR(0)、SLR(1)、规范LR(1)以及LALR分析表的构造算法。第8章介绍语法制导翻译方法，主要讨论了SDTS的基本原理、
3、属性翻译文法以及它们在中间代码生成中的应用。第9章讨论运行时的存储组织与管理，其中考虑了一些重要的语言特征，如过程调用、参数传递、数组和记录的存取方式以及多种存储分配技术。第10章讨论符号表的组织和存取符号表的各种方法。第11章介绍常用的优化方法。第12章简单讨论代码生成的原理。第一章 引论 本章主要介绍为什么需要编译程序以及编译程序的功能、体系结构、工作过程、组织方式，编译程序与高级程序设计语言的关系，以及编译自动化和并行编译程序等方面的基本知识。1.1 翻译程序1.1.1 程序设计语言 介绍了程序设计语言的发展1.1.2 翻译语言 翻译程序将高级语言编写的程序翻译成机器语言程序。翻译有两种
4、方式，一种是编译方式，另一种是解释方式。源 程 序编译程序(编译即翻译)目标程序初始数据系统子程序(运行)结 果编译方式 源 程 序解释程序(边翻译边执行)运行结果解释方式1.2 为什么要有编译程序编译程序有以下五个特点：v 模块性v 静态解释和动态解释v 机器无关性v 语言标准化v 程序语言特性1.3 编译程序的工作过程编译程序工作过程源程序分析综合符号表常数表中间语言程序目标程序1.3.1 分析 词法分析：词法分析是编译过程的基础，其任务是扫描源程序，根据语言的词法规则，分解和识别出每个单词，构造符号表、常数表以及将源程序转换成中间语言程序。语法分析：语法分析是在词法分析的基础上进行，其主
5、要任务是根据语言的语法规则检查源程序是否合乎语法。语义分析：语义分析进一步检查合法程序结构的语义正确性，其目的是保证标识符和常数的正确使用，把必要的信息收集、保存到符号表或中间代码程序中，并进行相应的处理。1.3.2 综合 存贮分配：主要任务是为程序和数据分配运行时的存贮单元。中间代码优化：中间代码优化通过调整和改变中间代码中某些操作的次序，以最终产生更加高效的目标代码（目标程序）。目标代码生成：这是编译程序的最后阶段。如果编译程序采用了中间代码，那么，目标代码生成阶段的任务则是将中间代码或优化之后的中间代码转换为等价的目标代码，即机器指令或汇编指令。1.4 编译程序的结构编译程序结构 源程序
6、目标程序出错处理符号表、常数表、中间语言程序词法分析语法分析语义分析代码优化代码生成1.4 编译程序的结构 编译过程还可采用“分遍”的形式，即编译过程可以由一遍或多遍编译程序来完成。对于源程序或中间代码程序，从头至尾扫描一次并完成所规定的工作称为一遍。在一遍中，可以完成一个或相连几个逻辑步骤的工作。例如，可以把词法分析作为第一遍；语法分析和语义分析作为第二遍；代码优化和存储分配作为第三遍；代码生成作为第四遍：从而构成一个四遍扫描的编译程序。1.5 编译程序的组织方式 如果宿主机的内存空间有限，则需要外存辅助，这种情况下，编译程序可以按照下面的方式组织。首先在内存中开辟三个覆盖区（共享区）：一个
7、存放最大的Comp1；一个存放输入对象（扫描对象）；一个存放加工结果（部分处理结果）。然后在外存开辟编译程序的暂存区和输入对象/加工结果的存放区。并且由“编译总控程序”负责控制和调度编译程序的各遍。外存内存编译总控Comp1扫描对象部分处理结束Comp1Comp2Compn加工结 果输入对 象 覆盖编译程序组织方式 1.6 编译程序的其他有关技术 v 编译程序的自展技术 v 编译程序的移植 v 编译程序的自动化 v 程序的可再入性 编译程序的自展技术 按照自展技术，需要把源语言L分解成一个核心部分L0与扩充部分L1，L2，Ln。分解源语言之后，先用汇编语言或机器语言编写L0的编译程序，然后再用
8、L0编写L1的编译程序，用Li编写Li+1的编译程序（i=1,2,n1），像滚雪球一样，愈滚愈大，最后得到源语言L的编译程序。编译程序的移植 编译程序可以通过移植得到，即可以将一个机器（宿主机）上的一个具有自编译性的高级语言编译程序搬迁到另一个机器（目标机）上。而可移植性则是对这种搬迁过程中难易过程的一种度量。如果工作量不大，则可称该程序是可移植的；若移植一个程序的开销远远低于最初研制该程序的开销，那么这种程序就是高度可移植的。编译程序的自动化v在编译程序自动化进程中，开发早且应用广泛的是词法分析程序生成器和语法分析程序生成器。v词法分析程序生成器：LEX（详见第13章）。它输入的是正规表达式
9、，输出的是词法分析程序。LEX的基本思想是由正规表达式构造有穷自动机。v语法分析程序生成器：基于LALR（1）文法的YACC（Yet Another Compiler Compiler）（详见第14章）。它接受LALR（1）文法，生成一个相应的LALR（1）分析表以及一个LALR（1）分析器，而且，YACC生成的语法分析器可以和扫描器连接。程序的可再入性如果一个程序具有下面的特性，我们可以称它是可再入的：当这个程序正在执行时，可以随时中断它的执行进程，也可随时从中断点恢复其原来的执行进程；而且可以再中断时间里，又从该程序的头上开始一个新的执行进程。程序的可再入性 要使一个程序具有可再入性，必需
10、满足以下的三个要求：程序执行过程中，该进程的所有指令不允许被修改，这种程序也被称为“纯代码”。该程序的不同进程具有不同数据区，这些数据区分别用来存放该程序中使用的数据、工作单元以及该程序产生的中间结果。对于程序执行过程中所使用的寄存器，在该程序的任何一个执行进程被中断时，应保存它们的内容，恢复执行时应能恢复它们原来保存过的内容。1.7 翻译程序编写系统 将有助于减轻编写翻译程序（包括编译程序、汇编程序、解释程序）工作的任何软件系统或工具包，统称为翻译程序编写系统（Translator Writing System，简称TWS），产生式语言的编译程序和自动分析算法的构造程序都是TWS。1.7 翻
11、译程序编写系统TWS可分为三类：1.自动产生编译程序的“编译程序的编译程序”（Compiler-Compiler）。只要给出某一高级程序语言的语法规则和语义描述，这类程序就能自动地生成相应语言的编译程序。2.面向语法的符号加工程序。这类程序比较通用。3.由可扩充语言组成的集合。这类TWS允许程序员利用已有的数据类型和语句去定义新的数据类型和语句。1.8 并行编译程序 适合于SIMD和MIMD结构计算机，具有并行处理功能的编译程序称为并行编译程序（或并行编译器）。并行编译程序的功能是，把串行的源程序或尚未充分并行化的并行源程序，自动转换成并行计算机系统上运行的并行目标程序或它所能接收的并行源程序
12、。The end.第二章 形式语言概论 本章主要介绍形式语言理论中的一些最基本的概念和基础知识，它是学习以后各章节的基石。2.1 语言成分 一个语言的成分包括字母表（Alphabet）,文法(Grammar)以及它的语义。本章将主要讨论字母表、符号串、产生式文法系统以及句子分析等方面的内容。2.1 语言成分v字母表与符号：字母表是元素的非空有穷集合。字母表中的元素称为符号。v符号串及其运算：符号串。符号串的长度。符号串的连接。符号串集合的乘积。符号串的方幂。符号串集合的方幂。符号串集合的正闭包。符号串集合的自反闭包。2.2 产生式文法和语言 文法(Grammar)是定义或描述语言的语法结构的一
13、组形式规则(即语法规则)。一个程序语言的文法的目的就是用适当条数的规则把该程序语言全部成分描述出来。2.2.1 产生式文法v 定义2.1 产生式文法定义成一个四元组G=(VN，VT，S，P)，VT:非空有限的终结符号集(符号表)；VN:非空有限的非终结符号集(变量表)；S:开始符号(识别符号)，是文法G规定的最终目标；P:产生式的集合。其中VNVT=，SVN。我们令V=VNVT，则P中产生式的一般形式为 A|AVN 且,V 或 A:=|(本书中统一采用“A|”的表示方法)。2.2.2 上下文无关文法v定义2.2 文法G是一个四元组，G=(VN，VT，P，S)，其中，VN、VT分别是非空有限的非
14、终结符号集和终结符号集，VNVT=，P是产生式集，SVN称为文法的识别符号或开始符号。开始符号S必须至少在某个产生式的左部出现一次。2.2.3 上下文无关文法定义的语言v定义2.3 设文法G=(VN，VT，P，S)，A是其中的产生式，若有符号串,(VNVT)*，使得 U=A，w=则称w为U应用产生式A所得到的直接推导(Direct Deriavtion)，也称w可直接归约到U,记为 Uw ,即 A特别的，当=时，有 A 即每个产生式的右部都是它左部的直接推导，符号“”仅指“推导一步”的意思。2.2.3 上下文无关文法定义的语言v定义2.4 如果存在一个直接推导的序列 v=012n=w （n0）
15、则称符号串w为符号串u的一个推导，或称“w可归约到v”记为 定义2.5 表示 或v=w。wuwuwuwu2.3 文法的分类2.3.1 文法分类v0型文法 v1型文法（上下文有关文法）v2型文法（上下文无关文法）v3型文法（右线性文法和正规文法）2.3.2 文法分类的意义2.3.3 文法举例0型文法 在2.2.1节中定义的文法即为0型文法(无限制的文法)。其产生式具有以下形式：其中，(VNVT)+，(VNVT)*1型文法（上下文有关文法）1型文法G的产生式具有以下形式：其中=1 A2；=12；1，2(VNVT)*；AVN；(VNVT)+。例 1型文法G6=(VN，VT，P，S)其中，VN=S，X
16、，Y，Z VT=（x，y，z）P=SxSYZxYZ,xYxy，yYyy,yZyz ZYYZ,zZzz 2型文法（上下文无关文法）在1型文法的产生式中上下文1和2用空符号串代替，则有以下形式的产生式称为2型文法：A其中，AVN，(VNVT)+。例 2型文法G3=(VN，VT，P，E)其中，VN=E，T，F VT=+，*，(，)，i P=EE+TT，TTFF，F(E)i 3型文法（右线性文法和正规文法）如果P中的产生式只含有下面的两种形式：Aa AaB 则称该文法为右线性文法，其中，A，BVN，aVT*。例 右线性文法 G4=(VN，VT，P，S)其中，VN=S，A，B VT=0,1 P=S011
17、A0B，A1A0B，B010B 3型文法（右线性文法和正规文法）在正规文法中，P中的每个产生式(S例外，S为文法的开始符号)只有两种形式：Aa，AaB 。其中 A，BVN，aVT。此外，如果S是P中的一个产生式，那么S不能出现在任何产生式的右边。例 正规文法G5(S)SdB|+A|-A|GAdB|GBdB|H|dGdHHdH|d 其中d代表十进制数字。2.4 语言和语法2.4.1 句型、句子和语言2.4.2 语法树2.4.3 产生式树2.4.1 句型、句子和语言v定义2.6 设S是文法G的识别符号，如果 ，则称符号串u为文法G的句型。v定义2.7 设S是文法G的识别符号，若 ，uVT*，则称符
18、号串u为文法G的子。v定义2.8 设S是文法G的识别符号，文法G的语 言L(G)=u|且u VT*，即文法 的语言是文法的所有句子构成的集合。uSuSuS2.4.2 语法树 在自然语言中，可通过树型表示直观地分析句子结构；在形式语言中，则是通过语法树直观地分析文法的句型结构。句子结构句 子主语 系词定语名词Physics冠词the前置词ofareThey连接词and名词students名词teachers名词Department.表语代词2.4.2 语法树 设文法G=(VN，VT，P，S)，对于文法G的任意一个句型都存在一个相应的语法树：树中每个结点都有一个标记，该标记是VNVT中的一个符号；
19、树的根结点标记是文法的识别符号S；若树的一个结点至少有一个叶子结点，则该结点的标记一定是一个非终结符；若树的一个结点有多个叶子结点，该结点的标记为A，这些叶子结点的标记从左到右分别是B1，B2，Bn，则(A，B1B2Bn)P。2.4.3 产生式树 文法的句型都可依据文法的产生式来生成相应的语法树。以句型E+(E+T)i为例：v 以文法G的识别符号E作为语法树根结点的标记。选择识别符E的一个产生式EE+T，然后生成根结点E的3个分支，根结点E的3个叶子结点的标记，从左到右分别记为E、和T。v 选择产生式TTF，生成以结点T作为根结点的子树。v 选择产生式Fi，以中子树最右边的叶子结点F为根结点，
20、延伸相应的子树。v 选择产生式TF，以中子树的叶子结点T为根结点，延伸相应的子树。v 选择产生式F(E)，以中子树的叶子结点F为根结点，延伸相应的子树，扩充相应的子树。2.5 文法和语言的一些特性 2.5.1 无用非终结符号 如果文法的某个非终结符不出现在文法的任何一个句型中，并且不能从它推导出终结符号串，则称该非终结符为无用非终结符号。2.5.2 不可达文法符号 如果一个非终结符（非识别符号）不出现在文法的任何一条产生式的右部，则称该非终结符为不可达文法符号。2.5.3 可空非终结符 2.5.4 最左、最右推导和规范推导 2.5.5 二义性 2.5.3 可空非终结符2型文法的产生式要求以下形
21、式：A其中，AVN，(VNVT)+。对2型文法可进行扩充，令(VNVT)*，允许有以下形式的产生式：A此产生式称为空产生式，A称为可空非终结符。2.5.4 最左、最右推导和规范推导v定义2.9 在xUyxuy直接推导中，若xVT*，UVN 即U是 符号串xUy中最左非终结符，则称此直接推导为 最左直接推导。若一个推导的每一步直接推导 都是最左直接推导，那么此推导称为最左推导。v定义2.10 在xUy:=xuy直接推导中，若yVT*,UVN，即U 是符号串xUy中最右非终结符，则称此直接推导 为最右直接推导。若一个推导的每一步直接推 导都是最右直接推导，则称此推导为最右推导。最右直接推导又称为规
22、范直接推导，最右推导又称为规范推导。2.5.4 最左、最右推导和规范推导v定义 2.11 假定x1x2xn是一个最左推导，我们称序列Bn，Bn-1，B1 是一个最右 归约。v定义 2.12 假定x1x2xn是一个最右推导，我们称序列Bn，Bn-1，B1，是一个最 左归约。v最左推导的逆过程是最右归约，最右推导的逆过程是最左归约。2.5.5 二义性v定义2.13 一个文法，如果它的一个句子有 两棵或两棵以上的语法树，则称 此句子具有二义性。如果一个文 法含有二义性的句子，则该文法 具有二义性。2.6 分析方法简介v一个分析器或分析自动机是这样一种系统，它能够根据给定的文法G，构造语言L(G)的任
23、意推导。分析也可看作是语法树的构造过程。我们主要讨论右线性文法和CFG的分析器。v分析的方法很多，可归纳为两类，一类是自上而下分析方法，另一类是自下而上分析方法。2.6.1自上而下分析方法 自上而下分析方法的基本思想是从文法的开始符号出发，利用其中的产生式，逐步推导出待分析的符号串。如果能推导出这个符号串，则表明此符号串是该文法的一个句型或句子，否则便不是。2.6.2 确定的自上而下分析方法 v当文法的某一个非终结符有几条产生式、而且每条产生式右部首符号都是终结符时，应保证它们是互不相同的终结符。v例 设文法G18S：SaBcbCd BeBf CdCc试检查符号串aefc是不是该文法的句子。2
24、.6.2 确定的自上而下分析方法上例推导过程：SaBc，SaBc；BeB，SaBcaeBc；Bf，SaBcaeBcaefc；该例属确定的自上而下分析方法。2.6.3 自下而上分析方法 自下而上分析方法的基本思想是从待检查的符号串出发，看最终是否能归约（推导的逆过程）到文法的识别符号。如果能归约到文法的识别符号，则表明此待检查的符号串是该文法的一个句型或句子，否则便不是。2.6.4 文法在内存中的表示 用语法图的表格结构表示文法。一个文法的语法图由该文法所有非终结符号的定义图组成。每个非终结符号的定义图是一个结构型数据。在自上而下分析方法中，用这种语法图表示文法有利于消除左递归，也有助于提取左因
25、子。The end.第三章 有穷自动机 本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式与有穷自动机之间的相互关系。3.1 概述v有穷状态自动机(Finite-state Automata 或简称FSA)在识别功能上与正规文法类等价，而且也等价于一个特殊类型的语言产生器正规表达式(Regular Expression)。因此许多简单的程序语言都可由FSA所识别。事实上，它是描述词法的有效工具，也是进行词法分析的主要理论基础。v有穷状态自动机在计算机系统中的价值是很明显的，它提供了一种逻辑地探测方式，去探测一些输入串是否属于某种语言，也就是说，它可以作为一种语法检查器(Syntax
26、 Checker)。3.2 有穷自动机的形式定义 v定义3.1 一个确定有穷自动机DFSA是一个五元组 M=(Q,t,q0,F)其中，Q是非空有穷状态集,其中的每个元素称为一个状态；是有穷输入字母表，它的每一个元素称为一个输入符号；t是一个单值映射QQ，也称状态转换函数，t(q,x)=q意指：当现行状态为q，面临的输入符号为x时，将转到下一状态q，q称为q的一个后继状态；q0Q称之为开始状态；FQ称为终止状态集，至少由一个终止状态组成。3.2.1 状态转换表v例3.1 有穷自动机 A=(Q,t,q0,F)其中，Q=S,A,B,G,H，=+，-，d，S是开始状态，终止状态集F=B,H，映射t:Q
27、Q由下表所示的状态转换表给出。BH符号状态+-d S A A G B A G B H B G H H3.2.2 状态转换图v例3.2 有穷自动机A(记为DFSA A)，A=(Q,t,q0,F)其中，Q=q0,q1,q2,q3，=a,b，q0是开始状态，终止状态集F=q0，映射t:QQ由下图所示的状态转换图给出。在图中，状态q0用双圆圈标记，表明它是终止状态；同时，用一个箭头标记，表明它是开始状态。q1 a a a b b a b b q2 q3 q0 3.2.3 构形和移动v构形(q0，)称为初始构形，其中q0是初始状态，是由该自动机可接收或拒绝的任何输入串。构形(q,)称为终止构形，其中是空
28、串，qF(终态集)。v自动机的移动(记为)是从一种构形到另一种构形的转换。v记号+称为的传递闭包；*称为的自反闭包。*表示“0次或多次移动”；+表示“一次或多次移动”。3.2.4 自动机的等价性v定义3.2 M和M是等价的，当且仅当对每一个串x，M接收x当且仅当M接收x。v定义3.3 如果M仅通过重新标记它的状态就能转换称M,则M和M称为同构的(Isomorphic)。vFSA的一个基本定理是：对每一个自动机M，存在一个等价的具有最少状态个数的自动机M，而且对于每一个其状态个数与M相同且等价于M的自动机M,必是与M同构的。换句话说，M在结构上是唯一的。3.2.5 非有穷状态自动机v定义3.4
29、一个非确定有穷自动机NDFSA是一个五元组 NDFSA=(Q,t,q0,F)其中，Q是一个非空有穷状态集，是一个非空有穷输入字母集，映射t为QQ的子集(即t是一个多值映射)，Q0Q是开始状态集，FQ是终止状态集。v同样的，NDFSA也可以用状态转换表和状态转换图表示。3.2.5 非有穷状态自动机 非确定有穷自动机与确定有穷自动机的主要区别有三：v1NDFSA有一个开始状态集，而DFSA只有一个开始状态。v2NDFSA的映射是QQ的子集，是一个多值映射，而DFSA的映射是QQ，是一个单值映射。v3NDFSA在没有扫描任何输入符号的情况下，也可以进行移动，这种移动称为空移。我们用表示法：t(q,)
30、=某些状态的集合将这种情况包括在状态转换函数中。注意，甚至当输入串已经完全扫描完之后还可能需要空移。3.3 NDFSA到DFSA的转换 通过下述步骤可将一个NDFSA转换称等价的DFSA：v寻找并消除空移环路；v 消除余下的空移；v 确定化。3.3.1 空移环路的寻找和消除 v例 图(a)所示的是一个NDFSA，结点q0是开始状态，q3是终止状态，结点q0、q1与q4形成一个空移环路。要消除这个空移环路，只需将3个结点q0、q1与q4合并成一个结点，以q0标记，并消除原来3个结点之间所有的环。由于这3个结点中的q0是开始状态，因此，合并之后的新结点q0被设置为开始状态，如图(b)所示。q2bq
31、3aq4q1q0abb(a)q2q3bq0abba(b)3.3.2消除空移 v下面给出一个消除空移的算法。给定从状态A到B的一个空移(即从状态A到B经由连线的一个转换，换言之，t(A,)=，B，)。置t(A,)=，对每个a和q，如果qt(B,a)，则将q加到t(A,a)。如果A是开始状态，则将B也加入开始状态集。如果B是终止状态，则将A也加入终止状态集。3.3.3利用状态转换表消除空移 利用FSA的状态转换表，可以很容易地消除空移。这种方法地基本步骤示：v首先，找出直接经由一个空移到达某个终态地所有状态。每当找到这样一个状态，便将它标记终态。v然后，考虑消除与未被标记为终态的那些状态相关的空移
32、。对表中每一个具有射出连线的状态继续按上述方式处理，直到状态转换表不再变动为止。v最后从表中删除列和没有任何元素的空行便得到一个不含空移的状态转换表。3.3.4 确定化子集法 设NDFSA M=(Q,t,Q0,F)是一个非确定有穷自动机，它的语言（即它能接受的符号串集合）记为L(A)。那么，一定可以构造一个和它等价的确定有穷自动机DFSA M=(Q,t,q0,F)，使L(A)=L(A)。构造如下：v M的状态集Q是由M的状态集Q的所有子集组成的。用p1,p2,pi表示Q的元素，其中p1,p2,pi是Q中的状态。以后，我们总假定状态p1,p2,pi是按某种规范顺序排列的。例如，对于子集p1p2=
33、p2，p1，Q的状态是p1,p2。v 若p是M的一个终态，则M中每一个包含p的状态，p，都是M的一个终态。3.3.4 确定化子集法v 若S=S1,S2,Sj 是M的初态，则S=S1,S2,Sj是M的初态。v 令p1,p2,pn是M中的一个状态，其中p1,p2,pn 是M中的一个状态。对某个输入符号a，考虑M中的转换函数：t(p1,a),t(p2,a),，t(pn,a)根据这些转换函数，我们可按如下方法构造M中的转换函数t：(a)令t(p1,a)t(p2,a)t(pn,a)=Q1,Q2,Qr。也就是将状态p1,p2,pn分别面临输入符号a时所确定出的状态统统汇集起来并取名为Q1,Q2,Qr。(b
34、)置t(p1,p2,pn,a)=Q1,Q2,Qr。注意，这是一个确定的转换函数。即M中的状态p1,p2,pn面临输入符号a时恰好确定出下一状态Q1,Q2,Qr。v 对M每一状态和每个输入符号a，重复步骤4。这个算法总是可以终止的。因为虽然M中含有许多可能的状态子集，但其不同子集的最大个数是有穷的。事实上，若M有a个状态，则M中最大可能的状态个数是(-1)。3.3.5确定化造表法 造表法是比子集法简单而有效的一种确定化方法。v定义3.5设NDFSA M=(Q,t,Q0,F)，假定I是M中状态集的一个子集，定义-closure(I)如下：若qI，则qclosure(I);若q-closure(I)
35、，q是由q出发经多条弧所到达的状态，则q -closure(I)。v定义3.6假定I是NDFSA M中状态集的一个子集，a，定义 =-closure(J)其中J是所有那些可从子集I中的任一状态出发，经过一条a连线(跳过a连线前的连线)而到达的状态(结)的全体。3.3.5确定化造表法造表法的具体步骤：假定给定的NDFSA M中仅含两个符号a，b。可用如下方法将M确定化：采用造表的方式，该表的每一行有三列(若中含有n个符号，则该表有n+1列)，第一列记为I，第二、三列分别记为Ia,Ib。v 置该表的第一行第一列为-closure(Q0)，即一列包含M初态集Q0 的-闭包。然后计算它的Ia 和Ib,
36、分别填入第二、三列上，一般，若某一行的第一列上的I已确定，便可根据前述定义求出这一行的第二、第三列上的Ia 和Ib。v 检查Ia 和Ib，看它们是否已在表的第一列中出现，把未曾出现者之一填入下一空行的第一列上，再计算该行的第二、第三列上的Ia 和Ib。3.3.5确定化造表法v 重复第二步，直至表中所有第二、第三列上的元素全部再第一列出现为止。因为M中的状态(子集)的个数是有限的，所以上述三步必定在有限步内终止。v 将由上述过程得到的最终形式的表看作一个状态转换表，即把其中第一列中的元素作为状态，把Ia,Ib分别看作是输入符号a，b，把其余信息看作是状态转换函数之值。这个表唯一地刻画了一个确定的
37、有穷状态自动机M，其初态是该表第一行第一列的元素，其终态是该表中所有那些含有原终态的元素。可以证明，这个DFSA M和NDFSA M是等价的。3.3.6 消除不可达状态 v在自动机中，从开始状态没有任何一条路径能达到的状态称为不可达状态。由于不可达状态事实上是无用的，因此可以删除它们。下面给出识别可达状态的算法。当该算法终止时，每一个未标记的状态就是不可达状态。v识别DFSA中可达状态的算法。标记开始状态S；给定任意标记过的状态P，如果对某个输入符号存在从状态P到Q的转换，则标记每一个这样的状态Q；重复步骤，直到不再有可标记的状态为止。3.3.7确定的有穷自动机的化简 v所谓确定有穷自动机M的
38、化简是指：寻找一个状态数必M少的确定的有穷自动机M，使得L(M)=L(M)。v定义3.7 假定q1和q2是M中的两个不同状态，称q1和q2是等价的：如果从状态q1出发能扫描任意串w而停止于终态，那么从状态q2出发也能扫描同一个串w而停止于终态；反之，亦然。v定义3.8 如果两个状态q1和q2不等价，则称这两个状态是可区分的。3.3.7确定的有穷自动机的化简DFSA M的化简算法。给定DFSA M=(Q,t,q0,F)，化简M的算法如下：v 将Q划分为二组：F（终态组）和Q-F（非终态组），以构成初始分划0；v 给定k，用下述方法构造新的分划k+1:for k中的每一子组Gi do begin
39、2-1)试图对Gi进行分划，使得状态s，t并入Gi的同一子组中 iffa，有t(s,a)和t(t,a)都落入k的同一子组中；否则，必须对Gi进行分划，使得分划后的某个子组包含s，另一子组包含t；2-2)将经上述分划后的子组并入k+1end；3.3.7确定的有穷自动机的化简v 若k+1k，则用k+1“替代”k，重复；否则，分划过程终止，转；v 得到化简后的DFSA M，其中Q的状态数即最终分划i的子组个数，取i中每个子组中的一个状态代表该子组构成Q。注意，此时，i中的每个子组是不相交的，且任何不同两个子组中的状态都是可区分的，而同一子组中的任何状态都是等价的。q0即i中含q0的子组；F即包含F中
40、任一状态的所有子组；=；t即i中子组到子组之间的变换(可能会合并一些连线)；v 去掉不可达状态和无用状态，便得到最终化简后的DFSA M。3.3.7确定的有穷自动机的化简 一个DFSA M的状态化简过程就是把M的状态集分划成一些不相交的子集，使得任何不同的两子集的状态都是可区分的，而同一子集的任何两个状态都是等价的。最后，从每个子集选出一个代表(代表该子集)，同时消去其它等价状态。3.3.8从化简后的DFSA到程序表示 识别标识符的DFSA1（见图(a)）需改为图(b)所示状态，其中，l代表字母，d代表数字。图（a）图（b）如果赋予状态q0、q1与q2一定的操作，则可得识别单词标识符的程序流程
41、图(见下图)。lq0l,dq1lq1l,dq2q0非 l,dchar ch,namekname read(ch)q0若 ch=lname name+chread(ch)q1非 l,d用 name 查符号表，若没有，则填表，否则返回其地址read(ch)q2若 ch=l or d3.4 正规文法与有穷自动机 正规文法与有穷自动机FA有着特殊的关系。可以证明：对任何正规文法G，可以构造一个FSA，它能而且只能识别语言L(G);反过来，对任何FSA，可以构造一个相应的正规文法G，它能生成由该FSA所识别的语言。3.4.1从正规文法到FSA 设正规文法G有形如UaV(aVT,VVN或V=)的产生式。由
42、正规文法G可以直接构造一个有穷自动机A(简称自动机A)，使L(A)=L(G)。构造步骤如下：v 令正规文法G的终结符号集作为有穷自动机A的字母表；v 文法G的每一个非终结符都作为自动机A的一个状态，特别是文法G的开始符作为自动机A的开始状态；v 在自动机A中增加一个新状态z作为自动机的终止状态；v 对于文法G的形如UaV(aVT或a=,VVN)的产生式，在自动机A中构造形如t(U,a)=V的映射；v 对于文法G的形如Ua(aVT)的产生式，在自动机A中构造形如t(U,a)=z的映射。3.4.2 从FA到正规文法 从正规文法可直接构造其自动机，反之，由自动机也可直接构造其正规文法。构造步骤如下：
43、v 自动机每一个状态的标记，均作为正规文法的非终结符，其中，自动机开始状态的标记将作为正规文法的开始符号。自动机的输入字母表中的所有符号，作为正规文法的终结符。v 对于自动机的映射t(U,a)=V（其中，U、V为自动机的状态标记；a为输入符号），构造文法的一条产生式 UaV U、V为文法的非终结符，a为终结符。v 对于自动机的终止状态Z，在正规文法中增加一条产生式 Z 3.5 正规表达式与FA 3.5.1 正规表达式的定义 3.5.2 正规表达式的CFG 3.5.3 正规表达式与FSA的对应性 3.5.4 正规表达式到NDFSA的转换 3.5.5 NDFSA M到正规表达式的转换 3.5.6
44、从正规文法到正规表达式 3.5.1 正规表达式的定义v 正规语言是正规集。正规表达式是用于描述称之为正规集的语言类的一种表示形式。v 以下是正规表达式的一些相关定义。3.5.1 正规表达式的定义v定义3.9 字母表上的正规表达式和正规集递归定义如下：a，a是上的一个正规表达式，它所表示的正规集为a。空串是上的一个正规表达式，它所表示的正规集为。空集是上的一个正规表达式，它所表示的正规集为。设e1与e2都是上的正规表达式，它们所表示的正规集分别为 L(e1)与L(e2)，则i)e1e2也是正规表达式，它所表示的正规集为L(e1e2)=L(e1)L(e2)；ii)e1 e2也是正规表达式，它所表示
45、的正规集为L(e1 e2)=L(e1)L(e2)；iii)(e1)*也是正规表达式，它所表示的正规表达式为L(e1)*)=(L(e1)*。3.5.1 正规表达式的定义v定义3.10 设e1与e2是上的两个正规表达式，若L(e1)=L(e2)，则称e1与e2等价，记为e1=e2，如 a(ba)*=(ba)*a3.5.1 正规表达式的定义v定理3.1 设e1、e2和e3都是上的正规表达式，则 e1e2=e2e1 (交换律)(e1 e2)e3=e1(e2 e3),(e1e2)e3=e1(e2e3)（结合律）e1(e2e3)=e1 e2e1 e3,(e1e2)e3=e1 e3 e2 e3（分配律）e1
46、=e1=e1 ()*=(空集的闭包是空串)e1=e1=e1*=e1|e1*(e1*)*=e1*e1|=e1 3.5.2 正规表达式的CFGv正规表达式是由下面的CFG GR=（N,P,R）描述的。其中，N=R，C，L =|,(,),*,a,v产生式集合P为：RR|C (选择)RC CCL (连结)CLL(R)(括号)LR*(闭包)La (正规语言中的任何符号)L (空串)v 该文法描述了操作符：连结，选择和闭包的优先级以及形成正规表达式的结构规则。3.5.3正规表达式与FSA的对应性 正规表达式和FSA是定义语言（符号串集）的两种不同形式。同一个语言，既可用FSA描述，也可用正规表达式描述。3
47、.5.4正规表达式到NDFSA的转换v对于字母表上任意一个正规表达式e，一定可以构造一个NDFSA M，使L(M)=L(e)。v先构造一个NDFSA M的一个广义转换图，其中，只有S与Z两个状态，S是开始状态，Z是终止状态，弧上是正规表达式e。然后，按照下图所示的替换规则对正规表达式e逐步进行分解，直到转换图中所有的弧上都是中的单个符号或为止。3.5.4正规表达式到NDFSA的转换（1）替换成（2）替换成（3）替换成Ae1e2B(a)Ae1Ce2B(b)Ae1e2B(c)AB(d)e1e2Ae1*B(e)ACB(f)e13.5.5 NDFSA M到正规表达式的 转换 对于一个具有输入字母表的N
48、DFSA M，在上也可以构造一个正规表达式e，使L(e)=L(M)。具体操作如下：v 首先，对NDFSA M进行拓广，在M的状态转换图中，新设置一个唯一的开始状态S和唯一的终止状态Z，并允许状态转换图中弧上可以为正规表达式。v 然后，从开始状态S到原来所有的开始状态连接弧，再从原来所有的终止状态到Z状态也连接弧。修改后,构成了一个新的NDFSA，它只有一个初态结点S和一个终态结点Z，这个新的NDFSA M显然和原NDFSA M等价。v 接着，利用下图所示的替换规则，逐步消去M中属于M的所有结点和有关连线，直到状态转换图中只剩下状态S和Z为止(这个过程称为消结)。在消结过程中，用相应的正规表达式
49、标记连线。3.5.5 NDFSA M到正规表达式的 转换（1）替换成（2）替换成（3）替换成Ae1Be2CAe1e2CABe1e2Ae1e2BAe1Be3Ce2AB321eee3.5.6从正规文法到正规表达式本节介绍两种转换方法：首先，正规文法中的每个非终结符都可以表示成关于它的一个正规表达式方程。把一正规文法中所有这样一些方程写在一起便构成该正规文法的一个联立正规表达式方程组。以下例介绍这种转换方法：v 例 现有正规文法G22S:S0A|1B|0|1A0S|1B|1B0A|1S可以写成如下关于变量S，A，B的一个正规表达式方程组：S=(0+1)+0A+1B （1）A=1+0S+1B (2)B
50、=1S+0A (3)3.5.6从正规文法到正规表达式v 解上方程组得：S=(0+10)(10)*(0+11)+11)S+(0+10)(10)*1+0+1)v 它的最小确定点解是：S=(0+10)(10)*(0+11)+11)*(0+10)(10)*1+0+1)即S=(0|10)(10)*(0|11)|11)*(0|10)(10)*1|0|1 它就是与正规文法G22S等价的正规表达式。3.5.6从正规文法到正规表达式 第二种正规文法到正规表达式的转换规则如下：v 产生式UV,V,VVN，,VT*，转换成正规表达式U=；v 产生式UU，转换成U=*；v 产生式U，转换成U=。3.6 DFSA在计算
