编译原理 第二章 词法分析.ppt

第一章第一章第一章第一章 总结总结总结总结 语言与语言的翻译编译器的基本组成编译器的分析/综合模式(编译器基础架构)扫描遍数编译器的编写1第二章第二章第二章第二章 词法分析词法分析词法分析词法分析词法的双重含义词法的双重含义规定单词形成的规则，被称为构词规则或词法规则。相当于立法，规定语言所允许的合法单词。根据构词规则识别输入序列，被称为词法分析。相当于执法，识别出合法的单词、指出非法的输入序列。主要内容主要内容词法分析中的若干问题模式的形式化描述记号的识别从正规式到词法分析器上机：函数绘图语言的词法分析器x :=y +z *60.0 ;id1:=id2+id3*60.0;22.1 2.1 词法分析中的若干问题词法分析中的若干问题词法分析中的若干问题词法分析中的若干问题F记号、模式与单词记号、模式与单词单词的基本分类：关键字kw(key word,or reserved word)标识符id(identifier)字面量literal特殊符号ks(key symbol,or special symbol)例2.1语句position:=initial +rate *60记号 id ks id ks id ks number注意：称识别出id而不是rate或initial问题：根据什么识别这些词法的基本单位（词法元素）？32.1 2.1 词法分析中的若干问题词法分析中的若干问题词法分析中的若干问题词法分析中的若干问题三个术语：模式模式(pattern)：产生和识别元素的规则 记号记号(token)：按照某个模式(或规则)识别出的元素(一组)单词单词(lexeme)：被识别出的元素自身的值(一个)，也称为词值 记号的类别记号的类别单词举例单词举例模式的非形式化描述模式的非形式化描述const(01)constconstif(03)ififrelation(81),=,=,=,=,=,.id(82)pi,count,D2字母打头的字母数字串num(83)3.1416,0,6.02E23任何数值常数literal(84)“core dumped”双引号间的任意字符串Commentx is an integer括号间的任意字符串42.1 2.1 词法分析中的若干问题词法分析中的若干问题词法分析中的若干问题词法分析中的若干问题F记号的属性记号的属性记号是按照某个模式识别出的元素。赋值句position:=initial+rate*60position、initial和rate均为标识符，种类均是id。问题：当识别出一个id时，如何判定是哪个id？当识别出一个relation时，究竟是=还是 25 由三个记号组成类别 82 81 83属性 “mycount”5 25注意：5与25的区别（根据记号的类别）25与“25”的区别（如何区别？）记号的类别relation(81)id(82)num(83)52.1 2.1 词法分析中的若干问题词法分析中的若干问题词法分析中的若干问题词法分析中的若干问题F词法分析器的作用与工作方式词法分析器的作用与工作方式 词法分析器是编译器中唯一与源程序打交道的部分。滤掉源程序中的无用成分，如注释、空格、回车等；处理与平台有关的输入，如文件结束符的不同表示等；根据模式识别记号，并交给语法分析器；调用符号表管理器或出错处理器，进行相关处理。工作方式：单独扫描，作为语法分析器的子程序，并行工作62.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述F字符串与语言字符串与语言 从词法分析的角度看程序设计语言，它是由记号组成的集合。定义定义2.1 语言L是有限字母表上有限长度字符串的集合说明说明：1.字母表是字符的集合，这些字符可以组成字符串。2.两个有限（计算机的表达能力有限）：字母表是有限的；字符串的长度是有限的。例2.3字母表=a,b,c，则其上的语言L=,a,b,c,aa,ab,ac,ba,bb,bc,.72.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述字符串的基本概念字符串的基本概念术语术语示例示例|S|abc|=3|=0S1S2 abc def=abcdefSn(abc)3=abcabcabcS的前缀的前缀X abc的前缀有：，a，ab,abcS的后缀的后缀X abc的后缀有：，c，bc,abcS的子串的子串X abc的子串有：，a，b,c,S的真前缀的真前缀abc的真前缀有：a，abS的真后缀的真后缀？S的真子串的真子串？S的子序列的子序列Xabdf是abcdef的一个子序列82.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述若 L=a,b,M=c,d，则 LM=ac,bc,ad,bd，LM=L*=,a,b,aa,bb,ab,ba,aaa,.L+=a,b,aa,bb,ab,ba,aaa,.术语术语意义意义 空集合 空串是唯一元素X=LM 并:X=s|sL or sM X=LM 交:X=s|sL and sMX=LM 连接:X=st|sL and tM X=L*(星)闭包:X=L0L1L2.X=L+正闭包:X=L1L2L3.92.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述F正规式与正规集正规式与正规集定义定义2.2 令是一个有限字母表，则上的正规式及其表示的集合递归定义如下:1.是正规式，它表示集合L()=2.若a是上的字符，则a是正规式，它表示集合L(a)=a 3.若正规式r和s分别表示集合L(r)和L(s)，则 （a）r|s是正规式，表示集合L(r)L(s)，（b）rs是正规式，表示集合L(r)L(s)，（c）r*是正规式，表示集合(L(r)*，（d）(r)是正规式，表示的集合仍然是L(r)可用正规式描述的语言称为正规语言正规语言或正规集正规集。102.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述定义定义2.2说明：说明：1.运算的优先级与结合性三种运算均具有左结合性质；优先级从高到低：闭包、连接、或。正规式中不必要的括号可以被省略。例如：(a)|(b)*)(c)可以简化成 a|b*c。2.正规式的等价不同算术表达式可以表示同一个数，如3+5、5+3、2+6等均表示8。不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系。112.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述定定义义2.3 若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q。例2.4 设字母表=a，b，c，则上有：正规式正规式 正规集正规集 a，b，ca，b，c a|b，b|aab=a，b a(a|b)*a，aa，ab，aba，abb，aab，.，a为首的ab串*，a，b，c，aa，ab，ac，ba，bb，bc，.例2.5 令 L(x)=a，b，L(y)=c，d，则 L(x|y)=a，b，c，d L(y|x)=a，b，c，d 122.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述利用正规式的等价性可以化简复杂的正规式。正规式的等价性判定可以采用两种方法：根据定义，证明不同的正规式表示同一集合（例2.5）根据下述正规式的代数性质进行运算公理公理公理公理r|s=s|r(r s)t=r(s t)r|(s|t)=(r|s)|t r=r,r =rr(s|t)=r s|r tr*=(r+|)(s|t)r=s r|t rr*=r*132.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述F记号的说明记号的说明自然语言对模式的非形式化描述很不精确，而正规式可以严格地规定记号的模式，用正规式说明记号的公式为：记号记号=正规式正规式读作 （左边）记号定义为（右边）正规式（左边）记号定义为（右边）正规式或者 记号是正规式记号是正规式例如，id=a(a|b)*可以读作为 id定义为定义为a(a|b)*注：注：在不引起混淆的情况下，把说明记号的公式简称为正规式，或者规则。142.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述例2.6 记号relation、id和num分别是Pascal的关系运算符、标识符和无符号数，它们的正规式表示如下所示。relation=|=|=|=id=(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|0|1|2|3|4|5|6|7|8|9)*num=(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)(|E(+|-|)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)返回返回152.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述简化正规式描述简化正规式描述1.正闭包正闭包若r是表示L(r)的正规式，则r+是表示(L(r)+的正规式：r+=r r*=r*r，r*=r+|例如：(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*化简为：(0|1|2|3|4|5|6|7|8|9)+2.可缺省可缺省若r是正规式，则r?是表示L(r)的正规式：r?=r|例如：E(+|-|)可改写为：E(+|-)?注：注：+、?、*具有相同的结合性和优先级引入？的原因在于字符无法使用键盘输入。162.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述3.字符组字符组若r是仅由|运算构成的正规式，则可改写为r，其中r可以有如下两种形式：枚举：如abc，等价于 a|b|c分段:如0-9a-z，等价于0123456789abcdefghijklmnopqrstuvwxyz4.非字符组非字符组若r是一个字符组形式的正规式，则r是表示-L(r)的正规式。例如：若=a,b,c,d,e,f,g，则 L(abc)=d,e,f,g 172.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述辅助定义辅助定义 通俗地讲，辅助定义的作用是为复杂的或重复出现的正规式命名，并在以后的使用中用名字代替该正规式。辅助定义的形式与正规式一样：辅助定义名字辅助定义名字=正规式正规式注：1.辅助定义不与任何模式匹配；2.作为辅助定义的正规式仅供内部使用，而不用于说明记号。辅助定义：辅助定义：内部名内部名=正规式正规式规则：规则：记号名记号名=正规式正规式182.2 2.2 模式的形式化描述模式的形式化描述模式的形式化描述模式的形式化描述例2.6 引入正规式的缩写形式和辅助定义式后，id和num的正规定义式可重写如下：char=a-zA-Zdigit=0-9digits=digit+optional_fraction=(.digits)?optional_exponent=(E(+|-)?digits)?id=char(char|digit)*num=digits optional_fraction optional_exponent对比原来对比原来19上次课总结上次课总结上次课总结上次课总结F词法的双重含义；F模式、记号与单词；F形式化描述：正规式与正规集；F正规式描述；正规式简化表示、辅助定义202.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机模式的描述正规式记号的识别有限自动机（不确定、确定）F不确定的有限自动机不确定的有限自动机（Nondeterministic Finite Automaton,NFA）定义定义2.4 NFA是一个五元组（5-tuple）：M=（S，move，s0，F），其中（1）S是有限个状态（state）的集合；（2）是有限个输入字符（包括）的集合；（3）move是一个状态转移函数，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态sj；（4）s0是唯一的初态（也称开始状态）；（5）F是终态集（也称接受状态集），它是S的子集，包含了所有的终态。212.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机NFA两种直观的表示方式两种直观的表示方式 状态转换图状态转换图NFA中的每个状态，对应转换图中的一个节点；NFA中的每个move(si,a)=sj，对应转换图中的一条有向边；表示从节点si出发进入节点sj，字符a(或)是边上的标记。状态转换矩阵状态转换矩阵每个矩阵元素Msi,a中的内容，是从状态si出发，经字符a(或)所到达的下一状态sj；在转换矩阵中，一般以矩阵第一行所对应的状态为初态，而终态需要特别指出。状态转换图中如何表示呢？状态转换图中如何表示呢？222.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机例2.7 识别正规式(a|b)*abb所描述正规集的NFA的三种表示形式分别如下。(其中转换矩阵表示中0为初态，3为终态)S=0,1,2,3,=a,bmove=move(0,a)=0,move(0,a)=1,move(0,b)=0,move(1,b)=2,move(2,b)=3 s0=0,F=3232.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机NFA如何识别记号如何识别记号?对字符串，从初态开始，经一系列状态转移到达终态。例如：对于字符串abb，有定义定义：move=move(0,a)=0,move(0,a)=1,move(0,b)=0,move(1,b)=2,move(2,b)=3 move(0,a)=1,move(1,b)=2,move(2,b)=3转换矩阵转换矩阵：m0,a=0,1,m1,b=2,m2,b=3转换图转换图：0a1b2b3，最直观开始识别能是开始识别能是0a0吗？吗？242.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机例2.8 识别表2.1中记号relation、id和num的转换图。relation=|=|=|=id=char(char|digit)*=能被识别为和=吗？最长识别原则最长识别原则252.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机optional_fraction=(.digits)?optional_exponent=(E(+|-)?digits)?num=digits optional_fraction optional_exponent262.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机NFA识别记号的最大特点是它的不确定性不确定性，即在当前状态下对同一字符有多于一个的下一状态转移。定义：move函数是1对多的；move=move(0,a)=0,move(0,a)=1,move(0,b)=0,.状态转换图：同一状态有多于一条边标记相同字符转移到不同的状态；状态转换矩阵：Msi,a是一个状态的集合272.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机NFA识别输入序列的一般方法：反复试探所有路径，直到到达终态，或者到达不了终态。不确定性带来的问题：识别输入序列时，在当前状态下遇到同一字符，应转移到哪个下一状态？例2.9 在正规式(a|b)*abb的NFA上识别输入序列abb和abab。282.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机NFA识别记号存在的问题只有尝试了全部可能的路径，才能确定一个输入序列不被接受，而这些路径的条数随着路径长度的增长成指数增长。识别过程中需要进行大量回溯，时间复杂度升高且算法趋于复杂。问题问题：是否可以构造这样的有限自动机，它识别正规式所描述的字符串，且在任何一个状态下遇到同一字符最多有一个状态转移？292.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机F确定的有限自动机确定的有限自动机（Deterministic Finite Automaton,Deterministic Finite Automaton,DFADFA）定义定义2.5 DFA是NFA的一个特例，其中：（1）没有状态具有 状态转移（-transition），即状态转换图中没有标记 的边；（2）对每个状态 s 和每个字符 a，最多有一个下一状态。与NFA相比，DFA的特征是其确定性确定性定义：move（si,a）函数是1对1的；转换图：从一个节点出发的边上标记均不相同；转换矩阵：M si,a 是一个状态。且字母表不包括 。302.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机DFA对NFA施加的两条限制：限制1：没有状态转移限制2：同一状态下没有重复字符的状态转移例2.10 正规式(a|b)*abb的DFA，识别输入序列abb和abab：识别abb：0a1b2b3，状态，接受识别abab：0a1b2a1b2，？312.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机DFA识别输入序列的算法被称为DFA模拟器或驱动器，它与DFA共同构成词法分析器的核心，特点是算法与模式无关。算法算法2.1 模拟DFA输入DFA D和输入字符串x(eof)。D的初态为s0，终态集为F输出若 D 接受 x，回答“yes”，否则回答“no”。方法用下述过程识别x：s:=s0;ch:=nextchar;-初值while cheof-x结束?loop s:=move(s,ch);ch:=nextchar;-循环转移end loop;if s is in F-终态返回then return“yes”;else return“no”;end if;322.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机识别abb：1.s=0,ch=a2.s=1,ch=b3.s=2,ch=b4.s=3,ch=eof5.yes识别abab：1.s=0,ch=a2.s=1,ch=b3.s=2,ch=a4.s=1,ch=b5.s=2,ch=eof6.no(a|b)*abb的的DFA332.3 2.3 记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机记号的识别有限自动机F有限自动机的等价有限自动机的等价定义定义2.6 若有限自动机M和M识别同一正规集，则称M和M是等价的，记为M=M。提示提示：正规式与有限自动机从两个侧面表示正规集。正规式是描述，自动机是识别。因此，当它们表示相同集合时，均存在等价的问题。有几种可能的等价？342.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器构造词法分析器的一般方法和步骤：1.描述描述：用正规式对模式进行描述；2.构造构造NFA：为每个正规式构造一个NFA；3.确定化确定化：将NFA转换成等价的DFA；4.最小化最小化：优化DFA，使其状态数最少；5.构造词法分析器构造词法分析器：由DFA构造词法分析器。问题问题：为何不直接从正规式构造DFA？机器构造需要规范的算法；正规式NFA：有规范的一对一的构造算法；DFA分析器：有便于记号识别的算法。352.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器F从正规式到从正规式到NFA 算法算法2.2 Thompson 算法输入字母表上的正规式 r输出接受 L(r)的NFA N方法首先分解 r，然后根据下述步骤构造NFA：1.对，构造NFA N()接受；2.对上的每个字符a，构造NFA N(a)接受a；3.若N(p)和N(q)是正规式p和q的NFA，则ar|srsr*(r)362.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器（a）对正规式p|q，构造NFA N(p|q)接受L(p)L(q)；（b）对正规式pq，构造NFA N(pq)接受L(p)L(q)；（c）对正规式p*，构造NFA N(p*)接受L(p*)；（d）对于正规式(p)，使用p本身的NFA，不再构造。ar|srsr*(r)372.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器例2.11 用Thompson算法构造正规式r=(a|b)*a b b的NFA N(r)。先分解正规式，再自下而上构造NFA注意注意：算法的构造与正规式一一对应构造一个新的NFA最多增加两个状态38上次课总结上次课总结上次课总结上次课总结FNFA定义M=（S，move，s0，F）FNFA直观表示：状态转换图与状态转换矩阵FNFA识别记号FNFA的不确定性FDFANFA的特例F模拟DFA的算法F自动机的等价F构造词法分析器的步骤FTompson算法392.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器F从从NFA到到DFA1.NFA识别记号的识别记号的“并行并行”方法方法例2.12 从甲地到乙地，可以乘汽车也可以骑自行车，具体路线如右图。其中c表示乘车，b表示骑自行车。现在要求从甲地到乙地，只许乘车而不许骑自行车，该如何走？抽象：识别是否有从甲到乙标记为全c的路径串行（试探）：甲 c 2 无路可走，退回甲 c 1 c 3 无路可走，退回甲 c 1 c 乙 到达乙地，成功 并行：有多辆汽车，每次到达汽车能到达的全体甲 c 1,2c 3,乙到达乙地，成功402.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器由于并行的方法在每试探一步时，考虑了所有的下一状态转移（所有下一状态作为一个状态集合），因此所走的每一步都是确定的。用NFA识别记号，并不采用串行的方法（算法不易构造，复杂度高且回溯），而是采用并行的方法，核心思想是将不确定的下一状态确定化。NFA上识别记号的确定化方法是在计算下一状态转移时，实施如下确定化的两个步骤：1.消除 状态转移：-闭包(T)2.消除多于一个的下一状态转移：smove(S,a)412.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器-闭包(T)：从状态T出发，不经任何字符达到的状态全体。smove(S,a)：从状态集S出发，标记为a的下一状态全体。与move(s,a)的唯一区别：用状态集取代状态。定义定义2.6 状态集T的-闭包(T)是一个状态集，且满足：（1）T中所有状态属于-闭包(T)；（2）任何smove(-闭包(T)，)属于-闭包(T)；（3）再无其他状态属于-闭包(T)。根据定义，-闭包(s2)应包括：1.s2自身s2（1）2.s4s2,s4（2）3.s5s2,s4,s5（2）422.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器算法算法2.4 求-闭包输入状态集T输出状态集T的-闭包方法for T中每个状态t loop 加入t到U;push(t);end loop;while 栈不空 looppop(t);for 每个u=move(t,)loop if u不在U中 then 加入u到U;push(u);end if;end loop;end loop;return U;闭包U和模拟递归的stack问题问题：试将函数直接写为递归的-闭包(s2)Ustack1s2s22s2,s4s43s2,s4,s5s54s2,s4,s5432.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器算法算法2.3 模拟NFA输入NFA N，x(eof)，s0，F 输出若N接受x，回答“yes”，否则“no”方法用下边的过程对x进行识别。S是一个状态的集合 S:=-闭包(s0);-所有可能初态的集合a:=nextchar;while a eof loop S:=-闭包(smove(S，a);-所有下一状态的集合a:=nextchar;end loop;if SF then return“yes”;else return“no”;end if;模拟DFA模拟NFA开始初态(s0)初态集(S)下一状态转移下一状态下一状态集结束s is in FSF442.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器识别abb:计算初态集：-闭包(0)=0,1,2,4,7 A从A出发经a到达：-闭包(smove(A,a)=3,8,6,7,1,2,4 B从B出发经b到达：-闭包(smove(B,b)=5,9,6,7,1,2,4 C从C出发经b到达：-闭包(smove(C,b)=5,10,6,7,1,2,4 D结束且D10=10，接受。识别的路径为：A a B b C b D例2.13 在NFA上识别输入序列abb和abab452.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器识别abab:初态集：-闭包(s0)=0,1,2,4,7 A从A出发经a到达：-闭包(smove(A,a)=3,8,6,7,1,2,4 B从B出发经b到达：-闭包(smove(B,b)=5,9,6,7,1,2,4 C从C出发经a到达：-闭包(smove(C,a)=3,8,6,7,1,2,4 B从B出发经b到达：-闭包闭包(smove(B,b)=5,9,6,7,1,2,4 C识别路径为：A a B b C a B b C。由于C10=，所以不接受例2.13 在NFA上识别输入序列abb和abab462.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器2.子集法子集法构造构造DFA并行模拟NFA的弱点：每次动态计算下一状态转移的集合，效率低。改进方法：将NFA上的全部路径均确定化并且记录下来，得到与NFA等价的DFA。从甲地到乙地的路径是一个NFA，可找到一个等价的DFA。例2.14 用DFA识别cc和cbc：甲 c 1,2 c 3,乙，接受 甲 c 1,2 b 3 c?，不接受 1.消除了不确定性2.无需动态计算状态集合47算法算法2.5 从NFA构造DFA（子集法）输入 NFA N输出等价的DFA D，其初态含有NFA初态，终态是含有NFA终态的状态集合。方法用下述过程构造DFADstates =-闭包(s0);-是唯一状态且未标记while Dstates有未标记状态T loop 标记T;for 每一个字符a loopU:=-闭包(smove(T，a);if U非空 thenDtranT，a:=U;if U不在Dstates中 then U作为未标记状态加入Dstates;end if;end if;end loop;end loop;状态集状态集Dstates和转换矩阵和转换矩阵Dtran48-闭包(0)=0,1,2,4,7*A-闭包(smove(A,a)=3,8,6,7,1,2,4*B-闭包(smove(A,b)=5,6,7,1,2,4*C-闭包(smove(B,a)=3,8,6,7,1,2,4B-闭包(smove(B,b)=5,9,6,7,1,2,4*D-闭包(smove(C,a)=3,8,6,7,1,2,4B-闭包(smove(C,b)=5,6,7,1,2,4C-闭包(smove(D,a)=3,8,6,7,1,2,4B-闭包(smove(D,b)=5,10,6,7,1,2,4*E-闭包(smove(E,a)=3,8,6,7,1,2,4B-闭包(smove(E,b)=5,6,7,1,2,4C例2.15 用算法2.5构造(a|b)*abb的DFA 选择哪一个选择哪一个DFA？492.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器3.最小化最小化DFA对于若干个等价的DFA，总是希望由状态数最小的DFA构造词法分析器。将一个DFA等价变换为另一个状态数最小的DFA的过程被称为最小化最小化DFA。定义定义2.7 对于任何两个状态t和s，若从一状态出发接受输入字符串，而从另一状态出发不接受，或者从t出发和从s出发到达不同的接受状态，则称对状态t和s是可区分可区分的。设想任何输入序列对s和t均是不可区分不可区分的，则说明从s出发和从t出发，分析任何输入序列均得到相同结果。因此，s和t可以合并成一个状态。最小化最小化DFA的实质的实质：在状态集S上找到一个基于不可区分基于不可区分的等价关系R，S/R即是最小DFA的状态集。502.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器算法算法2.6 最小化DFA的状态数输入DFA D=S，move，s0，F。输出等价的D=S，move，s0，F(D状态数最少状态数最少)方法执行如下步骤：1.初始划分=S-F，F1，F2，.，其中，Fi是F的子集，接受不同记号；2.应用下述过程构造新的划分new：for 的每一个组G loop划分G，G的两个状态s和t在同一组中的充要条件是:a.(move(s,a)Gimove(t,a)Gi)；用新划分的组替代G，形成新的划分new；end loop；3.若 new=则final:=且转4；否则=:new且转2；512.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器4.在final每个组Gi中选一个代表si，使得D中从Gi所有状态出发的状态转移在D中均从si出发，D中所有转向Gi中的状态转移在D中均转向si。含有D中s0的状态组G0的代表s0称为D的初态的初态，D中所有含F中状态的Gj的代表sj构成D的终态集的终态集F；5.删除死状态，即不是终态且对所有输入字符均转向其自身，或从初态不可到达的状态。最小化最小化DFA算法的主要步骤算法的主要步骤1.初始划分：终态与非终态；2.利用可区分的概念，反复分裂划分中的组Gi，直到不可再分裂；3.由最终划分构造D，关键是选代表和修改状态转移；4.消除可能的死状态和不可达状态。522.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器例2.17 用算法2.6化简DFA1初始化划分1=ABCD，E2反复分裂划分中的组：m(D,b)=E 2=ABC，D，E m(B,b)=D 3=AC，B，D，E 3？于是：final=AC，B，D，E 4根据final构造D：选代表，用A代表AC组；修改状态转移：用0123代替ABDEm(A,a)=B,m(A,b)=Cm(B,a)=B,m(B,b)=Dm(C,a)=B,m(C,b)=Cm(D,a)=B,m(D,b)=Em(E,a)=B,m(E,b)=C532.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器F由由DFA构造词法分析器构造词法分析器1.表驱动型的词法分析器表驱动型的词法分析器 有数据结构存放DFA；修改算法2.1：识别文件(而非一个记号)；满足最长匹配原则。对于输入序列：result:=a+b 正确的识别：id:=id+id 错误的识别：仅识别一个：id（result）不满足最长匹配：id（r或re或res.）542.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器2.直接编码的词法分析器直接编码的词法分析器将DFA和DFA识别输入序列的过程合并在一起，直接用程序代码模拟DFA识别输入序列。问题问题：如何用程序模拟DFA的状态和它的状态转移？1.状态和状态转移与语句的对应关系 初态程序的开始；终态程序的结束(不同终态return不同记号)；转移分情况或者条件语句(case/if)；环循环语句(loop)；return满足最长匹配原则。55void main()char buf=aba#,*ptr=buf;while(*ptr!=#)l0:while(*ptr=b)ptr+;/state 0l1:while(*ptr=a)ptr+;/state 1switch(*ptr)case a:goto l1;case b:ptr+;switch(*ptr)/state 2 case a:goto l1;case b:ptr+;switch(*ptr)/state3 case a:goto l1;case b:goto l0;case#:coutyesendl;return;default:break;default:break;default:break;break;/遇到非法字符cout no endl;562.4 2.4 从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器从正规式到词法分析器F词法分析器生成器简介词法分析器生成器简介理论基础理论基础：构造词法分析器的各个步骤均有算法。LEX的基本结构：分析表驱动器利用LEX构造词法分析器的关键：用LEX提供提供的正规式集合设计记号的模式；用LEX提供提供的语义支持识别记号或指出输入中的错误。表表驱动驱动直接编码直接编码分析器的速度慢快程序与模式的关系无关有关分析器的规模较大较小适合的编写方法工具生成手工编写572.5 2.5 本章小结本章小结本章小结本章小结词法的双重含义：词法规则词法规则词法分析词法分析F模式、记号与单词F形式化描述：正规式与正规集F记号的识别：有限自动机NFA：与正规式有对应关系，易于构造，状态数少；DFA：具有确定性，不易构造，状态数可能多；识别方法：模拟DFA、模拟NFA对于正规式r，构造自动机识别字符串x，有结论：自动机空间时间NFAO(|r|)O(|r|*|x|)DFAO(2|r|)O(|x|)582.5 2.5 本章小结本章小结本章小结本章小结F从正规式到词法分析器1.正规式描述模式2.由正规式构造NFA3.NFA的确定化（子集法：smove，-闭包）4.DFA的最小化（可区分概念）5.词法分析器：表驱动与直接编码59