[工学]第四章词法分析1课件

资源描述

《[工学]第四章词法分析1课件》由会员分享，可在线阅读，更多相关《[工学]第四章词法分析1课件（47页珍藏版）》请在金锄头文库上搜索。

1、计算机教研室第四章第四章词法分析词法分析o词法分析是编译过程的第一步，其主要任务是对词法分析是编译过程的第一步，其主要任务是对源程序进行扫描，源程序进行扫描，产生一个个的产生一个个的单词单词符号，把作符号，把作为字符串的源程序改造成为单词符号串的中间程为字符串的源程序改造成为单词符号串的中间程序。序。因此，词法分析是编译的基础。执行词法分因此，词法分析是编译的基础。执行词法分析是编译的基础。析是编译的基础。词法分析：根据词法规则识别及组合单词，进行词词法分析：根据词法规则识别及组合单词，进行词法检查。法检查。对数字常数完成数字字符串到（二进制）数值的转对数字常数完成数字字符串到（二进制）数值

2、的转换。换。删去空格字符和注解。删去空格字符和注解。7/25/20241第四章：词法分析计算机教研室4.1 4.1 词法分析程序的设计词法分析程序的设计o任务任务n执行词法分析的程序称为词法分析器执行词法分析的程序称为词法分析器. .n词法分析器的功能是输入源程序词法分析器的功能是输入源程序, ,输出单输出单词符号词符号. .n单词符号单词符号是是一个一个程序语言的基本程序语言的基本符号符号。7/25/20242第四章：词法分析计算机教研室4.1.24.1.2词法分析程序的输出词法分析程序的输出o程序语言的程序语言的单词符号一般分为五种单词符号一般分为五种: :o关关键键字字: : 由由程程序

3、序语语言言定定义义的的具具有有固固定定意意义义的的标标识识符符。有有时时称称这这些些标标识识符符为为保保留留字字或或基基本本字字。例例如如，PascalPascal中的中的beginbegin，endend，if,whileif,while等。等。o标识符标识符: :用来表示各种名字用来表示各种名字, ,如如: :变量名变量名, ,数组名等数组名等. . o常数常数: : 整型整型, ,实型实型, ,布尔型等布尔型等. .o运算符运算符: + - * / : + - * / 等等. .o界符界符: :逗号逗号, ,分号分号, ,括号括号,/*, */,/*, */等等. .一一个个程程序序语语

4、言言的的关关键键字字, ,运运算算符符, ,界界符符都都是是确确定定的的, ,一一般般只只有有几几十十或或上上百百个个, ,而而对对标标识识符符和和常常数数的的使使用用都都不加什么限制不加什么限制. .7/25/20243第四章：词法分析计算机教研室单词符号的表示单词符号的表示o单词符号常常表示成如下二单词符号常常表示成如下二元式元式: : ( (单词种别单词种别, , 单词符号的属性值单词符号的属性值) )o单词种别可用以下形式表示单词种别可用以下形式表示: :n单词种别通常用整数编码单词种别通常用整数编码. .n一个语言的单词符号如何分种，分成几种，怎样编码，是一个一个语言的单词符号如何分

5、种，分成几种，怎样编码，是一个技术性的问题。它主要取决于处理上的方便。技术性的问题。它主要取决于处理上的方便。n标识符一般统归一种。常数则宜按类型分种。关键字可将其全标识符一般统归一种。常数则宜按类型分种。关键字可将其全体视为一种，也可以一字一种。运算符可采用一符一种的分法，体视为一种，也可以一字一种。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般用但也可以把具有一定共性的运算符视为一种。至于界符一般用一符一种的分法。一符一种的分法。n一类单词统一用一个整数值代表其属性如一类单词统一用一个整数值代表其属性如 1 1 代表保留字代表保留字,2 ,2 代表标识符等

6、代表标识符等. .n每一个单词一个类别每一个单词一个类别. .如如 1 1 代表代表BEGIN,2 BEGIN,2 代表代表ENDEND等等. .7/25/20244第四章：词法分析计算机教研室n如果一个种别只含一个单词符号，那么，对于这个单词如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。出种别编码之外，还应给出有关单词符号的属性信息。o属性值属性值: :

7、n单词符号的属性是指单词符号的特性或特征单词符号的属性是指单词符号的特性或特征. .属性值则是属性值则是反应特性或特征的值反应特性或特征的值. .n例如，对于某个标识符，常将存放它的有关信息的符号例如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。的常数表项的指针作为其属性值。n在本书中，假定关键字、运算符和界符都是一符一种。在本书中，假定关键字、运算符和界符都是一符一种。对于它们词法分析器只给出某种别编码，不给出它自身对于它们词法分析器只给出某种别编码，不给出它自身的值。

8、标识符单列一种。常数按类型分种类。的值。标识符单列一种。常数按类型分种类。7/25/20245第四章：词法分析计算机教研室1 1）按单词种类分类）按单词种类分类单词名称单词名称单词名称单词名称标识符标识符标识符标识符无符号常数无符号常数无符号常数无符号常数( (整整整整) )无符号浮点数无符号浮点数无符号浮点数无符号浮点数布尔常数布尔常数布尔常数布尔常数字符串常数字符串常数字符串常数字符串常数保留字保留字保留字保留字分界符分界符分界符分界符类别编码类别编码类别编码类别编码1 12 23 34 45 56 67 7单词值单词值单词值单词值内部字符串内部字符串内部字符串内部字符串整数值整数值整数值

9、整数值数值数值数值数值0 0 或或或或 1 1内部字符串内部字符串内部字符串内部字符串保留字或内部编码保留字或内部编码保留字或内部编码保留字或内部编码分界符或内部编码分界符或内部编码分界符或内部编码分界符或内部编码7/25/20246第四章：词法分析计算机教研室2 2）保留字和分界符采用一符一类）保留字和分界符采用一符一类单词名称单词名称单词名称单词名称标识符标识符标识符标识符无符号常数无符号常数无符号常数无符号常数( (整整整整) )无符号浮点数无符号浮点数无符号浮点数无符号浮点数布尔常数布尔常数布尔常数布尔常数字符串常数字符串常数字符串常数字符串常数IFIFTHENTHENELSEELSE

10、FORFOR: :+ +* *, ,( (类别编码类别编码类别编码类别编码1 12 23 34 45 56 67 78 89 9.2020212122222323.单词值单词值单词值单词值内部字符串内部字符串内部字符串内部字符串整数值整数值整数值整数值数值数值数值数值0 0 或或或或 1 1内部字符串内部字符串内部字符串内部字符串- - - - -.- - - - - -7/25/20247第四章：词法分析计算机教研室o考虑下考虑下述述C+C+代码段：代码段：while (i=j) i-;while (i=j) i-; 经词法分析器处理后，它将被转换为如下的单词符号经词法分析器处理后，它将被转

11、换为如下的单词符号序列：序列： id, =,- =,- id, id, 7/25/20248第四章：词法分析计算机教研室词法分析程序的词法分析程序的实现方案实现方案1. 1. 词法分析单独作为一遍词法分析单独作为一遍词法分析单独作为一遍词法分析单独作为一遍S.P.S.P.( (字符串字符串字符串字符串) )词法词法词法词法分析分析分析分析S.P.S.P.( (符号串符号串符号串符号串) )语法语法语法语法分析分析分析分析第一遍第一遍第一遍第一遍第二遍第二遍单词串单词串优点优点: 结构清晰、各遍功能单一结构清晰、各遍功能单一缺点：效率低缺点：效率低2. 2. 词法分析程序作为单独的子程序词法分析

12、程序作为单独的子程序词法分析程序作为单独的子程序词法分析程序作为单独的子程序S.P.S.P.( (字符串字符串字符串字符串) )词法分词法分词法分词法分析程序析程序析程序析程序语法分语法分语法分语法分析程序析程序析程序析程序取单词取单词单词单词单词单词7/25/20249第四章：词法分析计算机教研室词法分析器的设计词法分析器的设计o输入、预处理输入、预处理 1.输入缓冲区输入缓冲区：词法分析器工作的第一步是输入源程序文本。输入串一：词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓冲区称为输入缓冲区。般是放在一个缓冲区中，这个缓冲区称为输入缓冲区。 2.预处理预处理：

13、就是将程序语言中的空白符、跳格符、回车符、换行符和注：就是将程序语言中的空白符、跳格符、回车符、换行符和注解等编辑性字符剔掉。解等编辑性字符剔掉。 3.预处理子程序预处理子程序：就是用来完成编译的预处理。：就是用来完成编译的预处理。 4.分析器分析器：分析器对扫描缓冲区进行扫描时一般用两个指示器，一个指：分析器对扫描缓冲区进行扫描时一般用两个指示器，一个指向当前正在识别的单词的开始位置，另一个用于向前搜索以寻找单词向当前正在识别的单词的开始位置，另一个用于向前搜索以寻找单词的终点。不论扫描缓冲区设得多大都不能保证单词符号不会被它的边的终点。不论扫描缓冲区设得多大都不能保证单词符号不会被它的边界

14、所打断。因此，扫描缓冲区最好使用一个如下所示的一分为二的区界所打断。因此，扫描缓冲区最好使用一个如下所示的一分为二的区域：域：起点指示器起点指示器搜索指示器搜索指示器这意味着对标识符和常数的长度实际上必须加以限制，否则，即使缓冲区这意味着对标识符和常数的长度实际上必须加以限制，否则，即使缓冲区再大也无济于事。再大也无济于事。7/25/202410第四章：词法分析计算机教研室词法分析器的工作方式词法分析器的工作方式7/25/202411第四章：词法分析计算机教研室单词符号的识别：超前搜索单词符号的识别：超前搜索o在在某些语言中，要识别一个单词符号必须超前某些语言中，要识别一个单词符号必须超前

15、看若干字符，直到能区别开这些单词为止，常看若干字符，直到能区别开这些单词为止，常应用在如下几个方面：应用在如下几个方面：关键字的识别；关键字的识别；标识符的识别；标识符的识别；常数的识别；常数的识别；算符和界符的识别；算符和界符的识别；7/25/202412第四章：词法分析计算机教研室例：关键字的识别例：关键字的识别o在在FORTRAN语言中，关键字和用户自定义的标示符或标语言中，关键字和用户自定义的标示符或标号之间没有特殊的界符作间隔，所以识别比较麻烦，看如号之间没有特殊的界符作间隔，所以识别比较麻烦，看如下例子：下例子：o1 DO99K=1,10o2 IF(5.EQ.M) I=10o3

16、DO99K=1.10o4 IF(5)=55o语句语句1、3的区别在于等号之后的第一个界符：一个为逗的区别在于等号之后的第一个界符：一个为逗点，另一个为句末符。所以一直搜索到这里点，另一个为句末符。所以一直搜索到这里才能区分开才能区分开1句是句是DO语句，语句，3语句是赋值句。语句是赋值句。o语句语句2、4主要区别在于右括号之后的第一个字符：一个主要区别在于右括号之后的第一个字符：一个为字母，另一个为等号。所以也只能搜索到该字符才能得为字母，另一个为等号。所以也只能搜索到该字符才能得到语句到语句2是是IF语句，语句语句，语句4是赋值句。是赋值句。7/25/202413第四章：词法分析计算机教研

17、室4.24.2单词的描述工具单词的描述工具o程序设计语言中的单词是基本语法符号。单词程序设计语言中的单词是基本语法符号。单词符号的语法可以用有效的工具加以描述，并且符号的语法可以用有效的工具加以描述，并且基于这类描述工具，可以建立词法分析技术，基于这类描述工具，可以建立词法分析技术，进而可以建立词法分析程序的自动构造方法。进而可以建立词法分析程序的自动构造方法。o多数程序设计语言的单词的语法都能用多数程序设计语言的单词的语法都能用正规文正规文法法来描述。来描述。7/25/202414第四章：词法分析计算机教研室4.2.14.2.1正规文法正规文法o文法文法G=(G=(N N，T T，) ) G

18、 G的任何产生式为的任何产生式为ABAB或或AA，其中，其中V VT T* *，A A，B B V VN N。o书上书上P52P52的例子都是用正规文法表示的。在这的例子都是用正规文法表示的。在这里注意里注意可以为可以为，所以右边的表达式可能是，所以右边的表达式可能是非终结符、终结符或终结符加上非终结符非终结符、终结符或终结符加上非终结符。o可以看例子中那些规则分别属于那种类型。可以看例子中那些规则分别属于那种类型。7/25/202415第四章：词法分析计算机教研室4.2.24.2.2正规正规式式对于字母表对于字母表而言而言, ,正正规式和它所代表的正式和它所代表的正规规集的集的递归定定义为

19、: :n和和是正规式是正规式, ,它们所表示的正规集分别为它们所表示的正规集分别为和和;n任何任何aa, , a a是是上的一个正上的一个正规式式, ,它所表示的正它所表示的正规集集为 a a ; ;n假定假定U U和和V V都是都是上的正上的正规式式, ,它它们所表示的正所表示的正规集分集分别为L(U)L(U)和和L(V),L(V),那么那么,(U|V),(U*V),(U),(U|V),(U*V),(U)* * 也都是正规式也都是正规式, ,它们它们所表示的正规集分别为所表示的正规集分别为L(U)L(V),L(U)L(V)(L(U)L(V),L(U)L(V)(连接积连接积) )和和(L(U

20、)(L(U)* * ( (闭包闭包) )。n仅由有限次使用上述三步骤而得到的表达式才是仅由有限次使用上述三步骤而得到的表达式才是上的上的正规式。由这些正规式所表示的字集才是正规式。由这些正规式所表示的字集才是上的上的正规集正规集7/25/202416第四章：词法分析计算机教研室例例4.24.2令令=a,b,=a,b,上上所所有有正正规规式式和和相相应应正正规规集集的的例例子子有有: :正规式正规式正规集正规集a aa aa|ba|b a,ba,b abab abab baba* * 上所有以上所有以b b为首后跟任意多个为首后跟任意多个a a的字的字 a(a|b)a(a|b)* * 上所有上

21、所有以以a a为首的字为首的字7/25/202417第四章：词法分析计算机教研室例例令令=A,B,0,1, =A,B,0,1, 则则: :正规式正规式正规集正规集(A|B)(A|B|0|1)(A|B)(A|B|0|1)* * 上标识符的全体上标识符的全体 (0|1)(0|1)(0|1)(0|1)* * 上上“数数”的全体的全体正正归集集是正规语言的另一种表示方法。是正规语言的另一种表示方法。7/25/202418第四章：词法分析计算机教研室正规式的等价性正规式的等价性若若两两个个正正规规式式所所表表示示的的正正规规集集相相同同，则则认认为为二二者者等等价价。两两个个等等价价的的正正规规式式U

23、室另另:U,V :U,V 和和W W均为正规式，下列关系普遍成立：均为正规式，下列关系普遍成立： (1) U|V=V|U (1) U|V=V|U (交换律）交换律） (2(2）U|U|（V|WV|W）= =（U|VU|V）|W (|W (结合律）结合律） (3(3）U U（VWVW）= =（UVUV）W (W (结合律）结合律） (4) U(4) U（V|WV|W）=UV|UW (=UV|UW (分配律）分配律）（V|WV|W）U =VU|WU (U =VU|WU (分配律）分配律） (5)(5)U=U=UU=U =U 是连接的恒等元素是连接的恒等元素 (6) (6) U|U=U U|U=U

24、 “或或”的抽取律的抽取律正规式服从的代数规律正规式服从的代数规律7/25/202421第四章：词法分析计算机教研室4.2.34.2.3正规文法和正规式的等价性正规文法和正规式的等价性o一一个个正正规规语语言言可可以以由由正正规规文文法法定定义义，也也可可以由正规式定义。以由正规式定义。o对对任任何何正正规规文文法法，存存在在定定义义同同一一语语言言的的正正规式；规式；o对对任任何何正正规规式式，存存在在生生成成同同一一语语言言的的正正规规文法。文法。7/25/202422第四章：词法分析计算机教研室正规式转换成正规文法正规式转换成正规文法o将将上上的的一一个个正正规规式式转转换换成成文文法法

25、=(=(T T, ,N N, , ,).).另另其其中中的的的的T T= =，确确定定产产生生式式和和N N的的元元素素用用如如下办法：下办法：o对对任任何何正正规规式式 r r，选选择择一一个个非非终终结结符符号号S S生生成成产产生生式式 S S r, r, 并将并将S S定为定为G G的识别符号。的识别符号。o若若x x和和y y都都是是正正规规式式，对对形形如如A Axyxy 的的产产生生式式，重重写写成成A AxBxB, , ByBy两两个个产产生生式式, , 其其中中B B是是新新选选择择的的非非终终结符号，即结符号，即 B BN N7/25/202423第四章：词法分析计算机教研

26、室正规式转换成正规文法正规式转换成正规文法o对对已已转转换换的的文文法法中中的的形形如如A Axx* *y y的的产产生生式式, ,重重写写为：为： A A xBxB A y A y B B xBxB B y B y 其中其中B B为一新非终结符为一新非终结符. .o对对形如形如A A x|y x|y 的的产生式，重写为：产生式，重写为： A x , A yA x , A y7/25/202424第四章：词法分析计算机教研室例：例：o将将R=a(a|d)R=a(a|d)* *转转化化成成相相应应的的正正规规文文法法，令令S S是是文文法法的的开开始始符符号号，首首先先形形成成S S a(a|d

28、A-xB,BxB,B -y yA=A=xyxy规则规则2 2A-A-xA|yxA|yA=xA=x* *y y规则规则3 3A-A-x, x, A-A-y yA=x|yA=x|y7/25/202426第四章：词法分析计算机教研室例：例：o文法文法GSGS S S aA,SaA,S a,A a,A aA,AaA,A dA,AdA,A a,A d a,A d先有先有 S= S= aA|aaA|a A=( A=(aA|dA)|(a|daA|dA)|(a|d) )再再将将A A的的正正规规式式变变换换为为A=(a|d)A|(a|d), A=(a|d)A|(a|d), 据据表表中中规规则则2 2变变换换为

29、为A=(a|d)A=(a|d)* *|(a|d), |(a|d), 再再将将A A右右端端代代入入S S的的正正规规式式得：得： S=a(a|d)S=a(a|d)* *|(a(a|d)|a|(a(a|d)|a再利用正规式的代数变换可以此得到再利用正规式的代数变换可以此得到 S=a(a|d)S=a(a|d)* * |(a|d)|(a|d)| S=a(a|d) S=a(a|d)* * 即即 a(a|d)a(a|d)* * 为所求。为所求。7/25/202427第四章：词法分析计算机教研室补充：补充：状态转换图状态转换图（1 1）状态转换图）状态转换图o状态转换图是一张有限方向状态转换图是一张有限方

30、向图图. .它只包含有穷多个它只包含有穷多个状态状态, ,即有穷多个结点，即有穷多个结点，用用表示表示；状态结点都代；状态结点都代表文法的非终结符号表文法的非终结符号, ,而且至少要包含一个终止状而且至少要包含一个终止状态态，用，用表示表示. . 状态之间用箭弧连接状态之间用箭弧连接, ,箭弧上的标箭弧上的标记指明在射出弧的结点状态下可能出现的输入字符记指明在射出弧的结点状态下可能出现的输入字符或字符类或字符类. .o状态转换图实质上是语法图的一种变形。状态转换图实质上是语法图的一种变形。7/25/202428第四章：词法分析计算机教研室(2)(2)利用状态图识别利用状态图识别( (或接受或接

31、受) )字符串的过程字符串的过程o从初始状态出发，按照与符号串余留部分中最左从初始状态出发，按照与符号串余留部分中最左字符相匹配的原则，游历状态图，直至符号串的字符相匹配的原则，游历状态图，直至符号串的末端为止。如果这时恰好到达终止状态，则符号末端为止。如果这时恰好到达终止状态，则符号串为该文法的句子；否则不是。串为该文法的句子；否则不是。o大多数程序设计语言的单词符号都可以用状态转大多数程序设计语言的单词符号都可以用状态转换图予以识别。可以用一张状态转换图或若干张换图予以识别。可以用一张状态转换图或若干张状态转换图来描述一个语言的所有单词。状态转换图来描述一个语言的所有单词。7/25/202

32、429第四章：词法分析计算机教研室(3)(3)状态图的画法状态图的画法由右线性正规文法（产生式形如由右线性正规文法（产生式形如 U-U-aW|aaW|a) )构造状构造状态转换图。态转换图。o除了原有代表非终结符号的状态，另增加一个终除了原有代表非终结符号的状态，另增加一个终止状态止状态Z, Z, 对于每一条产生式对于每一条产生式U-aU-a，从状态从状态U U向向Z Z画一条弧，标记为画一条弧，标记为a a，即即7/25/202430第四章：词法分析计算机教研室(3)(3)状态转换图的画法状态转换图的画法o对于每一条产生式对于每一条产生式U-U-aWaW，从状态从状态U U向向状态状态W

33、W画一条弧，标记画一条弧，标记为为a a，即，即以识别符号为开始状态。以识别符号为开始状态。7/25/202431第四章：词法分析计算机教研室(3)(3)状态图的画法状态图的画法由左线性正规文法（产生式形如由左线性正规文法（产生式形如 U-U-Wa|aWa|a) )构造构造状态转换图。状态转换图。o除了原有代表非终结符号的状态，另增加一个除了原有代表非终结符号的状态，另增加一个开始状态开始状态S,S,对于每一条产生式对于每一条产生式U-aU-a，从状态从状态S S向向U U画一条弧，标记画一条弧，标记为为a a，即即7/25/202432第四章：词法分析计算机教研室(3)(3)状态转换图的画

34、法状态转换图的画法o对于每一条产生式对于每一条产生式U-U-WaWa，从状态从状态W W向状态向状态U U画一条弧，标记画一条弧，标记为为a a，即，即以识别符号为终止状态。以识别符号为终止状态。7/25/202433第四章：词法分析计算机教研室例例1:1:o(a)(a)表示在状态表示在状态1 1下下, ,若输入字符为若输入字符为X,X,则读进则读进X,X,并转换到状态并转换到状态2.2.若输入若输入字符为字符为Y,Y,则读进则读进Y,Y,并转换到状态并转换到状态3.3.o(b)(b)表示在状态表示在状态0 0下下, ,若输入字符是一个字母若输入字符是一个字母, ,则读进它则读进它, ,并转入

35、状态并转入状态1.1.在状态在状态1 1下下, ,若下一个输入字符为字母或数字若下一个输入字符为字母或数字, ,则读进它则读进它, ,并重现进入状并重现进入状态态1.1.一直重复这个过程一直重复这个过程, ,直到状态直到状态1 1发现输入不再是字母或数字就进入发现输入不再是字母或数字就进入状态状态2.2.o(c)(c)为识别整数的转换图为识别整数的转换图. .o终态结上打个星号终态结上打个星号* *意味着多读进了一个不属于标识符部分的字符，意味着多读进了一个不属于标识符部分的字符，应把它退还给输入串。应把它退还给输入串。7/25/202434第四章：词法分析计算机教研室例例2:2:语言无符号整

36、数的描述语言无符号整数的描述八进制数八进制数: ( OCT: ( OCT，值值 ) )ooctoct o ( 0|.|7 ) ( 0|.|7 ) o ( 0|.|7 ) ( 0|.|7 )* *十进制数十进制数: ( DEC: ( DEC，值值 ) )odecdec 0 | ( 1|.|9 ) ( 0|.|9 ) 0 | ( 1|.|9 ) ( 0|.|9 )* *7/25/202435第四章：词法分析计算机教研室整数的状态图（整数的状态图（1/21/2）3421o0-70-7 56101-90-9 十进制整数十进制整数八进制整数八进制整数7/25/202436第四章：词法分析计算机教研室o识

37、别十六进制整数的状态图。识别十六进制整数的状态图。n n将上述三个状态转换图合并为一个，得到语言无符号整数识别的状态将上述三个状态转换图合并为一个，得到语言无符号整数识别的状态将上述三个状态转换图合并为一个，得到语言无符号整数识别的状态将上述三个状态转换图合并为一个，得到语言无符号整数识别的状态图，方法步骤：图，方法步骤：图，方法步骤：图，方法步骤：（1 1）从开始状态出发；）从开始状态出发；）从开始状态出发；）从开始状态出发；（2 2）选择输入符号，构成目标状态集；）选择输入符号，构成目标状态集；）选择输入符号，构成目标状态集；）选择输入符号，构成目标状态集；（3 3）从新状态集出发，重复

38、（）从新状态集出发，重复（）从新状态集出发，重复（）从新状态集出发，重复（1 1）、（）、（）、（）、（2 2） 7/25/202437第四章：词法分析计算机教研室例例3:3:识别某个简单语言的所有单词识别某个简单语言的所有单词用一些带用一些带$的特殊符号的特殊符号来表示种别编码和内部来表示种别编码和内部值值7/25/202438第四章：词法分析计算机教研室o为了对例为了对例3进行更好的说明，做了如下的限制：进行更好的说明，做了如下的限制： 1）所有关键字（如）所有关键字（如IF，WHILE等）都是等）都是“保留字保留字”；2）对关键字不需专设对应的转换图，而只需要将他们）对关键字不需专设对应

39、的转换图，而只需要将他们预先安排在一张表格中；预先安排在一张表格中；3）如果关键字、标识符和常数之间没有确定的运算符）如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔。或界符作间隔，则必须至少用一个空白符作间隔。有了上述假定后，多数单词符号的识别就不必使用有了上述假定后，多数单词符号的识别就不必使用超前搜索技术。下图是一张识别表的单词符号的状态转超前搜索技术。下图是一张识别表的单词符号的状态转换图。在图中，状态换图。在图中，状态0为初态；凡带双圈者均为终态；为初态；凡带双圈者均为终态；状态状态13是识别不出单词符号的出错情形。是识别不出单词符号的出错情形

40、。7/25/202439第四章：词法分析计算机教研室例例3 3的状态图：的状态图：7/25/202440第四章：词法分析计算机教研室状态转换图的实现状态转换图的实现o让每个状态结点对应一段小程序，即可用程序实现状态图。在此引进了一组全让每个状态结点对应一段小程序，即可用程序实现状态图。在此引进了一组全局变量和过程，将他们作为实现转换图的基本成分。它们是：局变量和过程，将他们作为实现转换图的基本成分。它们是：1 1）chch 字符变量，存放最新读进的源程序字符。字符变量，存放最新读进的源程序字符。2 2）strTokenstrToken 字符数组，存放构成单词符号的字符串。字符数组，存放构成单词

41、符号的字符串。3 3）GetCharGetChar子程序过程，将下一输入字符读到子程序过程，将下一输入字符读到chch中，搜索指示器前移一字符位置。中，搜索指示器前移一字符位置。4 4）GetBCGetBC子程序过程，检查子程序过程，检查chch中的字符是否为空白。若是，则调用中的字符是否为空白。若是，则调用GetCharGetChar直至直至chch中中进入一个非空白字符。进入一个非空白字符。5 5）ConcatConcat子程序过程，将子程序过程，将chch中的字符连接到中的字符连接到strTokenstrToken之后。例如，假定之后。例如，假定strTokenstrToken原原来的值

42、为来的值为“AB”AB”，而，而chch中存放中存放CC，经调用经调用concatconcat后，后，strTokenstrToken的值就变为的值就变为“ABC”ABC”。6 6）IsLetterIsLetter和和IsDigitIsDigit布尔函数过程，分别判断布尔函数过程，分别判断chch中的字符是否是字母和数字中的字符是否是字母和数字7 7）ReserveReserve整型函数过程，整型函数过程，对对strTokenstrToken中的字符串查找保留字表，若它是一个保留中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回字则返回它的编码，否则返回0 0值。值。8 8）Re

43、tractRetract子程序过程，将搜索指示器回调一个字符位置，将子程序过程，将搜索指示器回调一个字符位置，将chch置为空白字符置为空白字符9 9）InsertIdInsertId整型函数过程，将整型函数过程，将strTokenstrToken中的标识符插入符号表，返回符号表指针中的标识符插入符号表，返回符号表指针1010）InsertConstInsertConst整型函数过程，将整型函数过程，将strTokenstrToken中的常数插入常数表，返回常数表指针中的常数插入常数表，返回常数表指针7/25/202441第四章：词法分析计算机教研室对于不含回路的分叉结点来说，可让它对应一个对

44、于不含回路的分叉结点来说，可让它对应一个switchswitch语句或一组语句或一组ifthenelseifthenelse语句。对应程序语句。对应程序如下：如下：GetcharGetchar();();If (If (isLetterisLetter()()状态状态j j的对应程序段的对应程序段;Else Else if(isDigitif(isDigit()()状态状态k k的对应程序段；的对应程序段； Else if (Else if (chch=/)=/)状态状态l l对应程序段；对应程序段； Else Else 错误处理；错误处理； iljk字母字母数字数字/当当当当程序执行到达程序

45、执行到达程序执行到达程序执行到达“ “错误处理错误处理错误处理错误处理” ”时，意味着现行状态时，意味着现行状态时，意味着现行状态时，意味着现行状态I I I I和和和和当前所面临的输入串不匹配。如果后面还有状态图，当前所面临的输入串不匹配。如果后面还有状态图，当前所面临的输入串不匹配。如果后面还有状态图，当前所面临的输入串不匹配。如果后面还有状态图，出现在这个地方的代码应为：将搜索指示器回退一个出现在这个地方的代码应为：将搜索指示器回退一个出现在这个地方的代码应为：将搜索指示器回退一个出现在这个地方的代码应为：将搜索指示器回退一个位置，并令下一个状态图开始工作。如果后面没有其位置，并令下一个

46、状态图开始工作。如果后面没有其位置，并令下一个状态图开始工作。如果后面没有其位置，并令下一个状态图开始工作。如果后面没有其它状态图，则出现在上述位置的代码应进行真正的出它状态图，则出现在上述位置的代码应进行真正的出它状态图，则出现在上述位置的代码应进行真正的出它状态图，则出现在上述位置的代码应进行真正的出错处理，报告源程序含有非法符号，并进行善后处理。错处理，报告源程序含有非法符号，并进行善后处理。错处理，报告源程序含有非法符号，并进行善后处理。错处理，报告源程序含有非法符号，并进行善后处理。7/25/202442第四章：词法分析计算机教研室对于含回路的状态结点来说，可对于含回路的状态结点来说

47、，可让它对应一个由让它对应一个由whilewhile语句和语句和ifif语句构成的程序段，右图所对语句构成的程序段，右图所对应的程序段可为：应的程序段可为：GetCharGetChar();();While(isLetterWhile(isLetter() or () or isDigitisDigit()()GetCharGetChar();();状态状态j j的对应程序段的对应程序段ij字母或数字字母或数字其它其它终态结点一般对应一个形如终态结点一般对应一个形如终态结点一般对应一个形如终态结点一般对应一个形如return(code,value)return(code,value)retur

48、n(code,value)return(code,value)的语句。其中，的语句。其中，的语句。其中，的语句。其中，codecodecodecode为单词种别编码；为单词种别编码；为单词种别编码；为单词种别编码；valuevaluevaluevalue或是单词符号的属性值，或无定义。或是单词符号的属性值，或无定义。或是单词符号的属性值，或无定义。或是单词符号的属性值，或无定义。这个这个这个这个returnreturnreturnreturn意味着从分析器返回到调用者，一般指返回到语法意味着从分析器返回到调用者，一般指返回到语法意味着从分析器返回到调用者，一般指返回到语法意味着从分析器返回到调

49、用者，一般指返回到语法分析器。凡带分析器。凡带分析器。凡带分析器。凡带* * * *的终态结点意味着多读了一个不属于现行单词符的终态结点意味着多读了一个不属于现行单词符的终态结点意味着多读了一个不属于现行单词符的终态结点意味着多读了一个不属于现行单词符号的字符，这个字符应予退回，也就是说，必须把搜索指示器号的字符，这个字符应予退回，也就是说，必须把搜索指示器号的字符，这个字符应予退回，也就是说，必须把搜索指示器号的字符，这个字符应予退回，也就是说，必须把搜索指示器回调一字符位置。这项工作有回调一字符位置。这项工作有回调一字符位置。这项工作有回调一字符位置。这项工作有RetractRetract

50、RetractRetract过程来完成。过程来完成。过程来完成。过程来完成。7/25/202443第四章：词法分析计算机教研室转换图转换图3.3的词法分析器可构造如下：的词法分析器可构造如下：例例3 3的词法分析器：的词法分析器：intint code,value; code,value;strTokenstrToken :=“ ”; /* :=“ ”; /*置置strTokenstrToken 为空串为空串* */ /GetCharGetChar(); (); GetBCGetBC(); /*(); /*读入一字符读入一字符* */ /if (if (IsLetterIsLetter()()

51、beginbegin while(IsLetterwhile(IsLetter() or () or IsDigitIsDigit()() begin begin ConcatConcat(); (); GetCharGetChar(); /*(); /*将字符进行连接将字符进行连接* */ / end end7/25/202444第四章：词法分析计算机教研室Retract(); Retract(); /*/*回调一位回调一位* */ /code:=Reserve(); code:=Reserve(); /*/*是保留字还是标识符是保留字还是标识符* */ /if (code=0) if (c

52、ode=0) /*/*如是标识符如是标识符* */ / begin begin value:= value:=InsertId(strTokenInsertId(strToken); ); return($ID,value); return($ID,value); /*/*返回编码和属性值返回编码和属性值* */ / end endelseelse return(code,-); return(code,-);endend7/25/202445第四章：词法分析计算机教研室else else if(IsDigitif(IsDigit()()beginbegin while(IsDigitwhil

53、e(IsDigit()() begin begin ConcatConcat(); (); GetCharGetChar(); (); end end Retract(); Retract(); value:= value:=InsertConst(strTokenInsertConst(strToken);); return($INT,value); return($INT,value);endendelse else if(chif(ch= = ) return ($ASSIGN, -);= = ) return ($ASSIGN, -);else else if(chif(ch= + )

54、 return ($PLUS, -);= + ) return ($PLUS, -);7/25/202446第四章：词法分析计算机教研室else else if(chif(ch= * ) = * ) beginbegin GetCharGetChar();(); if ( if (chch = *) return ($POWER,-); = *) return ($POWER,-); Retract();return($SATR,-); Retract();return($SATR,-);endendelse else if(chif(ch= ; ) return ($SEMICOLON, -

55、);= ; ) return ($SEMICOLON, -);else else if(chif(ch= ( ) return ($LPAR, -);= ( ) return ($LPAR, -);else else if(chif(ch= ) ) return ($RPAR, -);= ) ) return ($RPAR, -);else else if(chif(ch= ) return ($LBRACE, -);= ) return ($LBRACE, -);else else if(chif(ch= ) return ($RBRACE, -);= ) return ($RBRACE, -);else else ProcErrorProcError();();7/25/202447第四章：词法分析

展开阅读全文

[工学]第四章词法分析1课件

最新文档