《compiler2词法分析.ppt》由会员分享，可在线阅读，更多相关《compiler2词法分析.ppt（73页珍藏版）》请在三一办公上搜索。
1、第二章 词法分析,一、教学目的熟悉编译程序的词法分析器的结构和功能，掌握自动机与正则表达式的概念，以及它们之间的相互转换。二、教学的难点与重点1、自动机DFA，NFA概念2、正则表达式RE概念3、自动机与正则表达式之间的转换(等价性),2.1 词法分析程序概述,2.1.1 词法分析程序的功能2.1.2 词法分析程序的实现方案2.1.3 单词的种类及输出形式2.1.4 C-(Minus)Token的表示方法2.1.5 词法结构的表示及识别方法,2.1.1 词法分析程序的功能,词法分析：根据词法规则识别及组合单词，进行词法检查。对数字常数完成数字字符串到（二进制）数值的转换。删去空格字符和注解。,
2、“字符”程序,“单词”程序或“字符序列”程序,词法分析程序,2.1.2 词法分析程序的实现方案,1.词法分析单独作为一遍,2.词法分析程序作为单独的子程序,S.P.(字符串),词法分析,S.P.(符号串),语法分析,第一遍,第二遍,单词串,S.P.(字符串),词法分析程序,语法分析程序,取单词,单词,优点:结构清晰、各遍功能单一缺点：效率低,1）保留字：if、then2）标识符：3）常数：无符号数、布尔常数4）符号：+、-、*,1.单词的种类：,固定串,用户定义串,用户定义串,特殊符号,2.1.3 单词的种类及输出形式,2.词法分析程序的输出形式-单词的内部形式,几种常用的单词内部形式：1）按
3、单词种类分类2）保留字和分界符采用一符一类,单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数保留字分界符,类别编码1234567,单词值内部字符串整数值数值0 或 1内部字符串保留字或内部编码分界符或内部编码,1）按单词种类分类,2）保留字和分界符采用一符一类,单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数IFTHENELSEFOR:+*,(,类别编码123456789.20212223.,单词值内部字符串整数值数值0 或 1内部字符串-.-,2.1.4 C-(Minus)Token的表示方法,typedef enum/*reserved words*/IF,THEN
4、,ELSE,END,REPEAT,UNTIL,READ,WRITE,/*multicharacter tokens*/ID,NUM,/*special symbols*/ASSIGN,EQ,LT,PLUS,MINUS,TIMES,OVER,LPAREN,RPAREN,SEMI TokenType;,单词的类型,例：C-(Minus)Token的表示方法,typedef struct TokenType tokenval;char*stringval;int numval;TokenRecord;,单词的属性,typedef struct TokenType tokenval;union cha
5、r*stringval;int numval;attribute;TokenRecord;,例：Token的扫描,TokenType getToken(void);getToken函数在调用时从输入中返回下一个记号,例：源程序：a index=4+2 假定代码行放一输入缓冲区。getToken的调用：跳过4个空格，识别由单个字符a 组成的串“a”，并返回记号值ID作为下个记号，此时的输入缓冲区如下所示：因此，getToken随后的调用将再次从左括号字符开始识别过程。,2.1.5 词法结构的表示及识别方法,词法结构的表示方法：正则表达式词法结构的识别方法：有穷自动机,2.2 正则表达式Regul
6、ar Expression,2.2.1 正则表达式概述2.2.2 用正则表达式的运算符构造正则表达式2.2.3 程序设计语言中的正则表达式2.2.4 正则表达式与3型文法等价,2.2.1 正则表达式概述,有字母表,定义在 上的正则表达式和正则集合递归定义如下:1和都是 上的正则表达式，它们所表示的正则集合分别为：和;2任何a，a是上的正则表达式，它所表示的正则集合为：a；3假定U和V是上的正则表达式,它们所表示的正则集合分别记为L(U)和L(V)，那么U|V，UV和U*也都是 上的正则表达式，它们所表示的正则集合分别为L(U)L(V)、L(U)L(V)和L(U)*4任何上的正则表达式和正则集合
7、均由1、2和3产生。,1.正则表达式和正则集合的定义,正则表达式中的运算符：|-或-连接*-重复(闭包),两正则表达式相等 两正则表达式表示的语言相等,2.正则表达式的运算符,设e1,e2和e3均是某字母表上的正则表达式,则有:单位正则表达式:e=e=e 交换律:e1|e2=e2|e1结合律:e1|(e2|e3)=(e1|e2)|e3 e1(e2e3)=(e1e2)e3分配律:e1(e2|e3)=e1e2|e1e3(e1|e2)e3=e1e3|e2e3 此外:r*=(r|)*r*=r*(r|s)*=(r*s*)*,3.正则表达式的性质：,2.2.2 用正则表达式的运算符构造正则表达式,ba*,
8、(a|b)*(aa|bb)(a|b)*,上所有以a为首的字的集合,例：令=a,b，上的正规式和相应的正规集如下：,例 2：令=A,B,0,1，则：,例 3：令=d,.,e,+,-，则上的无符号数的正则式 表示为：,（提示：无符号数包括无符号的整数、实数、科学计数法表示的数）,上的“标识符”的全体上的“数”的全体,例 3：令=d,.,e,+,-，则上的无符号数的正则式表示为：,dd*(.dd*|)(e(+|-|)dd*|),dd*(.dd*|)(e(+|-|)dd*|),dd*,解：,dd*(.dd*|)(e(+|-|)dd*|),dd*(.dd*|)(e(+|-|)dd*|),dd*(.dd*
9、|)(e(+|-|)dd*|),dd*.dd*,dd*(.dd*|)e+dd*,dd*(.dd*|)(e(+|-|)dd*|),dd*(.dd*|)e-dd*,dd*(.dd*|)edd*,2.2.3 程序设计语言中的正则表达式,例1：数字集D=0,1,9和字母集L=A|Z|a|z,D0|1|.|9L A|B|Z|a|b|z,例2：整常数的集合IntC可表示为：,IntCDD*或IntCD|IntC D IntC IntC D|DIntCD|D IntC IntC D IntC|D,例3：实常数的集合RealC可表示为：,RealC DD*.DD*或RealCIntC.IntC,“”读作“定义
10、为”,IDEL(L|D)*(_(L|D)+)*,例5：由/开始并以Eol（行结束符）结束的注释，可用正则表达式定义为如下：,Comment/(Not(Eol)*Eol其中Not(A)表示关于给定符号表的A的余集：-A,例4：由字母、数字和下划线组成，由字母为首，以字母或数字结束，且下划线不相连的标识符之集IDE可表示为如下：,2.2.4 正则表达式与3型文法等价,例如：正则表达式：ba*a(a|b)*3型文法：Z Za|b ZZa|Zb|a,Z=bZ=Za=baZ=Za=Zaa=baaZ=Za=Zaa=Zaaa=baaa,ba*,2.3 有穷自动机 Finite Automata,2.3.1
11、状态转换图2.3.2 确定有穷自动机（DFA）2.3.3 非确定的有穷自动机(NFA)2.3.4 NFA的确定化2.3.5 DFA的化简 2.3.6 正则表达式与DFA的等价性,2.3.1 状态转换图,S,U,V,Z,1,1,1,0,0,0,例：从下图结点S出发，最终到达结点Z，请判断01101 或1001可否为路径上符号的连结？,结点代表状态，用圆圈表示。状态之间用箭弧连结，箭弧上的标记(字符)代表在射出结点(即箭弧始结点)状态下可能出现的输入字符或字符类。一张转换图只包含有限个状态(即有限个结点)，其中一个为初态，至少一个为终态(双圈表示)。,状态转换图,状态转换图是设计词法分析程序的一种
12、好途径。状态转换图，一张有限方向图，规定：,例3：识别整数的转换图（如右上图）,例2：识别标识符的转换图（如左下图）,字母,0,字母或数字,数字,0,数字,表示：在状态1下，若输入字符为x，则读进x，并转换到状态2；若输入字符为y，则读进y，并转换到状态3。,例1：,文法：1.:=字母|字母|数字 2.:=数字|数字 3.:=:|+|*|,|(|)4.:=5.:=:,读字符,查保留字表,返回S,一个确定的有穷自动机（DFA）M是一个五元式:M=(S,，,S0,Z),其中:1.S 有穷状态集（非终极符集合）2.输入字母表（终极符集合）3.映射函数(也称状态转换函数)SS(s,a)=S,S,S S
13、,a4.S0 唯一的初始状态 S0 S5.Z终止状态集 ZS,2.3.2 确定有穷自动机（DFA）状态转换图的形式化,“确定”即状态转移函数是单值函数！,例：有DFA M=(0,1,2,3,a,b,0,3)其中为:(0,a)=1(0,b)=2(1,a)=3(1,b)=2(2,a)=1(2,b)=3(3,a)=3(3,b)=3,它所对应的状态转移矩阵如图：,2.状态转移矩阵,一个DFA可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示(s,a)的值，这个矩阵称状态转移矩阵。,状态,输入字符,后继状态,状态转换图可用于识别（或接受）一定的字符串,其中为:(0,a)=1(0,b)=2
14、(1,a)=3(1,b)=2(2,a)=1(2,b)=3(3,a)=3(3,b)=3,a,a,a|b,0,1,b,b,a,b,2,例：有DFA M=(0,1,2,3,a,b,0,3),DFA也可以用状态转换图表示,相关概念,对于中的任何字,若存在一条从初态结点到某一终态结点的通路，且这条通路上的所有弧的标记符连接成的字等于，则称可被DFA M所识别（读出或接受）。,若M的初态结点同时有是终态结点，则空字可为M所识别（或接受）。,a1,a2,an,如果存在状态序列S0,S1,Sn使得S0 S1 S1 S2 Sn-1 Sn，S0为初态，Sn为任一接受态，则称字符串a1a2an被有限自动机A所接受。
15、,DFA M所接受的语言为：L(M)=|(S0,)=Sn,S0为初态，Sn为任一接受态,2.3.3 非确定的有穷自动机(NFA),“非确定”即是多值函数，且输入可允许为。,NFA的形式定义为:,一个非确定的有穷自动机NFA M是一个五元式:NFA M=(S,S0,Z)，其中 S有穷状态集 输入符号加上,即自动机的每个结点所射出的弧可以是中的一个字符或是.转换函数 S 2S(2S-S的幂集）S0初态集 Z终态集,AB,i,j,A,B,i,j,k,A|B,i,j,A*,i,j,A,B,i,j,i,j,k,A,NFA替换规则,NFA允许边出现,例：令=a,b，上所有含有两个相继的a或两个相继的b的字
16、的集合用NFA表示如下：,(a|b)*(aa|bb)(a|b)*,NFA M=(0,1,2,3,4,5,6,7,a,b,0,7)其中如上（不可省略）,初态,终态,(a|b)*(aa|bb)(a|b)*,2.3.4 NFA的确定化,非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的,NFA M,DFA M,构造成一个,使得 L(M)=L(M),（）合并符号合并,转换思想：,NFA允许边出现,（）合并：如果有S1S2,则把S2状态合并到S1状态。,NFA到DFA的区别：,例1：NFA转换成DFA(符号合并),例2：设计一个DFA，其输入字母表是0,1，它能接受以0开始，以1结尾的所有序列。,
17、解：根据题意，得出相应的正则式：0(0|1)*1 得状态转换图(NFA)如下：,NFA确定为DFA过程：DFA的初态（为NFA的初始状态经过合并后的状态的并集）例：(S,)=;DFA的其它状态（为NFA的状态经过输入符号后产生的状态，再经过合并后的状态的并集）例：求(S,0)=？(S,0)=A;(A,)=B;(B,)=C;(C,)=；DFA的终态（为所有含有NFA的终态的状态）,0,1,0,C,S,A,B,1,NFA确定化过程：(初态、其它状态、终态),0,1,0,C,S,A,B,1,得状态转换图(DFA)如下：,在DFA中，所有含有NFA的终态的状态作为DFA的终态,DFA M=(S,A,B
18、,C,0,1,S,C)其中如上（不可省略）,定义1：集合I的-闭包：,令I是一个状态集的子集，定义-closure（I）为：1）若sI，则s-closure（I）；2）若sI，则从s出发经过任意条弧能够到达的任何状态都属于-closure（I）。状态集-closure（I）称为I的-闭包,为了使得NFA确定化，我们首先给出两个定义：,例：如图所示的状态图：令I=1，求-closure（I）=？,根据定义：-closure（I）=1，3,J是从状态子集I中的每个状态出发，经过标记为a的弧而达到的状态集合.,Ia是状态子集,其元素为J中的状态，加上从J中每一个状态出发通过弧到达的状态,定义2:令I
19、是NFA M的状态集的一个子集,a 定义:Ia=-closure(J)其中J=(s,a),SI,例：令I=1，求Ia=?,Ia=-closure(J)=-closure(1，a)）=-closure(2，4）=2，4，6,例：有NFA M，求DFA M。,I=-closure(1)=1,4Ia=-closure(1,a)(4,a)=-closure(2,3）=-closure(2,3)=2,3Ib=-closure(1,b)(4,b)=-closure(）=Ic=-closure(1,c)(4,c)=I=2,3,Ia=2,Ib=4,Ic=3,4,I Ia Ib Ic,1,4 2,3,2,3 2
20、 4 3,4,2 2 4,4,3,4 3,4,初态,start,符号,状态,a,b,c,0,2,3,4,1,2,2,1,_,_,_,_,_,_,_,_,3,3,4,4,DFA M状态转换矩阵,将求得的状态转换矩阵重新编号,0,1,4,2,3,1,4,2,3,4,2,a,c,a,b,b,c,3,4,“对于任一个DFA，存在一个唯一的状态最少的等价的DFA”一个有穷自动机是化简的 它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。,2.3.5 DFA的化简(极小化),定义：,(1)有穷自动机的多余状态：从该自动
21、机的开始状态出发，任何输入串也不能到达那个状态。,例:s0为初始状态,画状态图可以看出s4,s6,s8为不可达状态应该消除,(2)等价状态 状态s和t的等价条件是:,1)一致性条件：状态s和t必须同时为可接受状态或 不接受状态.2)蔓延性条件：对于所有输入符号,状态s和t必须 转换到等价的状态里.,对于所有输入符号c，Ic(s)=Ic(t)，即状态s、t对于c具有相同的后继，则称s，t是等价的。（任何有后继的状态和任何无后继的状态一定不等价）,有穷自动机的状态s和t不等价,称这两个状态是可区别的。,“分割法”：把一个DFA(不含多余状态)的状态分割成一些不相关的子集，使得任何不同的两个子集状态
22、都是可区别的，而同一个子集中的任何状态都是等价的.,例1:最小化,状态集的划分将所有DFA的终态与其它状态划分成两个子集G1,G2;分别从两个子集G1,G2中寻找等价状态进行化简。,解:,(一)区分终态与非终态,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,a,b,区号,区号,将所有DFA的终态与其它状态划分成两个子集,区号,区号,区号,例2：设计一个DFA，其输入字母表是0,1，它能接受以0开始，以1结尾的所有序列。化简,DFA M=(S,ABC,BCZ,0,1,S,BCZ)其中如上(不可省略),例2：试求与下图所示NFA等价的化简了的DFA。,
23、化简后的DFA:,例3：试构造与正则式R=(a*|b*)b(ba)*等价的状态最少的DFA。,NFA确定为DFA:,注：状态从18标注,2.3.6 正则表达式与DFA的等价性,由于正则集合与正则表达式相对应，所以该定理表明了正则表达式与DFA的等价性,V是正则集合，R是与其相对应的正则表达式 DFA M V=L(R)L(M)=L(R)所以 正则表达式R NFA M DFA M L(R)=L(M)=L(M)证明:根据定义.,定理：在上的一个子集V(V）是正则集合，当且仅当存在一个DFA M，使得V=L(M),2.4自动机、正则文法、正则表达式的相互转化,正则文法,NFA,正则表达式,1,2,3,
24、4,5,6,DFA,最小化,（1）有穷自动机正则文法,1.对转换函数(A,t)=B，可写成一个产生式:AtB,算法:,2.对可接受状态Z,增加一个产生式:Z,3.有穷自动机的初态对应于文法的开始符号,有穷自动机的字母表为文法的终结符号集。,例:给出如图NFA等价的正则文法G,1.对转换函数(A,t)=B，可写成一个产生式:AtB,2.对可接受状态Z,增加一个产生式:Z,3.有穷自动机的初态对应于文法的开始符号,有穷自动机的字母表为文法的终结符号集。,（2）正则文法G 有穷自动机M,算法:,1.字母表与G的终结符号相同.,2.为G中的每个非终结符生成M的一个状态,G的开始符号S是开始状态S;,3
25、.增加一个新状态Z,作为NFA的终态,4.对G中的形如AtB的产生式,其中t为终结符或,A和B为非终结符,构造M的一个转换函数f(A,t)=B,5.对G中的形如At的产生式,构造M的一个转换函数f(A,t)=Z,例:求与文法GS等价的NFA GS:SaA|bB|AaB|bA BaS|bA|,求得：,1.字母表与G的终结符号相同.,2.为G中的每个非终结符生成M的一个状态,G的开始符号S是开始状态S;,3.增加一个新状态Z,作为NFA的终态,4.对G中的形如AtB的产生式,其中t为终结符或,A和B为非终结符,构造M的一个转换函数f(A,t)=B,5.对G中的形如At的产生式,构造M的一个转换函数
26、f(A,t)=Z,语法制导方法,1.(a)对于正则式,所构造NFA:,x,y,(b)对于正则式,所构造NFA:,x,y,(c)对于正则式a,a,则 NFA:,x,y,a,（3）正则式 有穷自动机,2.若s,t为上的正则式,相应的NFA分别为N(s)和N(t);,(a)对于正则式R=s|t,NFA(R),(b)对正则式R=st,NFA(R),(c)对于正则式R=s*,NFA(R),(d)对R=(s),与R=S的NFA一样.,例:为R=(a|b)*abb构造NFA,使得L(N)=L(R),分解R的方法有很多种！,R=(a|b)*abb,（4）有穷自动机 正则式,()消除M中的所有结点,利用以下转换
27、规则,直至只剩下一个开始符号定义的产生式,并且产生式的右部不含非终结符.,规则,规则1,规则2,规则3,文法产生式,正则式,AxB,By,AxA|y,Ax,Ay,A=xy,A=x*y,A=x|y,（5）正则文法 正则式,例:有文法Gs SaA|a,AaA|dA|a|d,于是:S=aA|a A=(aA|dA)|(a|d)A=(a|d)A|(a|d)由规则二:A=(a|d)*(a|d)代入:S=a(a|d)*(a|d)|a 于是:S=a(a|d)*(a|d)|),算法:1)对任何正则式r,选择一个非终结符S作为识别符号.并产生产生式 Sr2)若x,y是正则式,对形为Axy的产生式,重写为 AxB
28、By,其中B为新的非终结符,BVN 同样:对于 Ax*y AxA Ay Ax|y Ax Ay,例:将R=a(a|d)*转换成相应的正则文法,解:1)Sa(a|d)*,2)SaA A(a|d)*,SaA A(a|d)A A,SaA AaA|dA A,（6）正则式 正则文法,第二章:词法分析小结,词法分析的功能单词的种类及词法分析程序的输出形式正则文法和状态图正则表达式与有穷自动机 词法分析程序（自行编写、LEX）上机作业自行编写词法分析程序 要求：体现NFA、DFA及最小化的过程,附：部分程序伪码(1)用转换表构造DFA,State:=Initstate;/初态Read(CurrentChar)
29、;/上字符(源程序字符)While T(State,CurrentChar)error If StateFinalStates then Accept else Error,T(State,CurrentChar)：转换函数,(2)NFA到DFA的转换()合并,ss:NFA的一个状态集;Close(ss):表示()合并后的状态集;,(3)NFA到DFA的转换符号合并,PROCEDURE MakeDFA(NA:NFA_state;DA:DFA_state)BEGIN1 DA.init_state=Close(NA.initial_states);DA.states:=DA.init_state;States:=DA.init_state;2 选择一个新元素ssstates,对每个a做:ss1:=Close(MoveSet(ss,a,NA.T);令DA.T(ss,a)=ss1;/确定DFA的转换函数 若ss1DA.states则将ss1分别加入states和DA.states中 3 从States删除ss;4 若States非空,则重复24;5 DA.final_state:=ss|ssDA.state,ss的某元素NA.final_statesEND,MoveSet(ss,a,NA.T)=s2|T(s1,a)=s2,s1ss,
