确定有穷自念头阐明内核

副标题#e#

前些时候进修编译道理，同时也为 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);
}

#p#副标题#e#

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("]");
　　　　}
　　}
}

#p#副标题#e#

法则表

阐明内核赖以事情的“法则”回收 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如图二所示。

图二

状态属性

虽然除了法则以外，另一个重要的数据就是状态的属性，阐明内核需要知道一个状态是不是终止态。m_stateArr 记录了所有的状态的属性。这个数组的下标代表状态编号，数组元素的值是状态属性。

竣事语

#p#分页标题#e#

大概列位都知道，其实作词法阐明挺简朴的，可是语法阐明十分的坚苦。据我所知，语法阐明尚且不十分的形式化，也就是说理论并非十分完善。这将对结构语法阐明器带来坚苦。我做 DocWizard 的时候并没有回收教科书上的语法阐明要领，做的很贫苦，并且也不能担保正确。说实在的做得挺滥的。呵呵～～ 但愿今后能做得好一些。

下一步我得好好的进修 lex 和 yacc 了。究竟用它们来结构阐明器照旧挺轻松的。