词法分析与有限状态自动机课件.ppt
2023/4/3,华东师大计算机科学技术系,1,有限状态自动机,3.1.1 基本概念FA的非形式描述有限状态自动机由3部分组成：一根输入带：输入带可以理解成由一系列带块组成，每个带块上只含有一个输入符号（终结符号），其全体构成集合VT，特殊符号“”表示输入符号串的结束，VT。一个输入头：初始时，输入头指向第一个带块（即指向输入带最左端的带块），输入头每次将输入头下方带块上的输入符号读入，然后输入头向右移动一个带块。,2023/4/3,华东师大计算机科学技术系,2,基本概念,一个有限状态控制器：有限状态控制器所能处于的状态的全体组成状态集合Q，Q中有若干特殊状态：一个初始状态q0和若干最终状态qf。开始时有限状态控制器处于初始状态，以后有限状态控制器所处状态由状态转换函数决定。,2023/4/3,华东师大计算机科学技术系,3,基本概念,例1 令VT=0,1,2,3Q=S,A,B,S是初态 用-表示A是终态用+表示有向弧表示转换,2023/4/3,华东师大计算机科学技术系,4,FA的工作过程,初始时，FA处于初态，输入头指向第一个输入符，随着带上符号的读入，FA从一个状态转向另一个状态。若遇到如下情况，FA结束工作：输入头指向、FA处于终态。称输入串被FA接受。（如2030）输入头指向、FA不在终态。称输入串不被FA接受。（如203）FA无法转换。称输入串不被FA接受。（如1031）,2023/4/3,华东师大计算机科学技术系,5,FA的形式描述,定义1：有限状态自动机M是一个五元组：M(VT,Q,q0,Qf)，其中：VT：有限非空终结符集合 Q：有限非空状态集合：从QVT到Q的幂集2Q上的状态转换函数 q0：初始状态，q0Q Qf：最终状态集，Qf Q|Qf|1,2023/4/3,华东师大计算机科学技术系,6,FA的形式描述,对q,q1 Qa VT(q,a)=q1的含义为：当前状态为q，若输入头所指符号为a，则转向下一状态q1，输入头右移。是QVT2Q上的一个单射一般地(q,a)=q1,q2,qn qi Q i=1,2,n因此称FA M为不确定的FA，记为NFA。若映射是QVT Q，即对任何qQ，ai VT，(q,ai)至多只有一个元素q，称FA M是确定性的FA，记为DFA。,2023/4/3,华东师大计算机科学技术系,7,FA的形式描述,对FA的拓展Q0 Q|Q0|1 即初态可以是一个集合：从QVT*到2Q上的单值映射，即输入符可以是一个串，包括称M为一个传递图或转换系统或NFA。例1：M1(VT,Q,q0,F)VT=a,b,Q=q0,q1,q2F=q2:(q0,a)=q1(q0,b)=q2(q1,a)=q1(q1,b)=q1(q2,a)=q2(q2,b)=q1M1是一个DFA。,2023/4/3,华东师大计算机科学技术系,8,FA的表示,3.1.2 状态转换图和状态转换表状态转换图：q Q若q，q Q，aVT，且q(q,a)，初态用标记、终态用+标记,q,q,q,a,2023/4/3,华东师大计算机科学技术系,9,状态转换图,例2：例1的DFA M1可表示为：,q0,q2,q1,a,b,b,a,a,b,2023/4/3,华东师大计算机科学技术系,10,状态转换表,状态转换表（矩阵）表的列对应输入符号及特殊符号，行和M的状态q相对应。状态转换表的qi行aj列中填以(qi,aj)中的状态。表的第一行和M的初始状态q0相对应；这一列和最终状态qf行的元素标以A，以表示该状态是最终状态。,2023/4/3,华东师大计算机科学技术系,11,状态转换表,例3：例1的DFA M1可表示为：,2023/4/3,华东师大计算机科学技术系,12,示例,例4：设计一个接受以a为头符号和尾符号，中间可出现任意多个a,b的符号串的FA M。解：令：VT=a,bQ=q0,q1,q2,M是NFA,2023/4/3,华东师大计算机科学技术系,13,FA识别的语言,格局FA M的一个格局是二元组（q,w)q Q，wVT*动作对q(q,a)则FA M 的动作记为：(q,aw)(q,w)aVT wVT*对wVT*，q0是初态，称w被FA M所接受，表示为：(q0,w)(qf,)qfF,2023/4/3,华东师大计算机科学技术系,14,FA识别的语言,定义2：设M是一个FA，wVT*若：(q0,w)(qf,)qfF q0是初态称w是M的一个句子。M句子的全体称为M的语言，记为：L(M)=w|(q0,w)(qf,),wVT*例5：对例4的NFA M，输入串abba有：(q0,abba)(q1,bba)(q1,ba)(q1,a)(q2,)q2 F abba L(M)L(M)=a|a(a|b)*a,2023/4/3,华东师大计算机科学技术系,15,FA的确定化,定义3：对FA M与FA M，若L(M)=L(M)则称M与M等价。3.1.4 FA的确定化定理3.1 对任一给定的NFA M存在一个DFA M使L(M)=L(M)。分析：由定理3.1 L(DFA)L(NFA)由FA的定义 L(DFA)L(NFA)得到 L(DFA)L(NFA),2023/4/3,华东师大计算机科学技术系,16,FA的确定化,证明：“构造性证明”对给定的NFA M(VT,Q,q0,F)构造一个DFA M(VT,Q,q0,F)令VT VTQ 2Q 即Q的元素是Q的子集，Q也是有限集，|Q|=2|Q|对a VT 若(qi1,.qin,a)=qj1,qjm 令(qi1,.qin,a)=qj1,qjm QM的初态q0=q0 QF中的元素由Q中那些至少含有F中一个元素的状态组成，即qj1,qjm F 则 qjkF 1k n M是DFA,2023/4/3,华东师大计算机科学技术系,17,FA的确定化,再证：L(M)=L(M)，即要证 x VT*(q0,x)qi1,qik,qim F(q0,x)qi1,qik,qim qik F证明：对x的长度|x|作归纳法1.当|x|=0时，结论成立2.假定|x|n，结论成立3.当|x|=n,由的定义，结论成立,2023/4/3,华东师大计算机科学技术系,18,FA的确定化,例6：例4的M 是NFA 可用表的形式表示为：,确定化,2023/4/3,华东师大计算机科学技术系,19,FA的最小化,3.1.3 FA的最小化一般地说，对给定的一个FA M，可以找到任意多个不同的FA M，有L(M)=L(M)，因此得到最小的FA是有意义的。定义4：若FA的二个状态q与q，对任意一个长度为k或小于k的符号串w，q接受w当且仅当q接受w，称q与q是k等价的，否则称q与q是k可区分的。q与q等价的充要条件是对k0，q与q是k等价的。,2023/4/3,华东师大计算机科学技术系,20,FA的最小化,状态分离法基本思想：对DFA的状态集Q进行k等价类划分，即将Q划分成Qk1,.Qkn的n个子集，子集中的状态是k等价的。然后进行k+1的等价类划分直至无法进一步划分为止。则得到的等价子集中各状态等价，可合并为一个状态。,2023/4/3,华东师大计算机科学技术系,21,状态分离法,具体做法：0等价类划分：将Q划分成F与Q-F二个0等价类。若已经进行了k等价类划分，Q已经被划分成Q1，Qn（n 2)n个子集，进行k+1等价类划分。对 Qi(i=1n)q,qQi，若有aVT，（q，a）Qj 和（q，a）Ql，jl 或（q，a）存在 而（q，a）不存在或反之。则将Qi划分为二个子集Qi1，Qi2，使qQi1，q Qi2。重复2直至无法进一步划分为止。,2023/4/3,华东师大计算机科学技术系,22,状态分离法,对每一个子集Qi(i=1n)，任选一个代表qi，并修改，修改方法为：转向Qi中任何一个状态改成转向qi。若一个状态子集中某一状态是原来的开始状态，则该状态子集的代表就是新的有限状态自动机的开始状态。同理，若一个状态子集中的状态均是最终状态，则该状态子集的代表就是新的有限状态自动机的最终状态。抹去可能存在的无用状态与不可及状态。则DFA M是最小的（或简化的）。,2023/4/3,华东师大计算机科学技术系,23,状态分离法,例7：试将下图中所示的有限状态自动机M最 小化。,2023/4/3,华东师大计算机科学技术系,24,例7续一,解：最小化的过程为：初始时的划分由2个子集组成，即：（A,B,C,D,E,F,G）集合D,E,F,G不需要进一步划分，考察子集A,B,C。由于（B,a）=DD,E,F,G，而（A,a）（C,a）BA,BC，因此Q可进一步划分为：（A,C,B,D,E,F,G）。由于（A,b）CA,C，而（C，b）ED,E,F,G。因此Q可进一步划分为：（A,C,B,D,E,F,G）,2023/4/3,华东师大计算机科学技术系,25,例7续二,这时不能再划分了，得到的最小化的有限状态自动机如下表所示：,2023/4/3,华东师大计算机科学技术系,26,习题,P55 习题31.3.22.3.33.补充题将如下所示的非确定有限状态自动机M确定化和最小化。,2023/4/3,华东师大计算机科学技术系,27,试给出下述每个有限状态自动机所识别的语言,a),b),2023/4/3,华东师大计算机科学技术系,28,c),2023/4/3,华东师大计算机科学技术系,29,正则表达式（REX),3.2 正则表达式（Regular Expression）、有限状态自动机、3型文法及其相互间的关系正则表达式又称正规式有限状态自动机(FA)是正则文法（3型文法）的数学模型，正则表达式（REX）所表示的值，即为FA所能接收的语言的全体，因此这三者的关系可用下图表示：,2023/4/3,华东师大计算机科学技术系,30,正则表达式,通常称有限状态自动机和三型文法所接受的语言为正则语言。REX在词法分析中有很重要的作用，它可以精确地表示单词符号的组成，定义单词符号集。3.2.1 正规式与正规集如程序设计语言中的标识符（ID）可以用REX表示为：Let(let|Dig)*其中 Let是字母、Dig是数字,2023/4/3,华东师大计算机科学技术系,31,正则表达式,定义1：设是字母表。上的REX及其值REX所表示的符号串集合（正规集）递归定义如下：、是正则表达式，其值表示空集和；对中每一字母ai，ai是正则表达式，其值表 示集合ai；若p,q是REX，值分别为L(p)和L(q)，则p|q，pq和p*也是 上的REX，其值分别是：L(p)L(q)，L(p)L(q)，L(p)*。有限次使用上述规则得到的仍是 上的REX。,2023/4/3,华东师大计算机科学技术系,32,正则表达式,规则：优先级由高到低为：*，,|。可用（，）改变优先级。记R*R为R+值L(R+)=L(R*)L(R)。性质交换律R|S=S|R结合律R|(S|T)=(R|S)|T R(ST)=(RS)T分配律R(S|T)=RS|RT(R|S)T=RT|ST同一律R=R=R,2023/4/3,华东师大计算机科学技术系,33,正则表达式,例1试写出 0，1上下述集合的REX：所有以1开始和结束的符号串。恰含有3个1的所有符号所组成的集合。集合01，1。所有以111结束的符号串。解答：1(0|1)*1|1 0*10*10*10*01|1(0|1)*111,2023/4/3,华东师大计算机科学技术系,34,正则表达式与有限状态自动机,3.2.2 REX 和FA定理3.2（Kleene)设R是上的一个REX，则存在一个FA M，有L(M)=L(R)。反之亦然。证：1.对给定的REX到FA从REX构造FA可以分两步进行。从REX R到传递图T,X,Y,R,2023/4/3,华东师大计算机科学技术系,35,Kleene定理,反复应用下述替代规则，直至所有有向弧都以中的符号或标记为止。,A|B,2023/4/3,华东师大计算机科学技术系,36,Kleene定理,消除应用所得到的传递图中的弧，可以分为两步：首先消除环路，其次消除其他弧。a)环路的消除方法：i将环路的诸项合并为一个顶点。ii修改各个相关的有向弧。iii若环路中某一状态是最终（或初始）状 态，则新顶点是最终（或初始）状态。b）其它弧的消除有两种方法：1）子集法：即计算-Closure（T），其表示从状态集T中任何一状态沿弧可以到达的状态全体。,2023/4/3,华东师大计算机科学技术系,37,Kleene定理,其要点是：从初始状态q0的X=-Closure（q0）开始，按如下方法构造状态集：i令SetX；ii若Set中还有未考察过的状态子集Xi，则对于每一输入符号aVT，计算：T=-Closure（move（Xi,a），Set=SetT（其中move(Xi,a)=q|q(p,a),pXi）。重复执行（ii），直至不存在这样的Xi。这样得到的Set即为消除弧后的DFA。DFA的初始状态就是-Closure（q0），最终状态由那些至少含有一个最终状态的状态子集组成。,2023/4/3,华东师大计算机科学技术系,38,Kleene定理,2）逐步消除法：其要点是找到类似于下图所示，但从B再无弧引出的弧。删除状态A到状态B的弧，对每一条从状态B到状态C标记为ai的弧，增加1条从状态A到状态C标记为ai的弧。若B是最终状态，则让A为最终状态。重复上述过程直至消除全部的弧，这样得到的一般是NFA。,2023/4/3,华东师大计算机科学技术系,39,Kleene定理,例2：试给出与下图所示的传递图等价的、确定的、最小的有限状态自动机。,2023/4/3,华东师大计算机科学技术系,40,例2（续一）,解法一 子集法：M的初始状态为D，而Closure(D)=D，E，G令A=D，E，G，B=D，E，F，G VT=0，1 Closure(move(A，1)=D，E，F，GClosure(move(A，0)=FClosure(move(F，1)=GClosure(move(G，1)=D，E，GClosure(move(B，1)=D，E，F，GClosure(move(B，0)=F,2023/4/3,华东师大计算机科学技术系,41,例2（续二）,所以，DFA M如下表所示：其中A=D,E,F,G、B=D,E,G。注意：状态F与表示该状态是最终状态的标记F的不同。,2023/4/3,华东师大计算机科学技术系,42,例2（续三）,解法二 逐步消除法：a)消除状态E到G的弧：,2023/4/3,华东师大计算机科学技术系,43,例2（续四）,b)消除状态D到E的弧：,2023/4/3,华东师大计算机科学技术系,44,例2（续五）,消除所有弧后得到的状态表,2023/4/3,华东师大计算机科学技术系,45,例2（续六）,c)确定化的DFA如下表所示：,2023/4/3,华东师大计算机科学技术系,46,Kleene定理,从传递图T到REX设传递图T为：逐步消除个状态或弧 得到只剩状态X、Y，消除方法为：略。得到：,S,a,b,c,d,f,f1,f2,X,Y,+,R,X,Y,2023/4/3,华东师大计算机科学技术系,47,正则表达式与有限状态自动机,例3：设V=a,b,V上的正则表达式R=ba|a+：试设计接收R所表示的符号串集合的确定的，最小的有限状态自动机M。解：正则表达式R可等价地改写为：R=(ba|a)*(ba|a)或R=(ba|a)(ba|a)*。有限状态自动机M=(V,Q,q0,Qf)，其中V=a,b,Q=S,A,B，q0=S，Qf=B，如下图所示,显然M是确定的和最小的。,2023/4/3,华东师大计算机科学技术系,48,2023/4/3,华东师大计算机科学技术系,49,3.2.3 有限状态自动机与3型文法定理3.3 对任一正则文法G，存在有限自动机M，使得L(M)=L(G)。反之亦然。证：1.设G=（VN，VT，p，），令与其对应的M（VT，Q，Qf)其中：VT，相同，即作为M的开始状态。令QVNF，FVN 若aP，让（,a）中含有 若aP，让（,a）中含有F aVT，令（F，a）令QfF 容易证明L(M)=L(G)。(例见P47）,2023/4/3,华东师大计算机科学技术系,50,设M是DFA M（VT，Q，Qf），令与其对应的G=（VN，VT，p，），其中：VT，相同，VNQ 若（,a）C，Q，CQf，让aP 若（,a）C，Q，CQf，让 aP或aP 容易证明L(M)=L(G)。（例见P49）,2023/4/3,华东师大计算机科学技术系,51,3.2.4 正则表达式与正则文法定理3.4 对任一正则文法G，存在REX R，使得L(R)=L(G)。反之亦然。证：一、从正则文法G到REX R 1.将G中每个非终结符表示为关于它的正则式方程，得到一个联立方程组。即对a|b 为：ab 2.如ab 则解为：a*b 3.利用REX的分配律、结合率和交换律求正则式方程组的解R。容易证明L(R)=L(G)。（例见P36）,2023/4/3,华东师大计算机科学技术系,52,二、从REX R到正则文法G对V上的REX R及正则文法G=（VN，VT，p，）VT=V。R让R。如a，b是REX，则对形如ab 的产生式转换为a及b，VN。对形如a*b转换为a|b。重复使用规则3.和4.，直至每个产生式至多含有一个非终结符。容易证明L(R)=L(G)。（例见P37）,2023/4/3,华东师大计算机科学技术系,53,例4：对例3的REX R=(ba|a)*(ba|a)，试设计接收R所表示的符号串集合的正则文法G。解：正则文法G=VT,VN,P,，其中VT=a,b，VN=,先让(ba|a)(ba|a)*并转换为：(ba|a)ba|a(ba|a)*ba|a|ba|b aba|b a注意：可以改为以及消除的方法，得：,2023/4/3,华东师大计算机科学技术系,54,P为：a|b|a a|b|a a|a,2023/4/3,华东师大计算机科学技术系,55,习题,P55 习题33.13.43.53.63.73.83.93.103.11,2023/4/3,华东师大计算机科学技术系,56,3.3 词法分析程序的设计和实现,词法分析程序从输入串中识别单词。单词的构词规则可由状态转换图（FA）或REX表示。将FA确定化、最小化即得到识别单词的FA。编程实现FA，即得到词法分析程序。,2023/4/3,华东师大计算机科学技术系,57,1.词法分析程序的任务及环境,词法分析程序的任务是：a)识别源程序组成的输入符号中语义独立的最小的词法单位单词（token）。b)删除注解和其他与输入介质相关的符号（如空格、回车等）。c)报告各种不符合程序设计语言规定的词法错误。d)符号表的维护（插入、查找),2023/4/3,华东师大计算机科学技术系,58,单词符号的种类单词是程序语言最基本的语法单位,通常有五种:(1)基本字：有的称关键字或保留字,如if、while、for、do、goto等(2)标识符：用户定义各种变量、数组、函数、过程等的名字，以字母打头后接若干个字母、数字。如X2、Len、getword(3)常数：如216、31.4(4)运算符：如+、=、*、/等；(5)界限符：如;、:、(、)及双字符界符:=、/*、*/及空白符等。（1）、（4）、（5）常可合为一，分为单、双字符界限符。,2023/4/3,华东师大计算机科学技术系,59,单词的编码词法分析程序输出的是统一格式的单词，形式为：(type,value,lineNo,columnNo)一般可分为三类：标识符：表示为（ID,addr)，addr是标识符在符号表的位置。常数：表示为（N,addr）addr是常数在常数表的位置。界限符：表示为（DEL,code)，将关键字、运算符、单（双）界限符统一预先编号，则code为界限符的内部码。,2023/4/3,华东师大计算机科学技术系,60,词法分析程序的实现可以有两种方案：把词法分析程序视为语法分析部分的一个子程序，每调用一次词法分析程序就扫描一个单词。把词法分析程序视为编译程序的一个独立模块，词法分析程序一次扫描全部的输入符号。常用的方法是a），优点是不用形成中间文件，直接生成符号表。,2023/4/3,华东师大计算机科学技术系,61,2.词法分析程序的设计,识别单词的FA的设计：,0,1,3,7,空白,字母|数字,字母,非字母与数字,数字,数字,非数字,界限符,非法字符,2,4,5,6,2023/4/3,华东师大计算机科学技术系,62,状态2的处理流程：查保留字 得内部码，输出（DEL，code）查或送符号表得到addr,输出（ID,addr)状态4的处理流程：检查前一单词，决定正负号转换相应的常数表示（二、八、十六进制）查或送常数表得到addr，输出（N,addr),Y,N,2023/4/3,华东师大计算机科学技术系,63,状态5的处理流程：若为.按小数点处理，转状态4 取下一字符 是否为双字符界限符 查表得到内部码，输出（DEL，code)回送，查表得到内部码，输出（DEL，code)状态6的处理流程：报错,Y,Y,N,N,2023/4/3,华东师大计算机科学技术系,64,说明,上述的FA只是一个粗框架，具体实现时应根据不同语言的词法规则，作必要的改进和相应的处理。特定要求的处理：如true、false表示真、假常数：NOT、IN等是运算符；.EQ.表示逻辑相等；允许0 x1f、35L等作常数等等。无符号数的识别：如无符号数用REX表示为：(D+E|D+.D+E|E|.D+E)(+|-)D|D)D*|D+|D*.D+其中D表示数字0，1，9，则相应的最小的DFA为：,2023/4/3,华东师大计算机科学技术系,65,E,E,+,D,D,D,D,.,D,.,E,+,D,+,D,2023/4/3,华东师大计算机科学技术系,66,超前搜索在FORTRAN语言中，关键字不是保留字，空格不是分隔符。因此：对语句 100 DO 110 I=1，10（循环语句，DO是关键字）100 DO 110 I=1.10（赋值语句，DO110I是标识符）拼字与缓冲区的组织P22的左、右两区的缓冲区组织形式。用getline();读入一行，如:char*fgets(char*S,int n,FILE*fp)这样拼字时只需移动缓冲区指针即可。while(*chp=)chp+;,2023/4/3,华东师大计算机科学技术系,67,3.词法分析程序的实现,FA的状态转换图可以视为一个程序的粗框图：FA程序状态子程序（程序段）状态转换程序的控制流,
