向后教授编制者

编译程序是一个引人入胜的复杂过程，高级程序通过该程序成为低级可执行代码。如何规划和实现这样的旅程？开发技术后，如何教给别人？

最近有很多关于编译器类的教学法的讨论。在此博客文章中，我们将重点介绍编译器构造类的一种设计：材料的表示顺序。通常，编译器类按执行顺序显示编译器的阶段。我们称此为“前进”方向。在特拉维夫大学，我们尝试了“向后”教学编译器。这篇文章介绍了这种方法，并描述了我们认为其主要优点。

首先，以“转发”方式简要介绍编译器的工作方式。首先，通过词法和句法分析，将输入程序的文本转换为抽象的语法树（AST），这是一种易于操作的表示形式。其次，编译器执行一系列语义检查，以确保程序“有意义” –变量在使用前定义，类型加总等。在此过程中，编译器构造符号表，并将类型归因于每个表达式，也将在以后的阶段中使用的成分。然后，编译器使用符号表并键入之前的信息，进入以低级中间表示（IR）生成代码的第三阶段。最后，将IR代码转换为目标语言（例如x86汇编）。

反向顺序以相反的顺序教授这些阶段：首先是代码生成；然后是代码生成。然后进行语义分析；然后进行句法分析。 （我们不是第一个尝试倒序的类–请参阅致谢以进行详细说明。）

编译器类中的首要概念挑战是了解如何将高级代码映射到低级代码。反向顺序首先阐明了编译器的目标，即在各个编译阶段的“方式”之前，已编译程序的“内容”。并且知道您将要去哪里知道如何到达那里很有用。

设定目标后，后序将从这个不太熟悉的一端返回到更加熟悉的方式。这是一种常见的解决问题的策略。一些研究表明，当新手解决专家们向前解决的问题时，他们倾向于使用向后启发式方法（Larkin等，1980； Simon＆amp; Simon，1978）。至关重要的是，我们认为研究编译器的后退阶段可以更好地激励他们。 （这类似于著名的Nand到Tetris类的方法。）

落后订单如何运作？在我们的课程中，学生将根据Jens Palsberg，Hal Perkins和Yannis Smaragdakis提供的资料，开发一种编译器，该编译器将从MiniJava（Java的子集）转换为LLVM低级中间表示（LLVM-IR）。

变量和方法重命名：输入是程序的AST，任务是重命名变量或方法;也就是说，在声明和用途中以新名称生成新的AST。重命名必须考虑到范围，可变隐藏，类层次结构和继承。本练习不是编译器本身的一部分，但是开发了下一个练习所必需的基本技能（而不是用后来的练习捆绑它们）：使用访问者实现通过AST的传递，并构建符号表。分析假定输入AST表示语义有效的程序，包括键入有效继承的规则和规则。

LLVM-IR代码生成：输入是程序的AST，任务是在LLVM-IR中生成等效代码。学生在采用他们在上一个练习中实现的符号表产生高级构造的低级翻译。所有这些都在假设下 - 在下一个练习中强制执行 - 输入AST表示一个语义有效的程序，包括输入规则;翻译依赖于声明的静态类型（无需额外检查）以选择存储类型和低级指令。因此，如果输入程序不符合语义规则，则转换可能无法生成代码，或者生成错误的代码。这种观察结果导致下一个练习。

语义分析：输入是程序的AST，任务是决定它是否符合语义规则列表。我们从我们在代码生成期间所做的假设（包括我们第一次忘记的假设中获取了列表，我们假设......）。

句法分析：最后，输入是文本中的程序代码，任务是生成捕获它的AST，或者如果程序与语言的语法不匹配，则报告错误。使用Lexer和Parser生成器来解析此帐户。

AST输入：除了最后一项练习中，输入不是常规的文本表示程序，但ASTS。我们使用了我们选择的特定AST结构的XML编码，并提供了将XML文件解码为学生代码操纵的Java类层次的代码。这样我们就可以推迟解析直到最后一次练习，但这意味着学生必须直接编码他们的测试程序的AST。学生对手工编写ASTS的前景并不完全令人惊讶，但它主要效果正常。

简化打字：在我们讨论的类型分析之前分配了前两个练习，这是第三次练习的一部分。但是类型信息对于这两项任务至关重要（如上所述）。我们发现依赖静态类型定义 - 如果我们采用另一个限制我们包括在语义检查中的这种限制学生必须验证。 （在原则上可以自动转换为通过变量提取遵守此规则。）总体而言，通过这种方式，可以在验证之前使用类型。

程序比其语法更多，这是一个克服的精神障碍。直到非常迟到的节目的AST代表性的帮助。

在落后方法中降低了聚光灯，高级代码学生写作的对应关系和低级代码实现已经是第二次练习的主题，这是第一练习是编译器本身的一部分。我们认为这是一个很好的焦点。

“良好类型的程序不能出错”我们之前在语义检查上投球的方式，语义检查的作用是确保输入程序满足代码生成阶段中所采用的所有假设。由于学生已经实现了代码生成并使用了假设，因此这归因于长期且看似无意义的语义检查列表。这是因为我们期望编译器为传递语义检查阶段的每个程序生成正确的代码 - 良好类型的程序类型的安全原理的一个非常有形的表现出来不会出错。

解析是激烈的解析构建AST。 ASTS如何促进编译器的分析，并且在在各种练习中实施多次分析之后，在这一点上，应当很好地理解，它们是如何操纵程序文本的。

从这种经历中，我们的外卖之一再次回来的是，编辑最好是全面了解;编译阶段和它们的相互依赖之间的接口只有在作为整体上时才真实地理解。这是一个有趣的思想实验，然后，在两个方向上考虑这些依赖性，而不是仅在通常的前进的方式。

我们享受落后的课堂，但也发现某些方面在这个工作流程中难以解释。

装配一代在哪里适合？我们不确定何时教导IR到集会的翻译，具有激活记录的特殊挑战。要求学生首先解决这些，作为“纯粹”的落后方法任务，是从可能被认为是较少的中央主题的。 （我们教会组装生成，但由于时间限制，没有要求学生实施它。）另一种方法是将集合生成作为另一个完整编译器的结论项目构成，这次IR对装配的这一时期。何时教授编译器优化时出现类似的问题。

什么是静态类型？面向对象语言的代码生成构建了静态和动态类型之间的差异。我们熟悉这些概念将来自上课，以对面向对象的编程，但对于在讨论类型检查之前，我们发现难以解释的学生。

语义检查的其他作用？语义检查不仅对于编译器很重要，还可以确保代码生成的有效性；它们还有另一个作用：警告程序员注意不合理的代码（即使编译器可以某种方式“克服”错误并生成代码！）。向后教学时，该其他角色似乎是次要的。

为什么要运行时检查？在实现代码生成时，学生必须生成代码以执行运行时检查，但是其他检查将“推迟”到语义检查的早期阶段。在讨论语义检查和静态分析之前，不清楚执行每个检查的阶段的原因。

为什么使用这种特定的AST结构？在我们目前的结构中，在分析过程中，直到很晚，“程序”还是“ AST”的同义词。这可能会给人一种幻想，即我们对AST的选择是该语言固有的。我们认为，在设计AST之前，不希望学生在看到完整的编译器之前就做出明智的选择，无论使用哪种方向，但是提到固定的AST结构有时都太容易了（当我们解释了语义和句法之间的区别时，我们非常感兴趣。错误）。另外，由于不经常提及该语言的语法，这使得学生更难于习惯他们所编译语言的语法子集。

完全不同的课程结构是编译器以增量方式构建以支持越来越多的语言功能时的情况。在适用的情况下，它通过共同努力解决所有阶段的秩序问题。在更传统的结构中，向编译器教学的“向后方法”只是对以下几个问题的一种可能的答案，其中最突出的是如何使编译器的最终目标切实可行，以及如何尽可能有效地激发解析和语义检查。在变量重命名的练习中，在传统的编译器设置之外执行代码分析的经验是很不错的选择。向后方法也提出了自己的问题，特别是沿着编译器如何过滤无效程序的轴，这可能会受益于向前的操作方向。我们希望看到关于实现这些方法综合的更多想法。

简介：Yotam Feldman是特拉维夫大学的一名博士生，致力于形式方法的研究，因此大多数时候都在谈论前进和后退（可达性）。 Mooly Sagiv是特拉维夫大学计算机科学教授，也是Certora的首席执行官。 Mooly的爱好包括程序分析，程序验证和运行。

致谢：我们的课堂受到UPenn的Steve Zdancewic的课堂的启发（哈佛的Greg Morrisett的课堂和Cornell的Andrew Myers的课堂的启发），并借鉴了Jens Palsberg，Hal Perkins和Yannis Smaragdakis提供的MiniJava编译材料。其他类也采用了从后到前的编译器方法，Lindsey Kuper在先前的PL Perspective中也进行了讨论。

我们感谢Oren Ish-Shalom，Jens Palsberg，Hila Peleg，Hal Perkins和Steve Zdancewic慷慨地向我们提供了他们的材料，Oren Ish-Shalom和Hila Peleg为项目设计提供了咨询，以及Oren Ish-Shalom，Jens Palsberg，James R Wilcox和Steve Zdancewic对这篇文章的草稿提出了意见和建议。

免责声明：这些职位是由个别贡献者撰写的，以分享他们关于社区利益的履行委员会的思想。 本博客中代表的任何观点或意见都是个人的，属于博客作者，并且不代表ACM Sigplan或其父组织，ACM。