词法分析有穷自动机

例3.4 Z→ A→ B→
有正规文法G： 0A 0A | 0B 1A | ε
例3.5 A→ B→ C→
有正规文法G： aB | bB aC | a | b aB
例3.6 Z→ U→ V→
有正规文法G： Z=0(0|01)*0 U0 | V1 A=(a|b)(aa)*(a|b) Z1 | 1 Z=(10|01)(10|01)* Z0 | 0
A
B
r2 ε
A C
A
B
ε
B
r1
④R为复合正规式？
例3.12 3.13 P41
教学进度
3.4.4 NFA确定化为DFA
方法（子集法） 1、改造M为M’： ①引进新的初态结点X、终态结点Y； ②对M的状态转换图实施分裂（替换）
计算机科学与工程系
2、将M’进一步变换为DFA :
①状态子集T的闭包_CLOSURE(T) ②定义状态集Ta = _CLOSURE(J) ③从DFA的初态_CLOSURE({X})开始计算状态转换矩阵；直到 不再产生新的状态子集为止。
第三章
• • • • • •
词法分析与有穷自动机
计算机科学与工程系
词法分析器的功能与输出 单词符号的两种定义方式 正规表达式与有穷自动机 正规文法与有穷自动机 词法分析器的设计 词法分析程序自动构造工具LEX简介
教学进度
3.1 词法分析器的功能

计算机科学与工程系
词法分析：对字符串表示的源程序进行从左到右的扫描和 分解，根据语言的词法规则识别出一个个具有独立意义的 单词符号。
教学进度
3.3 单词符号的两种定义方式
单词符号结构的描述方法：
计算机科学与工程系
正规文法（３型文法）(regular grammar)

ε
ε
2
ε
6 b
ε
f
3.4.5 DFA的最小化（化简）
• 最少状态DFA 对于一个DFA M，存在一个最少状态DFA M’， 使得L(M’)=L(M)。 (a)没有多余状态 (b)没有两个状态是互相等价的 结论： 一个NFA 对应的DFA不惟一 但它对应的最小化DFA不计同构是惟一的
• 多余状态的例子 a
例
正规式 φ
ε
a a|b ab (a|b)(a|b) a* ba* (a|b)*
正规集 φ {ε } {a} L(a|b)=L(a) ∪ L(b)={a,b} L(ab)=L(a)L(b)={ab} {aa,ab,ba,bb} { ε ,a,aa,aaa,…} {b,ba,baa,baaa,…} {所有由a和b组成的字}
• 例 DFA M=({0,1,2,3},{a,b}, f ,0,{3}) 其中 f 为： f (0,a)=1 f (0,b)=2 f (1,a)=3 f (1,b)=2 f (2,a)=1 f (2,b)=3 f (3,b)=3 f (3,a)=3
3.4.1 确定有穷自动机(DFA) • DFA的表示方法 两种：矩阵和图形的方式 矩阵称为状态转换矩阵 图形称为状态转换图
• NFA M所接受字符串的集合称为NFA M所能 识别的语言，记为L(M)。 • NFA的确定化 DFA是NFA的特例
NFA M存在与之等价的DFA M’,L(M)=L(M’) 与某一NFA等价的DFA不惟一 正规式 NFA 正规文法 DFA
3.4.4 NFA 确定化
• 状态集合I的空闭包：ε -closure(I) 它是一个状态集合，包含 ： ♠ I中任何状态q ♠ I中任何状态q经任意条空弧到达的任何状态 • 状态集合I的a弧转换：Ia 定义一个状态集J，J是I中所有状态经一条a 弧到达的状态的全体 Ia＝ε -closure(J)

5
例 过河问题 分析（续）
初始状态：MWGC-φ；终止状态：φ-MWGC。 g
MWGC-φ
WC-MG
问题：
6
例 过河问题 状态转换图
起始 g
MWGC-φ g
g φ-MWGC
g
7
WC-MG
m
m MWC-G
w
w
c
C-MWG
c W-MGC
g
g
MGC-W c
MG-WC
w
m
c G-MWC
m
gg MWG-C
+dd. ddd;
输入符号串
数字 数字
SB
.
数字
+
A
H
-.
数字
.G
接收：若扫描完输入串， 且在一个终止状态上结 束。
数字 阻塞：若扫描结束但未 停止在终止状态上；或 者为能扫描完输入串 （如遇不合法符号）。
不完全描述：某些状态 对于某些输入符号不存 在转换。
练习：+34.567 .123 3.4.5
w
有穷自动机（FA）
数字系统：可以从一个状态移动到另一个状态；每次 状态转换，都上由当前状态及一组输入符号确定的；可以 输出某些离散的值集。
FA：一个状态集合；状态间的转换规则；通过读头来 扫描的一个输入符号串。
读头：从左到右扫描符号串。移动（扫描）是由状态 转换规则来决定的。
8
读头
一个FA的例子
(3)运行： 串f(，Q,且t1tt21)∈= Σf(，f(Qt1,t2t1∈), Σt2*)，其中Q∈K， t1t2为输入字符
17
例３
题：试证abba可为例1的DFA M所识别（所接受）。

界符＝ ｌ １ Ｉ ， ； ． （Ｉ） 其中ｌ 示 ａ 表 —— ｚ中 的 任 何 一 个 字 母 ， 示 ｄ表 ９中的任何一 个数 字 。 ｅ＊也 都 是 正 规 式 ， 们 所 表 示 的 正 规 集 分 别 为 ｌ 它 关 键字 也 是一 种单 词 ，关 键 字集 合是 标 识符集 合 Ｌｅ） （１ＵＬｅ） （１・（２， （１ ； （１Ｌｅ） （２， ｅ）Ｌｅ）Ｌｅ） ， Ｌ （ ） 的子集 ， 关键字 与标 识符 的构 词原则 相 同。 （）仅 由有 限次 使 用上 述 三个 步骤 而 定 义 的表 达 ４ 式才 是 ∑上 的正 规式 ， 由这些 正 规式 所 表示 的字 集 仅 整数 前 面 的正 负 号 在 词 法 分 析 中可看 作 运 算 符 ， 因此 只定 义无 符号 整数 的词法 。 才是 ∑上 的正 规集 。［ １ １ － ． 正 规式 可 用 来 描述 符 号 串所 遵从 的规则 ，用 正规 ２３２将词法 转化 为有穷 自动机形 式 的词法模 型
２ １ 年第 １ ０ １ １期
福 建 电
脑
９ ５
有 穷 自动机在词 法分 析器建模 中的应 用研究
罗 海 丽
（内 蒙古科技 大 学 信息工程 学院 内蒙古 包头 ０ ４ １ １ ０ ０）
【 摘 要】 ：有 穷自动机可用于描述语言的词法模型，有穷自动机形式的词法模型与特定的控制程序 相 配合 可构 成语 言 的词 法分析 器 。介 绍 了利 用有 穷 自动机 建 立语 言的词 法模 型及 以此 词 法模 型为基础 构 建词 法分析 器的过程 。实例 证 明 ， 方 法构造 的词 法 分析 器正确 、 该 有效 。 【 关键词】 ：有穷 自 动机； 正规文法； 控制程序； 词法模型； 词法分析器