编译原理chpt3词法分析及其自动构造.

词法分析程序（扫描器）的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。描述程序设计语言的词法的机制是3型文法和正则表达式，识别机制是有穷状态自动机。第三章词法分析及其自动构造•单词的描述工具-正规表达式•单词的识别系统-有穷自动机•设计词法分析程序,实现词法分析程序的自动构造回顾什麽是词法分析程序实现词法分析（lexicalanalysis）的程序–按照构词规则将源程序切分成一系列单词，其输出为二元组：(单词种类，单词自身值)–单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。–可以是独立的一遍，更一般作为语法分析的一个子程序。源程序词法分析程序语法分析程序Tokengettoken….源程序词法分析程序语法分析程序3.1正规式与正规集正规式（regularexpression）,是定义正规集的数学工具。它是描述单词的模式(pattern)的一种重要的表示法。令={a，b}，上的正规式和相应的正规集的例子abab(ab)(ab)a(ab)(ab)(aabb)(ab){a,b}{ab}{aa,ab,ba,bb}{,a,……任意个a的串}{,a,b,aa……所有由a和b组成的串}{上所有含有两个相继的a或两个相继的b组成的串}正规表达式与正规集（正规语言）–设字母表为，辅助字母表`={，，，，，，}。–1.和都是上的正规式，对应的正规集分别为{}和{}–2.任何a，a是上的正规式，它对应的正规集为{a}；–3.假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正规式,它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1))。–4.仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集例3.1令={l，d}，则上的正规式r=l(ld)定义的正规集为:{l,ll,ld,ldd,……},其中l代表字母,d代表数字,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,是多数程序设计语言的标识符的词法规则.例3.2={d，，e，+，-},则上的正规式d(dd)(e(+-)dd)表示的是无符号数的集合。其中d为0~9的数字。程序设计语言的单词都能用正规式来定义若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。–例如：e1=(ab)与e2=bae1=b(ab)与e2=(ba)be1=(ab)与e2=(ab)正规式的描述能力有限，它不能用于描述嵌套的结构正规表达式与正规集的代数规律设r,s,t为正规式，正规式服从的代数规律有：–1.rs=sr“或”服从交换律–2.r(st)=(rs)t“或”的可结合律–3.(rs)t=r(st)“连接”的可结合律–4.r(st)=rsrt、(st)r=srtr分配律–5.r=r、r=r零一律–6.rr=rr=rrr…“或”的抽取律3.2有穷自动机有穷自动机作为一种识别装置，它能准确地识别正规集，即识别正规式所表示的集合。有穷自动机分为两类：确定的有穷自动机(DeterministicFiniteAutomata)和不确定的有穷自动机(NondeterministicFiniteAutomata)。3.2.1确定的有穷自动机DFA一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中1.K是一个有穷集，它的每个元素称为一个状态；2.Σ是一个有穷字母表，它的每个元素称为一个输入符号；3.f是转换函数，是在K×Σ→K上的映射，就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.S∈K是唯一的一个初态；5.ZK是一个终态集，终态也称可接受状态。一个DFA的例子：DFAM=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QDFA的状态图和矩阵表示bSUVQaaaba，bbabSUVUQVVUQQQQ字符状态0001∑*上的符号串t被DFAM接受例：证明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,baa结论：上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。CAaabDFAM所能接受的符号串的全体记为L(M).CabL={a打头的a、b符号串}L={长度为任意的a、b符号串}3.2.2不确定的有穷自动机NFA定义NFAM=K，，f，S，Z，其中K为状态的有穷非空集，为有穷输入字母表，f为K*到K的子集（2K）的一种映射，SK是初始状态集，ZK为终止状态集.例NFAM=（{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}SPZ00,1111状态图和矩阵表示01S{P}{S,Z}0P{}{Z}0Z{P}{P}1具有转移的不确定的有穷自动机f为K*到K的子集（2K）的一种映射123abc对任何一个具有转移的不确定的有穷自动机NFAN，一定存在一个不具有转移的不确定的有穷自动机NFAＭ，使得L(M)=L(N)2acbb31acacbb∑*上的串t在NFAM=K，，f，S，Z上运行一个输入符号串t（=Tt1，T∈∑，t1∈∑*）在NFAM上运行的定义为：f（Q，Tt1）=f（f（Q，T），t1）其中Q∈K.若t∑*，f(S0，t)=P，其中S0∈S，PZ，则称t为NFAM所接受（识别）这意味着，对于Σ*中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串等于t，则t为NFAM所识别(或接受)000101000111000000101100NFAM所能接受的符号串的全体记为：L(M)结论：上一个符号串集V是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。(0|1)*(000|111)(0|1)*NFAM→正规式R1.添加结点x、y，其中x与所有的初始结点ε弧连接，y与所有终态结点ε弧连接。2.反复使用以下规则，逐渐消去结点，直到只剩下x、y：1R1R2R1R22313121212313R1R2R1|R2R1R2R1R2*R3R3最后，x和y结点间弧上的标记则为所求的正规式R。例1R=(a|b)*(aa|bb)(a|b)*a,b42ababa,ba,bεyεεε0a,b(aa|bb)(a|b)*y3x01x例201aa,bbab,baab,baaa,bby0aa,bbxε(ab|ba)(aa|bb)*(ab|ba)ε((aa|bb)|(ab|ba)(aa|bb)*(ab|ba))*即识别所有那些含有偶数个a和偶数个b的字。IaIb{i,1,2}{1,2,3}{1,2,4}{1,2,3}{1,2,3,5,6,f}{1,2,4}{1,2,4}{1,2,3}{1,2,4,5,6,f}{1,2,3,5,6,f}{1,2,3,5,6,f}{1,2,4,6,f}{1,2,4,5,6,f}{1,2,3,6,f}{1,2,4,5,6,f}{1,2,4,6,f}{1,2,3,6,f}{1,2,4,5,6,f}{1,2,3,6,f}{1,2,3,5,6,f}{1,2,4,6,f}SABACBBADCCEDFDEFDFCE4f35621iaaaabbbb3.2.3NFA的确定化知道起点，知道下一步，也知道有限步，就可以构造整个工作过程！对每个NFAN一定存在一个DFAＭ，使得L(M)=L(N)与某一NFA等价的DFA不唯一.状态集合I的几个相关有关运算：1.状态集合I的ε-闭包ε-closure(I)是I中的任何状态S经任意条ε弧而能到达的状态的集合。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}；12534687aaaNFA确定化算法（子集法）假设NFAN=(K,,f,K0,Kt)，现构造一个等价的DFAM=(S，，d，S0，St)：1.M的状态集S由K的一些子集组成。用[S1S2...Sj]表示S的元素，其中S1,S2,,...Sj是K的状态；2.M和N的输入字母表相同，即是；3.转换函数的：d([S1S2,...Sj],a)=[R1R2...Rt]，其中{R1,R2,...,Rt}=-closure(move({S1,S2,,...Sj},a))4.S0=-closure(K0)为M的开始状态；5.St={[SiSk...Se]，其中[SiSk...Se]S且{Si,Sk,,...Se}Kt}IaIb{i,1,2}{1,2,3}{1,2,4}{1,2,3}{1,2,3,5,6,f}{1,2,4}{1,2,4}{1,2,3}{1,2,4,5,6,f}{1,2,3,5,6,f}{1,2,3,5,6,f}{1,2,4,6,f}{1,2,4,5,6,f}{1,2,3,6,f}{1,2,4,5,6,f}{1,2,4,6,f}{1,2,3,6,f}{1,2,4,5,6,f}{1,2,3,6,f}{1,2,3,5,6,f}{1,2,4,6,f}SABACBBADCCEDFDEFDFCE4f35621iaaaabbbbNFA的确定化等价的DFAaCDBAEFSbaaaaabbbbbabF3.2.4DFA的最小化最小状态DFA的含义:没有多余状态(死状态)没有两个状态是互相等价（不可区别）设s是自动机A的一个状态，从s出发能导出的所有符号串记为L(s).若有L(s)=L(t)，则称s和t是等价状态。（从s出发和从t出发效果完全相同—能处理完全相同的串）不等价就是可区分的。BAESabbbSAEbab最小状态DFA对于一个DFAM=（K,∑,f,k0,,kt)，存在一个最小状态DFAM’=（K’,∑,f’,k0’,,kt’)，,使L(M’)=L(M).结论：接受L的最小状态有穷自动机不计同构是唯一的。显然，终态与非终态是可区分的（为什么？）若s和t是等价状态，则它们在同一输入下的后继状态s’和t’等价；反之，对s和t，若存在某一个输入下的后继状态s’和t’不等价，则s和t肯定也不会等价。“分割法”DFA的最小化算法的核心把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。算法假定每个状态射出的弧都是完全的,否则,引入一个新状态,叫死状态,该状态是非终态，将不完全的输入弧都射向该状态，对所有输入，该状态射出的弧还回到自己。DFA的最小化算法DFAM=（K,∑,f,k0,,kt),最小状态DFAM’1.构造状态的一初始划分：终态kt和非终态K-k2.对∏施用过程PP构造新划分∏new3.如∏new=∏,则令∏final=∏并继续步骤4，否则∏:=∏new重复2.4.为∏final中的每一组选一代表，这些代表构成M’的状态。若k是一代表且f(k,a)=t,令r