第四章 词法分析.ppt

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

1、第四章词法分析第四章词法分析 本章将讨论词法分析程序的设计原则，本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程单词的描述技术，识别机制及词法分析程序的自动构造原理序的自动构造原理。4.1 4.1 词法分析程序词法分析程序4 4.2.2 正规表达式与正规集（正规语言）正规表达式与正规集（正规语言）4.3 4.3 有穷自动机有穷自动机4.44.4 词法分析程序词法分析程序的的自动自动构造构造第四章第四章 词法分析词法分析本章重点本章重点单词的描述工具单词的描述工具单词的识别系统单词的识别系统设计和实现词法分析程序设计和实现词法分析程序首先需要描述和刻画程序设计语言中的原子单

2、首先需要描述和刻画程序设计语言中的原子单位位单词，其次需要识别单词和执行某些相单词，其次需要识别单词和执行某些相关的动作。关的动作。描述程序设计语言的词法的机制是正则表达式，描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。识别机制是有穷状态自动机。回顾回顾 什么是词法分析程序什么是词法分析程序实现词法分析（实现词法分析（lexical analysislexical analysis）的程序的程序逐个读入源程序字符并按照构词规则切分成一系逐个读入源程序字符并按照构词规则切分成一系列单词。列单词。词法分析程序的主要任务：词法分析程序的主要任务：读源程序，产生单词符号读源程序，

3、产生单词符号词法分析程序的其他任务：词法分析程序的其他任务：滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序，追踪换行标志，复制出错源程序，宏展开，宏展开，词法分析程序与语法分析程序的接口词法分析程序与语法分析程序的接口1.词法分析单独作为一遍词法分析单独作为一遍2.词法分析程序作为单独的子程序词法分析程序作为单独的子程序S.P.(字符串字符串)词法分析词法分析S.P.(符号串符号串)语法分析语法分析第一遍第一遍第二遍第二遍单词串单词串取单词取单词S.P.(字符串字符串)词法分词法分析程序析程序语法分语法分析程序析程序单词单词4.14.1词法分析程序的设计词法

4、分析程序的设计单词的种类单词的种类（1 1）关键）关键字：字：if、for、while（2 2）标识符：如变量名标识符：如变量名,函数名等函数名等（3 3）常数：常数：（4 4）运算符：运算符：+、-、*（5 5）分界符：）分界符：,、;、(、)词法分析程序的输出形式词法分析程序的输出形式单词符号是一个程序设计语言的基本语法符号单词符号是一个程序设计语言的基本语法符号词法分析程序的输出形式词法分析程序的输出形式-二元式二元式单词类别单词类别 单词的属性值单词的属性值单词类别可以用整数编码表示单词类别可以用整数编码表示:单词类别单词类别关键字关键字标识符标识符常数常数运算符运算符分界符分界符编码

5、编码1 12 23 34 45 5单词类别单词类别单词的属性值单词的属性值1int2指向指向x的符号表入口指针的符号表入口指针4=3105,2指向指向y的符号表入口指针的符号表入口指针4=3205;intx=10,y=20;词法分析的结果词法分析的结果 词法分析工作从语法分析工作独立出来词法分析工作从语法分析工作独立出来的原因：的原因：简化设计简化设计改进编译效率改进编译效率增加编译系统的可移植性增加编译系统的可移植性 4.24.2单词的描述工具单词的描述工具 程序设计语言中的单词是基本语法程序设计语言中的单词是基本语法成分成分.单词符号的语法可以用有效的工具单词符号的语法可以用有效的工具加以

6、描述，并且基于这类描述工具，实加以描述，并且基于这类描述工具，实现词法分析程序的自动构造现词法分析程序的自动构造.多数程序设计语言的单词的语法都多数程序设计语言的单词的语法都能用正规文法能用正规文法(3(3型文法型文法)来描述来描述.正规文法正规文法3 3型文法（正规文法）：型文法（正规文法）：任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中，其中AVAVN N ，BVBVN N ，aVaVT T *程序设计语言中几类单词的规则描述程序设计语言中几类单词的规则描述:|,|；|（|）|正规式正规式也称正则表达式正规式也称正则表达式,正规表达式正规表达式（regular ex

7、pressionregular expression）是说明单词的模是说明单词的模式式(pattern)pattern)的一种重要的表示法（记号），的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正单词符号。下面是正规式和它所表示的正规集的递归定义。规集的递归定义。定义（正规式和它所表示的正规集）：定义（正规式和它所表示的正规集）：设字母表为设字母表为，辅助字母表，辅助字母表 =，。1 1。和和 都是都是 上的正规式，它们所表示的正规上的正规式，它们所表示的正规集分别为集分别为 和和 ；2 2。任何任何a a

8、 ，a a是是 上的一个正规式，它所表上的一个正规式，它所表示的正规集为示的正规集为 aa；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)。l其中的其中的“”读为读为“或或”（也有使用也有使用“+”代替代替 “”的）；的）；“”读为读为“连接连接”；“”读为读为“闭包闭包”（即，任意有限次的自重复连接）。（即，任意有

9、限次的自重复连接）。l在不致混淆时，括号可省去，但规定算符的优先顺序在不致混淆时，括号可省去，但规定算符的优先顺序为为“”、“”、“”。连接符。连接符“”一般一般可省略不写。可省略不写。“”、“”和和“”都是左结合都是左结合的。的。4 4。仅由有限次使用上述三步骤而定义的表仅由有限次使用上述三步骤而定义的表达式才是达式才是 上的正规式，仅由这些正规式所上的正规式，仅由这些正规式所表示的集合才是表示的集合才是 上的正规集。上的正规集。正规式与正规集的例子正规式与正规集的例子令令=a，b，上的正规式和相应的正规集的例子有：上的正规式和相应的正规集的例子有：正规式正规式 正规集正规集a aa b a

10、,bab ab(a b)(a b)aa,ab,ba,bba ,a,a,任意个任意个a的串的串(a b),a,b,aa,bb,ab 所有由所有由a,b组成的串组成的串(a b)(aa bb)(a b)上所有含有两个相继的上所有含有两个相继的a或两个相继的或两个相继的b组成的串组成的串 例例=d d，e e，+，-,-,则则 上的正规式上的正规式 d d(dddd )(e(+)(e(+-)dddd )其中其中d d为为0 0-9-9的数字。的数字。表示的是无符号数的集合。表示的是无符号数的集合。程序设计语言的单词都能用正规式来定义程序设计语言的单词都能用正规式来定义.若两个正规式若两个正规式e1和

11、和e2所表示的正规集相同所表示的正规集相同,则说则说e1和和e2等价等价,写作写作e1=e2。例如：例如：e1=(a b)，e2=b a又如：又如：e1=b(ab),e2=(ba)b e1=(a b),e2=(a b)设设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 是是“连接连接”的恒等元素的恒等元素零一律零一律

12、6。r r=r“或或”的抽取律的抽取律 r=r rr 1.正规文法正规文法正规式正规式规则规则1 1规则规则2 2规则规则3 3文法产生式文法产生式正规式正规式AxB,ByAxB,ByAxA|yAxA|yAx,AyAx,AyA=A=xyxyA=xA=x*y yA=x|yA=x|y步骤步骤1将每条产生式改写为正规式；将每条产生式改写为正规式；步步骤骤2用用代代入入法法解解正正规规式式方方程程组组，最最后后只只剩剩下下一一个个开开始始符符号号定定义义的的正正规规式式，其其中中不不含含非非终终结符。结符。正规文法与正规式正规文法与正规式【例例】GS:SaA|aAdA|dS=aA|aA=d*d代入代入

13、:S=ad*d|aad*4.3 4.3 有穷自动机有穷自动机有穷自动机是一种有穷自动机是一种数学模型数学模型，有穷自动机有穷自动机(也称也称有限自动机有限自动机)作为一种识别装置，它能准确地识作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方正是为词法分析程序的自动构造寻找特殊的方法和工具。法和工具。有穷自动机分为两类：有穷自动机分为两类：确定确定的有穷自动机的有穷自动机(D Deterministic eter

14、ministic F Finite inite A Automata)utomata)和和不确定不确定的的有穷自动机有穷自动机(N Nondeterministic ondeterministic F Finite inite A Automata)utomata)。关于关于有穷自动机我们将讨论如下内容有穷自动机我们将讨论如下内容确定的有穷自动机确定的有穷自动机DFADFA不确定的有穷自动机不确定的有穷自动机NFANFANFANFA的确定化的确定化DFADFA的最小化的最小化4.3.14.3.1确定的有穷自动机确定的有穷自动机DFADFADFADFA定义：定义：一个确定的有穷自动机（一个确定的

15、有穷自动机（DFADFA）M M是一个五元组：是一个五元组：M=M=（K K，f f，S S，Z Z）其中其中1.1.K K是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；2.2.是一个有穷字母表，它的每个元素称为一个输入符号，所是一个有穷字母表，它的每个元素称为一个输入符号，所以也称以也称为输入符号表；为输入符号表；3.3.f f是转换函数，是在是转换函数，是在K KK K上的映射，即，如上的映射，即，如 f f（kiki，a a）=kjkj，（，（kikiK K，kjkjK K）就意味着，当前状态为就意味着，当前状态为kiki，输入符为输入符为a a时，将转

16、换为下一个状态时，将转换为下一个状态kjkj，我们把我们把kjkj称作称作kiki的一个后继状态；的一个后继状态；4.4.S SK K是唯一的一个初态；是唯一的一个初态；5.5.Z Z K K是一个终态集，终态也称可接受状态或结束状态。是一个终态集，终态也称可接受状态或结束状态。一个一个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一个一个DFADFA可以表示成一个状态图可以表示成一个状态图(或称状态转换图或称状态

17、转换图)。假定假定DFA MDFA M含有含有m m个状态，个状态，n n个输入字符，那么这个状态图个输入字符，那么这个状态图含有含有m m个结点，每个结点最多有个结点，每个结点最多有n n个弧射出，整个图含有个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双唯一一个初态结点和若干个终态结点，初态结点冠以双箭头箭头“=”或标以或标以“-”，终态结点用双圈表示或标以，终态结点用双圈表示或标以“+”，若若 f(kf(ki i,a,a)=)=k kj j，则从状态结点则从状态结点k ki i到状态结点到状态结点k kj j画标记为画标记为a a的弧；的弧；DFA 的状态图表示的状态

18、图表示bSUVQaaaa，bbb一个一个DFADFA还可以用一个矩阵表示，该矩阵的行表示还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即行和输入字符列下的新状态，即k k行行a a列为列为f(k,a)f(k,a)的值。用双箭头的值。用双箭头“=”标明初态；否则第一行即标明初态；否则第一行即是初态，相应终态行在表的右端标以是初态，相应终态行在表的右端标以1 1，非终态，非终态标以标以0 0。DFA 的矩阵表示的矩阵表示字符字符状态状态0001*上的符号串上的符号串t t被被DFADFA M M接受

19、接受若存在一条初始状态到某一终止状态的路径，且这若存在一条初始状态到某一终止状态的路径，且这条路径上所有弧的标记符号连接成符号串条路径上所有弧的标记符号连接成符号串，则称则称为为DFA MDFA M（接受）识别。接受）识别。M=（K，f，S，Z）若若t *，f(S，t)=P，其中其中S为为 M的开始状态，的开始状态，P Z，Z为终态集。为终态集。则称则称t为为DFA M所接受（识别）所接受（识别）.为了说明为了说明DFADFA如何作为一种识别机制如何作为一种识别机制,我们还要理解我们还要理解下面的定义下面的定义 *上的符号串上的符号串t t在在DFADFA M M上运行上运行一个输入符一个输入

20、符号号串串t，（，（将它表示成将它表示成t1tx的形式，其中的形式，其中t1，tx *）在）在DFA M=（K，f，S，Z）上上运行的定义为：运行的定义为：f（Q，t1tx）=f（f（Q，t1），），tx）例：证明例：证明t=baab被下图的被下图的DFA所接受所接受。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属于终态。属于终态。得证。得证。bSUVQabba,baaDFA MDFA M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M).L(M).对于任何两个有穷自

21、动机对于任何两个有穷自动机M M和和MM，如果如果L(M)=L(M)，则称则称M M与与MM是等价的是等价的.结论：结论：上一个符上一个符号号串集串集V V 是正规的，当且仅当是正规的，当且仅当存在一个存在一个 上的确定有穷自动机上的确定有穷自动机M M，使得使得V=L(M)V=L(M)。DFADFA的确定性表现在的确定性表现在l 转换函数转换函数f:Kf:KKK是一个单值函数，也就是一个单值函数，也就是说，对任何状态是说，对任何状态kKkK，和输入符号和输入符号aa，f(k,a)f(k,a)唯一地确定了下一个状态。唯一地确定了下一个状态。l 从状态转换图来看，若字母表从状态转换图来看，若字母

22、表含有含有n n个输入个输入字符，那末任何一个状态结点最多有字符，那末任何一个状态结点最多有n n条弧射出，条弧射出，而且每条弧以一个不同的输入字符标记。而且每条弧以一个不同的输入字符标记。bSUVQabba,baaDFADFA的行为很容易用程序来模拟的行为很容易用程序来模拟.DFA M=DFA M=（K K，f f，S S，Z Z）的行为的模拟程序的行为的模拟程序K:=SK:=S；c:=c:=getchargetchar;while c!=while c!=结束符结束符 do do K:=f(K,c);K:=f(K,c);c:=c:=getchargetchar;if K is in Z t

23、hen return(if K is in Z then return(yesyes)else return(else return(nono)4.3.24.3.2不确定的有穷自动机不确定的有穷自动机NFANFA定义定义NFA M=NFA M=K K，f f，S S，Z Z，其中其中 1.K 1.K为状态的有穷非空集，它的每个元素称为一为状态的有穷非空集，它的每个元素称为一个状态个状态.2.2.为有穷字母表为有穷字母表,它的每个元素称为一个输入它的每个元素称为一个输入字符字符.3.f 3.f为为K K *到到K K的子集的一种映射的子集的一种映射,f f是一个是一个多值函数多值函数 4.S4.

24、S K K是初始状态集，是初始状态集，Z Z K K为终止状态集为终止状态集.例子例子 NFA M=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1）=Pf（S，1）=S，Z有穷自动机的不有穷自动机的不确定性表现在在确定性表现在在某个状态下，对某个状态下，对于某个输入字符于某个输入字符存在多个后继状存在多个后继状态，即状态的转态，即状态的转向是不确定的向是不确定的状态图表示 f（S，0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1）=Pf（S，1）=S，ZSPZ00,1111矩阵表示矩阵表示矩阵表示矩阵表示0 01 1SPS,Z0 0

25、PZ0 0ZPP1 1类似类似DFA,DFA,对对NFA M=NFA M=K K，f f，S S，Z Z 也有如下定也有如下定义义*上的符号串上的符号串t t在在NFANFA M M上运行上运行.一个输入符号串一个输入符号串t t，（，（我们将它表示成我们将它表示成TtTt1 1的形式，其的形式，其中中TT，t t1 1 *）在）在NFA MNFA M上运行的定义为：上运行的定义为：f f（Q Q，Tt Tt1 1）=f=f（f f（Q Q，T T），），t t1 1）其中其中QKQK.*上的符号串上的符号串t t被被NFANFA M M接受接受 即对于即对于*中的任何一个串中的任何一个串t,

26、t,若存在一条从若存在一条从某一初态结到某一终态结的道路某一初态结到某一终态结的道路,且这条道路上所且这条道路上所有弧的标记字依序连接成的串等于有弧的标记字依序连接成的串等于t,t,则称则称t t可为可为NFA NFA M M所接受所接受(识别识别)l DFADFA是是NFANFA的特例的特例.对每个对每个NFA NFA N N一定存一定存在一个在一个DFADFA ，使得使得 L(M)=L(N)L(M)=L(N)。对对每个每个NFA NNFA N存在着与之等价的存在着与之等价的DFA MDFA M。l与某一与某一NFANFA等价的等价的DFADFA不唯一不唯一.l有一种算法，将有一种算法，将N

27、FANFA转换成接受同样语言转换成接受同样语言的的DFA.DFA.这种算法称为子集法这种算法称为子集法.4.3.3 NFA 4.3.3 NFA 转换为等价的转换为等价的DFA DFA 从从NFANFA的矩阵表示中可以看出，表项的矩阵表示中可以看出，表项通常是一状态的集合，而在通常是一状态的集合，而在DFADFA的矩阵表的矩阵表示中，表项是一个状态，示中，表项是一个状态，NFANFA到相应的到相应的DFADFA的构造的基本思路是：的构造的基本思路是：DFADFA的每一个状态对应的每一个状态对应NFANFA的一组状的一组状态态.DFADFA使用它的状态去记录在使用它的状态去记录在NFANFA读入读

28、入一个输入符号后可能达到的所有状态一个输入符号后可能达到的所有状态.定义对状态集合定义对状态集合I I的几个有关运算：的几个有关运算：1.1.状态集合状态集合I I的的-闭包闭包，表示为，表示为-closure(I)closure(I)，定义为一状态集，是状态集定义为一状态集，是状态集I I中的任何状态中的任何状态S S经任意经任意条条弧而能到达的状态的集合。弧而能到达的状态的集合。状态集合状态集合状态集合状态集合I I I I的任何状态的任何状态的任何状态的任何状态S S S S都属于都属于都属于都属于-closure(I-closure(I-closure(I-closure(I)。2.2

29、.状态集合状态集合I I的的a a弧转换弧转换，表示为，表示为move(I,a)move(I,a)定义为状定义为状态集合态集合J J，其中其中J J是所有那些可从是所有那些可从I I中的某一状态经中的某一状态经过一条过一条a a弧而到达的状态的全体。弧而到达的状态的全体。状态集合状态集合I的有关运算的例子的有关运算的例子I=1,-closure(I)=1,2；I=5,-closure(I)=；move(1,2,a)=5,3,4-closure(5,3,4)=；12534687aaa5,6,22,3,4,5,6,7,8 NFANFA确定化算法确定化算法:假设假设NFA N=(K,NFA N=(K

30、,f,K,f,K0 0,K,Kt t)按如下办法构按如下办法构造一个造一个DFA M=(S,DFA M=(S,d,S,d,S0 0,S,St t)，使得使得L(M)=L(N)L(M)=L(N)：1.M1.M的状态集的状态集S S由由K K的一些子集的一些子集组成。用组成。用 S S1 1 S S2 2.S Sj j 表示表示S S的元素，其中的元素，其中S S1 1,S,S2,2,.,.S Sj j是是K K的状态。并且约定，状态的状态。并且约定，状态S S1 1,S,S2,2,.,.S Sj j是按某是按某种规则排列的，即对于子集种规则排列的，即对于子集 S S1 1,S,S2 2=S=S2

31、 2,S S1,1,来说，来说，S S的状态就是的状态就是 S S1 1 S S2 2；2 2 M M和和N N的输入字母表是相同的，即是的输入字母表是相同的，即是；3 3 转换函数是这样定义的：转换函数是这样定义的：d(d(S S1 1 S S2,2,.S Sj j,a)=a)=R R1 1R R2 2.R Rt t 其中其中 R R1,1,R R2,2,.,R Rt t =-closure(moveclosure(move(S S1 1,S,S2,2,.,.S Sj j,a)a)4 4 S S0 0=-closure(Kclosure(K0 0)为为M M的开始状态；的开始状态；5 5 S

32、 St t=S Si i S Sk k.S Se e，其中，其中 S Si i S Sk k.S Se e S S且且 S Si i ,S Sk k,.,.S Se e K Kt t（所有包含终态的子（所有包含终态的子集都构成集都构成DFADFA的终态）的终态）构造构造NFA N的的状态状态K K的子集的子集的算法：的算法：假定所构造的子集族为假定所构造的子集族为C，即即C=(T1,T2,.TI),其其中中T1,T2,.TI为状态为状态K的子集。的子集。1 开始，令开始，令-closure(K0)为为C中唯一成员，并中唯一成员，并且它是未被标记的。且它是未被标记的。2 while（C中存在尚未

33、被标记的子集中存在尚未被标记的子集T）do 标记标记T；for 每个输入字母每个输入字母a do U:=-closure(move(T,a)；if U不在不在C中中 then 将将U作为未标记的子集加在作为未标记的子集加在C中中 用子集法对用子集法对NFANFA确定化确定化：(1)(1)构造一张转换表构造一张转换表,该表的第该表的第1 1列为状态子集列为状态子集I,I,不同输入符不同输入符a a 对应表中一列对应表中一列IaIa。(2)(2)表的首行首列为表的首行首列为 _CLOSURE(k_CLOSURE(k0 0)。(即初态的即初态的 闭包）闭包）(3)(3)根据首行首列中的状态集根据首行

34、首列中的状态集,为每个输入符为每个输入符a a求求-closure(move(I,a)并记入相应的并记入相应的IaIa列中。若此列中。若此IaIa不同于不同于第第1 1列已存在的所有状态子集列已存在的所有状态子集,则将其写入空行中的第则将其写入空行中的第1 1列。列。(4)(4)重复重复(3)(3)直至对每个直至对每个I I及及a a均已求得均已求得IaIa,且无新的状态子集且无新的状态子集IaIa加入第加入第1 1列为止。列为止。(5)(5)重命名第重命名第1 1列的每个状态集列的每个状态集,所得状态转换矩阵即为与所得状态转换矩阵即为与NFA MNFA M等价的等价的DFA MDFA M”。

35、P59页例页例4.8 NFA的确定化 例子例子4f35621iaaaabbbb4f35621i aaaabbbb 等价的等价的DFAaCDBAEFSbaaaaabbbbbabF4.3.4 确定有穷自动机的化简确定有穷自动机的化简如果不同的如果不同的DFA能识别相同的语言，则称它们是等价的能识别相同的语言，则称它们是等价的DFA。在等价的在等价的DFA中，如果某一个中，如果某一个DFA的状态数是最少的，则这个的状态数是最少的，则这个DFA是最简的。是最简的。对于任一个对于任一个DFA，存在一个唯一的状态最少的等价的存在一个唯一的状态最少的等价的DFA最简的最简的DFA它没有多余它没有多余状态和等

36、价状态状态和等价状态定义定义1多余状态：从开始状态出发多余状态：从开始状态出发,任何输入串也不能到达的状态任何输入串也不能到达的状态01s0s1s2s3s5s7s1s5s1s2s2s5s5s1s1s3s0s101s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s6例例:画画状态图可状态图可以看出以看出s4,s6,s8为不可达状为不可达状态应该消除态应该消除定义定义2等价状态等价状态状态状态s和和t的等价条件是的等价条件是:状态状态S和和T必须同时为终态或非终态必须同时为终态或非终态对于所有输入符号，对于所有输入符号，S和和T必须转换到等价

37、的状态里必须转换到等价的状态里C和和F同是终态同是终态,C和和F读入读入a都到达都到达C,读入读入b都到达都到达E.所以所以C和和F等价等价aCDBAEFSbaaaaabbbbbabF“分割法分割法”DFA的最小化算法的核心的最小化算法的核心 把一个把一个DFA的状态分成一些不相交的子集，使得的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的子集中的任何两个状态都是等价的.DFA的最小化算法的最小化算法 DFA M=DFA M=（K,f,kK,f,k0 0,k kt t),),最小状态最小状态DFA

38、 M 1.1.构造状态的初始划分构造状态的初始划分：终态终态k kt t 和非终态和非终态K-K-k kt t两组两组(group)group)2.2.对终态集和非终态集，分别用输入字母后到达的状态是对终态集和非终态集，分别用输入字母后到达的状态是否等价进行进一步划分，直到任何子集的状态都是可区否等价进行进一步划分，直到任何子集的状态都是可区别的。别的。3 3、用一个状态代表一个子集即可得到最简的、用一个状态代表一个子集即可得到最简的DFADFA。DFA的最小化的最小化例子例子0:0:Y,A,B C,D,E,FY,A,B C,D,E,F1:Y,A,B 1:Y,A,B a AA Y,Y,B Bb

39、B B Y Y DBAYaaabbbbaCDBAEFYbaaaaaabbbbbbaC,D,E,F不可再划分不可再划分最后划分得到：最后划分得到：A,Y,B,C,D,E,FP61例例4.95724361srartaaaaaaabbbbbbb化简后化简后15 5243aaaaabbbbb4 4.4.4正规式与有穷自动机的等价性正规式与有穷自动机的等价性有穷自动机和正规表达式的等价性有穷自动机和正规表达式的等价性,即即：1.对于对于上的一个上的一个NFA M，可以构造一个，可以构造一个上的正上的正规式规式R,R,使得使得L(R)=L(M)。2 2.对于对于上的一个正规式上的一个正规式R，可以构造一个

40、，可以构造一个上的上的NFA M，使使的的L(M)=L(R)。1.NFAM正规式正规式R(1)(1)在在M M上加两个结点上加两个结点x,yx,y，从，从s s结点用结点用弧到弧到M M的所的所有初态，从有初态，从M M的所有终态的所有终态用用到到y y结成与结成与M M等价的等价的MM，MM只有一个初态只有一个初态x x和一个终态和一个终态y.y.例例:M M:03214starta,ba,ba,bbbaa解解:(1)(1)加加x yx yx03412yaa,ba,ba,babb(2)逐步消去逐步消去M中的所有结点中的所有结点,直至剩下直至剩下x和和y结点结点,在消结在消结过程中过程中,逐步

41、用正规式来标记弧逐步用正规式来标记弧,规则如下规则如下:1 1.对于对于代之为代之为2 2.对于对于 代之为代之为 3 3.对于对于代之为代之为R R1 1R R2 21 12 23 33 31 1R R1 1R R2 21 12 22 21 1R R2 2R R1 1R R2 2R R1 1|R R1 1R R3 31 12 23 33 31 1R R1 1R R2 2R R3 3R R2 2(2)(2)消除消除M M中的所有结点中的所有结点a|bx024yaabba|ba|bx0yaa(a|b)*bb(a|b)*a|b解解:(1)(1)加加xyxyx03412yaa,ba,ba,babbx

42、y(a|b)*(aa|bb)(a|b)*2.正规式正规式RNFAM（1 1）对对NFA NFA M M构构造造一一个个广广义义的的状状态态图图，其其中中只只有有一一个初态个初态x x和终态和终态y y，连接，连接x x和和y y的有向弧标记为正规式。的有向弧标记为正规式。（2 2）对对正正规规式式依依次次进进行行分分解解，分分解解的的过过程程是是一一个个不不断断加加入入结结点点和和弧弧的的过过程程，直直到到转转换换图图上上的的所所有有弧弧标记上都是字母表标记上都是字母表上的元素或上的元素或 为止。为止。若若s,ts,t为为上的正规式上的正规式(a)(a)对于正规式对于正规式R=R=ststx

43、xy yststx xy ys st tt t(b)(b)对于正规式对于正规式R=s|tR=s|tx xy ys|ts|tx xy ys st t(c)(c)对于正规式对于正规式R=R=rsrs*t tx xy yrsrs*t tx xy yrt ttsiyx(a|b)*abb例例:为为R=(a|b)R=(a|b)abbabb构造构造NFA,NFA,使得使得L(N)=L(R)L(N)=L(R)*yabbia|bjxyabbiajxbbybiajxkalb构造正规式相应的构造正规式相应的 NFA:1(0|1)*1014.5 4.5 正规文法与正规文法与有穷自动机的等价性有穷自动机的等价性（1）对

44、对于于NFAM，存存在在一一个个左左线线性性文文法法（右右线线性性文文法法）G，使使得得L(G)=L(M)；(左左线线性性文文法法:A或或A)（2）对对于于左左线线性性文文法法（右右线线性性文文法法）G，可可以以构构造造一个一个NFAM，使得使得L(M)=L(G)。1.NFA正规文法正规文法（1 1）NFANFA的字母表为文法的终结符号集；的字母表为文法的终结符号集；（2 2）NFANFA的状态集为文法的非终结符号集；的状态集为文法的非终结符号集；（3 3）NFANFA的初态对应于文法的开始符号；的初态对应于文法的开始符号；（4 4）NFANFA的转换函数的转换函数f(A,t)=Bf(A,t)

45、=B，写成一个产生式写成一个产生式AtBAtB；（5 5）对）对NFANFA的终态的终态Z Z，增加一个产生式增加一个产生式ZZ。ABt例例:给出如图给出如图NFANFA等价的正规文法等价的正规文法G GABCDaaabbbbG=（A，B，C，D，a，b，P，A）其中其中P:AaBAbDBbCCaACbDCDaBDbDD（1 1）文法的终结符号集为）文法的终结符号集为NFANFA的字母表；的字母表；（2 2）文法的非终结符号集为）文法的非终结符号集为NFANFA的状态集；的状态集；（3 3）文法的开始符号作为）文法的开始符号作为NFANFA的初态；的初态；（4 4）对文法中形如）对文法中形如A

46、tBAtB的产生式，其中的产生式，其中t t为为终结符或终结符或，A A和和B B为非终结符，构造为非终结符，构造NFANFA的一个的一个转换函数转换函数f(A,t)=Bf(A,t)=B；（5 5）对文法中形如对文法中形如AtAt的产生式，构造的产生式，构造NFANFA的的一个转换函数一个转换函数f(A,t)=Zf(A,t)=Z。2.正规文法正规文法NFA例例:求与文法求与文法GSGS等价的等价的NFANFA GS:GS:SaA|bB|SaA|bB|AaB|bAAaB|bA BaS|bA|BaS|bA|SZABstartaaabbb求得：求得：正规文法正规文法NFA正规式正规式654312DF

47、A最小化最小化转换方法转换方法874.64.6词法分析程序的自动生成工具词法分析程序的自动生成工具LEXLEX LexLex是由美国是由美国BellBell实验室实验室M.LeskM.Lesk等人用等人用C C语语言开发的一种词法分析器自动生成工具。言开发的一种词法分析器自动生成工具。它提供一种供开发者编写词法规则（正规式它提供一种供开发者编写词法规则（正规式等）的语言（等）的语言（LexLex语言）以及这种语言的翻译器语言）以及这种语言的翻译器（这种翻译器将（这种翻译器将LexLex语言编写的规则翻译成为语言编写的规则翻译成为C C语言程序）。语言程序）。一、一、LexLex的基本原理和使用

48、方法的基本原理和使用方法LexLex的基本工作原理为：由正规式生成的基本工作原理为：由正规式生成NFANFA，将，将NFANFA变换成变换成DFADFA，DFADFA经化简后，模拟生成词法分析器。经化简后，模拟生成词法分析器。其中正规式由开发者使用其中正规式由开发者使用LexLex语言编写，其余部分由语言编写，其余部分由LexLex翻翻译器完成译器完成.翻译器将翻译器将LexLex源程序翻译成一个名为源程序翻译成一个名为lex.yy.clex.yy.c的的C C语言源文语言源文件，此文件含有两部分内容：一部分是根据正规式所构造件，此文件含有两部分内容：一部分是根据正规式所构造的的DFADFA状

49、态转移表，另一部分是用来驱动该表的总控程序状态转移表，另一部分是用来驱动该表的总控程序yylexyylex()()。词法分析程序词法分析程序由正规式构造由正规式构造DFA识别单词的控制程序识别单词的控制程序yylex()当主程序需要从输入字符流中识别一个记号时，只需要调用当主程序需要从输入字符流中识别一个记号时，只需要调用一次一次yylex()就可以了。就可以了。为了使用为了使用LexLex所生成的词法分析器，我们需要将所生成的词法分析器，我们需要将lex.yy.clex.yy.c程序用程序用C C编译器进行编译，并将相关支持库函数连入目标编译器进行编译，并将相关支持库函数连入目标代码。代码。

50、LexLex的使用步骤可如下图所示：的使用步骤可如下图所示：格式格式含义含义示例示例x匹配单个字符匹配单个字符x.匹配换行符之外的任匹配换行符之外的任意字符意字符转义字符，定义同转义字符，定义同ANSIC如如n，t，r字符集合字符集合,匹配括号内匹配括号内的任意字符的任意字符abc匹配匹配a,b,和和c中的任何一中的任何一个个-指定范围指定范围a-z匹配匹配a和和z之间的任何一之间的任何一个个否定否定ab匹配除了匹配除了a和和b之外的任之外的任意字符意字符在在LEX源文件识别规则的最后源文件识别规则的最后应加一条规则：应加一条规则：.;LEX的的正规式正规式R*匹配匹配0个或多个个或多个R(R