compiler-construction - GCC/Clang 词法分析器和解析器

Question

我很好奇 C/C++ 词法分析器和解析器如何协同工作。我知道解析器通常需要至少提前一个 token 。我的问题是，在生产编译器(比如 gcc 或 clang)中:

1)先运行词法分析器，对整个文件进行词法分析，然后让分析器生成AST。这意味着词法分析器生成一个标记列表。

或者

2) 词法分析器是否只生成一小组足以让解析器完成其工作的标记。这意味着词法分析器和解析器轮流运行。

我绝对认为使用了选项 1，因为像 C++ 这样的语言有时需要任意前瞻，因为语法不是上下文无关的，但这会占用大量内存。

Answer 1

传统答案与您的案例 2 接近，但不完全是这样。请注意，词法分析器和解析器通常都实现为相对简单的状态机。

词法状态机可以由以下任一驱动:

给我一个新的代币

(显然需要获取输入代码并将它们组合成 token )，或者:

这是一个新的输入字符

(这最终会导致标记从词法分析器中“脱落”)。

解析器状态机可以从任一方向驱动:

帮我解析

(然后必须获得标记，直到找到完整的句子)，或者:

这是一个新 token

(然后必须将标记组合成一个句子)。

如果我们使用的解析器算法以这种方式驱动，我们将“编译”一个文件:

for all input characters:
    feed character to tokenizer

当标记从标记器“脱落”时，它们会驱动解析器。整个事情将是自下而上驱动的协程。

传统上，在由 yacc、bison 等生成的解析器中，以及在为它们提供服务的词法分析器中，我们运行更多的是“自上而下”，即有人调用 get me a sentence 函数(这可能会构建一个 AST ，或直接发出代码，或介于两者之间——例如，为一个函数或声明构建一个 AST，然后将其转换为中间代码，然后为另一个函数或声明构建另一个 AST，等等)。这促使一切都朝着从词法分析器中提取 token 的方向发展——但它仍然是协程式的，因为解析器一次只要求一个 token 。

这种方法也是手动编码递归下降解析器的明显方法:您的顶级函数是“给我一个句子”(或“给我所有句子”或其他什么)，最终导致一些调用“给我一个句子”的函数 token ”。所以在这两种情况下，算法的实际表达最终都会对词法分析器重复“给我一个 token ”调用。

GCC 有一个以这种方式工作的手工编码的解析器(和手工编码的词法分析器)。我没有看过 clang 的内部结构，但我怀疑它是一样的。

具体到 C++，好吧，它有一些非常讨厌的解析案例；见 https://en.wikipedia.org/wiki/Most_vexing_parse和 Pavel Minaev's answer至 Is there a good Python library that can parse C++? .一些编译器使用临时方法来处理这个问题，例如，提供一个过度接受的语法并尝试对最终的 AST 进行回补，或通过黑客“引导”语法。 (我已经看到 C++ 编译器在这里崩溃:向它们提供语法上有效的标记，这些标记使语义无意义，并且黑客可能会失败。)另一种可以说更好的方法是使用 GLR 解析器；见 Ira Baxter's answer here .

(我已经很久没有做过任何解析器理论了，在写这个答案时遇到了 sjoerd's comment 关于 2011 年的 GLL 解析器，这很有趣。)