词法分析的数据结构看起来如何？

Question

我知道词法分析器将输入标记化并将其存储在流中，或者至少我是这么理解的。不幸的是，我读过的几乎所有文章都只讨论对简单表达式进行词法分析。我感兴趣的是如何标记像这样的东西：

if (fooBar > 5) {
  for (var i = 0; i < alot.length; i++) {
    fooBar += 2 + i;
  }
}

请注意这是伪代码

问题：我想知道词法分析器创建的标记的数据结构是什么样的？我真的不知道我上面给出的代码嵌套的例子。举个例子就好了。

Answer 1

首先，令牌不一定是存储的。一些编译器确实将标记存储在 table 或其他数据结构中，但对于一个简单的编译器（如果有这样的东西）在大多数情况下，词法分析器可以 return 下一个的类型就足够了要解析的令牌，然后在某些情况下，解析器可能会向词法分析器询问组成令牌的实际文本。

如果我们使用您的示例代码，

if (fooBar > 5) {
  for (var i = 0; i < alot.length; i++) {
    fooBar += 2 + i;
  }
}

此示例中第一个标记的类型可能定义为 TOK_IF 对应于 "if" 关键字。下一个标记可能是 TOK_LPAREN，然后是 TOK_IDENT，然后是 TOK_GREATER，然后是 TOK_INT_LITERAL，依此类推。作为词法分析器（或分词器）代码的作者，您定义的类型究竟应该是什么。（请注意，有大约一百万种不同的工具可以帮助您避免手工处理这些细节的繁琐任务。）

除了 TOK_IDENT 和 TOK_INT_LITERAL 到目前为止，我们看到的标记完全由它们的类型定义。对于这两个，我们需要能够向词法分析器询问基础文本，以便我们可以评估令牌的值。

因此，在伪代码中处理 IF 语句的解析器的一小部分可能类似于：

...
  switch(lexer.GetNextTokenType())
  case TOK_IF:
    {
      // "if" statement  
      if (lexer.GetNextTokenType() != TOK_LPAREN)
        throw SyntaxError('( expected');
      ParseRelationalExpression(lexer);
      if (lexer.GetNextTokenType() != TOK_RPAREN)
        throw SyntaxError(') expected');
      ...

等等。

如果编译器确实选择实际存储标记以供以后参考，并且某些编译器会这样做，例如为了允许更有效的回溯，一种方法是使用类似于以下的结构

struct {
  int TokenType;
  char* TokenStart;
  int TokenLength;
}

这些容器可能是链表或std::vector（假设是 C++）。

词法分析的数据结构看起来如何？

How does the data structure for a lexical analysis look?

compiler-construction

parsing

lexical-analysis

tokenize