模式与匹配

我们在前边已经定义了我们的词法分析器适配的不同词法单元的构成，那么我们该如何判断输入的一个字符串属于哪一种词法单元呢？

按照我们的惯例，要想解决一个问题，首先要以工程师的方式准确描述这个问题。比如词法单元id，我们之前的描述是”一个及以上字符连接成的串，且首个字符不能是数字”，这种描述很通俗，但也很不准确、不简洁。因此我们需要一种描述一种模式的简洁的准确的通用的表达，并且尽量易于转化为程序：

正则表达式

我们通常使用”正则表达式”来描述一个串应有的格式。正则表达式由代表字符元素或字符元素类的标识符、和代表操作的运算符组成。
规范的正则运算符有如下几种：

• |或运算，表示在其左右两个表达式中取其一
• *闭包运算，表示重复此表达式0次及以上
• +正闭包运算，表示重复此表达式1次及以上
• ?0-1运算，表示此表达式可以存在，也可以不存在
• ()结合运算

比如：如下的表达式
\(\bold{idChar}(\bold{idChar} | \bold{digit10})^*\)
就表示“1个idChar字符类和0-无限个idChar或digit10字符类组成的串”
我们可以为一个词法单元规定一个或者多个正则表达式，但一个正则表达式能且只能对应一个词法单元

拥有正则表达式，我们就可以通用地描述一个字符串的格式了。但，我们在工程上如何使用正则表达式的信息呢？

自动机

很直观地，以简单的正则abcdef为例，我们要想知道一个串是否匹配它，我们需要维护两个信息：

1. 对于输入的字符串，我们目前访问到的位置
2. 对于正则表达式，我们目前匹配到的位置

也就是说，我们需要某种方式来记录我们正则匹配的进度。直观地，对于正则的每一项来讲，我们都可以为其划分一个”进度状态”。比如对于abcdef，我们可以划分这么几项:

1. 已匹配(null)，未匹配abcdef
2. 已匹配a，未匹配bcdef
3. 已匹配ab，未匹配cdef
4. ….

然后，每一个状态对于输入字符串中的下一个字符都存在一个动作（我们称其为状态转移）：如

1. 等待输入a，如输入a转入状态2，输入其他返回错误
2. 等待输入b，如输入b转入状态3，输入其他返回错误
3. 等待输入c，如输入a转入状态4，输入其他返回错误

基于上述的原理，我们可以实现一种叫做“自动机”的技术。每一个正则均可以表达成一个自动机。
如果自动机是无二义的，即每一个状态对于一个输入仅存在唯一的动作选择，且不存在通过空输入转换的边，那么这种自动机称为“确定有限状态自动机”，而如果自动机是二义的，那么这种自动机称为“不确定有限状态自动机”。自动机的属性与正则表达式的形式密切相关：
如：下述两个正则:

1. $(a)^+aab$
2. $(a)^+b$

其中，1产生一个不确定自动机：由于在输入1个a之后，自动机不知道是否该跳出$(a)^+$的循环。而2产生确定的自动机。
不确定自动机可以通过一种算法转化为确定自动机，但是我们这里没有必要说明：程序设计语言的词法正则一般不会。也一般不建议出现二义性。

知道自动机的原理，我们就可以试着实现一个自动机：通过switch-case语句块或者funcmap就可以实现一个简单的自动机。如对于正则$(a)^+b$:

switch state:
    case START:
        if input == 'a': state = 1
        else error
    case 1:
        if input == 'a': state = 1
        else if input == 'b': state = 2
    case 2:
        if input == 'b': state = FINISH
        else error

实际上真正的编译器工程所用的词法分析所用的自动机实现起来要啰嗦得多：

//satoru 0.11 LexAnaDFA
bool DFA::trans(char _iptc) {
    using namespace DFAstate;
    switch (this->state) {
    case START: // 0
        if (isDigit(_iptc) && _iptc != '0') {
            stateTo(NUM10_MAIN_INPUTING_DIGIT);
            return true;
        } 
        else if (isEmptyChar(_iptc)) {
            stateTo(START);
            return true;
        }
        else if (_iptc == '0') {
            stateTo(NUM_MAIN_FIRST_ZERO_IN);
            return true;
        } 
        else if (_iptc == 0) {
            stateTo(END);
            return true;
        }
        else if (isIdChar(_iptc)) {
            stateTo(ID_FIRST_CHAR_IN);
            return true;
        }
        else if (isReptbOperatorChar(_iptc)) {
            stateTo(OP_RPTB_FIRST_IN);
            return true;
        }
        else if (isSingleOperatorChar(_iptc)) {
            stateTo(OP_SINGLE_CHAR_IN);
            return true;
        }
        else if (isOpreatorCharOnlyDblWEqual(_iptc)) {
            stateTo(OP_NOMDBL_FIRST_IN);
            return true;
        }
        else if (_iptc == '"') {
            stateTo(STR_QUO_IN);
            return true;
        }
        else if (_iptc == '\'') {
            stateTo(CHAR_SQUO_IN);
            return true;
        }
        break;

    case OP_NUM_MAIN_PONE_IN: // 此状态未启用
        if (isDigit(_iptc)) {
            stateTo(NUM10_MAIN_INPUTING_DIGIT);
            return true;
        } 
        if (_iptc == '=' || _iptc == host->getLastChar()) {
            stateTo(OP_DBL_ACC);
            return true;
        }
        break;

    case NUM10_MAIN_INPUTING_DIGIT: // 2
        if (isDigit(_iptc)) {
            stateTo(NUM10_MAIN_INPUTING_DIGIT);
            return true;
        } 
        else if (_iptc == 'U' || _iptc == 'u') {
            stateTo(NUM10_ACCEPT_UNSIGNED_INT);
            return true;
        }
        else if (_iptc == '.') {
            stateTo(NUM10_FLT_DOT_IN);
            return true;
        }

    case NUM10_ACCEPT_UNSIGNED_INT: // 3
        //错误情况：对于终点的状态进行了转换，应初始化。
        break;
    
    case NUM_MAIN_FIRST_ZERO_IN: // 4
        if (isDigit(_iptc)) {
            stateTo(NUM10_MAIN_INPUTING_DIGIT);
            return true;
        }
        else if (_iptc == '.') {
            stateTo(NUM10_FLT_DOT_IN);
            return true;
        }
        else if (_iptc == 'u' || _iptc == 'U') {
            stateTo(NUM10_ACCEPT_UNSIGNED_INT);
            return true;
        }
        else if (_iptc == 'x') { //接16进制整数图
            stateTo(NUM16_X_IN);
            return true;
        }
        else if (_iptc == 'X') { //接2进制整数图
            stateTo(NUM2_X_IN);
            return true;
        }
        break;

    case NUM10_FLT_DOT_IN: // 5
        if (isDigit(_iptc)) {
            stateTo(NUM10_FLT_INPUTING_DIGIT);
            return true;
        }
        break;
    
    case NUM10_FLT_INPUTING_DIGIT: //6
        if (isDigit(_iptc)) {
            stateTo(NUM10_FLT_INPUTING_DIGIT);
            return true;
        } 
        else if (_iptc == 'e' || _iptc == 'E') {
            stateTo(NUM10_FLT_INDEX_E_IN);
            return true;
        } 
        break;

    case NUM10_FLT_INDEX_E_IN: // 7
        if (isDigit(_iptc)) {
            stateTo(NUM10_FLT_INDEX_INPUT_DIGIT);
            return true;
        }
        else if (_iptc == '+' || _iptc == '-') {
            stateTo(NUM10_FLT_INDEX_PONE_IN);
            return true;
        }
        break;
    
    case NUM10_FLT_INDEX_INPUT_DIGIT: // 8
        if (isDigit(_iptc)) {
            stateTo(NUM10_FLT_INDEX_INPUT_DIGIT);
            return true;
        }
        break;

    case NUM10_FLT_INDEX_PONE_IN: // 9
        if (isDigit(_iptc)) {
            stateTo(NUM10_FLT_INDEX_INPUT_DIGIT);
            return true;
        }
        break;
    
    case ID_FIRST_CHAR_IN: //10
        if (isIdChar(_iptc) || isDigit(_iptc)) {
            stateTo(ID_CHAR_INPUT);
            return true;
        }
        break;

    case ID_CHAR_INPUT: // 11
        if (isIdChar(_iptc) || isDigit(_iptc)) {
            stateTo(ID_CHAR_INPUT);
            return true;
        }
        break;

    case OP_NOMDBL_FIRST_IN: // 14
        if (_iptc == '=') {
            stateTo(OP_DBL_ACC);
            return true;
        }
        break;

    case OP_RPTB_FIRST_IN: // 16
        if (_iptc == '=' || _iptc == host->getLastChar()) {
            stateTo(OP_DBL_ACC);
            return true;
        }
        break;
    
    case STR_QUO_IN: // 17
        if (_iptc == '"') {
            stateTo(STR_END_QUO_IN);
        }
        else if (_iptc > 0) {
            stateTo(STR_CHAR_INPUT);
            return true;
        }
        break;
    
    case STR_CHAR_INPUT: //18
        if (_iptc == '"' && host->getLastChar() != '\\') {
            stateTo(STR_END_QUO_IN);
            return true;
        }
        else if (_iptc > 0) {
            stateTo(STR_CHAR_INPUT);
            return true;
        }
        break;

    case CHAR_SQUO_IN: // 20
        if (_iptc == '\'') {
            stateTo(CHAR_ACC);
            return true;
        }
        else if (_iptc == '\\') {
            stateTo(CHAR_WAIT_CTRL_CHAR);
            return true;
        }
        else if (_iptc > 0) {
            stateTo(CHAR_WAIT_SQUO);
            return true;
        }
        break;
    
    case CHAR_WAIT_SQUO: // 21
        if (_iptc == '\'') {
            stateTo(CHAR_ACC);
            return true;
        }
        break;
    
    case CHAR_WAIT_CTRL_CHAR: // 23
        if (_iptc > 0) {
            stateTo(CHAR_WAIT_SQUO);
            return true;
        }
        break;

    case NUM2_X_IN: // 24
        if (isNum2Digit(_iptc)) {
            stateTo(NUM2_DIGIT_INPUT);
            return true;
        }
        break;
    
    case NUM2_DIGIT_INPUT: // 26
        if (isNum2Digit(_iptc)) {
            stateTo(NUM2_DIGIT_INPUT);
            return true;
        }
        else if (_iptc == 'u' || _iptc == 'U') {
            stateTo(NUM2_ACCEPT_UNSIGNED_INT);
            return true;
        } 
        break;
    
    case NUM16_X_IN : // 28
        if (isNum16Digit(_iptc)) {
            stateTo(NUM16_DIGIT_INPUT);
            return true;
        }
        break;
    
    case NUM16_DIGIT_INPUT: // 30 
        if (isNum16Digit(_iptc)) {
            stateTo(NUM16_DIGIT_INPUT);
            return true;
        }
        else if (_iptc == 'u' || _iptc == 'U') {
            stateTo(NUM16_ACCEPT_UNSIGNED_INT);
            return true;
        } 
        break;
    }
    return false;
}

自动机状态转移图

我们可以基于自动机的状态转移关系来绘制一个直观的状态转移图：

如上述代码对应一个这样的转移图：

加粗的环表示成功匹配出一个词法单元。接受状态中有星号者表示向前看1个符号，如还能转移则转移，如失配则接受并重启词法分析，无星号者表示立即接受。这反映了词法设计中的从左至右“最长匹配原则”。