compiler4_词法分析

1、第二章第二章 词法分析词法分析 本章内容本章内容 词法分析器：把构成源程序的字符流翻译成词法分析器：把构成源程序的字符流翻译成 记号流，记号流，还完成和用户接口的一些任务还完成和用户接口的一些任务 围绕词法分析器的自动生成展开围绕词法分析器的自动生成展开 介绍正规式、状态转换图和有限自动机概念介绍正规式、状态转换图和有限自动机概念 词法分析器词法分析器 语法分析器语法分析器 符号表符号表 记号记号 取下一个记号取下一个记号 源程序源程序 2.1 词法记号及属性词法记号及属性 2.1.1 词法记号、模式、词法单元词法记号、模式、词法单元 词法记号词法记号词法单元例举词法单元例举模式的非形式描述模

2、式的非形式描述 var var var for for for relation , = , = , 或或 0） 2.2 词法记号的描述与识别词法记号的描述与识别 语言的运算语言的运算 和：和：LM = s | s L 或或 s M 连接：连接：LM = st | s L 且且 t M 指数：指数：L0是是 ，Li是是Li -1L 闭包：闭包：L L = = L L0 L L1 L L2 正闭包正闭包： L L+ = = L L1 L L2 例例 L: A, B, , Z, a, b, , z , D: 0, 1, , 9 LD, LD, L6, L*, L(LD )*, D+ 2.2 词法记

3、号的描述与识别词法记号的描述与识别 2.2.2 正规式正规式 正规式正规式用来表示简单的语言，用来表示简单的语言，叫做叫做正规集正规集 正规式正规式定义的语言定义的语言备注备注 a a a (r) | (s)L(r)L(s) r和和s是正规式是正规式 (r)(s)L(r)L(s) r和和s是正规式是正规式 (r)*(L(r)* r是正规式 是正规式 (r)L(r) r是正规式是正规式 (a) (b)*)| (c)可以写成可以写成ab*| c 2.2 词法记号的描述与识别词法记号的描述与识别 正规式的例子正规式的例子 = = a, b a | ba, b (a | b) (a | b )aa,

4、ab, ba, bb aa | ab | ba | bbaa, ab, ba, bb a*由字母由字母a构成的所有串集构成的所有串集 (a | b)*由由a和和b构成的所有串集构成的所有串集 复杂的例子复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：01001101000010000010111001 2.2 词法记号的描述与识别词法记号的描述与识别 2.2.3 正规定义正规定义 对正规式命名，使表示简洁。对正规式命名，使表示简洁。 d1 r1 d2 r2 . . . dn rn 各个各个di的名字都不同的名字都不同 每个

5、每个ri都是都是 d1, d2, , di-1 上的正规式上的正规式 2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例子 Pascal语言的标识符集合语言的标识符集合 letter A | B | | Z | a | b | | z digit 0 | 1 | | 9 id letter( (letter| |digit) )* =a,b=a,b，上的正规式和相应的正规集如下上的正规式和相应的正规集如下： 例例 2 2：令令=A,B,0,1=A,B,0,1，则，则： 例例 3 3：令令=d,.,e,+,-=d,.,e,+,-，则，则上的无符号数的正规式上的无符号数的

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

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

8、2； 若输入字符为y，则读进y，并转 换到状态3。 1 3 2x y 例1： 2.3 有有 限限 自自 动动 机机 2.3.1 不确定的有限自动机（简称不确定的有限自动机（简称NFA） 一个数学模型，它包括一个数学模型，它包括: : 状态集合状态集合S； 输入符号集合输入符号集合 ； 转换函数转换函数move : S ( ) P(S)； 状态状态s0是开始状态；是开始状态； F S是接受状态集合是接受状态集合。 NFA的形式定义为的形式定义为: AB ij AB ijk A|B ij A* ij A B ij ijk A NFA替换规则替换规则 NFA允许允许边出现边出现 =a,b， 上所有含

9、有两个相继的上所有含有两个相继的a或两或两 个相继的个相继的b的字的集合的字的集合用用NFA表示如下表示如下： (a|b)* (aa|bb) (a|b)* 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|bb) (a|b)* 2.3 有有 限限 自自 动动 机机 12 开始开始a 0 a b b 识别语言识别语言 (a|b)*ab 的的NFA 输输 入入 符符 号号 ab 00, 10 1 2 2 状状

10、 态态 NFA的转换表的转换表 2.3 有有 限限 自自 动动 机机 例例 识别识别aa* *| |bb* *的的NFA 12 开始开始 a 0 a b b 3 4 2.3 有有 限限 自自 动动 机机 2.3.2 确定的有限自动机（简称确定的有限自动机（简称DFA) ) 一个数学模型，包括：一个数学模型，包括： 状态集合状态集合S； 输入字母表输入字母表 ； 转换函数转换函数move : S S； 唯一的初态唯一的初态 s S； 终态集合终态集合F S； 12 开始开始a 0 a b b a b 识别语言识别语言 (a|b)*ab 的的DFA 它所对应的状态转移矩阵如图： 一个一个DFADF

11、A可用一个矩阵表示，该矩阵的行表示状态，可用一个矩阵表示，该矩阵的行表示状态， 列表示输入字符，矩阵元素表示列表示输入字符，矩阵元素表示(s,a)(s,a)的值，这个的值，这个 矩阵称状态转移矩阵。矩阵称状态转移矩阵。 状态状态ab 012 132 213 333 状态转换图可用于识别（或接受）一定的字符串状态转换图可用于识别（或接受）一定的字符串 aa a|b 031 b b a b 2 a1a2 an v（）合并）合并 v符号合并符号合并 转换函数初态 NFA M (S,S0,F) SS的子集 多值映射 S0 S 非空初态 DFA M (S,s0,F) SS 单值映射 s0S 唯一的初态

12、NFA允许允许 边出现边出现 （）合并：）合并：如果有S1S2,则把S2状态合并到S1状态。 例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 得状态转换图(NFA)如下： 01stateDFA state SS,ABC SABCS,ABCS,ABC ABCBCBCZ ABC,BC,BCZS,ABC,BC,BCZ BCBCBCZ BC,BCZS,ABC,BC,BCZ BCZBCBC

13、Z BCZS,ABC,BC,BCZ (S,)=; (S,0)=？ (S,0)=A; (A,)=B; (B,)=C; (C,)=； 0,1 0 ZCSAB 1 01stateDFA state SS,ABC SABCS,ABCS,ABC ABCBCBCZ ABC,BC,BCZS,ABC,BC,BCZ BCBCBCZ BC,BCZS,ABC,BC,BCZ BCZBCBCZ BCZS,ABC,BC,BCZ 0,1 0 ZCSAB 1 (ABC,0) 初态初态 (S,0) 得状态转换图(DFA)如下： 0 0 0 S C A 10 1 B 1 0 0 0 S BCZ ABC 10 1 BC 1 在DF

14、A中，所 有含有NFA的 终态的状态作 为DFA的终态 DFA M=( S,A,B,C , 0,1 , , S , C ) 其中其中如上（不可省略） 初态初态 v将所有DFA的终态与其它状态划分成两个子集G1,G2; v分别从两个子集G1,G2中寻找等价状态进行化简。 v将所 有DFA 的终态 与其它 状态划 分成两 个子集 例2：设计一个DFA，其输入字母表是0,1，它能接受 以0开始，以1结尾的所有序列。化简 01 SABC ABCBCBCZ BCBCBCZ BCZBCBCZ 01 SABC ABCABCBCZ BCZABCBCZ DFA M=( S,ABC,BCZ , 0,1 , ,S,

15、 BCZ )其中其中如上(不可省略) 0 0 SBCZ ABC 0 1 1 0 0 5 3 1 1 2 4 0,1 1 0,1 0,1 0 1 b ba b 7 2 3 86145 b b a 注：状态从18标注 * 附：部分程序伪码附：部分程序伪码 (1)(1)用转换表构造用转换表构造DFADFA State:=Initstate; /初态 Read(CurrentChar); /上字符(源程序字符) While T(State,CurrentChar)error Read(CurrentChar); If StateFinalStates then Accept else Error T(State,CurrentChar)：转换函数 (2)(2) NFA NFA到到DFADFA的转换的转换()()合并合并 ss:NFA的一个状态集; Close(ss):表示()合并后的状态集; PROCEDURE Close(ss:NFA_state) BEGIN new:=1; While new:=1 do If (存在Sjss DA:DFA_state) BEGIN 1 DA.init_state=Close(NA.initial_states); DA.states:=DA.init_state ; States:=DA.init_state; 2 选择一个新元素