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

《the 词法分析第二章形式语言与自动机理论基础guide dow.pdf》由会员分享，可在线阅读，更多相关《the 词法分析第二章形式语言与自动机理论基础guide dow.pdf（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第 1 页页Ch3 词法分析词法分析3.1 词法分析程序的功能词法分析程序的功能词法分析器词法分析器(Scanner)属性字流 L1属性字流 L1源程序源程序?词法分析程序的功能词法分析程序的功能从左至右地对源程序进行，按照语言的词法规则从左至右地对源程序进行，按照语言的词法规则识别各类单词，并产生相应单词的属性字。识别各类单词，并产生相应单词的属性字。第第 2 页页Ch3 词法分析词法分析3.1 词法分析程序的功能词法分析程序的功能?关于词法分析程序关于词法分析程序*组织输入、扫描、分析、输出；组织输入、扫描、分析、输出；*接收字符串形式的源程序，按照源程序输入的次接收字符串形式的源程序，

2、按照源程序输入的次序依次扫描源程序，在扫描的同时根据语言的词法序依次扫描源程序，在扫描的同时根据语言的词法规则识别出具有独立意义的单词，并产生与源程序规则识别出具有独立意义的单词，并产生与源程序等价的属性字（等价的属性字（Token）流）流.完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器。完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器。第第 3 页页Ch3 词法分析词法分析3.1 词法分析程序的功能词法分析程序的功能?关于词法分析程序关于词法分析程序（作为一个独立子程序）（作为一个独立子程序）(1)只要不修改接口，则词法分析器所作的修改只要不修改接口，则词法分析器所作的

3、修改不会影响整个编译器，且词法分析器易于维护；不会影响整个编译器，且词法分析器易于维护；(2)整个编译器结构简捷、清晰；整个编译器结构简捷、清晰；(3)可以采用有效的方法和工具进行处理。可以采用有效的方法和工具进行处理。完全独立相对独立协同程序完全独立相对独立协同程序第第 4 页页Ch3 词法分析词法分析3.1 词法分析程序的功能词法分析程序的功能例例3.1有如下有如下C源程序片段源程序片段 int int1;int1=33;printf(int1=%dn,int1);词法分析后识别出如下单词：词法分析后识别出如下单词：、int、int1、;、int1、=、33、;、printf、(、int1

4、%dn”、,、int1、)、;、第第 5 页页Ch3 词法分析词法分析3.1 词法分析程序的功能词法分析程序的功能?说明：说明：1.词法分析是编译程序的第一个阶段且是必要阶段；词法分析是编译程序的第一个阶段且是必要阶段；2.词法分析的核心任务是扫描、识别单词且对识别词法分析的核心任务是扫描、识别单词且对识别出的单词给出定性、定长的处理；出的单词给出定性、定长的处理；3.实现词法分析程序的常用途径：自动生成手工生成实现词法分析程序的常用途径：自动生成手工生成第第 6 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.1 单词与属性字单词与属性字1.单词.单词

5、单词是语言中具有独立意义的最小语法单位。单词是语言中具有独立意义的最小语法单位。例如，例如，A*B，单词是，单词是“A”、“*”和和“B”。要素要素独立的意义最小的语法单位独立的意义最小的语法单位*词法规则制约词法规则制约int int1,单词是单词是“int”和和“int1”。A+*B,单词是,单词是“A”、“+”、“*”和和“B”。第第 7 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.1 单词与属性字单词与属性字?流行语言词法规则的表示：流行语言词法规则的表示：BNF或或EBNF；3型文法；正规式型文法；正规式?int|float|for|#in

6、clude|char|?|V=（|）*?a|b|z?a|b|z|0|1|9第第 8 页页常用的程序设计语言的单词类：常用的程序设计语言的单词类：（1）关键字）关键字(亦称保留字,基本字等)(亦称保留字,基本字等)关键字一般是语言系统本身定义的,通常是由字母关键字一般是语言系统本身定义的,通常是由字母组成的字符串。组成的字符串。例如:例如:C语言中的语言中的 int,for,break,static,char,switch,unsigned等,关键字一般关联到语句的性质。等,关键字一般关联到语句的性质。（2）标识符）标识符用来表示各类名字的标识。如,变量名,数组用来表示各类名字的标识。如,变量名

7、,数组名,结构名,函数名,文件名等。名,结构名,函数名,文件名等。Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.1 单词与属性字单词与属性字第第 9 页页（3）常量）常量语言中各种类型的常数。如整型常数,实型常数语言中各种类型的常数。如整型常数,实型常数,不同进制的常数,布尔常数,字符及字符串常数等。,不同进制的常数,布尔常数,字符及字符串常数等。I常数：常数：-26，19，0 x123，037 R常数常数：-1.6，2e-6，2.5e06，B常数：常数：TRUE，FALSE，0或非或非0，C、String:$，$123 ，“abc”，Ch3 词法分析词法

8、分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.1 单词与属性字单词与属性字第第 10 页页（4）运算符）运算符表示程序中算术运算,逻辑运算,字符及位串等表示程序中算术运算,逻辑运算,字符及位串等运算的确定字符(或串)。运算的确定字符(或串)。（5）界限符）界限符如逗号,分号,括号,单双引号等。如逗号,分号,括号,单双引号等。Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.1 单词与属性字单词与属性字例如，例如，各类语言较通用的,*,/,*,等。还有一些语言特有的运算符，如各类语言较通用的,*,/,*,等。还有一些语言特有的运算符，如C语言中

9、的+,?:,语言中的+,?:,&,等。,等。FORTRAN 语言中的.语言中的.AND.,.,.NOT.,.,.OR.。第第 11 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.1 单词与属性字单词与属性字2.属性字.属性字对所识别的单词的数据结构表示。对所识别的单词的数据结构表示。L1=（T，C）属性字属性字Token Code 刻画单词类别（单词性质）例如，标识符；运算符；刻画单词类别（单词性质）例如，标识符；运算符；单词的内码值（可空）单词的内码值（可空）第第 12 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现

10、3.2.1 单词与属性字单词与属性字互锁互锁0 15标 常 构 过 保 运 实 界标 常 构 过 保 运 实 界 I R B C 形识造程 留 算 参限参符 量类字 符符型形识造程 留 算 参限参符 量类字 符符型例例3.2:字长字长m=16的单词类别的设计。的单词类别的设计。考虑类考虑类PASCAL语言，允许含隐式类型说明。语言，允许含隐式类型说明。第第 13 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.1 单词与属性字单词与属性字设有变量设有变量real x,a;integer b;对语句对语句 x=a+b;词法分析结果：词法分析结果：0400

11、=m=00000100000000008040 aam=10000000010000000400 +m=00000100000000008080 bbm=10000000100000000100 ;m=0000000100000000L18040 xxm=1000000001000000Token Code第第 14 页页?注意：注意：关于属性字单词类别部分设计：单词如何分关于属性字单词类别部分设计：单词如何分类？分为几类？怎样编码？单词类别部分包含类？分为几类？怎样编码？单词类别部分包含多少信息？多少信息？Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.1

12、 单词与属性字单词与属性字视具体情况而定。视具体情况而定。考虑后续处理方便。考虑后续处理方便。第第 15 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.1 单词与属性字单词与属性字常见类单词的属性字设计：常见类单词的属性字设计：1.标识符标识符标识符类码标识符类码point 符号表符号表sum2.关键字关键字语言的关键字个数一般是固定的，考虑每个关键语言的关键字个数一般是固定的，考虑每个关键字对应一个属性类别码，内码值部分为空。字对应一个属性类别码，内码值部分为空。第第 16 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与

13、实现3.2.1 单词与属性字单词与属性字3.常量常量常量类码常量类码point 常量表常量表2.16按类型设置按类型设置(考虑类型相容优先级考虑类型相容优先级)4.运算符和界限符运算符和界限符(1)按照一个符号分别对应一个属性类别码，内码按照一个符号分别对应一个属性类别码，内码值部分为空。值部分为空。(2)运算符可以考虑优先级相同的对应一个属性运算符可以考虑优先级相同的对应一个属性类别码。优先级高的类别编码值大。类别码。优先级高的类别编码值大。第第 17 页页31 +31 32 *32 /10:?例如例如Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.1 单

14、词与属性字单词与属性字第第 18 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.2 源程序的输入与预处理源程序的输入与预处理1输入缓冲区输入缓冲区成对且对半互补的输入缓冲区模式。即将一个成对且对半互补的输入缓冲区模式。即将一个缓冲区分为两个半区,每个半区长度为缓冲区分为两个半区,每个半区长度为n(n一般为一般为磁盘块或簇长的整倍数),其结构如图所示。磁盘块或簇长的整倍数),其结构如图所示。n n+1?B Fi+;j+;switch (a)前半区前半区(first half)后半区后半区(second half)12n第第 19 页页Ch3 词法分析词法

15、分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.2 源程序的输入与预处理源程序的输入与预处理?n:取取2的整次幂；的整次幂；?每个半区的末尾设置标志每个半区的末尾设置标志“eof”表示读入的源程表示读入的源程序的结束；序的结束；?B：单词单词w开始指针；开始指针；F：扫描扫描w的指针；的指针；?两半区互补功能算法：两半区互补功能算法：if (F=“eof”)重新分配、装入后半区；重新分配、装入后半区；F+；else if (F=“eof”)重新分配、装入前半区；重新分配、装入前半区；F=1；else F+;第第 20 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词

16、法分析器的设计与实现3.2.2 源程序的输入与预处理源程序的输入与预处理2两个缓冲区的输入模式两个缓冲区的输入模式X:固定长度的存储空间固定长度的存储空间;输入缓冲区输入缓冲区X1输入源程序输入源程序L输入缓冲区输入缓冲区X扫描器扫描器预处理子程序预处理子程序控制线数据线控制线数据线L1第第 21 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.2 源程序的输入与预处理源程序的输入与预处理预处理程序：预处理程序：（作用）（作用）(1)减少内存空间占用；减少内存空间占用；(2)减轻扫描器实质性处理的负担；减轻扫描器实质性处理的负担；预处理程序主要任务：预处

17、理程序主要任务：(1)滤掉源程序中的非单词成分滤掉源程序中的非单词成分(如无用空格；换如无用空格；换行符等行符等)；滤掉注释；宏替换；文件包含的嵌入；条件编译的嵌入；滤掉注释；宏替换；文件包含的嵌入；条件编译的嵌入；(2)实际的预处理工作实际的预处理工作第第 22 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.3 扫描器设计与实现扫描器设计与实现?设计工具设计工具 FA作为扫描器的状态转换图的构造：作为扫描器的状态转换图的构造：step1:对语言的各类单词分别构造状态图；对语言的各类单词分别构造状态图；step2:将各类状态图合并，构成一个能识别该语言

18、所有单词的状态图。将各类状态图合并，构成一个能识别该语言所有单词的状态图。(1)将各类单词的状态图的初态合并为一个惟一初态；将各类单词的状态图的初态合并为一个惟一初态；(2)调整冲突编号。调整冲突编号。第第 23 页页例例3.3设某语言由标识符和无符号正整数两类单设某语言由标识符和无符号正整数两类单词构成，并设词构成，并设L表示字母，表示字母，D表示十进制数字，则表示十进制数字，则有标识符和无符号正整数的词法规则：有标识符和无符号正整数的词法规则：L(L|D|_)|_)*DD*其中：其中：other表示非表示非L|D|_字符字符3L|D|_*12otherL02Dother1D*D其中其中ot

19、her表示非表示非 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调

20、整冲突编号调整冲突编号第第 26 页页3L|D|_*12otherL5Dother4D*DCh3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.3 扫描器设计与实现扫描器设计与实现词法分析方法：直接分析法词法分析方法：直接分析法第第 27 页页例例3.4设设C语言子集由下列单词符号构成，以正规语言子集由下列单词符号构成，以正规式的形式表示：式的形式表示：关键字：关键字：int,if,for标识符：标识符：字母(字母|数字)字母(字母|数字)*无符号整常数：无符号整常数：数字(数字)数字(数字)*运算符或分界符：运算符或分界符：=,*,+，+，+=，=,*,+，+，

21、+=，讲义讲义 P55 例例3.3Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.3 扫描器设计与实现扫描器设计与实现第第 28 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.3 扫描器设计与实现扫描器设计与实现?状态转换图的实现之一状态转换图的实现之一 数据中心法数据中心法将状态转换图看成一种数据结构将状态转换图看成一种数据结构(状态矩阵表状态矩阵表)，用总控程序控制输入的源程序串在其上运行。用总控程序控制输入的源程序串在其上运行。据语言词法规则据语言词法规则状态转换图状态转换图可行的扫描器可行的扫描器存储和激活问

22、题存储和激活问题数据中心法程序中心法数据中心法程序中心法第第 29 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.3 扫描器设计与实现扫描器设计与实现?状态矩阵问题二级目录表状态矩阵问题二级目录表1.主表：数据项主表：数据项=状态状态+分表地址或子程序入口分表地址或子程序入口状态状态=终态时，分表地址为子程序入口状态 终态时，为分表入口终态时，分表地址为子程序入口状态 终态时，为分表入口2.分表：数据项分表：数据项=当前输入字符当前输入字符+转换状态转换状态第第 30 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.

23、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

24、*输入字符转换状态输入字符转换状态Other8*分表分表(1)输入字符转换状态输入字符转换状态字母字母1数字数字3=5*6*+71112Other13第第 32 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.3 扫描器设计与实现扫描器设计与实现?算法算法3.1(总控算法总控算法 二级目录表二级目录表)：输入：输入：字符串形式的源程序流；字符串形式的源程序流；输出：输出：源程序单词的属性字流；源程序单词的属性字流；算法：算法：/*B 状态寄存器；状态寄存器；W 字符寄存器；字符寄存器；W 字符串寄存器；字符串寄存器；*/(1)B=初态初态;W=;(2)当

25、前读入字符当前读入字符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 扫描器设计与实现扫描器设计与实现?状态转换图的实现之二状态转换图的实现之二 程序中心法程序中心法将状态转换图看成一个流程图，从初态开始对

26、将状态转换图看成一个流程图，从初态开始对它的每个节点（状态）编写一函数或直接跟踪状态它的每个节点（状态）编写一函数或直接跟踪状态图从初态开始的转换完成所有分支的跟踪来编写程图从初态开始的转换完成所有分支的跟踪来编写程序。序。a.z0.9/ijkl例例3.5 设单一小写字母或单一数字或设单一小写字母或单一数字或“/”为合法单为合法单词，表示它们的状态转换图如图所示。词，表示它们的状态转换图如图所示。第第 34 页页Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.3 扫描器设计与实现扫描器设计与实现char char1;char1=nextchar();if (

27、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()为一函数，功能是从当前扫描的源程序读取为一函数，功能是从当前扫描的源程序读取下一个字符；下一个字符；第第 35 页页int state=0;enum lettet(a.z);enum number(0.9);char char1;char1=nextc

28、har();switch(state)case 0:switch(char1)case az:state=1;break;case 09:state=3;break;case =:state=5;break;case *:state=6;break;case +:state=7;break;case :state=11;break;case :state=12;break;default :state=13;break;Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.3 扫描器设计与实现扫描器设计与实现例例3.4状态转换图的实现状态转换图的实现第第 36 页

29、页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;

30、/*属性属性03表示无符号整常数表示无符号整常数*/case 5:return(04,);break;/*属性属性04表示表示“”*/case 6:return(05,);break;/*属性属性05表示表示“*”*/Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.3 扫描器设计与实现扫描器设计与实现第第 37 页页case 7:char1=nextchar();if(char1=+)state=9;else if(char1=”=”)state=10;else state=8;break;case 8:untread();return(08,);break

31、;/*属性属性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 是语法错处理函数是语法错处理函数*/Ch3 词法分析词法分析3.2 词法分析器的设计与实现词法分析器的设计与实现3.2.3 扫描器设计与实现扫描器设计与实现第第 38 页页一一.自

32、动生成思想自动生成思想一个词法分析程序产生器它接收用正规式表示一个词法分析程序产生器它接收用正规式表示的定义在某语言字母表上的单词的定义在某语言字母表上的单词,然后从此正规式然后从此正规式出发出发(1)构造能识别正规式 描述的单词集构造能识别正规式 描述的单词集(正规集正规集)的非确的非确定有限自动机定有限自动机NFA M,此步构造算法定义为此步构造算法定义为X。(2)用子集法用子集法(子集法实现算法命名为子集法实现算法命名为Y)将将M 确定化确定化,得到与其等价的得到与其等价的DFA M；(3)用划分算法用划分算法(命名为命名为Z)对对M 化简化简,得到得到DFA M。则这个则这个DFA M

33、即是理论上的扫描器。即是理论上的扫描器。Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 39 页页XYZDFA MV LEX编译器编译器用正规式对语言的词法规则进行描述用正规式对语言的词法规则进行描述,而正规式实际输而正规式实际输入形式是用入形式是用LEX语言来描述的。语言来描述的。+总控程序总控程序Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 40 页页二二.扫描器自动生成器扫描器自动生成器LEX/FLEXLEX (Lexical Analyzer Generator)1972年贝尔实验室在年贝尔实验室在UNIX上首先实现的，它是上首先实

34、现的，它是UNIX标准应用程序。标准应用程序。Flex(Fast Lexical Analyzer Generator)始于始于1984年的年的GNU工程推出，它是对工程推出，它是对LEX的扩充的扩充，同时也与，同时也与LEX兼容。兼容。Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 41 页页LEX运行与应用过程运行与应用过程LEX编译器接收编译器接收LEX源程序，由源程序，由LEX编译器处理编译器处理LEX源程序，产生一个词法分析器作为输出。在源程序，产生一个词法分析器作为输出。在UNIX环境中，环境中，LEX编译器的输出是一个具有标准文件名编译器的输出是一个具有

35、标准文件名lex.yy.c的的C程序，经过程序，经过C编译器的编译产生编译器的编译产生a.out文件，文件，a.out是一个实际可以运行的词法分析器。是一个实际可以运行的词法分析器。(语言语言x 的词法规则的的词法规则的lex描述描述)Lex源程序源程序a.out语言语言x的词法分析器的词法分析器Lex.yy.cLEX编译器编译器C编译器编译器Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 42 页页a.outLex.yy.cC编译器编译器PAS源程序的词法分析结果源程序的词法分析结果PAS源程序源程序a.outLex.yy.cLEX编译器编译器PAS.l例例3.6:

36、产生产生PAS语言的词法分析器语言的词法分析器Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 43 页页三个步骤：三个步骤：（1）编辑）编辑LEX源程序(例如，生成文本格式的源程序(例如，生成文本格式的PAS语言的语言的LEX源文件源文件PAS.l)；)；（2）使用命令）使用命令 lex PAS.l 运行运行LEX，正确则输出，正确则输出lex.yy.c；（；（3）调用）调用C编译器编译编译器编译 lex.yy.c，并与其它，并与其它C模块连接产生执行文件；调试执行文件，直至获得正确输出。模块连接产生执行文件；调试执行文件，直至获得正确输出。Ch3词法分析词法分析3.

37、3词法分析器的自动生成词法分析器的自动生成第第 44 页页definitions DiRi/*包含模式宏定义和包含模式宏定义和C语言的说明信息语言的说明信息*/%rules Pi Ai%subroutines /*规则动作部分所需的辅助过程的的规则动作部分所需的辅助过程的的C代码代码*/LEX程序结构程序结构规则部规则部分分说明部分说明部分用户代码部分用户代码部分Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 45 页页例如，有例如，有C说明和说明和LEX宏定义示例如下宏定义示例如下#include#include extern int flag#define Mar

38、ry 1#define Lida 2 int ERROR=-1char cdigit 0-9alpha a-zA-Zalnum a-zA-Z0-9C说明说明正规式辅助定义正规式辅助定义说明部分说明部分Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 46 页页识别规则部分一般形式是识别规则部分一般形式是Pi Ai 模式模式1 动作动作1模式模式2 动作动作2模式模式n 动作动作nPi Ai Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 47 页页模 式模 式说明说明示例示例x匹配单个字符匹配单个字符xabc匹配匹配a或或b或或ca-h0-5a

39、bcde匹配除去匹配除去a-e之间的任意字符之间的任意字符(可为可为a-e)abA-Zn表示匹配除小写字母表示匹配除小写字母a,b大写字母大写字母AZ和换行符外任意字符和换行符外任意字符转义符定义同转义符定义同ANSI C匹配除去换行符之外的任意字符匹配除去换行符之外的任意字符r*r是正规式，是正规式，r*匹配匹配0个或多个个或多个rr+r是正规式，是正规式，r+匹配匹配1个或多个个或多个rr?r是正规式，是正规式，r?匹配匹配0个或个或1个个rCh3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 48 页页单 词 值单 词 值wsififthenthenelseelsei

40、did名表指针名表指针numnum常数表指针常数表指针relopLTrelopLErelopEQrelopNErelopGTrelopGE单词的正规式表示单词的正规式表示属性属性例例3.7下表给出了某语言的单词的词法分析结果。下表给出了某语言的单词的词法分析结果。Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 49 页页该语言的该语言的LEX源程序如下源程序如下:#include#include#include#define IF1#define THEN2#define ELSE3#define ID4#define LT5#define LE6#define EQ

41、7#define NE8#define GT9#define GE10%Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 50 页页/*正规式模式宏定义正规式模式宏定义*/digit 0-9alpha a-zA-Zalnuma-zA-Z0-9delim tnwsdelim+id letter(letter|digit)*number digit+(.digit+)?(E+|-?digit+)?%Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 51 页页ws /*no action and no return*/if return(IF);the

42、n return(THEN);else return(ELSE);id yyIvaI=install_id();return(ID);number yyIvaI=install_num();return(NUMBER);yyIvaI=LT;return(RELOP);=yyIvaI=LE;return(RELOP);=yyIvaI=EQ;return(RELOP);yyIvaI=NE;return(RELOP);yyIvaI=GT;return(RELOP);=yyIvaI=GE;return(RELOP);%Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 52 页页

43、install_id()/*procedure to install the lexeme,whose firstcharacter is printed to by yytext and whose length is yyleng,into the symbol table and return a pointer thereto*/install_num()/*simllar procedure to install alexeme that is a number*/Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 53 页页词法分析器产生器的实现词法分析器产生

44、器的实现 对 对LEX源程序识别规则中的每个源程序识别规则中的每个Pi i构造一个相应的构造一个相应的NFA Mi i。引入惟一初态引入惟一初态X，从初态，从初态X通过弧将所有通过弧将所有NFAMi i(i=1，.,n)连接成新的(i=1，.,n)连接成新的NFA M。,两步实际两步实际是完成从正规式到非确定有限自动机的构造，其算法为是完成从正规式到非确定有限自动机的构造，其算法为X。对 对NFA M 确定化，产生确定化，产生DFA M，实现此步变换的算，实现此步变换的算法为法为Y。DFA M化简,引用算法化简,引用算法Z。给出总控程序。给出总控程序。Ch3词法分析词法分析3.3词法分析器的自

45、动生成词法分析器的自动生成第第 54 页页?算法算法3.2(总控算法总控算法)：输入：输入：字符串形式的源程序流；字符串形式的源程序流；输出：输出：源程序单词的属性字流；源程序单词的属性字流；算法：算法：/*I 当前状态；当前状态；a 当前输入字符；当前输入字符；A 字符串寄存器；字符串寄存器；*/I=0；A=空空；当前读入字符=a；当前读入字符=a；I=I(a)；/*送（/*送（I,a）的后继状态=）的后继状态=I*/*/A=A+a；/*/*“+”是指字符连接的加*/是指字符连接的加*/I如果是终态则转向，否则转向 ；I如果是终态则转向，否则转向 ；处理识别单词（处理识别单词（A）。）。Ch3词法分析词法分析3.3词法分析器的自动生成词法分析器的自动生成第第 55 页页Ch3 词法分析词法分析?词法分析的任务和词法分析方法。词法分析的任务和词法分析方法。?词法分析程序总体设计的考虑。词法分析程序总体设计的考虑。?词法分析程序输入对象的分析、提炼及相应输出属性字的设计。词法分析程序输入对象的分析、提炼及相应输出属性字的设计。?词法分析程序的设计工具与实现机制。词法分析程序的设计工具与实现机制。?词法分析程序自动生成的思想。词法分析程序自动生成的思想。?LEX应用与应用与LEX源程序的结构与描述。源程序的结构与描述。?第三章提要第三章提要