天津大学编译原理讲义-Part3词法分析2

Part3词法分析授课：胡静内容提要词法分析器的作用词法分析程序的设计与实现——状态图词法分析程序的自动生成——有穷自动机正则表达式与有限自动机问题的提出如果只向前看一个字符，不能够确定我们将要读入的是哪种类型的token如果token的开头是“i”，那么它一定是标识符么？如果token的开头是“2”，那么它一定是一个整型的常数么？如果我们通过上面的类似“插入”式的方法来写识别token的程序，这样的程序不容易写正确，而且也不容易维护因此需要一个更加有原理性的方法：词法分析器的生成器，可以自动产生有效的词法分析器。（例如lex，flex，Jlex）一般说来，没有限制的向前看是必要的一些问题如何明确的描述tokens2.e020.e-012.0000“”“x”“\\”“\”\’”如何将文本分割成tokensif(x==0)a=x1;if(x==0)a=x1;如何描述tokens我们可以使用正则表达式来描述程序设计语言中的tokens。正则表达式的定义如下：正则集合（语言）正则表达式的例子令={a，b}，正则表达式正则集合集a{a}ab{a,b}ab{ab}(ab)(ab){aa,ab,ba,bb}a{,a,a,……任意个a的串}(ab){,a,b,aa,ab……所有由a和b组成的串}(ab)(aabb)(ab){上所有含有两个相继的a或两个相继的b组成的串}正则表达式的例子={a，b}，r=a(ab)定义的正则集合:{a,aa,ab,abb,……}={d，，e，+，-},则上的正则表达式d(dd)(e(+-)dd)表示的是无符号数的集合。其中d为0~9的数字。若两个正则表达式所表示的正则集合相同，则认为二者等价。两个等价的正则表达式U和V记为U=V。例如：U=(ab)，V=ba又如：U=b(ab),V=(ba)b再如：U=(ab),V=(ab)正则表达式的性质设U、V和W都是正则表达式，则如下关系普遍成立：U|V=V|U（交换律）U|(V|W)=(U|V)|W（结合律）U(VW)=(UV)W（结合律）、U(V|W)=UV|UW（分配律）(V|W)U=VU|WU；εU=Uε=Urr=rr=rrr…“或”的抽取律正则文法和正则表达式对上的正则表达式U,存在一个正则文法G=(VN,VT,P,S):L(G)=L(r)初始，VT=,SVN，生成正则产生式SU(R.1)对形如Ar1r2的正则产生式：Ar1BBr2BVN(R.2)对形如Arr1的正则产生式：ArBAr1BrBBr1BVN(R.3)对形如Ar1r2的正则产生式:Ar1Ar2不断应用R做变换，直到每个产生式右端只含一个VN正则文法和正则表达式对G=(VN,VT,P,S),存在一个=VT上的正则表达式r:L(r)=L(G)AxB,ByA=xyAxAyA=xyAxyA=xy正则文法和正则表达式举例例1：r=a(ad)VT={a,d}Sa(ad)R.1SaAA(ad)R.2A(ad)BAB(ad)BBR.3G[s]:SaAAVT={a,d}AaBVN={S,A,B}AdBBaBBdBBP正则表达式和正则文法举例G[s]:SaAAaAAdASaAaAdSaAaAaAadAdA(ad)A(ad)A(ad)(ad)S=a(ad)(ad)a=a((ad)(ad))=a((ad)+)R=a(ad)有穷自动机有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正则集合，即识别正则文法所定义的语言与正则表达式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机（DFA）和不确定的有穷自动机（NFA）。其中“不确定”的含义是：对于某个输入符号，在同一状态上存在不止一种转换。确定的和不确定的有穷自动机都能而且仅能识别正则集合，即它们能够识别正则表达式所表示的语言。确定的有穷自动机一个确定的有穷自动机(DFA)M是一个五元式：M=(S,∑,δ,s0,F)其中S是一个有限集，它的每个元素称为一个状态。∑是一个有穷字母表，它的每个元素称为一个输入字符δ是一个从S×∑至S的单值映射。δ(s,a)=s’意味着：当现行状态为s、输入字符为a时，将转换到下一个状态s’。我们称s’为s的一个后继状态。s0∈S，是唯一的初态。FS，是一个终态集（可空）确定的有穷自动机DFAM=（{S，U，V，Q}，{a，b}，δ，S，{Q}）其中f定义为：δ（S，a）=Uδ（V，a）=Uδ（S，b）=Vδ（V，b）=Qδ（U，a）=Qδ（Q，a）=Qδ（U，b）=Vδ（Q，b）=QabSUVUQVVUQQQQ字符状态bSUVQaaaba，bb确定的有穷自动机DFA接受的字符串对于∑*中的任何字符串t，若存在一条从初态结到某一终态结的道路，且这条路上所有弧的标记符连接成的字符串等于t，则称t可为DFAM所接收，若M的初态结同时又是终态结，则空字可为M所识别。∑*上的符号串t被M接受若t∑*，δ(S，t)=P，其中S为M的开始状态，PZ，Z为终态集。则称t为DFAM所接受（识别）。∑*上的符号串t，（我们将它表示成t1tx的形式，其中t1∈∑，tx∈∑*）在DFAM上运行的定义为：δ(Q,t1tx)=δ(δ(Q,t1),tx)其中Q∈S确定的有穷自动机例：证明t=baab被例中的DFA所接受。δ(S,baab)=δ(δ(S,b),aab)=δ(V,aab)=δ(δ(V,a),ab)=δ(U,ab)=δ(f(U,a),b)=δ(Q,b)=QQ属于终态。DFAM=（{S，U，V，Q}，{a，b}，δ，S，{Q}）其中δ定义为：δ（S，a）=Uδ（V，a）=Uδ（S，b）=Vδ（V，b）=Qδ（U，a）=Qδ（Q，a）=Qδ（U，b）=Vδ（Q，b）=Q非确定的有穷自动机一个非确定的有穷自动机(NFA)M是一个五元式：M=(S,∑,δ,S0,F)其中S是一个有限集，它的每个元素称为一个状态。∑是一个有穷字母表，它的每个元素称为一个输入字符δ是一个从S×∑*至S子集的单值映射。即：δ:S×∑*→2SS0S，是一个非空的初态集FS，是一个终态集（可空）非确定的有穷自动机例子NFAN=（{S,P,Z},{0,1},δ,{S,P},{Z}）其中δ(S,0)={P}δ(S,1)={S，Z}δ(P,1)={Z}δ(Z,0)={P}δ(Z,1)={P}SPZ00,111101S{P}{S,Z}0P{}{Z}0Z{P}{P}1简化为01SPS,Z0P.Z0ZPP1非确定的有穷自动机对于∑*中任何字α，若存在一条从某一初态结点到某一个终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略那些标记为ε的弧）等于α，则称α可为NFAM所识别（读出或接受）。若M的某些结点既是初态结点又是终态结点，或存在一条从某一初态结点到某一终态结点的ε通路，那么空字ε可为M所识别。NFA的确定化NFA的确定化显然，DFA是NFA的特例，但是对于每个NFAM都存在一个DFAM’’，使L(M)=L(M’’)。定义对状态集合I的几个有关运算：1状态集合I的-闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态s经任意条弧而能到达的状态的集合。状态集合I的任何状态s都属于-closure(I)。2状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体。定义Ia=-closure(move(I,a))-闭包的例子I={1},-closure(I)={1,2}；I={5},-closure(I)={5,6,2}；move({1,2},a)={5,3,4}I={1,2},Ia=-closure({5,3,4})={2,3,4,5,6,7,8}；12534687aaaNFA确定化的例子4f35621iaaaabbbb{i,1,2}{1,2,3}{1,2,3}{1,2,4}{1,2,3,5,6,f}{1,2,4}{1,2,3}IbIa{1,2,4}SAB{1,2,3,5,6,f}ABCCA{1,2,4,5,6,f}D{1,2,4,5,6,f}D{1,2,3,5,6,f}{1,2,4,6,f}{1,2,3,6,f}{1,2,4,5,6,f}CE{1,2,4,6,f}EF{1,2,3,6,f}FD{1,2,3,6,f}F{1,2,4,5,6,f}D{1,2,3,5,6,f}C{1,2,4,6,f}EB包含原初始状态i的状态子集为DFA的初态包含原终止状态f的状态子集为DFA的终态NFA的确定化aCDBAEFSbaaaaabbbbbabFSAABCBAbaBCDDCEFDEFFDCEDFA的最小化DFA的最小化（DFA的化简）——一个有穷自动机通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。最小状态DFA没有多余状态(死状态)没有两个状态是互相等价（不可区别）两个状态s和t可区别：不满足兼容性（一致性）——同是终态或同是非终态传播性（蔓延性）——从状态s出发读入某个aa和从状态t出发读入某个a到达的状态等价。DFA的最小化算法的核心把M的状态集K分成不相交的子集。结论接受L的最小状态有穷自动机不计同构是唯一的。DFAM=（K,∑,f,k0,,kt),最小状态DFAM’1.构造状态的初始划分：终态kt和非终态K-kt两组2.对∏施用传播性原则构造新划分∏new3.如∏new=∏,则令∏final=∏并继续步骤4，否则∏:=∏new重复24.为∏final中的每一组选一代表，这些代表构成M’的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M’中有一转换f’(k,a)=rM’的开始状态是含有K0的那组的代表M’的终态是含有Kt的那组的代表5.去掉M’中的死状态.DFA的最小化1645732aaaaabbbbbbbaa初始划分：一个由终态组成，一个由非终态组成P0=({1,2,3,4},{5,6,7})观察第一个子集，在读入a之后划分为P1=({1,2},{3,4},{5,6,7})观察第二个子集，在读入a之后划分为P1=({1,2},{3},{4},{5,6,7})观察第四个子集，在读入a之后划分为P1=({1,2},{3},{4},{5},{6,7})16453aaabbbbbaa正则文法与有限自动机的等价性对于正则文法G和有限自动机M，如果L(G)=L(M)，则称G和M是等价的。关于正则文法和有限自动机的等价问题，有以下结论：对每一个右线性正则文法G或左线性正则文法G，都存在一个正则自动机(FA)M，使得L(M)=L(G)。对每一个FAM，都存在一个右线性正则文法GR和左线性正则文法GL，使得L(M)=L(GR)=(GL)。正则文法与有限自动机的等价性正则文法GR={0,1},{A,B,C,D},A,P其中P由以下产生式构成A→0|0B|1DB→0D|1CC→0|0B|1DD→0D|1DABDC001010,11ABDC001010,11F00正则表达式和有限自动机的等价性关于正则表达式与自动机的等价性，有如下性质：对任何FAM，都存在一个正则表达式r，使得L(r)=L(M)。对任何正则表达式r，都存在一个FAM，使得L(M)=L(r)。ijV1V2ijij代之以12V13代之以12代之以123V2V1V2V1V2V3V1|V2V1V2*V3正则表达式和有限自动机的等价性对于简单的正则表达式：对于正则表达式Φ，所构造的NFA为：对于正则表达式ε，构造的NFA为：对于正则表达式a，a∈∑，构造的NFA为：xyxyεxya正则表达式和有限自动