编译原理2词法分析

1、1 内容提要内容提要: 状态转换图状态转换图 正规式与有限制动机正规式与有限制动机 词法分析器的自动生成词法分析器的自动生成 词法分析器词法分析器 源程序源程序单词序列单词序列 2 第一节第一节 状态转换图状态转换图 一一 单词分类及表示单词分类及表示 编译中编译中,把高级语言的单词分为五类把高级语言的单词分为五类: 标识符标识符,基本字基本字,常数常数,运算符运算符,界符界符 基本字基本字,运算符运算符,界符都是有限可枚举的界符都是有限可枚举的;而标识符而标识符,常数可常数可 认为是无限的认为是无限的. 简单起见简单起见,单词可表示为如下单词可表示为如下二元组二元组: (单词分类号单词分类号

2、,单词自身值单词自身值); 或者为或者为: (单词种别码单词种别码,单词自身值单词自身值); 标识符标识符,常数常数 各为一个种别码各为一个种别码,而由于基本字而由于基本字,运算符运算符,界符界符 的有限性的有限性,可以设计为一字一个种别码可以设计为一字一个种别码. 3 例如例如: 单词单词 单词种别码单词种别码分类号分类号 标识符标识符1 1 常数常数 2 2 if 3 3 then4 3 end90 3 ,91 4 ;92 4 =151 5 +152 5 保留字保留字 界符界符 运算符运算符 4 二二 词法分析器的设计词法分析器的设计 1 源程序的预处理子程序源程序的预处理子程序 源程序中

3、源程序中,存在许多编辑用的符号存在许多编辑用的符号,它们对程序逻辑功能无它们对程序逻辑功能无 任何影响任何影响. 例如例如:回车回车,换行换行,多余空白符多余空白符,注释行等注释行等.在词法分析在词法分析 之前之前,首先要剔除掉这些符号首先要剔除掉这些符号,使得词法分析更为简单使得词法分析更为简单. 源程序源程序输入缓冲区输入缓冲区 预处理子程序预处理子程序 扫描缓冲区扫描缓冲区2扫描缓冲区扫描缓冲区1 缓冲区分为两部分缓冲区分为两部分,每每 个长度为个长度为256字节字节,这样这样 单词的总长度可达到单词的总长度可达到 256字节字节.预处理子程序预处理子程序 把处理好的字符串轮把处理好的字

4、符串轮 流放入两个缓冲区中流放入两个缓冲区中, 供词法分析程序使用供词法分析程序使用. 5 2 词法分析程序词法分析程序 词法分析程序又称为词法分析程序又称为词法分析器或扫描器词法分析器或扫描器.可以单独为一个可以单独为一个 程序程序;也可以作为整个编译程序的一个子程序也可以作为整个编译程序的一个子程序,当需要一个单词时当需要一个单词时, 就调用词法分析子程序返回一个单词就调用词法分析子程序返回一个单词.这里这里,作为子程序介绍作为子程序介绍. 词法分析器的结构词法分析器的结构: 源程序源程序输入缓冲区输入缓冲区 预处理子程序预处理子程序 扫描缓冲区扫描缓冲区2扫描缓冲区扫描缓冲区1 词法分析

5、子程序词法分析子程序 调用调用 返回一单词返回一单词 数据数据 6 3 词法规则的表示词法规则的表示-状态转换图状态转换图 定义定义:状态转换图是一有向图状态转换图是一有向图,由有限个结点及有向边连接而成由有限个结点及有向边连接而成; 每个结点称为状态每个结点称为状态;状态图有一个初态状态图有一个初态,多个终态多个终态;每条边上每条边上 有相应的字符有相应的字符. 状态转换图用于表示单词结构状态转换图用于表示单词结构,从状态转换图的初态到终态从状态转换图的初态到终态 间间,每条路径上字符的连接每条路径上字符的连接,就构成了该状态图的合法单词就构成了该状态图的合法单词. 例如例如: 012初态初

6、态终态终态 字母字母 字母字母 数字数字 其它其它 * 1标识符的状态图表示标识符的状态图表示: 星号表示单词尾部多跟星号表示单词尾部多跟 一个字符一个字符,应该去掉应该去掉. 7 012初态初态终态终态 数字数字 数字数字 其它其它 * 2整数的状态图表示整数的状态图表示: 01 6 初态初态 终态终态 数字数字 数字数字 其它其它 * 3实数的状态图表示实数的状态图表示: 2345 6 数字数字数字数字 数字数字 E+或或 数字数字 E 其它其它 数字数字 8 4 单词的识别单词的识别 状态图即可以表示单词规则状态图即可以表示单词规则,同时也可以用于识别单词同时也可以用于识别单词. 设有一

7、字符串设有一字符串S = s1s2.sn, 若状态图中存在一初态到终态的若状态图中存在一初态到终态的 路径路径,且路径上字符的连接为且路径上字符的连接为: s1s2.sn, 称称 S 可被状态图识别可被状态图识别. 例如例如: S=var1 012初态初态终态终态 v ar 1 其它其它 * 保留字保留字由于满足标识符定义由于满足标识符定义,因此可以跟标识符用同样的状因此可以跟标识符用同样的状 态图表示与识别态图表示与识别,只需增加一个只需增加一个保留字表保留字表,当识别出一个标识符时当识别出一个标识符时, 通过查保留字表来区别保留字及普通标识符通过查保留字表来区别保留字及普通标识符. 因此因

8、此 var1 是一个合法的标识符是一个合法的标识符. 9 5 一个简单示例一个简单示例 构造一个简单语言所有单词的状态转换图构造一个简单语言所有单词的状态转换图.该语言的单词种类如下表所示该语言的单词种类如下表所示: 单词符号单词符号 种别码种别码 助记符助记符 内码值内码值 DIM IF DO STOP END 标识符标识符 正常数正常数 = + * * , ( ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 $DIM $IF $DO $STOP $END $ID $INT $ASSIGN $PLUS $STAR $POWER $COMMA $LPAR $RPAR (

9、1 , ) ( 2 , ) ( 3 , ) ( 4 , ) ( 5 , ) ( 6 , 串值串值) ( 7 , 数值数值) ( 8 , ) ( 9 , ) ( 10, ) ( 11, ) ( 12, ) ( 13, ) ( 14, ) 10 0 1 2初态初态终态终态 字母字母 字母字母数字数字 其它其它 * 空白空白 3 4 终态终态 数字数字 数字数字 非数字非数字* 5 = 6 + 7 * 9 8 * *非非 * * 10 , 11 ( 12 ) 13 其它其它 11 6 状态转换图的程序实现状态转换图的程序实现 为便于程序实现为便于程序实现,假设每个单词间都有界符或运算符或空格隔假设每

10、个单词间都有界符或运算符或空格隔 开开,并引入下面的全局变量及子程序并引入下面的全局变量及子程序: 1) CHAR 字符变量字符变量 2) TOKEN 单词字符串单词字符串 3) GETCHAR 读一个字符到读一个字符到 CHAR 中中 4) GETBC 读一个非空白字符到读一个非空白字符到CHAR 中中 5) CONCAT 把把CHAR 中字符连接到中字符连接到TOKEN 之后之后 6) LETTER 判断判断CHAR 中字符是否为字母中字符是否为字母 7) DIGIT 判断判断CHAR 中字符是否为数字中字符是否为数字 8) RESERVE 用用TOKEN中的字符串查找保留字表中的字符串查

11、找保留字表,并返回保留并返回保留 字种别码字种别码,若返回零若返回零,则非保留字则非保留字 9) RETRACT 把把CHAR 中字符回送到缓冲区中字符回送到缓冲区 12 下面分析状态图的结构特点下面分析状态图的结构特点.每个状态图都由三种结构构成每个状态图都由三种结构构成: 分支结构分支结构 循环结构循环结构 终结点终结点 1分支结构程序设计分支结构程序设计 i i2 i1 in c1 c2 cn state i:GETCHAR; CASE CHAR OF c1 :CONCAT；state i1: . c2 :CONCAT；state i2: . cn :CONCAT；state in: .

12、 ELSE ERROR END; 13 2循环结构程序设计循环结构程序设计 i j C 其它其它 state i:GETCHAR; WHILE CHAR=C DO CONCAT;GETCHAR; RETRACT； state j: . 3终结点程序设计终结点程序设计 一般对应一条返回语句一般对应一条返回语句: return( c,val); c 为种别码为种别码, val 为单词值为单词值. 带带 * 号的终结点号的终结点,必须用必须用RETRACT 退还多余字符退还多余字符 下面程序为简单示例语言的实现下面程序为简单示例语言的实现: 14 TYPE WORDTYPE=RECORD C：INT

13、EGER； VAL：CHAR； END； FUNCTION RETURN_WORD( ):WORDTYPE; STATE0: TOKEN:=;GETCHAR;GETBC; CASE CHAR OF A.Z: CONCAT; STATE1:GETCHAR; WHILE (LETTER OR DIGIT) DO CONCAT;GETCHAR; RETRACT； STATE2: C:=RESERVE; IF C=0 THEN RETURN($ID,TOKEN) ELSE RETURN(C,_ ) 15 0. 9: CONCAT; STATE3:GETCHAR; WHILE ( DIGIT) DO C

14、ONCAT;GETCHAR; RETRACT； STATE4: RETURN($INT,TOKEN ); =: STATE5:RETURN($ASSIGN,_ ); +: STATE6:RETURN($PLUS,_ ); *: STATE7:GETCHAR; STATE9: IF CHAR=* THEN RETURN($POWER,_ ); STATE8: RETRACT; RETURN($STAR,_ ); , : STATE10:RETURN($COMMA,_ ); ( : STATE11:RETURN($LPAR,_ ); ) : STATE12:RETURN($RPAR,_ ); EL

15、SE STATE13: ERROR 16 这节介绍词法规则的这节介绍词法规则的形式表示形式表示(正规式正规式),从正规式向有限自动从正规式向有限自动 机的转化机的转化. 正规式正规式有限自动机有限自动机词法分析器词法分析器 控制程序控制程序 自动生成器自动生成器 转化转化合成合成 第二节第二节 正规式与有限自动机正规式与有限自动机 17 一一 基本概念基本概念 定义定义 1 字与字集字与字集 假设假设: 是一有穷字符集是一有穷字符集,它的每个元素称为一个字符它的每个元素称为一个字符; 字字- 上的一个字上的一个字,是由是由 中的字符所构成的一个有穷序列中的字符所构成的一个有穷序列; 空串空串-

16、不包含任何元素的序列称为空串不包含任何元素的序列称为空串,记为记为; 闭包闭包*- 上所有可能的字的全体上所有可能的字的全体; 空字集空字集-不含任何字的集合称为空字集不含任何字的集合称为空字集;记为记为 = ; 例如例如: =a,b 则则 *=,a,b,aa,ab,ba,bb. 注意注意: , , 三者间的关系三者间的关系 定义定义 2 连接运算连接运算 设设 U,V * 则则 UV= | U, V 一般一般 UVVU Vn =VV.V 称为称为 V 的的 n 次积次积 18 例如例如: 设设 U=a,aa, V=b 则则UV=ab,aab VU=ba,baa 定义定义 3 V的闭包的闭包

17、设设 V 为字集为字集,且且 V0= 令令 V*=V0V1 V2 . V+= V* - 称称V* 为为V的闭包的闭包 称称V+ 为为V的正则闭包的正则闭包 注意注意: * 与与 V* 的区别的区别. 19 二二 正规式与正规集正规式与正规集 *是一个无穷集是一个无穷集,在程序语言中在程序语言中,我们只研究满足词法规则我们只研究满足词法规则 (正规式正规式)的单词集的单词集(正规集正规集). 定义定义 1 正规式与正规集的递归定义正规式与正规集的递归定义 : 1) , 是是 上的正规式上的正规式, 所表示的正规集为所表示的正规集为 , ; 2) 若若 a ,则则 a 为正规式为正规式, 所表示的

18、正规集为所表示的正规集为 a; 3) 设设U,V 为为 上的正规式上的正规式, 所表示的正规集为所表示的正规集为 L(U),L(V); 则则 U|V为为 上的正规式上的正规式, 所表示的正规集为所表示的正规集为 L(U) L(V); UV为为 上的正规式上的正规式, 所表示的正规集为所表示的正规集为 L(U) L(V); V* 为为 上的正规式上的正规式, 所表示的正规集为所表示的正规集为 L(V)* ; 4) 仅当有限次使用上述三步骤而定义的表达式仅当有限次使用上述三步骤而定义的表达式,才是才是 上的正规式上的正规式 , 而这些正规式所表示的字集才是而这些正规式所表示的字集才是上的正规集上的

19、正规集. 20 示例示例: 令令=A.Z,0.9 则则整数整数的正规式为的正规式为: (0|1|2.|9)(0|1|2.|9) * 所表示的正规集为所有整数所表示的正规集为所有整数; 标识符标识符的正规式为的正规式为:(A|B|.Z)(A|B|.Z| 0|1|.|9) * 所表示的正规集为所有标识符所表示的正规集为所有标识符 定义定义 2 若两个正规式若两个正规式 U,V 所表示的正规集相同所表示的正规集相同,即即 L(V)=L(U), 则称两个则称两个正规式等价正规式等价,记为记为 U=V. 正规式的运算正规式的运算: 设设 U V W 为正规式为正规式, 则满足以下关系则满足以下关系: 1

20、) U|V=V|U 2) U|(V|W)=(U|V)|W 3) U(VW)=(UV)W 4) U(V|W)=UV|UW (U|V)W=UW|VW 5) U=U =U 21 三三 确定有限自动机确定有限自动机 一个确定有限自动机一个确定有限自动机(DFA M)是一个五元式是一个五元式: DFA M=(S, , f,s0,Z) 其中其中 S 是一有限集是一有限集,每个元素称为一个状态每个元素称为一个状态; 是一个有穷字母表是一个有穷字母表,每个元素为一字符每个元素为一字符; f 是一个单值映射函数是一个单值映射函数,f(si,a)=sj ( si , sj S, a ); 其含义为其含义为:在状态

21、在状态 si ,输入字符输入字符 a 时时,将转换到下一状态将转换到下一状态sj. 称称sj为为 si的后继状态的后继状态. s0 S, 是唯一的初态是唯一的初态; Z S ,是终态集是终态集. 一个一个DFAM可用可用状态转换矩阵状态转换矩阵或或状态图状态图表示表示 22 例如例如: DFAM=( 0,1,2,3, a,b, f, 0, 3) 其中其中f为为: f(0,a)=1 f(1,a)=3 f(2,a)=1 f(3,a)=3 f(0,b)=2 f(1,b)=2 f(2,b)=3 f(3,b)=3 状态转换矩阵可表示为状态转换矩阵可表示为: 状态图可表示为状态图可表示为: ab 012

22、132 213 333 状状 态态 字字 符符 0 1 3初态初态终态终态 2 a b b a a a b b 23 四四 非确定有限自动机非确定有限自动机 一个非确定有限自动机一个非确定有限自动机(NFA M)是一个五元式是一个五元式: NFA M=(S, , f,S0,Z) 其中其中 S 是一有限集是一有限集,每个元素称为一个状态每个元素称为一个状态; 是一个由穷字母表是一个由穷字母表,每个元素为一字符每个元素为一字符; f 是一个多值映射函数是一个多值映射函数,f(si,)=s i1 , s i2 ,. s ik ( si , si1 ,. , s ik S, *); 其含义为其含义为:

23、在状态在状态 si ,输入字串输入字串 时时,将转换到下一状态集将转换到下一状态集: s i1 , s i2 ,. s ik S0 S, 是初态集是初态集; Z S ,是终态集是终态集. 一个一个NFAM也可用也可用状态图状态图表示表示,此时每条边用字串表示此时每条边用字串表示. 24 例如例如: 01初态初态终态终态 2 aa bb a,b a,b a,b 终态终态 DFAM 是是 NFAM 的特例的特例. 定义定义: 状态图中状态图中,从初态到终态任一路径上的字串连接从初态到终态任一路径上的字串连接,称为该状称为该状 态图可识别的单词态图可识别的单词,可识别单词的全体记为可识别单词的全体记

24、为:L(M). 若若L(M)= L(M), 称称M 与与M等价等价. 25 五五 正规式与有限自动机的等价性正规式与有限自动机的等价性 前面前面,介绍了正规式介绍了正规式,DFAM,NFAM, 下面讨论这三个概念间的下面讨论这三个概念间的 关系关系. 定理定理1 : 对任意正规式对任意正规式V,存在一个存在一个NFAM ,使得使得L(V)=L(NFAM); 证明证明: (1)构造一个拓广转换图构造一个拓广转换图 显然显然,该转换图能识别的该转换图能识别的 单词集为单词集为:L(V) XY V 26 (2) 进行如下等价变换进行如下等价变换,直到转换图的每条边上的标志为直到转换图的每条边上的标志

25、为上的上的 字符字符. ij V1V2 ij V1 k V2 a ij V1 | V2 i V1 j V2 b ij V* ij k c V 等价变换后的转换图等价变换后的转换图M 符合符合 NFAM的定义的定义,显然有显然有 L(V)=L(M). 该定理说明该定理说明,从正规式可逐步构造一个从正规式可逐步构造一个NFAM. 27 定义定义:设设 S 是一个状态集是一个状态集, _CLOSURE(S)定义如下定义如下: a) 若若 s S,则则 s _CLOSURE(S); b) 若若 s S,则则 从从 s 出发经过任意条出发经过任意条 边所能到达的状态边所能到达的状态 s 都属于都属于 _

26、CLOSURE(S). 状态集状态集_CLOSURE(S)称为称为 S 的的_ 闭包闭包. 定理定理2: 对任意对任意NFAM,存在一个存在一个DFAM ,使得使得L(DFAM)=L(NFAM); 证明证明: (1) 对对 NFAM 进行等价变换进行等价变换,使得变换后的转换图使得变换后的转换图NFAM中中 仅含仅含边和边和 上的字符边上的字符边; (2) 用状态转换矩阵用状态转换矩阵M 表示表示NFAM; 28 其中其中, I0 为初态集的为初态集的_ 闭包闭包. Ii a = _ CLOSURE f(si 1 , a) f(si 2 , a) f(sik , a) si 1 , si 2

27、,. sik Ii (3) 将将M 中的状态集换名中的状态集换名, si = Ii 得到一新的状态转换矩阵得到一新的状态转换矩阵 M , M 满足满足 DFAM 的定义的定义. Iabc. I0 I1 Ii Ii a Ii b Ii c In M 29 证毕证毕. 推论推论: 对任意正规式对任意正规式V,存在一个存在一个DFAM ,使得使得L(DFAM)= L(V). Sabc. s0 s1 si si a si b si c sn M 30 示例示例: 设正规式为设正规式为 ( a|b) *(aa|bb)(a|b) *,求与之等价的求与之等价的DFAM. (1) 由定理由定理 1 的证明方法

28、的证明方法,可如下构造可如下构造NFAM X Y ( a|b) *(aa|bb)(a|b) * 等价变换得到等价变换得到: 51 3 26 4 a a a a b b b b NFAM X Y (2) 用状态转换矩阵用状态转换矩阵M 表示表示NFAM; 31 Iab x,5,1 5,1,3 5,1,4 5,1,3 5,1,3,2,6,y 5,1,4 5,1,4 5,1,3 5,1,4,2,6,y 5,1,3,2,6,y 5,1,3,2,6,y 5,1,4,6,y 5,1,4,2,6,y 5,1,3,6,y 5,1,4,2,6,y 5,1,4,6,y 5,1,3,6,y 5,1,4,2,6,y

29、5,1,3,6,y 5,1,3,2,6,y 5,1,4,6,y M (3) 将将M 中的状态集换名中的状态集换名, si = Ii 得到一新的状态转换矩阵得到一新的状态转换矩阵 M 注意注意: M 与与 M等价等价. 32 Sab s0 s1 s2 s1 s3 s2 s2 s1 s4 s3 s3 s5 s4 s6 s4 s5 s6 s4 s6 s3 s5 M M满足确定有限自动机的定义满足确定有限自动机的定义,状态图状态图 表示如下表示如下: s0 s1s3s5 s6s4 a b b s2 a a a a a a b bb b b 33 第三节第三节 词法分析器的词法分析器的 自动生成原理及自

30、动生成原理及LEX语言语言 正规式正规式 确定自动机确定自动机 状态转换矩阵状态转换矩阵 词法分析器词法分析器 控制程序控制程序 自动生成器自动生成器 转化转化合成合成 一一 自动生成原理自动生成原理 34 二二 LEX 语言语言 LEX 语言用正规式描述单词的词法规则语言用正规式描述单词的词法规则,并通过并通过LEX编译编译,自自 动生成词法扫描器动生成词法扫描器. LEX语言语言 源程序源程序 LEX编译编译词法分析器词法分析器 LEX语言源程序由两部分组成语言源程序由两部分组成: 正规式辅助定义式正规式辅助定义式 识别规则识别规则 35 1 辅助定义式辅助定义式 辅助定义式是如下形式的辅

31、助定义式是如下形式的 LEX 语句语句 D1 R1 D2 R2 Dn Rn Ri为正规式为正规式, Di为简名为简名. 规定规定Ri中只能出现中只能出现上的字符及之前上的字符及之前 已定义过的已定义过的D1. Di -1 . 例如例如: Letter A|B|.|Z|a|b|.|z Digit 0|1|2.|9 Iden Letter(Letter| Digit)* 36 2 识别规则识别规则 Unsignedint Digit( Digit)* Sign +| - | signedint Sign Unsignedint P1 A1 P2 A2 Pm Am Pi为正规式为正规式, 规定规定Pi中只能出现中只能出现上上 的字符及的字符及D1. Dn ;P1. Pm 代表了某代表了某 种高级语言的所有词形种高级语言的所有词形. Ai为一段程序代码为一段程序代码,指出当识别出满指出当识别出满 足规则足规则Pi的单词时的单词时,扫描器应采取的动作扫描器应采取的动作. 37