《第2章 词法分析12第三次》由会员分享，可在线阅读，更多相关《第2章 词法分析12第三次（49页珍藏版）》请在金锄头文库上搜索。
1、第第2 2章章 词法分析词法分析 第第2章章 词法分析词法分析 2.1 词法分析器设计方法词法分析器设计方法 2.2 一个简单的词法分析器示例一个简单的词法分析器示例 2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介 2.4 正规表达式到有限自动机的构造正规表达式到有限自动机的构造 2.5 词法分析器的自动生成词法分析器的自动生成 第第2 2章章 词法分析词法分析 2.3 正规表达式与有限自动机简介正规表达式与有限自动机简介 2.3.1 正规表达式与正规集1、正规表达式：单词符号结构的形式化表示方法，精确地定义了单词符号集。简称为正规式，它表示的集合即为正规集。第第2 2章章 词法
2、分析词法分析 例如：letter(letterdigit)*标识符的正规式标识符集-正规式所表示的正规集第第2 2章章 词法分析词法分析 2 2、对对于于给给定定的的字字母母表表，正正规规式式和和正正规集的递归定义如下：规集的递归定义如下：(1)(1)和和都都是是上上的的正正规规式式，所所表表示示的的正规集分别为正规集分别为和和。(2)(2)(2) (2) 对对任任一一个个aa，a a是是上上的的一一个个正规式，它所表示的正规集为正规式，它所表示的正规集为aa。第第2 2章章 词法分析词法分析 (3) (3) 如如果果R R和和S S是是上上的的正正规规式式，它它们们所所表表示的正规集分别为示
3、的正规集分别为L(R)L(R)和和L(S)L(S)，则：则： RSRS是是上的正规式，它所表示的正上的正规式，它所表示的正规集为规集为L(R)L(S)L(R)L(S)； R.SR.S是是上的正规式，它所表示的正上的正规式，它所表示的正规集为规集为L(R) L(S)L(R) L(S)； (R)*(R)*是是上上的的正正规规式式，它它所所表表示示的的正正规集为规集为(L(R)*(L(R)*；第第2 2章章 词法分析词法分析 R R也也是是上上的的正正规规式式，它它所所表表示示的正规集为的正规集为L(R)L(R)。(4) (4) 仅仅由由有有限限次次使使用用规规则则(1)(1)(3)(3)得得到到的
4、的表表示示式式是是上上的的正正规规式式，它它所所表表示的集合是示的集合是上的正规集。上的正规集。第第2 2章章 词法分析词法分析 说明：说明： 规规则则(1)(1)、(2)(2)为为基基础础规规则则，规规则则(3)(3)为为归归纳纳规规则则，规规则则(4)(4)是是界界限限规规则则或或终止规则。终止规则。 上上的的一一个个字字是是指指由由中中的的字字符符所所构成的一个有穷序列；构成的一个有穷序列；第第2 2章章 词法分析词法分析 空字：空字：。* * ：表表示示上上所所有有字字的的全全体体，也也在其中。在其中。： 例例如如，若若=a=a，bb，则则* *=，a a，b b，aaaa，abab，
5、baba，bbbb，aaaaaa， 。第第2 2章章 词法分析词法分析 3、正规式间的运算符正规式间的运算符“”：表示或：表示或“ ”：表示连接（通常可省略）：表示连接（通常可省略）“* *”：表示闭包：表示闭包 RS=RS=RR &S &S 第第2 2章章 词法分析词法分析 R R0 0=R R* *=R=R0 0RR1 1RR2 2RR3 3，则则称称R R* *是是R R的的闭包闭包R+=RRR+=RR* *，R R+ +是是R R的的正则闭包正则闭包。上上的的正正规规式式R R和和S S，如如果果它它所所表表示示的的正正规规集集L(R)=L(S)L(R)=L(S)，则则称称R R和和S
6、 S等等价价并并记为记为R=SR=S。第第2 2章章 词法分析词法分析 正规式具有下列性质：正规式具有下列性质：(1) (1) 交换律：交换律：RS = SRRS = SR。(2) (2) 结合律：结合律：R(ST) = (RS)TR(ST) = (RS)T； R(ST) = (RS)TR(ST) = (RS)T。 (3) (3) 分配律：分配律：R(ST) = RSRTR(ST) = RSRT； (RS)T = RTST(RS)T = RTST。 (4) (4) 同一律：同一律：R = R = RR = R = R。第第2 2章章 词法分析词法分析 例例2.1 令令=a,b，上的正规式上的正
7、规式 R = (ab)*a S = a(ba)*试求其表示的正规集。试求其表示的正规集。 解答解答第第2 2章章 词法分析词法分析 2.3.2 2.3.2 有限自动机有限自动机 FA FA 有限自动机（有限自动机（FAFA）是更一般化的状态是更一般化的状态转换图，分为确定有限自动机转换图，分为确定有限自动机DFADFA和非和非确定有限自动机确定有限自动机NFANFA第第2 2章章 词法分析词法分析 1 1确定有限自动机（确定有限自动机（DFADFA） DFA DFA M Md d是一个是一个五元组五元组 M M d d= =（S, f, sS, f, s0 0, Z, Z），），(1)S(1)
8、S是是一一个个有有限限状状态态集集，它它的的每每一一个个元元素称为一个状态；素称为一个状态；(2) (2) 是一个是一个有穷输入字母表有穷输入字母表，它的每，它的每一个元素称为一个输入字符；一个元素称为一个输入字符； 第第2 2章章 词法分析词法分析 (3)f(3)f是是一一个个从从S S到到S S的的单单值值映映射射，f f(s(si i,a,a)= )= s sj j；s si i、s sj jSS和和aa；(4)s(4)s0 0SS，是是惟一的一个初态惟一的一个初态；(5)Z (5)Z 包含于包含于S S，是一个是一个终态集终态集。 DFA DFA M Md d有有三三种种表表示示形形式
9、式：五五元元组组形形式、状态转换图、状态转换矩阵式、状态转换图、状态转换矩阵第第2 2章章 词法分析词法分析 例例2.4 2.4 假定假定 DFA DFA M Md d=(s=(s0 0，s s1 1，s s2 2 ，aa，bb，f f，s s0 0，ss2 2)，且有：，且有：f(sf(s0 0，a)=sa)=s1 1 f(s f(s0 0，b)= sb)= s2 2f(sf(s1 1，a)=sa)=s1 1 f(s f(s1 1，b)= sb)= s2 2 f(sf(s2 2，a)=sa)=s2 2 f(s f(s2 2，b)= sb)= s1 1第第2 2章章 词法分析词法分析 （1 1
10、）DFADFA的状态转换图的状态转换图第第2 2章章 词法分析词法分析 （2 2）DFADFA状态转换矩阵状态转换矩阵 字符 状态abs0s1s2s1s1s2s2s2s1第第2 2章章 词法分析词法分析 2 2非确定有限自动机非确定有限自动机(NFA)(NFA)NFA NFA M Mn n MnMn=(S,f,Q,Z)=(S,f,Q,Z)，其中：其中：(1)S(1)S、Z Z的意义与的意义与DFADFA相同；相同；(2)f(2)f是一个从是一个从S S*到到S S的子集映射；的子集映射；(3)Q(3)Q包含于包含于S S，是一个非空初态集。是一个非空初态集。 第第2 2章章 词法分析词法分析
11、例例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 2章章 词法分析词法分析 表2.3 状态转换矩阵 字符 状态abs0s2s0，s1s1s2s2s1第第2 2章章 词法分析词法分析 2.4 2.4 正规表达式到有限自动机的构造正规表达式到有限自动机的构造 2.4.1 2.4.1 由由正正规规表表达达式式构构造造等等价价的的NFA NFA M M方法如下：方法如下：(1
12、)(1)将将正正规规表表达达式式R R表表示示成成如如图图2 21010所所示的拓广转换图。示的拓广转换图。(2) (2) 对正规表达式采用如图对正规表达式采用如图2-112-11所示所示的三条转换规则来构造的三条转换规则来构造NFA MNFA M。 第第2 2章章 词法分析词法分析 图2-10 拓广转换图第第2 2章章 词法分析词法分析 图2-11 转换规则 第第2 2章章 词法分析词法分析 例例2.6 对给定正规表达式对给定正规表达式 (a b)*(aa bb)(a b)* 构造其构造其NFA M。 第第2 2章章 词法分析词法分析 2.4.2 NFA M2.4.2 NFA M的确定化的确
13、定化我们采用我们采用子集法子集法来对来对NFA MNFA M确定化。确定化。首先定义首先定义FA MFA M的一个状态子集的一个状态子集I I的的_闭包闭包，即，即_CLOSURE(I)_CLOSURE(I)，则：则：(1) (1) 若若s si iII，则，则s si i_CLOSURE(I_CLOSURE(I) )；(2) (2) 若若s si iII，则则对对从从sisi出出发发经经过过通通路路所所能能到到达达的的任任何何状状态态s sj j，都都有有s sj j_CLOSURE(I_CLOSURE(I) )。 其其次次对对FA FA M M的的一一个个状状态态子子集集I I，若若a a
14、是是中的一个字符，定义中的一个字符，定义 I Ia a= =_CLOSURE(J_CLOSURE(J) )其其中中，J J是是所所有有那那些些可可以以从从I I中中的的某某一一状状态态出出发发经经过过有有向向边边a a而而能能到到达达的的状状态态集集第第2 2章章 词法分析词法分析 例例2.7 已已知知一一状状态态转转换换图图如如下下图图所所示示，且且假假定定I=_1=1，2，试试求求从从状状态态I出出发发经经过过一一条条有有向向边边a而而能能到到达达的的状状态态集集J和和_CLOSURE(J)。第第2 2章章 词法分析词法分析 第第2 2章章 词法分析词法分析 用子集法对用子集法对NFA确定
15、化的方法如下：确定化的方法如下：(1)构构造造一一张张转转换换表表，其其第第一一列列为为状状态态子子集集I，对对不不同同的的a (a)在在表表中中单单设一列设一列Ia。(2)表表 的的 第第 一一 行行 第第 一一 列列 其其 状状 态态 子子 集集 I为为 _CLOSURE(s0)；其中，；其中，s0为初始状态。为初始状态。第第2 2章章 词法分析词法分析 1.(3) 根根据据第第一一列列中中的的I为为每每一一个个a求求其其Ia并并记记入入对对应应的的Ia列列中中，如如果果此此Ia不不同同于于第第一一列列已已存存在在的的所所有有状状态态子子集集I，则将其顺序列入空行中的第一列。则将其顺序列入
16、空行中的第一列。 (4) 重重复复步步骤骤（3）直直至至对对每每个个I及及a均均已已求求得得Ia，并并且且无无新新的的状状态态子子集集Ia加加入入第第一一列列时时为为止止；此此过过程程可可在在有有限步后终止。限步后终止。第第2 2章章 词法分析词法分析 (5) 重重新新命命名名第第一一列列的的每每一一状状态态子子集集，则则转转换换表表便便成成为为新新的的状状态态转转换换矩矩阵阵，其其状状态态转转换换函函数数f是是S到到S的的单单值值映映射，即为与射，即为与NFA M等价的等价的DFA M。 第第2 2章章 词法分析词法分析 例例2.8正规表达式正规表达式（a b）*(aa bb)(a b)*的
17、的NFA M如如图图214所所示示，试试将将其其确确定定化化为为DFA M。 第第2 2章章 词法分析词法分析 解答解答 用子集法将图用子集法将图2-14所示的所示的NFA M确定化为表确定化为表2.4。 对对表表2.4中中的的所所有有子子集集重重新新命命名名，得得到到表表2.5的的状状态态转转换换矩矩阵阵及及对对应应的的状状态态转换图转换图(见图见图2-15)。第第2 2章章 词法分析词法分析 图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,31,2
18、,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章章 词法分析词法分析 图215 例2.8未化简的DFA M第第2 2章章 词法分析词法分析 表2.5 例2.8的状态转换矩阵 Sab012132214335464564635第第2 2章章 词法分析词法分析 2.4.3 DFA M的化简的化简 DFA M化化简简:是是指指寻寻找找一一个个状状态态数数比比M少少的的DFA M，使使得
19、得L(M)=L(M)。DFA M 满足下述两个条件：满足下述两个条件： (1) 没有多余状态；没有多余状态； (2) 在其状态集中，没有两个相互等在其状态集中，没有两个相互等价的状态存在。价的状态存在。 第第2 2章章 词法分析词法分析 两两个个状状态态相相互互等等价价：对对给给定定的的DFA M，若若存存在在状状态态s1、s2S且且s1s2，如如果果从从s1出出发发能能识识别别字字符符串串而而停停于于终终态态，从从s2出出发发也也同同样样能能够够识识别别这这个个而而停停于于终终态态；反反之之，若若从从s2出出发发能能识识别别而而停停于于终终态态，则则从从s1出出发发也也能能识识别别这这个个而
20、而停停于于终终态态，则则称称s1和和s2是是等价的，否则就是可区分的。等价的，否则就是可区分的。第第2 2章章 词法分析词法分析 一个一个DFA M的状态最小化过程是将的状态最小化过程是将M的状态集分割成一些不相交的子集，的状态集分割成一些不相交的子集，使得任何不同的两个子集其状态都使得任何不同的两个子集其状态都是可区分的，而同一子集中的任何是可区分的，而同一子集中的任何两个状态都是等价的。两个状态都是等价的。 第第2 2章章 词法分析词法分析 DFA M的化简方法如下：的化简方法如下：(1) 首首先先将将DFA M的的状状态态集集S中中的的终终态态与与非非终终态态分分开开，形形成成两两个个子
21、子集集，即即得得到基本划分。到基本划分。第第2 2章章 词法分析词法分析 (2) 对对当当前前已已划划分分出出的的I(1)、I(2)、I(m) 子子集集（属属于于不不同同子子集集的的状状态态是是可可区区分分的的），看看每每一一个个I是是否否能能进进一一步步划划分分；也也即即对对某某个个I(i)=s1,s2,sk，若若存存在在一一个个输输入入字字符符a（a）使使得得Ia(i)不不全全包包含含在在当当前前划划分分的的某某一一子子集集I(j)中中（即即跨跨越越到到两两个个子子集集），就将就将I(i)一分为二（见图一分为二（见图216）。）。第第2 2章章 词法分析词法分析 图216 是否划分示意(a
22、) 无需划分；(b) 需要划分第第2 2章章 词法分析词法分析 (3) 重重复复步步骤骤(2)，直直到到子子集集个个数数不不再再增增加加为为止止（即即每每个个子子集集已已是是不不可可再再分分的的了了）。所所谓谓不不能能划划分分，是是指指该该子子集集或或者者仅仅有有一一个个状状态态，或或者者虽虽有有多多个个状状态态但但这这些些状状态态均均不不可可区区分分（即等价）。（即等价）。 第第2 2章章 词法分析词法分析 例例2.9 化简由例化简由例2.8得到的得到的DFA。 解解答答 (1) 首首先先将将状状态态集集S=0，1，2，3，4，5，6划划分分为为终终态态集集3，4，5，6和和非非终终态态集集
23、0，1，2。 (2) 考考 察察 0， 1， 2a： 因因0a=2a=1，而而1a=3，分分属属于于非非终终态态集集和和终终态态集集，故故将将0,1,2划分为划分为0，2和和1。 (3) 考考察察0，2b：0b=2，2b=4，它它们们分分属属于于两两个个不不同同的的状状态态集集，故故0，2划划分分为为0和和2。第第2 2章章 词法分析词法分析 (4) 考察考察3,4,5,6a：3a=6a=33,4,5,6；4a=5a=63,4,5,6，即都属于终态集，故不进行划分。即都属于终态集，故不进行划分。 (5) 考察考察3,4,5,6b：3b=6b=53,4,5,6；4b=5b=43,4,5,6，即都属于终态集，故不进行划分。即都属于终态集，故不进行划分。 (6) 按按 顺顺 序序 重重 新新 命命 名名 状状 态态 子子 集集 0、 1、 2、3,4,5,6为为0、1、2、3，则则得得到到化化简简后后的的状状态态转转换换矩矩阵（见表阵（见表2.6）和）和DFA M (见图见图217)。第第2 2章章 词法分析词法分析 表2.6 例2.9的状态转换矩阵 Sab012132213333第第2 2章章 词法分析词法分析 图217 例2.9化简后的DFA M
