《编译原理》第三章词法分析

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 词法分析,第三章 词法分析,主要章节,3.1 词法分析与词法分析程序,3.2,词法分析程序的设计与实现,3.3,词法分析程序的自动生成,3.1,词法分析程序的功能,词法分析的,功能,从左至右逐个字符地对源程序进行扫描，产生一个个单词,符号，再转换成词标流的过程,3,词法分析器,源程序,单词序列,4,while,(i=j),if,(ij)ii-j;,else,j=j-i,while,，,(,，,i,，,=,，,j,，,),，,if,，,(,，,i,，,，,j,),i,=,i,-,j ,;,，,else,j ,=,j,-,i,;,词法分析器,3.1,词法分析程序的功能,3.2,词法分析器的设计与实现,3.2.1,单词与属性字,1.,单词,单词是语言中具有独立意义的最小语法单位。,要素,独立的意义,最小的语法单位,5,例,A*B,，单词是“,A”,、“*”和“,B”,。,int int1,单词是“,int”,和“,int1”,。,A+*B,单词是“,A”,、“,+”,、“*”和“,B”,。,复习,流行语言词法规则的表示：,BNF,或,EBNF,；,3,型文法；,正规式,例,-int|float|for|#include|char|,-|,V=,（,|,）*,6,1关键字(保留字或基本字),：,关键字一般是语言系统本身定义的,通常是由字母组成的字符串。,7,2标识符：用来表示各种名字,如,变量名,数组名,结构名,函数名,文件名等。,3.2.1,单词与属性字,3常数：256，3.14，,true,abc,4运算符：如，、*、/等等,5分界符：如逗号,分号,括号,单双引号等,8,3.2.1,单词与属性字,3.2.1,单词与属性字,注意：,(1),同一个字符开头,+,后续字符,-,跨多个单词类；,9,(2),非单词成分和预处理成分；,例,:,源程序注释；,/*.*/,预处理指令：,#define#include,3.2.1,单词与属性字,2.,属性字,对所识别的单词的数据结构表示。,L1=,（,T,，,C,）,属性字,10,刻画单词类别（单词性质）,如,:,标识符；运算符；,单词的内码值（可空）,Token Code,说明,11,单词类别,通常用整数编码,单词类别,提供给语法分析程序使用,单词符号属性信息记录单词符号的特征或特性,单词的属性值提供给语义分析程序使用,编码形式：,一类一种：,关键字、标识符、常数、运算符、界符,一字一种：关键字、运算符、分界符各一码,例题,（一类一种）,int x=10,，,y,；,12,单词类别,单词属性值,1,int,2,指向,x,的符号表入口指针,4,=,3,10,5,，,2,指向,y,的符号表入口指针,5,；,注：通常将标识符的属性放在符号表中，因此常把指向存放标识符有关信息的符号表入口的指针作为标识符的属性值,13,源程序经词法分析器的输出,while，,id，,指向,i,的符号表入口的指针,relationalop ，,id，,指向,j,的符号表入口的指针,do，,if，,id，,指向,i,的符号表入口的指针,id，,指向,j,的符号表入口的指针,while,，,i,，,，,j,，,do,，,if,，,i,，,，,j,then,i,:=,i,-,j ,else,j ,:=,j,-,i,例题,（一字一种）,3.2.2,源程序的输入与预处理,1,输入缓冲区,成对且对半互补的输入缓冲区模式。即将一个缓冲区分为两个半区,每个半区长度为,n(n,一般为磁盘块或簇长的整倍数,),其结构如图所示。,14,n:,取,2,的整次幂；,每个半区的末尾设置标志“,eof”,表示读入该半区的源程序的结束；,B,：单词,w,开始指针；,F,：扫描,w,的指针；,两半区互补功能算法：,if (F=,前“,eof”),重新分配、装入后半区,;F+,；,else if (F=,后“,eof”),重新分配、装入前半区；,F=1,；,else F+;,15,2,两个缓冲区的输入模式,控制线 数据线,X:,固定长度的存储空间,;,16,预处理程序（作用）,(1),减少内存空间占用；,(2),减轻扫描器实质性处理的负担；,预处理程序主要任务：,(1),滤掉源程序中的非单词成分,(,如无用空格；换行符等,),；,(2),实际的预处理工作,17,滤掉注释；,宏替换；,文件包含的嵌入；,条件编译的嵌入；,设计工具,FA,作为扫描器的状态转换图的构造：,step1:,对语言的各类单词分别构造状态图；,step2:,将各类状态图,合并,，构成一个能识别该语言所有单词的状态图。,18,(1),将各类单词的状态图的初态合并为一个惟一初态；,(2),调整冲突编号。,例,3.2,设某语言由标识符和无符号正整数两类单词构成，标识符和无符号正整数的词法规则：,L a|b|z|A|B|Z,D 0|1|9,L(L|D|_)*,DD*,19,step1:,对语言的各类单词分别构造状态图；,20,2,L,L|D|_,1,3,other,1,D,D,0,2,other,其中：,other,表示非,L|D|_,字符,其中：,other,表示非,D,字符,step1,*,*,step2:,将各类状态图,合并,，构成一个能识别该语言所有单词的状态图。,21,2,L,L|D|_,1,3,other,1,D,D,0,2,other,其中：,other,表示非,L|D|_,字符,其中：,other,表示非,D,字符,step2,*,*,4,5,词法分析方法：直接分析法,例：设,C,语言子集由下列单词符号构成，以正规式的形式表示：,关键字：,int,if,for,标识符：字母,(,字母,|,数字,)*,无符号整常数：数字,(,数字,)*,运算符或分界符：,=,*,+,，,+,，,+=,，,，,22,23,24,25,26,语言词法规则,状态转换图,(FA),可行的扫描器,存储和激活问题,数据中心法,程序中心法,状态转换图的实现之一,数据中心法,将状态转换图看成一种数据结构,(,状态矩阵表,),，用总控程序控制输入的源程序串在其上运行。,27,状态矩阵 二级目录表,主表：,数据项,=,状态,+,分表地址或子程序入口,状态,=,终态时，分表地址为子程序入口,状态,=,非终态时，为分表入口,2.,分表：,数据项,=,当前输入字符,+,转换状态,主表 分表,28,状态转换图的实现之二,程序中心法,将状态转换图看成一个流程图，从初态开始对它的每个节点（状态）编写一函数或直接跟踪状态图从初态开始的转换完成所有分支的跟踪来编写程序。,例,3.5,设单一小写字母或单一数字或“,/”,为合法单词，表示它们的状态转换图如图所示。,29,char char1;,char1=nextchar();,if (state=i),switch(char1),case az:J(chartype,char1);break;,case 09:K(chartype,char1);break;,case,:L(chartype,char1);break;,default:error;,其中：,J,，,K,，,L,为状态,j,，,k,，,l,所对应的函数；,nextchar(),为一函数，功能是从当前扫描的源程序读取下一个字符；,状态转换图的实现,int state=0;,enum lettet(a.z);,enum number(0.9);,char char1;,while(1),char1=nextchar();,switch(state),case 0:switch(char1),case az:state=1;break;,09:state=3;break;,case case =:state=5;break;,case *:state=6;break;,case +:state=7;break;,case :state=11;break;,case :state=12;break;,default :state=13;,break;,31,状态转换图的实现,case 1:while(char1=letter|number),char1=nextchar();,state=2;break;,case 2:untread();return(02,value)or return(01,value);break;,/*,函数,untread(),功能是回退一个已读进的字符；,属性,01,表示关键字；属性,02,表示标识符*,/,case 3:while(char1=number)char1=nextchar();,state=4;break;,case 4:untread();return(03,value);break;,/*,属性,03,表示无符号整常数*,/,case 5:return(04,);break;,/*,属性,04,表示“”*,/,case 6:return(05,);break;,/*,属性,05,表示“*”*,/,32,状态转换图的实现,case 7:char1=nextchar();,if(char1=+)state=9;,else if(char1=”=”)state=10;,else state=8;break;,case 8:untread();return(08,);break;/*,属性,08,表示“,+”*/,case 9:return(09,);break;/*,属性,09,表示“,+”*/,case 10:return(12,);break;/*,属性,12,表示“,+=”*/,case 11:return(10,);break;/*,属性,10,表示“,”*/,case 12:return(11,);break;/*,属性,11,表示“,”*/,case 13:error;/*error,是语法错处理函数*,/,33,一,.,自动生成思想,一个词法分析程序产生器它接收用正规式表示的定义在某语言字母表,上的单词,然后从此正规式出发,(1),构造能识别正规式描述的单词集,(,正规集,),的非确定有限自动机,NFA M,此步构造算法定义为,X,。,(2),用子集法,(,子集法实现算法命名为,Y),将,M,确定化,得到与其等价的,DFA M,；,(3),用划分算法,(,命名为,Z),对,M,化简,得到,DFA M,。则这个,DFA M,即是理论上的扫描器。,34,LEX,运行与应用过程,35,二,、,用,LEX,建立词法分析程序的过程,LEX,编译器,LEX,源程序,lex,.,1,C,编译器,Lex.yy.c,a.out,语言,x,的词法分析器,LEX,编译器接收,LEX,源程序，由,LEX,编译器处理,LEX,源程序，产生一个词法分析器作为输出。在,UNIX,环境中，,LEX,编译器的输出是一个具有标准文件,lex.yy.c,的,C,程序，经过,C,编译器的编译产生,a.out,文件，,a.out,是一个实际可以运行的词法分析器。,练习,例,:,设有识别,C,语言“,+”“”“+=”,的,NFA,如下,36,1,+,0,2,+,3,4,+,6,+,5,7,=,连接成一个,NFA,例,:,设有识别,C,语言“,+”“”“+=”,的,NFA,如下,37,1,+,0,2,+,4,+,6,+,7,=,+,=,0,1 4 6,-,1 4 6,2,7,2,-,-,7,-,-,0,1,2,3,*,*,*,+,=,0,1,-,1,2,3,2,-,-,3,-,-,*,*,*,