编译原理 Compiler Principles 第三章 词法分析 湖南大学信息科学与工程学院 软件工程系 杨金民 2019/02.

Presentation on theme: "编译原理 Compiler Principles 第三章 词法分析 湖南大学信息科学与工程学院 软件工程系 杨金民 2019/02."— Presentation transcript:

1 编译原理 Compiler Principles 第三章 词法分析 湖南大学信息科学与工程学院 软件工程系 杨金民 2019/02

2 第三章 词法分析 1. 词法分析的含义； 2. 词法分析的基本概念； 3. 正则表达式——词法单元模式的表达； 4. 状态转换图；
第三章 词法分析 1. 词法分析的含义； 2. 词法分析的基本概念； 3. 正则表达式——词法单元模式的表达； 4. 状态转换图； 5. 词法分析器构造工具； 6. 有穷状态自动机； 7. 从正则表达式到NFA，DFA的映射方法；

3 词法分析 词法分析/扫描（lexical analysis, scanning） 高级语言程序的源文件（文本文件），可将其看作字符流。
对源程序文件中的字符流进行扫描，切分成为词素流； 例如：return (initial<=10)?100:(position+initial**2）; return ( initial <= 10 ) ? 100 : ( position + initial ** 2 ) ;

4 语言中的词法单元 词素流 （标识符流） 文本文件 (字符流) 词法分析程序
return ( initial <= 10 ) ? 100 : ( position + initial ** 2 ) ; forward begin 目标：高效能：一次扫描解决

5 语言中的词法单元 id 词法 预定义符 自定义符 保留字 运算符 标点符 特义符 变量 常量 ； “ ... if while int
数据变量 函数变量 预定义符：相互独立，没有相交性。 语法主要通过预定义符来体现和标识。

6 词法分析 例如：return (initial<=10)?100:(position+initial**2）; 词素流：符号表：
row_id name type class row_num 1 return 预留 保留字 120 2 ( 特义符 3 initial 自定义 变量 4 <= 运算符 5 10 常量 6 ？ 标点符号

7 词法分析要解决的问题 要解决的问题：如何从字符流切分识别为词素流。
return ( initial <= 10 ) ? 100 : ( position + initial ** 2 ) ; forward begin 词法单元的模式：从左到右的字符序列，在其组成上的约束条件。 如果一个字符串匹配某个词法单元的模式，就说它是该词法单元的一个实例，称之为词素 如何描述词法单元的模式？  正则表达式

8 语法分析中的三个概念 词法单元（token)：词素的类概念，例如，自定义符； 词素(lexme)：字符序列；
词法单元的实例；例如，上例中的position，initial。 词法单元的模式(pattern) 词法单元的构成规约；

9 程序语言中词法单元的模式 customed identifier:
变量：以字母或者下划线开头，接任意多个字母、下划线， 数字；例如： i ； _if ; if3; 数值常量：例如：0.1; 32; 49.8; 3.6E8; 0.5E-2; 8.9E+5; 字符常量：引号括起来的字符串 ； reserved keywords: if; else; do; while; for; else if +; - ; * ; / ; ** ; ++； +- =; ==; <; <=; >; >= ; != ； ， “ ” ‘ ’ blank; tab; newline

10 模式表达中的概念 字符（character)：字符集，例如，ASCII字符集：字母集，数字集，标点符号集；
串(string): 某个字符集下的字符串。注意：串不是集合。 串s的长度记为|s|。空串用ε表示。 语言(language）：串的集合。 在语言中，串有语义。 字，词，句，段，文都是串。 例如：C语言， Java语言，英语，汉语。，{a}是语言。 串s的前缀(prefix), 后缀(suffix), 子串(substring), 子序列(subsequence): 去掉了一些其中的字符。

11 串的运算 串的连接运算：也叫“乘积”运算，串x连接串y记为xy。结果还是为串。
例如， x=my, y =house, 那么xy =myhouse； 自然有：sε = εs = s 串的“指数”运算： si = si-1s; s0 = ε 例如， x=my, 那么x3 =mymymy； 表达串接特性 常量合并，复写传播 表达重复串接性

12 语言的运算 并运算，联接，闭包三种运算： 结果还是为语言。语言L和M 并运算：LM = L | M = {s| sL 或者 sM｝；
联接运算： LM = ｛st ｜ sL ， tM｝； 闭包运算：L的Kneene闭包： L的正闭包： 可选性 串接性 串接的重复出现性 例如：个位整数：1|2|3|4|5|6|7|8|9 两位整数：(1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9) 整数：(1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)*

13 思考的问题 L= {A, B,...,Z, a,b, ...., z}, D = {0,1,2,3,4,5,6,7,8,9} LD ，LD中包含的串元素的个数各为多少？ L0=｛ε｝。L4， L*， D+， L(LD)*分别是什么？

14 语言运算的例子 L= {A, B,...,Z, a,b, ...., z}, D = {0,1,2,3,4,5,6,7,8,9}
LD = {A, B,...,Z, a,b, ...., z, 0,1,2,3,4,5,6,7,8,9}； (LD)2 = (LD)(LD) = {AA, AB, Az, A0, A9,...., 9A,9B, 99}，其中的串元素各个数为： (LD)* = {ε}  (LD)  (LD)2  ...  (LD) 因此，L(LD)*是以字母开头，由字母和数字组成的串的集合。 注意：(LD)n和(LD)*,(LD)+是完全不同的概念

15 正则表达式—描述串接约束—词法单元的模式
语言运算表达式就称作正则表达式(Regular expression)： 表达式中通常是变量(斜体字)运算表达式. 并运算符：或｜。 语言运算的结合律和交换律，不言而喻；但(a|b)* ≠ a*| b* 三种运算的优先级：*(+) > 联接 > 或｜ 正则表达式也可给它取一个名字，随后用于其它正则表达式： 例如，C语言的自定义标示符的一个正则定义可以是： letter_ → A | B | ... | Z | a | b | ... | z | _ digit → 0 | 1 | 2 | ... | 9 id → letter_ (letter_ | digit)*

16 正则表达式表达词法单元的模式 digit → 0 | 1 | 2 | ... | 9
digits → digit digit* = digit+ optionalFraction → . digits | ε optionalExponent → (E(+ | - | ε ) digits) | ε number → digits optionalFraction optionalExponent 问题：01匹配number吗？ 1.0匹配number吗？ 1. 匹配number吗？

17 正则表达式的标记符扩展 基本运算符：并、连接、Kleene闭包(*) 扩展的标记符：
0个或多个实例： (r)* = r*r , r* = r+ | ε 1个或多个实例：(r)+ = rr* = r*r , r* = r+ | ε 0个或1个实例：ε | r = r? 字符类：连续的字符中的任选其一，例如 a1 | a2 | …| an = [a1a2…an] = [a1- an] a | b | c | d | e = [a - e] 仅仅只是使正则表达式更简洁。

18 简洁的正则表达式例子 letter_ → [A- Z a - z _ ] digit → [0 - 9] id → letter_ (letter_ | digit)* digits → digit+ number → digits (.digits )?( E [+ - ]? digits)?

19 正则表达式的特性——描述串接性问题 字符串在构成上的串接约束；这些串接约束必须相互独立，不能重贴交叉: 例如：asdfgghjkweyr38839ssdf 只能 不会 约束1 约束2 约束3 id → letter_ (letter_ | digit)* digits → digit+ number → digits (. digits )?( E [+ - ]? digits)?

20 程序语言的词法单元及其正则表达式 letter_ → [A- Z a - z _ ] digit → [0 - 9]
digits → digit+ customed identifier: id → letter_ (letter_ | digit)* number → digits (. digits )?( E [+ - ]? digits)? reserved keywords: if→ if else → else; operator→ = | < | > | == | <= | >= | != punctuation →； ｜，｜“ ｜” ｜‘ ｜’ space →( blank | tab | newline )+

21 随堂测试1 character → [A- Z a - z 0-9]
SQL语言中可模糊查询，比如： LIKE “zhang%”, 为模糊 查询，其中%可以在任意位置，请用正则表达式表达该类 模糊查询的模式。 IP地址例子为 ，即0~255的四个数用点隔开。请 写出IP地址得正则表达式。

22 正则表达式例子 digit → [0 - 9] id → letter_ (letter_ | digit)*
letter_ → [A- Z a - z _ ] digit → [0 - 9] id → letter_ (letter_ | digit)* digits → digit+ number → digits (.digits )?( E [+ - ]? digits)?

23 词法分析算法 return ( initial <= 10 ) ? 100 : ( position + initial ** 2 ) ; forward lexemeBegin string s= ε;  i, RE[i].math = true; //所有词法单元的正则表达式 while ( i, RE[i].math == true) { s = s + 下一个字符;  i, if (RE[i].math == true) if s does not math RE[i] RE[i].math = false; } Java的编译方式有两种，一种是和C++等语言一样的，把源代码编译成和本地机器平台相关的机器语言，叫即时编译。另一种是编译成一种中间的字节码，与机器平台无关的，这种也是常用的，叫解释型的。 得出了词素，也得出了它所属的词法单元

24 正则表达式的状态转换图 将字符流切分成词素流，表达了一个词素的获取过程。 < 2 4 return operator. <= 5
start = < > 1 other 2 3 8 9 6 7 4 * 5 return operator. > return operator. >= return operator. < return operator. <= return operator. = return operator. ==

25 词法单元的正则表达式的状态转换图 将字符流切分成词素流，表达了一个词素的获取过程。 < 2 4
start = < > 1 other 2 3 8 9 6 7 4 * 5 return operator. > return operator. >= return operator. < return operator. <= return operator. = return operator. == 状态转换图

26 正则表达式的状态转换图 正则表达式: id → letter_ (letter_ | digit)* start letter_ 10 .
letter_ 10 . other 11 letter_ | digit * 正则表达式: if → if Java的编译方式有两种，一种是和C++等语言一样的，把源代码编译成和本地机器平台相关的机器语言，叫即时编译。另一种是编译成一种中间的字节码，与机器平台无关的，这种也是常用的，叫解释型的。 not letter_ | digit i . * f start 23 24 25

27 正则表达式的状态转换图 正则表达式: number → digits (. digits )?( E [+ - ]? digits)? E
other 20 * start digit 13 . 14 15 16 +|- 17 18 19 21 Java的编译方式有两种，一种是和C++等语言一样的，把源代码编译成和本地机器平台相关的机器语言，叫即时编译。另一种是编译成一种中间的字节码，与机器平台无关的，这种也是常用的，叫解释型的。

28 正则表达式的兼容性vs最长匹配原则 正则表达式: id → letter_ (letter_ | digit)* start letter_
letter_ 10 . other 11 letter_ | digit * 正则表达式: if → if Java的编译方式有两种，一种是和C++等语言一样的，把源代码编译成和本地机器平台相关的机器语言，叫即时编译。另一种是编译成一种中间的字节码，与机器平台无关的，这种也是常用的，叫解释型的。 not letter_ | digit i . * f start 23 24 25

29 基于状态转换图的词法分析体系结构 if(area>=len*h/2-2) forward lexemeBegin
state = 0; while (1) { c = Char(forward); swith(state) { case 0: if (c is letter_ ) // id state =10; else if (c = '<') //operator state = 2; else if (c is digit) // number state =12; forward++； break; case 10: if (!(c is not letter_ or digit)) forward; find_id(lexemeBegin, forward -1); lexemeBegin = forward; } else forward++； if(area>=len*h/2-2) forward lexemeBegin letter_ 10 . other 11 letter_ | digit * 状态，以及输入字符驱动下的状态变迁

30 随堂测试2 1. 写出(a|b)*a(a|b)(a|b)的状态转换图。
2.对正则表达式: number → digits (. digits )?( E [+ - ]? digits)? E other 20 * start 12 digit 13 . 14 15 16 +|- 17 18 19 21 Java的编译方式有两种，一种是和C++等语言一样的，把源代码编译成和本地机器平台相关的机器语言，叫即时编译。另一种是编译成一种中间的字节码，与机器平台无关的，这种也是常用的，叫解释型的。 写出该状态转换图的词法分析程序。

31 3.5 词法分析器生成工具Lex 词法单元的正则表达式 → 状态转换图 → 词法分析代码 工具Lex 表达 生成 lex.l lex工具
词法单元的正则表达式 → 状态转换图 → 词法分析代码 工具Lex 表达 生成 lex.l lex工具 lex.yy.c C编译器 a.out 源程序的字符流 a.out 词素流

32 3.5 词法分析器生成工具Lex 词法单元的正则表达式 → 状态转换图 → 词法分析源程序 工具Lex 表达 生成 lex.l lex工具
词法单元的正则表达式 → 状态转换图 → 词法分析源程序 工具Lex 表达 生成 lex.l lex工具 lex.yy.c C编译器 a.out 源程序的字符流 a.out 词素流

33 词法分析器构造接下来要解决的问题 从正则表达式  状态转换图，在前面是手工构造的，
能否有一种方法（算法），以正则表达式表达式为输入，状态 转换图为输出呢？ 状态转换图有哪些类型？各种类型之间的关系如何？

34 正则表达式的状态转换图的分类 正则表达式: number → digits (. digits )?( E [+ - ]? digits)?
other 20 * start 12 digit 13 . 14 15 16 +|- 17 18 19 21 a b start 1 2 3 a Java的编译方式有两种，一种是和C++等语言一样的，把源代码编译成和本地机器平台相关的机器语言，叫即时编译。另一种是编译成一种中间的字节码，与机器平台无关的，这种也是常用的，叫解释型的。 (a|b)*abb

35 另一个例子 语言L((aa*|bb*)的状态转换图: 开始状态：一个 a 接受状态：可多个 转换函数 1 2 ε 边上的标号 start b
1 2 a ε 开始状态：一个 接受状态：可多个 转换函数 边上的标号 3 4

36 3.6 有穷自动机 将状态转换图形式化，上升为一种理论知识，被称作有穷自动机(finite automata)。为两类：
非确定有穷自动机NFA（Nondeterministic Finite Automata）。图中的某一状态结点，一个驱动符号（即边上的标号），可引出多条边， ε 可以是边上的标号。 确定性有穷自动机DFA（ Deterministic Finite Automata）：图中的状态结点，一个驱动符号，有且仅有一条出边。驱动符号不包含ε 。

37 NFA 正则表达式(a|b)*abb的NFA表示。NFA的图表示 开始状态：一个 a 接受状态：可多个 转换函数； 边上的标号。 start
1 2 3 NFA的表表示法：转换表

38 NFA的另一个例子 语言L((aa*|bb*)的NFA: 开始状态：一个 a 接受状态：可多个 转换函数 1 2 ε 边上的标号 start
1 2 a ε 开始状态：一个 接受状态：可多个 转换函数 边上的标号 3 4

39 3.6.2. DFA匹配（DFA模拟) state = 0; ; c = nextChar(); while (c != eof ) {
state = move(state, c); } if (state 在 接受状态集合F） return true; else return false;

40 对NFA中ε变迁的认识：ε-closure()函数
7 8 b 10 ε a start 1 2 3 4 5 6 9 开始状态的集合：S = ε-closure( {0} ) = ｛0,1,2,4, 7｝; 其中0是自己； 1，7是直接的ε后继； 2和4是间接的ε后继； ε-closure(S) = sS ε-closure(s) = ｛0,1,2,4, 7｝= S;

41 NFA中状态集S在字符a驱动下的的后继状态集
7 8 b 10 ε a start 1 2 3 4 5 6 9 开始状态的集合：S = ε-closure(0) = ｛0,1,2,4, 7｝； move(S,a) = {3,8}

42 NFA中状态集S在字符a驱动下的的后继状态集{3,8} 的 ε-closure（）
7 8 b 10 ε a start 1 2 3 4 5 6 9 状态集合S在字符a的驱动下的后继状态集合： DTran[S,a] = ε-closure(move(S,a) )= ε-closure( {3, 8｝) ={1, 2, 3, 4, 6, 7, 8}

43 NFA中状态集S在字符b驱动下的的后继状态集
7 8 b 10 ε a start 1 2 3 4 5 6 9 开始状态的集合：S = ｛0,1,2,4, 7｝； move(S,b) = {5}； DTran[S,b] = ε-closure(move(S,b) )=ε-closure( {5} )

44 NFA中状态集S在字符b驱动下的的后继状态集{5} 的 ε-closure（）
7 8 b 10 ε a start 1 2 3 4 5 6 9 DTran[S,b] = ε-closure(move(S,b) )=ε-closure( {5} ) ={1,2,4,5,6,7};

45 DFA和NFA的匹配对比 state = 0; c = nextChar(); while (c != eof ) {
state = move(state, c); } if (state接受状态集F!=） return true; else return false; states = ε-closure(0) ; c = nextChar(); while (c != eof ) { states = ε-closure(move(states,c); } if (states接受状态集F!=） return true; else return false; DFA匹配 NFA匹配

46 总的思路与框架 词法分析程序 正则表达式 NFA DFA 状态数最小化后的DFA

47 正则表达式的NFA实例 7 8 b 10 ε a start 1 2 3 4 5 6 9 对于正则表达式r= (a|b)*abb

48 正则表达式的基本元素 正则表达式中仅只有三种运算： r= s|t r= st r= s* 作用域类比：势力范围

49 3.7 简单正则表达式的NFA 对于单个字符的表达式r = a，构建其NFA： 对于表达式 r= ε，构建其NFA： f start i a

50 并运算与NFA组合的对应 对于表达式r =s | t ，构建其NFA： ft start it t ir is fs s ε fr ft

51 联接运算与NFA组合的对应 对于表达式r =s t ，构建其NFA： s t start is fs it ft ε s t start

52 +运算的NFA画法 对于表达式r =s+，构建其NFA： start is fs s ε start is fs s

53 *运算与NFA组合的对应 对于表达式r =s* =  | s+， 构建其NFA： ε start is fs s start f i ε
ir fr ε is fs s f i

54 *运算与NFA组合的对应 对于表达式r =s* =  | s+， 构建其NFA： start ir is fs s fr ε

55 其它运算的NFA画法 对于表达式：r =s？ = s |  ft start it ε ir is fs s fr fs s start

56 正则表达式的NFA构建例子 对于正则表达式r= (a|b)*abb 1 ε 3 b 2 a 4 5 6 start 2 a 3 b 5 4

57 正则表达式的NFA构建例子 a 3 ε 2 start 1 6 b 5 4 a 3 2 start ε 7 1 6 b 5 4
对于正则表达式r= (a|b)*abb

58 正则表达式的NFA构建例子 7 ε b start 1 2 3 a 4 5 6 7 a 8 ε a 2 3 ε ε start ε a ε
7 a 8 ε a 2 3 ε ε start ε a ε 1 6 7 8 b ε ε 5 ε 4 对于正则表达式r= (a|b)*abb

59 正则表达式的NFA构建例子 7 8 b 10 ε a start 1 2 3 4 5 6 9 对于正则表达式r= (a|b)*abb

60 对正则表达式的NFA构建——错误认识1 对于正则表达式(a|b)* 引起的状态变迁：尽管是空变迁，但是有方向。 7 ε b start 1
2 3 a 4 5 6 错误的画法： b start 1 ε 2 3 a 4 5 6 导致a或b驱动的变迁失去意义：1状态 = 6状态

61 正则表达式的NFA构建——错误认识2 对于正则表达式(a|b)* ε a 3 2 ε ε start ε ε 7 1 6 b ε ε 5 ε
1 6 7 b ε ε 5 ε 4 错误的画法： ε 没有区分驱动字符：a或b，与，它俩有相同的结果状态。 a 2 3 ε ε start ε 1 6 b ε ε 5 4 ε

62 正则表达式的NFA构建——错误认识3 对于正则表达式(a|b)* ε a 3 2 ε ε start ε ε 1 6 7 b ε ε 5 ε
1 6 7 b ε ε 5 ε 4 错误的画法： 7 ε b start 1 2 3 a 4 5 6 对开始状态与变迁后状态混为一谈； (a|b)* =  | (a|b)+

63 对正则表达式的处理顺序 过程分解： 正则表达式r= (a|b)*abb, 先构建其语法分析树： a b r1 r2 r3 | ( ) r4
作用域类比：势力范围

64 NFADFA 对正则表达式的NFA，并不能用于词法分析器的构造；
怎么解决？ idea：使用穷举，把所有可能情况列举出来，把不确定性转变成确定性  实现 NFA  DFA

65 NFADFA：子集构造法 7 8 b 10 ε a start 1 2 3 4 5 6 9

66 NFA中的开始状态0的ε闭包 7 8 b 10 ε a start 1 2 3 4 5 6 9
开始状态的集合：S = ε-closure(0) = ｛0,1,2,4, 7｝; 其中0是自己； 1，7是直接的ε后继； 2和4是间接的ε后继； ε-closure(S) = sS ε-closure(s) = ｛0,1,2,4, 7｝;

67 NFA中的状态集，在字符驱动下的变迁  后继状态集
7 8 b 10 ε a start 1 2 3 4 5 6 9 开始状态的集合：S = ε-closure(0) = ｛0,1,2,4, 7｝； move(S,a) = {3,8}

68 S在字符b的驱动下的后继状态 7 8 b 10 ε a start 1 2 3 4 5 6 9 状态集合S在字符a的驱动下的后继状态集合：
状态集合S在字符a的驱动下的后继状态集合： DTran[S,a] = ε-closure(move(S,a) )= ε-closure( {3, 8｝) ={1, 2, 3, 4, 6, 7, 8}

69 S在字符b的驱动下的后继状态 7 8 b 10 ε a start 1 2 3 4 5 6 9
开始状态的集合：S = ｛0,1,2,4, 7｝； move(S,b) = {5}； DTran[S,b] = ε-closure(move(S,b) )=ε-closure( {5} )

70 NFA中状态集{5}的ε闭包 7 8 b 10 ε a start 1 2 3 4 5 6 9
DTran[S,b] = ε-closure(move(S,b) )=ε-closure( {5} ) ={1,2,4,5,6,7};

71 观察 S = ｛0,1,2,4, 7｝ DTran[S,a] =ε-closure( {3,8} ) = {1,2,3,4,6,7,8} = S1,1; DTran[S,b] =ε-closure( {5} ) = {1,2,4,5,6,7} = S1,2;

72 S1,1在字符a的驱动下的后继状态 7 8 b 10 ε a start 1 2 3 4 5 6 9
已知状态的集合：S1,1 = {1,2,3,4,6,7,8}； DTran[S1,1, a] = ε-closure(move(S1,1, a) )= ε-closure( {3, 8} ) = S1,1;

73 S1,1在字符b的驱动下的后继状态 7 8 b 10 ε a start 1 2 3 4 5 6 9
已知状态的集合：S1,1 = {1,2,3,4,6,7,8}； DTran[S1,1, b] = ε-closure(move(S1,1, b) )= ε-closure( {5, 9} )

74 S1,1在字符b的驱动下的后继状态 7 8 b 10 ε a start 1 2 3 4 5 6 9
已知状态的集合：S1,1 = {1,2,3,4,6,7,8}； DTran[S1,1, b] = ε-closure(move(S1,1, b) )= ε-closure( {5, 9} ) = {1,2,4,5,6,7,9} = S2,1 新状态！！！

75 S1,2在字符a的驱动下的后继状态 ε a ε 2 3 ε ε ε a start b b 1 6 7 8 9 10 b ε 5 ε ε 4
1 6 7 8 9 10 b ε 5 ε ε 4 已知状态的集合：S1,2 = {1,2,4,5,6,7}； DTran[S1,2, a] = ε-closure(move(S1,2, a) )= ε-closure( {3, 8} ) = S1,1

76 S1,2在字符b的驱动下的后继状态 7 8 b 10 ε a start 1 2 3 4 5 6 9
已知状态的集合：S1,2 = {1,2,4,5,6,7}； DTran[S1,2, b] = ε-closure(move(S1,2, b) )= ε-closure( {5} ) = S1,2

77 S2,1在字符a的驱动下的后继状态 7 8 b 10 ε a start 1 2 3 4 5 6 9
已知状态的集合：S2,1 = {1,2,4,5,6,7,9}； DTran[S2,1, a] =ε-closure(move(S2,1, a) )= ε-closure( {3, 8} ) = S1,1

78 S2,1在字符b的驱动下的后继状态 7 8 b 10 ε a start 1 2 3 4 5 6 9
已知状态的集合：S2,1 = {1,2,4,5,6,7,9}； DTran[S2,1, b] = ε-closure(move(S2,1, b) )= ε-closure( {5, 10} ) = {1,2,4,5,6,7,10} = S3,1 新状态！！！

79 S3,1在字符a的驱动下的后继状态 7 8 b 10 ε a start 1 2 3 4 5 6 9
已知状态的集合：S3,1= {1,2,4,5,6,7,10}； DTran[S3,1, a] =ε-closure(move(S3,1, a) )= ε-closure( {3, 8} ) = S1,1

80 S3,1在字符b的驱动下的后继状态 7 8 b 10 ε a start 1 2 3 4 5 6 9
已知状态的集合：S3,1= {1,2,4,5,6,7,10}； DTran[S3,1, b] =ε-closure(move(S3,1, b) )= ε-closure( {5} ) = S1,2

81 总结——DFA D的转换表 NFA状态集 DFA状态 a b ｛0,1,2,4, 7｝ S S1,1 S1,2
{1,2,3,4,6,7,8} S2,1 {1,2,4,5,6,7} {1,2,4,5,6,7,9} S3,1 {1,2,4,5,6,7,10}

82 3.7.1 由NFA转化成DFA（子集构造法） 正则表达式r= (a|b)*abb，构建其NFA，然后转化为DFA： S1,2 b
start S S1,1 a S1,2 b S2,1 S3,1

83 最小化DFA的状态数量 对于DFA中的状态，分为两个集合S和F： start S T a U b Z Q

84 3.9.6 最小化DFA的状态数量 对S集合中的任一元素s，如果move(s,a)或者move(s,b)不在S中，则将其从S脱离出来； U
start S T a U b Z Q

85 最小化DFA的状态数量 start S T a U b Z Q

86 最小化DFA的状态数量 对于表达式r =s t ，构建其NFA： start S T a U b Z Q

87 最小化DFA的状态数量 对于表达式r =s t ，构建其NFA： start S T a U b Z Q

88 最小化DFA的状态数量 对于表达式r =s t ，构建其NFA： start S T a U b Z Q

89 最小化DFA的状态数量 b U b b start S T a Z b Q start S T a b Z Q

90 例题1：正则表达式(0?0?1) *0?0?的NFA start 6 7 1 2 3 5 4  S0={0,1,2,3,5,6,7}
3  6 5 7 4 S0={0,1,2,3,5,6,7} move(S0,1) = {4} ; ε-closure({4}) = {1,2,3,4,5,6,7} =S1 move(S0,0) = {2,3,6,7} ; ε-closure({2,3,6,7}) ={2,3,6,7} = S2 move(S1,1) = {4} = S1 move(S1,0) = {2,3,6,7} = S2 ; move(S2,1) = {4} = S1 move(S2,0) = {3,7} ; ε-closure({3,7}) ={3,7} = S3 move(S3,1) = {4} =S1; move(S3, 0) = 

91 正则表达式(0?0?1)*0?0?的DFA S1 1 start start S3 S0 S2 S3 S0 1 S2
S3 1 S1 S0 start S0 S2 S3 1 注意：上述状态S3对于字符0没有变迁。意思是说在状态S3，如果当前输入符号为0，就直接得出结论：该字符串就与该正则表达式不匹配。例如”000”就不匹配。 start S0 1 上述DFA不能化简为：

92 例题2：number → digits (.digits )?( E [+ - ]? digits)?
digit → [0 - 9] digits → digit+ number → digits (.digits )?( E [+ - ]? digits)? digit → [0 - 9] digits → digit+ number → digits ( | (.digits )) ( | ( E(( | [+ - ]) digits)

93 digits → digit+  start 1 [0-9]

94 digits ( | (.digits)) start [0-9] . 2 3 4 1   start . [0-9] 3 4 5 2
 start 1 [0-9] 4 3 2 . 5

95 ( | [+ - ])   [+-] 2 3 4 5 

96 E(( | [+ - ]) digits  E   [0-9] 6 [+-] 1 2 3 4 5 

97 ( | ( E(( | [+ - ]) digits)
 5 [0-9] 6 1 E 2 3 [+-] 4 7

98 number → digits ( | (.digits )) ( | ( E(( | [+ - ]) digits)
4 3 [0-9] 2 . 5 start 1 [0-9] 5  10 [0-9] 11 6 E 7 8 [+-] 9 12

99 DFA D状态转换表 NFA状态集 DFA状态 [0-9] . E [+-] ｛0｝ S0 S1,1  {0,1,2,5,6,12}
{3} S3,1 {7,8,10} S3,2 S3,3 {3,4,5,6,12} {10,11,12} {9,10}

100 DFA的图形表示法 正则表达式r= number → digits (.digits )?( E [+ - ]? digits)?
[0-9] [0-9] S3,1 S2,1 [0-9] . E start [0-9] E [0-9] S0 S1,1 S2,2 S3,2 [+-] [0-9] [0-9] S3,3

101 语言中的词法单元的模式的正则表达式表达 id 词法 预定义符 自定义符 保留字 运算符 标点符 特义符 变量 常量 ； “ ... if
while int 数据变量 函数变量 预定义符：相互独立，没有相交性。 变量与保留字的冲突，采用最长匹配办法解决

102 软件构造方法学：用软件编软件——词法分析器生成工具Lex
词法单元的正则表达式 → NFA → DFA → 词法分析代码 工具Lex 表达 生成 lex.l lex工具 lex.yy.c C编译器 a.out 源程序的字符流 a.out 词素流

103 随堂测试 对正则表达式：b*(a|ab)*, 画出其NFA，得出DFA D的转换表，画出DFA，给出待匹配的字符串例子3个，对给出的每个例子，要求长度>5，并在匹配过程中，走遍DFA中所有状态，并且最终分别结束在接受状态，非接受状态，无变迁边（即无须进一步匹配，直接得出不匹配结论）

104 小结1：词法分析 字符 字符串 语言：既有类概念，也有实例概念 词法单元（类概念） 字符串的三种运算 正则表达式 模式 词素（实例概念）
语言的类概念：词法单元的集合； 匹配 语言的实例概念：词素的集合； 字符串的三种运算 正则表达式

105 小结2 语言的词法分析程序 正则表达式 NFA DFA 状态数的最小化

106 随堂测试 对正则表达式：((ε|a)b*)*, 画出其DFA. 证明它与(a|b)*等价。

107 第二章作业 3.1.1，3.1.2 3.3.2， 3.3.5(1-3, 8-9)，3.3.12 3.4.1，3.4.2 3.6.2, , 3.7.1,

108 第一次讨论课 第一次讨论课的主题： 词法分析。小主题： 1) 正则表达式转换NFA； 2) NFA确定化为DFA；
5) TINY编译器与TM虚拟机； 6) 词法分析器自动工具（如：FLEX） 自己定题，也可以选择如下内容： 1) Unix/Linux中的grep指令嵌套使用的典型应用案例； 2) 练习3.3.5（4，5，6，8）中的任何一个； 3) 其它习题也可以；

109 谢 谢 谢 谢！