编译原理 第三章词法分析.doc

第三章 词法分析词法分析是编译的第一个阶段，它的主要任务是从左至右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描程序。本章我们将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。本章重点：正规式、有限自动机（DFA、NFA）、NFA到DFA的转换、DFA的最小化。第一节 词法分析程序的设计一、词法分析程序的输出词法分析程序的功能是读入源程序，输出单词符号，单词符号是一个程序设计语言的基本语法符号。程序设计语言的单词符号一般可分为下列5种：1、基本字，也称关键字，如PASCAL语言中的begin, end, if, while和var等。2、标识符，用来表示各种名字，如常量名、变量名和过程名等。3、常数，各种类型的常数，如25,3.1415,TRUE和“ABC”等。4、运算符，如+, , =等。5、界符，如逗点，分号，括号等。词法分析程序所输出的单词符号常常采用以下二元式表示：（单词种别，单词自身的值）。单词的种别是语法分析需要的信息，而单词自身的值则是编译其它阶段需要的信息。比如在PASCAL的语句const i=25, yes=1;中的单词25和1的种别都是常数，常数的值25和1，对于代码生成来说，是必不可少的。有时，对某些单词来说，不仅仅需要它的值，还需要其它一些信息以便编译的进行。比如，对于标识符来说，还需要记载它的类别、层次还有其它属性，如果这些属性统统收集在符号表中，那么可以将单词的二元式表示设计成如下形式（标识符，指向该标识符所在符号表中位置的指针），如上述语句中的单词i和yes的表示为：（标识符，指向i的表项的指针）（标识符，指向yes的表项的指针）单词的种别可以用整数编码表示，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5，程序段if i=5 then x ：= y；在经词法分析器扫描后输出的单词符号和它们的表示如下： 保留字if (3，if) 标识符i（1，指向i的符号表入口） 等号 =（4，=） 常数5（2，5） 保留字then（3，then） 标识符x（1，指向x的符号表入口） 赋值号 ：=（4：=） 标识符y（1，指向y的符号表入口） 分号；（5，；）第二节 单词的描述工具程序设计语言中的单词是基本语法符号。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，可以建立分析技术，进而可以建立词法分析程序的自动构造方法。一、正规文法多数程序设计语言的单词的语法都能用正规文法或3型方法来描述。回顾一下3型方法G =（VN，VT，S，P）的特征，即P中的每一条规则都有下述形式：AaB或Aa其中A，BVN，aV。正规文法所描述的是V上的正规集。程序设计语言中的几类单词可用下述规则描述：1|11| d |1 |d d | d + | | | / | | =，| ；|（ | ）| 其中1表示a z中的任何一英文字母，d表示0 9中的任一数字。二、 正规式正规式也称正则表达式，也是表示正规集的工具。也是我们用以描述单词符号的方便工具。下面是正规式和它所表示的正规集的递归定义。设字母表为 ，辅助字母表= ，, |, (,) 。1、和都是上的正规式，它们所表示的正规集分别为和；2、任何a ，a是上的一个正规式，它所表示的正规集为a；3、假定e1和e2都是上的正规式，它们所表示的正规集分别为L (e1),和L (e2)，那么，(e1), e1 |e2, e1e2和e1也都是正规式，它们所表示的正规集为L (e1), L (e1) UL (e2), L (e1) L (e2)和 (L(e1) )。4、仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。例 1 令 =a, b, 上的正规式和相应的正规集的例子有： 正规式正规集 aa a | ba , b abab (a | b) (a | b)aa, ab, ba, bb a, a, aa,任意个a的串 (a | b), a, b, aa, ab所有a, b组成的串 (a | b) (aa | bb) (a | b) 上所有含有两个相继的a或两个相继的b组成的串。三、 正规文法到正规式一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，存在一个定义同一个语言的正规式；反之，对每个正规式，存在一个生成同一个语言的正规文法，有些正规语言很容易用文法定义，有些语言更容易用正规式定义，本节介绍两者间的转换，从结构上建立它们的等价性。1、将上的一个正规式转换成文法G=（VN，VT，S，P）。令其中的VT= ，确定产生式和VN的元素用如下办法。对任何正规式r，选择一个非终结符S生成产生式Sr，并将S定为G的识别符号。若x和y都是正规式，对形如Axy的产生式，重写成：AxB, By两产生式，其中B是新选择的非终结符，即BVN。对已转换的文法中的形如Axy的产生式，重写为：AxBAyBxBBy 其中B为一新非终结符，对形如Ax | y的产生式，重写为：Ax Ay不断利用上述规则做变换，直到每个产生式最多含有一个终结符为止。例2 将R = a (a | d )转换成相应的正规文法，令S是文法的开始符号，首先形成Sa (a | d),然后形成SaA和A (a | d )，再重写第二条产生式形成SaA,A (a | d )B,A,B (a|d)B和B进而变换为SaA,BaB,AaB,BdBAdB,BA2、将正规文法转换成正规式。基本上是上述过程的逆过程，最后只剩下一个开始符号定义的产生式，并且该产生式的右部不含非终结符。其转换规则列于表4.1表4.1 正规文法到正规式的转换规则文法产生式正规式规则1规则2规则3AxB, ByAxA | yAx AyAxyAx yAx | y例3 文法GSSaASaAaAAdAAaAd先有：S=aA|aA=(aA|dA)|(a|d)再将A的正规式变换为A=(a|d) A|(a|d)，据表中规则2变换为：A=(a|d)*(a|d)，再将A右端代入S的正规式得：S=a(a|d) *(a|d)|a再利用正规式的代数变换可依次得到S=a(a|d) *(a|d)|a 即a(a|d) *为所求。第三节 有穷自动机有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机（Deterministic Finite Automata）和不确定的有穷自动机（Nondeterministic Finite Automata），下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。一、 确定的有穷自动机（DFA）一个确定的有穷自动机（DFA）M是一个五元组：M =（K, , f, S, Z）其中1、K是一个有穷集，它的每个元素称为一个状态；2、是一个有穷字母表，它的每个元素称为一个输入字符，所以也称为输入符号字母表；3、f是转换函数，是在k K上的映像，即，如f (ki, a ) = kj (kik, kjk )就意味着，当前状态为Ki，输入字符为a时，将转换到一状态kj，我们把kj称作ki的一个后继状态；4、SK是唯一的一个初态；5、ZK，是一个终态集，终态也称可接受状态或结束状态。例 3 DFA M=（S,U,V,Q,a, b,f, S,Q）其中f定义为：f (S, a) = Uf ( V, a ) = Uf (S, b) = Vf ( V, b ) = Qf (U, a) = Qf ( Q, a ) = Qf (U, b) =Vf ( Q, b) = Q一个DFA可以表示成一个状态图（或称状态转换图）。假定DFA有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以“”或标以“”，终态结点用双圈表示或标以“+”，若f (ki, a) = kj，则从状态结点ki到状态结点kj，画标记为a的弧；例3中的DFA的状态图表如图3-3-1。 a.baaa b a b b图3-3-1 状态图表示UQFQQQSV a.baaa b a b b图3-3-1 状态图表示UQQQQSV 字符状态abSUV0UQV0VUQ0QQQ1图3-3-2 矩阵表示 一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f (k, a)的值。用“”标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。例3中的DFA的矩阵表示如图3-3-2对于中的任何字符串t,若存在一条从初态结到某一终态结的道路，且这条路上所有弧的标记符连接成的字符串等于t,则称t可为DFA M所接受，若M的初态结同时又是终态结，则空字可为M所识别（接受）。DFA M所能接受的字符串的全体（字的全体）记为L（M）。结论： 上一个符号串集V*是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。DFA的确定性表现在转换函数f：KK是一个单值函数，也就是说，对任何状态kK，和输入符号a，f（k，a）唯一地确定了下一个状态。从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。二、不确定的有穷自动机（NFA）一个不确定的有穷自动机（NFA）M是一个五元组，M=（K，f，S，Z）其中1 K是一个有穷集，它的每个元素称为一个状态；2 是一个有穷字母表，它的每个元素称为一个输入字符；3 f是一个从K*到K的子集的映像。4 SK，是一个非空初态集；5 ZK，是一个终态集。一个含有m个状态和n个输入字符的NFA可表示成如下的一张状态转换图：这张图含有m个状态结，每个结可射出若干条箭弧与别的结相连接，每条弧用*中的一个串作标记，整个图至少含有一个初态结以及若干个终态结。a，b b a a a b b a b图3-3-3 NFA M01342例4 一个NFA M=（0，1，2，3，4，a，b，f，0，2，4）其中f（0，a）=0，3 f（2，b）=2f（0，b）=0，1 f（3，a）=4 f（1，b）=2 f（4，a）=4f（2，a）=2 f（4，a）=4它的状态图表示如图3-3-3。对于*中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串（不理采那些标记为的弧）等于t，则称t可为NFA M所识别（读出或接受）。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路，那么空字可为M所接受。显然DFA是NFA的特例。对于每个NFA M，存在一个DFA M、使得L（M）=L（M）。对于任何两个有穷自动机M和M，如果L（M）=L（M），则称M与M是等价的。三、 NFADFA的转换为介绍算法首先定义对状态集合I的几个有关运算：1状态集合I的闭包，表示为closure（I），定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。如输入字符是空串，则自动机仍停留在原来的状态上，显然，状态集合I的任何状态S都属于closure（I）。2状态集合I的a弧转换，表示为move（I，a）定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。假设NFA N（K，f，K0，Kt）按如下办法构造一个DFA M（S，D，S0，St）使得L（M）L（N）：1M的状态集S由D的一些子集组成。（构造K的子集的算法将在后面给出）我们用S1，S2，Sj表示S的元素，其中S1，S2，Sj是K的状态。并且约定，状态S1，S2，Sj是按某种规则排列的，即对于子集 S1，S2 S2， S1来说，S的状态就是S1，S2；2M和N的输入字母表是相同的，即是；3转换函数D是这样定义的：D（S1，S2，Sj，a）R1，R2，Rj其中closure（Move（S1，S2，Sj，a）R1，R2，Rj；4S0closure（K0）为M的开始状态；5StSj，Sk，Se，其中Sj，Sk，SeS且Sj，Sk，SeKt下面给出构造NFA N的状态K的子集的算法。假定所构造的子集族为C，即C（T1，T2，Ti）其中T1，T2，Ti为状态K的子集。1 开始，令closure（K0）为C中唯一成员，并且它是未被标记的。2 While（C中存在尚未被标记的子集T）标记T； for每个输入字母a doU：=closure（Move（T，a）；if U不在C中 the a a b b b 图3-3-4 NFA N012435678910将U做为未被标记的子集加在C中 例5 应用上面的算法对图3-3-4的NFA N构造子集，步骤如下：1首先计算closure（0），令T0=closure（0）=0,1,2,4,7，T0未被标记，它现在是子集族C的唯一成员。2标记T0；令T1=closure（move(T0,a)）=1,2,3,4,6,7,8,将T1加入C中，T1未被标记。令T2=closure（move(T,b)）=1,2,4,5,6,7，将T2加入C中，它未被标记。3标记T1；计算closure（move(T1,a)），结果为1,2,3,4,6,7,8，即T1,T1已在C中。计算closure（move(T1,b)），结果为1,2,5,4,6,7,9，令其为T3,T3加至C中，它未被标记。4标记T2；计算closure（move(T2,a)），结果为1,2,3,4,6,7,8，即T1,T1已在C中。计算closure（move(T2,b)），结果为1,2,5,4,6,7，即T2,T2已在C中。5标记T3；计算closure（move(T3,a)），结果为1,2,3,4,6,7,8，即T1，T1已在C中计算closure（move(T3,b)），结果为1,2,5,4,6,7,10，令其为T4,加入C中，T4未被标记。6标记T4；计算closure（move(T4,a)），结果为1,2,3,4,6,7,8，即T1。计算closure（move(T4,b)）结果为1,2,3,4,6,7即T2。至此，算法终止共构造了五个子集：T0=0, 1, 2, 4, 7 T1=1, 2, 3, 4, 6, 7,8T2=1, 2, 4, 5, 6, 7 T3=1, 2, 4, 5, 6, 7,9 T4=1, 2, 4, 5, 6, 7,10那么图3-3-4的NFA构造的DFA M为1 S= T0， T1， T2， T3， T42 =a, b3 D（T0，a）=T1 D（T2，a）=T1D（T0，b）=T2D（T2，b）=T2D（T1，a）=T1D（T3，a）=T1D（T1，b）=T3 D（T3，b）=T4D（T4，a）=T1D（T4，b）=T24 S0=T05 St=T4 b b a b a b b a a a 图3-3-5 DFA M01342不防将 T0， T1， T2， T3， T4重新命名，以利于书写，或用A，B，C，D，E或用0，1，2，3，4分别表示。若采用后者，该DFA M状态转换图如图3-3-5所示。 还可采用矩阵的方法。令字母表只包含两个字符a和b。我们构造一张表，此表含有三列，分别标记为I、Ia、Ib。首先，置该表第一行第一列为CLOSURE（X），这是一个包含M的初态X的_闭包。一般来说，若某一行的第一列的状态子集已经确定下来，例如记为I；那么可根据上述的定义，求出这一行的第二和第三子集Ia和Ib。然后，检查Ia和Ib，看它们是否已在表的第一列中出现，将未曾出现者填入到下面空行的第一列位置上。其后，对未填入Ia和Ib的新行重复上述过程，直到所有的第二列和第三列的子集全部在第一列中出现过为止。上述过程必定在有限步里终止（因M的状态子集个数有限）。我们将已构造好的表看作是一张状态转换表，即把其中的每个子集看成是一个状态，这张表唯一刻划了一个确定有限自动机M；它的初态是该表的第一行第一列的那个-CLOSURE（X），它的终态就是那些含有原终态Y的子集。至此，已将非确定有限自动机M确定为确定的有限自动机M。如，例5构造的表如下所示：IIaIb0,1,2,4,703,8,6,7,1,2,415,6,1,2,4,723,8,6,7,1,2,413,8,6,7,1,2,415,9,6,7,1,2435,6,1,2,4,723,8,6,7,1,2,415,6,1,2,4 25,9,6,7,1,2,433,8,6,7,1,2,411,2,4,5,67,1041,2,4,5,6,7,1041,2,3,4,6,7,811,2,4,5,6,72 S0=0 St=4四、 确定有穷自动机的化简我们说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。所谓有穷自动机的多余状态，是指这样的状态：从该自动机的开始状态出发，任何输入串也不能到达的那个状态。对于给定的有穷自动机，如果它含有多余状态，可以非常简单地将多余状态消除，而得到与它等价的有穷自动机。在有穷自动机中，两个状态s和t等价的条件是：1 一致性条件状态s和t必须同时为可接受状态或不可接受状态。2 蔓延性条件对于所有输入符号，状态s和状态t必须转换到等价的状态里。我们介绍一个方法，叫做“分割法”，来把一个DFA（不含多余状态）的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。我们通过将此方法施于图3-3-6的DFA M上来做一介绍。 a a b a a a a a b b a b a a b b a a b b b b b b图3-3-6（a） 图3-3-6（b） b b b b b ( a ) ( b )图4.8 DFA M和DFA M1746530210426530 例6 将图形3-3-6(a)中的DFA M最小化。首先将M的状态分成两个子集：一个由终态（可接受态）组成，一个由非终态组成，这个初始划分P0为：P0=（1,2,3,4, 5,6,7），显然第一个子集中的任何状态都不与第二个子集中的状态等价。现在观察第一个子集1，2，3，4，在读入输入符号a后，状态3和4分别转换为第一个子集中所含的状态1和4，而1和2分别转换为第二个子集中所含的状态6和7，这就意味着1，2中的状态和3，4中的任何状态读入a后到达了不等价的状态，因此1，2中的任何状态与3，4中的任何状态都是可区别的，因此得到了新的划分P1如下：P1=（1，23，45，6，7）下面试图在P1中寻找一个子集和一个输入符号使得这个子集中的状态可区别，P1中的子集3，4对应输入符号a将再分割，而得到划分P2=1，2，3，4，5，6，7。P2中的5，6，7可由输入符号a或b而分割，得到划分P3=（1，2，3，4，5，6，7）。经过考察，P3不能再划分了。令1代表1，2消去2，令6代表6，7，消去7，我们便得到了图3-3-6（b）的DFA M，它是3-3-6（a）的DFA M的最小化。比起原来的有穷自动机，化简了的有穷自动机具有较少的状态，因而在计算机上实现起来将简洁些。第四节 正规式和有穷自动机的等价性正规式和有穷自动机的等价性由以下两点说明：1 对于上的NFA M，可以构造一个上的正规式R，使得L（R）=L（M）。2 对于上的每个正规式R，可以构造一个上的NFA M，使得L（M）=L（R）。首先介绍如何为上的NFA M构造相应的正规式R。我们把状态转换图的概念拓广，令每条弧可用一个正规式作标记。第一步，在M的状态转换图上加进两个结，一个为x结点，一个为y结点，从x结点用弧连接到M的所有初态结点，从M的所有终态结点用连接到y结点。形成一个与M等价的M，M只有一个初态x和一个终态y。第二步，逐步消去M中的所有结点，直至只剩下x和y结点。在消结过程中，逐步用正规式来标记弧。其消结的规则如下：1对于 R1 R2 代之为： R1 R2 12313R12对于 代之为： R1|R2R21212 R2 3对于 R1 R3代之为： R1R*2R312313 最后x和y结点间的弧上的标记则为所求的正规式R。例7 以例4的NFA M为例，M的状态图在图3-3-3，求正规式R，使L（R）=L（M）。第一步，加x和y结点，形成如图3-4-1（a）所求的M第二步，逐步消去M的结点，消去1和3之后如图3-4-1（b）所示；再消去点2和4后如图3-4-1（c）所示，最后只剩下x和y结点如图3-4-1（d）所示。R=（a | b）*（aa | bb）（a | b）*即为所求。 a|b a|b aa bb a|b（b）x042y a,b a,b a a b b a,b（a）x03142y a|b aa(a|b)* bb(a|b)*（c）x0y (a|b)*(aa|bb)(a|b)*（d）xy图3-4-1从NFAM构造正规式R下面介绍从上的一个正规式R构造上的一个NFAM，使得L（M）=L（R）的方法。首先把正