编译原理第15章-参考资料

1、编译原理 文法文法/ /正规式正规式/ /有限自动机有限自动机 基础知识基础知识课外材料课外材料(未未修过相关课程者参考修过相关课程者参考)编译原理 形式语言概念形式语言概念 正规语言及其描述正规语言及其描述文法文法/ /正规式正规式/ /有限自动机有限自动机基础知识基础知识 上下文无关文法及语言上下文无关文法及语言编译原理形式语言概念形式语言概念 字母表字母表 （Alphabet）- 形式符号的集合形式符号的集合- 常用常用 表示表示 - 举例举例 英文字母表英文字母表 a, b, , z, A, B , , Z 汉字表汉字表 , 自自, , 动动 , , 机机, 化学元素表化学元素表 H,

2、 He, Li, ,Une = a, n, y, 任任,意意 编译原理形式语言概念形式语言概念 字符串字符串 （String）- 字母表字母表 上的一个上的一个字符串字符串（串串），或称为），或称为 字字（word），为），为 中字符构成的一个有限中字符构成的一个有限 序列。序列。 空串空串（empty string）, 常用常用 表表 示，不包含任何字符。示，不包含任何字符。 - 字符串字符串 w 的的长度长度，记为，记为 w ，是包含在，是包含在 w 中字符的个数中字符的个数 举例举例 = 0， bbaba = 5编译原理形式语言概念形式语言概念 字符串的字符串的连接连接（concaten

3、ation ）运算）运算- 设设 x, y为串为串, 且且 x a1a2 am, y b1b2 bn, 则则 x 与与 y 的的连接连接 x y a1a2 am b1b2 bn- 连接运算的连接运算的性质性质 ( x y ) z x（ y z ） x x x x y x + y 编译原理形式语言概念形式语言概念 字母表上的运算字母表上的运算- 幂运算幂运算 设设 为字母表，为字母表，n 为任意自然数，为任意自然数， 定义（定义（1） 0 = （2）设）设 x n-1，a ， 则则a x n （3） n 中的元素只能由（中的元素只能由（1）和）和（2） 生成生成- 闭包闭包 * * = = 0

4、0 1 1 2 2 - 闭包闭包 + + = = 1 1 2 2 3 3 编译原理形式语言概念形式语言概念 语言语言 （Languages）- 概念概念 设设 为字母表，则任何集合为字母表，则任何集合 L * 是是字字 母表母表 上的上的一个一个语言语言 - 举例举例 , English, , words , any, 任意任意 - 比较比较 空语言空语言 与与仅含空字的语言仅含空字的语言 编译原理形式语言概念形式语言概念 语言上的运算语言上的运算- 两个语言两个语言 L 和和 M 的的联合联合（union） L M = w w L w M - 两个语言两个语言 L 和和 M 的的连接连接（c

5、oncatenation） L M = w1w2 w1 L w2 M - 语言语言 L 的的闭包闭包（closure） L* = L0 L1 L2 = i 0 Li , 其中其中 L0 = ， L1 = L, L2 = LL, Ln = Ln-1L编译原理形式语言概念形式语言概念 程序设计语言程序设计语言- C 源程序的集合源程序的集合用用 * 表示表示 （ 为为 ASCII字符集）字符集）- L 表示由满足表示由满足 C 语言语言词法规则词法规则的单词构成的语的单词构成的语言言 - M表示由满足表示由满足 C 语言语言语法规则语法规则的源程序构成的的源程序构成的语语 言言 - S 表示由正确

6、的表示由正确的C语言源程序构成的语言语言源程序构成的语言 - 四者之间的关系四者之间的关系L *，M *，S *M L*, S L* S M编译原理形式语言概念形式语言概念 几个重要的几个重要的形式语言类形式语言类编译原理正规语言及其描述正规语言及其描述 描述正规语言的形式工具描述正规语言的形式工具- 3 型（正规）文法型（正规）文法- 有限自动机有限自动机- 正规表达式正规表达式编译原理 有限自动机的有限自动机的五要素五要素- 有限状态集有限状态集 - 有限输入符号有限输入符号集集 - 转移函数转移函数 - 一个开始状态一个开始状态 - 一个终态集合一个终态集合q0q1q2q3Start01

7、101100正规语言及其描述正规语言及其描述编译原理- 有限状态集有限状态集 - 有限输入符号有限输入符号集集 - 转移函数转移函数 - 一个开始状态一个开始状态 - 一个终态集合一个终态集合 一个确定有限状态自动机一个确定有限状态自动机 DFA (deterministic finite automata) 是一个五元组是一个五元组 A = (Q, , , q0 , F ). : Q Q q0 Q F Q 确定有限自动机的形式定义确定有限自动机的形式定义正规语言及其描述正规语言及其描述编译原理- Q = q0 , q1 , q2 , q3 - = 0, 1 - (q0 ,0) = q2 ,

8、(q0 ,1) = q1 (q1 ,0) = q3 , (q1 ,1) = q0 (q2 ,0) = q0 , (q2 ,1) = q3 (q3 ,0) = q1 , (q3 ,1) = q2 - q0 - F = q0 , q3 q0q1q2q3Start01101100 转移图表示的转移图表示的 DFA 正规语言及其描述正规语言及其描述编译原理 q0q1q2 q301q2q1q3q0q0q3q1q2- Q = q0 , q1 , q2 , q3 - = 0, 1 - (q0 ,0) = q2 , (q0 ,1) = q1 (q1 ,0) = q3 , (q1 ,1) = q0 (q2 ,0

9、) = q0 , (q2 ,1) = q3 (q3 ,0) = q1 , (q3 ,1) = q2 - q0 - F = q0 , q3 转移表表示的转移表表示的 DFA 正规语言及其描述正规语言及其描述编译原理q1q2q3q0 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q2q3q0q1 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q2q0q1q3 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q2q3q0q1 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其

10、描述编译原理q1q2q3q0 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q1q3q0q2 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q1q0q2q3 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q1q2q3q0 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q1q3q0q2 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q1q2q3q0 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其

11、描述编译原理q1q2q3q0 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q2q3q0q1 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q2q0q1q3 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q1q3q0q2 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q1q2q3q0 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理q2q3q0q1 DFA如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其

12、描述编译原理- 设一个设一个 DFA A = (Q, , , q0 , F ) : Q Q - 扩充定义扩充定义 : Q * Q 对任何对任何q Q，定义：定义： 1 (q , ) = q 2 若若w = xa, 其中其中 x *, a , 则则 ( q , w) = ( ( q , x) , a) 扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串正规语言及其描述正规语言及其描述编译原理 q0q1q2 q301q2q1q3q0q0q3q1q2- 举例举例 (q0 , ) = q0 (q0 , 0) = (q0 , 0) = q2 (q0 , 00) = (q2 , 0) = q0 (q

13、0 , 001) = (q0 , 1) = q1 (q0 , 0010) = (q1 , 0) = q3Start01101100 扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串正规语言及其描述正规语言及其描述编译原理- 设一个设一个 DFA A = (Q, , , q0 , F ) - 定义定义 A 的语言：的语言： L(A) = w ( q0 , w) F - 可以证明，可以证明，如果存在如果存在一个一个 DFA A = (Q, , , q0 , F )，满足，满足L = L(A) ， 则则 L 是一个正规语言是一个正规语言. DFA 的语言的语言正规语言及其描述正规语言及其描述

14、编译原理Startpr0, 10q1(1)Startp0, 11qr0, 1(2) 非确定有限自动机举例非确定有限自动机举例正规语言及其描述正规语言及其描述编译原理- 有限状态集有限状态集 - 有限输入符号有限输入符号集集 - 转移函数转移函数 - 一个开始状态一个开始状态 - 一个终态集合一个终态集合 一个非确定有限状态自动机一个非确定有限状态自动机 NFA nondeterministicfinite automata) 是一个五元组是一个五元组 A = (Q, , , q0 , F ).q0 Q F Q- 与与 DFA 唯一不同之处唯一不同之处 : Q 2Q 非确定有限自动机的形式定义非

15、确定有限自动机的形式定义正规语言及其描述正规语言及其描述编译原理Startpr0, 10q1(1)Startp0, 11qr0, 1(2)pq r0 q q q, r 1pq r0 p r r 1 p, q 转移图和转移表表示的转移图和转移表表示的NFA正规语言及其描述正规语言及其描述编译原理Startp0, 11qr0, 1010100100111010 NFA 如何接受输入符号串如何接受输入符号串 正规语言及其描述正规语言及其描述编译原理- 设一个设一个 NFA A = (Q, , , q0 , F ) - : Q 2Q - 扩充定义扩充定义 : Q * 2Q - 对任何对任何q Q，定义

16、定义： 1 (q , ) = q 2 若若w = xa, 其中其中 x * , a , 并且假设并且假设 ( q , x) = p1 , p2 , , pk , 则则 ( q , w) = ( pi , a ) i = 1k 扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串正规语言及其描述正规语言及其描述编译原理- 举例举例 ( p , ) = p ( p , 0 ) = q ( p , 01 ) = q , r ( p , 010 ) = q ( p , 0100 ) = q ( p , 01001 ) = q , r pq r0 q q q, r 1Startpr0, 10q1 扩

17、展转移函数适合于输入字符串扩展转移函数适合于输入字符串正规语言及其描述正规语言及其描述编译原理- 设一个设一个 NFA A = (Q, , , q0 , F ) - 定义定义 A 的语言的语言： L(A) = w ( q0 , w) F - 设设 L 是是 上的语言，上的语言，如果存在如果存在一个一个 NFA A = (Q, , , q0 , F )，满足满足L = L(A) ，则则 可以证明可以证明 L 也也是一个正规语言是一个正规语言. NFA 的语言的语言正规语言及其描述正规语言及其描述编译原理- 定理定理: L 是某个是某个 DFA 的语言的语言, 当且仅当当且仅当 L 也是某个也是某

18、个 NFA 的语言的语言. - 证明思路证明思路: 分两步证明分两步证明. (1) 设设 L 是某个是某个 DFA D 的语言的语言, 则存在一个则存在一个 NFA N , 满足满足 L(N) = L(D) = L; (2) 设设 L 是某个是某个 NFA N 的语言的语言, 则存在一个则存在一个 DFA D , 满足满足 L(D) = L(N) = L; DFA 和和 NFA 的等价性的等价性正规语言及其描述正规语言及其描述编译原理- 设设 L 是某个是某个 DFA D = (Q, , D , q0 , F ) 的语的语 言言, 则存在一个则存在一个 NFA N = (Q, , N ,q0,

19、F ) , 其中其中 N定义为定义为 对对q Q 和和a , 若若 D (q,a) = p, 则则 N (q,a) = p. 可以证明可以证明: L(N) = L(D) = L. 从从 DFA 构造等价的构造等价的 NFA正规语言及其描述正规语言及其描述编译原理- 设设 L 是某个是某个 NFA N = (QN, , N , q0 , FN) 的语言的语言, 则存在一个则存在一个 DFA D = (QD, , D , q0 , FD ) , 其中其中 QD = S S QN 对对 S QD 和和 a , D ( S , a ) = N (q,a) . FD = S S QN S FN 可以证明

20、可以证明: L(D) = L(N) = L.q S 从从 NFA 构造等价的构造等价的 DFA（子集构造法）（子集构造法）正规语言及其描述正规语言及其描述编译原理pq r0 q q q, r 10 q 1 p q r p, q p, r q, r p, q, r q q, r q q, r q q q, r q q, r Startp0, 10q1q,r1010 子集构造法举例子集构造法举例正规语言及其描述正规语言及其描述编译原理01 p p, q, r p p, q pq r0 p r r 1 p, q p p, q p, q p, r p, q, r p, r p, r p, q, r S

21、tartp1p,q10100p,q,rp,r01 子集构造法举例子集构造法举例正规语言及其描述正规语言及其描述编译原理Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4比较：比较：NFA without Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.0,1, . ,90,1, . ,9.q0q1q2q3q4q 5+, 带带 -转移的非确定有限自动机转移的非确定有限自动机( - NFA )举例举例正规语言及其描述正规语言及其描述编译原理 一个一个 - NFA 是一个五元组是一个五元组 A

22、= (Q, , , q0 , F ). 有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合q0 Q F Q 与与 NFA 的不同之处的不同之处 : Q 2Q 带带 - 转移的非确定有限自动机（转移的非确定有限自动机（ - NFA） 的的形式定义形式定义正规语言及其描述正规语言及其描述编译原理Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4 q1 +,.0,1, ,9q0q1q2q3q4q5 q1 q2 q3 q3 q5 q3 q1,q4 转移图和转移表表示

23、的转移图和转移表表示的 - NFA正规语言及其描述正规语言及其描述编译原理q1q0q2q3q5 ,+,q4- 该该 - NFA 可以接受的字符串如：可以接受的字符串如： 3.14 +.314 314. - NFA 如何接受输入符号串如何接受输入符号串正规语言及其描述正规语言及其描述编译原理Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4- 状态状态 q 的的 - 闭包，记为闭包，记为ECLOSE(q)，定义为从，定义为从 q 经经 所有的所有的 路径可以到达的状态（包括路径可以到达的状态（包括q自身），如：自身），如： EC

24、LOSE(q0) = q0,q1 ECLOSE(q2) = q2 ECLOSE(q3) = q3,q5 - 闭包（闭包（closure）正规语言及其描述正规语言及其描述编译原理- 设设 - NFA A = (Q, , , q0 , F )，q Q，ECLOSE(q) 为满足如下条件的最小集：为满足如下条件的最小集： （1）q ECLOSE(q)（2）if p ECLOSE(q) and r (p, ) , then r ECLOSE(q)- 对于右图，有：对于右图，有： ECLOSE(1) = 1,2,4,5,6,7 ECLOSE(2) = 2,4,5,6,7 ECLOSE(7) = 5,7

25、1235647abcStart - 闭包闭包正规语言及其描述正规语言及其描述编译原理- 设一个设一个 - NFA E = (Q, , , q0 , F ) - : Q 2Q - 扩充定义扩充定义 : Q * 2Q - 对任何对任何q Q，定义：定义： 1 (q , ) = ECLOSE(q ) 2 若若w = xa, 其中其中 x * , a , 假设假设 ( q , x) = p1 , p2 , , pk , 并且并且 令令 ( pi , a ) = r1 , r2 , , rm ， 则则 ( q , w) = ECLOSE( rj ) i = 1kj = 1m 扩展转移函数适合于输入字符串

26、扩展转移函数适合于输入字符串正规语言及其描述正规语言及其描述编译原理Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4- 举例举例 计算计算 (q0, 5.6) (q0, ) = ECLOSE( (q0) ) = q0,q1 (q0, 5) (q1, 5) = q1,q4 (q0, 5) = ECLOSE( (q1) ) ECLOSE( (q4) ) = q1,q4 (q1, .) (q4, .) = q2,q3 (q0, 5.) = ECLOSE( (q2) ) ECLOSE( (q3) ) = q2,q3 ,q5 (q2,

27、 6) (q3, 6) (q5, 6) = q3 (q0, 5.6) = ECLOSE( (q3) ) = q3 ,q5 扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串正规语言及其描述正规语言及其描述编译原理- 设一个设一个 - NFA E = (Q, , , q0 , F ) - 定义定义 E 的语言：的语言： L(E) = w ( q0 , w) F - 设设 L 是是 上的语言，上的语言，如果存在如果存在一个一个 -NFA E = (Q, , , q0 , F )，满足，满足L = L(E) ，则则 可以证明可以证明 L 也也是一个正规语言是一个正规语言. - NFA 的的 语

28、语 言言正规语言及其描述正规语言及其描述编译原理- 定理定理: L 是某个是某个 - NFA 的语言的语言, 当且仅当当且仅当 L 也是某个也是某个 DFA 的语言的语言. - 证明思路证明思路: 分两步证明分两步证明. (1) 设设 L 是某个是某个 DFA D 的语言的语言, 则存在一个则存在一个 - NFA E , 满足满足 L(E) = L(D) = L; (2) 设设 L 是某个是某个 - NFA E 的语言的语言, 则存在则存在 一个一个 DFA D , 满足满足 L(D) = L(E) = L. - NFA 与与 DFA 的等价性的等价性正规语言及其描述正规语言及其描述编译原理-

29、 设设 L 是某个是某个 DFA D = (Q, , D , q0 , F ) 的语言的语言, 则存在一个则存在一个 - NFA E = (Q, , E , q0 , FE ) , 其中其中 E 定义为定义为 对任何对任何q Q, E (q, ) = 对任何对任何q Q 和和a , 若若 D (q,a) = p, 则则 N (q,a) = p. 可以证明可以证明L(E) = L(D) = L 从从 DFA 构造等价的构造等价的 - NFA正规语言及其描述正规语言及其描述编译原理- 设设 L 是某个是某个 - NFA E = (QE, , E , q0 , FE) 的语言的语言, 则则存存 在一

30、个在一个 DFA D = (QD, , D , qD , FD ) , 其中其中 QD = S S QE S = ECLOSE(S) qD = ECLOSE(q0) FD = S S QD S FE 对对 S QD 和和 a , 令令 S = p1 , p2 , , pk ， 并设并设 E ( pi , a ) = r1 , r2 , , rm ， 则则 D ( S , a ) = ECLOSE( rj ) . 可以证明可以证明: L(D) = L(E) = L.i = 1kj = 1m 从从 - NFA 构造等价的构造等价的 DFA（修改的子集构造法）（修改的子集构造法）正规语言及其描述正规

31、语言及其描述编译原理Start0,1, . ,9.0,1, . ,90,1, . ,90,1, . ,9.q1q0q2q3q5 ,+,q4Startq0 q1+,-q10,1, . , 9q1 q4.q20,1, . ,9.0,1, . ,9.q2 q3 q50,1, . ,9q3 q50,1, . ,90,1, . ,9 修改的子集构造法举例修改的子集构造法举例正规语言及其描述正规语言及其描述编译原理- 用代数的方法用代数的方法表示正规语言表示正规语言 - 语义语义 作用于语言上的三种代数运算作用于语言上的三种代数运算 联合联合（union） 连接连接（concatenation） （星）（

32、星）闭包闭包（closure） - 语法语法 不同应用有所不同，但都含有上述不同应用有所不同，但都含有上述 三种代数运算的表示形式；为方便起见，三种代数运算的表示形式；为方便起见， 通常还需要引入一些助记符通常还需要引入一些助记符 正规表达式正规表达式正规语言及其描述正规语言及其描述编译原理- 定义定义及及解释解释 设正规表达式设正规表达式E代表的语言为代表的语言为L(E),归纳定义归纳定义正规表达式正规表达式如下：如下：归纳归纳1 和和 为正规表达式，且为正规表达式，且L( ) = 、 L( ) = 2 若若a 为任一字符，则为任一字符，则 a 为正规表达式，且为正规表达式，且L(a) =

33、a3 任一变量（通常大写）任一变量（通常大写）L 为正规表达式，代表任意语言为正规表达式，代表任意语言 1 若若 E 和和 F 为正规表达式，则为正规表达式，则E | F也为正规表达式，且也为正规表达式，且 满足满足 L( E | F ) = L( E ) L( F ) 2 若若 E 和和 F 为正规表达式，则为正规表达式，则 EF 也为正规表达式，且也为正规表达式，且 满满足足 L( EF ) = L( E ) L( F ) 基础基础 3 若若 E 为正规表达式，则为正规表达式，则 E* 也为正规表达式，且也为正规表达式，且 满足满足 L( E* ) = ( L( E ) ) * 4 若若

34、E 为正规表达式，则为正规表达式，则 ( E ) 也为正规表达也为正规表达式，且式，且 满足满足 L( ( E ) ) = L( E ) 正规表达式正规表达式（regular expression）正规语言及其描述正规语言及其描述编译原理算符优先级（算符优先级（precedence）依次为）依次为- （ closure ）- 连接连接（concatenation）- |（ union ） 正规表达式算符优先级正规表达式算符优先级正规语言及其描述正规语言及其描述编译原理 设计表示如下语言的正规表达式：设计表示如下语言的正规表达式： 该语言中的每个字符串由该语言中的每个字符串由交替的交替的 0 和

35、和 1 构成构成- (01)* | (10)* | 0(10)* | 1(01)*- ( | 1) (01)* ( | 0) - ( | 0) (10)* ( | 1) 正规表达式举例正规表达式举例正规语言及其描述正规语言及其描述编译原理 有限自动机与正规表达式的关系有限自动机与正规表达式的关系结论结论: 正规表达式所表示的语言是正规语言正规表达式所表示的语言是正规语言.证明策略证明策略 -NFANFADFARE正规语言及其描述正规语言及其描述编译原理 从从有限自动机有限自动机构造等价的正规表达式构造等价的正规表达式思路（状态消去法）思路（状态消去法） : - 扩展自动机的概念，允许正规表达式

36、作为转移扩展自动机的概念，允许正规表达式作为转移弧弧 的标记的标记. 这样，就有可能在消去某一中间状态这样，就有可能在消去某一中间状态 时，保证自动机能够接受的字符串集合保持不变时，保证自动机能够接受的字符串集合保持不变. - 在消去某一中间状态时，与其相关的转移弧也在消去某一中间状态时，与其相关的转移弧也将将 同时消去，所造成的影响将通过修改从每一个前同时消去，所造成的影响将通过修改从每一个前 趋状态到每一个后继状态的转移弧标记来弥补趋状态到每一个后继状态的转移弧标记来弥补. 正规语言及其描述正规语言及其描述编译原理 从从有限自动机有限自动机构造等价的正规表达式构造等价的正规表达式 （中间状

37、态的消去）（中间状态的消去）sSq1qkp1pmP1PmQkQ1R11R1mRkmRk1R11+ Q1S* P1R1m+ Q1S* PmRkm+ QkS* PmRk1 + QkS* P1q1p1qkpm消去消去 s正规语言及其描述正规语言及其描述编译原理 从从有限自动机有限自动机构造等价的正规表达式构造等价的正规表达式步骤（状态消去法）步骤（状态消去法） : (1) 对每一终态对每一终态q，依次消去除，依次消去除 q 和初态和初态 q0 之外的其它状态之外的其它状态;StartRStartSTUR(2) 若若q q0，最终可得到一般形式如下左图两状态自动机，最终可得到一般形式如下左图两状态自动

38、机， 该自动机对应的正规表达式可表示为该自动机对应的正规表达式可表示为 ( R | SU*T )*SU*.(3) 若若q= q0，最终可得到如下右图的自动机，它对应的正规，最终可得到如下右图的自动机，它对应的正规 表达式可以表示为表达式可以表示为 R*.(4) 最终的正规表达式为每一终态对应的最终的正规表达式为每一终态对应的 正规表达式之和（并）正规表达式之和（并）.正规语言及其描述正规语言及其描述编译原理 从从有限自动机有限自动机构造等价的正规表达式构造等价的正规表达式- 状态消去法举例状态消去法举例A0,1StartBCD0,10,11正规语言及其描述正规语言及其描述编译原理 从从有限自动

39、机有限自动机构造等价的正规表达式构造等价的正规表达式- 状态消去法举例状态消去法举例对于终态对于终态D正规语言及其描述正规语言及其描述编译原理 从从有限自动机有限自动机构造等价的正规表达式构造等价的正规表达式- 状态消去法举例状态消去法举例对于终态对于终态C正规语言及其描述正规语言及其描述编译原理对于终态对于终态C对于终态对于终态D D等价的正规表达式等价的正规表达式(0|1)*1(0|1) | (0|1)*1(0|1)(0|1) 从从有限自动机有限自动机构造等价的正规表达式构造等价的正规表达式- 状态消去法举例状态消去法举例正规语言及其描述正规语言及其描述编译原理 从正规表达式构造等价的从正

40、规表达式构造等价的 - NFA （归纳构造过程（归纳构造过程: : Thompson 构造法构造法）基础基础:1 对于对于 ，构造为构造为 3 对于对于 a ，构造为构造为a2 对于对于 ，构造构造为为正规语言及其描述正规语言及其描述编译原理归纳归纳:1 对于对于 R | S ，构造为构造为SR 正规语言及其描述正规语言及其描述 从正规表达式构造等价的从正规表达式构造等价的 - NFA （归纳构造过程（归纳构造过程: : Thompson 构造法构造法）编译原理归纳归纳:2 对于对于 RS ，构造为构造为RS R3 对于对于 R* ，构造为构造为 正规语言及其描述正规语言及其描述 从正规表达式

41、构造等价的从正规表达式构造等价的 - NFA （归纳构造过程（归纳构造过程: : Thompson 构造法构造法）编译原理 从正规表达式构造等价的从正规表达式构造等价的 - NFA 从正规表达式构造等价的从正规表达式构造等价的 - NFA举例举例:设正规表达式设正规表达式 1*0(0|1)*, 构造等价构造等价的的 -NFA.100|1 11* 正规语言及其描述正规语言及其描述编译原理 从正规表达式构造等价的从正规表达式构造等价的 - NFA举例举例:设正规表达式设正规表达式 1*0(0|1)*, 构造等价构造等价的的 -NFA.(0|1)*10 11001*0(0|1)* 正规语言及其描述正

42、规语言及其描述编译原理 DFA 的化简的化简- 知识回顾：知识回顾：集合上的等价关系与划集合上的等价关系与划分分等价关系等价关系 设设 Q 为一个集合，二元关系为一个集合，二元关系 R 是是 Q 上的一个上的一个 等价关系等价关系, 当且仅当满足以下条件：当且仅当满足以下条件： 1. 自反性自反性 对任何对任何a Q , aRa 成立；成立； 2. 对称性对称性 对任何对任何a,b Q , 如果如果 aRb 成立成立, 则有则有 bRa 成立；成立； 3. 传递性传递性 对任何对任何a,b,c Q , 如果如果 aRb 和和 bRc 成立成立, 则有则有 aRc 成立成立.正规语言及其描述正规

43、语言及其描述编译原理 DFA 的化简的化简设设 Q 为一个集合，为一个集合，R 是是 Q 上的一个上的一个等价关系等价关系, 由由 R 产产生的所有等价类（或块）的集合构成生的所有等价类（或块）的集合构成 Q 的一个的一个划分划分.- 注释注释 1. 等价类等价类 对任何对任何a Q , a 所在的块用所在的块用a表示表示, 定义为定义为 a = x | xRa ； 2. 每一元素都属于唯一的块每一元素都属于唯一的块 即满足即满足 （1） a Q a = Q ; 和和 （2）对任何）对任何a,b Q , 或者或者 a=b , 或者或者 a b= - 知识回顾：知识回顾：集合上的等价关系与划集合

44、上的等价关系与划分分正规语言及其描述正规语言及其描述编译原理 DFA 的化简的化简- DFA 状态集合上的一个等价关状态集合上的一个等价关系系设一个设一个 DFA D = (Q, , , q0 , F ), 定义定义Q上的一个二上的一个二元关系元关系 R 为：为： 对任何对任何 p,q Q, pRq iff w *. ( (p,w) F (q,w) F )证明：证明：1. 自反性自反性 对任何对任何q Q , qRq 成立；成立； 2. 对称性对称性 对任何对任何p,q Q , pRq qRp 成立；成立；3. 传递性传递性 对任何对任何p,q,r Q , 设设pRq 和和 qRr 成立成立,

45、 即对任何即对任何w *, (p,w) F (q,w) F 和和 (q,w) F (r,w) F 成立；由此，也有成立；由此，也有 (p,w) F (r,w) F 成立成立. 所以所以，qRr 成立成立正规语言及其描述正规语言及其描述编译原理 DFA 的化简的化简- DFA 状态集合上的一个等价关状态集合上的一个等价关系系若若pRq, 称称 p 和和 q 等价等价（equivalent）. 若若p 和和q 不等不等价，则称价，则称 p 和和q 是是可区别的可区别的（distinguashable）.关系关系 R 对应有限状态集对应有限状态集 Q 的一个划分；的一个划分； 该划分的每个块是该划分

46、的每个块是 Q 的一个子集；的一个子集；同一划分块同一划分块中的所有状态之间都是中的所有状态之间都是相互等价相互等价的；的；分属分属不同划分块不同划分块的任何两个状态之间都是的任何两个状态之间都是可区别的可区别的.- DFA 的优化的优化 通过合并等价的（或不可区别的）状通过合并等价的（或不可区别的）状态态. 关键：如何计算上述划分？关键：如何计算上述划分？正规语言及其描述正规语言及其描述编译原理 DFA 的化简的化简- 计算状态集划分的算计算状态集划分的算法法填表算法（填表算法（table-filling algorithm）基于如下递归基于如下递归地标记可区别的状态偶对的过程地标记可区别的

47、状态偶对的过程:（ (r,aw) = (p,w) , (s,aw) = (q,w) ）基础基础 如果如果 p 为终态，而为终态，而 q 为非终态，则为非终态，则 p 和和 q 标标记为可区别的；记为可区别的；归纳归纳 设设 p 和和 q 已标记为可区别的已标记为可区别的, 如果状态如果状态 r 和和 s 通过某个通过某个 输入符号输入符号 a 可分别转移到可分别转移到 p 和和 q ，即，即 (r,a)=p , (s,a)=q , 则则 r 和和 s 也标记为可区别的；也标记为可区别的；这是因为：这是因为：若若 p 和和 q 可为字符串可为字符串 w 区别区别, 则则 r 和和 s可为字符串可

48、为字符串 aw 区别区别. 正规语言及其描述正规语言及其描述编译原理 DFA 的化简的化简- 填表算法举例填表算法举例212334455667xxxxxxxxxxxxx651Start3724aaaaaaabbbbbbb(1) 区别所有终态和非终态区别所有终态和非终态(2) 区别区别(1,3), (1,4), (2,3), (2,4), (5,6), (5,7)xxxxx(3) 区别区别 (3,4)x(4) 结束结束. 划分结果：划分结果：1,2, 3, 4, 5, 6,7正规语言及其描述正规语言及其描述编译原理 DFA 的最小化的最小化- 可以证明：可以证明： 通过以下通过以下步骤步骤 ，可

49、以得到状态数最少的等价，可以得到状态数最少的等价DFA 1. 删除所有从开始状态不可到达的状态及与其相关的边删除所有从开始状态不可到达的状态及与其相关的边, 设所得到的设所得到的 DFA 为为 A = (Q, , , q0 , F ) ； 2. 使用填表算法找出所有等价的状态偶对；使用填表算法找出所有等价的状态偶对； 3. 根据根据 2 的结果计算当前状态集合的划分块，每一划分的结果计算当前状态集合的划分块，每一划分 块中的状态相互之间等价，而不同划分块中的状态之块中的状态相互之间等价，而不同划分块中的状态之 间都是可区别的间都是可区别的. 包含状态包含状态 q 的划分块用的划分块用 q 表示

50、表示. 4. 构造与构造与 A 等价的等价的 DFA B = (QB, , B, q0, FB ) , 其中其中 QB= q | q Q, FB = q | q F, B(q ,a)= (q,a)正规语言及其描述正规语言及其描述编译原理 DFA 的最小化的最小化- 举例举例 651Start3724aaaaaaabbbbbbb 划分结果：划分结果： 1, 2 , 3, 4, 5, 6, 7 651Start34aaaabbbbba- 最小化结最小化结果果 等价的状态偶对为：等价的状态偶对为： （1, 2）,（6, 7） 新的状态集合：新的状态集合： 1, 3, 4, 5, 6正规语言及其描述正

51、规语言及其描述编译原理上下文无关语言及其描述上下文无关语言及其描述 上下文无关文法上下文无关文法(context-free grammars)- 例子例子 E EOE E (E) E v E d O O 编译原理 上下文无关文法上下文无关文法的的四个基本要素四个基本要素 1. 终结符终结符(terminals)的集合的集合 有限符号集，相当于字母表有限符号集，相当于字母表E EOEE (E)E vE dO O 终结符终结符 2. 非终结符非终结符(nonterminals)的集合的集合 有限变量符号的集合有限变量符号的集合非终结符非终结符 3. 开始符号开始符号(start symbol) 一

52、个特殊的非终结符一个特殊的非终结符开始符号开始符号 4. 产生式产生式(productions)的集合的集合 形如：形如： 产生式集合产生式集合上下文无关语言及其描述上下文无关语言及其描述编译原理 上下文无关文法的形式定义上下文无关文法的形式定义终结符的集合终结符的集合 一个上下文无关文法一个上下文无关文法 CFG (context-free grammars) 是一个四元组是一个四元组 G = (VN, VT, P , S ).非终结符的集合非终结符的集合产生式的集合产生式的集合开始符号开始符号满足满足 VN VT = S VN产生式形如产生式形如 A , 其中其中 A VN, (VN VT

53、)*上下文无关语言及其描述上下文无关语言及其描述编译原理 上下文无关文法上下文无关文法举例举例CFG Gexp = (E,O, (, ), , v, d , P , E ). 其中产式集合其中产式集合 P 为为 E EOE E (E) E v E d O O 上下文无关语言及其描述上下文无关语言及其描述编译原理 产生式集合的缩写记法产生式集合的缩写记法形如形如 A 1, A 2, , A n 的产生式的产生式集合可简缩记为集合可简缩记为 A 1 2 n ，如，如 E EOEE (E)E vE dO O E EOE (E) v dO 上下文无关语言及其描述上下文无关语言及其描述编译原理 归约与推

54、导归约与推导- 用于推理字符串是否属于文法所定义的语用于推理字符串是否属于文法所定义的语言言 一种是自下而上的方法，称为一种是自下而上的方法，称为递归推理递归推理 （recursive inference），递归推理的过程），递归推理的过程 习称为习称为归约归约；另一种是自上而下的方法，称；另一种是自上而下的方法，称 为为推导推导（derivation）.- 归约过程归约过程 将产生式的右部（将产生式的右部（body）替换）替换为为 产生式的左部（产生式的左部（ head ）.- 推导过程推导过程 将产生式的左部（将产生式的左部（ head ）替换）替换 为产生式的右部（为产生式的右部（ bo

55、dy ）.上下文无关语言及其描述上下文无关语言及其描述编译原理 归约过程举例归约过程举例对于对于CFG Gexp = (E,O, (, ), , v, d , P , E ) ，P 为为 （1）E EOE （2） E (E) （3） E v （4） E d （5） O （6） O 递归推理出字符串递归推理出字符串 v (vd) 的一个归约过程为的一个归约过程为v (vd)（4）v (vE)（6）vO(vE)（3）vO(EE)（5）vO(EOE)（1）vO(E)（2）vOE（3）EOE（1）E上下文无关语言及其描述上下文无关语言及其描述编译原理 推导过程举例推导过程举例对于对于CFG Gexp

56、= (E,O, (, ), , v, d , P , E ) ，P 为为 （1）E EOE （2） E (E) （3） E v （4） E d （5） O （6） O 递归推理出字符串递归推理出字符串 v (vd) 的一个推导过程为的一个推导过程为v (vd)（4）v (vE)（6）E (E)（3）（1）v (EOE)（5）（3）EOE（1）EE E（2）v (E)v (EE)上下文无关语言及其描述上下文无关语言及其描述编译原理G 推导关系推导关系 对于对于 CFG G = (VN, VT, P , S )，上述推导过程可用关系，上述推导过程可用关系 描述描述. 设设 , (VN VT)*，A

57、 是一个产生式，则定义是一个产生式，则定义 A . 若若 G 在上下文中是明确的，则简记为在上下文中是明确的，则简记为 A .G 扩展推导关系到自反传递闭包扩展推导关系到自反传递闭包 定义上述关系的自反传递闭包，记为定义上述关系的自反传递闭包，记为 ，可归纳定义如下：，可归纳定义如下： 基础基础 对任何对任何 (VN VT)*，满足满足 . 归纳归纳 设设 , , (VN VT)*，若，若 ， 成立，则成立，则 . GGGGG 上下文无关语言及其描述上下文无关语言及其描述编译原理 最左推导最左推导 (leftmost derivations) 若推导过程的每一步总是替换出现在最左边的非终结符，

58、若推导过程的每一步总是替换出现在最左边的非终结符， 则这样的推导称为则这样的推导称为最左推导最左推导. 为方便，最左推导关系用为方便，最左推导关系用 表示，其自反传递闭包用表示，其自反传递闭包用表示表示. 如对于文法如对于文法Gexp ，下面是关于，下面是关于 v (vd) 的一个最左推导的一个最左推导： lmlmE EOEE (E)E vE dO O v (vd)v (vE)v (EOE)EOEEv (E)vOEv Ev (vOE) lm lm lm lm lm lm lm lm上下文无关语言及其描述上下文无关语言及其描述编译原理 最右推导最右推导 (rightmost derivation

59、s) 若推导过程的每一步总是替换出现在最右边的非终结符，若推导过程的每一步总是替换出现在最右边的非终结符， 则这样的推导称为则这样的推导称为最右推导最右推导. 为方便，最右推导关系用为方便，最右推导关系用 表示，其自反传递闭包用表示，其自反传递闭包用表示表示. 如对于文法如对于文法Gexp ，下面是关于，下面是关于 v (vd) 的一个最右推导的一个最右推导： rmrmE EOEE (E)E vE dO O v (vd)E (vd)EO(Ed)EOEEEO(EOd)EO(E)EO(EOE)EO(vd) rm rm rm rm rm rm rm rm上下文无关语言及其描述上下文无关语言及其描述编

60、译原理 句型句型 (sentential forms) 设设 CFG G = (VN, VT, P , S )，称，称 (VN VT)* 为为 G 的一个的一个句型句型，当且仅当，当且仅当 S . 若若 S ，则，则 是一个是一个左句型左句型; 若若 S ，则，则 是一个是一个右句型右句型. 若句型若句型 VT* ，则称，则称 为一个为一个句子句子（sentence）. lmrm 上下文无关语言及其描述上下文无关语言及其描述编译原理 上下文无关文法的语言上下文无关文法的语言 设设 CFG G = (VN, VT , P , S )，定义，定义 G 的语言为的语言为 L(G) = w w VT*