确定有穷自动机分析内核

前些时候学习编译原理，同时也为 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() 函数中。如下所示是一个规则的

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!