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

VC++
用VC++创建自定义向导程序
自定义 CRichEditCtrl 控件
Office 2000 风格的停泊、智能型菜单
黑客攻击手段之偷梁换柱
完善 CPopupText 类
让工具条显示256色图像
定制编辑框的上下文菜单
列表控件排序功能的实现
一个优秀的网格控件CGridCtrl
如何用代码动态添加控件
如何在编辑框中使用IAutoComplete接口
应用程序中添加“Coolbars”的简单方法
介绍一个有Toolbar功能的可重用类 CPopupText
在工具栏按钮上添加文本标签
类似Dreamweaver的颜色选择器
如何设置ListView控件的完全行(Full Row)选项
如何enable/disable菜单项
关于CEdit控件的透明 --作者：monsoon
动态菜单项、状态条提示、工具条提示问题
CAnimateCtrl::Open的使用问题

No. « 18 19 20 21 »

技术文章搜索

关键字

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

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


图二