直接编码的词法分析器 vs 表驱动的词法分析器？

Question

直接编码的词法分析器 vs 表驱动的词法分析器？

compiler-constructionlexertable-driven

12

我是一位有用的助手，可以翻译文本。

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

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

谢谢。

编辑：

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

- Ahmed T. Ali

2

表驱动是基于查找表的方法，如下面的答案所述。直接编码是一种简单地为DFA自动机编写代码的方法。这是常见的方法。手工编码是指具有固定转换并且适用于小语言的方法。 - Am_I_Helpful

幸运的是，我碰巧有Torczon的书。让我看一下。 - Martin Törnwall

好的，我已经编辑了我的帖子，并提供了一个直接编码（就像Torczon书中的那样）的词法分析器示例。 - Martin Törnwall

1

@shekharsuman 谢谢您。 - Ahmed T. Ali

2

@shekharsuman 我不知道，我只是在维基百科上读到了这个链接，它说：“..Lex/flex生成器家族使用表驱动方法，这种方法比直接编码方法效率低得多...” 无论如何，这并不重要，我不会使用它们 :-) - Ahmed T. Ali

显示剩余3条评论

2个回答

-1

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

- Radoslaw Jocz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martin Törnwall · Accepted Answer

我假设你所说的“direct-coded”是指手写词法分析器，而不是由词法分析器生成器产生的输出。在这种情况下...（见下文）

一个基于表的词法分析器是一个（通常是自动生成的）程序，它使用某种查找表来确定要采取的操作。考虑与正则表达式ab*a相对应的有限状态自动机（故意不最小化）：

DFA for ab*a

如果我们仅考虑字符 'a' 和 'b'，我们可以像这样在查找表中对其进行编码：

#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 };

现在我们只需要一个实际使用表格的驱动程序：

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! */
}

当然，在实际的词法分析器中，每个标记都必须有对应的接受状态，并且你需要以某种方式修改接受表以包含标记标识符。但我想强调两件事情：

1. 表驱动的词法分析器不一定在DFA状态的水平上操作。 2. 我不建议手写表驱动的词法分析器，因为这是一个繁琐且容易出错的过程。

一个手写的（因为没有更好的名字）词法分析器通常不使用查找表。假设我们需要一个简单的类Lisp语言的词法分析器，该语言具有括号、标识符和十进制整数：

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;
}

像表驱动词法分析器示例一样，这个示例也不完整。首先，它需要某种缓冲区来存储作为标记的字符，例如IDENT和NUMBER。其次，它不能很好地处理EOF。但希望您能理解其要点。

编辑：根据编译器工程中的定义，直接编码的词法分析器基本上是两者的混合体。不使用表格，而是使用代码标签来表示状态。让我们看看在使用与之前相同的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; }
}

在我个人的经验中，编写词法分析器的“最佳”方法是我上面概述的手写方法。它适用于每个平台、每种语言，您无需学习像lex这样的古老工具，也许最重要的是，您可以灵活地扩展词法分析器，使用一些难以或不可能通过工具实现的功能。例如，也许您希望您的词法分析器能够理解类似Python的块缩进，或者您需要动态扩展某些标记类别。