确定有穷自动机分析内核

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

时间: 2016-09-27