编译原理词法分析演示

（优选）编译原理词法分析ppt讲解当前1页，总共57页。2.1词法分析器的设计考虑及

手工构造词法分析任务：从文件读入源程序，去除源程序中与编译无关的编辑字符、注释等，由字符拼接单词。每当识别出一个单词，就用单词的内部码（单词二元式）替换。执行词法分析任务的程序称为词法分析器。当前2页，总共57页。2.1.1单词类型及二元式编码㈠单词类型任何程序设计语言的单词都可将其分为5种类型，它们是：基本字 real、integer、……标识符 通常为以字母开始的数字字母串（简单变量、标号、……）常数 整常数（123）、实常数（123.456）、……运算符 +、*、/、……界符 ;、(、)、……㈡单词的性质基本字、运算符和界符对于某一程序设计语言来说是确定的，而源程序中的标识符和常数的个数是不确定的，随源程序而异。有些单词由单个字符构成，而有些单词由多个字符构成。当前3页，总共57页。㈢单词二元式编码经词法分析后，单词用二元式(code,val)表示。code表示单词的种别，用整数码表示。单词种别表示单词的语法特性，在语法分析时使用。val表示单词的值，在本书中用字符串表示。单词值表示了单词的语义特性，在语义分析时使用。㈣编码原则通常将标识符归为一种，常数按类型分种，基本字、运算符及界符采用一符一种。如果一个种别仅包含一个单词，那么单词种别就可代表该单词，无需给出单词值。为了输入和处理的方便，无意义的单词值用字符串"NUL"表示。若一个种别含有多个单词，除给出种别外，还需给出它的值。当前4页，总共57页。㈤实例设有某一程序设计语言，其部分单词二元式编码如下所示：单词单词种别单词值integeraNULrealcNULbegin{NULend}NUL标识符i字符串形式符号名无符号整常数x字符串形式数字无符号实常数y字符串形式数字==NUL**NUL++NUL((NUL))NUL,,NUL;;NUL计算园柱体表面积的源程序（输入输出略）如下所示：Begin/*S=2*3.14*R*R+2*3.14*R*H*/Realr,h,s;s=2*3.14*r*(r+h)End根据单词二元式编码，上述程序的单词二元式序列应为： ('{',"NUL") …………当前5页，总共57页。2.1.2源程序的输入及预处理

㈠源程序的输入

分段读入处理（早期）全部读入后处理源程序以文件形式存于外存，首先要将其读入内存才可进行词法分析。早期计算机内存较小，只能在内存设置长度有限的缓冲区，分段读入源程序进行处理。在编制程序时，必须考虑由于源程序分段读入所产生的问题。例如，由多个字符构成的单词有可能被缓冲区边界所打断（留作习题）。目前计算机所使用的的内存已超过若干年前硬盘容量，计算机内存足以容纳源程序的全部，故源程序可一次全部读入内存进行处理。当前6页，总共57页。设源程序如下所示，其中'\'为续行符。Begin/*S=2*3.14*R*R+2*3.14*R*H*/\n\tReal

r,h,s;\n\ts=2*3.\\n14*r*(r+h)\nEnd\n\0......\0源程序读入后，输入缓冲区的内容如下所示：当前7页，总共57页。㈡预处理词法分析器通常由二个部分构成： 预处理程序 扫描器（单词识别程序）①分成二部分的理由目前使用的程序设计语言大都采用自由格式书写，允许在单词之间存在多余的空格、换行和制表符（TAB）。源程序通常带有注释，注释不是程序的必要组成部分。有些语言还提供续行功能（例C语言中的续行符'\'），当一个单词过长（例字符串常数），可分多行列出。对于Fortran和Cobol之类语言，源程序还受到书写格式的限制。词法分析器可在输入缓冲区上直接识别单词，但从程序设计的角度来看，若把源程序预处理一下，则单词识别就比较容易。当前8页，总共57页。②预处理主要工作删除注释删除续行符，以及后续换行符(0AH)。换行符、TAB和空格具有界符作用，预处理时通常予以保留。在后面的分析中可以看到，它们的存在反而给后续的单词识别带来方便。为了简化判断，可在预处理时，将换行符和TAB统一替换为空格。大多数语言（除C语言）不区分大小写，可在预处理时，将大写字母变换成小写字母，或相反，以方便后续处理。对于受书写格式限制的语言（例Fortran和Cobol），还应识别标号区，正确给出语句标号。识别续行标志，把相继行捻接在一起，给出语句结束符。beginrealr,h,s;

s=2*3.14*r*(r+h)

end\0...\0上述源程序经预处理后，扫描缓冲区中的内容如下所示：当前9页，总共57页。㈢预处理例用伪代码编写一个预处理程序，要求如下：去除源程序中注释（源程序中的注释用/*……*/标记，不允许嵌套使用）去除源程序中续行符（\）将TAB和换行符替换为空格将大写字母变换成小写在源程序尾部添加字符'#'，这是编译程序内部的一个特殊的单词，以示源程序结束。每调用一次，将经预处理的源程序全部送入内存中的扫描缓冲区，供扫描器识别单词。当前10页，总共57页。①算法说明用伪代码编写预处理程序，输入和预处理可同时进行，无需输入缓冲区，将读入后经预处理的源程序直接送扫描缓冲区buf[1..n]。定义布尔变量in_comment，记录当前处理字符是否处于注释。若in_comment的值为false，则表示当前读入字符未处于注释中，此时应将当前处理字符存入扫描缓冲区；若in_comment的值为true，则表示当前处理字符处于注释中，此时无需将该字符存入buf中，相当于掉弃。当读入“/*”，布尔变量in_comment的值由false变为true；当读入“*/”，布尔变量in_comment的值由true变为false。可用变量cur_c记录当前正在处理的字符，用old_c记录刚处理过的字符。 ΧΧΧΧΧ/*ΧΧΧΧΧ*/ΧΧΧΧΧin_comment:f………f/t…………t/f………f当前11页，总共57页。0.procedurepro_process() //扫描缓冲区buf[]和扫描缓冲区指针i1.old_c←‘\0’:in_comment←false:cur_c←文件第一个字符:i←12.whilenoteof(“source.txt”)do//文件尚未处理完3. ifnotin_commentthen//当前字符未处于注释中4. ifold_c='/'andcur_c='*'then//进入注释5. i←i-1:in_comment←true6. else7. ifold_c='\'andcur_c=换行符theni←i-1//是续行符8. else9. ifcur_c≥'A'andcur_c≤'Z'thencur_c←cur_c+3210. ifcur_c=制表符orcur_c=换行符thencur_c←空格11. i←i+1:buf[i]←cur_c //送入扫描缓冲区12. endif13. endif14. else//当前字符处于注释中15. ifold_c='*'andcur_c='/'thenin_comment←false //离开注释16. endif 17. old_c←cur_c:cur_c←文件下一个字符18.endwhile19.i←i+1:buf[i]←'#'20.endprocedure当前12页，总共57页。2.1.3基本字的识别和超前搜索程序设计语言单词以基本字识别最为困难，原因如下：①有些语言对基本字不加保护，用户可用作普通标识符。②基本字、用户定义的标识符和常数之间可能没有分隔符。例标准Fortran对基本字不加保护，用户可以把它们用作普通标识符。让我们来观察下面三个Fortran语言语句。IF(5.EQ.M)GOTO55 逻辑IF，当M等于5转标号为55的语句。IF(5)=55 IF为数组名，IF(5)为下标变量IF(X+Y)110,120,130算术IF，当X+Y<0，转标号为110的语句；当X+Y等于0，转标号为120的语句；当X+Y>0，转标号为130的语句显然仅根据IF无法判断其为何种单词，可能是基本字，也可能是标识符。当前13页，总共57页。解决办法是超前搜索，一直扫描到右括号后面的字符。若该字符为字母G或g，则为逻辑IF；若为数字，则为算术IF；若为=，则为标识符。超前搜索导致词法分析器实现困难。为了降低词法分析器的复杂性，避免超前搜索，在实际实现中，大多数语言的编译程序对用户采取了二条限制措施：①所有基本字均为保留字，用户不得使用它们作为标识符。②将空格、TAB和换行符视为界符。在基本字、用户定义的标识符和常数之间，若没有运算符或界符，则至少用一个空格（或TAB、换行符）加以分隔。这样空格、TAB和换行符不再是没有意义的了，这也就是为什么在词法分析预处理中将空格、TAB和换行符保留下来的原因。采用上述二条限制措施，对用户来讲是完全可接受的，并且已成为程序员进行程序设计的惯例。词法分析器对于所有单词的识别，最多只要向前看一个字符就足够了。当前14页，总共57页。2.1.4遍㈠遍的基本概念由外存获得前一遍的工作结果(对于第一遍而言，从外存获得源程序)，完成它所含的有关阶段工作之后，再把结果存于外存。㈡遍引入的历史背景早期的计算机内存较小，编译程序相对而言体积较大。使用遍技术的优点在于，可根据当前遍的工作，装入相应的工作程序。当一遍工作完之后，内存空间大部分被释放。当下一遍进入后，几乎可以使用全部存储空间。遍数多一点还有一个好处，即整个编译程序的逻辑结构较为清晰。但是，遍数多势必增加输入输出所耗费的时间。㈢遍和编译程序的结构遍决定了编译程序的结构。在本书中，词法分析器是以函数形式书写的，函数的返回值是一个单词的二元式。①词法分析不作为独立一遍②词法分析作为独立一遍（本书采用）当前15页，总共57页。2.1.5状态转换图和词法分析器手工构造㈠引入状态转换图的必要性若不考虑科学计数法形式，程序设计语言的无符号实型常数有三种书写形式，它们是： 无小数部分形式 134. 无整数部分形式 .12 完全形式 3.14如果考虑科学计数法形式，则无符号实型常数识别更复杂。直接编写识别无符号实型常数的程序有一定难度，状态转换图是构造单词识别程序（扫描器）的一种较好工具。㈡状态转换图基本概念及应用①状态转换图是一个有向图。在状态转换图中，结点代表状态，用园圈表示。状态之间用箭弧连接。箭弧上的标记代表在射出结状态下可能出现的合法的输入字符。当前16页，总共57页。②一个状态转换图包含若干个状态（结点），其中有一个是初态，用符号指示，是识别字符串的起点。状态转换图至少有一个终态，表示已识别出一个字符串（单词），终态用双圈表示。例，识别标识符的状态转换图如下所示：其中0为初态，2为终态。02当前17页，总共57页。③若当前状态是1，只有当输入字符为非字母数字，才可能到达状态2，显然多读了一个字符，这就是终态结2上星号‘*’的含义，它并不是正在识别的标识符的组成部分。此时应将其退回，下次识别单词从该字符开始。④单词的尾部空格作为单词的结束标志，单词的前导空格在识别单词前滤去，所以在初态0有一个标记为空格的自回路。在词法分析预处理中，空格作为界符被保留下来。由于空格不是任何单词的组成部分（除字符串常数），故在识别单词前，应将单词的前导空格滤去。由于空格的特殊性，状态转换图中用虚线表示（若当前输入字符是空格，重新进入1状态）。在识别标识符的过程中，当读入的字符不是字母或数字，可能是空格，说明当前正在识别的单词已完全读入。为程序处理方便起见，不管是什么字符，均将其退回。若退回的是空格，该空格将成为下一个单词的前导空格。当前18页，总共57页。⑤一个状态转换图可用于识别单词，从初态出发，经一条通路到达某一终态，路径上的标记依次连接而成的字符串，即为状态转换图识别出的单词。例，识别实常数和整常数的状态转换图如下所示：0596当前19页，总共57页。设输入串为"134.+……"，从初态0出发，经路径到达终态5，路径上标记依次连接而成的字符串为"134.+"，退回多读的字符'+'，识别出的字符串（单词）为"134."。50当前20页，总共57页。⑥一个程序设计语言单词的识别，可以用若干张状态转换图予以描述，虽然用一张图也可以，但用若干张图，有时会有助于概念的清晰化。将上述三个图合并视为一个图，初始状态为0。从初态0出发，若当前输入字符是字母，则进入状态1；若为数字，则进入状态3；若为小数点，则进入状态7。若为加号，则进入状态10。否则，或进入其它单词的识别（若有的话），或出错（非法字符）。下图是识别"#"、"+"和"++"的状态转换图。0111213当前21页，总共57页。㈢利用状态转换图识别单词状态转换图每次只能识别一个单词，若源程序中有N个单词，则需使用状态转换图N次。设源程序为"x+++y#"（'#'是预处理程序添加的），单词识别程序（扫描器）共使用状态转换图5次。从初态0出发，读入'x'进入状态1，在状态1读入'+'，进入终态2，识别出标识符"x"，退回'+'；从初态0出发，读入'+'进入状态10，在状态10读入'+'，进入终态11，识别出运算符"++"；从初态0出发，读入'+'进入状态10，在状态10读入'y'，进入终态12，识别出运算符"+"，退回'y'；从初态0出发，读入'y'进入状态1，在状态1读入'#'，进入终态2，识别出标识符"y"，退回'#'；从初态0出发，读入'#'进入状态13，识别出单词"#"，识别出单词"#"意味着整个源程序中字符处理完毕。当前22页，总共57页。㈣根据状态转换图编制程序状态转换图就是程序控制流程图，每个结点对应一段程序。分叉结点：if语句或switch语句含自回路结点：while语句终态结点：return语句返回单词的二元式。若终态结点带有星号'*'，则缓冲区指针值不变；否则缓冲区指针值加1，指向下一字符。下面是根据识别标识符的状态转换图编制的部分扫描程序。structcode_val{ //结构用于存放单词二元式 charcode;charval[20];};structcode_valscanner(char*buf);//单词识别程序(扫描器)，每调用一次返回一个单词的二元式。voidconcat(chartoken[],charc); //拼接单词函数charreserve(chartoken[]); //查基本字表函数当前23页，总共57页。structcode_val{ charcode;charval[20];};structcode_valscanner(char*buf)//每调用一次返回一个单词的二元式{//buf为扫描缓冲区存放经预处理的源程序。

staticinti=0; //静态局部变量，扫描缓冲区指示器。

structcode_valt={'\0',"NUL"};//用于存放单词二元式，识别前清空。

chartoken[20]=""; //用于拼接单词的字符数组，识别前清空。

//去除前导空格 while(buf[i]=='')i++;//进入标识符或基本字的识别 if(buf[i]>='a'&&buf[i]<='z'){ while(buf[i]>='a'&&buf[i]<='z'||buf[i]>='0'&&buf[i]<='9') concat(token,buf[i++]); //拼接函数 t.code=reserve(token); //查基本字表函数 if(t.code=='i')strcpy(t.val,token); //是标识符 returnt; //返回标识符或基本字的二元式 } ………………… //其余单词识别程序略}//endofscanner当前24页，总共57页。①拼接函数concat(token[],ch)concat为拼接函数，它有二个参数。设在调用前token[]内容为"beg",输入字符ch为'i'，则调用拼接函数concat后，token的内容为"begi"。voidconcat(chartoken[],charc){for(inti=0;token[i]!='\0';i++); //找到尾token[i]=c;token[++i]='\0';}②查基本字表函数reserve(token[])基本字通常是由字母构成，符合标识符规则。考虑简化程序设计，将基本字作为一种特殊标识符来处理。设置一个基本字表（包括相应二元式编），当状态转换图识别出一个标识符时，就去查对这张表，确定它是基本字还是标识符。charreserve(chartoken[]){//基本字及编码表constchar*table[]={"begin","end","integer","real"};constcharcode[]={"{}ac"};for(inti=0;i<strlen(code);i++) if(strcmp(token,table[i])==0)returncode[i];return'i';//标识符的单词种别为'i'}begin}end{integerarealc0123当前25页，总共57页。2.2正规式、自动机及词法分析器的自动生成当前26页，总共57页。2.2.1基本概念㈠有穷字母表∑符号有限集，它的每个元素称为字符。㈡字（字符串）∑上字符所构成的有限序列。①空字不包含任何字符的字，称为空字，记为ε（空字相当于高级语言中的空串“”）。 ε 空字 {} 空集 {ε} 集合仅有一个元素ε②∑*∑上所有字的全体，包括ε。例：∑={0，1} ∑*={ε，0，1，00，01，10，11，000，001，……}当前27页，总共57页。③（集合的）积运算定义：设U、V∑*，U和V的积记为UV（或UV）且定义为 UV={αβ|（α∈U）∧（β∈V）}积不满足交换律 UV≠VU积满足结合律 (UV)W=U(VW)证明见本书38页积满足分配律 X(Y∪Z)=XY∪XZ④（集合的）闭包设VΣ*，V的闭包记为V*且定义为V自身的任意有限次积，即V*=V0∪V1∪V2∪……∪Vn，规定V0={ε}。设V={0,1}，则V*={ε,0,1,00,01,10,11,000,001,……}闭包V*中的每个字都是由V中的字经有限次连接而成。⑤（集合的）正则闭包定义：设VΣ*，V的正则闭包记为V+，且定义V+=VV*。根据定义可以证明V+=V1∪V2∪……∪Vn(详见本书18页)。设V={0,1}，则V+=V1∪V2∪……∪Vn={0,1,00,01,10,11,000,001,……}，V+可理解为二进制数的全体。若V=U，则UV=VV=V2当前28页，总共57页。2.2.2正规式与正规集㈠正规式和正规集的定义：ε和Φ是∑上的正规式，相应的正规集为{ε}、{}。若字符a∈∑，则字符a是正规式，相应正规集为{a}。若α、β为正规式，相应正规集分别记为L(α)和L(β)，则α|β是正规式，其相应正规集记为L(α|β)，且令L(α|β)=L(α)∪L(β)。若α、β为正规式，相应正规集分别记为L(α)和L(β)，则αβ(或α·β)是正规式，其相应正规集记为L(αβ)，且令L(αβ)=L(α)L(β)。若α=β，则L(αβ)=L(αα)=

L(α2)=L(α)2。推广到一般，正规式α自身的n次积αα…α是正规式，可记为αn，其相应正规集记为L(αn)，显然L(αn)=L(α)n。）若α为正规式，相应正规集记为L(α)，则α*=α0|α1|α2|……|αn是正规式，规定α0=ε，其相应正规集记为L(α*)，且令L(α*)=L(α)*。正规式运算符优先性依次为:*、·、︱,可用园括号改变运算顺序。例子详见本书第21页当前29页，总共57页。㈡实际意义有穷字母表Σ是程序设计语言所使用的字符集的抽象正规集是程序设计语言单词集的抽象正规式是程序设计语言构词规则的抽象㈢正规式相等原理二个正规式是相等的，当且仅当二个正规式所表示的正规集是相等的。例：设α是正规式，求证α|α=α。证： L(α|α)=L(α)∪L(α)=L(α) ∵L(α|α)=L(α) ∴α|α=α㈣正规式满足下列关系①交换律：α|β=β|α②结合律：α|(β|γ)=(α|β)|γ，α(βγ)=(αβ)γ③分配律：α(β|γ)=αβ|αγ，(β|γ)α=βα|γα④εα=αε=α当前30页，总共57页。㈤例设α=a|b|……|z，β=0|1|……|9。描述标识符的正规式： α(α|β)*

描述二进制数的正规式： (0|1)(0|1)*描述无符号整常数的正规式： ββ*

描述无符号实常数的正规式：ββ*.β*|.ββ*|(ββ*.β*|.ββ*|ββ*)(E|e)(+|-|ε)ββ*123.45 123.当前31页，总共57页。2.2.3确定有限自动机（DFA）㈠DFA定义一个确定有限自动机M是一个五元式 M=(S，Σ，f，s0，Z)S是一个有限集，它的每一个元素称为状态。Σ是一个有穷字母表，它的每个元素称为一个输入字符。f是一个从S×Σ至S的映照，即f：S×Σ→S（单值函数）例f(si,a)=sj，表示当现行状态为si，若输入字符为a，则转移到下一状态sj，sj称为si的后继状态。s0∈S，是唯一的一个初态。ZS，是一个终态集。例：一个识别二进制数的确定有限自动机 M=（{0，1}，{'0','1'}，f，0，{1}）其中f的定义如下： f(0,'0')=1、f(0,'1')=1、f(1,'0')=1、f(1,'1')=1当前32页，总共57页。㈡状态转换矩阵函数f可用矩阵表示，行表示状态，列表示输入字符，该矩阵称为状态转换矩阵。只要对初态和终态作适当标记，可用一个状态转换矩阵来表示DFA。㈢DFAM可用一个（确定的）状态转换图表示例识别二进制数的DFA可用（确定的）状态转换图表示如下：状态/字符'0''1'011111接上例当前33页，总共57页。㈣字α可为DFAM识别对于一个字α，若存在一条从初态结到某一终态结的路径，且路径上的所有弧的标记依序连接成的字为α，则称α可为DFAM所识别或接受。若DFAM的初态结同时又是终态结，则称空字ε可为DFAM所识别或接受。DFAM所识别的字全体记为L(M)。设α=1012=5因从初态0出发，存在一条到终态1的路径。路径上的标记依次连接为101，则称α=101可为M所识别或接受。 L(M)={α|α为二进制数}。当前34页，总共57页。2.2.4非确定有限自动机（NFA）㈠NFA定义一个非确定的有限自动机M是一个五元式 M=（S，Σ，f，S0，Z）S是一个有限集，它的每一个元素称为状态。Σ是一个有穷字母表，它的每个元素称为一个输入字符。f是一个从S×Σ*到S的子集映照，即f：S×Σ*→2S（多值函数）2S表示幂集，若S={0，1}，则2S={{}，{0}，{1}，{0，1}}。S0S，是一个非空初态集，即NFA的初态不一定唯一。ZS，是一个终态集。DFA和NFA的主要区别为：映照f（函数），DFA的映照f是从"状态×字符"映射到"状态"，f为单值函数；而NFA的映照f是从"状态×字"映射到"状态子集"，f为多值函数。当前35页，总共57页。例某一非确定有限自动机 M=（{1，2，3，4，5，6}，{a，b}，f，{1，2}，{3}）其中f的定义为：f(1,"a")={4，5}、f(5，ε)={6}、f(6，ε)={2}、f(2，"ab")={3}其余情况f(si，α)={}（α∈Σ*，si∈S）㈡NFAM可用一个（非确定的）状态转换图表示当前36页，总共57页。㈢字α可为NFAM识别对于Σ*中的一个字α，若在NFAM中存在一条从某一初态到某一终态的路径，且路径上的所有标记依序连接成的字为α，则称α可为NFAM所识别或接受。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的ε道路，那么空字ε可为M所接受。非确定有限自动机M所识别的字全体记为L(M)。对于任何二个有限自动机M和M'，若L(M)=L(M')，则称二个有限自动机M和M'等价。DFA是NFA的特例，对于每个NFAM存在一个DFAM'，使得L(M)=L(M')。当前37页，总共57页。2.2.5正规式与确定有限自动机的等价性对于Σ上的每个正规式V，存在一个Σ上的确定有限自动机M，使得L(V)=L(M)。㈠VNFA①将V表示成拓广NFA②根据下面三条规则对V进行分裂（规则基于识别的语言不变），直至每条弧上的标记为Σ上的一个字符或ε。 V 当前38页，总共57页。例，已知正规式(a|b)*(aa|bb)构造它的NFA。当前39页，总共57页。㈡NFADFA为了便于描述NFA确定化算法，我们引进二个概念。①I的ε闭包I的ε闭包记为ε_CLOSURE(I)或CLOSURE(I)，设I是NFAM状态集的一个子集，I的ε闭包定义为：若状态s∈I，则s∈ε_CLOSURE(I)。若状态s∈I，则从状态s出发，经一条或多条ε弧所能到达的状态s'也属于ε_CLOSURE(I)。②IaI NFAM状态集的一个子集Ja 从I出发经一条a弧所能到达的状态全体Ia ε_CLOSURE(Ja)当前40页，总共57页。设I={1}，则CLOSURE(I)=CLOSURE({1})={1,2}。设I={5,4,3}，则CLOSURE(I)=CLOSURE({5,4,3})={5,4,3,6,2,8,7}。接上例设I={1，2}，则Ja={4,5}∪{3}={3,4,5}Ia=CLOSURE({3,4,5})={5,4,3,6,2,8,7}③NFA确定化算法IIa（a∈∑）Ib（b∈∑）CLOSURE({X})1）数据结构及初始状态手工计算当前41页，总共57页。2）算法描述0.procedureNFA_TO_DFA1. p_cur←1 //当前指针，指示当前处理的状态子集。2. p_end←1 //表尾指针3. I[1]←CLOSURE({X})4. whilep_cur≤p_end5. fori←1ton //设∑={x1,x2,…,xn}6. ifIXi[p_cur]≠{}andIXi[p_cur]I[1..p_end]then7. p_end←p_end+18. I[p_end]←IXi[p_cur]9. endif10. endfor11. p_cur←p_cur+112. endwhile13.endprocedure当前42页，总共57页。IIaIb{X,1,2}{1,3,2}{1,4,2}{1,3,2}{1,3,Y,2}{1,4,2}{1,4,2}{1,3,2}{1,Y,4,2}{1,3,Y,2}{1,3,Y,2}{1,4,2}{1,Y,4,2}{1,3,2}{1,Y,4,2}根据上述算法对NFAM进行确定化。因NFAM具有6个状态，状态子集个数（包括空集）最多为64，故表的长度不会超过26-1=63，循环必然在有限步中结束。3）结果处理将I中的每个子集视为DFAM'的一个状态。ε_CLOSURE({X})视为DFAM'的初态。将所有含有原NFA终态(即Y)的DFAM'状态视为终态。将I、Ia、Ib、……视为DFAM’状态转换矩阵，即函数f。4）重新标记状态/字符ab0121322143324140是初态，3和4为终态。当前43页，总共57页。5）用（确定的）状态转换图表示构造过程采用子集法，从字的识别角度来看，DFAM'和NFAM是等价的。当前44页，总共57页。2.3词法分析器的自动生成输入正规式（构词规则），经自动生成器加工，其结果为DFA。词法分析器的自动生成器输入正规式输出DFA（状态转换矩阵）㈠自动生成过程概述①构造描述每个单词的正规式Pi(1≤i≤N)。②根据正规式Pi构造NFAMi(1≤i≤N)，假定初态均为0。在构造NFAMi的同时，逐步并且最终形成识别全部单词的NFAM。③NFAM确定化④重新标记，构造DFAM'。当前45页，总共57页。㈡实例（模型语言的词法）①模型语言字符集{'a'..'z'，'0'..'9'，'+'，'='，'*'，','，';'，'('，')'，'#'}②模型语言单词集基本字：begin、end、integer、real标识符：以字母开始的数字字母串无符号整常数：数字串运算符：+、*、++、=界符：,、;、(、)、#③单词编码基本字：begin('{',"NUL"}、end('}',"NUL")、integer('a',"NUL")、real('c',"NUL")标识符：('i',字符串) 无符号整常数：('x',字符串)运算符:=('=',"NUL")、+('+',"NUL")、*('*',"NUL")、++('$',"NUL")界符：,(',',"NUL")、;(';',"NUL")、(('(',"NUL")、)(')',"NUL")、#('#',"NUL")当前46页，总共57页。②构造NFAM实例解：①构造正规式（令α=a|b|c|d|……|z、β=0|1|2|3|4|5|6|7|8|9）标识符 α(α|β)*无符号整常数 ββ*运算符 单词本身（例'='的正规式为'='，"++"的正规式为"++"）界符 单词本身（例';'的正规式为';'）基本字通常是由字母构成，符合标识符规则，将基本字作为一种特殊标识符来处理（可设置保留字表，二者区分可通过查表）。当前47页，总共57页。③NFAM确定化IIαIβI=I+I*I,I;I(I)I#{0}{1,12,13}{2,14,15}{3}{4,5}{6}{7}{8}{9}{10}{11}{1,12,13}{12,13}{12,13}{2,14,15}{14,15}{3}{4,5}{16}{6}{7}{8}{9}{10}{11}{12,13}{12,13}{12,13}{14,15}{14,15}{16}当前48页，总共57页。④重新标记，构造DFAM'。状态/字符αβ=+*,;()#0123456789101111121234135678910111111121213注：0为初态，其余均为终态。当前49页，总共57页。㈢扫描器控制程序工作原理每次识别单词，控制程序总是从初态出发，不断读入字符，进入下一状态，寻求最长匹配，直到无法前进为止，这样始终多读一个字符。在状态迁移过程中，需用Token数组保存读入字符。在无法前进时，若发现当前状态为终态，则认为识别出一个单词，反之出错，即Token数组所保存的字符串不构成一个单词，而是源程序中的一个错误词形。事先设置一个单词二元式编码表，它包括除标识符和整常数以外的所有单词（基本字、运算符和界符）。当DFA识别出一个单词，就根据Token数组所保存的字符串去查表。若该单词在表中存在，即可获得二元式编码；若不存在，则该单词必为标识符和整常数二者之一，只要稍加判断即可区分。首字符为字母的是标识符，首字符为数字的是无符号整常数。当前50页，总共57页。DFA每次只能识别一个单词，需多次使用DFA来识别源程序中单词，直到源程序中的字符全部处理完。由于构造的方法不同，在DFA某一个终态中，有可能包含原NFA中的二个终态或更多，即在该状态可识别出二个词形相似的单词，这就存在一个优先匹配问题。此时，需调整单词二元式编码表中的单词排列顺序，将需优先匹配的单词排在表的较前面，这样在单词查找过程，让其先得到匹配。设源程序为“x+++y#”（‘#’是预处理程序添加的），扫描器共使用确定有限自动机5次（见下页）。当前51页，总共57页。从初态0出发，读入'x'进入状态1，在状态1读入'+'，无法前进。因当前所处状态1为终态，故识别出一个单词。查表未果，由于首字符为字母，故单词"x"为标识符，返回单词二元式编码('i',"x")并退回'+'。从初态0出发，读入'+'进入状态4，在状态4读入'+'，进入终态13，在状态13读入'+'，无法前进。因当前所处状态13为终态，故识别出一个单词。查表，确认识别出单词为"++"，返回单词二元式编码('$',"NUL")并退回'+'。从初态0出发，读入'+'进入状态4，在状态4读入'y'，无法前进。因当前所处状态4为终态，故识别出一个单词。查表，确认识别出单词为"+"，返回单词二元式编码('+',"NUL")并退回'y'；从初态0出发，读入'y'进入状态1，在状态1读入'#'，无法前进。因当前所处状态1为终态，故识别出一个单词。查表未果，由于首字符为字母，故单词"y"为标识符，返回单词二元式编码('i',"y")并退回'#'。从初态0出发，读入'#'，进入状态10。由于无法再读入字符，即查表，确认识别出单词为"#"，返回单词二元式编码('#',"NUL")。识别出单词"#"意味着整个源程序中字符全部处理完毕。当前52页，总共57页。㈣扫描器控制程序的实现⑴状态转换矩阵的数字化控制程序是根据DFA来工作的，首先要将状态转换矩阵数字化，空白用0表示。在预处理中，空格作为界符被保留下来。单词的前导空格在识别一个单词前被滤去，单词的尾部空格用作单词的终止标志，故在状态转换矩阵中，应增加空格列，该列每个元素的值均标记为0。因26个字母作用相同，故可用一列表示。在查表时可将26个字母转换成1个，例'a'。因10个数字作用相同，故可用一列表示。在查表时可将10个数字转换成1个，例'0'。状态转换矩阵经数字化后如下页所示：当前53