编译原理 第二章词法分析-2

编译原理课件-第二章词法分析-2

2.3.2 NFA的定义 的定义 NFA的必要 的必要识别程序设计语言中所有记号的DFA遇到的 遇到的 识别程序设计语言中所有记号的 问题 典型的程序设计语言中都有许多记号， 典型的程序设计语言中都有许多记号，每一 个记号都能被其自己的DFA识别出来 个记号都能被其自己的 识别出来 理论上应该能将所有的记号都合并为一个巨 大的DFA。 大的 。

编译原理课件-第二章词法分析-2

1

letter digit < < <

letter,digit [other] 2 digit [other] 4 = 6 > 8 10

3 5 7 9

这不是一个DFA。如果不使用系统化的方法 。 这不是一个 将所有的记号都合并为一个巨大的DFA,将 将所有的记号都合并为一个巨大的 ， 非常复杂。 非常复杂。

编译原理课件-第二章词法分析-2

解决这个问题的方法 扩展到NFA (对于当前的输入，当前 对于当前的输入， 将DFA扩展到 扩展到 对于当前的输入 的状态将转换为多个状态) 的状态将转换为多个状态 NFA 转换为 DFA的算法 的算法

编译原理课件-第二章词法分析-2

不确定的有穷自动机( 不确定的有穷自动机(NFA) NFA M=(S,Σ,T,S0,A), 其中 1. S 是状态的集合 2. ∑是字母表 是字母表 3. T是转换函数 是转换函数: 是转换函数 S X (∑∪{ε})-> S的子集 ∪ 的子集 4. S0∈S 初始状态 5. A S 接受状态集合

编译原理课件-第二章词法分析-2

NFA 类似于 DFA,除了 ，扩展 ∑ 包括 ε NFA 可以包含 ε-转换 无需考虑输入串就 转换—无需考虑输入串就 转换 有可能发生的转换

ε 1 2扩展T的定义 扩展 的定义 每一个字符都可以导致多个状态。因此T的值 每一个字符都可以导致多个状态。因此 的值 是状态的一个集合而不是单独的状态

编译原理课件-第二章词法分析-2

M=({S, Z},{0,1},f,S,{Z}) 例 NFA M=({S,P,Z},{0,1},f,S,{Z}) 其中 ={S, f(S,0)={P} f(S,1)={S,Z} f(Z,0)={P} f(Z,1)={P} f(P,1)={Z} 状态图表示: 状态图表示:1 1 S 0 0,1 P 1 Z

矩阵表示: 矩阵表示: S P Z 0 {P} {} {P} 1 {S,Z} {Z} {P}

0 0 1

编译原理课件-第二章词法分析-2

L(M): 由自动机 M 所接受(识别)的语 所接受(识别) 言 L(M) :is the set of strings of character字符 字符c1c2…cn ,每一个 都 每一个ci 字符 属于 ∑∪{ε}, 且存在关系：s1 在 ∪ , 且存在关系： T(S0,c1)中,s2在T(S1,c2)中,…,Sn 在 中 在 中 T(Sn-1,cn) 中， s0 是初始状态， Sn 是A 是初始状态， 的元素c1c2…cn 中的任一 ci 都可能是 都可能是ε 真正被接受的串是删除了ε的串 真正被接受的串是删除了 的串 c1c2…cn

编译原理课件-第二章词法分析-2

非确定性 接受特定串的转换序列并不由状态和下 一个输入字符在每一步确定下来

编译原理课件-第二章词法分析-2

例如 2 a 1 a 3 ε下面两个转换序列都可接受串 “abb” : 1 1 a a 2 3 b ε 4 4 ε ε b b 4 4 ε 2 b 4

b ε

ε 4

2 2

编译原理课件-第二章词法分析-2

2.3.3 用代码实现有穷自动机构建扫描程序(词法分析程序)的过程: 构建扫描程序(词法分析程序)的过程 正则表达式 DFA 扫描程序

正则表达式表示一种模式， 正则表达式表示一

种模式，用来描述记号 DFAs 表示按照正则表达式描述的模式接受符 号串的算法

编译原理课件-第二章词法分析-2

从正则表达式到DFA(2.4节) ( 节 从正则表达式到 有穷自动机构造词法分析程序

编译原理课件-第二章词法分析-2

1 用代码实现 DFA用代码实现DFA的一般算法 的一般算法 用代码实现 用一个变量保持当前的状态 将转换写成一个双层嵌套的case语句而 将转换写成一个双层嵌套的 语句而 不是一个循环 第一个case语句测试当前的状态 第一个 语句测试当前的状态 嵌套着的第2层测试输入字符及所给的状 嵌套着的第 层测试输入字符及所给的状 态

编译原理课件-第二章词法分析-2

例如:接受标识符的 例如 接受标识符的DFA 接受标识符的 letter letter [other] digit state:=1;{start} while state=1 or 2 do case state of 1:case input character of letter:advance the input; state:=2; else state:=…{error or other}; end case

1

2

3

编译原理课件-第二章词法分析-2

letter

1

2

letter [other] digit

3

2:case input character of letter,digit:advance the input; state:=2; else state:=3; end case; end case; end while; if state=3 then accept else error;

编译原理课件-第二章词法分析-2

2 用代码实现 用代码实现DFA的状态转换表 的状态转换表使用转换表，可以用代码实现任一 使用转换表，可以用代码实现任一DFA

编译原理课件-第二章词法分析-2

代码图解中用到的变量 转换被保存在一个转换数组 “T”中，T由状 中 由状 态和输入字符索引； 态和输入字符索引； 先行输入的转换是由布尔数组 “Advance” 给出, 它们也由状态和输入字符索引； 给出 它们也由状态和输入字符索引； 由布尔数组 “Accept”给出的接受状态由状 给出的接受状态由状 态索引