在这里，我试图展示实践中来自编译器创建领域的一些重要概念。 这样完成15分钟的故事可能是深入探讨复杂主题的好方法。 最好不要被动阅读下面的内容，还要检查工作中的代码。
如果最初的经验是成功的，那么将来您可以期望在编译器主题上还有15分钟的“草图”。
将讨论什么
让我们做一个算术表达式编译器。 一种将反向波兰语符号 （也称为RPN或POLIZ）的源文本转换为与堆栈兼容的中间代码的代码。 但是我们可以不用翻译。 接下来，我们立即将结果转换为C表示形式。 也就是说，我们得到了从RPN到C的编译器。
顺便说一下，我们将用Python编写编译器。 但是，不要阻止那些喜欢其他编程语言的人。 这是一个有用的练习：将下面的代码翻译成您喜欢的语言。 或使用已经完成的翻译：
F＃实现（通过gsomix ）：
第一版
SSA版本
让我们从解析开始
def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens]
我们在这里做了什么？ 扫描功能从用户那里收到一个用反向波兰语表示的字符串（“ 2 2 +”）。
在输出处，我们得到其中间表示。 这是一个例子：
[ ('Push', 2), ('Push', 2), ('Op', '+') ]
因此，我们已经有了编译器。 但是他很轻浮。 回想起初它是关于C代码的。
让我们用C广播
def trans(ir): code = [] for tag, val in ir: if tag == "Push": code.append("st[sp] = %d;" % val) code.append("sp += 1;") elif tag == "Op": code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val) code.append("sp -= 1;") return "\n".join(code)
这是怎么回事 让我们看一下该函数的输出（使用带有“ 2 2 +”的相同示例）。
st[sp] = 2; sp += 1; st[sp] = 2; sp += 1; st[sp - 2] = st[sp - 2] + st[sp - 1]; sp -= 1;
是的，它已经看起来像C代码了。 数组st充当堆栈的角色，而sp是其指针。 通常，虚拟堆栈机可以处理这些事情。
那只是机器本身-解释器，我们没有。 有一个编译器。 我们还剩下什么？ 必须为C程序添加必要的帧。
我们的第一个完成的编译器
ST_SIZE = 100 C_CODE = r"""#include <stdio.h> int main(int argc, char** argv) { int st[%d], sp = 0; %s printf("%%d\n", st[sp - 1]); return 0; }""" def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens] def trans(ir): code = [] for tag, val in ir: if tag == "Push": code.append("st[sp] = %d;" % val) code.append("sp += 1;") elif tag == "Op": code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val) code.append("sp -= 1;") return "\n".join(code) def rpn_to_c(source): return C_CODE % (ST_SIZE, trans(scan(source))) print(rpn_to_c("2 2 +"))
仍然需要使用C编译器来编译该程序的输出。
您还准备继续吗？ 然后，让我们讨论一下我们做了什么。 有一个值得怀疑的时刻-我们的编译器会转换常量表达式，您可以在编译阶段简单地计算它们。 将它们转换为代码没有任何意义。 但是现在让我们来看一下，一些参数可以从外部进入堆栈。 让我们谈谈我们发展的实际意义可以在以后给出的事实。 现在，掌握构建最简单的编译器的总体思路很重要，对吧？
你喜欢标题吗？ SSA-对于任何编译器来说，这听起来都很可靠。 现在，我们将使用相同的SSA。 这是什么 让我们按顺序移动。
我们目前正在生成C代码，没有任何虚拟机。 但是，为什么我们需要堆栈操作形式的基础知识呢？ 让我们用C中的普通变量替换这些操作。 此外，我们将不保存变量-我们将为每个表达式使用一个新名称。 让C编译器处理所有这一切。 事实证明，对于我们来说，每个变量仅分配一次值。 顺便说一下，这就是SSA的形式。
这是我们的新编译器。
C_CODE = r"""#include <stdio.h> int main(int argc, char** argv) { %s printf("%%d\n", %s); return 0; }""" def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens] def trans(ir): stack, code = [], [] name_cnt = 0 for tag, val in ir: if tag == "Push": code.append("int t%d = %d;" % (name_cnt, val)) stack.append("t%d" % name_cnt) name_cnt += 1 elif tag == "Op": a, b = stack.pop(), stack.pop() code.append("int t%d = %s %s %s;" % (name_cnt, b, val, a)) stack.append("t%d" % name_cnt) name_cnt += 1 return "\n".join(code), stack.pop() def rpn_to_c(source): return C_CODE % trans(scan(source)) print(rpn_to_c("2 2 +"))
请注意，C代码中不再有堆栈，并且在翻译过程中会模拟使用该堆栈。 编译过程中使用的堆栈不包含值，但包含变量名。
这是最终结果：
#include <stdio.h> int main(int argc, char** argv) { int t0 = 2; int t1 = 2; int t2 = t0 + t1; printf("%d\n", t2); return 0; }
总结
我们的联合课程时间似乎已经到期。 我们致力于将程序从一种语言翻译成另一种语言。 这称为源到源翻译。 或者-只是翻译，可以将其视为编译的同义词，但通常编译器会将程序从高级表示转换为低级表示。 源到源翻译器还有一个流行词“翻译器”。 但是，对于编译器专家而言，提及“编译器”可能会很烦人，请注意！
试用代码。 等待反馈！