湖州网站推广,微网站开发手机模拟器,我国外贸网站的建设,阿里邮箱登录一、正规式和正规集
正规集#xff1a;程序设计语言的单词表、词汇集构成的集合#xff0c;即是字的集合。它有一定特殊性#xff0c;我们称之为正规集。用来代表程序语言的单词表。
正规式#xff1a;可以说是正规集的名称。
正规集可以用正规表达式#xff08;简称正…一、正规式和正规集
正规集程序设计语言的单词表、词汇集构成的集合即是字的集合。它有一定特殊性我们称之为正规集。用来代表程序语言的单词表。
正规式可以说是正规集的名称。
正规集可以用正规表达式简称正规式表示正规表达式是表示正规集一种方法一个字集合是正规集当且仅当它能用正规式表示
比如冯诺依曼构造自然数的方案使用集合来定义正规集,表达式来表达正规式
集合表达式0123 再比如
DIM单独来说是一个正规式也可以表达含有DIM和空集的正规集即{DIM}。
DIMIF可以当作一个正规式则{DIMIF}为其对应的正规集。 二、正规式和正规集的递归定义
对给定的字母表(为字母表):
和都是上的正规式它们所表示的正规集为和任何 则是上的正规式它所表示的正规集为假定和都是上的正规式它们所表示的正规集为和则 1为正规式它所表示的正规集为 2为正规式做连接它所表示的正规集为连接 3为正规式它所表示的正规集为闭包
优先级‘’比‘|’高
仅由有限次使用上述三步骤而定义的表达式才是上的 正规式仅由这些正规式表示的字集才是上的正规集。 所有词法结构一般都可以用正规式描述
若两个正规式所表示的正规集相同则称这两个正规式等价。如 b(ab)*(ba)*b 证明 左侧 L(b(ab)*) L(b)L((ab)*) L(b)(L(ab))* L(b)(L(a)L(b))* {b}{ab}* {b}{ ,ab, abab,ababab,…} {b,bab,babab,bababab,…} 右侧 L((ba)*b) L((ba)*)L(b) (L(ba))*L(b) (L(b)L(a))*L(b) {ba}*{b} { ,ba,baba,bababa,...}{b} {b,bab,babab,bababab,...} 由于L(b(ab)*) L( (ba)*b) 因此b(ab)*(ba)*b 等价成立式
| | 交换律
|(|) (| )| 结合律
( ) ( ) 结合律
(| ) | 分配律
(| ) | 分配律 ! 三、有限自动机Finite Automata
确定与非确定统称为有限自动机。
1.确定有限自动机DFADeterministic Finite Automata
对状态图进行形式化则可以下定义
确定有限自动机 (DFA) M 是一个五元式
此处M是指其DFA实例 DFA M
M(S, , f, , F),其中: 1.S:有穷状态集即包含起点重点在内的各个状态 2.:输入字母表(有穷)即状态改变的条件 3.f:状态转换函数为 的单值部分映射即由A状态到B状态的改变 f(s,a) s’ 表示当现行状态为s 输入字符为a时将状态转换到下一状态s’s’称为s的一个后继状态 4.:是唯一的一个初态即起点唯一 5. 终态集(可空)即最终状态不唯一。
比如
DFA M({0123}{ab}f0{3})
其中f 定义如下
f(0a) 1 f(0b) 2
f(1a) 3 f(1b) 2
f(2a) 1 f(2b) 3
f(3a) 3 f(3b) 3 如上图所示DFA 可以表示为状态转换图
假定 DFA M含有m个状态和n个输入字符这个图含有m个状态结点每个结点顶多含有 n 条箭弧射出且每条箭弧用 Σ 上的不同的输入字符来作标记 对于Σ * 中的任何字若存在一条从初态到某一终态的道路且这条路上所有弧上的标记符连接成的字等于则称为DFA M 所识别(接收)
DFA M 所识别的字的全体记为 L(M) 换言之从初态到终态的字符构成了一个字一个字符也可以定义为一个字。而所有的初态到终态可形成的字的集合就是字符集。
字与字的组合或者单个字可以作为一个正规式其所代表的就是正规集。 2.非确定有限自动机 (NFANondeterministic Finite Automata)
一个非确定有限自动机 (NFA) M
是一个五元式 M(S, , f, , F) 其中
1.S: 有穷状态集
2.:输入字母表(有穷)
3.f: 状态转换函数为的部分映射
4. :是非空的初态集
5 终态集 ( 可空 ) 对于 * 中的任何字若存在一条从初态 到某一终态的道路且这条路上所有弧上 的标记字连接成的字等于 ( 忽略那些标记为的弧 ) 则称为 NFA M 所识别 ( 接 收 )
NFA M 所识别的字的全体记为 L(M) NFA示例 3.区别 DFA
如有后继状态则其后继状态是唯一的只有一个初态弧上标记仅能为长度为1的字或单个字符易于程序实现
NFA
给定当前状态其后继状态不是唯一的。可有多个初态。弧上的标记可以是字符、字还可以是正规式。同一个字可以出现在同状态的多条弧上易于人工设计 DFA是NFA的特例 4.NFA与DFA
定义对于任何两个有限自动机M和M’ 如果L(M)L(M’)则称 M 与 M’ 等价
自动机理论中一个重要的结论判定两个自动机等价性的算法是存在的
对于每个NFA M 存在一个DFA M’使得L(M)L(M’)
DFA 与 NFA 描述能力相同 5.将NFA等价转换为DFA
1.假定 NFA M我们对M的状态转换图进行以下改造 1) 引进新的初态结点X和终态结点YX,YS从X到中任意状态结点连一条箭弧从F中任意状态结点连一条箭弧到 Y 。
即我们给一个NFA M多个初态前加了一个状态使得其有唯一初态末态同理 2) 对M的状态转换图进一步施行替换其中k是新引入的状态。
即我们将aabb这样的换位下图34过程 替换方法 通过上述过程逐步把这个图转变为每条弧只标记为上的 一个字符或
最后得到一个 NFA M’ 显然 L(M’)L(M) 2.接着我们再把把上述 NFA 确定化——采用子集法
概念
设 是的状态集的一个子集定义 的 - 闭包 - closure() 为 : i) 若 s 则 s-closure(I) ii) 若 s 则从 s 出发经过任意条弧而能到达的任 何状态 s’ 都属于 -closure() 即 -closure(){s’| 从某个 s‘| 出发经过任意条弧 能到达 s’ 设 是中的一个字符定义 -closure(J) 其中 J 为 中的某个状态出发经过一条 弧而到达的状态集合。 比如 -closure({1}) {1 2} (从1出发看与它距离一个的状态就为
J {5 4 3}从 -closure({1}) 出发需要经过一个距离的状态就是J -closure(J) -closure({5 4 3}) {5 4 3 6 2 7 8} 6.正规式与有限自动机的等价性
对任何 FA M 都存在一个正规式 r 使得 L(r)L(M) 。对任何正规式 r 都存在一个 FA M 使得 L(M)L(r) 。
证明
1.对上任一 NFA M 构造一个上的正规 式 r 使得 L(r)L(M) 。 首先在 M 的转换图上加进两个状态 X 和 Y 从 X 用弧连接到 M 的所有初态结点从 M 的所有终态结点用弧连接到 Y 从而形成一 个新的 NFA 记为 M’ 它只有一个初态 X 和一个终态 Y 显然 L(M)L(M’) 。然后反复使用下面的一条规则逐步消去的 所有结点直到只剩下 X 和 Y 为止最后 X 到 Y 的弧上标记的正规式即为所 构造的正规式 r显然 L(r)L(M)L(M’)
替换方式即为之前的相反方向。 注意要保留下每一个状态。比如下图我们将1.左上的图变换至右上的图2.再将右上的图变为最下面的图。 证明:
2.对于上的正规式r构造一个 NFA M使 L(M)L(r)并且 M 只有一个终态而且没有从该终态出发的箭弧。
下面使用关于 r 中运算符数目的归纳法证明上述结论。 1若 r 具有零个运算符则 r 或 r 或 ra 其中 a 。此时下图所示的三个有限自动机显然符合上述要求。
左识别
中识别空
右长度为1的字符 2假设结论对于少于 k(k1) 个运算符的正规式成立。当 r 中含有 k 个运算符时 r 有三种情形
情形 1
和中运算符个数少于k 。从而由归纳假设对 存在使得 并且 没有从终态出发的箭弧 i1,2 。 不妨设 在 中加入两个新 状态。 情形 2
设 同情形 1(i1,2) 情形 2
设同情形1 7.将正规表达式转换为有限自动机的算法 1构造上的 NFA M’ 使得 L(V)L(M’)
把 V 表示成 一样的替换逻辑 2逐步把这个图转变为每条弧只标记为上的 一个字符或最后得到一个 NFA M’ 显然 L(M’)L(V) 比如 四、确定有限自动机的化简
是指对DFA M的化简 : 寻找一个状态数比 M 少的 DFA M’ 使得 L(M)L(M’)
假设 s 和 t 为 M 的两个状态称 s 和 t 等价如果从状态 s 出发能读出某个字任意而 停止于终态那么同样从 t 出发也能读出而停止于终态反之亦然
两个状态不等价则称它们是可区别的存在一个使得从状态 s 出发能读出某个字任意停止于终态从 t 出发读出停止于非终态或者反过来 DFA M 最少化的基本思想
把 M 的状态集划分为一些不相交的子集 使得任何两个不同子集的状态是可区别的 而同一子集的任何两个状态是等价的。 最后让每个子集选出一个代表同时消去其他状态
按照上述原则对 DFA 的状态集合 S 进行第 一次划分将集合分为终态和非终态。即找到一个字划分连个状态比如空字 对 M 的状态集进行划分
1 首先把 S 划分为终态和非终态两个子集 形成基本划分。
2 假定到某个时候已含 m 个子集记为检查中的每个子集看是否能进一步划分:
对某个令 若存在 一个输入字符 a 使得 不会包含在现行的某个子集中则至少应把 分为两个部分。
2.1 如何划分为两个部分
假定状态 和 经 a 弧分别到达 和 : 和 属于现行中的两个不同子集。说明有一个字 读出 后到达终态而 读出后不能到达终态或者反之。那么对于字 a 读出 a 后到达终态 而 读出 a 不能到达终态或者反之所以 和 不等价将 I (i) 分成两半使得一半含有 :,且 s 经 a 弧到达 t, 且 t 与 属于现行 中的同一子集 ;另一半含有 : 一般地对某个 a 和 若 落入现行 中 N 个不同子集则应把 划分成 N 个不相交的组使得每个组 J 的 都落入的 同 一子集。这样构成新的划分。 3 重复上述过程直到 所含子集数不再增长。
4 对于上述最后划分 中的每个子集我们选取每个子集 中的一个状态代表其他状态 则可得到化简后的 DFA M’ 。
5 若 含有原来的初态则其代表为新的初态 若 含有原来的终态则其代表为新的终态 我们使用上述算法对下图优化 首先把其分为两个集合非终态和终态集合 随后我们判断非终态集合识别a时发现3不在当前子集中 于是将抵达1的与抵达3的分开 再次判断第一个集合判断识别a时抵达状态是否在子集判断识别b时状态是否在子集中发现不在 于是将抵达2的和抵达4的分开 再次判断发现非终态集合划分完毕。判断终态发现均在子集中 由此可以画出 五、词法分析器的自动产生 --LEX Yacc 与 Lex 快速入门 http://www.ibm.com/developerworks/cn/linux/sdk/lex/index.html UNIX, LINUX The Lex Yacc Page http://dinosaur.compilertools.net/ Flex (The Fast Lexical Analyzer) http://flex.sourceforge.net/ for Windows: http://gnuwin32.sourceforge.net/packages/flex.htm 六、正规文法与有限自动机的等价性
对于正规文法 G 和有限自动机 M 如果 L(G) L(M) 则称 G 和 M 是等价的
关于正规文法和有限自动机的等价性有以下结论
1. 对每一个右线性正规文法 G 或左线性正规文法 G 都存在一个有限自动机 (FA) M 使得
2. 对每一个 FA M 都存在一个右线性正规文法 和左线性正规文法 使得
例子
右线性文法-NFA
推导 左线性文法-NFA
推导 证明
1.对每一个右线性正规文法 G 或左线性正规文法 G 都构造一个有限自动机 (FA) M 使得 L(M) L(G) 。
(1) 设右线性正规文法 。将 中的每一非终结符号视为状态符号 并增加一个新的终结状态符号 f 。 令 其中状态转换函数由以下规则定义 (a)若对某个 及 P 中有产生式 A→a 则令 (A,a)f (b) 对任意的 及 设 P 中左端为 A 右端第一符号为 a 的所有产生式为 A→|…| 不包括 A→a 则令 (A,a){ ,…, } 。
显然上述 M 是一个 NFA 。 (2) 设左线性正规文法 。将 中的每一非终结符号视为状态符号并 增加一个初始状态符号 。 令 M其中状 态转换函数由以下规则定义 (a) 若对某个 及 若 P 中有产生式 A→a则令 ( ,a)A (b) 对任意的 及 若 P 中所有右端第一符号为 A 第二个符号为 a 的产生式为 则令 (A,a) 。
与 (1) 类似可以证明 L(G) L(M) 2.对每一个 DFA M 都存在一个右线性正规文法 和左线性正规文法 GL 使得 L(M) L() L() 。
设 DFA
(1)若 我们令 其中 P 是由以下规则定义的产生式集合
对任何 及 A,BS 若有 (A,a)B 则: (a)当 BF 时令 A→aB (b) 当 BF 时令 A→a|aB 。
对任何 不妨设 其中 (i1,…k) 。若 则存在一个最左推导 因而在 M 中有一条从 出发依次经过 到达终态的通路该通路上所有箭弧的标记依次为 。反之亦然。所 以 wL(GR ) 当且仅当 wL(M) 。 (2)现在考虑 的情形,
因为 所以 。但不属于上面构造的 所产生的语言 L() 。不难发现 L()L(M)-{ } 。
所以我们在上述 GR 中添加新的非终结符号 ( )和产生式 并用 代替 作开始符号。这样修正 后得到的文法 仍是右线性正规文法并且 L()L(M) 。
(2) 类似于 (1) 从 DFA M 出发可构造左线性正规文法 使得 L()L(M) 。 最后由 DFA 和 NFA 之间的等价性结论 2 得证明。 小结
