第3讲词法分析精选PPT.ppt

《第3讲词法分析精选PPT.ppt》由会员分享，可在线阅读，更多相关《第3讲词法分析精选PPT.ppt（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3讲词法分析第1页，本讲稿共94页3.1 词法分析程序的设计词法分析程序的设计词法分析（词法分析（lexical analysis）逐个读入源程序字符并按照构词规则切分成一系逐个读入源程序字符并按照构词规则切分成一系 列单词。列单词。词法分析是编译过程中的一个阶段，在语法分词法分析是编译过程中的一个阶段，在语法分 析前进行。也可以和语法分析结合在一起作为析前进行。也可以和语法分析结合在一起作为 一遍，由语法分析程序调用词法分析程序来获一遍，由语法分析程序调用词法分析程序来获 得当前单词供语法分析使用。得当前单词供语法分析使用。单词单词是语言中具有独立意义的是语言中具有独立意义的最小单位最小单

2、位，包括保留字、标识符、运算符、标点符号和常包括保留字、标识符、运算符、标点符号和常量等。量等。第2页，本讲稿共94页一、词 法 分 析 程 序源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序Tokenget token.主要任务：主要任务：读源程序，产生单词符号读源程序，产生单词符号 其他任务：其他任务：滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序，追踪换行标志，复制出错源程序，宏展开，宏展开，第3页，本讲稿共94页二、二、单单 词词 符符 号号单词符号一般可分为下列五种：单词符号一般可分为下列五种：1、基本字、基本字（关键字关键字）：）：b

3、egin,end,if,while,var 等等2、标识符、标识符：各种名称，如常量名、变量名、过程名等：各种名称，如常量名、变量名、过程名等3、常数、常数（量）：（量）：25,3.1415,TRUE,“ABC”等等4、运算符、运算符：如：如+，-，*，/，201:=202*203试分析输入串：IF a10 THEN b1:=c1*d1 ELSE b1:=5经词法分析后的输出。第6页，本讲稿共94页解：输出的单词串为：(1,_)(101,a1)(201,_)(102,0)(2,_)(101,b1)(202,_)(101,c1)(203,_)(101,d1)(3,_)(101,b1)(202,_

4、)(102,5)第7页，本讲稿共94页词法分析工作独立的原因：词法分析工作独立的原因：简化设计简化设计改进编译效率改进编译效率增加编译系统的可移植性增加编译系统的可移植性 第8页，本讲稿共94页3.2 单单 词词 的的 描描 述述 工工 具具正规文法：正规文法：文法文法G=（VN，VT，P，S），），P中每一产生式中每一产生式的的形式都为：形式都为：AaB AaB 或或 AaAa，（右线型文法右线型文法）或或 ABa ABa 或或 AaAa，（左线型文法左线型文法）其中：其中：AVAVN N ，BVBVN N ，aV aVT T第9页，本讲稿共94页一、一、几几 类类 单单 词词 的的 描描

5、述述标识符标识符：标识符标识符 l|l字母数字字母数字 字母数字字母数字 l|d|l字母数字字母数字|d 字母数字字母数字 无符号整数无符号整数：无符号整数无符号整数 d|d无符号整数无符号整数运算符运算符：运算符运算符+|-|*|/|=|界符界符：界符界符,|;|(|)|其中：其中：l 表示字母；表示字母；d表示数字表示数字第10页，本讲稿共94页无符号实数无符号实数：无符号实数无符号实数 d 余留无符号数余留无符号数|.十进小数十进小数|e指数部分指数部分 余留无符号数余留无符号数 d 余留无符号数余留无符号数|.十进小数十进小数|e指数部分指数部分|十进小数十进小数 d 余留十进小数余留

6、十进小数余留十进小数余留十进小数 e指数部分指数部分|d 余留十进小数余留十进小数|指数部分指数部分 d 余留整指数余留整指数|s整指数整指数整指数整指数 d 余留整指数余留整指数余留整指数余留整指数 d 余留整指数余留整指数|其中其中s表示正或负号。表示正或负号。如如 25.55e+5 和和 2.1第11页，本讲稿共94页二、正二、正 规规 式式(regular expression)定义定义（正规式正规式和它所表示的和它所表示的正规集正规集）：）：设字母表为设字母表为，辅助字母表，辅助字母表 =，。1、和和 都是都是 上的正规式，它们所表示的上的正规式，它们所表示的 正规集分别为正规集分别

7、为 和和 ；2、任何、任何 a ，a 是是 上的一个正规式，它所上的一个正规式，它所 表示的正规集为表示的正规集为 a；第12页，本讲稿共94页3、假定假定e1和和e2都是都是 上的正规式，它们所表示的正规集分上的正规式，它们所表示的正规集分别为别为L(e1)和和L(e2)，那么，那么，(e1),e1 e2,e1 e2,e1 也都是也都是正规式正规式,它们所表示的正规集分别为它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和和(L(e1)。4、仅由有限次使用上述三步骤而定义的表达式才是、仅由有限次使用上述三步骤而定义的表达式才是 上的正规上的正规式，仅由这些正规式

8、所表示的字集才是式，仅由这些正规式所表示的字集才是 上的正规集。上的正规集。第13页，本讲稿共94页其中其中“”读为读为“或或”（也有使用（也有使用“+”代替代替“”的）；的）；“”读为读为“连接连接”；“”读为读为“闭包闭包”(即，任意有限次的自重复连接即，任意有限次的自重复连接)。在不致混淆时，括号可省去。在不致混淆时，括号可省去。规定算符的优先顺序为规定算符的优先顺序为“”、“”、“”。连接符连接符“”一般可省略不写。一般可省略不写。“”、“”和和“”都是左结合的。都是左结合的。第14页，本讲稿共94页例例4.2 令令=a，b，上的正规式和相应的正规上的正规式和相应的正规集的例子有：集的

9、例子有：正规式正规式正规集正规集a a a b a,b ab ab(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 组成组成 的串的串 第15页，本讲稿共94页例例 =l，d，r=l(l d)定义的正规集定义的正规集:l,ll,ld,ldd,（标识符）标识符）例例4.3 =d，.，e，+，-,则则 上的正规上的正规式式 d(.dd )(e(+-)dd )表示的表示的是

10、无符号数的集合。其中是无符号数的集合。其中d为为09的数字。的数字。第16页，本讲稿共94页 例：正规式(1+10)*的正规集是什么？解：正规式解：正规式(1+10)*所表述的句子是：所表述的句子是：,1,10,110,101,11,1110,1011,1,10,110,101,11,1110,1011,该正规式代表所有以该正规式代表所有以1开始且没有两个连开始且没有两个连续的续的0的的0，1串的集合。串的集合。第17页，本讲稿共94页 例：最多只有两个相继的1的0，1串的正规表达式。解：对不包含相继的解：对不包含相继的1的所有的所有0和和1字符串字符串的集合，正规表达式为：的集合，正规表达式

11、为：1(0+01)*或或(0+10)*1包含最多一对相继的包含最多一对相继的1的所有的所有0和和1字符串字符串的集合，正规表达式为：的集合，正规表达式为：(0+10)*11(0+01)*所以，正规表达式为：所以，正规表达式为：1(0+01)*+(0+10)*1+(0+10)*11(0+01)*第18页，本讲稿共94页三、三、正正 规规 式式 等等 价价若两个正规式若两个正规式e1和和e2所表示的所表示的正规集相同正规集相同,则说则说e1和和e2等价等价,写作写作e1=e2。例如：例如：e1=(a b)，e2=b a又如：又如：b(ab)=(ba)b(a b)=(a b)第19页，本讲稿共94页

12、四、四、正正 规规 式式 的的 运运 算算 律律设设 r,s,t 为正规式，正规式服从的代数规律有：为正规式，正规式服从的代数规律有：1、r s=s r“或或”服从交换律服从交换律2、r(s t)=(r s)t“或或”的可结合律的可结合律3、(rs)t=r(st)“连接连接”的可结合律的可结合律4、r(s t)=rs rt (s t)r=sr tr 分配律分配律 5、r=r,r =r 是是“连接连接”的恒等元素的恒等元素6、r r=r r =r rr“或或”的抽取律的抽取律第20页，本讲稿共94页五、正规文法和正规式的等价变换五、正规文法和正规式的等价变换对对 上的正规式上的正规式 r,存在一

13、个存在一个G=(VN,VT,P,S)使得使得 L(G)=L(r)，反之亦然。反之亦然。第21页，本讲稿共94页1.将将 正正 规规 式式 转转 换换 成成 正正 规规 文文 法法 VT=,S VN，生成正规产生式生成正规产生式 S r (1)对形如对形如 A xy 的的正规产生式：正规产生式：A xB B y （B VN）(2)对形如对形如Ax y的的正规产生式：正规产生式：A xA A y (3)对形如对形如Ax y的的正规产生式正规产生式:A x A y 不断应用上述规则做变换，直到每个产生式最多含一个不断应用上述规则做变换，直到每个产生式最多含一个终结符。终结符。第22页，本讲稿共94页

14、例：将例：将 r=a(a d)转换成相应的正规文法。转换成相应的正规文法。GS:SaA AaA AdA AVT=a,d Sa(a d)SaAA(a d)A(ad)A AAaA AdA第23页，本讲稿共94页2.将将 正正 规规 文文 法法 转转 换换 成成 正正 规规 式式 文法产生式文法产生式文法产生式文法产生式 正规式正规式正规式正规式 （1）A xB,B y A=xy（2）A xA y A=x y（3）A x y A=x y第24页，本讲稿共94页Gs:S aA A aA A dA S a A a A d S=aA a A =aA dA a d =(a d)A(a d)=(a d)(a

15、d)S=a(a d)(a d)a =a(a d)(a d)=a(a d)R=a(a d)第25页，本讲稿共94页有文法有文法GS:SaS,SaB,BbC,CaC,Ca第26页，本讲稿共94页3.3 有有 穷穷 自自 动动 机机确定的有穷自动机（确定的有穷自动机（DFA）不确定的有穷自动机（不确定的有穷自动机（NFA）NFA DFA 的转换的转换DFA的化简的化简第27页，本讲稿共94页状态转换图（状态图）状态转换图（状态图）状态转换图是一张有限方向图。用结点代表状态，状态转换图是一张有限方向图。用结点代表状态，状态之间用箭弧连接，箭弧上的标记（字符）代状态之间用箭弧连接，箭弧上的标记（字符）代

16、表在射出状态下可能出现的输入字符或字符类。表在射出状态下可能出现的输入字符或字符类。一个状态转换图只包含有限个状态，有一个初态一个状态转换图只包含有限个状态，有一个初态（用（用标识标识），至少有一个终态（用双圈表示）。），至少有一个终态（用双圈表示）。ST字母字母或数字S：初态；T：终态；第28页，本讲稿共94页一、一、DFA 的的的的 定定定定 义义义义 DFADFA定义定义定义定义：一个确定的有穷自动机（：一个确定的有穷自动机（DFA）M是一个是一个五元组：五元组：M=（K，f，S，Z）其中其中:1 1。K K 是一个有穷集，是一个有穷集，状态集状态集,它的每个元素称为一个状态；它的每个元

17、素称为一个状态；2 2。是一个有穷字母表，它的每个元素称为一个输入符号，所以也称是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为为输入符号表输入符号表；3 3。f f 是是转换函数转换函数，是在，是在 KK 上的映射，即，如上的映射，即，如 f（ki，a）=kj，（，（kiK，kjK）就意味着，当前状态为就意味着，当前状态为ki，输入符为输入符为 a 时，将转换为下一个状态时，将转换为下一个状态 kj，我们把我们把 kj 称作称作 k ki 的一个后继状态；的一个后继状态；4。S SK K 是唯一的一个是唯一的一个初态初态；5 5。Z Z K 是一个是一个终态集终态集，终态也称，终态

18、也称可接受状态可接受状态或或结束状态结束状态。第29页，本讲稿共94页1.DFA 示 例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第30页，本讲稿共94页2.DFA 的的 状状 态态 图图 表示表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V,b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb第31页，本讲稿共94页3.DFA 的的 矩矩 阵阵 表表 示示f（S，a）=Uf

19、（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q字符字符状态状态0100第32页，本讲稿共94页*上的符上的符号号串串 t 在在 M 上运行上运行一个输入符一个输入符号号串串t，（，（我们将它表示成我们将它表示成t1tx的形式，其的形式，其中中t1，tx*）在）在DFA M上上运行运行的定义为：的定义为：f（Q，t1tx）=f（f（Q，t1），），tx）其中其中QK扩充转换函数扩充转换函数f f，是是K*K上的映射，且：上的映射，且：f（Q，）=Q递归定义递归定义第33页，本讲稿共94页4.*上的符上的符号号串串 t 被被 M 接受

20、接受对于对于*中的任何字符串中的任何字符串t，若存在一条从初态结点到某一若存在一条从初态结点到某一终态结点的道路，且这条路上所有弧的的标记符连接成的终态结点的道路，且这条路上所有弧的的标记符连接成的字符串等于字符串等于t，则称则称t可为可为DFA M所接受，若所接受，若M的初态结的初态结点同时又是终态结点，则空字点同时又是终态结点，则空字()可为可为M所所接受接受（识别识别）。若若 t *，f(S，t)=P，其中其中 S 为为 DFA M 的开始状态，的开始状态，P Z，Z为终态集。为终态集。则称则称 t 为为 DFA M所所接受接受（识别识别）。）。第34页，本讲稿共94页例：证明例：证明

21、t=baab 被如下的被如下的 DFA 所接受所接受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第35页，本讲稿共94页bSUVQaaaba，bb证明：证明：f（S，baab）=f（f（S，b），），aab）=f（V，aab）=f（f（V，a），），ab）=f（U，ab）=f（f（U，a），），b）=f（Q，b）=QQ属于终态。得证。属于终态。得证。第36页，本讲稿共94页5.确定的有穷自动机（确定的有穷自动机（DFA）接受的语言）

22、接受的语言DFA M=（K，f，S，Z）所能接所能接受的符号串的全体记为受的符号串的全体记为 L(M)L(M)=x|f(S,x)Z,x 结论：结论：上一个字符串集上一个字符串集 V 是正规的，是正规的，当且仅当，存在一个当且仅当，存在一个 上的确定有穷上的确定有穷自动机自动机 M，使得使得 V=L(M)。第37页，本讲稿共94页DFA M=（K，f，S，Z）的行为的模拟程序的行为的模拟程序K:=S；c:=getchar;while ceof do K:=f(K,c);if K=then break else c:=getchar;if K is in Z then return(yes)els

23、e return(no)第38页，本讲稿共94页二、不确定的有穷自动机二、不确定的有穷自动机NFA定义定义N=(K，f，S，Z)，其中其中K为状态为状态的有的有穷非空穷非空集集，为为有穷输入有穷输入字母表字母表，f为映射为映射函数函数，f:K *2K，S K是初是初始状始状态态集集，Z K为终为终止状止状态集态集。第39页，本讲稿共94页1.状状 态态 图图 表表 示示例例:NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中：f（S，0）=P f（S，1）=S，Zf（P，1）=Z f（Z，0）=Pf（Z，1）=PSPZ00,1111第40页，本讲稿共94页2.矩矩 阵阵 表表 示示简化

24、为简化为例：例：NFA N=（S，P，Z，0，1，f，S，P，Z）其中：其中：f（S，0）=P f（S，1）=S，Z f（P，1）=Z f（Z，0）=P f（Z，1）=P第41页，本讲稿共94页*上的符上的符号号串串t在在NFA N上运行。上运行。*上的符上的符号号串串t被被NFA N接受（识别）。接受（识别）。具有具有 转移的不确定的有穷自动机转移的不确定的有穷自动机 NFAf为为 K （）到）到2K的的映射。的的映射。对任何一个具有对任何一个具有 转移的不确定的有穷自动机转移的不确定的有穷自动机NFA N，一定存在一个不具有一定存在一个不具有 转移的不确定的有穷自动转移的不确定的有穷自动机

25、机NFA，使得，使得L(M)=L(N)。第42页，本讲稿共94页例：NFA N01234aabba,ba,ba,bN所能识别的那些含有相继两个所能识别的那些含有相继两个a或相继两个或相继两个b的串。的串。第43页，本讲稿共94页NFA与DFA的区别NFA有一个开始状态集，而有一个开始状态集，而DFA只有一只有一个初态；个初态；NFA的映射是多值映射，而的映射是多值映射，而DFA是一个是一个单值映射；单值映射；第44页，本讲稿共94页三、三、NFA 的的 确确 定定 化化DFA是是NFA的特例的特例.对每个对每个NFA M一定存一定存在一个在一个DFA ，使得，使得 L(M)=L(M)。对每个对

26、每个NFA M存在着与之存在着与之等价等价的的DFA M 。与某一与某一NFA等价的等价的DFA不唯一。不唯一。第45页，本讲稿共94页1.定义对状态集合定义对状态集合I的几个有关运算的几个有关运算1 状态集合状态集合 I 的的 -闭包，表示为闭包，表示为 -closure(I)，定义为一定义为一状态集，是状态集状态集，是状态集 I 中的任何状态中的任何状态 R 经经任意条任意条 弧弧而能而能到达的状态的集合。到达的状态的集合。状态集合状态集合I的任何状态的任何状态 R 都属于都属于 -closure(I)。2 状态集合状态集合 I 的的 a 弧转换，表示为弧转换，表示为 move(I,a)定

27、义为状态集定义为状态集合合 J，其中其中 J 是所有那些可从是所有那些可从 I 的某一状态经过的某一状态经过一条一条 a 弧弧而到达的状态的全体。而到达的状态的全体。3 定义：定义：Ia =-closure(J)，其中：，其中：J=move(I,a)第46页，本讲稿共94页例例I=1,-closure(I)=1,2；I=5,-closure(I)=5,6,2；move(1,2,a)=5,4,3-closure(5,3,4)=5,4,3,6,2,8,7；15243687aaa第47页，本讲稿共94页2.NFA 到 DFA 的 等 价 变 换 算 法假设假设 NFA N=(K,f,K0,Kt)按如

28、下办法构造按如下办法构造一个一个 DFA M=(S,d,S0,St)，使得使得L(M)=L(N)：1.M的状态集的状态集S由由K的一些子集组成。用的一些子集组成。用S1 S2.Sj表示表示S的元素，其中的元素，其中S1,S2,.Sj是是K的状态。并且约定，状态的状态。并且约定，状态S1,S2,.Sj是按某种规则排列的，即对于子集是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，来说，S的状态就是的状态就是S1 S2；第48页，本讲稿共94页2.M和和N的输入字母表是相同的，即是的输入字母表是相同的，即是；3.转换函数是这样定义的：转换函数是这样定义的：D(S1,S2,.,Sj,a)=

29、R1,R2,.,Rt其中其中：R1,R2,.,Rt=-closure(move(S1,S2,.,Sj,a)4.S0=-closure(K0)为为M的开始状态；的开始状态；5.St=Si,Sk,.,Se|Si,Sk,.,Se S 且且 Si,Sk,.Se Kt 第49页，本讲稿共94页构造构造NFA N的状态的状态K的子集的算法：的子集的算法：假定所构造的子集族为假定所构造的子集族为C，即即C=(T1,T2,.TI),其中其中T1,T2,.TI为状态为状态K的子集。的子集。1.开始，令开始，令-closure(K0)为为C中唯一成员，中唯一成员，并且它是未被标记的。并且它是未被标记的。第50页，

30、本讲稿共94页2.while（C中存在尚未被标记的子集中存在尚未被标记的子集T）do 标记标记T；for 每个输入字母每个输入字母a do U:=-closure(move(T,a)；if U不在不在C中中 then 将将U作为未标记的子集加在作为未标记的子集加在C中中 第51页，本讲稿共94页例，将下图的例，将下图的NFA N转换成转换成DFA M023456789101bbbaaNFA N第52页，本讲稿共94页023456789101bbbaa-closure(move(Ti,a)-closure(move(Ti,b)T0=-closure(0)=0,1,2,4,71,2,3,4,6,7

31、,8加入为T11,2,4,5,6,7 加入为T2T1=1,2,3,4,6,7,81,2,3,4,6,7,8 已存在T11,2,4,5,6,7,9 加入为T3T2=1,2,4,5,6,71,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2T3=1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7,10 加入为T4T4=1,2,4,5,6,7,10 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2第53页，本讲稿共94页-closure(move(Ti,a)-closure(move(Ti,b)T0=-closure(

32、0)=0,1,2,4,71,2,3,4,6,7,8加入为T11,2,4,5,6,7 加入为T2T1=1,2,3,4,6,7,81,2,3,4,6,7,8 已存在T11,2,4,5,6,7,9 加入为T3T2=1,2,4,5,6,71,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2T3=1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7,10 加入为T4T4=1,2,4,5,6,7,10 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2初态终态b02134abaaaabbbDFA M第54页，本讲稿共94页将下图

33、NFA确定化：SQVUZ0，110，1110001第55页，本讲稿共94页四、四、DFA 的最小化（化简）的最小化（化简）最小状态最小状态DFA没有多余状态没有多余状态(死状态死状态)没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别）两个状态两个状态s和和t等价：满足等价：满足一致性一致性同是终态或同是非终态同是终态或同是非终态蔓延性蔓延性从从s出发读入某个出发读入某个a a和和从从 t出发出发读入某个读入某个a到达的状到达的状态等价。态等价。第56页，本讲稿共94页消消 除除 多多 余余 状状 态态s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0

34、s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7第57页，本讲稿共94页如图，状态0和4是可区别的。状态2和3是可区别的，因为读入b后分别到达2和4，而2和4不是等价的。DFA Mb02134abaaaabbb第58页，本讲稿共94页对于一个对于一个DFA M=DFA M=（K,f,kK,f,k0 0,k,kt t)，存

35、在一个存在一个最小最小状态状态DFA M=（K K,f,f,k,k0 0,k,kt t)，使使L(M)=L(M).算法的核心：算法的核心：把把M的状态集的状态集K分成不相交的子集分成不相交的子集。结论结论接受接受L的最小状态有穷自动机不计同构是唯一的。的最小状态有穷自动机不计同构是唯一的。第59页，本讲稿共94页最小化方法最小化方法-分割法分割法把一个把一个DFA（不含多余状态）的状态分（不含多余状态）的状态分成一些不相交的子集，使得任何不同的成一些不相交的子集，使得任何不同的两个子集的状态都是可区分的，而同一两个子集的状态都是可区分的，而同一个子集中的任何两个状态都是等价的。个子集中的任何两

36、个状态都是等价的。第60页，本讲稿共94页将下图中的将下图中的DFA M最小化最小化1,2 3,4 5 6,71,2 3 4 5 6,713546aaaaabbbbb 1,2,3,4,5,6,7Ia:6,7,1,4,7,4,4Ib:3,3,5,6,3,1,21,2,3,4 5,6,71352746aaaaaaabbbbbbb第61页，本讲稿共94页五、五、正规式正规式和有穷自动机的等价性和有穷自动机的等价性1.对于对于上的上的NFA M，可以构造一个，可以构造一个上的正规式上的正规式R,R,使得使得L(R)=L(M)。2 2.对于对于上的一个正规式上的一个正规式R，可以构造，可以构造一个一个上

37、的上的NFA M，使得，使得L(M)=L(R)。第62页，本讲稿共94页1.对于对于上的上的NFA M，可以构造一个，可以构造一个上的正规上的正规式式R,R,使得使得L(R)=L(M)。第一步：在第一步：在M的状态转换图上的状态转换图上加进两个结点加进两个结点，一个为，一个为x结结点，一个为点，一个为y结点。从结点。从x结点用结点用弧连接到弧连接到M的的所有初态所有初态结点结点，从，从M的的所有终态结点所有终态结点用用弧连接到弧连接到y结点。形成一结点。形成一个与个与M等价的等价的M,M只有只有一个初态一个初态x和和一个终态一个终态y。第二步：逐步消去第二步：逐步消去M中的所有结点，直至只剩下

38、中的所有结点，直至只剩下x和和y。（消去规则见下页）消去规则见下页）最后最后x和和y结点间的弧上的标记则为所求的正规式结点间的弧上的标记则为所求的正规式R。第63页，本讲稿共94页123R1R213R1 R213R1R213R1|R2123R1R3R213R1 R2*R3第64页，本讲稿共94页例：求该求该NFA所对应的正规式所对应的正规式R.03124a,baaa,ba,bbb第65页，本讲稿共94页03124a,baaa,ba,bbbxy024a|baaa|ba|bbbxy第66页，本讲稿共94页a|b024a|baaa|bbbxy0a|baa(a|b)*bb(a|b)*xy第67页，本讲

39、稿共94页0a|baa(a|b)*bb(a|b)*xyxy(a|b)*(aa|bb)(a|b)*0a|bxyaa(a|b)*|bb(a|b)*(aa|bb)(a|b)*R=(a|b)*(aa|bb)(a|b)*第68页，本讲稿共94页2 2.对于对于上的一个正规式上的一个正规式R，可以构造一个，可以构造一个上的上的NFA M，使得，使得L(M)=L(R)。(1)R=,任一具有空终态集的任一具有空终态集的NFA M(2)R=，NFA M=(k0,f,k,f,k0 0,kk0 0):):f f（k k0 0,a),a)对于对于 所有所有a 都没定义。都没定义。(3)R=a,NFA M=,NFA M

40、=(k0,k1,f,k,f,k0 0,kk1 1):f():f(k0,a)=k1xyk0k1ak0第69页，本讲稿共94页 (4)R=R1|R2,分别将步骤（分别将步骤（1）（）（2）（）（3）应用到）应用到R1,R2 产生产生M1=(K1,1,f,f1,k,k1,F,F1),M2=(K2,2,f,f2,k,k2,F,F2),),其中其中K K1,K,K2不相交不相交.则，则，NFA M=NFA M=(K1 K2 k0,f,k,f,k0,F),F)，k k0是新增加的状态符号是新增加的状态符号:=1 2；f f=f=f1 f f2 f(kf(k0,)=k)=k1,k,k2；F=F1 F2k0k

41、1M1k2M2第70页，本讲稿共94页 (5)R=R1 R2,分别将步骤分别将步骤(1)(2)(3)应用到应用到R1,R2 产生产生M1=(K1 1,1 1,f,f1 1,k,k1 1,F,F1 1),M2=(K2 2,2 2,f,f2 2,k,k2 2,F,F2 2),),K K1 1,K,K2 2不相交不相交.则，则，NFA MNFA M =(K1 1 K2 2,1 1 2 2,f,f,k k1,F,F2 2 ):):f f=f1=f1 f2f2 对对F F1 1中的所有终态中的所有终态k k有：有：f1(k,f1(k,)=k2 2 。k1M1k2M2第71页，本讲稿共94页(6)R=R*

42、,分别将步骤分别将步骤(1)(2)(3)应用到应用到R 产生产生M1=(K1 1,f,f1 1,k,k1 1,F,F1 1).).则，则，NFA M=NFA M=(K1 k0 0，kf f,f,f,k k0 0,k kf f):):k0 0，kf f是新增加的状态符号，是新增加的状态符号，f f=f=f1 1 f(f(k0 0,)=)=kf f，f(f(k k0 0,)=)=k k1 1 f(f(k,)=)=kf f ：k k F F1 1 f(k,)=k1：k F F1 1k1M1kfk0kf第72页，本讲稿共94页例例:为为 R=(a|b)*abb 构造构造NFA N，使得使得 L(N)=

43、L(R)。23a54bR=(a|b)*abbR=(a|b)*abbR=(a|b)*abb2354ab16第73页，本讲稿共94页R=(a|b)*abbR=(a|b)*abb继续加上abb即可得到结果。2354ab162354ab1607第74页，本讲稿共94页R=(a|b)*abb继续对abb进行分解。xjyabbiabxjyabbia|bxiy(a|b)*abb第75页，本讲稿共94页为正规式为正规式 dd*(.dd*|)(e(+|-|)dd*|)构造构造NFA.1234675dd.ddee+-ddd第76页，本讲稿共94页例：下图例：下图NFA所接受的字符串所接受的字符串ABaab接受字符

44、串的 的NFA第77页，本讲稿共94页SCDBAaaaaabbbbb写出下图自动机所表示的语言。第78页，本讲稿共94页六、正规文法和有穷自动机间的转换六、正规文法和有穷自动机间的转换1.采用下面的规则从正规文法采用下面的规则从正规文法G=(VT,VN,S,P)直接构造一个直接构造一个有穷自动机有穷自动机NFA M=(,K,f,k0,Z)，使得：使得：L(M)=L(G)：字母表与字母表与 G 的终结符集相同，的终结符集相同，=VT；增加一个新状态增加一个新状态kf，作为作为NFA的终态，的终态，Z=kf；G中的每个非终结符作中的每个非终结符作为为M的一个状态，的一个状态，(不妨取称相同的名字不

45、妨取称相同的名字),K=VN kf；G的开的开始符号为始符号为M的开始状态，的开始状态，k0=S；对对G中的形如中的形如AaB的产生式（其中的产生式（其中a为终结符或为终结符或，A和和B为非终结符）为非终结符），构造，构造M的一个转换函数的一个转换函数f(A,a)=B；对对G中形如中形如Aa的产生式的产生式,构造构造M的一个转换函数的一个转换函数f(A,a)=Z。右线性文法右线性文法第79页，本讲稿共94页例例1：与文法：与文法GS等价的等价的NFA M(右线性右线性)GS：SaASbBSAaBAbABaSBbABSABZaabbab第80页，本讲稿共94页采用下面的规则将一个有穷自动机采用下

46、面的规则将一个有穷自动机NFA M转换转换成正规文法成正规文法G，使得，使得L(G)=L(M)：G的终结符集与字母表相同；的终结符集与字母表相同；M的每一个状态对应的每一个状态对应G中的每个非终结符中的每个非终结符,开始状态开始状态S是是G的开始符号的开始符号；转换函数转换函数f(A,a)=B对应对应G中的形如中的形如AaB的产生式（其中的产生式（其中a为终结符或为终结符或，A和和B为非终结符）为非终结符）；对终态结点对终态结点Z,对应对应G中形如中形如Z的产生式的产生式。第81页，本讲稿共94页例例:为下面的为下面的DFA N，构造出等价的正规文法构造出等价的正规文法G。文法GA：AaB|b

47、DBbCCaA|bD|DaB|bD|BCabADaabbb第82页，本讲稿共94页SCDBAaaaaabbbbb写出下图自动机所表示的语言。可得可得GS:S aA|bCA aB|bS|B aB B aB|bAC aS|bDD aA|bC|第83页，本讲稿共94页用消元法表示出下列文法的语言用消元法表示出下列文法的语言GS:S0A|1B|0 A0A|1B|0S B 1B|1|0第84页，本讲稿共94页七、词法分析程序的自动构造工具七、词法分析程序的自动构造工具把正规式转换为一个把正规式转换为一个NFA进而转换为相进而转换为相应的应的DFA，由此构造出词法分析程序。由此构造出词法分析程序。LEX编

48、译系统编译系统第85页，本讲稿共94页对对DFA编程实现词法分析：编程实现词法分析：关键点：根据状态设计程序关键点：根据状态设计程序if语句语句或或switch语句语句While循环语句循环语句return语句语句词法分析程序编程词法分析程序编程第86页，本讲稿共94页实验题目实验题目针对下面文法针对下面文法G(S)：S v=E EE+EE-EE*EE/E（E）v i其中，其中，v为标识符，为标识符，i为整型或实型数。为整型或实型数。要求完成要求完成 使用自动机技术实现一个词法分析程序；使用自动机技术实现一个词法分析程序；使用算符优先分析方法实现语法分析程序，在语使用算符优先分析方法实现语法分

49、析程序，在语法分析过程中完成常量表达式的计算。法分析过程中完成常量表达式的计算。第87页，本讲稿共94页实验过程实验过程实验的本质内容：实验的本质内容：写程序模拟自动机实现过程，完成赋值写程序模拟自动机实现过程，完成赋值语句中单词识别，构造单词二元组语句中单词识别，构造单词二元组-词词法分析；法分析；计算一个赋值语句计算一个赋值语句-语法分析（语法分析（ch5，ch6）。）。第88页，本讲稿共94页词法分析实现词法分析实现 单词分类：单词分类：标识符：标识符：v常量：常量：i运算符：运算符：+，-，*，/，（，），（，）分隔符：分隔符：=作为赋值语句的作为赋值语句的标记标记第89页，本讲稿共9

50、4页 文法描述：文法描述：S+|-|*|/|(|)|=|lA|dBA lA|dA|B dB|dC|B dB|dC|C d D|.F|eG D d D|.F|eG|F d HH eG|d H|G d J|sKK d JJ d J|词法分析实现词法分析实现其中:l表示小写字母，d表示09，s表示正或负号第90页，本讲稿共94页 12348+_*ll,d 自动机：自动机：词法分析实现词法分析实现 编程编程第91页，本讲稿共94页词法分析的自动机技术应用：词法分析的自动机技术应用：输入的有效性检查；输入的有效性检查；面向对象的软件测试技术；面向对象的软件测试技术；UMLUML的活动图，时序图；的活动图