直接编码还是表驱动词法分析器？

Question

我是编译器构造领域的新手，我想知道直接编码与表驱动词法分析器之间的区别是什么？

如果可能，请使用简单的源代码示例。

谢谢。

编辑：

在Engineering a Compiler书中，作者将词法分析器分为三（3）种类型：表驱动、直接编码和手工编码。

Answer 1

~~我假设你所说的 "direct-coded" 是指 hand-written 词法分析器，而不是作为词法分析器生成器输出的词法分析器。在那种情况下...~~（见下文。）

... table-driven 词法分析器是一个（通常自动生成的）程序，它使用某种查找 table 来确定要采取的操作.考虑对应正则表达式 ab*a 的 finite automaton （有意不最小化）：

如果我们限制自己只考虑字符 'a' 和 'b'，我们可以在查找 table 中对其进行编码，如下所示：

#define REJECT -1

/* This table encodes the transitions for a given state and character. */
const int transitions[][] = {
    /* In state 0, if we see an a then go to state 1 (the 1).
     * Otherwise, reject input.
     */
    { /*a*/  1,  /*b*/  REJECT },
    { /*a*/  2,  /*b*/  3      },
    { /*a*/ -1,  /*b*/ -1      }, /* Could put anything here. */
    { /*a*/  2,  /*b*/  3      }
};

/* This table determines, for each state, whether it is an accepting state. */
const int accept[] = { 0, 0, 1, 0 };

现在我们只需要一个实际使用 table:

的驱动程序

int scan(void) {
    char ch;
    int state = 0;

    while (!accept[state]) {
        ch = getchar() - 'a'; /* Adjust so that a => 0, b => 1. */
        if (transitions[state][ch] == REJECT) {
            fprintf(stderr, "invalid token!\n");
            return 0; /* Fail. */
        } else {
            state = transitions[state][ch];
        }
    }
    return 1; /* Success! */
}

当然，在真正的词法分析器中，每个标记都有相应的接受状态，您将不得不以某种方式修改接受 table 以包含标记标识符。不过，我想强调两件事：

table-driven 词法分析器不一定在 DFA 状态级别上运行。
我不建议手动编写 table-driven 词法分析器，因为这是一个乏味且 error-prone 的过程。

A hand-written（因为缺少更好的名称）词法分析器通常不使用查找 table。假设我们想要一个用于具有括号、标识符和十进制整数的简单 Lisp-like 语言的词法分析器：

enum token {
    ERROR,
    LPAREN,
    RPAREN,
    IDENT,
    NUMBER
};

enum token scan(void) {
    /* Consume all leading whitespace. */
    char ch = first_nonblank();
    if (ch == '(') return LPAREN;
    else if (ch == ')') return RPAREN;
    else if (isalpha(ch)) return ident();
    else if (isdigit(ch)) return number();
    else {
        printf("invalid token!\n");
        return ERROR;
    }
}

char first_nonblank(void) {
    char ch;
    do {
        ch = getchar();
    } while (isspace(ch));
    return ch;
}

enum token ident(void) {
    char ch;
    do {
        ch = getchar();
    } while (isalpha(ch));
    ungetc(ch, stdin); /* Put back the first non-alphabetic character. */
    return IDENT;
}

enum token number(void) {
    char ch;
    do {
        ch = getchar();
    } while (isdigit(ch));
    ungetc(ch, stdin); /* Put back the first non-digit. */
    return NUMBER;
}

与 table-driven 词法分析器示例一样，这个示例并不完整。一方面，它需要某种缓冲来存储作为令牌一部分的字符，例如 IDENT 和 NUMBER。另一方面，它不能特别优雅地处理 EOF。但希望你能理解它的要点。

Edit：根据Engineering a Compiler中的定义，direct-coded词法分析器基本上是他们俩。我们没有使用 table，而是使用代码标签来表示状态。让我们看看使用与以前相同的 DFA 会是什么样子。

int scan(void) {
    char ch;

state0:
    ch = getchar();
    if (ch == 'a') goto state1;
    else { error(); return 0; }

state1:
    ch = getchar();
    if (ch == 'a') goto state2;
    else if (ch == 'b') goto state3;
    else { error(); return 0; }

state2:
    return 1; /* Accept! */

state3:
    ch = getchar();
    if (ch == 'a') goto state2;
    else if (ch == 'b') goto state3; /* Loop. */
    else { error(); return 0; }
}

根据我的个人经验，"best" 编写词法分析器的方法就是我上面概述的 hand-written 方法。它适用于每个平台，适用于每种语言，您无需学习像 lex 这样的古老工具，而且，也许最重要的是，您可以灵活地使用工具难以或不可能实现的功能来扩展词法分析器。例如，也许您希望词法分析器理解 Python-esque 块缩进，或者您可能需要动态扩展某些标记类.

Answer 2

看看我的词法分析器生成器，非常简单易懂，它生成 DFA 直接代码自动机，作为嵌套开关指令。我在我的项目中使用了这种方法，首先是手写，然后使用这个工具生成。该方法基于我通过阅读几本书和研究更高级解析器生成器的实现来研究该主题的经验。 github - rmjocz/langgen

上有一个项目

直接编码还是表驱动词法分析器？

direct-coded vs table-driven lexer?

compiler-construction

lexer

table-driven