确定有穷自动机分析内核

确定有穷自动机分析内核


作者/孙雪青

下载源代码

    前些时候学习编译原理，同时也为 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);}

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 statereturn 0;}    

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 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();