当前位置: 首页 > 图文教程 > 开发语言 > VC++ > 确定有穷自动机分析内核

VC++
用 auto_ptr 类模板帮助动态内存管理
走近 STL
一步一步学STL标准模板库
使用 <multimap> 库创建重复键关联容器
使用 <map> 库创建关联容器
用 vectors 改进内存的再分配
用函数模板实现和优化抽象操作
STL 字符串类与 UNICODE 及其它......
如何在Dll中导出STL类
再谈“在STL列表（Lists）中插入不同类型的对象”
使用::std::vector<>作为管理动态数组的优先选择
三种常见中文内码的转换方法
JNI 中文处理问题小结
构建 GB2312 汉字库的 unicode 码表
正则表达式简介
在非MFC程序中引用CString
UTF-8与GB2312之间的互换
宽字符标量L"xx"在VC6.0/7.0和GNU g++中的不同实现
用VC++设计语法编辑器
C语言中对时间和日期的处理

No. « 8 9 10 11 »

技术文章搜索

关键字

VC++ 中的 确定有穷自动机分析内核

出处:互联网   整理: 软晨网（RuanChen.com）   发布: 2009-10-30   浏览: 71 ::
收藏到网摘: n/a

确定有穷自动机分析内核


作者/孙雪青


下载源代码

    前些时候学习编译原理，同时也为 DocWizard 做词法分析技术的准备，于是便想出了一种词法分析内核。这个分析内核可以在不改变代码的情况下分析不同的 DFA。

分析器的基本构造

如图一所示，脚本 Scripts 进入分析内核 ParsingKernel，分析内核根据 DFA 规则作词法分析，生成单词序列 WordsSequence。
   

图一

其中的 DFA Rules 其实就是 DFA 中的状态转换规则。分析内核在工作时需要查阅规则表。只要更换这个规则表，就可以分析不同的词法。

工作原理

    例子程序中的 CStateChangeRule 代表一条转换规则。它由如下三个数据构成：

  • 当前状态编号：int nCurState
  • 下一个状态编号：int nNextState
  • 需要匹配的字符：CHAR_RANGE route[ROUTE_BUF_LEN]
    内核在刚开始工作的时候，设定当前状态为 0，然后对输入字符串 pszLine 进行扫描。Route()函数根据当前需要处理的字符和当前状态，计算出下一个状态。Accept()函数负责接收一个单词。 
void CAjaxParserDlg::OnParse() {	char *pszLine = " void CAjaxParserDlg::OnParse() +12.3 12.3 -12.3 -.12 +.12 .12 +12. -12. 12. .023 ";	int i=0, nLen, nState=0, nNext=-1, nStart;	nLen = strlen(pszLine);	while(i<nLen)	{	if(nState==0)	{	nStart = i;	}	nNext = Route(nState, *(pszLine+i));	Accept(nState, nNext, pszLine+nStart, i-nStart);	if(!(nState!=0 && nNext==0))	i++;	nState = nNext;	}	Accept(nState, 0, pszLine+nStart, i-nStart);}
    Route()函数是一个很重要的函数。它负责查阅 DFA 规则表，检索当前状态为 nCurState，并且接受字符 c 的规则。如果检索到了，则返回下一个状态的编号。例子程序中的实现代码效率不高，因为它采用线性搜索。各位可以将其改为更快的搜索算法。 
int CAjaxParserDlg::Route(int nCurState, BYTE c){	int i, nSize;	nSize = m_ruleArr.GetSize();	CStateChangeRule rule;	for(i=0; i<nSize; i++)	{	rule = m_ruleArr[i];	if(rule.nCurState==nCurState	&& InRoute(c, rule.route))	{	return rule.nNextState;	}	}	if(nCurState==0)	{	Logln("start state, cannot recognize char");	}	// return to state 0 the start state	return 0;}
    Accept()函数比较简单，它负责接受分析得到的单词。如果当前状态是终止状态，并且下一个状态将要转向状态0，则说明现在已经是一个完整的单词了，并且下一个字符将不属于这个单词。这个时候 Accept() 函数调用 Log() 将这个单词输出。在实际应用中，往往需要把单词存放到一个单词数组。 
void CAjaxParserDlg::Accept(int nCurrent, int nNext, LPCTSTR pszLine, int nLen){	char psz[256];	if(nNext==0 && nCurrent!=0)	{	sprintf(psz, "Accept word(s:%d)[", nCurrent);	Log(psz);	strncpy(psz, pszLine, nLen);	psz[nLen] = 0;	Log(psz);	if(!(m_stateArr[nCurrent].nFlag&STATE_END))	{	Logln("]unrecogized char, can''t accept");	}	else	{	Logln("]");	}	}}
规则表
    分析内核赖以工作的“规则”采用 CStateChangeRule 来表示。例子程序中的规则表的初始化在 CAjaxParserDlg::OnInitDialog() 函数中。如下所示是一个规则的建立。 
 CStateChangeRule rule; rule.nCurState = 0; rule.nNextState = 1; rule.route[0].byStart = ''_''; rule.route[0].byEnd = ''_''; rule.route[1].byStart = ''A''; rule.route[1].byEnd = ''Z''; rule.route[2].byStart = ''a''; rule.route[2].byEnd = ''z''; m_ruleArr.Add(rule); rule.Clear();
例子程序中的DFA如图二所示。


图二