基于状态转换图的词法分析器

手动编写词法分析器要比使用自动生成工具要麻烦，因为大多数词法不复杂的语言的都可以通过正则表达式来表示词法单元。手动编写还需要模拟正则表达式，而自动生成工具就不需要。
手写可以基于状态转换图，或者直接扫描输入串来寻找模式匹配。

手动编写可以将正则表达式的模式转化为状态转换图，状态转换图有一组"状态"的节点。词法分析在扫描输入串的过程中寻找模式匹配的词素，而转换图中每个状态代表一个可能在这个过程中出现的情况。
状态图中的边从图的一个状态指向另一个状态，边上包含一个或多个符号，从一个节点经过一个边如果匹配则进入下一个节点，否则判断下一条边是否匹配。如果遇到一个终止状态则返回一个词法单元。

基于状态转换图的词法分析器的结构:
用一个变量state来表示当前状态节点的编号，然后用一个switch语句根据state的值来判断进入了哪个状态节点。
例如: 判断词法单元>, <, =, <=, >=

#define TOKEN int

TOKEN getrelop()
{
    while (1) {
        switch (state) {
        case 0:
            c = nextchar();
            if (c == '<') state = 1;
            else if (c == '=') state = 5;
            else if (c == '>') state = 6;
            else failed();
            break;
        case 1:
            c = nextchar();
            if (c == '=') state = 2;
            else if (c == '>') state = 3;
            else state = 4;
            break;
        case 2: return LE;
        case 3: return NE;
        case 4: retract(); return LT;    、/* retract将多读的字符退回输入流
                                            * 这里表示如果读到<和另一个非=号的字符
                                            * 就会判断是一个<符号的词法单元，所以
                                            * 要将下一个读到的退回输入流
                                            */
        case 5: return EQ;
        case 6:
            c = nextchar();
            if (c == '=') state = 7;
            else state = 8;
            break;
        case 7: return GE;
        case 8: retract(); return GT;
        }
    }
}

retract函数负责将读到的字符回退到输入流，例如: >=和>1，后者判断为>符号，并且将1使用ungetc等类似的动作将其退回到输入流，前者则判断为>=符号。

将这种转换图的代码集成到整个词法分析有几种方法:
1) 让程序顺序的执行所有的状态转换图，每次遇到一个failed函数就重置输入流并启动下一个转换图，而这种方法在识别标识符的时候就可能会与关键字冲突，例如: int应该识别为一个关键字，但标识符的转换图也会认为他可能是一个标识符。这种情况只需要将每个关键字的转换图放在标识符的转换图之前即可识别。这和lex程序的识别类似，在使用lex的时候要把关键字都放到识别id的正则表达式的前面，否则lex将不会匹配后面的关键字。这种方法也避免了诸如intnext会被识别为一个关键字的情况。

int keyword_graph();
int id_graph();

int lexer()
{
    int tok;
    tok = keyword_graph();
    if (tok != NONE)
        goto done;
    ...
    get_relop();
    ...
    tok = id_graph();
    if (tok != NONE)
        goto done;
    ...
done:
    return tok;
}

int keyword_graph()
{
    int tok;
    tok = int_graph();
    /*如果匹配了int，则返回int的词法单元, 否则继续处理下一个状态转换图*/
    if (tok != NONE)
        goto done;
    float_graph();
    if (tok != NONE)
        goto done;
    double_graph();
    ...
done:
    return tok;

}

2）并行的执行每个转换图，将下一个输入字符传递给所有的状态转换图，然后每个转换图执行转换。但这种方法的一个问题是，假如对于thenext而言，then的转换图完成了匹配，但id的转换图会继续处理输入。这个问题的通常处理策略是取最长，类似于正则表达式中的贪婪匹配。
3）更好的办法是将所有的状态转换图合并成一个图，这种方法在合并几个图的时候很简单，但合并很多图的时候会越来越复杂。(本文不叙述)


引用:

编译原理(第二版)            Alfred V.Aho, Monica S.Lam, Ravi Sethi, Jeffery D.Ullman