第四章词法分析.ppt

1、第4章,词法分析,本章目的,本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 描述程序设计语言的词法的机制是3型文法和正则表达式，识别机制是有穷状态自动机。,4.1 词法分析程序的设计,词法分析(lexical analysis) 逐个读入源程序字符并按照构词规则切分成一系列单词。 单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。 词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍。,4.1.1 词法分析程序与 语法分析程序的接口方式,主要任务：读源程序，产生单词符号 其他任务： 滤掉空

2、格，跳过注释、换行符 追踪换行标志，复制出错源程序， 宏展开，,帮助理解术语,常常遇到的术语 Token 单词,词标，符号 lexeme词素，词位 pattern模式，式样 In general，there is a set of strings in the input for which the same token is produced as output.,帮助理解术语,This set of strings is described by a rule called a pattern associated with the token. The pattern is said t

3、o match each string in the set. A lexeme is a sequence of characters in the source program that is matched by the pattern for a token. e.g. Const pi=3.14159；中的pi是token “identifier”的lexeme，其pattern为letter followed by letters and/or digit.,4.1.2 词法分析程序的输出,单词符号一般可分为下列五种： 基本字(关键字) begin end if while var

4、 标识符常量名、变量名、过程名 常数(量)数值常量、字符串、逻辑值 运算符+、-、*、/、= 界符 ，；( ),词法分析程序的输出,输出表示采用单词的二元式形式： (单词种别，单词自身的值) 语句：Const i=25,yes=1 (Id,指向i的符号表的入口指针) (Id,指向yes的符号表的入口指针),词法分析程序的输出,单词的种别用整数编码表示： 编码 单词 1 标识符 2 常数 3 保留字 4 运算符 5 界符,词法分析程序的输出,程序段：if i=5 then x:=y; if (3, if) i (1,指向i的符号表入口) = (4,= ) 5 (2,5) then (3, the

5、n) x (1,指向x的符号表入口) := (4, := ) y (1,指向y的符号表入口) ; (5,; ),4.1.3 将词法分析工作分离的考虑,词法分析工作独立的原因： 1. 简化设计 2. 改进编译效率 3. 增加编译系统的可移植性,4.2 单词的描述工具,单词基本语法符号 描述工具程序设计语言的单词的语法都能用正规文法或3型文法来描述。 词法分析技术基于描述工具建立的,4.2.1 正规文法,3型文法 G=(VN,VT,P,S) P中的每一条规则都有：AaB或Aa 其中A，B VN a VT 正规文法描述的是VT 上的正规集,正规文法的例单词的描述,ll ldld dd +-* /=

6、= ， ；( ),正规文法的例单词的描述,例4.1 无符号数的单词描述 d .e d .e d e d,正规文法的例单词的描述,ds d d 其中s表示 + 或 - 号 用实数 25.55e+5 和 2.1 进行分析,4.2.2 正规式,正规式也称正则表达式，正规表达式 正规表达式(regular expression)是说明单词的pattern(词法)的一种重要的表示法(记号)，是定义正规集的数学工具。,正规式的定义,正规式和它所表示的正规集的递归定义： 设字母表为 辅助字母表=，*，(，)。 其中的“”读为“或”，亦可用“+” “ ”读为“连接”； “*”读为“闭包”，即任意有限次自重复连

7、接。,正规式的定义,1. 和都是上的正规式，它们所表示的正规集分别为 和； 2. 任何 a ，a是上的一个正规式，它所表示的正规集为a；,正规式的定义,3、假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1) e1 e2 e1e2 e1* 也都是正规式它们所表示的正规集分别为： L(e1) L(e1)L(e2) L(e1)L(e2) (L(e1)* 4、仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。,正规式与正规集,在不致混淆时，括号可省略。 规定算符的优先顺序为“(”、“)”、“*”、“ ”、“” 。

8、连接符“ ”一般可省略不写。 “*”、“ ”和“” 都是左结合的。,review,Regular expressions on the alphabet are defined by the following recursive rules: 1) Every symbol of is a regular expression 2) and is a regular expression 3) if r1 and r2 are regular expressions, so are (r1 ) r1 r2 r1 | r2 r1 *,review,4) Nothing else is a re

9、gular expression. = 0,1,2,3,4,5,6,7,8,9 (1|2|3|4|5|6|7|8|9|0) * is a regular expression (1|2|3|4|.8|9|0) (1|2|3.|8|9|0) * is a regular expression (1|2|3.|8|9|0)+,正规式与正规集的例,例4.2 令=a，b，上的正规式和相应的正规集的例子有： 正规式 正规集 a a ab a,b ab ab (ab)(ab) aa,ab,ba,bb,正规式与正规集的例,正规式 正规集 a* ,a,a, 任意个a的串 (ab)* ,a,b,aa,ab 所有

10、由a 和b组成的串 (ab)*(aabb)(ab)* *上所有含有两个相继的a 或两个相继的b组成的串,正规式与正规集的例,例 4.3 =d，.，e，+，-， 则上的正规式： d*(.dd* )(e(+- )dd* ) 表示的是无符号数的集合。 其中d为09的数字，“.”为小数点。 上的正规式： e2=dd* 定义的正规集：无符号整数 可以简单的导出具体的数，例如：,正规式与正规集的例,例： =l，d 则上的正规式：r=l(l d)* 定义的正规集： l,ll,ld,ldd, 例： =字母，数字 =l，d 则上的正规式：e1=字母(字母数字)* e1=l(l d)* 定义的正规集：所有标识符的

11、集合,正规式的等价,若两个正规式e1和e2所表示的正规集相同，则说e1和e2等价，写作e1=e2 例如：e1= ab 等价于 e2 = ba 又如：e1= b(ab)* 等价于 e2 =(ba)*b e1= (ab)* 等价于 e2 =(a*b*)*,正规式服从的代数规律,设r,s,t为正规式，有： 1. rs=sr “或”服从交换律 2. r(st)=(rs)t “或”的可结合律 3. (rs)t=r(st) “连接”的可结合律 4. r(st)=rsrt (st)r=srtr 分配律 5. r=r r=r 是“连接”的恒等元素零一律 6. rr=r r*=rrr “或”的抽取律,4.2.3

12、 正规文法到正规式,一个正规语言可以由正规文法定义，也可以由正规式定义。 对任意一个文法，存在一个定义同一个语言的正规式。反之亦然。 两者之间的转换结构的等价性。即： 对于上的一个正规式r ，存在一个文法G=(VN,VT,P,S) 且语言 L(G)=L(r) 反之亦然。,正规式到正规文法,1. 将上的一个正规式转换成文法： G=VN,VT,P,S 所谓转换就是确定： 非终结符的非空有穷集VN 终结符的非空有穷集VT 产生式的非空有穷集P 开始符号S,正规式到正规文法,令VT = 确定产生式和VN的元素 对任何的正规式r，S VN ，生成正规产生式：Sr，同时确定VN和P。 将S定为G的识别符号

13、。 不断应用上述规则做变换，直到每个产生式右端最多只含一个终结符为止。,正规式到正规文法,若x和y都是正规式，对形如 Axy的正规产生式，重写为： AxB By 并且新非终结符BVN 对形如 Ax*y的正规产生式，可重写为： AxB Ay BxB By BVN 形如Ax y的产生式，可重写为： Ax Ay,正规式到正规文法,例4.4 将 R=a(ad)* 转换成 G1=(S,A,B,a,d,S,P 其中 P：S aA B (ad)B A (ad)B A B 令S为文法的开始符号， VT=a,d VN=S,A,B,正规式到正规文法,R=a(ad)* Sa(ad)* SaA A(ad)*,SaA

14、AaB AdB A BaB BdB B,SaA A(ad)B A B(ad)B B,正规文法到正规式,2. 将正规文法转换成正规式 转换结果为形如：开始符S终结符 的形式 转换规则：,正规文法到正规式,例4.5文法Gs： SaA Sa AaA AdA Aa Ad, S=aAa A=(aAdA)(ad) A=(ad)A(ad) A=(ad)*(ad),应用规则 转换,S=a(ad)*(ad)a =a(ad)*(ad) =a(ad)*) =a(ad)*,正规式r,应用代数 规律,4.3 有穷自动机,有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规

15、式所表示的集合， 有穷自动机分为两类： 确定的有穷自动机DFA (Deterministic Finite Automata) 不确定的有穷自动机NFA (Nondeterministic Finite Automata),4.3.1 确定的有穷自动机(DFA),DFA定义： 一个确定的有穷自动机(DFA)M是一个五元组：M=(K，f，S，Z) 其中： 1. K是一个有穷集，它的每个元素称为一个状态； 2. 是一个有穷字母表，它的每个元素称为一个输入符号，也称为输入符号字母表；,DFA定义,3. f是转换函数，是在KK上的映射，即，如 f(ki，a)=kj，(kiK，kjK) 就意味着，当前状

16、态为ki，输入符为a时，将转换为下一个状态kj，把kj称作ki的一个后继状态； 4. SK是唯一的一个初态； 5. Z K是一个终态集，终态也称可接受状态或结束状态。,DFA 例,例4.6 DFA M=(S,U,V,Q，a,b，f，S，Q) 其中f定义为： f(S，a)=Uf(V，a)=U f(S，b)=Vf(V，b)=Q f(U，a)=Qf(Q，a)=Q f(U，b)=Vf(Q，b)=Q,DFA 的状态(转换)图表示,假定DFA M含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出。 整个图有唯一的初态结点和若干个终态结点。 若 f(ki，a)=kj 表示从状态

17、结点ki到kj有标记为a的弧。,DFA 的状态(转换)图表示,前例的状态图,DFA 的矩阵表示,前例的矩阵：行表示状态，列表示输入字符，矩阵元素表示对应行、列的状态。,DFA的接受,若 t *，f(S，t)=P 其中S为 M的开始状态，P Z，Z为终态集。 则称 t为DFA M所接受(识别)。 扩充转换函数f： 设QK，函数f(Q，)= Q，即如果输入串为空串，则仍停留在原来的状态上。,一个输入符号串t，将它表示成t1tx的形式，其中t1，tx* 符号串t在DFA M上运行的定义为： f(Q， t1tx)=f(f(Q，t1)，tx) 其中QK,DFA M 上的运行,DFA 例,例：证明 t=b

18、aab 被例4.6的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)=Q Q属于终态。 得证。,DFA的结论,DFA M所能接受的符号串的全体记为L(M) 结论： 上一个符号串集V*是正规的，当且仅当存在一个上的确定有穷自动机M，使得 V=L(M)。,DFA的确定性,DFA的确定性表现在转换函数f：KK是一个单值函数 对任何状态 kK，输入符号 a，f(k,a)唯一地确定下一个状态,DFA模拟程序,DFA M=（K，f，S，Z）的行为的模拟程序 K:=S; c:=getchar;

19、 while ceof do K:=f(K,c); c:=getchar; ; if K is in Z then return (yes) else return (no),review,DFA M=（K，f，S，Z） 1) A finite set of states, one of which is designated the initial state or start state, and some of which are designated as final states. 2) An alphabet of possible input symbols. 3) A fini

20、te set of transitions that specifies for each state and for each symbol of the input alphabet, which state to go to next.,DFA,DFA = digit,not digit,4.3.2 不确定的有穷自动机(NFA),NFA定义：M=K，f，S，Z 其中：K为状态的有穷非空集 为有穷输入字母表 f为K * 到K的子集的映象 S K是初始状态集 Z K为终止状态集,NFA的例和状态图表示,NFA M=(S,P,Z,0,1, f,S,P,Z) 其中 f(S，0)=P f(S，1)

21、=S，Z f(P，1)=Z f(Z，0)=P f(Z，1)=P,矩阵表示NFA,矩阵表示,被NFA M接受,*上的符号串t被NFA M接受： 若存在从初态到终态结点的弧的标记串t，则 t*，f(S0，t)=P， 其中S0 S，P Z，忽略标记为的弧， 则称t为NFA M所接受(识别),在NFA上运行,类似DFA, 对NFA M=K，f，S，Z也有如下定义： *上的符号串t在NFA M上运行： 一个输入符号串t，将它表示成t1 tx的形式，其中t1，tx* 在NFA M上运行的定义为： f(Q,t1tx)=f(f(Q,t1),tx) 其中QK,NFA与DFA,DFA是NFA的特例。对每个NFA

22、M一定存在一个DFA M，使得 L(M)=L(M)。则称：M与M是等价的。 对每个NFA M都存在着与之等价的DFA M。与某一NFA等价的DFA不唯一,4.3.3 NFADFA的转换,定理：设L为一个由NFA接受的集合，则存在一个接受L的DFA NFA的确定化NFADFA的转换 转换算法子集法： DFA的每一个状态对应NFA的一组状态 在NFA读入一个输入符号串后，T是标记某个符号的路径可以到达的一个子集，DFA的状态表示NFA状态的T。,NFA的确定化,定义对状态集合I的几个有关运算： 1. 状态集合I的-闭包，表示为： -closure(I) 定义为一状态集，是状态集I中的任何状态S，经

23、任意条弧而能到达的状态的集合。 状态集合I的任何状态S都属于-closure(I)。,NFA的确定化,2. 状态集合I的a弧转换，表示为： move(I,a) 定义为状态集合J，其中J是所有那些可从I的某一状态，经过一条a弧而到达的状态的全体。 定义 Ia = -closure(J),NFA的确定化的例,I=0, -closure(I)=0,1,2,4,7； move(0,1,2,4,7,a)=3,8 -closure(3,8)=1,2,3,4,6,7,8,NFA的确定化的例,I=1, -closure(I)=1,2； I=5, -closure(I)=5,6,2； move(1,2,a)=5

24、,3,4 -closure(5,3,4)=2,3,4,5,6,7,8；,NFA的确定化,假设NFA N=(K, , f, K0, Kt)，若I是K的一个子集，设 I=(S1,S2,S3,SJ)，a是中的一个元素，则： move(I,a)=f(S1,a) f(S2,a) f(S3,a) 按如下办法构造一个 DFA M=(S, ,d,S0,St)， 使得L(M)=L(N),NFA的确定化,1. M的状态集S由K的一些子集组成。 用S1 S2. Sj表示S的元素， 其中S1, S2,. Sj是K的状态。 并且约定，状态S1, S2,. Sj是按某种规则排列的，即对于子集S1, S2= S2, S1,

25、来说，S的状态就是S1 S2；,NFA的确定化,2. M和N的输入字母表是相同的，即是； 3. 转换函数是这样定义的： d(S1 S2,. Sj,a)= R1R2. Rt 其中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a),NFA的确定化,4. S0=-closure(K0)为M的开始状态； 5. St=Si Sk. Se 其中 Si Sk. SeS 且 Si , Sk,. SeKt,NFA的确定化,构造NFA N的状态K的子集的算法： 假定所构造的子集族为C，即C= (T1, T2,. TI),其中T1, T2,. Ti为状态K的子集。 1. 开始，

26、令-closure(K0)为C中唯一成员，并且它是未被标记的。,NFA的确定化,2. While (C中存在尚未被标记的子集T) do 标记T； for 每个输入字母a do U:= -closure(move(T,a)； if U不在C中 then 将U作为未标记的子集加在C中 ,4.3.4 确定有穷自动机的化简,最小状态DFA 没有多余状态(死状态) 没有两个状态是互相等价(不可区别) 两个状态s和t可区别：不满足 兼容性同是终态或同是非终态 传播性从s出发读入某个a (a) 和从t出发读入某个a到达的状态等价。,确定有穷自动机的化简,说一个有穷自动机是化简了的，即是说，它没有多余状态并且

27、它的状态中没有两个是互相等价的。 一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。 所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。,DFA的最小化,对于一个DFA M =（K,f, k0,kt)，存在一个最小状态DFA M =(K,f, k0,kt)，使L(M)=L(M) 算法的核心：把M的状态集K分成不相交的子集。 结论：接受L的最小状态有穷自动机不计同构是唯一的。,DFA的最小化,DFA M =（K,f, k0, kt),最小状态DFA M 1. 构造状态的一初始划分

28、：终态kt 和非终态K- kt两组 2. 对施用过程PP 构造新划分new 3. 如new =,则令 final= 并继续步骤 4. 否则:=new重复2,DFA的最小化,4. 为final中的每一组选一代表，这些代表构成M的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M中有一转换f(k,a)=r M 的开始状态是含有S0的那组的代表 M 的终态是含有F的那组的代表 5.去掉M中的死状态.,0:S,A,B C,D,E,F 1:S,A,B C,D,E,F 2:,a,a,DFA的最小化的例,4.4 正规式和有穷自动机的等价性,有穷自动机和正规表达式的等价性： 1.对于上的一个NFA

29、M，可以构造一个上的正规式R,使得L(R)=L(M)。 2.对于上的一个正规式R，可以构造一个上的NFA M，似的L(M)=L(R)。 “语法制导”的方法：按上的一个正规式R的语法结构指引构造过程，构造上的一个NFA M，使得L(M)=L(R)的方法。,“语法制导”构造规则,构造规则具体描述如下： (1) R=, 任一具有空终态集的NFA M (2) R= ，NFA M=(k0, ,f,k0.k0): f（k0,a)对于 所有a都没定义。 (3) R=a,NFA M=(k0,k1,f,k0.k1): f(k0,a) = k1,“语法制导”构造规则,(4) R =R1 | R2, 分别将步骤(1)、(2)、(3)应用到R1,R2 产生：M1= (K1,f1,k1,F1), M2=(K2,f2,k2,F2) 其中K1,K2不相交. NFA M= (K1K2k,f,k,F) k是新增加的状态符号，,“语法制导”构造规则,f包含f1和f2,且f(k,a