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

Question

我是编译器构建世界的新手,我想知道直接编码与表驱动词法分析器有什么区别？

如果可能,请使用简单的源代码示例.

谢谢.

编辑:

在" 编译工程"一书中,作者将词法分为三(3)种类型:表驱动,直接编码和手动编码.

Answer 1

我将假设您通过"直接编码"表示手写的词法分析器而不是作为词法分析器生成器生成的词法分析器.那种情况......(见下文)

... 表驱动词法分析器是一种(通常是自动生成的)程序,它使用某种查找表来确定要采取的操作.考虑与正则表达式相对应的有限自动机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这样的古老工具,也许最重要的是,您可以灵活地使用工具实现难以或无法实现的功能来扩展词法分析器.例如,您可能希望lexer理解Python-esque块indentaiton,或者您可能需要动态扩展某些令牌类.