编译3词法分析2

1、编译原理编译原理(第三版第三版) 陈火旺等编著22022-6-223.3 3.3 正规表达式与有限自动机正规表达式与有限自动机n几个概念几个概念: :考虑一个考虑一个有穷有穷 字母表字母表 ( (字符集字符集) )其中每一个元素称为一个其中每一个元素称为一个字符字符上的上的字字( (也叫也叫字符串字符串) ) 是指由是指由中的字符所中的字符所构成的一个有穷序列构成的一个有穷序列不包含任何字符的序列称为不包含任何字符的序列称为空字空字，记为，记为用用* *表示表示上的所有字的全体上的所有字的全体, ,包含空字包含空字例如例如: 设设 =a a， b b，则，则 *=,a,b,aa,ab,ba,b

2、b,aaa,.,a,b,aa,ab,ba,bb,aaa,.32022-6-22n*的子集的子集U和和V的的连接连接（积积）定义为）定义为UV | U & V V自身的自身的 n次积记为次积记为Vn=VVVn规定规定V0= ，令，令 V*=V0V1V2V3 称称V*是是V的的;n记记 VVV* ，称，称V+是是V的正规闭包。的正规闭包。42022-6-223.3.1 正规式和正规集正规式和正规集n正规集正规集可以用可以用正规表达式正规表达式（简称（简称正规式正规式）表示。表示。n正规表达式正规表达式是表示是表示正规集正规集一种方法。一一种方法。一个字集合是个字集合是正规集正规集当且仅当它能用当且

3、仅当它能用正规正规式式表示。表示。52022-6-22n正规式和正规集的递归定义：正规式和正规集的递归定义：对给定的字母表对给定的字母表 1) 和和都是都是 上的正规式，它们所表示的正规上的正规式，它们所表示的正规集为集为 和和;2) 任何任何a ，a是是 上的正规式，它所表示的上的正规式，它所表示的正规集为正规集为a ;62022-6-223) 假定假定e1和和e2都是都是 上的正规式，它们所表示的上的正规式，它们所表示的正规集为正规集为L(e1)和和L(e2)，则，则i) (e1|e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为 L(e1) L(e2)，ii) (e1 e2)

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

5、*b*)*=(a|b)*L( (ba)*b) = L(ba)*) L(b)= (L(ba)*L(b) = (L(b)L(a)* L(b) = 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)*b82022-6-22n对正规式，下列等价成立：对正规式

6、，下列等价成立：e1|e2 = e2|e1 交换律交换律e1 |(e2|e3) = (e1|e2)|e3 结合律结合律e1(e2e3) = (e1e2)e3 结合律结合律e1(e2|e3) = e1e2|e1e3 分配律分配律(e2|e3)e1 = e2e1|e3 e1分配律分配律e = e = e （e1e2 e2 e1 ） L(e1|e2) = L(e1 ) L(e2)= L(e2 ) L(e1)= L(e2|e1)92022-6-22正规集正规集正规式正规式3.3.1102022-6-223.3.2 确定有限自动机确定有限自动机(DFA)n对状态图进行形式化，则可以下定义：对状态图进行形

7、式化，则可以下定义：自动机自动机M是一个五元式是一个五元式M=(S, , f, S0, F),其中：其中：1. S: 有穷有穷状态集状态集，2. ：输入字母表：输入字母表(有穷有穷)，3. f: 状态转换函数，为状态转换函数，为SS的单值部分映射，的单值部分映射，f(s，a)=s。表示：当现行状态为表示：当现行状态为s，输入字符，输入字符为为a时，将状态转换到下一状态时，将状态转换到下一状态s。我们把。我们把s称称为为s的一个后继状态。的一个后继状态。4. S0 S是唯一的一个初态；是唯一的一个初态； 5. F S ：终态：终态集集(可空，识别不出的字符串可空，识别不出的字符串)。112022

8、-6-22n例如：例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：其中：f定义如下：定义如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=3ab012132213333状态转换矩阵状态转换矩阵0312aaaa状态转换图状态转换图bbbb122022-6-22nDFA可以表示为状态转换图。假定可以表示为状态转换图。假定DFA M含有含有m个状态和个状态和n个输入字符，那么，这个输入字符，那么，这个图含有个图含有m个状态结点，每个结点顶多含个状态结点，每个结点顶多含有有n条箭弧射出，且每条箭弧用

9、条箭弧射出，且每条箭弧用上的不同上的不同的输入字符来作标记。的输入字符来作标记。132022-6-22n对于对于 * *中的任何字中的任何字 ，若存在一条从初态，若存在一条从初态到某一终态的道路，且这条路上所有弧上到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于的标记符连接成的字等于 ，则称，则称 为为DFA M所所识别识别(接收接收)nDFA M所识别的字的全体记为所识别的字的全体记为L(M)。n可以证明：可以证明： 上的字集上的字集 V V* * 是正规集，是正规集，当且仅当存在当且仅当存在 上的上的DFA M，使得，使得VL(M)。142022-6-223.3.3 3.3.3

10、非确定有限自动机非确定有限自动机(NFA) n定义：一个非确定有限自动机定义：一个非确定有限自动机(NFA) M是是一个五元式一个五元式M=(S, M=(S, , , f, S, S0 0, F), F)，其中：，其中：1 S: 有穷状态集；有穷状态集；2 ：输入字母表：输入字母表(有穷有穷)；3 f: 状态转换函数，为状态转换函数，为S*2S的部分映的部分映 射射(非单值，非单值，S的子集映射的子集映射)；4 S S0 0 S S是非空的初态是非空的初态集集；5 F S S ：终态集：终态集(可空可空)。152022-6-22n从状态图中看从状态图中看NFA 和和DFA的区别：的区别： 1

11、弧上的标记可以是弧上的标记可以是 *中的一个字，而不中的一个字，而不一定是单个字符；一定是单个字符； 2 同一个字可能出现在同状态射出的多条同一个字可能出现在同状态射出的多条弧上。弧上。nDFA是是NFA的特例。的特例。162022-6-22021 a，baaa，bbba，b012abab识别所有含相继两个识别所有含相继两个a或相继两个或相继两个b的字的字ambn | m，n 1172022-6-22n定义：对于任何两个有限自动机定义：对于任何两个有限自动机M和和M，如果如果L(M)=L(M)，则称，则称M与与M等价。等价。n自动机理论中一个重要的结论：判定两个自动机理论中一个重要的结论：判定

12、两个自动机等价性的算法是存在的。自动机等价性的算法是存在的。n对于每个对于每个NFA M存在一个存在一个DFA M，使得，使得 L(M)=L(M)。亦即。亦即DFA与与NFA描述能力描述能力相同。相同。182022-6-221. 假定假定NFA M=，我们对，我们对M的的状态转换图进行以下改造：状态转换图进行以下改造： 1) 引进新的初态结点引进新的初态结点X和终态结点和终态结点Y，X,Y S， 从从X到到S0中任意状态结点连一条中任意状态结点连一条 箭弧，箭弧， 从从F中任意状态结点连一条中任意状态结点连一条 箭弧到箭弧到Y。 2) 对对M的状态转换图进一步施行替换，其中的状态转换图进一步施

13、行替换，其中k是是新引入的状态。新引入的状态。证明证明:192022-6-22代之为代之为ikABjijAB代之为代之为ijA|BijBA代之为代之为ijA*ik jA按下面的三条规则对转换图进行分裂按下面的三条规则对转换图进行分裂:202022-6-22n逐步把这个图转变为每条弧只标记为逐步把这个图转变为每条弧只标记为 上的上的一个字符或一个字符或 ，最后得到一个，最后得到一个NFA M，显，显然然L(M)=L(M)212022-6-22n识别所有含相继两个识别所有含相继两个a或相继两个或相继两个b的字的字XY 514236ab ababab5126ab abaabb222022-6-222

14、. 把上述把上述NFA确定化确定化采用子集法采用子集法.n 设设I是的状态集的一个子集，定义是的状态集的一个子集，定义I的的 -闭闭包包 -closure(I)为为: i) 若若s I，则，则s-closure(I)； ii) 若若s I，则从则从s出发经过任意条出发经过任意条 弧而能到弧而能到达的任何状态达的任何状态s都属于都属于 -closure(I) 即即 -closure(I) = I s|从某个从某个s I出发经出发经过任意条过任意条 弧能到达弧能到达s232022-6-22n设设a是是 中的一个字符，定义中的一个字符，定义Ia= -closure(J) 其中，其中，J为为I中的某个

15、状态出发经过一条中的某个状态出发经过一条a弧而到达的状态集合。弧而到达的状态集合。242022-6-22n -closure(1)=1，2=I J=5，4，3 Ia= -closure(J)= -closure(5，4，3) =5，4，3，6，2，7，861a 234578aa n设设a是是 中的一个中的一个字符，定义字符，定义Ia= -closure(J) 其中，其中，J为为I中的某中的某个状态出发经过个状态出发经过一条一条a弧而到达弧而到达的状态集合。的状态集合。252022-6-22n确定化的过程确定化的过程: : 不失一般性，设字母表只包含两个不失一般性，设字母表只包含两个: a: a

16、和和b b，我们构造一张表，我们构造一张表: :IIaIb -Closure(X)262022-6-22首先，置第首先，置第1行第行第1列为列为 -closure(X), 求出求出它的它的Ia，Ib；然后，检查这两个然后，检查这两个Ia，Ib，看它们是否已在，看它们是否已在表中的第一列中出现，把未曾出现的填入表中的第一列中出现，把未曾出现的填入后面的空行的第后面的空行的第1列上，求出每行第列上，求出每行第2，3列列上的集合上的集合.重复上述过程，直到所有第重复上述过程，直到所有第2，3列子集全列子集全部出现在第一列为止。部出现在第一列为止。272022-6-22IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY 514236ab ababab282022-6-22n现在把这张表看成一个状态转换矩阵，把现在把这张表看成一个状态转换矩阵，把其中