GCC/Clang 词法分析器和解析器
GCC/Clang lexer and parser
我很好奇 C/C++ 词法分析器和解析器是如何协同工作的。我知道解析器通常需要先行至少一个标记。不过，我的问题是，在生产编译器中（例如 gcc 或 clang）：
1) 词法分析器运行先对整个文件进行词法分析，然后让解析器生成AST。这意味着词法分析器会生成一个标记列表。
或
2) 词法分析器是否只生成一小组足以让解析器完成其工作的标记。这意味着词法分析器和解析器轮流 运行ning.
我绝对认为使用了选项 1，因为像 C++ 这样的语言有时需要任意先行，因为语法不是上下文无关的，但这会占用大量内存。
传统答案与您的情况 2 很接近，但不完全是这样。请注意，词法分析器和解析器通常都是作为相对简单的状态机实现的。
词法分析状态机可以由以下任一驱动：
- 给我一个新令牌
（这显然需要获取输入代码并将它们 assemble 转换为标记），或者：
- 这是一个新的输入字符
（最终导致词法分析器 "fall out" 的标记）。
解析器状态机可以从任一方向驱动：
- 给我一个解析
（然后必须获得令牌，直到找到一个完整的句子），或者：
- 这是一个新令牌
（然后必须 assemble 将标记变成一个句子）。
如果我们使用的解析器算法是以这种方式驱动的，我们将 "compile" 一个包含以下内容的文件：
for all input characters:
feed character to tokenizer
作为标记器的标记 "fall out"，它们将驱动解析器。整个事情将是自下而上驱动的协程。
传统上，在由 yacc、bison 等生成的解析器中，以及在为它们服务的词法分析器中，我们 运行 多 "top-down"，即有人调用 给我一个句子 函数（它可以构建一个 AST，或者直接发出代码，或者介于两者之间——例如，为一个函数或声明构建一个 AST，然后将其转换为中间代码，然后构建另一个函数或声明的另一个 AST，等等）。这推动一切朝着从词法分析器拉取标记的方向发展——但它仍然相当协程，因为解析器一次只请求一个标记。
这种方法也是手动编写递归下降解析器的明显方法：您的顶级函数是 "get me a sentence"（或 "get me all sentences" 或其他），最终导致调用 "get me a token"。因此，在这两种情况下，算法的实际表达式最终都会重复 "get me a token" 调用词法分析器。
GCC 有一个以这种方式工作的手工编码的解析器（和手工编码的词法分析器）。我没有看过 clang 的内部结构，但我怀疑它是一样的。
具体到 C++，嗯，它有一些非常 讨厌的解析案例；参见 https://en.wikipedia.org/wiki/Most_vexing_parse and Pavel Minaev's answer to Is there a good Python library that can parse C++?. Some compilers use ad-hoc methods to deal with this, e.g., provide an overly accepting grammar and try to back-patch the eventual AST, or "steer" the grammar via hacks. (I've seen C++ compilers crash here: feed them syntactically valid tokens that make semantic nonsense, and the hacks can misfire.) Another, arguably much better, method is to use a GLR parser; see Ira Baxter's answer here。
（我已经很久没有做过任何类似解析器理论的事情了，在写这个答案时遇到了 sjoerd's comment 关于 2011 年的 GLL 解析器，这很有趣。）
我很好奇 C/C++ 词法分析器和解析器是如何协同工作的。我知道解析器通常需要先行至少一个标记。不过，我的问题是，在生产编译器中（例如 gcc 或 clang）：
1) 词法分析器运行先对整个文件进行词法分析，然后让解析器生成AST。这意味着词法分析器会生成一个标记列表。
或
2) 词法分析器是否只生成一小组足以让解析器完成其工作的标记。这意味着词法分析器和解析器轮流 运行ning.
我绝对认为使用了选项 1，因为像 C++ 这样的语言有时需要任意先行，因为语法不是上下文无关的，但这会占用大量内存。
传统答案与您的情况 2 很接近，但不完全是这样。请注意，词法分析器和解析器通常都是作为相对简单的状态机实现的。
词法分析状态机可以由以下任一驱动：
- 给我一个新令牌
（这显然需要获取输入代码并将它们 assemble 转换为标记），或者：
- 这是一个新的输入字符
（最终导致词法分析器 "fall out" 的标记）。
解析器状态机可以从任一方向驱动：
- 给我一个解析
（然后必须获得令牌，直到找到一个完整的句子），或者：
- 这是一个新令牌
（然后必须 assemble 将标记变成一个句子）。
如果我们使用的解析器算法是以这种方式驱动的，我们将 "compile" 一个包含以下内容的文件：
for all input characters:
feed character to tokenizer
作为标记器的标记 "fall out"，它们将驱动解析器。整个事情将是自下而上驱动的协程。
传统上，在由 yacc、bison 等生成的解析器中，以及在为它们服务的词法分析器中，我们 运行 多 "top-down"，即有人调用 给我一个句子 函数（它可以构建一个 AST，或者直接发出代码，或者介于两者之间——例如，为一个函数或声明构建一个 AST，然后将其转换为中间代码，然后构建另一个函数或声明的另一个 AST，等等）。这推动一切朝着从词法分析器拉取标记的方向发展——但它仍然相当协程，因为解析器一次只请求一个标记。
这种方法也是手动编写递归下降解析器的明显方法：您的顶级函数是 "get me a sentence"（或 "get me all sentences" 或其他），最终导致调用 "get me a token"。因此，在这两种情况下，算法的实际表达式最终都会重复 "get me a token" 调用词法分析器。
GCC 有一个以这种方式工作的手工编码的解析器（和手工编码的词法分析器）。我没有看过 clang 的内部结构，但我怀疑它是一样的。
具体到 C++，嗯，它有一些非常 讨厌的解析案例；参见 https://en.wikipedia.org/wiki/Most_vexing_parse and Pavel Minaev's answer to Is there a good Python library that can parse C++?. Some compilers use ad-hoc methods to deal with this, e.g., provide an overly accepting grammar and try to back-patch the eventual AST, or "steer" the grammar via hacks. (I've seen C++ compilers crash here: feed them syntactically valid tokens that make semantic nonsense, and the hacks can misfire.) Another, arguably much better, method is to use a GLR parser; see Ira Baxter's answer here。
（我已经很久没有做过任何类似解析器理论的事情了，在写这个答案时遇到了 sjoerd's comment 关于 2011 年的 GLL 解析器，这很有趣。）