在第一个C编译器中使用了哪种lexer / parser？

Question

1970年代初期，Dennis Ritchie编写了第一个C编译器。

在2017年，我想编写一个C编译器。诸如Deep C Secrets之类的书籍（Peter Van Der Linden）说，C首先是为了易于编译而设计的。但是我一直在遇到麻烦。

首先，要想出C语言的Lex / Yacc规范已经相对困难了，而当Ritchie制作他的编译器时，这些工具甚至还不存在！

另外，还有很多示例令人惊讶的小型C编译器，它们没有使用Lex＆Yacc的任何帮助。（看看这个从法布里斯·贝拉。注意微小混淆的C编译器，他的“生产” tinycc源实际上相当长的时间是，最有可能在能够容纳更多的架构的努力，并成为更具可读性）

那我在这里想念什么？Ritchie在其编译器中使用了哪种词法分析器/解析器？有没有更简单的编写编译器的方法？

Answer 1

Yacc 的名字是“yet another compiler compiler”的缩写，这强烈暗示它既不是第一个也不是第二个这样的工具。

事实上，维基百科关于编译器构建历史的文章指出

在 1960 年代初期，德州仪器 (TI) 的罗伯特·麦克卢尔 (Robert McClure) 发明了一种名为 TMG 的编译器-编译器，该名称取自“transmogrification”。在接下来的几年中，TMG 被移植到几台 UNIVAC 和 IBM 大型计算机上。

…

1969 年 Ken Thompson 为 PDP-7 编写了第一个 Unix 版本后不久，Doug McIlroy 创建了新系统的第一个高级语言：McClure 的 TMG 的实现。TMG 也是 Ken Thompson 在 1970 年在他的 PDP-7 上为 B 语言编写编译器时使用的编译器定义工具。 B 是 C 的直接祖先。

这不是您问题的完全答案，但它提供了一些可能性。

原答案：

如果 Ritchie 只是将一个手工构建的自顶向下或运算符优先级解析器组合在一起，我一点也不会感到惊讶。这些技术是众所周知的，原始的 C 语言几乎没有挑战。但是解析器生成工具肯定存在。

后记：

Alexey Frunze对 OP 的评论指出了 C 编译器的早期版本。它基本上是一个递归下降自顶向下的解析器，直到需要解析表达式的点为止，它使用类似分流码的运算符优先语法。（请参阅tree表达式解析器的第一个源文件中的函数。）这种从自顶向下算法开始并在需要时切换到自底向上算法（例如运算符优先级）的风格有时称为“左角”（ LC) 解析。

所以这基本上就是我所说的架构，不会让我感到惊讶，它也没有:)。

值得注意的是，Alexey 发掘的编译器（以及@Torek 在对这篇文章的评论中）并没有处理任何接近我们现在通常认为的 C 语言的东西。特别是，它只处理声明语法的一小部分（例如，没有结构或联合），这可能是 K&R C 语法中最复杂的部分。因此，它没有回答您关于如何为 C 生成“简单”解析器的问题。

C（大部分）可以使用 LALR(1) 语法进行解析，尽管您需要实现某些版本的“词法分析器黑客”才能正确解析转换表达式。解析器（翻译阶段 7）的输入将是由预处理代码（翻译阶段 4，可能包含阶段 5 和 6）生成的令牌流，它本身可能利用 (f) lex 标记器（阶段 3），其输入将根据阶段 1 和阶段 2 以某种方式进行消毒。（有关阶段的精确定义，请参见第 5.1.1.2 节）。

可悲的是，(f)lex 并非设计为管道的一部分；他们真的只想处理阅读源代码的任务。但是，通过重新定义YY_INPUT 宏，可以说服 flex 允许您提供输入块。可以使用简单的状态机处理三合字母（如果您选择这样做）和行延续；这些转换只缩小输入很方便，将最大输入长度参数的处理简化为YY_INPUT。（不要按照 flex 手册中的示例的建议一次输入一个字符。）

由于预处理器必须生成令牌流（此时，空格不再重要），因此使用 bison 的 push-parser 接口很方便。（确实，使用推送 API 通常更方便。）如果您采纳该建议，您将最终将阶段 4 作为解析的顶级驱动程序。

您可以手动构建一个预处理器指令解析器，但正确获取#if表达式和pragmas 建议使用单独的 Bison 解析器进行预处理。

如果您只想学习如何构建编译器，您可能想从更简单的语言开始，例如 Tiger，在 Andrew Appel 的关于编译器构建的优秀教科书中用作运行示例的语言。