《编译原理》第三章词法分析.ppt
第三章 词法分析第三章 词法分析n主要章节主要章节l3.1 词法分析与词法分析程序l3.2 词法分析程序的设计与实现l3.3 词法分析程序的自动生成3.1 词法分析程序的功能词法分析程序的功能n词法分析的词法分析的功能功能l从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，再转换成词标流的过程z3词法分析器源程序源程序 单词序列单词序列 z4while (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 词法分析器的设计与实现词法分析器的设计与实现n3.2.1 单词与属性字单词与属性字n1.单词单词n单词是语言中具有独立意义的最小语法单位。l要素 l独立的意义l最小的语法单位z5n例lA*B，单词是“A”、“*”和“B”。lint int1,单词是“int”和“int1”。lA+*B,单词是“A”、“+”、“*”和“B”。复习n流行语言词法规则的表示：流行语言词法规则的表示：lBNF或EBNF；l3型文法；l正规式n例例l-int|float|for|#include|char|l-|lV=（|）*z6n 1关键字(保留字或基本字)：l关键字一般是语言系统本身定义的,通常是由字母组成的字符串。z7n2标识符：用来表示各种名字l如,变量名,数组名,结构名,函数名,文件名等。3.2.1 单词与属性字n 3常数：256，3.14，true,abcn 4运算符：如，、*、/等等n 5分界符：如逗号,分号,括号,单双引号等z83.2.1 单词与属性字3.2.1 单词与属性字n注意：注意：l(1)同一个字符开头+后续字符-跨多个单词类；z9l(2)非单词成分和预处理成分；例:源程序注释；/*.*/l预处理指令：#define#include3.2.1 单词与属性字l2.属性字l对所识别的单词的数据结构表示。L1=L1=（T T，C C）属性字属性字z10刻画单词类别（单词性质）刻画单词类别（单词性质）如如:标识符；运算符；标识符；运算符；单词的内码值（可空）单词的内码值（可空）Token Code Token Code 说明z11l单词类别通常用整数编码l单词类别提供给语法分析程序使用l单词符号属性信息记录单词符号的特征或特性l单词的属性值提供给语义分析程序使用l编码形式：l一类一种：关键字、标识符、常数、运算符、界符l一字一种：关键字、运算符、分界符各一码例题例题（一类一种）（一类一种）nint x=10，y；z12 单词类别单词类别 单词属性值单词属性值1int2指向x的符号表入口指针4=3105，2指向y的符号表入口指针5；注：通常将标识符的属性放在符号表中，因此常把指向存放标识符有关信息的符号表入口的指针作为标识符的属性值z13源程序经词法分析器的输出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 3.2.2 源程序的输入与预处理源程序的输入与预处理n1输入缓冲区输入缓冲区l成对且对半互补的输入缓冲区模式。即将一个缓冲区分为两个半区,每个半区长度为n(n一般为磁盘块或簇长的整倍数),其结构如图所示。z14ln:取2的整次幂；l每个半区的末尾设置标志“eof”表示读入该半区的源程序的结束；lB：单词w开始指针；l F：扫描w的指针；n两半区互补功能算法：两半区互补功能算法：lif (F=前“eof”)重新分配、装入后半区;F+；lelse if (F=后“eof”)l 重新分配、装入前半区；F=1；lelse F+;z152两个缓冲区的输入模式n 控制线 数据线nX:固定长度的存储空间;z16n预处理程序（作用）预处理程序（作用）l(1)减少内存空间占用；l(2)减轻扫描器实质性处理的负担；n预处理程序主要任务：预处理程序主要任务：l(1)滤掉源程序中的非单词成分(如无用空格；换行符等)；l(2)实际的预处理工作z17滤掉注释；宏替换；文件包含的嵌入；条件编译的嵌入；n 设计工具设计工具 FAl作为扫描器的状态转换图的构造：lstep1:对语言的各类单词分别构造状态图；lstep2:将各类状态图合并合并，构成一个能识别该语言所有单词的状态图。z18(1)将各类单词的状态图的初态合并为一个惟一初态；(2)调整冲突编号。n例3.2 设某语言由标识符和无符号正整数两类单词构成，标识符和无符号正整数的词法规则：lL a|b|z|A|B|ZlD 0|1|9l L(L|D|_)*l DD*z19step1:对语言的各类单词分别构造状态图；z202LL|D|_13other1DD02other其中：other表示非L|D|_字符其中：other表示非D 字符step1*step2:将各类状态图合并合并，构成一个能识别该语言所有单词的状态图。z212LL|D|_13other1DD02other其中：other表示非L|D|_字符其中：other表示非D 字符step2*45词法分析方法：直接分析法n例：设C语言子集由下列单词符号构成，以正规式的形式表示：l关键字：int,if,forl标识符：字母(字母|数字)*l无符号整常数：数字(数字)*l运算符或分界符：=,*,+，+，+=，z22z23z24z25z26语言词法规则 状态转换图(FA)可行的扫描器 存储和激活问题数据中心法程序中心法n状态转换图的实现之一状态转换图的实现之一 数据中心法数据中心法l将状态转换图看成一种数据结构(状态矩阵表)，用总控程序控制输入的源程序串在其上运行。z27状态矩阵 二级目录表1.主表：主表：数据项=状态+分表地址或子程序入口 状态状态=终态时，分表地址为子程序入口终态时，分表地址为子程序入口 状态状态=非终态时，为分表入口非终态时，为分表入口2.分表：分表：数据项=当前输入字符+转换状态n主表 分表z28状态转换图的实现之二状态转换图的实现之二 程序中心法程序中心法n将状态转换图看成一个流程图，从初态开始对它的每个节点（状态）编写一函数或直接跟踪状态图从初态开始的转换完成所有分支的跟踪来编写程序。n例3.5 设单一小写字母或单一数字或“/”为合法单词，表示它们的状态转换图如图所示。z29nchar char1;n char1=nextchar();n if (state=i)n switch(char1)n l case az:J(chartype,char1);break;l case 09:K(chartype,char1);break;l case:L(chartype,char1);break;l default:error;n n其中：lJ，K，L为状态j，k，l所对应的函数；lnextchar()为一函数，功能是从当前扫描的源程序读取下一个字符；状态转换图的实现lint state=0;lenum lettet(a.z);lenum number(0.9);lchar char1;lwhile(1)l char1=nextchar();l switch(state)l case 0:switch(char1)l l case az:state=1;break;l 09:state=3;break;l case case =:state=5;break;l case *:state=6;break;l case +:state=7;break;l case :state=11;break;l case :state=12;break;l default :state=13;l break;z31状态转换图的实现lcase 1:while(char1=letter|number)l char1=nextchar();l state=2;break;lcase 2:untread();return(02,value)or return(01,value);break;l /*函数untread()功能是回退一个已读进的字符；l 属性01表示关键字；属性02表示标识符*/lcase 3:while(char1=number)char1=nextchar();l state=4;break;lcase 4:untread();return(03,value);break;l /*属性03表示无符号整常数*/lcase 5:return(04,);break;l /*属性04表示“”*/lcase 6:return(05,);break;l /*属性05表示“*”*/z32状态转换图的实现lcase 7:char1=nextchar();l if(char1=+)state=9;l else if(char1=”=”)state=10;l else state=8;break;lcase 8:untread();return(08,);break;/*属性08表示“+”*/lcase 9:return(09,);break;/*属性09表示“+”*/lcase 10:return(12,);break;/*属性12表示“+=”*/lcase 11:return(10,);break;/*属性10表示“”*/lcase 12:return(11,);break;/*属性11表示“”*/lcase 13:error;/*error 是语法错处理函数*/llz33一一 .自动生成思想自动生成思想n一个词法分析程序产生器它接收用正规式表示的定义在某语言字母表上的单词,然后从此正规式出发l(1)构造能识别正规式描述的单词集(正规集)的非确定有限自动机NFA M,此步构造算法定义为X。l(2)用子集法(子集法实现算法命名为Y)将M确定化,得到与其等价的DFA M；l(3)用划分算法(命名为Z)对M 化简,得到DFA M。则这个DFA M即是理论上的扫描器。z34LEX运行与应用过程z35二、用LEX建立词法分析程序的过程LEX编译器LEX源程序lex.1C编译器Lex.yy.ca.out语言x的词法分析器nLEX编译器接收LEX源程序，由LEX编译器处理LEX源程序，产生一个词法分析器作为输出。在UNIX环境中，LEX编译器的输出是一个具有标准文件lex.yy.c的C程序，经过C编译器的编译产生a.out文件，a.out是一个实际可以运行的词法分析器。练习n例:设有识别C语言“+”“”“+=”的NFA如下z361+02+34+6+57=连接成一个连接成一个NFA例:设有识别C语言“+”“”“+=”的NFA如下z371+02+4+6+7=+=01 4 6-1 4 6272-7-0123*+=01-1232-3-*
