编译原理及实践-第2章词法分析.ppt

《编译原理及实践-第2章词法分析.ppt》由会员分享，可在线阅读，更多相关《编译原理及实践-第2章词法分析.ppt（149页珍藏版）》请在三一办公上搜索。

1、1,第2章 词法分析,2.1 词法分析器的作用2.2 正则表达式 2.3 有穷自动机2.4 从正则表达式到DFA 2.5 用代码实现有穷自动机2.6 利用lex自动生成词法分析程序,单词的描述工具,单词的识别系统,设计和实现词法分析程序,2,2.1 词法分析器的作用,词法分析器(词法分析程序)的任务：从源代码中读取输入字符，产生单词序列(生成独立的有意义的逻辑单元称作单词(token)，提交给语法分析使用。,3,任务：逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。识别出源程序中的单词；删除无用的空白字符及注释

2、（空格、回车 等），这些信息仅增加了源程序的可读性，便于程序员阅读和维护程序，而对于语法分析是完全无用的。进行词法检查，能够检测出输入中不能形成源语言任何单词的错误字符串。,4,The big elephant ate the peanut.,词法分析的结果：,5,token表示的字符串（串值或词义）：if,y,3,then,x,=,0,token的类型（词法）：关键字（if,else,for,int,return）操作符（+,-,）数字（3,45,）标识符（x,y,name）补充：typedef enum 类似宏 IF,THEN,PLUS,MINUS,NUM,ID TokenType;,词法

3、分析器的输出:token序列,6,if y3 then x=0,词法分析器,例如：C源代码:if y3 then x=0,词法分析器的输出是？,类型 串值例 ID 表示 标识符 类型 x 表示 具体的标识符串,7,定义逻辑项token的数据类型：typedef struct,union char*stringval;int numval;attribute;,TokenRecord;,TokenType tokenval;,Token类型,Token词义,补充：union数据类型,8,词法分析程序的函数接口：TokenRecord getToken(void);,Token,getToken(

4、),源程序,词法分析程序,语法分析程序,符号表,9,第2章 词法分析,2.1 词法分析器的作用2.2 正则表达式 2.3 有穷自动机2.4 从正则表达式到DFA 2.5 用代码实现有穷自动机2.6 利用lex自动生成词法分析程序,记号的描述工具,记号的识别系统,设计和实现词法分析程序,10,正则表达式：,对自动生成词法分析程序而言，正则表达 式也是非常有用的工具。,所谓正则表达式就是用特定的运算符及运算对象按某种规则构造的表达式。例如：a*匹配 空串,a,aa,aaa,其表示的是一个集合，记为L(a*)。,正则表达式用来描述单词结构(定义单词)。,11,2.2.1 基本概念和术语2.2.2 正

5、则表达式的定义2.2.3 正则表达式基本等价关系2.2.4 正则表达式的扩展2.2.5 单词的正则表达式举例,2.2正则表达式 单词的描述工具,12,2.2.1 基本概念和术语,字母表（符号表、符号集）由若干元素（符号、字母）组成的有限非空集合。不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。,13,符号串 由字母表中的符号组成的任何有穷序列称为符号串:例如00，11，10 是字母表=0，1上的符号串。字母表A=a，b，c上的符号串有：a，b，c，ab，aaca等。在符号串中，符号的顺序是很重要的，符号串ab就不同于ba，abca和aabc也不同。,14,符号串的长

6、度 如果某符号串x中有m个符号，则称其长度为m，表示为x=m，如001110的长度是6。空符号串，即不包含任何符号的符号串，用表示，其长度为0，即=0。,15,符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如 x=ST，y=abu，则它们的连接 xy=STabu，x=2，y=3，xy=5由于的含义，显然有x=x=x。符号串的方幂：符号串自身连接n次得到的符号串xn 定义为 xxx；n个x x1=x,x2=xx且x0=,16,例；若x=ab 则:x0=x1=ab x2=abab x3=ababab xn=xxn-1=xn-1x(n0),17,符号串集合

7、：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串集合的和与积设A，B为两个符号串集合，定义和 A+B(或AB)=w|wA，或wB积 AB=xy|xA,yB,18,若用表示空集，则有：A+=+A=A A=A=A=A=A 例：若集合A=ab,cde，集合B=0,1，则AB=ab1,ab0,cde0,cde1；,19,的闭包：用*表示上的一切符号串（包括）组成的集合，*称为的闭包。例如：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,的正闭包：上除外的所有符号串组成的集合记为+，+称为的正闭包。例如：=a,b+=a,b,aa,ab,ba,bb,aaa,a

8、ab,20,2.2.1 基本概念和术语2.2.2 正则表达式的定义2.2.3 正则表达式基本等价关系2.2.4 正则表达式的扩展2.2.5 单词的正则表达式举例,2.2正则表达式,21,正则表达式就是用特定的运算符及运算对象按某种规则构造的表达式。每个正则表达式代表一个字符串的集合，我们把其称为正则集。语言(Language)是字符串组成的集合，我们也可以把正则表达式表示的正则集称为该正则表达式表示的语言。,2.2.2正则表达式的定义,22,正则表达式和它所表示的正则集(字符串的集合)的递归定义如下：设有字母表为，辅助字母表=,|,.,*,(,),23,(1)和是上的正则式，它们所表示的正则集

9、分别为和;(2)若a，则a是上的正则式，它所表示的正则集为a;,若r和s都是上的正则式，且它们所表示的正则集分别为L(r)和L(s)，那么：,24,r|s 是正则式，表示的正则集为 L(r|s)=L(r)L(s)；rs 是正则式，表示的正则集为 L(rs)=L(r)L(s)；r*是正则式，表示的正则集为(L(r)*。(r)是正则式，表示的正则集为L(r)；,“.”运算符常省略,25,(4)仅由有限次使用上述三步骤而定义的表达式才是上的正则式，仅由这些正则式所表示的符号串集合才是上的正则集。注：算符的优先级为先“*”，再“.”最后“|”,都是左结合的，它们满足结合律。,26,例1，令=a，b，上

10、的正则式和相应的正则集的例子：,正则式 正则集,a,a,ab,ab,(ab)(ab),a,a,b,ab,aa,ab,ba,bb,a,aa,任意个a的串,(ab),a,b*,即,a,b,aa,ab,ba,bb,27,例2，正则式(a)|(b)*(c)它所表示的正则集为：,根据运算符的优先级，上述正则式可以表示成 a|b*ca|b*c所表示的正则集为：字符串a以及由零个或多个b后跟一个c 形成的字符串的集合或写成L(a|b*c)=a bnc|其中n是大于或等于0的整数,28,给定一个正则式,它唯一确定一个正则集；反之不成立。即一个正则集可由多个不同的正则式表示。,aa,a,aa,aaa,任意个a的

11、串,a|aa,a,aa,aaa,任意个a的串,例如：,29,若二个正则式描述同一正则集，则称二式等价(相等)。判断下列正则表达式e1和e2是否等价？e1=(ab)，e2=bae1=b(ab),e2=(ba)be1=(ab),e2=(ab),30,正则表达式是表示模式的一种重要方法，每个模式匹配一个字符串集合(即正则集)。正则集是正则表达式所定义的语言。正则表达式可以作为字符串集合(即正则集)的名字。,31,2.2.1 基本概念和术语2.2.2 正则表达式的定义2.2.3 正则表达式基本等价关系2.2.4 正则表达式的扩展2.2.5 单词的正则表达式举例,2.2正则表达式,32,A1.r|s=s

12、|r A2.r|r=rA3.r|=rA4.(r|s)|t=r|(s|t)A5.(rs)t=r(st)A6.r(s|t)=rs|rtA7.(s|t)r=sr|trA8.r=r=A9.r=r=rA10.r*=(|r)*=|rr*从集合论的角度去理解！,2.2.3 正则式基本等价关系,33,2.2.1 基本概念和术语2.2.2 正则表达式的定义2.2.3 正则表达式基本等价关系2.2.4 正则表达式的扩展2.2.5 单词的正则表达式举例,2.2正则表达式,34,2.2.4 正则表达式的扩展,1.一个或多个重复（+，*）：假设r是正则表达式，r的重复是通过使用标准的闭包运算来描述，写作r*。它允许r被

13、重复0次或更多次。用r+表示r 被重复1次或更多次。因此有：(0|1)+=(0|1)(0|1)*,35,2.任意字符（.）:句点“.”表示可以匹配除换行符之外的任意单个符。利用这个字符就可为所有包含至少一个b 的串写出一个正则表达式，如下所示：.*b.*引号“”，引号中的字符串表示文本字符串本身。例如：“.”表示要匹配.字符本身。,36,字符范围：表示法a|b|z 表示所有小写字母；0|1|9表示0到9间的所有数字；常见的表示法是利用方括号和一个连字符，如a-z是指所有小写字母，0-9则指数字。第二种表示法还可用作表示单个的解，a|b|c可写成abc，它还可用于多个范围，如 a-z A-Z 代

14、表所有的大小写字母。,37,正则表达式的名字,为较长的正则表达式提供一个简化的名字很有用处，这样就不用每次使用正则表达式书写较长的表达式本身了；如要写一个正则表达式:a-z A-Z(a-z A-Z 0-9),它定义的正则集为：以字母打头后跟若干字母或数字组成的符号串的集合。,38,上述正则式定义的是程序设计语言标识符的词法规则，通过为正则表达式提供一个简化的名字，上述正则表达式可写作：letter=a-z A-Z digit=0-9 identify=letter(letterdigit),39,例：写出正则表达式signedNatnat=0-9+signedNat=nat|+nat|-nat

15、对应的正则集？,40,可选的子表达式（？）：如果在特定的串中包括既可能出现又可能不出现的可选部分。例如，nat=0-9+signedNat=nat|+nat|-nat我们可以引入问号?来表示r 匹配的串是可选的；上面的例子可写成：nat=0-9+signedNat=(+|-)？nat,41,2.2.1 基本概念和术语2.2.2 正则表达式的定义2.2.3 正则表达式基本等价关系2.2.4 正则表达式的扩展2.2.5 单词的正则表达式举例,2.2正则表达式,42,2.2.5 单词的正则表达式举例,每一种程序设计语言都有自己的字符集(字母表)。语言中的各个单词或是上的单个字符(如运算符、分隔符等)

16、，或是上的字符串(如常数、表示符和关键字等)。程序设计语言的单词都能用正则式来定义.由正则式描述的单词类也称为正则集。,43,1.数：nat=0-9+signedNat=(+|-)?natnumber=signedNat(“.”nat)?(“E”signedNat)?例如：3,3.5,2.71E-22.保留字：reserved=else|if|int|return|void|while,44,3.标识符：letter=a-zA-Zdigit=0-9identifier=letter(letter|digit)*,45,包含单词词法描述的语言手册是编译器的程序员最常见的。在下面的示例中，被匹配的

17、串是汉语描述，其任务是将描述翻译为正则表达式。,46,在字母表=a,b,c中，考虑在这个字母表上的仅包括一个b 的所有串的集合，这个集合所对应的正则表达式为：,串b、abc、abaca、baaaac、ccbaca和ccccccb等都是满要求的符号串。,(a|c)*b(a|c)*,47,在字母表=a,b,c中，如果字符串集合是包括最多一个b 的所有串，则这个集合的正则表达式为：,仅包括一个b 的串的集合对应的正则表达式(a|c)*b(a|c)*不包括b 的串的集合对应的正则表达式(a|c)*故所求表达式为：(a|c)*|(a|c)*b(a|c)*或者为:(a|c)*(b|)(a|c)*,48,在

18、字母表=a,b上串S的集合是由一个b及在其前后有相同数目的a 组成：S=b,aba,aabaa,aaabaaa,.=anban|n0,正则表达式并不能描述这个集合，其原因在于重复运算只有闭包运算*一种，它允许有任意次的重复。因此如要写出表达式a*ba*，就不能保证在b 前后的a 的数量是否相等了。,49,并非用简单术语描述的所有串都可由 正则表达式产生，因此为了与其他集合相区分，作为正则表达式描述的串集合称作正则集(regular set)。非正则集偶尔也作为串出现在需要由扫描程序识别的程序设计语言中。,50,第2章 词法分析,2.1 词法分析器的作用2.2 正则表达式 2.3 有穷自动机2.

19、4 从正则表达式到DFA 2.5 用代码实现有穷自动机2.6 利用lex自动生成词法分析程序,记号的描述工具,记号的识别系统,设计和实现词法分析程序,51,2.3.1有穷自动机2.3.2确定性有穷自动机(DFA)的定义2.3.3非确定性有穷自动机(NFA),2.3有穷自动机,52,2.3.1 有穷自动机,有穷自动机(也称有限自动机)作为一种数学模型，它能准确地识别正则集，即识别正则式所表示的集合。有穷自动机是设计和实现词法分析器的有效工具，其直观图是一种状态转换图。引入有穷自动机理论，也是为词法分析程序的自动构造寻找方法和工具。,53,有穷自动机(Finite Automata,or fini

20、te-state machines)有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata，DFA)。不确定的有穷自动机(Nondeterministic Finite Automata，NFA)。,54,在程序设计语言中，用正则式定义的标识符如下：letter=a-zA-Zdigit=0-9identifier=letter(letter|digit)*该正则式匹配的标识符是以一个字母开头且其后为任意字母、数字序列形成的字符串。,55,变量xtemp 识别为标识符的过程可表示为：,1,x,2,t,2,e,2,m,2,p,2,标识符模式的识别过程：,5

21、6,2.3.1有穷自动机的引入2.3.2确定性有穷自动机(DFA)的定义2.3.3非确定性有穷自动机(NFA),2.3有穷自动机,57,2.3.2确定性有穷自动机（DFA）的定义,DFA(确定性有穷自动机)有五个部分组成：(1)有限个输入符号组成的字母表,记作;(2)有限个状态的集合,记作S;(3)转换函数T T:SS 即：T(s,c)=s 其中sS，sS，c上述转换函数表示：若当前状态为s,且当前识别的输入符号为c,识别c后进入的下一个状态为s。,58,(4)初始状态s0S;指示识别符号串的开始状态;(5)若干个识别符号串的接受状态(或称为终止状 态)的集合 A S;(由上述五个要素组成的五

22、元式M=(S;T;s0;A)称为一个确定的有限自动机(DFA:Deterministic Finite Automata)。,59,DFA M=（s1,s2,s3,s4,a,b,T,s1,s4）其中转换函数T定义为：T(s1,a)=s2 T(s3,a)=s2 T(s1,b)=s3 T(s3,b)=s4T(s2,a)=s4 T(s4,a)=s4T(s2,b)=s3 T(s4,b)=s4,一个DFA 的例子：,有限个状态的集合s,字母表,初始状态,接受状态的集合A,60,状态转换图一个DFA可以表示成一个状态图(或称状态转换图)。状态转换图是由一组矢线连结的有限个结点所组成的有向图。例如：,61,

23、假定DFA M含有m个状态，那么这个状态图就含有m个结点；结点用小圆圈表示，圆圈中标入状态的名字或编号。为了醒目起见，用箭头指示初始状态，用双圆圈表示终止转态。,s0,初始状态,接受状态,62,若 T(s,a)=s，则从状态结点s到状态结点s画标记为a的矢线。表示当词法分析器处于该矢线的结点所指示的状态s时，可能要识别的输入字符为a，而矢线进入的结点s则指示识别相应的输入字符a后进入的下一个状态。,63,例：M=(s0,s1,s2,0,1,T,s0,s2)其中,T的定义如下：T(s0,0)=s1 T(s1,0)=s1 T(s1,1)=s2,s0,0,s1,1,0,状态转换图举例,上述DFA对应

24、的状态转换图：,64,在状态转换图中，从一个结点可以同时引出若干条矢线到有向图中的其余结点(也可从一结点引矢线到其自身)；每一矢线上均标记一个字符或字符类记号，表示当词法分析器处于该矢线的结点所指示的状态时，可能要识别的输入字符，而矢线进入的结点则指示识别相应的输入字符后进入的下一个状态。,65,DFA的接受集(即识别的字符串集合),DFA识别的字符串c1 c2 cn的集合满足如下条件：每个ci，且存在状态 s1=T(s0，c1),s2=T(s1，c2),sn=T(sn-1，cn),其中s0 是初态，sn 是终态。,66,s0,c1,s1,c2,s2,sn-1,cn,sn,c3,cn-1,字符

25、串c1 c2 cn若被DFA识别，则在状态转换图中存在一条从初态到终态的有向路经，该路径上所有矢线上方的字符连接在一起即是字符串c1 c2 cnDFA M识别的字符串的集合 记作L(M)L(M)也称为由正则表达式M生成的语言。,67,b,s1,s2,s3,a,b,b,a,|,b,a,a,例：证明字符串序列baab被下图的DFA所接受。,任意列出它接受的另外两个输入串？任意列出它拒绝接受的两个输入串？,68,证明：由于存在,T(s1,b）=s3,T(s3,a）=s2,T(s2,a）=s4,T(s4,b）=s4,s4属于终态，得证。,69,(1).状态转换图中的状态可以使用任何标识系统来标识(2)

26、.状态转换图中的转换可以使用字符集合的名字标出,关于DFA的状态转换图的2点说明,70,例1：自然数的集合被下图所示的DFA接受。,注：digit=0-9,DFA的示例,71,例2：字母表=a,b,c上有且仅有一个b构成的字符串集合被下图所示的DFA接受。,72,例3：字母表=a,b,c上包含最多一个b构成的字符串的集合被下图所示的DFA接受。,73,例4：有C风格注释的DFA,注：other1表示除*之外的所有字符的集合的名字；other2表示除*,/之外的所有字符的集合的名字。,74,2.3.1有穷自动机的引入2.3.2确定性有穷自动机(DFA)的定义2.3.3非确定性有穷自动机(NFA)

27、,2.3有穷自动机,75,2.3.3非确定性有穷自动机（NFA）,下图是识别,字符串的一个有穷自动机，对于输入符号,在状态0上存在不止一种转换。,=,76,有穷自动机对于某个输入符号，如果在同一个状态上存在不止一种转换，我们称该有穷自动机为不确定的有穷自动机。在给出非确定性有穷自动机的定义之前先引入-转换的概念。,77,-转换是无需考虑输入串就有可能发生的转换。它可看作是一个空串的“匹配”，-转换的图形表示为：,-转换的引入,-转换可以清晰地描述出空串的匹配：,0,1,78,-转换可以通过添加一个新的初始状态来链接各个自动机，从而将它们合并为一个自动机。将识别数字和字符的两个DFA和并为一个非

28、确定的有穷自动机：,letter,letter,START2,START1,digit,digit,79,通过-转换将识别:=、=、=的DFA合并为：,80,NFA(非确定性有穷自动机)有五个部分组成：(1)有限个输入符号组成的字母表,记作;(2)有限个状态的集合,记作S;(3)转换函数T;T:S()(S),T(s,c)=sk1,skm 表示若当前状态为sS,且要识别的输入符号为c,识别c后进入的状态是S的一个状态子集sk1,skm;,2.3.2非确定性有穷自动机（NFA）的定义,81,(4)初始状态s0S;(5)若干个接受状态的集合:A S 由上述五个要素组成的五元式 M=(S；T；s0；A

29、)称为一个非确定的有限自动机(NFA:Nondeterministic Finite Automata),由上述定义可以看出，DFA是NFA的一个特例。,82,一个NFA 的例子：NFA M=（S，P，Z，0，1，T，S，Z）其中 T（S，0）=P;T（Z，0）=P;T（P，1）=Z;T（Z，1）=P;T（S，1）=S，Z;,83,NFA的状态转换图例：M=(,=,0，1，2，3，4，5,T,0,2，4，5)其中T的定义如下：T(0,)=4,=,84,NFA M 的接受集记作L(M)L(M)定义为字符串c1c2 cn的集合，其中每个ci，且存在：s1T(s0,c1),s2T(s1,c2),sn

30、T(sn-1,cn),其中s0是初态，sn是终态集中的一个元素。,NFA的接受集,85,例：考虑下面的NFA图。,这个NFA接受集与正则表达式ab+|ab*|b*对应的正则集相同。,列举两个转换序列都可接受串abb？,86,第2章 词法分析,2.1 词法分析器的作用2.2 正则表达式 2.3 有穷自动机2.4 从正则表达式到DFA 2.5 用代码实现有穷自动机2.6 利用lex自动生成词法分析程序,记号的描述工具,记号的识别系统,设计和实现词法分析程序,87,2.4从正则表达式到DFA,正则式是单词的一种描述工具。由于正则式的简洁性，趋向于先用正则式来描述单词，然后构造等价的有限自动机。,有限

31、自动机可以描述输入串被识别的过程，我们可以根据有限自动机构造我们的词法分析程序。,88,正则式和有限自动机之间可以相互转换，也就是说它们之间存在着等价性，即：,对于上的NFA M，可以构造一个上的正则式R，使得：L(R)=L(M)对于上的每个正则式R，可以构造一个上的NFA M，使得：L(M)=L(R),89,2.4.1 从正则表达式到NFA2.4.2 从NFA 到DFA2.4.3 将DFA中的状态数最小化,2.4从正则表达式到DFA,90,2.4.1 从正则表达式到NFA,从正则表达式到NFA的转化方法按正则式的运算指引构造过程，将正则式分解为一系列子表达式，然后将子表达式对应的NFA依次连

32、接而成，正则式R转化为NFA M 的基本步骤：,91,1.基本正则式转换为NFA M的方法：,92,2.复合正则式R转换为NFA M的方法：首先将复合正则表达式表示成如下拓广的状态转换图，然后按照正则式的运算(以下(a),(b),(c),(d)四种情况)递归生成NFA M,93,94,(d)正则式R=（r）的NFA同正则式 R=r的NFA相同,95,例1,设有正则表达式R=ab|a,试构造NFA M，使L(R)=L(M)。,96,例2，设有正则表达式letter(letter|digit)*,试构造与之等价的NFA。,97,98,2.4.1 从正则表达式到NFA2.4.2 从NFA 到DFA2

33、.4.3 将DFA中的状态数最小化,2.4从正则表达式到DFA,99,2.4.2 从NFA 到DFA,对任一NFA M，总可构造一个DFA M，使 L(M)=L(M)成立。这就是NFA与DFA的等价性。定理 对于字母表上的任一NFA M，必存在与M等价的DFA M(即有 L(M)=L(M)成立)。在给出具体的构造算法之前先引入状态s和状态集合S的-闭包的概念：,100,（1）状态s的-闭包：定义为从s出发可由一系列的零个或多个-转换能达到的状态的集合，并将这个集合记为（2）状态集合S的-闭包:定义为S中各个状态的-闭包的并集,101,=1,2,4,=2,=3,2,4,=4,例：求下列状态机中状

34、态1、2、3、4的-闭包：,102,从给定的NFA M构造DFA 的原理是一次尝试所有的可能路径，避免NFA的回溯()。,已知 NFA M=(S；T；s0；A)设构造的与之等价的,DFA,记作：,103,计算M初始状态s0的-闭包，令其作为,的初始状态：,=;,T,-,=,由NFA构造DFA的子集构造算法步骤如下：,104,对 中尚未标记的状态=si1,si2,sim:,开始由标记的状态求新状态,105,106,例1，考虑下图中的NFA,试构造与之等价的DFA。,1,2,a,3,状态,终结符,a,1,2,4,3,2,4,3,2,4,3,2,4,a,0,1,107,例2，考虑下图中的NFA,试构

35、造与之等价的DFA。,a,b,状态,终结符,a,b,0,1,2,1,2,1,1,3,4,5,108,例3，考虑下图中的NFA,试构造与之等价的DFA。,状态,终结符,letter,digit,0,2,3,1,2,3,1,3,1,3,1,3,1,3,1,3,1,109,letter,letter|digit,letter|digit,构造的与上述等价的DFA如下图所示：,110,2.4.1 从正则表达式到NFA2.4.2 从NFA 到DFA2.4.3 将DFA中的状态数最小化,2.4从正则表达式到DFA,111,2.4.3 将DFA中的状态数最小化,结论：对于任何给定的DFA，都有一个含有最少状

36、态等价的DFA，而且这个最小状态的DFA在同构意义下是唯一的。状态集合的等价类：若两个状态s1,s2在DFA中完成相同的识别功能，则可将s1,s2置于同一个等价类中。,112,对于任意给定的输入串w，若DFA分别从状态s1,s2出发，能够得到是否接受w的相同的结论，则称状态s1,s2位于同一个等价类，即若从s1出发DFA能接受w,则从s2出发DFA也能接受w，反之，若从s1出发DFA拒绝w,则从s2出发DFA亦拒绝w。否则称状态s1,s2是可区分的。,113,DFA最小化算法：,首先将状态集合S分为两个等价类：A及S-A；()等价类细分：对于当前已经划分的任意等价类K,如果a)或b)条件满足，

37、就将当前划分的等价类K细分为两个更小的等价类K1,K2,并使s1,s2分别落入细分后的不同等价类中；,114,如果存在输入符号a()，K中的两个状态s1,s2可由a转换到当前已经划分的不同的等价类中；如果存在输入符号a()，K中的两个状态s1,s2，当切仅当存在一个状态（s1或s2）对于a 的转换没有意义即T(si,a)=；,115,对于步骤2细分之后的所有等价类，递归上述步骤2中细分等价类的工作，直到对于同一等价类中的所有状态及任何输入符号a()，我们都不能将其细分到不同的等价类为止。,116,对于处于同一等价类中的状态，我们可以选用其中任一状态作为代表即可，等价类中的其他状态皆可省略，同时

38、，把所有引向省略状态的弧引向代表状态。这就是实现DFA最小化的基本原理。,117,(1)首先划分为两个等价类：2，3，1,例1：将下图所示的DFA M最小化,(2)对于输入符号letter:T(2,letter)=3,T(3,letter)=3;对于输入符号digit:T(2,digit)=3,T(3,digit)=3;,118,同一等价类2，3中的状态2，3不能被任何输入符号所区分。故状态集合最终划分为两个等价类：2，3，1。,最小化后的DFA M如下图所示。,119,例2：将下图所示的DFA M最小化,a,0,1,3,2,a,a,a,a,b,b,b,b,首先将状态集划分为两个等价类：4，0

39、,1,2,3,120,对于输入符号a,T(0,a)=1,T(1,a)=1,T(2,a)=1,T(3,a)=1 对于输入符号b,T(0,b)=2,T(1,b)=3,T(2,b)=2,T(3,b)=4所以0,1,2,3被b区分为两个等价类：0，1，2，3 此时状态集划分为三个等价类4，0，1，2，3,121,有2.中的列举的转换知：0，1，2被b进一步区分为两个等价类 0，2，1此时状态集划分为四个等价类：4，0，2，1，3所求最小化后的DFA M如下图所示。,122,第2章 词法分析,2.1 词法分析器的作用2.2 正则表达式 2.3 有穷自动机2.4 从正则表达式到DFA 2.5 用代码实现有

40、穷自动机2.6 利用lex自动生成词法分析程序,记号的描述工具,记号的识别系统,设计和实现词法分析程序,123,正则式是单词的一种描述工具。由于正则式的简洁性，趋向于先用正则式来描述单词，然后构造等价的有限自动机。,有限自动机可以描述输入串被识别的过程，我们可以根据有限自动机构造我们的词法分析程序。,2.5 用代码实现有穷自动机（书节）,124,确定的有穷自动机导出的识别单词的程序比不确定的有穷自动机导出的识别程序快的多，但确定的有穷自动机可能比与之等价的不确定的有穷自动机大得多。用代码实现有穷自动机遇到的问题：,125,错误问题：,遇到出错状态的典型动作是在输入中备份或生成错误记号。,126

41、,最长匹配原则：,当字符串可以是单个单词也可以是若干个单词的序列时，则通常解释为单个单词。即最长匹配原则。当字符串既可以是标识符也可以是关键字时，则认为它是关键字。,127,分割符问题：xtemp=ytemp,优先考虑分割符，应将其返回到输入串并且不能丢掉，并将刚识别的单词返回。,128,3,other,return ID,other,return ERROR or other,将上述自动机的状态重新标示：,129,模拟上述DFA最早且最简单的方法是：,starting in state 1if the next character is a letter then advance the i

42、nput;now in state 2 while the next character is a letter or a digit do advance the input;stay in state 2 end while;go to state 3 without advancing the input accept;else error or other casesend if;,130,上述代码使用代码的位置来隐含当前状态机所处的状态，如果没有太多的状态且DFA中的循环较小，用这种方法实现扫描器是合适的。类似这样的代码已被用来编写小型扫描程序。但这个方法有两个缺点：首先它必须用略微

43、不同的方法处理各个DFA，规定一个用这种办法将每个DFA翻译为代码的算法较难。其次：当状态增多时，且当不同的状态与任意路径增多时，代码会变得非常复杂。,131,一个较好的实现方法是：利用一个状态变量保持当前的状态，并将转换写成一个双层嵌套的case语句。其中第1个case语句测试当前的状态，嵌套的第2层测试输入字符并且保存当前状态遇到该输入字符转换之后的状态。,132,利用状态变量和嵌套的case测试模拟DFA:,state:=1;while(state！=3)do case state of 1:case input character of letter:advance the input

44、;state:=2;default:state:=error or other end case;,133,2:case input character of letter,digit:advance the input;state:=2;default:state:=3;end case;end case;end while;if state=3 then accept(while循环推出，state=3!)else error;,134,标识符的DFA可以用如下的二维转换表格表示,在这个表格中，空表项表示到错误状态的转换。,error(state),135,基于上述的转换表，我们可以用数据

45、结构来表示DFA，并写出实现数据结构的行为的代码。state：保存当前的状态；ch：存储当前扫描的下一个字符；Tstate,ch：存储state遇到ch转换后的状态；Acceptstate：表示state是否为接受状态；Advancestate,ch：表示state遇到ch是否消耗输入字符ch，如果Advancestate,ch为真，接着读取源程序中下一个字符并存入ch；,136,状态矩阵法：state:=1;ch:=next input character;while not Accept state and not error(state)donewstate:=Tstate,ch;if

46、Advancestate,ch then ch:=next input character;state:=newstate;end while;if Accept state then accept;,137,上述算法被称作表驱动(table driven)算法，这是因为它们利用二维表格来引导算法的过程。表驱动方法有若干优点：代码的长度缩短了，相同的代码可以解决许多不同的问题，代码也较易改变(维护)了。表驱动方法也有一些缺点：表格会变得非常大，使得程序要求使用的空间也变得非常大。实际上，我们刚描述过的数组中的许多空间都浪费了。因此，尽管表压缩经常会多耗费时间，但表驱动方法经常仍要依赖于诸如稀疏

47、数组表示法的压缩方法，来提高扫描程序的效率。,138,2.5节 TINY 词法分析程序的实现,4.注释：注释应放在花括号中，且不可嵌套,YINY词法如下：,1.关键字：if then else end repeat until read write,5.专用符号：+，-，*，/，=，(，)，:=,2.标识符和数字：ID=letter letter*,3.空白格(whitespace):空格(char c=),换行符（n）,制表符（t）,NUM=digit digit*,letter=a-z A-Z,digit=0-9,139,140,TINY词法分析程序的DFA,2.5 TINY 词法分析程序

48、的实现,TINY词法分析程序的实现 SCAN.C,141,第2章 词法分析,2.1 词法分析器的作用2.2 正则表达式 2.3 有穷自动机2.4 从正则表达式到DFA 2.5 用代码实现有穷自动机2.6 利用Lex自动生成词法分析程序,记号的描述工具,记号的识别系统,设计和实现词法分析程序,142,2.6 利用Lex自动生成扫描程序,词法分析程序一般来说比较简单，很容易手工编程实现。另一种方法就是利用Lex等自动生成工具来生成词法分析程序。,143,它接受以正则表达式为输入形式的对程序设计语言所使用的单词符号的描述；构造一个能够识别这个正则表达式所描述的正则集的确定性有穷自动机，在这个构造过程

49、中一般要借助于非确定性有穷自动机；最后生成的词法分析程序就是这个确定性有穷自动机的实现。,词法分析程序的自动生成器一般采用如下的工作原理：,144,Lex是一个扫描程序生成器。Lex工具的输入:包含了正则表达式的文本文件，另外还包括每一个表达式被匹配时所采取的动作。Lex工具的输出:一个名为的c语言程序文件。(词法分析程序),145,Lex输入文件的格式如下所示：definitions%rules%auxililary routinesParser-Generator(YACC and Lex for Windows),146,一般来说，开发一种新语言时，由于它的单词符号在不停地修改，采用Le

50、x等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。自动生成的词法分析器常常受到速度太慢的批评。Gray1988指出，直接将DFA转换为可执行代码(将状态作为case语句来实现)，其速度可以和手工编写的词法分析器一样快。例如，Flex(fast lexical analyzer generator)Paxson 1995的速度就比Lex要快许多。,147,课程实验,要求参见：编译原理-词法分析实验-冯博琴.doc,148,作业：,是单词的描述工具，用来定义描述单词结构（定义单词）。是单词的识别系统，作为一种识别装置，它能准确地识别正则集，即识别