《词法分析副》PPT课件.ppt

第2章 词法分析,2.1 词法分析器的设计考虑及手工构造,2.1.1 单词类型及二元式编码 单词类型基本字、标识符、常数、运算符、界符单词的性质 个数确定和不确定单字符或多字符构成,2.1 词法分析器的设计考虑及手工构造,单词二元式编码经词法分析后，单词用二元式(code,val)表示。code表示单词的种别，用整数码表示，在语法分析时使用。val表示单词的值，在本书中用字符串表示，在语义分析时使用。,2.1 词法分析器的设计考虑及手工构造,编码原则通常将标识符归为一种，常数按类型分种，基本字、运算符及界符采用一符一种。,2.1 词法分析器的设计考虑及手工构造,实例-设有某一程序设计语言，其部分单词二元式编码如下所示：,2.1 词法分析器的设计考虑及手工构造,2.1 词法分析器的设计考虑及手工构造,用该程序设计语言编制的计算园柱体表面积的源程序（输入输出略）如下所示：Begin/*S=2*3.14*R*R+2*3.14*R*H*/Real r,h,s;s=2*3.14*r*(r+h)End,2.1 词法分析器的设计考虑及手工构造,根据单词二元式编码，上述程序的单词二元式序列应为：(,NUL)(c,NUL)(i,r)(,NUL)(i,h)(,NUL)(i,s)(;,NUL)(i,s)(=,NUL)(x,2)(*,NUL)(y,3.14)(*,NUL)(i,r)(*,NUL)(,NUL)(i,r)(+,NUL)(i,h)(),NUL)(,NUL),2.1 词法分析器的设计考虑及手工构造,2.1.2 源程序的输入及预处理源程序的输入l 分段读入处理（早期）l 全部读入后处理设源程序如下所示，其中为续行符。,2.1 词法分析器的设计考虑及手工构造,2.1 词法分析器的设计考虑及手工构造,源程序读入后，输入缓冲区的内容如下所示：,2.1 词法分析器的设计考虑及手工构造,预处理词法分析器通常由二个部分构成：预处理程序扫描器（单词识别程序）,2.1 词法分析器的设计考虑及手工构造,分成二部分的理由词法分析可在输入缓冲区上直接进行，但从程序进行的角度来讲，若是把输入串预处理一下，则单词识别就会比较容易，故词法分析器通常由预处理程序和扫描器（单词识别程序）两部分组成。,2.1 词法分析器的设计考虑及手工构造,预处理主要工作1.删除注释2.删除续行符以及后续换行符（0AH）3.Tab的作用相当于多个空格，换行符、Tab和空格具有界符作用，预处理时通常予以保留。在后面的分析中可以看到，它们的存在给后续的单词识别带来方便。为了简化判断，可在预处理时将换行符和Tab统一替换为空格。4.大多数语言（除C语言外）不区分大小写，可在预处理时大写字母变换成小写字母，或相反，以方便后续处理。5.对于受书写格式限制的语言（如FORTRAN和COBOL），还应识别标号区，正确给出语句标号；识别续行标志，把相继行连接在一起，给出语句结束符。,2.1 词法分析器的设计考虑及手工构造,上述源程序经预处理后，扫描缓冲区中的内容如下所示：,2.1 词法分析器的设计考虑及手工构造,预处理程序下面用C/C+语言来编写一个预处理程序，其作用是去除源程序中的注释和续行符，将Tab和换行符替换为空格，将大写字母变换成小写字母。每调用一次，将经预处理的源程序全部送入内存中的扫描缓冲区，供扫描区识别单词。,2.1 词法分析器的设计考虑及手工构造,程序实现，由两个函数构成：主函数main是测试驱动程序，调用预处理函数pro_process，模拟词法分析器工作；函数pro_process执行预处理任务，借助于传地址获得扫描缓冲区的首址，将经预处理的源程序送入扫描缓冲区。,2.1 词法分析器的设计考虑及手工构造,由于算法需要，在源程序尾部添加字符#，这是一个特殊的单词，表示源程序的结束。源程序中的注释用/*.*/标记，不允许嵌套使用，这和大多数高级语言的规定一致。,2.1 词法分析器的设计考虑及手工构造,源程序的输入及预处理#include#include void pro_process(char*);void main()/测试驱动程序/定义扫描缓冲区char buf4048=0;/缓冲区清0/调用预处理程序pro_process(buf);/在屏幕上显示扫描缓冲区的内容coutbufendl;,2.1 词法分析器的设计考虑及手工构造,void pro_process(char*buf)/预处理程序ifstream cinf(source.txt,ios:in);int i=0;/计数器char old_c=0,cur_c;/前一个字符，当前字符。bool in_comment=false;/false表示当前字符未处于注释中。while(cinf.read(/在源程序尾部添加字符#,2.1 词法分析器的设计考虑及手工构造,while(cinf.read(/保留前一个字符/end of while,2.1 词法分析器的设计考虑及手工构造,数据说明source.txt（源程序文件）char buf（扫描缓冲区）bool in_comment（状态标志）若in_comment的值为false，表示当前从文件读入的字符未处于注释中，此时应将读入的字符存入扫描区；若in_comment的值为ture，则表示当前读入的字符处于注释中，此时读入的字符应丢弃。XXXXX/*XXXXX*/XXXXXf.f/t.t/f f当读入“/*”时，布尔变量in_comment的值由false变为true；当读入“*/”时，布尔变量in_comment的值由ture变为false。,2.1 词法分析器的设计考虑及手工构造,上机练习用高级语言编写一词法分析预处理程序。从文件读入源程序，去除源程序中的注释（注释用标记），用空格取代源程序中的Tab和换行符，将预处理结果显示在屏幕上。源程序中无续行符，字母无须处理，源程序尾部需要添加字符。,2.1 词法分析器的设计考虑及手工构造,2.1.3 基本字的识别和超前搜索 程序设计语言单词以基本字识别最为困难，原因如下：有些语言对基本字不加保护，用户可用作普通标识符。基本字、用户定义的标识符和常数之间没有分隔符。,2.1 词法分析器的设计考虑及手工构造,解决办法：所有基本字均为保留字(Reserved word)，用户不得使用它们作为标识符。将空格、TAB和换行符视为界符。在基本字、用户定义的标识符和常数之间，若没有运算符或界符，则至少用一个空格（或TAB、换行符）加以分隔。,2.1 词法分析器的设计考虑及手工构造,遍的基本概念由外存获得前一遍的工作结果，完成后把结果存于外设。遍引入的历史背景早期内存较小，编译程序相对较大遍和编译程序的结构1.一遍工作后，内存大部分释放，下一遍后，可以使用全部存储空间2.使得编译程序的逻辑结构比较清晰3.但增加了输入输出所耗费时间,2.1 词法分析器的设计考虑及手工构造,2.1.5 状态转换图和词法分析器的手工构造引入状态转换图的必要性程序设计语言的无符号实型常数有三种书写形式：无小数部分形式：134无整数部分形式：.12完全形式：3.14直接编写识别程序有难度，使用状态转换图是构造单词识别程序的好途径。,2.1 词法分析器的设计考虑及手工构造,状态转换图基本概念及应用状态转换图是一个有向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连接箭弧上的标记代表在射出结点状态下可能出现的合法的输入字符,2.1 词法分析器的设计考虑及手工构造,例1，识别标识符的状态转换图如下所示：,2.1 词法分析器的设计考虑及手工构造,例2，识别实常数和整常数的状态转换图,2.1 词法分析器的设计考虑及手工构造,例3，识别#、+和+的状态转换图,2.1 词法分析器的设计考虑及手工构造,利用状态转换图识别单词 状态转换图每次只能识别一个单词，若源程序中有N个单词，则需使用状态转换图N次。设源程序为x+y#（#是预处理程序添加的），单词识别程序（扫描器）共使用状态转换图5次。,2.1 词法分析器的设计考虑及手工构造,1.从初态0出发，读入x进入状态1，在状态1读入+，进入终态2，识别出标识符x，退回+；2.从初态0出发，读入+进入状态10，在状态10读入+，进入终态11，识别出运算符+；,2.1 词法分析器的设计考虑及手工构造,3.从初态0出发，读入+进入状态10，在状态10读入y，进入终态12，识别出运算符+，退回y；4.从初态0出发，读入y进入状态1，在状态1读入#，进入终态2，识别出标识符y，退回#；,2.1 词法分析器的设计考虑及手工构造,5.从初态0出发，读入#进入状态13，识别出单词“#”，识别出单词“#”意味着整个源程序中字符处理完毕。为什么在C语言中x+y解释为(x+)+y,2.1 词法分析器的设计考虑及手工构造,根据状态转换图编制程序（见“识别标识符的状态转换图编制的扫描程序”WORD文件）,2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例1.字符集a.z0.9+=*，；（）#发现集合以外的字符，即非法字符，应终止词法分析器,2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例2.单词集基本字：begin,end,integer,real标识符：以字母开始的数字字母串无符号整常数无符号实常数运算符+*+=界符，；（）#错误形式.前后无数字字符的小数点出现错误形式，终止词法分析器运行,2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例3.单词编码基本字：begin(,NUL),end(,NUL),integer(a,NUL),real(c,NUL)标识符(i,字符串)无符号整常数(x,字符串)无符号实常数(y,字符串)运算符+(+,NUL)*(*,NUL)+($,NUL)=(=,NUL)界符,(,NUL);(;,NUL)(,NUL)(),NUL)#(#,NUL),2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例4.状态转换图对单字符单词可以不画状态转换图，多字符单词需要画出状态转换图,2.1 词法分析器的设计考虑及手工构造,词法分析器手工构造实例5.程序实现词法分析器由5个函数构成：主函数main预处理函数pro_process扫描函数scanner拼接函数concat查基本字表函数reserve,2.1 词法分析器的设计考虑及手工构造,主函数先调用预处理函数进行预处理，然后不断调用扫描函数，获得单词二元式编码，然后将输出到文件Lex_r.txt，直到源程序全部处理完成。,2.1 词法分析器的设计考虑及手工构造,void main()char buf4048=0;/扫描缓冲区pro_process(buf);/预处理coutbufendl;/显示bufofstream coutf(Lex_r.txt,ios:out);/单词识别code_val t;/临时变量dot=scanner(buf);/调用一次扫描器获得一个单词二元式 coutt.codett.valendl;/屏幕显示单词二元式 coutft.codett.valendl;/单词二元式输出至文件 while(t.code!=#);coutEnd of lexical analysis!endl;getch();,2.1 词法分析器的设计考虑及手工构造,扫描函数scanner中调用：拼接函数concat和查基本字表函数reserve,2.1 词法分析器的设计考虑及手工构造,上机练习请手工构造一个词法分析器，要求：1.从文件读入源程序2.去除源程序中的注释（注释用标记）3.用空格取代源程序中的Tab和换行符4.将预处理结果显示在屏幕上。5.源程序尾部需要添加字符。6.识别以下单词，并转换成二元式：基本字begin(a,NUL),end(b,NUL),integer(c,NUL),real(d,NUL)标识符(z,字符串)无符号整常数(x,字符串)无符号实常数(y,字符串)运算符+(+,NUL)*(*,NUL)+(,NUL)=(=,NUL)界符,(,NUL);(;,NUL)(,NUL)(),NUL)#(#,NUL),2.2正规式、自动机及词法分析器的自动生成,2.2.1 基本概念 有穷字母表设是一个有穷字母表，它的每个元素称为字符。即符号的非空有限集 例：=a，b，c符号：字母表中的元素 例：a，b，c符号串：符号的有穷序列 例：a,aa,ac,abc，.空字 空集,2.2正规式、自动机及词法分析器的自动生成,字（符号串）:上字符所构成的有限序列。空字：不包含任何字符的字，*：上所有字的全体。空字属于*,2.2正规式、自动机及词法分析器的自动生成,符号串和符号串集合的运算1.符号串相等：若x、y是集合上的两个符号串，则xyiff（当且仅当）组成x的每一个符号和组成y的每一个符号依次相等。2.符号串的长度：x为符号串，其长度|x|等于组成该符号串的符号个数。例：xSTV，|x|=3,2.2正规式、自动机及词法分析器的自动生成,3.符号串的联接：若x、y是定义在是上的符号串，且xXY，yYX，则x和y的联接 xyXYYX也是上的符号串。注意：一般xyyx，而xx,2.2正规式、自动机及词法分析器的自动生成,符号串集合的乘积运算：令A、B为符号串集合，定义 AB xy|xA,yB,ac，ad，bc，bd 因为xxx，所以A=A=A,例：Aa,b,B=c,d,AB=？,2.2正规式、自动机及词法分析器的自动生成,5.符号串集合的幂运算：有符号串集合A，定义A0=A1=AA2=AAA3=AAAAnAn-1A=AAn-1，n0,2.2正规式、自动机及词法分析器的自动生成,6.符号串集合的闭包运算：设A是符号串集合，定义 A A1 A2 A3 An 称为集合A的正闭包。A*A0 A称为集合A的闭包。,例：A=x,y A？A*？,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A1 A2 A3,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A0 A1 A2 A3,2.2正规式、自动机及词法分析器的自动生成,为什么对符号、符号串、符号串集合以及它们的运算感兴趣？若A为某语言的基本字符集Aa,b,z,0,1,9,+,_/,(,),=B为单词集B=begin,end,if,then,else,for,则B A*。语言的句子是定义在B上的符号串。若令C为句子集合，则C B*,程序 C,2.2正规式、自动机及词法分析器的自动生成,2.2.2 正规式与正规集 正规式和正规集的定义：l和是上的正规式，相应的正规集为、。l 若a，则a是正规式，相应正规集为a。l若、为正规式，相应正规集分别记为L()和L()，则|是正规式，其相应正规集记为L(|)，且令L(|)=L()L(),2.2正规式、自动机及词法分析器的自动生成,l若、为正规式，相应正规集分别记为L()和L()，则(或)是正规式，其相应正规集记为L()，且令L()=L()L()。正规式自身的n次积是正规式，记为n，其相应正规集记为L(n)，显然L(n)=L()n。l 若为正规式，相应正规集记为L()，则*=0|1|2|n是正规式，规定0=，其相应正规集记为L(*)，且令L(*)=L()*。l*，可用园括号改变运算顺序。,2.2正规式、自动机及词法分析器的自动生成,正规式有3个运算符：|或，连接，*闭包。优先级依次为：*，|。连接可以省略。,2.2正规式、自动机及词法分析器的自动生成,为什么要定义所谓的正规集和正规式有穷字母表是程序设计语言所使用的字符集的抽象正规集是程序设计语言单词集的抽象正规式是程序设计语言构词规则的抽象词法分析器自动构造的输入正是描述单词的正规式Abcdefdog,godn:dog,god,2.2正规式、自动机及词法分析器的自动生成,正规式相等原理二个正规式是相等的，当且仅当二个正规式所表示的正规集是相等的。,2.2正规式、自动机及词法分析器的自动生成,正规式满足下列关系交换律：|=|结合律：|(|)=(|)|，()=()分配律：(|)=|，(|)=|=,2.2正规式、自动机及词法分析器的自动生成,正规式，其中=a|b|z,=0|1|9 1.(|)*2.*3.*.*.*.*(E|e)(+|-|).*.*(E|e)(+|-|).*(E|e)(+|-|).*4.(0|1)(0|1)*,标识符,无符号整常数,无符号实常数,二进制数,2.2正规式、自动机及词法分析器的自动生成,2.2.3 确定有限自动机（DFA）形式化状态转换图DFA定义一个确定有限自动机M是一个五元式M=(S，f，s0，Z)l S是一个有限集，它的每一个元素称为状态。l 是一个有穷字母表，它的每个元素称为一个输入字符。l f是一个从S至S的映照，即，f：SS（单值函数）,有限自动机：一种识别器，准确识别正规集，是词法分析器自动构造所需要的特殊方法和工具。,2.2正规式、自动机及词法分析器的自动生成,例f(si,a)=sj，表示当现行状态为si，若输入字符为a，则转移到下一状态sj，sj称为si的后继状态。l s0S，是唯一的一个初态。l ZS，是一个终态集。,2.2正规式、自动机及词法分析器的自动生成,状态转换矩阵函数f可以使用矩阵表示，行表示状态，列表示输入字符，矩阵元素表示下一个状态。只要对初态和终态做标记，就可以用一个状态转换矩阵来表示DFA,2.2正规式、自动机及词法分析器的自动生成,DFA M也可用一个（确定的）状态转换图表示假定DFA M含有m个状态和n个输入字符，那这个图含有m个状态结，每个状态结最多有n条箭弧射出和其他状态相连接，包括该状态本身。每条弧用中的一个不同输入字符做标记，整个图含有唯一一个初态和若干个终态。,2.2正规式、自动机及词法分析器的自动生成,字可为DFA M识别对于一个字，如果存在一条从初态结到某一终态结的路径，且路径上的所有弧的标记按照顺序连接成的字为，则称可为DFA M识别或接受。若DFA M的初态结同时又是终态结，则称空字可为DFA M所识别或接受。DFA M所识别的字的全体称为L（M）,2.2正规式、自动机及词法分析器的自动生成,DFA的确定性表现在映射SS是一个单值函数。即对任何状态 sS和输入符号a，f(s,a)唯一确定下一个状态。从状态转换图来看，假定字母表含有n个输入字符，那么一个状态最多只有n条弧射出，并且每条弧以不同的输入字符为标记。,2.2正规式、自动机及词法分析器的自动生成,2.2.4 非确定有限自动机（NFA）f是一个多值函数，得到NFA定义一个非确定的有限自动机M是一个五元式M=（S，f，S0，Z）lS是一个有限集，它的每一个元素称为状态。l是一个有穷字母表，它的每个元素称为一个输入字符。,2.2正规式、自动机及词法分析器的自动生成,l f是一个从S*到S的子集影射，即，f：S*2S（多值函数）2S表示幂集，若S=0，1，则2S=，0，1，0，1。l S0S，是一个非空初态集，即NFA的初态不一定唯一。lZS，是一个终态集。,2.2正规式、自动机及词法分析器的自动生成,NFA M可用一个（非确定的）状态转换图表示一个含有m个状态和n个输入字符的NFA可唯一表示成一个（非确定的）状态转换图，这个图含有m个状态结，每个结可射出若干个箭弧与别的结相连接，每条弧用*中的一个字做标记（输入字），不一定要不同的字，还可以是空字。一个DFA可以含有多个初态结，初态结同时也可以是终态结。,2.2正规式、自动机及词法分析器的自动生成,字可为NFA M识别对于*中一个字，如果NFA M中存在一条从某一初态到某一终态的路径，且路径上的所有弧的标记按照顺序连接成的字为，则称可为NFA M识别或接受。若M的某些结既是初态结同时又是终态结，或者存在一条从某个初态结到某个终态结的道路，则称空字可为M所识别或接受。NFA M所识别的字的全体称为L（M）,2.2正规式、自动机及词法分析器的自动生成,DFA是NFA的特例对于任何两个有限自动机M和M，如果L（M）=L（M），那么称两个有限自动机M和M等价。对于每个NFA M存在一个DFA M，使得L（M）=L（M）,2.2正规式、自动机及词法分析器的自动生成,2.2.5 NFA的确定化设I是NFAM状态集的一个子集，定义状态集-CLOSURE（I）为：（1）若状态s I,则s-CLOSURE（I）（2）若状态s I,则从状态s出发，经一条或多条弧所能到达的状态s也属于-CLOSURE（I）-CLOSURE（I）称为I的闭包。,2.2正规式、自动机及词法分析器的自动生成,NFADFAI的闭包IaNFA确定化算法,2.2正规式、自动机及词法分析器的自动生成,2.2.6 正规式的NFA表示把正规式表示成转换图的形式，然后通过加新结的方法对分裂，直到每条弧的标记为上的一个字符或。VNFA将V表示成拓广NFA根据三条规则对V进行分裂，直至每条弧上的标记为上的一个字符或。,2.2正规式、自动机及词法分析器的自动生成,2.2.7正规式与确定有限自动机的等价性对于上的每个正规式V，存在一个上的确定有限自动机M，便得L(V)=L(M)。,2.3词法分析器的自动生成,输入正规式（构词规则），经自动生成器加工，其结果为DFA。,2.3词法分析器的自动生成,2.3词法分析器的自动生成,自动生成过程概述构造描述每个单词的正规式Pi(1iN)。根据正规式Pi构造NFA Mi(1iN)，假定初态均为0。在构造NFA Mi的同时，逐步并且最终形成识别全部单词的NFA M。NFA M确定化重新标记，构造DFA M。,2.3词法分析器的自动生成,利用上述原理，构造一个识别简单程序设计语言单词的DFA。,2.3词法分析器的自动生成,扫描器控制程序工作原理扫描器控制程序的实现,上机练习,