在编译器中键入检查

Question

我目前正在尝试创建一个TypeChecker,它将成功检查MiniJava程序.在过去的10个小时里,我一直在努力,盯着它,但我甚至不知道从哪里开始.我已经放弃了及时完成项目,但我还是想知道它是如何完成的.我们给出了MiniJava的完整解析器和一组用于遍历抽象语法树的类,以及两个不同的默认访问者,DepthFirstVisitor和GJDepthFirst.我们应该扩展这些访问者以完成项目.

我理解需要完成的非常基本的概念:我们需要捕获解析器无法捕获的代码中的错误.我们需要在2遍中运行代码.第一遍是构建符号表(？)和第二遍,使用符号表进行检查.它是否正确？但后来我不知道在代码中何处或如何开始实现它.

我意识到这不是一个真正的问题.......但是任何形式的指导或帮助将不胜感激.我班上有几个朋友跟我一样.

谢谢!

Answer 1

由于您的语言类似于 Java，您可以进行简单的类型传播，而不是更通用的类型推断。首先，您必须定义一个新的 AST，每个表达式都用其类型进行注释。然后，执行从旧 AST 到新 AST 的深度优先（对于表达式）/广度优先（对于块语句）转换，对每个节点应用简单的规则：

• 每个变量都按其类型进行注释，并且由于您对块进行了广度优先处理，因此必须在引用变量时固定所有变量类型。这适用于类字段、方法参数和局部范围的变量。
• 每个文字都会产生一个默认类型（字符串是字符串，整数是 32 位整数，浮点数是双精度数，等等）
• 二进制算术运算会根据一些排名规则插入隐式转换（选择任何一个，这并不重要）
• 三元运算符检查第一个参数是否为布尔值且其他两个参数是否为相同类型
• 方法调用是这里最复杂的事情：您必须获得第一个可能的重载方法，其参数类型可以隐式转换为所有参数。如果发生冲突，由您决定如何处理。
• 等等...

语句不能用类型注释，但您必须检查它们的表达式参数类型并可能进行隐式转换。您也可以在此阶段推断var或auto键入（请注意，这不是“类型推断”，只是类型传播的一种特殊情况）。