第三章词法分析 第2章主要内容回顾.ppt

《第三章词法分析 第2章主要内容回顾.ppt》由会员分享，可在线阅读，更多相关《第三章词法分析 第2章主要内容回顾.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2 2章主要内容回顾章主要内容回顾n文法的定义文法的定义：=(=(T T，N N，)n推导与归约推导与归约：n最左推导（左句型、最右归约）n最右推导（右句型、规范句型、规范（最左）归约）n语法树语法树n二义性二义性（定义）n文法的分类文法的分类n0型文法（短语结构文法）、1型文法（上下文有关文法）、2型文法（上下文无关文法）、3型文法（正则文法）1/9/20231第三章：词法分析第三章第三章 词法分析词法分析n单词的描述工具（正规表达式与正规集）单词的描述工具（正规表达式与正规集）n状态转换图与基本符号的识别状态转换图与基本符号的识别n有限自动机有限自动机n词法分析器的设计与实现词法分析器

2、的设计与实现本章主要内容：本章主要内容：1/9/20232第三章：词法分析3.1 3.1 单词的描述工具单词的描述工具n正规表达式与正规集的定义：正规表达式与正规集的定义：正规表达式也称正规式，是用以描述单词符号的方便工具，也是表示正规集的工具。n正规表达式的定义：正规表达式的定义：P52P52。设设是一个字母表，是一个字母表，是是上的上的RE，L()=；是是上的上的RE，L()=；对于对于 a，a是是RE，L(a)=a；如果如果r和和s是是RE，L(r)=R,L(s)=S，则：则：r与与s的的“或或”(r|s)是是RE，L(r|s)=RS；r与与s的的“连接连接”(rs)是是RE，L(rs)

3、=RS；r的克林闭包的克林闭包(r*)是是RE，L(r*)=R*。只有满足只有满足、的才是的才是RE。1/9/20233第三章：词法分析3.1 3.1 单词的描述工具单词的描述工具n一个由正规表达式表示的语言称为一个正规集。一个由正规表达式表示的语言称为一个正规集。n例例3-1，令=a,b,则上的正规式和正规集的例子有：正规式 正规集 a a a|b a,b ab ab (a|b)(a|b)aa,ab,ba,bb a*,a,aa,aaa任意个a组成的串的集合 a|a*b a,b,ab,aab,aaab含有符号串a和包括零个或多于零个的a后跟一个b的所有符号串形成的集合。(a|b)*,a,b,a

4、a,ab,ba,bb,aaa所有含a和b的符号串组成的集合。1/9/20234第三章：词法分析3.1 3.1 单词的描述工具单词的描述工具n两个正规表达式的等价：两个正规表达式的等价：P54。如果两个正规表达式表示同样的语言，则称这两个正规式是等价的。如(a|b)与(b|a),(a|b)*与(a*b*)*都是等价的。n正规表达式的正规表达式的运算优先级和代数规律运算优先级和代数规律:P54 *高于“连接”和|，“连接”高于|具有交换律、结合律 “连接”具有结合律、和对|的分配律 ()指定优先关系.意义清楚时，括号可以省略 是“连接”运算的恒等元素。n程序设计语言中的单词都能用正规表达式来定义。

5、比如，用l l来代表字母，d d代表数字，=l,d,则则r1=l(l|d)*表示的是标识符，r2=dd*则定义了无符号整数，r3=d*(.dd*|)(e(+|-|)dd*|)表示的是无符号数。1/9/20235第三章：词法分析3.1 3.1 单词的描述工具单词的描述工具n正规式与正规文法正规式与正规文法n上的正规式到正规文法上的正规式到正规文法G转换（特指右线性正规文法）：转换（特指右线性正规文法）：方法：方法：令其中的VT=；对于任何正规式r，选择S，生成Sr，然后按以下三条规则对Sr进行分解直到每个产生式最多含有一个终结符为止。并将并将S定为定为G的开始符号的开始符号；若x和y都是正规式，

6、对形如Axy的产生式重写为：A xB和B y两产生式，其中B是新选择的非终结符；对形如A x*y的产生式，重写为：A xA和A y 对形如A x|y的产生式，重写为：A x和A y1/9/20236第三章：词法分析3.1 3.1 单词的描述工具单词的描述工具例例3-2，将r=a(a|d)*转换成相应的正规文法：解解：令S为文法的开始符号，首先形成Sa(a|d)*然后对其进行分解，得到SaA和A(a|d)*,再对后条规则重写为：A（a|d)A和A，最终形成的文法G为：SaA AaA AdA A n将正规文法将正规文法G转换成转换成上的正规式：上的正规式：基本上是上述过程的逆过程，最后只剩下一个开

7、始符号定义的产生式，并且该产生式的右部不含非终结符，则此产生式的右部为所求。其转换规则如下：规则1：A xB,B y A xy 规则2：A xA|y A x*y 规则3：Ax,Ay A x|y1/9/20237第三章：词法分析3.1 3.1 单词的描述工具单词的描述工具例例3-3，将文法GS：S aA S a A aA A dA A a A d 转换为相应的正规表达式。解解：过程如下：S aA|a A aA|dA|a|d 可写为 A(aA|dA)|(a|d)可写为 A(a|d)A|(a|d)可写为 A(a|d)*(a|d)将其代入S可得：S a(a|d)*(a|d)|a a(a|d)*(a|d

8、)|)a(a|d)*即a(a|d)*为所求。1/9/20238第三章：词法分析3.2 3.2 状态转换图与基本符号的识别状态转换图与基本符号的识别n状态转换图的引进：状态转换图的引进：P63P63 通常，为了识别标识符，画出识别标识符的流程图如右图所示。现在引进“状态状态”这个概念，在开始状态开始状态下取得一个字母便处于标识符状态，如果后面取到的仍然是字母或数字，则继续处于标识符状态，直到不是字母或数字才离开标识符状态，根据此将其变成下面的图：入口字母？取字符字母？数字？出口出口否是是否是否2letterLetter,digit3其它其它终态终态1初态初态 状态转换图状态转换图是为了识别正规文

9、法的句子专门设计的有向图。它只包含有穷多个状态有穷多个状态，即有穷多个结点。（除了终止状态结点不代表任何非终结符号外）每个状态结点都代表每个状态结点都代表文法的非终结符号文法的非终结符号。状态之间用箭弧（或称状态之间用箭弧（或称有向边）连接有向边）连接。弧上的标记标记指明在射出弧的结点状态下可能出现的输入字符。1/9/20239第三章：词法分析3.23.2状态转换图与基本符号的识别状态转换图与基本符号的识别n状态转换图的构造：状态转换图的构造：P64P64n构造方法：构造方法：对于右线形正则文法，状态转换图构造步骤如下：以每个非终结符为状态结点，开始符号对应初态 S；增设一个终态 Z；对于规则

10、 AaB，画从状态 A 到 B 的弧，标记为 a；对于规则 Aa，画从状态 A 到终态 Z 的弧，标记为a。n例例3-4，为例3中所给的文法GS构造其转换图如下：Aaaa,dS初态初态dZ终态终态aS aAS aA aAA dAA aA d1/9/202310第三章：词法分析3.23.2状态转换图与基本符号的识别状态转换图与基本符号的识别n利用状态图识别句子的步骤如下：利用状态图识别句子的步骤如下：（=a=a1 1a a2 2aan n,a ai iVVT T)1.1.从从初初态态S S出出发发，并并自自左左至至右右逐逐个个扫扫描描中中的的各各个个字字符符，显然，在状态S之下所扫视的输入字符为

11、a a1 1，此时在结点S所射出的箭弧中寻找标记为a1的箭弧（如不存在，则表明有词法错误），读入读入a a1 1，并沿并沿箭弧所指的方向前进到下一个状态箭弧所指的方向前进到下一个状态；2.2.设在在状状态态A Ai i的的情情况况下下，所扫视的输入字符为ai+1,在结点Ai所射出的各箭弧中寻找标记为ai+1 的箭弧，读读入入a ai i+1+1，并并过过渡渡到到下一状态下一状态A Ai+1i+1;3.3.重重复复上上面面的的过过程程，直直到到中中全全部部字字符符读读完完且且进进入入终终态态Z Z时时，宣告整个识别结束，已被接受。因为：因为：因为：因为：S S a a1 1 A A1 1，A A

12、1 1 a a2 2A A2 2，A A2 2 a a3 3A A3 3,A,Ai i a ai i+1+1A Ai+1i+1,A,An-1n-1 a an nA An n所以有：所以有：S S=a a1 1 A A1 1=a a1 1a a2 2A A2 2=a a1 1a a2 2a a3 3A A3 3=a a1 1a a2 2a a3 3a an n 1/9/202311第三章：词法分析3.3 3.3 有限自动机有限自动机n确定的有限自动机确定的有限自动机DFA M：n 定义：状态图的形式化。见定义：状态图的形式化。见P73的的 定义定义3.1。确定的有限自动机确定的有限自动机DFA

13、M 是一个五元组，即是一个五元组，即 M =（,Q,q0,F,）其中：其中：字母表字母表 Q：有限状态集合有限状态集合 q0：初态初态 F Q：终态集合终态集合 ：Q Q 的单值映射的单值映射1/9/202312第三章：词法分析3.3 3.3 有限自动机有限自动机n表示形式表示形式：状态图状态图:假定M有n个状态，m个输入符号，那么这个状态转换图含有n个状态结，每个状态结最多由m条箭弧射出与别的状态结相连接。准确地说，若转移函数对于q,qQ及a ,有(q,a)=q，则从q到q有一条标记为a的箭弧。整个图含有唯一一个初态结和若干个终态结。矩阵表示矩阵表示：一个DFA还可以用一个矩阵的形式来表示，

14、该矩阵的行表示状态行表示状态，列表示输入字符列表示输入字符，矩阵元素矩阵元素表示在相应状态行和输入字符列下的新状态表示在相应状态行和输入字符列下的新状态，即k行a列为(k,a)的值。用“”表示初态，否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。n 例例3-5，设DFA M=（a，b，S，U，V，Q，S，Q，）其中定义为：(S,a)=U,(S,b)=V,(V,a)=U,(V,b)=Q,(U,a)=Q，(U,b)=V,(Q，a)=Q，(Q，b)=Q1/9/202313第三章：词法分析3.3 3.3 有限自动机有限自动机例例3-5中的DFA的状态图表示状态图表示如下：SaUVbaQb

15、baa,bQQQQUVVQUVUS b a字符字符状态状态0010(S,a)=U,(S,b)=V(V,a)=U,(V,b)=Q(U,a)=Q，(U,b)=V(Q，a)=Q，(Q，b)=Q矩阵表示矩阵表示如右：1/9/202314第三章：词法分析3.3 3.3 有限自动机有限自动机n利用利用DFA对字符串的识别对字符串的识别：P74 对于 上的任何符号串*，若存在一条从初态结到终态结的通路，在这条通路上的所有箭弧标记符号连接成的符号串恰好是，则称为为DFADFA所识别所识别。或或 若*，(q0，)=p,其中q0为DFA M的开始状态，p p F,F为终态集，则称为DFA所接受（识别）。为了理解上

16、述定义，扩充函数如P75上。即对任何a,qqQ将扩张为：(q，)=q (q，a)=(q，)，a)用此定义试证：baab可为例5的DFA M所接受。过程：(S，baab)=(S，b)，aab)=(V，aab)=(V，a)，ab)=(U，ab)=(U，a)，b)=(Q，b)=Q，Q属于终态，得证。nDFA M所识别的语言所识别的语言：所能识别的符号串的全体，记为L（M）。即L（M）=|*，若存在p p F,使(q0，)=q。(S,a)=U,(S,b)=V(V,a)=U,(V,b)=Q(U,a)=Q，(U,b)=V(Q，a)=Q，(Q，b)=Q1/9/202315第三章：词法分析3.3 3.3 有限

17、自动机有限自动机n非确定的有限（状态）自动机非确定的有限（状态）自动机NFA M：在前面的从正则文法构造NFA的例子中，恰好从一个状态射出的弧的标记是两两不同的。但是，如果有两条规则AaT1和AaT2，那么从A到T1和T2的弧的标记都是a。此时，不能用不能用DFA的映射的映射来表示状态为A时，输入a时的后继状态。也就是说，当状态为A，输入为a时，这个转换图的下一步动作出现了不确定性。即此时映射函数已不是单值的而是多值函数（(A，a)=T1,(A，a)=T2)。这就要扩充确定有限自动机的概念。n定义：定义：P75的定义的定义3.2。对定义的理解：对定义的理解：这里，并不要求具有单值性，它可以把序

18、偶（qi,ai)映射到Q的子集qk1,qk2,qkn,即（qi,ai)=qk1,qk2,qkn。1/9/202316第三章：词法分析3.3 3.3 有限自动机有限自动机 的意义：的意义：是Q 的幂集，即Q中所有子集组成的集合。比如，Q=1，2，3则 =,1,2,3,1,2,1,3,2,3,1,2,3有 个子集。Q 表示映射到 子集中的某一个，但并不是说某个子集（如1，3）就是合法的状态，而只是说1和3都有可能，还需继续去试1还是3。n状态转换图的表示：状态转换图的表示：一个含有n个状态，m个输入符号的NFA M，也可以形象地通过一张状态转换图来表示，这张图含有n个状态结，每个状态结可射出若干箭

19、弧与别的状态结相连接。准确地说，如果(q，a)=q1,q2,qk,则从q出发分别向q1,q2,qk各射出一条标记为a的箭弧（q1,q2,qkQ，a，k可以是0），整个图含有一个初态结和若干个终态结。1/9/202317第三章：词法分析3.3 3.3 有限自动机有限自动机例例3-6，一个NFA M=（a,b,0,1,2,3,4,0,2,4,)其中(0，a)=0，3，(0，b)=0，1,(1，b)=2,(2，a)=2，(2，b)=2,(3，a)=4,(4，a)=4,(4，b)=4。与之对应的状态图表示状态图表示如下：0a31b4ab2aaa,b,b,b1/9/202318第三章：词法分析3.3 3

20、.3 有限自动机有限自动机例例3-7，构造一个DFA M，它接受字母表a,b,c上，以a或b开始的字符串，或以c开始但所含的a不多于一个的字符串。满足此条件的状态转换图如下：01 a bb c a2 cc b 3 ac b故：DFAM=(a,b,c,0,1,2,3,0,1,2,3，)其中：(0,a)=1 (0,b)=1 (0,c)=2 (1,a)=1 (1,b)=1 (1,c)=1(2,a)=3 (2,b)=2 (2,c)=2 (3,b)=3(3,c)=31/9/202319第三章：词法分析3.3 3.3 有限自动机有限自动机n利用利用NFA对字符串的识别对字符串的识别：P76 对于 上的任何

21、符号串*，若存在一条从初态结到终态结的通路，且在这条通路上的所有箭弧标记符号连接成的符号串恰好是，则称为NFA所识别。若q0 F,F为终态集，这时q0状态结既是初态结也是终态结，因而存在一条从初态结到终态结的-道路，此时空符号串可为可为NFA所接受所接受。n具有具有-转移的非确定有限自动机：转移的非确定有限自动机：P78。若文法G中有形如A B（相当于A B）或A 时，在状态图中会有从A出发标有的箭弧到B或终态结，也就是说转移函数应该有(A，)=B，据此将非确定的有限自动机扩充为：Q（）的映射，而其它不变，这样所形成的非确定有限自动机为具有具有-转移的非确定有限自动机转移的非确定有限自动机。此

22、自动机与其它非确定有限自动机基本上是一样的，只是在识别时时不理睬那些标记为的箭弧即可。1/9/202320第三章：词法分析3.3 3.3 有限自动机有限自动机nNFA DFA的转换：的转换：事实已经证明了不管是非确定的有限自动非确定的有限自动机机M还是具有具有-转移的非确定的有限自动机转移的非确定的有限自动机M，都可以找到一个与之等价的确定有限自动机确定有限自动机M，使得L（M）=L（M）。P76的定理3.1 转换思路：转换思路：由M出发构造与之等价的M的办法是M的状态对应于M的状态集合，即要使转换后的DFA的每一个状态对应NFA的一组状态。该DFA使用它的状态去记录在NFA读入一个输入符号后

23、可能到达的所有状态，也就是说，在读入符号串a1a2a3an之后，该DFA处在这样一个状态，该状态表示这个NFA的状态的一个子集T，而T是从NFA的开始状态沿着某个标记为a1a2a3an的路径可以到达的那些状态。引进两个定义：引进两个定义：（对状态集合（对状态集合I）状态集合状态集合I的的-closure(I):定义为一状态集，是状态集I中的任何状态经任意条弧而能到达的状态的集合。1/9/202321第三章：词法分析3.3 3.3 有限自动机有限自动机 状态集合状态集合I的的a弧转换弧转换Ia:定义为一状态集，是指从状态集I出发先经过a弧后再经过若干条弧而能到达的状态的集合。可以写作：Ia=-c

24、losure(J)，J=move(I,a),其中，J是从I中任一状态出发经过一条a弧到达的状态集合，记为move(I,a)。比如，比如，对于以下状态图中：-closure(0)=0,1,2,4,7在这里设I=0,1,2,4,7，则因为有因为有move(I,a)=3,8=J,所以所以 Ia=-closure(J)=-closure(3,8)=1,2,3,4,6,7,811024ba0356789abb1/9/202322第三章：词法分析3.3 3.3 有限自动机有限自动机具体转换步骤：具体转换步骤：(子集构造法）子集构造法）以下面的基于字母表=a,b上的具有-转移的非确定有限自动机M为例。步骤步

25、骤1：以以I，Ia、Ib等为列做表，其中等为列做表，其中I列第一行的内容是初态的列第一行的内容是初态的 -闭包所得到的状态集合。并以此为闭包所得到的状态集合。并以此为I计算计算Ia、Ib等，而等，而 且在所计算出的且在所计算出的Ia、Ib等中等中若有若有新的状态集产生，就重复新的状态集产生，就重复 以此新的集合为以此新的集合为I再此计算再此计算Ia、Ib等，直到在所得的等，直到在所得的Ia、Ib等中不再产生新的状态集为止等中不再产生新的状态集为止。1y34bax526bbaaab1/9/202323第三章：词法分析3.3 3.3 有限自动机有限自动机步骤步骤1后的结果如下：后的结果如下：IIa

26、Ibx,5,1初态的初态的-闭闭包包5,1,35,1,45,1,3,2,6,y5,1,45,1,35,1,4,2,6,y5,1,3,2,6,y5,1,4,6,y5,1,3,6,y5,1,4,2,6,y5,1,3,6,y5,1,4,2,6,y5,1,3,2,6,y5,1,4,6,y5,1,4,2,6,y5,1,45,1,3,2,6,y5,1,35,1,4,6,y5,1,3,6,y1y34bax526bbaaab1/9/202324第三章：词法分析3.3 3.3 有限自动机有限自动机步骤步骤2：在上表中将原：在上表中将原NFA初态的初态的-闭包作为转换后的闭包作为转换后的DFA的的初态，包含原初态

27、，包含原NFA终态的状态作为转换后的终态的状态作为转换后的DFA的终态，并的终态，并进行重新编号得到转换后进行重新编号得到转换后的的DFA的状态转移矩阵如下：的状态转移矩阵如下：abx,5,1 15,1,3 25,1,4 35,1,3 25,1,3,2,6,y45,1,4 35,1,4 35,1,325,1,4,2,6,y 55,1,3,2,6,y 45,1,3,2,6,y45,1,4,6,y 65,1,4,2,6,y 55,1,3,6,y 75,1,4,2,6,y 55,1,4,6,y 65,1,3,6,y 75,1,4,2,6,y 55,1,3,6,y 75,1,3,2,6,y 45,1,

28、4,6,y 60001111包含原终态的状态作为新的终态1/9/202325第三章：词法分析3.3 3.3 有限自动机有限自动机步骤步骤3：画出转换后的：画出转换后的DFA的状态图：的状态图：1a23b4ab5baa7aaba6bbb1/9/202326第三章：词法分析3.3 3.3 有限自动机有限自动机n正规文法与有限自动机的等价性（证略）：正规文法与有限自动机的等价性（证略）：通过前面引入有限自动机概念时我们看到正规文法G所用以识别句子的状态转换图就是某个有限自动机的状态转换图。这就是说正规文法G所产生的语言和某个有限自动机M所识别的语言是相同的，此时称G和M是等价的。等价性等价性：对于任

29、何一个正规文法，都存在一个FA M，使L（M）=L（G），反之亦然。见书中见书中P8287内容。内容。n有限自动机与正规表达式的等价性：有限自动机与正规表达式的等价性：上的符号或空或经过连接、闭包所得的为正规表达式，而且可以看到，程序设计语言中的表达式（单词）大多数都可通过正规表达式比较清晰、方便地表示出来。1/9/202327第三章：词法分析3.3 3.3 有限自动机有限自动机n有限自动机与正规表达式的等价性：有限自动机与正规表达式的等价性：可以证明，对任何一个正规表达式r,都存在一个FA M，使L（M）=L（r)，反之亦然。见书见书中中P87的定理的定理3.5。结合正规文法与有限自动机的等

30、价性，我们可以看到正规文法、正规表达式、有限自动机这三者之间在某种意义下是互相等价的。也就是说，字母表字母表上的上的一个正规语言，一个正规语言，既可以由某一个正规文法产生，也可以由某一正规表达式所表示，既可以由某一个正规文法产生，也可以由某一正规表达式所表示，还可以由某一个有限自动机所识别，甚至还可以由某一个确定的还可以由某一个有限自动机所识别，甚至还可以由某一个确定的有限自动机所识别。有限自动机所识别。可根据需要在不同的情况采取不同的表达语言的方法。一般是正规表达式正规表达式 NFA DFA。n对于对于上的上的一个正规式一个正规式r构造与之等价的构造与之等价的NFA M：（这里要把状态图的概

31、念拓广，令每条弧可用一个正规式作标记。）1/9/202328第三章：词法分析3.3 3.3 有限自动机有限自动机具体转换步骤：具体转换步骤：步骤步骤1：规定r与 等价，其中x为NFA 的初态，y为终态。步骤步骤2：按以下三条规则将弧上的正规表达式逐渐分解直至分：按以下三条规则将弧上的正规表达式逐渐分解直至分 解为单个的字符或空为止。解为单个的字符或空为止。规则规则 等价为等价为规则规则 等价为等价为规则规则 等价为等价为 xyriABjiAkjBiA|BjijABiA*jikjA1/9/202329第三章：词法分析3.3 3.3 有限自动机有限自动机例例3-8，构造与正规表达式(a|b)*(a

32、a|bb)(a|b)*等价的 NFA M：首先：(a|b)*(aa|bb)(a|b)*等价为等价为等价为等价为xy(a|b)*(aa|bb)(a|b)*xy(a|b)*12(aa|bb)(a|b)*a|bxy1256aabba|bbxy125634baabbaa1/9/202330第三章：词法分析3.3 3.3 有限自动机有限自动机n对于对于的的一个一个NFA M构造与之等价的正规式：构造与之等价的正规式：步骤步骤1：在M的状态图上加两个状态结，一个为x结点，一个为 y结点。从x结点用连接到M的初态，从M的所有终 态结点用弧连接到y结点，形成只有一个初态和一个 终态的M。步骤步骤2：使用以下三

33、条规则逐步消去M中的所有结点，直至只 剩下x和y结点，这时在x和y之间箭弧上的标记即为所求。规则规则 等价为等价为规则规则 等价为等价为规则规则 等价为等价为 iABjiAkjBiA|BjijABiAC*BjiAkjBC上述两规则的逆 更具一般性1/9/202331第三章：词法分析3.3 3.3 有限自动机有限自动机例例3-9，为以下图所表示的NFA M构造与之等价的正规式r：增加结点增加结点x x和和y y后形成新的后形成新的M M的状态转换图如下：的状态转换图如下：0413aa,bba2ba,ba,b0413aa,bba2ba,ba,bxy1/9/202332第三章：词法分析3.3 3.3

34、 有限自动机有限自动机使用上述三条规则逐渐消去使用上述三条规则逐渐消去M中的所有结点后：中的所有结点后：0a,bbbaax42a,ba,by0a,bbb(a|b)*xyaa(a|b)*(a|b)*(aa(a|b)*|bb(a|b)*)xy即r=(a|b)*(aa(a|b)*|bb(a|b)*)=(a|b)*(aaaa|bb|bb）(a(a|b)*为所求。1/9/202333第三章：词法分析3.3 3.3 有限自动机有限自动机nDFA的化简（最小化）：的化简（最小化）：n化简条件：接受的语言必须相同。化简条件：接受的语言必须相同。n化简化简(最小化最小化)算法基本思想算法基本思想划分法划分法：1

35、.将DFA M 中的状态划分为互不相交的子集，每个子集内部的状态都状态都等价等价；而在不同子集间的状态均不等价状态均不等价。2.从每个子集中任选一个状态作为代表，消去其它等价状态。3.把那些原来射入其它等价状态的弧改为射入相应的代表状态。n等价状态：等价状态：设DFA M中有两个状态s,t1.s,t等价等价：如果从状态s出发能读出某个字串而停于终态，从t出发也能读出同样的字串而停于终态，则称s,t 等价。2.s,t可区别：可区别：如果s,t不等价，则称为s,t可区别。1/9/202334第三章：词法分析3.3 3.3 有限自动机有限自动机n化简（最小化）算法：化简（最小化）算法：1.把状态集Q

36、划分为终态集和非终态集：非终态，终态。因为终态能识别，而非终态不能，所以它们是可区别的；2.对每个子集中的任何一个状态对（p,q)，若对每一个输入符号a，r=(p,a),s=(q,a)且r与s均等价，则易知p和q等价；若存在某个a使r和s可区别，则p和q可区别。以此将各子集继续分解，直至不能再分解为止。3.在最终的由各子集组成的状态集合中，在每个子集中任取一个状态做“代表”，而删去子集中其余状态，并把射向其它等价状态的箭弧都改作射向这个做“代表”的状态结中。这样得到的状态转换图所对应的DFA M就是接受L（M）的具有最少状态的DFA。1/9/202335第三章：词法分析3.3 3.3 有限自动

37、机有限自动机例例3-10，设有一DFA 的状态转换图如下，试化简之。0 1 2 3 5 4 6 a a a a a a a b b b b b b b1 0,2，1解：1.1.1，2=0，1，2，3，4，5，6 2.2.考察子集1 0，1，2由(0,a)=1 (1,a)=3 (2,a)=11/9/202336第三章：词法分析3.3 3.3 有限自动机有限自动机 再由(0,b)=2 (2,b)=5 1 0,1,2接着考察子集2 3,4,5,6,由于(3,a)=3 (3,b)=4(4,a)=6 及 (4,b)=5(5,a)=6 (5,b)=5(6,a)=3 (6,b)=42不可再分，即 2 3，4

38、，5，6所以，最终 0，1，2，3，4，5，63.令状态3代表3,4,5,6，把原来到达状态4，5，6的弧都指向3，并删除4，5，6。得：2 a b 1 3 0 a a a b b b 0 1 2 3 5 4 6 a a a a a a a b b b b b b b1/9/202337第三章：词法分析课堂练习（作业）课堂练习（作业）课上练习课上练习1：将下图中的DFA最小化。1 A,B，F此时A，B是否可分取决于C和D是否等价。解：1.1.1，2=A，B，F，C，D，E，G 2.2.考察子集1 A，B，F由(A,b)=C (B,b)=D (F,b)=ABF D EC a b a a a b

39、b b b bG1/9/202338第三章：词法分析课堂练习（作业）课堂练习（作业）再由(C,b)=E (D,b)=F 接着考察子集2 C,D,E,G,由于(C,a)=(D,a)=(G,a)=(E,a)=G 2 C，D，G，E所以，最终 A，B，C，D，G，E，F3.令状态D代表D，G，把原来到达状态G的弧都射向D，并删除 G，得：2 C，D，G，E并由此可知1 A,B，F a BDA a b b aC b aEF a bABF D EC a b a a a b b b b bG1/9/202339第三章：词法分析课堂练习（作业）课堂练习（作业）课上练习课上练习2：设计一个DFA，其输入字母表

40、是0，1，它能接受以0开始以1结尾的所有序列。解：（1.1.）根据题意，得到相应的正则式：0（0|1）*1 （2.2.）构造其NFA如下：S A 0 B 0，1 CZ 1（3.3.）NFA确定化为DFA（并换名）：I0I11 S2A，B，C2A，B，C3B，C4B，C，Z3B，C3B，C4B，C，Z4B，C，Z3B，C4B，C，Z1/9/202340第三章：词法分析课堂练习（作业）课堂练习（作业）相应DFA的状态图如下为：1 2 0 0 3 04 1 1 1 0（4.4.）DFA最小化：解：1.1.1，2=1，2，3，4 2.2.考察子集1 1，2，3由(1,1)=(2,1)=4 (3,1)=

41、41 1，2,31/9/202341第三章：词法分析课堂练习（作业）课堂练习（作业）再由(2,0)=3 (3,0)=3 这样，最终 1，2，3，4所以，最小化DFA的状态图如下：状态2与状态3等价S A 0 0B B101故故最终的最终的DFA设计为：设计为：M =（,Q,S,F,）其中其中=0，1Q=S，A，BF=B：(S,0)=A (A,0)=A (A,1)=B (B,0)=A (B,1)=B课课后练习后练习：请构造与正则式r=(a*b)*ba(a|b)*等价的状态最少的DFA。1/9/202342第三章：词法分析课后作业课后作业nP993.123.13(a)1/9/202343第三章：词

42、法分析3.4 3.4 词法分析器的设计词法分析器的设计n词法分析程序的任务：词法分析程序的任务：从左至右逐个字符对源程序进行扫描，按照词法规则识别出一个个正确单词，并转换为相应的二元式（种别，属性值）（种别，属性值）形式，交给语法分析使用。另外，词法分析程序除了识别出单词及其属性外，往往还要完成那些在语法分析之前需要做的工作，如删除注解、空格、换行符等非必要信息，把标识符登录到符号表及其某些预加工处理等。词法分析词法分析表格管理表格管理语法分析语法分析源源程程序序单词单词符号表符号表常数表常数表1/9/202344第三章：词法分析3.4 3.4 词法分析器的设计词法分析器的设计n词法分析程序的

43、输出：词法分析程序的输出：词法分析程序的输出通常表示成二元式（种别，属性值）（种别，属性值）的的形式，其中，常用单词种别常用单词种别有：n各关键字（保留字、基本字），各种运算符，各种分界符各关键字（保留字、基本字），各种运算符，各种分界符各用一个种别码标识各用一个种别码标识n其它标识符其它标识符用一个种别码标示用一个种别码标示n常数常数用一个种别码标示用一个种别码标示而单词符号的属性值是指反映单词符号特性或特征的值。常常用单词属性值用单词属性值有：n常数的值，标识符的名字等常数的值，标识符的名字等n保留字、运算符、分界符的属性值可以省略保留字、运算符、分界符的属性值可以省略1/9/202345

44、第三章：词法分析例例 3-11:3-11:单词符号单词符号序列序列while(*pointer!=0)pointer+;while(*pointer!=0)pointer+;while while (WHILE(WHILE，_)_)(SLP(SLP，_)_)*(FETCH(FETCH，_)_)pointer pointer (IDN(IDN，符号表入口指针符号表入口指针)!=!=(RELOPRELOP，NE)NE)0 0 (CONST(CONST，0)0)(SRP(SRP，_)_)(LP(LP，_)_)pointer pointer (IDN(IDN，符号表入口指针符号表入口指针)+(INCI

45、NC，_)_);(SEMI(SEMI，_)_)(RP(RP，_)_)3.4 3.4 词法分析器的设计词法分析器的设计1/9/202346第三章：词法分析3.4 3.4 词法分析器的设计词法分析器的设计n词法分析程序设计为一个独立子程序的原因：词法分析程序设计为一个独立子程序的原因：词法分析器可作为一个独立的子程序，但这并不意味着必须把词法分析作为独立的一遍。词法分析程序作为一个独立子程序的好处：1.1.使整个编译程序的结构更简洁、清晰和条理化使整个编译程序的结构更简洁、清晰和条理化（简化语法分析过程）。2.2.编译程序的效率会改进编译程序的效率会改进。大部分的编译时间是花费在扫描字符以把单词符

46、号分离出来，把词法分析独立出来，可采用专门的读字符和分离单词的技术可大大加快编译速度。另外，由于单词的结构可用有效的方法和工具进行扫描和识别，进而可建立词法分析程序的自动构造工具。3 3.增加编译程序的可移植性增加编译程序的可移植性。在同一个语言的不同实现中，或多或少地会涉及到与设备有关的特征，将这些置于词法分析程序中解决而不影响编译其它成分的设计。1/9/202347第三章：词法分析3.4 3.4 词法分析器的设计词法分析器的设计n词法分析中的缓冲技术：词法分析中的缓冲技术：有时词法分析程序为了得到某个单词符号的确切性质，只从该符号本身所含有的那些字符还不能作出判定，还需要超过该符号沿着程序

47、字符流继续向前看若干个字符后才能作出确定分析，这就提出了设置输入缓冲器的必要性。特别是某些高级语言对关键字不加保护，单词间没有明确界符，要在上下文环境中识别单词，这时一定需要超前搜索。例如：FORTRAN中对“IF”的使用：IF(5.EQ.M)GOTO 50 IF=100 IF(100)=5 另外，对内存的操作比对文件系统要快。1/9/202348第三章：词法分析3.4 3.4 词法分析器的设计词法分析器的设计n词法分析程序的手工设计：词法分析程序的手工设计：n两步骤：两步骤：1.1.画框图：画框图：正规式 NFA DFA 最小化的DFA具体的是：写出该语言的词法规则。把词法规则转换为相应的状

48、态转换图。把各转换图的初态连在一起，构成识别该语言的自动机。2.由特殊的框图（即状态图）写出词法分析程序。由特殊的框图（即状态图）写出词法分析程序。将状态转换图看作通常的程序框图，按如下方法写出相应的词法分析程序。对于状态图中的每一状态（代表一个非终结符号）构造一段代码，代码的功能为：子集法子集法子集法子集法 化简化简化简化简1/9/202349第三章：词法分析3.4 3.4 词法分析器的设计词法分析器的设计从输入串中读一个字符；判断读入的字符与由此状态出发的哪条弧上的标记相匹配，然后转至相匹配的那条弧所指向的状态；重复步骤1直至无法前进（即到达那样的一个状态，它所面临的输入字符没有后继状态。

49、可能有三种情况：一是没有前进的道路，二是超出了最长字符限制，三是文件系统单词读完了）。然后判断所在的是否为终态，是则“吃进”的字符序列为合法的单词，否则回退，直至遇到回退中的第一个终态为止，此时所形成的为合法单词。均不匹配时便失败（不能到达正常出口）。1/9/202350第三章：词法分析3.4 3.4 词法分析器的设计词法分析器的设计n例例题题3-123-12，设计能识别以下三条规则表示的单词的词法分析程序。1.1.三条规则：三条规则：a r1 abb r2 a*bb*r3 2.NFA:a abb a*bb*1 1 a2 24 43 3 a6 65 5 b b7 7 b8 8a ab b1/9

50、/202351第三章：词法分析3.4 3.4 词法分析器的设计词法分析器的设计3.3.合并合并：0 04 43 3 a6 65 5 b b7 7 b8 8a ab b a2 21 14.4.DFA:DFA:IIaIb到达终态时所识别的单词0,1,3,72,4,782,4,775,8a(r1)88a*bb*(r3)7785,86,8a*bb*(r3)6,88abb1/9/202352第三章：词法分析3.4 3.4 词法分析器的设计词法分析器的设计重新编号重新编号：ab0121342233245520 01 11 10 01 11 11/9/202353第三章：词法分析3.4 3.4 词法分析器的