the 词法分析第二章形式语言与自动机理论基础guide download

第1页Ch3词法分析3.1词法分析程序的功能词法分析器(Scanner)属性字流L1源程序ƒ词法分析程序的功能从左至右地对源程序进行，按照语言的词法规则识别各类单词，并产生相应单词的属性字。第2页Ch3词法分析3.1词法分析程序的功能ƒ关于词法分析程序*组织输入、扫描、分析、输出；*接收字符串形式的源程序，按照源程序输入的次序依次扫描源程序，在扫描的同时根据语言的词法规则识别出具有独立意义的单词，并产生与源程序等价的属性字（Token）流.完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器。第3页Ch3词法分析3.1词法分析程序的功能ƒ关于词法分析程序（作为一个独立子程序）(1)只要不修改接口，则词法分析器所作的修改不会影响整个编译器，且词法分析器易于维护；(2)整个编译器结构简捷、清晰；(3)可以采用有效的方法和工具进行处理。完全独立相对独立协同程序第4页Ch3词法分析3.1词法分析程序的功能例3.1有如下C源程序片段{intint1;int1=33;printf(int1=%d\n,int1);}词法分析后识别出如下单词：{、int、int1、;、int1、=、33、;、printf、(、int1＝%d\n”、,、int1、)、;、}第5页Ch3词法分析3.1词法分析程序的功能x说明：1.词法分析是编译程序的第一个阶段且是必要阶段；2.词法分析的核心任务是扫描、识别单词且对识别出的单词给出定性、定长的处理；3.实现词法分析程序的常用途径：自动生成手工生成第6页Ch3词法分析3.2词法分析器的设计与实现3.2.1单词与属性字1.单词单词是语言中具有独立意义的昀小语法单位。例如，…A*B…，单词是“A”、“*”和“B”。要素独立的意义昀小的语法单位*词法规则制约…intint1…,单词是“int”和“int1”。…A++*B…,单词是“A”、“++”、“*”和“B”。第7页Ch3词法分析3.2词法分析器的设计与实现3.2.1单词与属性字ƒ流行语言词法规则的表示：BNF或EBNF；3型文法；正规式关键字pint|float|for|#include|char|…标识符p字母{字母|数字}V=字母（字母|数字）*标识符pa后缀|b后缀|…|z后缀后缀pa后缀|b后缀|…|z后缀|0后缀|1后缀|…|9后缀第8页常用的程序设计语言的单词类：（1）关键字(亦称保留字,基本字等)关键字一般是语言系统本身定义的,通常是由字母组成的字符串。例如:C语言中的int,for,break,static,char,switch,unsigned等,关键字一般关联到语句的性质。（2）标识符用来表示各类名字的标识。如,变量名,数组名,结构名,函数名,文件名等。Ch3词法分析3.2词法分析器的设计与实现3.2.1单词与属性字第9页（3）常量语言中各种类型的常数。如整型常数,实型常数,不同进制的常数,布尔常数,字符及字符串常数等。I常数：-26，19，0x123，037…R常数：-1.6，2e-6，2.5e06，…B常数：TRUE，FALSE，0或非0，…C、String:'$'，'$123'，“abc”，……Ch3词法分析3.2词法分析器的设计与实现3.2.1单词与属性字第10页（4）运算符表示程序中算术运算,逻辑运算,字符及位串等运算的确定字符(或串)。（5）界限符如逗号,分号,括号,单双引号等。Ch3词法分析3.2词法分析器的设计与实现3.2.1单词与属性字例如，各类语言较通用的＋,－,*,/,**,＜＝,＞＝,＜,＞等。还有一些语言特有的运算符，如C语言中的++,?:,&,％＝等。FORTRAN语言中的.AND.,.NOT.,.OR.。第11页Ch3词法分析3.2词法分析器的设计与实现3.2.1单词与属性字2.属性字对所识别的单词的数据结构表示。L1=（T，C）属性字TokenCode刻画单词类别（单词性质）例如，标识符；运算符；…单词的内码值（可空）第12页Ch3词法分析3.2词法分析器的设计与实现3.2.1单词与属性字互锁015标常构过保运实界IRBC形识造程留算参限参符量类字符符型例3.2:字长m=16的单词类别的设计。考虑类PASCAL语言，允许含隐式类型说明。第13页Ch3词法分析3.2词法分析器的设计与实现3.2.1单词与属性字设有变量realx,a;integerb;对语句x=a+b;词法分析结果：0400==m=00000100000000008040aam=10000000010000000400++m=00000100000000008080bbm=10000000100000000100;;m=0000000100000000L18040xxm=1000000001000000TokenCode第14页z注意：关于属性字单词类别部分设计：单词如何分类？分为几类？怎样编码？单词类别部分包含多少信息？Ch3词法分析3.2词法分析器的设计与实现3.2.1单词与属性字视具体情况而定。考虑后续处理方便。第15页Ch3词法分析3.2词法分析器的设计与实现3.2.1单词与属性字常见类单词的属性字设计：1.标识符标识符类码point符号表…sum2.关键字语言的关键字个数一般是固定的，考虑每个关键字对应一个属性类别码，内码值部分为空。第16页Ch3词法分析3.2词法分析器的设计与实现3.2.1单词与属性字3.常量常量类码point常量表…2.16按类型设置(考虑类型相容优先级)4.运算符和界限符(1)按照一个符号分别对应一个属性类别码，内码值部分为空。(2)运算符可以考虑优先级相同的对应一个属性类别码。优先级高的类别编码值大。第17页31+31–32*32/10…:?例如Ch3词法分析3.2词法分析器的设计与实现3.2.1单词与属性字第18页Ch3词法分析3.2词法分析器的设计与实现3.2.2源程序的输入与预处理1．输入缓冲区成对且对半互补的输入缓冲区模式。即将一个缓冲区分为两个半区,每个半区长度为n(n一般为磁盘块或簇长的整倍数),其结构如图所示。nn+1yyBF……i++;j++;…switch(a)前半区(firsthalf)后半区(secondhalf)12n第19页Ch3词法分析3.2词法分析器的设计与实现3.2.2源程序的输入与预处理ƒn:取2的整次幂；ƒ每个半区的末尾设置标志“eof”表示读入的源程序的结束；ƒB：单词w开始指针；F：扫描w的指针；ƒ两半区互补功能算法：if(F=“eof”){重新分配、装入后半区；F++}；elseif(F=“eof”){重新分配、装入前半区；F=1}；elseF++;第20页Ch3词法分析3.2词法分析器的设计与实现3.2.2源程序的输入与预处理2．两个缓冲区的输入模式X:固定长度的存储空间;输入缓冲区X1输入源程序L输入缓冲区X扫描器预处理子程序控制线数据线L1第21页Ch3词法分析3.2词法分析器的设计与实现3.2.2源程序的输入与预处理预处理程序：（作用）(1)减少内存空间占用；(2)减轻扫描器实质性处理的负担；预处理程序主要任务：(1)滤掉源程序中的非单词成分(如无用空格；换行符等)；滤掉注释；宏替换；文件包含的嵌入；条件编译的嵌入；(2)实际的预处理工作第22页Ch3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现ƒ设计工具——FA作为扫描器的状态转换图的构造：step1:对语言的各类单词分别构造状态图；step2:将各类状态图合并，构成一个能识别该语言所有单词的状态图。(1)将各类单词的状态图的初态合并为一个惟一初态；(2)调整冲突编号。第23页例3.3设某语言由标识符和无符号正整数两类单词构成，并设L表示字母，D表示十进制数字，则有标识符和无符号正整数的词法规则：标识符→L(L|D|_)*无符号正整数→DD*其中：other表示非L|D|_字符3L|D|_*12otherL02Dother1D*D其中other表示非D的字符Ch3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现第24页3L|D|_*12otherL02Dother1D*DCh3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现第25页Ch3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现2Dother1D*DL|D|_*12otherL3合并为一个识别该语言所有单词的NFA调整冲突编号第26页3L|D|_*12otherL5Dother4D*DCh3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现词法分析方法：直接分析法第27页例3.4设C语言子集由下列单词符号构成，以正规式的形式表示：关键字：int,if,for标识符：字母(字母|数字)*无符号整常数：数字(数字)*运算符或分界符：=,*,+，++，+=，{，}讲义P55——例3.3Ch3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现第28页Ch3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现ƒ状态转换图的实现之一——数据中心法将状态转换图看成一种数据结构(状态矩阵表)，用总控程序控制输入的源程序串在其上运行。据语言词法规则状态转换图可行的扫描器存储和激活问题数据中心法程序中心法第29页Ch3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现ƒ状态矩阵问题二级目录表1.主表：数据项=状态+分表地址或子程序入口状态=终态时，分表地址为子程序入口状态≠终态时，为分表入口2.分表：数据项=当前输入字符+转换状态第30页Ch3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现主表状态分表地址0（1）1（（2）2*（标识符保留字）/34*子(整常数)5*子(=)6*7(4)8*9*10*11*12*13*Error（3）子(+)子(*)子(++)子(,)子({)子(})第31页Ch3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现分表(2)输入字符转换状态字母1数字1Other2*分表(3)输入字符转换状态数字3Other4*分表(4)+9*=10*输入字符转换状态Other8*分表(1)输入字符转换状态字母1数字3=5**6*+7{11}12Other13第32页Ch3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现ƒ算法3.1(总控算法—二级目录表)：输入：字符串形式的源程序流；输出：源程序单词的属性字流；算法：/*B—状态寄存器；W—字符寄存器；W’—字符串寄存器；*/(1)B=初态;W’=‘’;(2)当前读入字符W;(3)据B查主表子程序入口，转(4)；分表地址，转(5)；(4)终态处理：输出单词(W’)属性字，goto(1);(5)据W查分表，将W对应的状态B，(B)是终态？是，则转(3)；不是，组合单词W’=W’+W，转(2)。第33页Ch3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现ƒ状态转换图的实现之二——程序中心法将状态转换图看成一个流程图，从初态开始对它的每个节点（状态）编写一函数或直接跟踪状态图从初态开始的转换完成所有分支的跟踪来编写程序。a..z0..9/ijkl例3.5设单一小写字母或单一数字或“/”为合法单词，表示它们的状态转换图如图所示。第34页Ch3词法分析3.2词法分析器的设计与实现3.2.3扫描器设计与实现charchar1;｛char1=nextchar();if(state=i)switch(char1)｛case‘a’…‘z’:J(chartype,char1);break;case‘0’…‘9’:K(chartype,char1);break;case‘／’:L(chartype,char1);break;default:error;｝｝其中：J，K，L为状态j，k，l所对应的函数；nextchar()为一函数，功能是从当前扫描的源程序读取下一个字符；