传统的答案接近于您的第二种情况,但并非完全如此。请注意,词法分析器和解析器通常都是相对简单的状态机实现。
词法分析状态机可以从以下任一方式驱动:
- 获取一个新标记
(显然需要获取输入代码并将其组装成标记),或者
- 这里有一个新的输入字符
(最终导致标记从词法分析器中“掉落”)。
解析器状态机可以从以下任一方向驱动:
- 给我一个解析
(然后必须获取标记,直到找到一个完整的句子),或者
- 这里有一个新的标记
(然后必须将标记组合成一个句子)。
如果我们使用的解析器算法是这样驱动的,我们将会用以下方法“编译”文件:
for all input characters:
feed character to tokenizer
当标记从分词器“掉落”时,它们会驱动解析器。整个过程都是从下向上驱动的协程。
传统上,在由yacc、bison等生成的解析器中,以及为它们服务的词法分析器中,我们更多地运行在“自上而下”的方式,即某人调用一个“给我一个句子”的函数(它可以构建AST,或直接发出代码,或介于两者之间——例如,为一个函数或声明构建一个AST,然后将其转换为中间代码,然后为另一个函数或声明构建另一个AST等)。这驱动着将标记从词法分析器中提取出来的方向,但它仍然相当像协程,因为解析器只询问一个标记。
这种方法也是手工编写递归下降解析器的显而易见的方法:你的顶层函数是“给我一个句子”(或“给我所有句子”或其他),最终导致某个函数调用“给我一个标记”。因此,在这两种情况下,算法的实际表达形式都会使得重复地向词法分析器进行“给我一个标记”的调用。
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。
我已经很久没有做与解析理论相关的事情了,在撰写这篇答案时,我发现2011年sjoerd的评论提到了GLL解析器,这非常有趣。