第2章词法分析3

1、第第2 2章章 词法分析词法分析 第第2章章 词法分析词法分析 2.1 词法分析器设计方法词法分析器设计方法 2.2 一个简单的词法分析器示例一个简单的词法分析器示例 2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介 2.4 正规表达式到有限自动机的构造正规表达式到有限自动机的构造 2.5 词法分析器的自动生成词法分析器的自动生成 第第2 2章章 词法分析词法分析 2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介 2.3.1 正规表达式与正规集正规表达式与正规集 正规表达式是一种形式化的表示法，表示单词符号的正规表达式是一种形式化的表示法，表示单词符号的结构结构，从而精

2、确地定义单词符号集。正规表达式简称，从而精确地定义单词符号集。正规表达式简称为正规式，它表示的集合即为正规集。为正规式，它表示的集合即为正规集。 letter (letter digit)*-标识符的正规式，标识符的正规式， 标识符集标识符集-正规式所表示的正规集。正规式所表示的正规集。第第2 2章章 词法分析词法分析 对于给定的对于给定的字母表字母表，正规式和正规集的递归定义如下：，正规式和正规集的递归定义如下： 和和都是都是上的正规式，所表示的正规集分别为上的正规式，所表示的正规集分别为和和。 对任一个对任一个a，a是是上的一个正规式，它所表示的正规集为上的一个正规式，它所表示的正规集为a

3、。 (3) 如果如果R和和S是是上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为L(R)和和L(S)，则：，则： R S是是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为L(R)L(S)； R.S是是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为L(R) L(S)； (R)*是是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为(L(R)*； R也是也是上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为L(R)。(4) 仅由有限次使用规则仅由有限次使用规则(1)(3)得到的表示式是得到的表示式是上的正规式，上的正规式，它所

4、表示的集合是它所表示的集合是上的正规集。上的正规集。第第2 2章章 词法分析词法分析 说明：说明： 规则规则(1)、(2)为基础规则，规则为基础规则，规则(3)为归纳规则，规则为归纳规则，规则(4)是是界限规则或终止规则。界限规则或终止规则。 上的一个字是指由上的一个字是指由中的字符所构成的一个有穷序列；中的字符所构成的一个有穷序列； 不包含任何字符的序列称为不包含任何字符的序列称为空字空字，用，用表示。表示。 *表示表示上所有字的全体，则空字上所有字的全体，则空字也在其中。也在其中。 表示不含任何元素的表示不含任何元素的空集空集 例如，若例如，若=a，b，则，则*=，a，b，aa，ab，ba

5、，bb，aaa，。第第2 2章章 词法分析词法分析 正规式间的运算符正规式间的运算符 “ ”表示或表示或 “ ”表示连接（通常可省略）表示连接（通常可省略） “*”表示闭包，使用括号可以改变运算的次序。表示闭包，使用括号可以改变运算的次序。*的正规式的正规式R和和S的连接可以形式化地定义为的连接可以形式化地定义为 RS= R&S 即集合即集合RS中的字是由中的字是由R和和S中的字连接而成的，且中的字连接而成的，且R自身的自身的n次连接记为次连接记为 n 个 Rn=RRR 第第2 2章章 词法分析词法分析 R0= R*=R0R1R2R3，则称，则称R*是是R的的闭包闭包 R+=RR*，并

6、称，并称R+是是R的的正闭包正闭包。对于对于上的正规式上的正规式R和和S，如果它所表示的正规集，如果它所表示的正规集L(R)=L(S)，则称则称R和和S等价等价并记为并记为R=S。正规式具有下列性质：正规式具有下列性质： (1) 交换律：交换律：R S = S R。 (2) 结合律：结合律：R (S T) = (R S) T； R(ST) = (RS)T。 (3) 分配律：分配律：R (S T) = RS RT； (R S)T = RT ST。 (4) 同一律：同一律：R = R = R。第第2 2章章 词法分析词法分析 例例2.1 令令=a,b，设，设R=(ab)*a、 S= a(ba)*是

7、是上的正规上的正规式，试求其表示的正规集。式，试求其表示的正规集。 解答解答第第2 2章章 词法分析词法分析 2.3.2 有限自动机有限自动机 有限自动机（有限自动机（FA）是更一般化的状态转换图）是更一般化的状态转换图 确定有限自动机确定有限自动机DFA 非确定有限自动机非确定有限自动机NFA 1确定有限自动机（确定有限自动机（DFA） 一个确定的有限自动机一个确定的有限自动机Md（记为（记为DFA Md）是一个）是一个五元组五元组M d=（S, f, s0, Z），其中：），其中： (1) S是一个是一个有限状态集有限状态集，它的每一个元素称为一个状态；，它的每一个元素称为一个状态； (2

8、) 是一个是一个有穷输入字母表有穷输入字母表，它的每一个元素称为一个输入，它的每一个元素称为一个输入字符；字符； 第第2 2章章 词法分析词法分析 (3) f是一个从是一个从S到到S的单值映射，即的单值映射，即f (si , a)=sj且有且有si、sjS和和a； (4) s0S，是，是惟一的一个初态惟一的一个初态； (5) Z ( S，是一个，是一个终态集终态集。 DFA Md有三种表示形式：五元组形式、状态转换图、状态有三种表示形式：五元组形式、状态转换图、状态转换矩阵转换矩阵例例2.4 假定假定DFA Md=(s0，s1，s2，a，b，f，s0，s2)，且有：，且有： f(s0，a)=

9、s1 f(s0，b)= s2 f(s1，a)= s1 f(s1，b)= s2 f(s2，a)= s2 f(s2，b)= s1第第2 2章章 词法分析词法分析 DFA的状态转换图与状态转换矩阵表示的状态转换图与状态转换矩阵表示 （1）假定）假定DFA有有m个状态、个状态、n个输入字符（或字），个输入字符（或字），则这个状态转换图含有则这个状态转换图含有m个状态，每个状态最多有个状态，每个状态最多有n条条输出边与其它状态相连接，每一条输出边用输出边与其它状态相连接，每一条输出边用（或（或*）中的一个不同的输入字符（或一个输入字）作标记，中的一个不同的输入字符（或一个输入字）作标记，整个图含有惟一一

10、个初态（或多个初态）和若干个终整个图含有惟一一个初态（或多个初态）和若干个终态。态。 （2）DFA也可以用状态转换矩阵表示。状态转换矩阵也可以用状态转换矩阵表示。状态转换矩阵的行表示状态，列表示输入符号，矩阵元素表示的行表示状态，列表示输入符号，矩阵元素表示f(si，a)的值。的值。第第2 2章章 词法分析词法分析 s12 s2s0aabbab第第2 2章章 词法分析词法分析 表2.2 状态转换矩阵 字符 状态abs0s1s2s1s1s2s2s2s1第第2 2章章 词法分析词法分析 2非确定有限自动机非确定有限自动机(NFA) 一个非确定有限自动机一个非确定有限自动机Mn（记为（记为NFA M

11、n）是一个）是一个五元组五元组Mn=(S,f,Q,Z)，其中：，其中： (1) S、Z的意义与的意义与DFA相同；相同； (2) f是一个从是一个从S*到到S的子集映射；的子集映射； (3) Q ( S，是一个非空初态集。，是一个非空初态集。 第第2 2章章 词法分析词法分析 例例2.5 假定假定 NFA Mn=(s0，s1，s2，a，b，f，s0，s2，s1)，且有：且有： f(s0，a)= s2 f(s0，b)= s0 ,s1 f(s1，a)= f(s1，b)= s2 f(s2，a)= f(s2，b)= s1 第第2 2章章 词法分析词法分析 2 s1s0s2bbbba第第2 2章章 词法

12、分析词法分析 表2.3 状态转换矩阵 字符 状态abs0s2s0，s1s1s2s2s1第第2 2章章 词法分析词法分析 2.4 正规表达式到有限自动机的构造正规表达式到有限自动机的构造 2.4.1 由正规表达式构造等价的由正规表达式构造等价的NFA M 由正规表达式构造等价的由正规表达式构造等价的NFA M的方法如下：的方法如下：(1) 将正规表达式将正规表达式R表示成如图表示成如图210所示的拓广转换图。所示的拓广转换图。(2) 对正规表达式采用如图对正规表达式采用如图2-11所示的三条转换规则来构所示的三条转换规则来构 NFA M。 第第2 2章章 词法分析词法分析 图2-10 拓广转换图

13、X2 YR第第2 2章章 词法分析词法分析 图2-11 转换规则 sisjr1 | r2sisjr1r2sisjr1*123sisjr1r2sisjskr1r2sisjskr1第第2 2章章 词法分析词法分析 例例2.6 对给定正规表达式对给定正规表达式 (a b)*(aa bb)(a b)*构造其构造其NFA M。 第第2 2章章 词法分析词法分析 2.4.2 NFA M的确定化的确定化我们采用我们采用子集法子集法来对来对NFA M确定化。确定化。 首 先 定 义首 先 定 义 FA M 的 一 个 状 态 子 集的 一 个 状 态 子 集 I 的的 _ 闭 包闭 包 ， 即， 即_CLOS

14、URE(I)，则：，则： (1) 若若siI，则，则si_CLOSURE(I)； (2) 若若siI，则对从，则对从si出发经过出发经过通路所能到达的任何状通路所能到达的任何状态态sj，都有，都有sj_CLOSURE(I)。 其次对其次对FA M的一个状态子集的一个状态子集I，若，若a是是中的一个字符，定中的一个字符，定义义 Ia=_CLOSURE(J)其中，其中，J是所有那些可以从是所有那些可以从I中的某一状态出发经过有向边中的某一状态出发经过有向边a而而能到达的状态集能到达的状态集第第2 2章章 词法分析词法分析 例例 2 . 7 已 知 一 状 态 转 换 图 如 下 图 所 示 ， 且

15、 假 定已 知 一 状 态 转 换 图 如 下 图 所 示 ， 且 假 定I=_1=1，2，试求从状态，试求从状态I出发经过一条有向边出发经过一条有向边a而能而能到达的状态集到达的状态集J和和_CLOSURE(J)。1524aa6378a第第2 2章章 词法分析词法分析 解答解答 从状态从状态I中的状态中的状态1或状态或状态2出发经过一条出发经过一条a弧而能到达的状态集弧而能到达的状态集J为为 5，3，4 若若siJ，则由，则由si出发经过任意条出发经过任意条有向边而能到达有向边而能到达的任何状态的任何状态sj_CLOSURE(J)，因此，因此_CLOSURE(J)为为 5，6，2，3，8，4

16、，7第第2 2章章 词法分析词法分析 用子集法对用子集法对NFA确定化的方法如下：确定化的方法如下： (1) 构造一张转换表，其第一列为状态子集构造一张转换表，其第一列为状态子集I，对不同的，对不同的a (a)在表中单设一列在表中单设一列Ia。 (2) 表的第一行第一列其状态子集表的第一行第一列其状态子集I为为_CLOSURE(s0)；其中，；其中，s0为初始状态。为初始状态。 (3) 根据第一列中的根据第一列中的I为每一个为每一个a求其求其Ia并记入对应的并记入对应的Ia列中，列中，如果此如果此Ia不同于第一列已存在的所有状态子集不同于第一列已存在的所有状态子集I，则将其顺序，则将其顺序列入

17、空行中的第一列。列入空行中的第一列。 (4) 重复步骤（重复步骤（3）直至对每个）直至对每个I及及a均已求得均已求得Ia，并且无新的，并且无新的状态子集状态子集Ia加入第一列时为止；此过程可在有限步后终止。加入第一列时为止；此过程可在有限步后终止。第第2 2章章 词法分析词法分析 (5) 重新命名第一列的每一状态子集，则转换表便成为重新命名第一列的每一状态子集，则转换表便成为新的状态转换矩阵，其状态转换函数新的状态转换矩阵，其状态转换函数f是是S到到S的单的单值映射，即为与值映射，即为与NFA M等价的等价的DFA M。 例例2.8 正规表达式（正规表达式（a b）*(aa bb)(a b)*

18、的的NFA M如图如图214所示，试将其确定化为所示，试将其确定化为DFA M。 解答解答 用子集法将图用子集法将图2-14所示的所示的NFA M确定化为确定化为表表2.4。 对表对表2.4中的所有子集重新命名，得到表中的所有子集重新命名，得到表2.5的状态的状态转换矩阵及对应的状态转换图转换矩阵及对应的状态转换图(见图见图2-15)。第第2 2章章 词法分析词法分析 34251X6abababab2 Y图214 例2.8的NFA M第第2 2章章 词法分析词法分析 表2.4 例2.8的转换表 IIaIbX,1,21,2,31,2,41,2,31,2,3,5,6,Y1,2,41,2,41,2,

19、31,2,4,5,6,Y1,2,3,5,6,Y1,2,3,5,6,Y1,2,4,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,4,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,3,5,6,Y1,2,4,6,Y第第2 2章章 词法分析词法分析 2 32 52 42 6120abbaabaabbaabb图215 例2.8未化简的DFA M第第2 2章章 词法分析词法分析 表2.5 例2.8的状态转换矩阵 Sab012132214335464564635第第2 2章章 词法分析词法分析 2.4.3 DFA M的化简的化简 对对NFA确定化后所得

20、到的确定化后所得到的DFA可能含有多余的状可能含有多余的状态，因此还应对其进行化简。所谓态，因此还应对其进行化简。所谓DFA M的化简，是的化简，是指 寻 找 一 个 状 态 数 比指 寻 找 一 个 状 态 数 比 M 少 的少 的 D FA M ， 使 得， 使 得L(M)=L(M)。化简了的。化简了的DFA M 满足下述两个条件：满足下述两个条件： (1) 没有多余状态；没有多余状态； (2) 在其状态集中，没有两个相互等价的状态存在。在其状态集中，没有两个相互等价的状态存在。 第第2 2章章 词法分析词法分析 所谓两个状态相互等价是指：对一给定的所谓两个状态相互等价是指：对一给定的DF

21、A M，若存在状态若存在状态s1、s2S且且s1s2，如果从，如果从s1出发能识别字符出发能识别字符串串而停于终态，从而停于终态，从s2出发也同样能够识别这个出发也同样能够识别这个而停而停于终态；反之，若从于终态；反之，若从s2出发能识别出发能识别而停于终态，则从而停于终态，则从s1出发也能识别这个出发也能识别这个而停于终态，则称而停于终态，则称s1和和s2是等价是等价的，否则就是可区分的。的，否则就是可区分的。 一个一个DFA M的状态最小化过程是将的状态最小化过程是将M的状态集分的状态集分割成一些不相交的子集，使得任何不同的两个子集其割成一些不相交的子集，使得任何不同的两个子集其状态都是可

22、区分的，而同一子集中的任何两个状态都状态都是可区分的，而同一子集中的任何两个状态都是等价的。是等价的。 第第2 2章章 词法分析词法分析 DFA M的化简方法如下：的化简方法如下： (1) 首先将首先将DFA M的状态集的状态集S中的终态与非终态分开，中的终态与非终态分开，形成两个子集，即得到基本划分。形成两个子集，即得到基本划分。 (2) 对当前已划分出的对当前已划分出的I(1)、I(2)、I(m) 子集（属于子集（属于不同子集的状态是可区分的），看每一个不同子集的状态是可区分的），看每一个I是否能进一步是否能进一步划分；也即对某个划分；也即对某个I(i)=s1,s2,sk，若存在一个输入字

23、，若存在一个输入字符符a（a）使得）使得Ia(i)不全包含在当前划分的某一子集不全包含在当前划分的某一子集I(j)中中（即跨越到两个子集），就将（即跨越到两个子集），就将I(i)一分为二（见图一分为二（见图216）。）。第第2 2章章 词法分析词法分析 图216 是否划分示意(a) 无需划分；(b) 需要划分(a)(b)s3s4s3s4s1s2s1s2s5aaaa第第2 2章章 词法分析词法分析 (3) 重复步骤重复步骤(2)，直到子集个数不再增加为止，直到子集个数不再增加为止（即每个子集已是不可再分的了）。所谓不能划分，（即每个子集已是不可再分的了）。所谓不能划分，是指该子集或者仅有一个状态

24、，或者虽有多个状态但是指该子集或者仅有一个状态，或者虽有多个状态但这些状态均不可区分（即等价）。这些状态均不可区分（即等价）。 那么，如何进行划分呢？假定当前子集那么，如何进行划分呢？假定当前子集I(i)=s1,s2,，且状态，且状态s1和和s2经过有向边经过有向边a分别到达状态分别到达状态t1和和t2，而，而t1和和t2又分属于当前已划分出的两个不同子集又分属于当前已划分出的两个不同子集I(j)和和I(k)，则此时应将，则此时应将I(i)分为两部分，使得一部分含有分为两部分，使得一部分含有s1： I(i1)=s sI(i)且且s经有向边经有向边a到达到达t1第第2 2章章 词法分析词法分析 而另一部分含有而另一部分含有s2： I(i2)=I(i) I(i1) 由于由于t1和和t2是可区分的，即存在一个字符串是可区分的，即存在一个字符串，t1将将读出读出而停于终态，而而停于终态，而t2或读不出或读不出或者可以读出或者可以