PPT《*》

* 《编译原理与技术》讲义 * 编译原理与技术 词法分析 (2) * 《编译原理与技术》讲义 * 有限自动机 有限自动机(Finite Automata-FA)是种更一般化的状态转换图.

分为NFA和DFA.词法分析器自动生成:正规式 NFA DFA 词法程序 非确定有限自动机 确定的有限自动机 * 《编译原理与技术》讲义 * 非确定有限自动机-NFA NFA Mn 是一个五元组 Mn =(?, S, S0,F,?),其中:?-有限字母表(输入符号集)S-有限状态集S0-非空初态集合,S0?SF-终态集合,F ?S?-状态转换函数,S x ?* ? 2S * 《编译原理与技术》讲义 * 确定的有限自动机-DFA DFA Md 是一个五元组 Md =(?, S, S0,F,?),其中: ?, S, S0,F 同NFA中的定义,而?定义如下: ? :S x ? ? S , 为一单值映射函数. * 《编译原理与技术》讲义 * 有限自动机的表示 1)状态转换图 开始状态 一般状态 终态 s ?(s,a)=t t a s ?(s,?)=t t ? * 《编译原理与技术》讲义 * 有限自动机的表示 2)状态转换矩阵(表) ?*状态(集) a b … Si {Sj} … Sj … … ?(Si,a) = {Sj} * 《编译原理与技术》讲义 * 有限自动机的表示 e.g.7 NFA Mn =(?, S, S0,F,?),其中:? = { 0,1 } , S = {S0, S1 , S2 , S3 , S4 },F={S2 , S4} ?(S0,0)= {S0, S3 } ?(S0,1)= {S0, S1 } ?(S1,0)?(S1,1)= {S2} ?(S2,0)= {S2}?(S2,1)= {S2} ?(S3,0)= {S4}?(S3,1)= ? ?(S4,0)= {S4}?(S4,1)= {S4} * 《编译原理与技术》讲义 * 有限自动机的表示 e.g.7 中NFA的状态转换图如下: S0 S3 S1 0,1

0 0 0,1

1 1 0,1 S2 S4 * 《编译原理与技术》讲义 * 有限自动机的表示 e.g.7 中NFA的状态转换矩阵(表)如下: ?*状态(集)

0 1 S0 {S0, S3 } {S0, S1 } S1 ? {S2} S2 {S2} {S2} S3 {S4} ? S4 {S4} {S4} * 《编译原理与技术》讲义 * 有限自动机识别的语言 e.g.8 下面FA识别(接受)的串是什么? S0 S1 S2

0 1 FA识别(接受)串?∈?* , 如果存在一个从FA的初态到某个终态的(状态)转换路径,该路径上所有标记的字符依次连接为?.FA M 所识别的语言 L(M)L(M) = {? | M 识别 ?∈?* } * 《编译原理与技术》讲义 * 有限自动机识别的语言 e.g.9 下面DFA M识别的语言L(M)是什么? S2 S1

0 1 S0 S3

1 1

1 0

0 0 S

1 0 * 《编译原理与技术》讲义 * 有限自动机识别的语言 e.g.9 L(M) = {含偶数个0和偶数个1的0,1串} S2 S1

0 1 S0 S3

1 1

1 0

0 0 S2 S1 S0 S3 偶数个

0 与偶数个

1 的0,1串 偶数个

0 与奇数个

1 的0,1串 奇数个

0 与偶数个

1 的0,1串 奇数个

0 与奇数个

1 的0,1串*《编译原理与技术》讲义 * 有限自动机识别的语言 e.g.10 下面DFA M识别的语言L(M)是什么? S2 S1 S0

0 1

0 1

0 1 * 《编译原理与技术》讲义 * 有限自动机识别的语言 e.g.10 L(M) = { 能被

3 整除的二进制数(串) } S2 S1 S0

0 1

0 1

0 1 S2 S1 S0 能被3整除 被3整除…余1 被3整除…余2 * 《编译原理与技术》讲义 * 有限自动机识别的语言 e.g.10 L(M) = { 能被

3 整除的二进制数(串) }二进制串

10010 , 即十进制18的识别过程: S2 S1 S0

0 1

0 1

0 输入串

1 0

0 1

0 * 《编译原理与技术》讲义 * 比较 DFA 和NFA(1) DFA NFA ? :S x ? ? S ? :S x ? ? 2S 没有 ?转换 有 ?转换 对?∈?*,DFA的 识别 路径唯一且完全由?确定 对?∈?*的 识别 路径可能存在多条不同的路径 对于正规式R,均有DFA Md和NFA Mn,使得L(Md) = L(Mn)=L(R),即两者识别正规语言能力相同(等价) * 《编译原理与技术》讲义 * 比较 DFA 和NFA(2) DFA NFA 容易实现-当输入串结束时(或不存在相应状态转换)时,若当前状态为终态即为接受 已读入 的串,否则拒绝. 由于面临同样输入符号存在多重状态转换或存在?转换的选择,实现较为复杂.一般地,NFA接受串?如果它在读完串?后 能够 到达某终态. 识别相同正规集的DFA和NFA: DFA的规模(在状态数和状态转换上)一般比相应的NFA复杂(可以达到指数级) * 《编译原理与技术》讲义 * 比较 DFA 和NFA(3) e.g.11 识别正规式(0|1)*01的DFA和NFA S2 S1 S0