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

VC++
在类VC的界面实现中加入目录树
软件换肤技术在 BCB 中的实现
利用非模窗口生成MDI介面
报表输出轻松搞定
Windows 中不规则窗体的编程实现
解说Win32的窗口子类化
使用测试优先方法开发用户界面
一个简单的登录对话框的实现
一个简单的日记本程序
从资源中加载皮肤
一个在RichEdit中添加表情图象的类
ActiveSkin 4.3 软件换肤在VC中的实现
一种另类“关于(About)”对话框的动态显示方法
对话框打印预览及打印
关于如何换肤、子类化的解决方案
制作 MSN、QQ 的消息提示窗口
如何对 BCGControlBarPro 进行换肤
定制个性化的对话框窗口类
改变窗口中的光标形状
更新MFC中的视图，跟踪.NET Framework中的事件

No. « 20 21 22 23 »

技术文章搜索

关键字

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

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


图二