复习一下编译,在龙书中提到的NFA(不确定有穷自动机)到DFA(确定有穷自动机)的转换,master regular expression中提到的不依赖于正则表示式的识别问题,不用精心构造正则表达式,只需将正则表达式转化为NFA,进而转化为DFA,则任何长度为n的字符串都可以在O(n)时间内判断出来是否符合该正则表达式。关于正则表示式如何转化为NFA暂略,这里演示一下使用子集构造算法将NFA转化为DFA,转换为后对于词法分析能显著提高效率。
演示@google code
1.示例 NFA
2.转换后DFA:
3.代码结构:
Ext.ns("Ext.ux.compiler");
/*
状态机基类
*/
Ext.ux.compiler.Fa = function () {
}
Ext.override(Ext.ux.compiler.Fa, {
/*
用于简化dfa状态标记,得到s的状态index
*/
getStateIndex: function (s) {
},
/*
加入终结状态
*/
addEndState: function (s) {
},
/*
加入转移字符,排除x空字符
*/
addInput: function (c) {
},
/*
加入状态
*/
addState: function (s, end) {
},
/*
是否为终结状态
*/
containEndState: function (array) {
},
/*
是否已经包含该状态
*/
containState: function (array, end) {
}
});
/*
DFA类
*/
Ext.ux.compiler.Dfa = function () {
}
Ext.extend(Ext.ux.compiler.Dfa, Ext.ux.compiler.Fa, {
/*
配置dfa状态图
从from状态经input字符转移到to状态
*/
transState: function (from, to, input) {
},
/*
得到标记简化的新dfa
*/
genCompress: function () {
}
});
/*
Nfa类
*/
Ext.ux.compiler.Nfa = function (nfaConfig, nfaStart, nfaEnd) {
}
Ext.extend(Ext.ux.compiler.Nfa, Ext.ux.compiler.Fa, {
/*
states中是否包含nfa的终结状态
*/
isCrossEndState: function (states) {
},
/*
初始化,状态图,开始状态,结束状态
*/
init: function (nfa, nfaStart, nfaEnd) {
},
/*
配置状态图,同DFA类
*/
transState: function (from, to, input) {
},
/*
递归得到由state从空字符可以转到的状态,注意不要重复就行了
*/
x_closure: function (state, currentStates) {
},
/*
从state状态经由a字符可以转换到的状态,注意a不要为x(空字符)
*/
move: function (state, a) {
},
/*
得到该NFA对应的DFA
*/
genDfa: function () {
}
});
分享到:
相关推荐
NFA到DFA转换 存储NFA与DFA,编程实现子集构造法将NFA转换成DFA。 (1)确定NFA与DFA的存储格式,为3个以上测试NFA准备好存储文件。 (2)用C或JAVA语言编写将NFA转换成DFA的子集构造法的程序。 (3)经测试无误。...
编译原理中NFA到DFA的自动转换程序,测试过,可以正确运行, 自己写的
采用c++语言编程,从而实现NFA与DFA之间的转换,代码简单
编译原理NFA到DFA的转换源码
这是一个可以实现正规式到NFA的转换,NFA 转换为DFA,DFA的最小化的程序
自己用C语言做的NFA到DFA的转换 有较为详细的备注,希望有所帮助。
NFA到DFA的转化程序,Java
从nfa到dfa。编译原理课程题目。计算机、软件。
NFA到DFA的转换过程.doc
NFA到DFA的转换 这是用visual C++ 编写的程序 有注释!
用C语言实现NFA到DFA的转换过程 NFA (nondeterministic finite-state automata)是不确定性有限状态自动机的简写,NFA的定义为: 一个不确定性有限状态自动机由以下部分所组成: A. 一个有限的输入字符集I B. 一个...
用Java语言实现NFA到DFA的等价变换 姓名:桂日培 单位:湖北工业大学计算机学院02计算机1班 学号:0212002123 时间:2005年10月31日
NFA转换成DFA代码,计算理论Project1
本人用c++写的一个将NFA转换成DFA的程序,希望大家指教。
编译原理课的大作业 包含三个小实验 在一个cpp文件里 正则表达式转换为nfa nfa转换为dfa dfa最小化 个人原创代码
介绍NFA到DFA的转换过程 通俗易懂 适用于编译技术初学者
编译原理实验 NFA转DFA python实现
本代码包含NFA与DFA的表示,NFA 转 DFA,DFA最小化,NFA与DFA语言子集等。
NG_NFA_DFA相互转换NG_NFA_DFA相互转换NG_NFA_DFA相互转换NG_NFA_DFA相互转换NG_NFA_DFA相互转换