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

VC++
面试题目：猫吃老鼠问题的求解
一个最基本的有限元计算程序
简单的表达式求值
C程序移植到VC开发环境下
一个小语言的词法分析程序
A/B 向上取整的方法
马走日棋盘算法
一种随机抽题的简单算法
clone模式在平衡排序二叉树实现中的应用
递归的应用 -- 最简单分形图形实现
比较数据排序前后的查找次数
根据前序和中序序列生成二叉树
如何用CZip/CUnzip类压缩/解压缩文件
使用 random_shuffle() 算法随机化序列元素
Ceb解除打印屏蔽实战
基于SHA-256的HMAC文件校验器
模拟信息加密流程图简介
关于数据校验
浅谈利用RSA算法防止非法注册机的制作
加密它：用新的高级加密标准（AES）保持你的数据安全

No. « 10 11 12 13 »

技术文章搜索

关键字

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

出处:互联网   整理: 软晨网（RuanChen.com）   发布: 2009-10-30   浏览: 78 ::
收藏到网摘: 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如图二所示。


图二