编译原理第四章

1、1词法分析程序的设计原则 单词的描述技术单词的识别机制词法分析程序的自动构造原理第4章 词法分析及其自动构造2回顾回顾 什麽是词法分析程序4实现词法分析（lexical analysis）的程序 逐个读入源程序字符并按照构词规则切分成一系列单词。 是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。 词法分析是编译过程中的一个阶段，在语法分析前进行 。可以和语法分析结合在一起作为一遍。3 词法分析程序和语法分析程序的关系源程序词法分析程序语法分析程序Tokenget token.源程序词法分析程序语法分析程序4 词法分析程序的主要任务主要任务： 读源程序，产生单词符号

2、词法分析程序的其他任务其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序， 宏展开，5词法分析程序的输出 4词法分析程序所输出的单词符号常常采用以下二元式表示：4 (单词种别，单词自身的值)。 4(标识符，指向该标识符所在符号表中位置的指针)语法分析需要的信息 编译其它阶段需要的信息 6 词法分析工作从语法分析工作独立出来的原因： 简化设计 改进编译效率 增加编译系统的可移植性 7单词的描述工具-正规表达式正规表达式 回顾正规文法正规文法描述的是VT上的正规集，即是正规语言4 标识符l|l字母数字字母数字l|d|l字母数字|d字母数字无符号整数d|d无符号整数运算符+|-|*

3、|/|=|等号|等号等号=界符，|；|(|)| 8正规式 正规式也称正则表达式,是定义正规集的数学工具。 正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），我们用以描述单词符号。94设字母表为，辅助字母表=，|，*，(，) 。 和都是上的正规式，它们所表示的正规集分别为和 ； 任何a，a是上的一个正规式，它所表示的正规集为a； 假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1|e2, e1e2, e1*也都是正规式,它们所表示的正规集分别为L(e1), L(e1)L(e2), L(

4、e1)L(e2)和(L(e1)*。 仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。 10令=a，b， 上的正规式和相应的正规集的例子 a ab ab (ab)(ab) a (ab) (ab)(aabb)(ab) a a,b ab aa,ab,ba,bb ,a,aa, 任意个a的串 ,a,b,aa,ab,bb 所有由 a和b组成的串 上所有含有两个相继的a或两个相继的b组成的串11讨论例1 令=l，d，则上的正规式 r=l(l d) 定义的正规集为: l,ll,ld,ldd,其中l代表字母,d代表数字,正规式 即是 字母(字母|数字) ,它表示的

5、正规集中的每个元素的模式是“字母打头的字母数字串”, 多数程序设计语言允许的的标识符的词法规则.例2=d，e，+，-,则上的正规式 d(dd )(e(+- )dd )表示的是无符号数的集合。其中d为09的数字。 程序设计语言的单词都能用正规式程序设计语言的单词都能用正规式 来定义来定义. .12正规文法与正规式4r-G变换 对任何正规式r，选择一个非终结符S生成产生式Sr叫做正规产生式，并将S定为G的识别符号。若x和y都是正规式，对形如Axy的正规产生式，重写成：AxB，By两个正规产生式，其中B是新选择的非终结符对已形成的形如Ax*y的正规产生式，重写为：AxBAyBxBBy B为一新非终结

6、符。对形如Ax|y的正规产生式，重写为：Ax，Ay不断利用上述规则做变换，直到每个产生式都符合三型文法的要求。 134将R=a(a|d)*转换成相应的正规文法：4令S是文法的开始符号Sa(a|d)*，4 SaA A(a|d)*， 重写第二条 4SaAA(a|d)B，AB(a|d)B和B进而变换为SaABaBAaBBdBAdBBA即为所求。144文法GSSaASaAaAAdA4 AaAd4S=aA|aA=(aA|dA)|(a|d)再将A的正规式变换A=(a|d)A|(a|d)， 4 A=(a|d)*(a|d)，4 A 右端代入S的正规式：S=a(a|d)*(a|d)|a再利用正规式的代数变换可依

7、次得到S=a(a|d)*(a|d)|)S=a(a|d)*即a(a|d)*为所求。 15有穷自动机有穷自动机将讨论如下内容：确定的有穷自动机DFA不确定的有穷自动机NFANFA的确定化DFA的最小化16有穷自动机有穷自动机 有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规式所表示的集合.应用有穷自动机这个理论，为词法分析程序的自动构造寻找有效的方法和工具。 有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有 穷自动机(Nondeterministic Finite Automata) 。17确定的有穷自动机

8、DFADFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，S，Z）其中1.K是一个有穷集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；18DFA定义3.f是转换函数，是在KK上的映射，即，如 f（ki，a）=kj，（kiK， kj K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj ，我们把kj称作ki的一个后继状态；4.SK是唯一的一个初态；5.Z K是一个终态集，终态也称可接受状态或结束状态。19一个DFA 的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定义为：f（S，a）=Uf（

9、V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q20 DFA 的状态图表示4f(ki,a)=kj表示为从ki到kj的标记为a的弧线bSUVQaaaba，bb21DFA 的矩阵表示的矩阵表示abSUVUQVVUQQQQ字符字符状态状态0001224DFA的表现在转换函数f:KK是一个单值函数，也就是说，对任何状态kK，和输入符号a，f(k,a)唯一地确定了下一个状态。4从状态转换图来看，若字母表含有n个输入字符，那末任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符标记。 4对于对于*中的任何符号串中的任何符号串t，如果存

10、在一条，如果存在一条从初态结点到某一个终态结点的道路，从初态结点到某一个终态结点的道路，而且这条路上的所有弧的标记符连接成而且这条路上的所有弧的标记符连接成的符号串等于的符号串等于t，称，称t可以为可以为DFA M所接所接受。受。4若若M的初态结点同时也是终态结点，则的初态结点同时也是终态结点，则空字可被空字可被M所识别（接受）所识别（接受）23244*上的符号串上的符号串t被被M接受接受- 若t*，f(S，t)=P，其中S为 M的开始状态，PZ，Z为终态集。- 则称t为DFA M所接受（识别）4*上的符号串上的符号串t在在M上上运行运行一个输入符号串t，表示成t1t2的形式-其中t1，t2

11、*,在DFA M上运行的定义为：- f（Q， t1t2 ）=f（f（Q， t1 ）， t2 ） 其中QK - 扩充转换函数f，是K*K上的映射， 且： f（ki，）= ki25* *上的符号串上的符号串t t被被DFADFA M M接受接受例例：证明证明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, baa26DFA M所能接受的符号串的全体记为L(M).结论： 上一个符

12、号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。27DFA的行为很容易用程序来模拟.DFA M=（K，f，S，Z）的行为的模拟程序 K:=S； c:=getchar; while ceof do K:=f(K,c); c:=getchar; ; if K is in Z then return (yes) else return (no)28DFA = digit,not digit29不确定的有穷自动机NFA定义NFA M=K，f，S，Z，其中K为状态的有穷非空集， 为有穷输入字母表，f为K * 到K的子集（2 K）的一种映射，S K是初始状态集，Z K为终止状态集

13、.30例子 NFA M=（S，P，Z，0，1，f，S，P，Z）其中 f（S，0）=Pf（S，1）=S，Z f（P，1）=Zf（Z，0）=Pf（Z，1）=P31状态图表示SPZ00,111132矩阵表示矩阵表示01SPS,Z0PZ0ZPP1简化为01SPS,Z0P.Z0ZPP133具有转移的不确定的有穷自动机f为K * 到K的子集（2 K）的一种映射 123abc34有如下定理: 对任何一个具有转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA ，使得L(M)=L(N)。与上例等价的一个NFA.cb2acbb31acab35类似DFA, 对NFA M=K，f，S

14、，Z也有如下定义*上的符号串t在NFA M上运行.一个输入符号串t，（我们将它表示成Tt1的形式，其中T，t1 *）在NFA M上运行运行的定义为：f（Q， Tt1）=f（f（Q，T），t1） 其中QK.*上的符号串t被NFA M接受若t *，f(S0，t)=P，其中S0 S，P Z，则称t为NFA M所接受接受（识别识别）36 *上的符号串t被NFA M接受也可以用状态转换图来理解 对于中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，则称t可为NFA M所识别(读出或接受)。 若M的某些结既是初态结又是终态结

15、，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为，那么空字可为M所接受。37NFA M所能接受的符号串的全体记为 L(M)结论： 上一个符号串集V是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。3800011110100011100000010001100特点？特点？39(0|1)*(000|111)(0|1)*40确定有限自动机和不确定有限自动机确定有限自动机和不确定有限自动机关系关系 DFA是NFA的特例。 对每个NFA N一定存在一个DFA ，使得 L(M)=L(N)。 找一种算法，将找一种算法，将NFA转换成接受同转换成接受同样语言的样语言的DF

16、A. 子集法子集法. 与某一与某一NFA等价的等价的DFA不唯一不唯一.等等价价41先定义对状态集合I的有关运算：1. 状态集合状态集合I I的的-闭包闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S而能到达的状态的集合。 状态集合I的任何状态-closure(I)。2. 状态集合状态集合I I的的a a弧转换弧转换，表示为move(I,a) 定义为状态集合J，其中J是所有那些可从I中的某一状态而到达的状态的全体。42状态集合I的有关运算的例子I=1, -closure(I)=1,2；I=5, -closure(I)=5,6,2；move(1,2,a)=5,3,4-

17、closure(5,3,4)=2,3,4,5,6,7,8；12534687aaa43 NFA确定化算法: NFA N=(K, ,f,K0,Kt)按如下办法构造一个DFA M=(S, ,d,S0,St)，使得L(M)=L(N)：1. M的状态集S由K K的一些子集的一些子集组成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的状态。并且约定，状态S1, S2,. Sj是按某种规则排列的，即对于子集S1, S2= S2, S1,来说，S的状态就是S1 S2；442 M和N的输入字母表是相同的，即是；3 转换函数是这样定义的： d(S1 S2,. Sj,a)= R1R2. Rt 其

18、中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4 S0=-closure(K0)为M的开始状态；5 St=Si Sk. Se，其中Si Sk. SeS且Si , Sk,. SeKt45构造NFA N的状态状态K K的子集的子集的算法：假定所构造的子集族为C，即C= (T1, T2,. TI),其中T1, T2,. TI为状态K的子集。1 开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。462 while （C中存在尚未被标记的子集T）do 标记T； for 每个输入字母a do U:= -closure(move(T,a)； i

19、f U不在C中 then 将U作为未标记的子集加在C中 47 NFA的确定化 例子4f35621iaaaabbbbIaIbi,1,21,2,31,2,41,2,31,2,3,5,6,f1,2,41,2,41,2,31,2,4,5,6,f1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,6,f1,2,3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,f4f35621iaaaabbbb49 等价的DFAaCDBAEFSbaaaaabbbbbabF50确定有穷自动机的化简 一个

20、有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。 一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。 多余状态，是指：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。 51 DFA的最小化就是寻求最小状态DFA最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t等价等价：满足兼容性同是终态或同是非终态传播性从s出发读入所有aa和从 t出发读入所有a到达的状态等价。分析52最小状态DFA对于一个DFA M =（K,f, k0,kt)，存在一个最小状

21、态DFA M =（K,f, k0,kt)，,使L(M)=L(M). 结论 接受L的最小状态有穷自动机不计同构是唯一的。53“分割法”DFA的最小化算法的核心 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集不同的两子集的状态都是可区别的，而同一子集同一子集中的任何两个状态都是等价的. 算法假定每个状态射出的弧都是完全的,否则,引入一个新状态,叫死状态,该状态是非终态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己.54 DFA的最小化算法 DFA M =（K,f, k0, kt),最小状态DFA M 1.构造状态的一初始划分： 终态kt 和非终态K- kt两组(

22、group) 2.对施用过程过程PPPP 构造新划分new 3. 如new =,则令 final= 并继续步骤4，否则:=new重复2 . 4.为final中的每一组选一代表，这些代表构成M的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M中有一转换f(k,a)=r55 M 的开始状态是含有S0的那组的代表 M 的终态是含有F的那组的代表 5.去掉M中的死状态.56过程过程PPPP : Construction of new 对对每一个状态组每一个状态组G进行下述工作：进行下述工作：将将G划分为子组。划分为子组。G的两个状态的两个状态s和和t分分在同一子组的充要条件是：对所有的在同

23、一子组的充要条件是：对所有的输入符号输入符号a，状态，状态s和和t的的a转换都是转换都是的的同一组中的状态。同一组中的状态。形成的所有子组成为形成的所有子组成为new的状态组。的状态组。 57 DFA的最小化例子0:S,A,B C,D,E,F1:S,A,B C,D,E,F 2: CDBAEFSbaaaaaabbbbbba S,BA bB SDBASaaabbbbaa58词法分析程序的自动构造 词法分析程序的自动构造方法,这个方法基于有穷自动机和正规表达式的等价性有穷自动机和正规表达式的等价性,即即： 1.对于上的一个NFA M，可以构造一个上的正规式R,使得L(R)=L(M)。2.对于上的一个

24、正规式R，可以构造一个上的NFA M，使的L(M)=L(R)。59RNFA从上的一个正规式R构造上的一个NFA M，使得L(M)=L(R)的方法。“语法制导”的方法，即按正规式的语法结构指引构造过程，构造规则具体描述如下： 60对于正规式 ,构造的NFA 61对于正规式 ,构造的NFA 62对于正规式a ,构造的NFA 63对于正规式r, r= s|t构造的NFA s和t相应的NFA分别为N(s)和N(t), 64对于正规式r, r=st 构造的NFA65对于正规式r, r = s*构造的NFA对于正规式r, r = （s）构造的NFA4同S的NFA一样6667正规表达式正规表达式 1*0(0+1)*举例举例:从从正规表达式正规表达式构造等价的构造等价的 - NFA100+1 11* 68从从正规表