编译原理 词法分析

1、1 第四章第四章: :词法分析词法分析 Lexical AnalysisLexical Analysis 2 3 4 第二遍第二遍单词串单词串 取单词取单词 优点优点: 结构清晰、各遍功能单一结构清晰、各遍功能单一 缺点：效率低缺点：效率低 5 6 2. 词法分析程序的输出形式词法分析程序的输出形式-单词的内部形式单词的内部形式 7 If (3, if) I (1, 8 9 10 11 12 13 =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,+,-，则，则上的无符号数上的无符号数 的正则式表示为：的正则式表示为： 16 4.2.3 4.2.3 程序设计语言中的正则表达式程序设计语言中的正则表达式 例1：数字集D=0,1,9和字母集L=A|Z|a|z 例2：整常数的集合IntC可表示为： 例3：实常数的集合RealC可表示为： “”读作“定义定义 为为” 17 例5：由/开始并以Eol（行结束符）结束的注释，可 用正则表达式定义为如下： 例4：由字母、数字和下划线组成，由字母为首，以 字母或数字结束，且下划线不相

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

4、数字数字 01 数字数字 表示：在状态1下，若输入字符 为x，则读进x，并转换到状态2； 若输入字符为y，则读进y，并转 换到状态3。 1 3 2x y 例1： 23 24 它所对应的状态转移矩阵如图： 一个一个DFADFA可用一个矩阵表示，该矩阵的行表示状态，可用一个矩阵表示，该矩阵的行表示状态， 列表示输入字符，矩阵元素表示列表示输入字符，矩阵元素表示(s,a)(s,a)的值，这个的值，这个 矩阵称状态转移矩阵。矩阵称状态转移矩阵。 状态状态ab 012 132 213 333 25 状态转换图可用于识别（或接受）一定的字符串状态转换图可用于识别（或接受）一定的字符串 aa a|b 031

5、 b b a b 2 26 a1a2 an 27 NFA的形式定义为的形式定义为: 28 AB ij AB ijk A|B ij A* ij A B ij ijk A NFA替换规则替换规则 NFA允许允许边出现边出现 29 =a,b， 上所有含有两个相继的上所有含有两个相继的a或两或两 个相继的个相继的b的字的集合的字的集合用用NFA表示如下表示如下： NFA M=( 0,1,2,3,4,5,6,7 , a,b , , 0 , 7 ) 其中其中如上（不可省略） (a|b)* aa|bb (a|b)* aa 576 b b a b 012 3 4b a 初态初态终态终态 (a|b)* (aa|

6、bb) (a|b)* 30 31 v（）合并）合并 v符号合并符号合并 转换函数初态 NFA M (S,S0,F) SS的子集 多值映射 S0 S 非空初态 DFA M (S,s0,F) SS 单值映射 s0S 唯一的初态 NFA允许允许 边出现边出现 （）合并：）合并：如果有S1S2,则把S2状态合并到S1状态。 32 例1：NFA转换成DFA (符号合并) 例2：设计一个DFA，其输入字母表是0,1，它能接受 以0开始，以1结尾的所有序列。 a a 3 c b 0 1 2 a 01,2 c b 3 0,1 0 ZCSAB 1 解：解：根据题意，得出相应的正则式：0(0|1)*1 得状态转换

7、图(NFA)如下： 33 01stateDFA state SS SABCS,ABCS,ABC ABCBCBCZ ABC,BC,BCZS,ABC,BC,BCZ BCBCBCZ BC,BCZS,ABC,BC,BCZ BCZBCBCZ BCZS,ABC,BC,BCZ (S,)=; (S,0)=？ (S,0)=A; (A,)=B; (B,)=C; (C,)=； 0,1 0 ZCSAB 1 34 得状态转换图(DFA)如下： 0 0 0 S C A 10 1 B 1 0 0 0 S BCZ ABC 10 1 BC 1 在DFA中，所 有含有NFA的 终态的状态作 为DFA的终态 DFA M=( S,A,B,C , 0,1 , , S , C ) 其中其中如上（不可省略） 35 36 37 初态初态 38 39 40 41 42 v将所有DFA的终态与其它状态划分成两个子集G1,G2; v分别从两个子集G1,G2中寻找等价状态进行化简。 43 v将所 有DFA 的终态 与其它 状态划