分隔符、比较、运算符令牌类型

Question

来自 "Compilers Principles, Techniques, & Tools, 2nd Ed." ("The Purple Book")，作者：Aho、Lam、Sethi 和 Ullman：

图 3.2：令牌示例 pg。 112

[Token]       [Informal Description]                  [Sample Lexemes]
if            characters i, f                         if
else          characters e, l, s, e                   else
comparison    < or > or <= or >= or == or !=          <=, !=
id            letter followed by letters and digits   pi, score, D2
number        any numeric constant                    3.14159, 0, 6.02e23
literal       anything but ", surrounded by "'s       "core dumped"

在上面，他们将 if 和 else 分成了自己的标记类型。在我见过的大多数示例中，这些将是单个 keyword 标记类型，标记的值将是 if 或 else。为每个关键字使用单独的标记类型而不是 keyword 标记类型有什么好处？

使用 comparison 这样的令牌类型有什么好处？为什么不像下面这样为每种比较设置一个标记类型？

[Token]       [Informal Description]                  [Sample Lexemes]
lt            <                                       <
gt            >                                       >
lte           <=                                      <=
gte           >=                                      >=
eq            ==                                      ==
neq           !=                                      !=

Answer 1

当运算符在句法上相同时，对于如何表示各个运算符的观点各不相同。许多人会为不同的运算符编写单独的产生式，即使没有真正的句法差异并且语义差异有限。

话虽如此，但有些语言的 ==、>= 和 <= 在句法上是不同的。在 C（及其系列）中，这些运算符的优先级不同，因此可以编写不带括号的 a <= b == b <= c，尽管包含该表达式的代码不太可能通过代码审查。（即使有括号，表达式也是有问题的。）在 Perl 中，a <= b <= c 是有效的级联比较，但 a <= b == c 不是。等等

一般规则是，如果令牌在语言语法中具有不同的作用，则解析器必须能够看到差异，并且解析器仅考虑令牌的类型，而不考虑其值。因此，if、then 和 else 在任何实际语法中必须是不同的标记类型。

Answer 2

为什么要对关键字使用不同的标记类型

在编写解析器时，您通常 switch 在标记类型上。如果令牌类型的信息不足以做出决定，这意味着您还必须检查 case 中令牌的值。如果令牌的值表示为字符串，则比较起来也会更昂贵（即使字符串是 intern 的，if-else-if 的序列仍然比 switch 效率低）。在许多解析器生成器中，根据标记的值做出决定要么是不可能的，要么比仅使用标记的类型更复杂。

为了说明这一点，这里是手写解析器的摘录，其中不同的关键字具有不同的标记类型：

parse_statement() {
  switch(current_token.type) {
    case IF:
      parse_if_statement(); break;
    case WHILE:
      parse_while_statement(); break;
    //...
    case ID: case NUMBER: case LITERAL:
      parse_expression_statement(); break;
    default:
      syntax_error(); break;
  }
}

相同的代码，但情况并非如此：

parse_statement() {
  switch(current_token.type) {
    case KEYWORD:
      if (current_token.value == "if") {
        parse_if_statement();
      } else if (current_token.value == "while") {
        parse_while_statement();
      // '}  else if(...) {'s for other valid keywords go here
      } else {
        syntax_error();
      }
    // Other statement types that don't start with a keyword go here
    case ID: case NUMBER: case LITERAL:
      parse_expression_statement(); break;
    default:
      syntax_error(); break;
  }
}

注意额外的嵌套，现在有两个地方调用了 syntax_error。

对于解析器生成器，不同的标记类型看起来像这样：

statement
  : IF condition body (ELSE body)?
  | WHILE condition body
  | ... | expression ';' ;

或者如果只有关键字令牌类型，则像这样：

statement
  : if condition body (else body)?
  | while condition body
  | ... | expression ';' ;

if: {current_token.value == "if"} KEYWORD ;
else: {current_token.value == "else"} KEYWORD ;
while: {current_token.value == "while"} KEYWORD ;

这仅适用于支持语义谓词的解析器生成器。在许多其他情况下，这根本不可能。

为什么要对比较运算符使用相同的标记类型

当不同的标记总是出现在语法中的相同位置时，即语法不区分它们时，将它们合并为单个标记类型是一种方便的快捷方式。再次让我们将语法与比较类型与单独类型进行比较：

comparison_exp: additive_exp COMPARISON additive_exp ;

以及个别类型：

comparison_exp: additive_exp comparison additive_exp ;
comparison: LT | GT | LTE | GTE | EQ | NEQ;

因此，如果您只有一种标记类型，则无需在语法中拼出所有选项。

与第一个问题相比，这是一个更次要和主观的事情。

分隔符、比较、运算符令牌类型

Separator, Comparison, Operator Token Types

parsing

compiler-construction

lexical-analysis

为什么要对关键字使用不同的标记类型

为什么要对比较运算符使用相同的标记类型