编译原理—chapter2

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

2、形式描述模式的非形式描述 if if 字符字符i, f for for字符字符f, o, r relation , = , = , 或或 = 或或 = 或或 id sum, count, D5由字母开头的字母数字串由字母开头的字母数字串 number 3.1, 10, 2.8 E12任何数值常数任何数值常数 literal“seg. error” 引号引号“和和”之间的任意字符之间的任意字符 串，但引号本身除外串，但引号本身除外 2.1 词法记号及属性词法记号及属性 历史上词法定义中的一些问题历史上词法定义中的一些问题 忽略空格带来的困难忽略空格带来的困难 DO 8 I 3. 75 DO8I

3、3. 75 DO 8 I 3, 75 关键字不保留关键字不保留 IF THEN THEN THEN=ELSE；ELSE 关键字、保留关键字、保留字和字和标准标识符的区别标准标识符的区别 保留保留字字是语言预先确定了含义的词法单元是语言预先确定了含义的词法单元, 如如if 标准标识符也是预先确定了含义的标识符，但程标准标识符也是预先确定了含义的标识符，但程 序可以重新声明它的含义序可以重新声明它的含义 2.1 词法记号及属性词法记号及属性 2.1.2 词法记号的属性词法记号的属性 position = initial + rate 60的的序列：序列： id，指向符号表中指向符号表中positi

4、on条目的指针条目的指针 assign _ op id，指向符号表中指向符号表中initial条目的指针条目的指针 add_op id，指向符号表中指向符号表中rate条目的指针条目的指针 mul_ op number，整数值整数值60 2.1 词法记号及属性词法记号及属性 2.1.3 词法错误词法错误 词法分析器对源程序采取非常局部的观点词法分析器对源程序采取非常局部的观点 难以发现下面的错误难以发现下面的错误 fi (a = f (x) ) 在实数是在实数是a.b格式下，可以发现下面的错误格式下，可以发现下面的错误 123. 2.2 词法记号的描述与识别词法记号的描述与识别 2.2.1 串

5、和语言串和语言 字母表：符号的有限集合，字母表：符号的有限集合， 例：例： = 0, 1 串：符号的有穷序列，例：串：符号的有穷序列，例：0110, 语言：字母表上的一个串集语言：字母表上的一个串集 , 0, 00, 000, , , 句子和字句子和字：属于语言的串：属于语言的串 串的运算串的运算 连接连接xy，s = s = s 积积（指数）（指数） s0为为 ，si为为si -1s（i 0） 2.2 词法记号的描述与识别词法记号的描述与识别 语言的运算语言的运算 和：和：L M = s | s L 或或 s M 连接连接：LM = st | s L 且且 t M 指数：指数：L0是是 ，L

6、i是是Li -1L 闭包：闭包：L = L0 L1 L2 正闭包：正闭包： L+ = L1 L2 例例 L: A, B, , Z, a, b, , z , D: 0, 1, , 9 L D, LD, L6, L*, L(L D )*, D+ 2.2 词法记号的描述与识别词法记号的描述与识别 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)可

7、以写成可以写成ab*| c 正规式正规式用来表示简单的语言，用来表示简单的语言，叫做叫做正规集正规集 2.2 词法记号的描述与识别词法记号的描述与识别 正规式的例子正规式的例子 = = a, b a | ba, b (a | b) (a | b )aa, ab, ba, bb aa | ab | ba | bbaa, ab, ba, bb a*由字母由字母a构成的所有串集构成的所有串集 (a | b)*由由a和和b构成的所有串集构成的所有串集 复杂的例子复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：01001101000

8、0100000101110011？ 2.2 词法记号的描述与识别词法记号的描述与识别 2.2.3 正规定义正规定义 对正规式命名，使表示简洁对正规式命名，使表示简洁 d1 r1 d2 r2 . . . dn rn 各个各个di的名字都不同的名字都不同 每个每个ri都是都是 d1, d2, , di-1 上的正规式上的正规式 2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例子 C语言的标识符是字母、数字和下划线组成的串语言的标识符是字母、数字和下划线组成的串 letter_ A | B | | Z | a | b | | z | _ digit 0 | 1 | | 9

9、 id letter_( (letter_ | |digit) )* 2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子正规定义的例子 无符号数集合，例无符号数集合，例1946, ,11.28, ,63E8, ,1.99E 6 digit 0 | 1 | | 9 digits digit digit* optional_fraction . .digits| | optional_exponent ( E ( + | | ) digits ) | number digits optional_fraction optional_exponent 简化表示简化表示 number d

10、igit+ (.digit+)? (E(+| )? digit+)? 这里这里r?=r| r?=r| 2.2 词法记号的描述与识别词法记号的描述与识别 正规定义的例子（进行下一步讨论的例子）正规定义的例子（进行下一步讨论的例子） while while do do relop | = | = | | | = letter A | B | | Z | a | b | | z id letter (letter | digit )* number digit+ (.digit+)? (E (+ | )? digit+)? delim blank | tab | newline ws delim+

11、识别记号 词法分析器词法分析器 语法分析器语法分析器 符号表符号表 记号记号(token) 取下一个记号取下一个记号 源程序源程序 描绘了语法分析器为了得到下一个记号而调用词法分析 器时，词法分析器所做的动作。 状态转化图 2.2 词法记号的描述与识别词法记号的描述与识别 2.2.4 转换图转换图 关系算符的转换图关系算符的转换图 0 5 1 6 2 4 8 3 7 return(relop, LE) return(relop, NE) return(relop, LT) return(relop, GE) return(relop, GT) return(relop, EQ) 开始开始 =

12、= * * other other 2.2 词法记号的描述与识别词法记号的描述与识别 标识符和保留字的转换图标识符和保留字的转换图 91011 开始开始 letterother * letter或或digit return(installId( ) 2.2 词法记号的描述与识别词法记号的描述与识别 无符号数的转换图无符号数的转换图 开始开始 19 12 131415161718 digit digit digit digit digit digit other .E+/ E digit other other return( installNum( ) ) * number digit+ (.

13、 .digit+)? (E (+ | )? digit+)? 2.2 词法记号的描述与识别词法记号的描述与识别 空白空白的转换图的转换图 delim blank | tab | newline ws delim+ 21 22 开始开始delimother * delim 20 词法分析器代码示例 有限自动机 (语言)识别器 字符串x Y/N? 有限 自动机 不确定有限自动机 确定有限自动机 （Nondeterministic Finite Automata） （Deterministic Finite Automata） 2.3 有有 限限 自自 动动 机机 2.3.1 不确定的有限自动机（简

14、称不确定的有限自动机（简称NFA） 一个数学模型，它包括：一个数学模型，它包括： 1、状态集合、状态集合S 2、输入符号集合、输入符号集合 3、转换函数、转换函数move : S ( ) P(S), P(S)是是S的幂集的幂集 4、状态、状态s0是唯一开始状态是唯一开始状态 5、F S是接受（终止）状态集合是接受（终止）状态集合 识别语言识别语言 (a|b)*ab 的的NFA 12 开始开始a 0 a b b 12 开始开始a 0 a b b 识别语言识别语言 (a|b)*ab 的的NFA 输输 入入 符符 号号 ab 00, 10 12 2 状状 态态 NFA的转换表的转换表 2.3 有有

15、限限 自自 动动 机机 2.3 有有 限限 自自 动动 机机 例例 识别识别aa* *| |bb* *的的NFA 12 开始开始 a 0 a b b 3 4 2.3.2 确定的有限自动机（简称确定的有限自动机（简称DFA) ) 一个数学模型，包括：一个数学模型，包括： 1、状态集合、状态集合S 2、输入字母表、输入字母表 3、转换函数、转换函数move : S S 4、唯一的初态、唯一的初态 s S 5、终态集合、终态集合F S 12 开始开始a 0 a b b a b 识别语言识别语言 (a|b)*ab 的的DFA 2.3 有有 限限 自自 动动 机机 1、没有 转换,必须有符号； 2、任何

16、状态s和字符a， 最多只有一条标记离开 画出画出DFA, ,接受接受 0和和1的个数都是偶数的字符串的个数都是偶数的字符串 3 1 2 0 1 1 1 1 0000 开始开始 偶偶0偶偶1 奇奇0奇奇1奇奇0偶偶1 偶偶0奇奇1 2.3 有有 限限 自自 动动 机机 例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 2.3 有有 限限 自自 动动 机机 1010111000 1010 111000 10101 11000 1010111000被能被能5整除整除？ 例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123

17、开始开始 4 0 2.3 有有 限限 自自 动动 机机 例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 2.3 有有 限限 自自 动动 机机 例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 2.3 有有 限限 自自 动动 机机 例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 2.3 有有 限限 自自 动动 机机 例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1

18、 0 0 1 0 2.3 有有 限限 自自 动动 机机 例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 0 1 2.3 有有 限限 自自 动动 机机 例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 0 1 0 2.3 有有 限限 自自 动动 机机 例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 0 1 0 1 2.3 有有 限限 自自 动动 机机 例：识别例：识别 =0,1上能被能上能被能5整除的二

19、进制数整除的二进制数 0123 开始开始 4 1 0 0 1 0 1 0 1 0 2.3 有有 限限 自自 动动 机机 例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 0 1 0 1 0 1 2.3 有有 限限 自自 动动 机机 例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 0 1 0 1 0 1 2.3 有有 限限 自自 动动 机机 10102 = 1010 余余0 1112 = 710 余余21010111000余？余？ 2.3 有有 限限 自自 动动 机机

20、 输输 入入 符符 号号 ab 00, 10 12 2 2.3.3 NFA到到DFA的变换的变换 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法 1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合 2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk 2.3 有有 限限 自自 动动 机机 (a|b)*ab 的的NFA 1 2 a 开始开始 0 a b b 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法 1、DFA的一个状态是的一个状

21、态是NFA的一个状态集合的一个状态集合 2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk 1 2 a 开始开始 0 a b b00, 1 a 2.3 有有 限限 自自 动动 机机 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法 1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合 2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk

22、1 2 a 开始开始 0 a b b00, 1 a b 2.3 有有 限限 自自 动动 机机 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法 1、DFA的一个状态是的一个状态是NFA的一个状态集合的一个状态集合 2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk 1 2 a 开始开始 0 a b b00, 1 a b a 2.3 有有 限限 自自 动动 机机 2.3.3 NFA到到DFA的变换的变换 子集构造法子集构造法 1、DFA的一个状态是的一个状态是NFA的

23、一个状态集合的一个状态集合 2、读了输入、读了输入a1 a2 an后后， NFA能到达的所有状态：能到达的所有状态：s1, s2, , sk，则则 DFA到达状态到达状态s1, s2, , sk 1 2 a 开始开始 0 a b b00, 1 a b a 0, 2 b 2.3 有有 限限 自自 动动 机机 NFA状态上的运算 -closure(s): 从从NFA开始状态开始状态s出发，经出发，经 转化能达到的转化能达到的NFA状态集合状态集合 -closure(T)： 从从NFA状态集合状态集合T中某个状态中某个状态s出发，经出发，经 转化能达到的转化能达到的NFA 状态集合状态集合 move

24、(T,a)： 从从NFA状态集合状态集合T中某个状态中某个状态s出发，经标记出发，经标记a的的转化能达到转化能达到 的的NFA状态集合状态集合 2.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 45 输入符号输入符号 ab 状态状态 1. N 属于属于 T= -closure(s0)状态状态 2. N 移动到移动到 move(T,a)中任一个状态中任一个状态 3. N 可到达可到达 T= -closure(move(T,a) 中任一个状态中任一个状态 2.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 45 输入符号输入

25、符号 ab A 状态状态 A = 0, 1, 2, 4, 7 2.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 45 输入符号输入符号 ab AB 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 2.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 45 输入符号输入符号 ab AB B 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 2.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 45 输入

26、符号输入符号 ab ABC B 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 2.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 45 输入符号输入符号 ab ABC B C 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 2.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 45 输入符号输入符号 ab ABC BB C 状态状态 A = 0, 1

27、, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 2.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 45 输入符号输入符号 ab ABC BBD C 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 2.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 45 输入符号输入符号 ab ABC BBD C D 状态状态 A = 0, 1

28、, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 2.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 45 输入符号输入符号 ab ABC BBD CBC D 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 2.3 有有 限限 自自 动动 机机 1 9 开始开始 0 a b ab 678 23 45 输入符号输入符号

29、ab ABC BBD CBC DBC 状态状态 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 2.3 有有 限限 自自 动动 机机 BD 开始开始a A a b b a b C b a 19 开开 始始 0 a b ab 678 23 45 输入符号输入符号 ab ABC BBD CBC DBC 状态状态 2.3 有有 限限 自自 动动 机机 BD 开始开始a A a b b a b C b a 12 开始开始a 0 a b b a b 1 9 开始开始 0 a b

30、ab 678 23 45 识别语言识别语言 (a|b)*ab 的的自动机自动机 2.3 有有 限限 自自 动动 机机 BD 开始开始a A a b b a b C b a 12 开始开始a 0 a b b a b 1 9 开始开始 0 a b ab 678 23 45 识别语言识别语言 (a|b)*ab 的的自动机自动机 子集构造法不一子集构造法不一 定得到最简定得到最简DFA 2.4 从正规式到有限自动机从正规式到有限自动机 从正规式建立识别器从正规式建立识别器 从正规式构造从正规式构造NFA 用语法制导的算法，它用正规式语法结构来指用语法制导的算法，它用正规式语法结构来指 导构造过程导构造

31、过程 把把NFA变成变成DFA （子集构造法）子集构造法） 将将DFA化简化简 （合并不可区别状态）（合并不可区别状态） 2.4 从正规式到有限自动机从正规式到有限自动机 首先构造识别首先构造识别 和字母表中一个符号的和字母表中一个符号的NFA i 开始开始 识别正规式识别正规式 的的NFA a fif 开始开始 识别正规式识别正规式a的的NFA 2.4 从正规式到有限自动机从正规式到有限自动机 构造识别主算符为选择的正规式的构造识别主算符为选择的正规式的NFA f i 开始开始 识别正规式识别正规式s | t的的NFA N (s) N (t) 2.4 从正规式到有限自动机从正规式到有限自动机

32、 构造识别主算符为连接的正规式的构造识别主算符为连接的正规式的NFA i N (s) f 开始开始 识别正规式识别正规式st 的的NFA N (t) 2.4 从正规式到有限自动机从正规式到有限自动机 构造识别主算符为闭包的正规式的构造识别主算符为闭包的正规式的NFA N (s) f 开始开始 识别正规式识别正规式s* 的的NFA i 2.4 从正规式到有限自动机从正规式到有限自动机 对于加括号的正规式对于加括号的正规式(s)，使用使用N(s)本身作为本身作为 它的它的NFA。 2.4 从正规式到有限自动机从正规式到有限自动机 本方法产生的本方法产生的NFA有有下列性质下列性质: : N(r)的

33、状态数最多是的状态数最多是r中符号和算符总数的两倍中符号和算符总数的两倍 N(r)只有一个开始状态和一个接受状态，接受状只有一个开始状态和一个接受状态，接受状 态没有向外的转换态没有向外的转换 N(r)的每个状态有一个用的每个状态有一个用 的符号标记的指向其的符号标记的指向其 它结点的转换，或者最多两个指向其它结点的它结点的转换，或者最多两个指向其它结点的 转换转换 2.4 从正规式到有限自动机从正规式到有限自动机 1 9 开始开始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 2.4 从正

34、规式到有限自动机从正规式到有限自动机 1 9 开始开始 0 ab 678 a b 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 2.4 从正规式到有限自动机从正规式到有限自动机 1 9 开始开始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 2.4 从正规式到有限自动机从正规式到有限自动机 1 9 开始开始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a |

35、b a b (a|b)*ab的分解的分解 2.4 从正规式到有限自动机从正规式到有限自动机 1 9 开始开始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 2.4 从正规式到有限自动机从正规式到有限自动机 1 9 开始开始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 2.4 从正规式到有限自动机从正规式到有限自动机 1 9 开始开始 0 a b ab 678 23 45 r9 r7 r8

36、 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 2.4 从正规式到有限自动机从正规式到有限自动机 (a|b)*ab的两个的两个NFA的比较的比较 1 2 开始开始a 0 a b b 1 9 开始开始 0 a b ab 678 23 45 手工构造手工构造: 算法构造算法构造: 2.4 从正规式到有限自动机从正规式到有限自动机 小结：从正规式建立识别器的步骤小结：从正规式建立识别器的步骤 从正规式构造从正规式构造NFA 把把NFA变成变成DFA 将将DFA化简化简 存在其它办法存在其它办法 2.5 词法分析器的生成器词法分析器的生成器 Lex(le

37、xical analyzer generator) 用用Lex建立词法分析器的步骤建立词法分析器的步骤 Lex 编译器编译器 Lex源程序源程序lex.l lex.yy.c C 编译器编译器 lex.yy.ca.out a.out 输入流输入流 记号序列记号序列 2.5 词法分析器的生成器词法分析器的生成器 Lex程序包括三个部分程序包括三个部分 声明声明 翻译规则翻译规则 辅助过程辅助过程 Lex程序的翻译规则程序的翻译规则 p1动作动作1 p2动作动作2 pn动作动作n 2.5 词法分析器的生成器词法分析器的生成器 例例-声明部分声明部分 % /* * 常量常量LT, LE, EQ, NE

38、, GT, GE, WHILE, DO, ID, NUMBER, RELOP的定义的定义* */ % /* * 正规定义正规定义 * */ delim t n wsdelim+ letterA Za z digit0 9 idletter(letter|digit)* * numberdigit+( .digit+)?(E+ ?digit+)? 2.5 词法分析器的生成器词法分析器的生成器 例例-翻译规则部分翻译规则部分 ws/* * 没有动作，也不返回没有动作，也不返回 * */ whilereturn (WHILE); doreturn (DO); idyylval = install_i

39、d ( ); return (ID); numberyylval = install_num( ); return (NUMBER); “ ”yylval = LT; return (RELOP); “ = ” yylval = LE; return (RELOP); “ = ”yylval = EQ; return (RELOP); “ ”yylval = NE; return (RELOP); “ ”yylval = GT; return (RELOP); “ = ”yylval = GE; return (RELOP); 2.5 词法分析器的生成器词法分析器的生成器 例例-辅助过程部分辅

40、助过程部分 install_ id ( ) /* * 把词法单元装入符号表并返回指针。把词法单元装入符号表并返回指针。 yytext指向该词法单元的第一个字符，指向该词法单元的第一个字符， yyleng给出的它的长度给出的它的长度* */ install_num ( ) /* * 类似上面的过程，但词法单元不是标识符而是类似上面的过程，但词法单元不是标识符而是 数数 * */ 本本 章章 要要 点点 词法分析器的作用和接口，用高级语言编写词词法分析器的作用和接口，用高级语言编写词 法分析器等内容，它们与词法分析器的实现有法分析器等内容，它们与词法分析器的实现有 关关 掌握下面涉及的一些概念，它们之间转换的技掌握下面涉及的一些概念，它们之间转换的技 巧、方法或算法巧、方法或算法 非形式描述的语言非形式描述的语言 正规式正规式 正规式正规式 NFA 非形式描述的语言非形式描述的语言 NFA NFA DFA DFA 最简最简DFA 非形式描述的语言非形式描述的语言 DFA（或最简或最简DFA） 例例 题题 1 叙述下面的正规式描述的语言，并画出接受叙述下面的正规式描述的语言，并画出接受