parsing - 标记化然后构建 AST 有什么好处吗？

Question

首先对源文件进行标记，然后将每个标记单独推送到 AST 中，有什么好处吗？

我正在解析的语言不是上下文无关的；某些标记在不同的上下文中具有不同的含义。

因此，如果我进行上下文无关标记化，那么我的标记名称将没有多大意义 - 我将拥有像 COMMENT_START_OR_IDENTIFIER_START 这样的标记。

我还可以进行上下文感知标记化，然后将每个符号转换为正确的标记 - COMMENT_START 和 IDENTIFIER_START 作为单独的标记，尽管它们都是由组成的相同的字符串。

但那时我想知道，在一次传递中构建 AST 是否比先制作线性标记流，然后将该解析为 AST 更好？ p>

Answer 1

标记生成器不应该关心标记的语法目的是什么。它只需要识别标记(并可能将其与语义值相关联，尽管将其与源字符串相关联应该完全足够。)因此，只要清楚标记的边界是什么 - 就可以了是，哪些源字符构成了 token ——它不会使 token 的“名称”有丝毫不同。

相同的字符序列在两个不同的语法上下文中具有不同的语义这一事实不足以使语法上下文敏感。这是一个愚蠢的例子:语法描述了一个表达式列表，其中每个表达式都可以选择用数字来标识，如下所示:

27: a * b

并且可以使用数字表达式的值:

28: $27 + 4

这里的整数可能是表达式标识符或常量。但分词器不需要关心；它只返回一个 INTEGER。

program: %empty
       | program line
       ;

line   : INTEGER ':' expr
       | expr
       ;

expr   : term
       | expr '*' expr
       | expr '+' expr
         /* ... */
       ;

term   :  IDENTIFIER
       |  INTEGER      { /* a constant */ }
       |  '$' INTEGER  { /* an expression identifier */ }
       ;

即使标记化依赖于语法上下文，语法仍然可以是上下文无关的，但编写单独的词法分析器可能并不那么容易。例如，在许多语言中，正则表达式可以直接用作常量，并用 / 包围，尽管 / 也是算术运算符。 Javascript 和 Awk 只是两个例子。 [注1]

实际上，为此类语言编写 CFG 有点棘手，但这当然是可能的。无扫描器解析器正是因为这些问题而变得流行，无扫描器语法将证明该语言仍然是上下文无关的。 (不过，它可能不再是 LR(1) 了。)

也可以使用传统的 yacc/lex 解析器，但是由于分词器和解析器是由不同的工具独立生成的，因此在两者之间共享解析器/扫描器状态并不那么容易。在典型的实现中，这种语言的扫描器将维持足够的状态来决定 / 的含义，不是为了让解析器知道，而是为了让解析器知道。为了能够在正则表达式的持续时间内切换标记化规则。生成的解析器可能看起来不是上下文无关的，但解析的语言仍然是上下文无关的。

C++ 是上下文相关语言的真实示例，因为在 C++ 中，在不知道标识符是否为模板括号或小于号的情况下，不可能确定标识符后面的 < 是模板括号还是小于号。前面的标识符是否是模板标识符，这只能通过在符号表中查找标识符来实现。 (或者更糟。有可能安排决策需要任意复杂的计算。)

---

注释

1. Perl 是另一个例子，但 Perl 并不假装是上下文无关的。