编译原理 词法分析

1、1第四章第四章: :词法分析词法分析Lexical AnalysisLexical Analysis234第二遍第二遍单词串单词串取单词取单词优点优点: 结构清晰、各遍功能单一结构清晰、各遍功能单一缺点：效率低缺点：效率低562. 词法分析程序的输出形式词法分析程序的输出形式-单词的内部形式单词的内部形式7If (3, if)I (1,8910111213=a,b=a,b，上的正规式和相应的正规集如下上的正规式和相应的正规集如下：14例例 2 2：令令=A,B,0,1=A,B,0,1，则，则：例例 3 3：令令=d,.,e,+,-=d,.,e,+,-，写出，写出上的无符号数的正则上的无符号数的

2、正则式式15例例 3 3：令：令=d,.,e,+,-=d,.,e,+,-，则，则上的无符号数上的无符号数的正则式表示为：的正则式表示为：164.2.3 4.2.3 程序设计语言中的正则表达式程序设计语言中的正则表达式例1：数字集D=0,1,9和字母集L=A|Z|a|z例2：整常数的集合IntC可表示为：例3：实常数的集合RealC可表示为：“”读作“定义定义为为”17例5：由/开始并以Eol（行结束符）结束的注释，可用正则表达式定义为如下：例4：由字母、数字和下划线组成，由字母为首，以字母或数字结束，且下划线不相连的标识符之集IDE可表示为如下：18 192021v 结点代表状态，用圆圈表示。

3、v 状态之间用箭弧连结，箭弧上的标记(字符)代表在射出结点(即箭弧始结点)状态下可能出现的输入字符或字符类。v 一张转换图只包含有限个状态(即有限个结点)，其中一个为初态，至少一个为终态(双圈表示)。状态转换图状态转换图状态转换图是设计词法分析程序的一种好途径。状态转换图是设计词法分析程序的一种好途径。状态转换图，一张有限方向图，规定：状态转换图，一张有限方向图，规定：22例3：识别整数的转换图（如右上图）例2：识别标识符的转换图（如左下图）字母字母01字母或数字字母或数字数字数字01数字数字表示：在状态1下，若输入字符为x，则读进x，并转换到状态2； 若输入字符为y，则读进y，并转换到状态3

4、。132xy例1：2324它所对应的状态转移矩阵如图：一个一个DFADFA可用一个矩阵表示，该矩阵的行表示状态，可用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示列表示输入字符，矩阵元素表示(s,a)(s,a)的值，这个的值，这个矩阵称状态转移矩阵。矩阵称状态转移矩阵。状态状态ab01213221333325状态转换图可用于识别（或接受）一定的字符串状态转换图可用于识别（或接受）一定的字符串aaa|b031bbab226a1a2an27NFA的形式定义为的形式定义为:28ABijABijkA|BijA*ijABijijkANFA替换规则替换规则NFA允许允许边出现边出现29=a

5、,b， 上所有含有两个相继的上所有含有两个相继的a或两或两个相继的个相继的b的字的集合的字的集合用用NFA表示如下表示如下：NFA M=( 0,1,2,3,4,5,6,7 , a,b , , 0 , 7 )其中其中如上（不可省略）(a|b)*aa|bb(a|b)*aa576bbab01234ba初态初态终态终态(a|b)* (aa|bb) (a|b)* 3031v（）合并）合并v符号合并符号合并转换函数初态NFA M (S,S0,F)SS的子集多值映射S0 S非空初态DFA M (S,s0,F)SS单值映射s0S唯一的初态NFA允许允许边出现边出现（）合并：）合并：如果有S1S2,则把S2状态

6、合并到S1状态。32例1：NFA转换成DFA (符号合并)例2：设计一个DFA，其输入字母表是0,1，它能接受以0开始，以1结尾的所有序列。aa3cb012a01,2cb30,10ZCSAB1解：解：根据题意，得出相应的正则式：0(0|1)*1 得状态转换图(NFA)如下：3301stateDFA stateSSSABCS,ABCS,ABCABCBCBCZ ABC,BC,BCZS,ABC,BC,BCZBCBCBCZ BC,BCZS,ABC,BC,BCZBCZBCBCZ BCZS,ABC,BC,BCZ(S,)=;(S,0)=？(S,0)=A; (A,)=B; (B,)=C; (C,)=； 0,10ZCSAB134得状态转换图(DFA)如下：000SCA101B1000SBCZABC101BC1在DFA中，所有含有NFA的终态的状态作为DFA的终态DFA M=( S,A,B,C , 0,1 , , S , C )其中其中如上（不可省略）353637初态初态3839404142v将所有DFA的终态与其它状态划分成两个子集G1,G2;v分别从两个子集G1,G2中寻找等价状态