词法分析程序的设计原则-单词的描述技术-识别机制及词法

词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。,第三章 词法分析及其自动构造,单词的描述工具 单词的识别系统 设计词法分析程序,实现词法分析程序的自动构造,回顾 什麽是词法分析程序,实现词法分析（lexical analysis）的程序 逐个读入源程序字符并按照构词规则切分成一系列单词。 单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。 词法分析是编译过程中的一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。,词法分析程序和语法分析程序的关系,源程序,词法分析程序,语法分析程序,Token,get token,.,源程序,词法分析程序,语法分析程序,源程序,词法分析程序,语法分析程序,源程序,词法分析程序的主要任务： 读源程序，产生单词符号 词法分析程序的其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序， 宏展开，,词法分析工作从语法分析工作独立出来的原因： 简化设计 改进编译效率 增加编译系统的可移植性,单词的描述工具-正规表达式 单词的识别系统-有穷自动机 设计词法分析程序,实现词法分析程序的自动构造,令=a，b， 上的正规式和相应的正规集的例子,a ab ab (ab)(ab) a (ab) (ab)(aabb)(ab),正规式,正规式也称正则表达式,是定义正规集的数学工具。正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），我们用以描述单词符号。,令=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组成的串,讨论两个例子 例3.1 令=l，d，则上的正规式 r=l(l d) 定义的正规集为: l,ll,ld,ldd,其中l代表字母,d代表数字,正规式 即是 字母(字母|数字) ,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,就是Pascal和 多数程序设计语言允许的的标识符的词法规则. 例3.2 =d，e，+，-, 则上的正规式 d(dd )(e(+- )dd )表示的是无符号数的集合。其中d为09的数字。 程序设计语言的单词都能用正规式 来定义.,有穷自动机 有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规式所表示的集合.应用有穷自动机这个理论，为词法分析程序的自动构造寻找有效的方法和工具。 有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有 穷自动机(Nondeterministic Finite Automata) 。,关于有穷自动机我们将讨论如下题目,确定的有穷自动机DFA 不确定的有穷自动机NFA NFA的确定化 DFA的最小化,确定的有穷自动机DFA,DFA定义： 一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，S，Z）其中 1.K是一个有穷集，它的每个元素称为一个状态； 2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；,DFA定义,3.f是转换函数，是在K×K上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态； 4.SK是唯一的一个初态； 5.Z K是一个终态集，终态也称可接受状态或结束状态。,一个DFA 的例子：,DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定义为： f（S，a）=U f（V，a）=U f（S，b）=V f（V，b）=Q f（U，a）=Q f（Q，a）=Q f（U，b）=V f（Q，b）=Q,DFA 的状态图表示,b,DFA 的矩阵表示,0 0 0 1,*上的符号串t被DFA 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）=Q Q属于终态。 得证。,b,a,b,a,a,DFA M所能接受的符号串的全体记为L(M). 结论： 上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得 V=L(M)。,DFA的行为很容易用程序来模拟. 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),DFA å = digit,not digit,不确定的有穷自动机NFA,定义 NFA M=K，f，S，Z，其中K为状态的有穷非空集， 为有穷输入字母表，f为K * 到K的子集（2 K）的一种映射，SK是初始状态集，Z K为终止状态集.,例子 NFA M=（S，P，Z，0，1，f，S，P，Z） 其中 f（S，0）=P f（S，1）=S，Z f（P，1）=Z f（Z，0）=P f（Z，1）=P,状态图表示,矩阵表示,矩阵表示,具有转移的不确定的有穷自动机,f为K * 到K的子集（2 K）的一种映射,1,2,a,b,c,有如下定理:,对任何一个具有转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA ，使得L(M)=L(N)。 与上例等价的一个NFA.,2,a,c,b,b,a,c,a,c,b,b,类似DFA, 对NFA M=K，f，S，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所接受（识别）,*上的符号串t被NFA M接受也可以这样理解,对于中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为的弧)等于t，则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为，那么空字可为M所接受。,000 111 1010001 110000001 00 01100,NFA M所能接受的符号串的全体记为 L(M) 结论： 上一个符号串集V是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。,(0|1)*(000|111)(0|1)*,确定有限自动机和不确定有限自动机,DFA是NFA的特例.对每个NFA N一定存在一个DFA ，使得 L(M)=L(N)。对每个NFA N存在着与之等价的DFA M。 有一种算法，将NFA转换成接受同样语言的DFA.这种算法称为子集法. 与某一NFA等价的DFA不唯一.,NFA确定化算法:,假设NFA N=(K, ,f,K0,Kt)按如下办法构造一个DFA M=(S, ,d,S0,St)，使得L(M)=L(N)： 1. M的状态集S由K的一些子集组成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的状态。并且约定，状态S1, S2,. Sj是按某种规则排列的，即对于子集S1, S2= S2, S1,来说，S的状态就是S1 S2；,2 M和N的输入字母表是相同的，即是； 3 转换函数是这样定义的： d(S1 S2,. Sj,a)= R1R2. Rt 其中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4 S0=-closure(K0)为M的开始状态； 5 St=Si Sk. Se，其中Si Sk. SeS且Si , Sk,. SeKt,定义对状态集合I的几个有关运算：,1. 状态集合I的-闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。 状态集合I的任何状态S都属于-closure(I)。 2. 状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。,状态集合I的有关运算的例子,I=1, -closure(I)=1,2； I=5, -closure(I)=5,6,2； move(1,2,a)=5,3,4 -closure(5,3,4)=2,3,4,5,6,7,8；,构造NFA N的状态K的子集的算法： 假定所构造的子集族为C，即C= (T1, T2,. TI),其中T1, T2,. TI为状态K的子集。 1 开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。,2 while （C中存在尚未被标记的子集T）do 标记T； for 每个输入字母a do U:= -closure(move(T,a)； if U不在C中 then 将U作为未标记的子集加在C中 ,NFA的确定化,例子,等价的DFA,a,a,b,确定有穷自动机的化简,说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。 所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。,DFA的最小化就是寻求最小状态DFA,最小状态DFA的含义: 没有多余状态(死状态) 没有两个状态是互相等价（不可区别） 两个状态s和t可区别：不满足 兼容性同是终态或同是非终态 传播性从s出发读入某个aa和从 t出发读入某个a到达的状态等价。,C和D同是终态,读入a到达C和F, C和F同是终态, C和F读入a都到达C,读入b都到达E. C和D等价,a,a,b,最小状态DFA,对于一个DFA M =（K,f, k0,kt)，存在一个最小状态DFA M =（K,f, k0,kt)，,使L(M)=L(M). 结论 接受L的最小状态有穷自动机不计同构是唯一的。,“分割法”,DFA的最小化算法的核心 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的. 算法假定每个状态射出的弧都是完全的,否则,引入一个新状态,叫死状态,该状态是非终