编译器中中缀运算符的类型检查

Question

我正在编写一个编译器（使用Haskell语言），在该语言的语法中有添加中缀运算符的规则（以加法为例）：

EAdd . Expr ::= Expr "+" Expr

这意味着EAdd是一个表达式，它由表达式、字符串"+"和另一个表达式组成。

解析器返回抽象语法树（AST）：

data Expr = ... | EAdd Expr Expr

我想制作一个类型检查器，用于检查函数调用是否给出了正确类型的参数。

请注意，“+”是一个接受两个整数并返回一个整数的函数。其他运算符类似。

目前，我想到了三种方法来对 EAdd 进行类型检查，它们都包括将“+”添加为初始符号表中的函数：

1. Declare that infix plus is syntax sugar for calling function "+" with two arguments. Put "desugarizer" which converts AST from parser into another data type (without EAdd) in between parser and typechecker.

2. (similar to the first) Declare that infix plus is syntax sugar, but desugarizer uses same AST data type. Typechecker returns an error when it's given EAdd.

3. Inline "desugarizer" into typechecker. Similar to this:

   ...
   typecheck (EAdd a b) = typecheck (ECall infixPlus [a, b])
   ...
   

注意，所有二元中缀运算符都受到此影响(其他算术、布尔运算、比较运算符)。

似乎第一种方法是正确的。但这意味着在编译器流水线的后期，特别是在代码生成器中，那些ECalls应该被处理为特殊情况，因为在编译器的输出中(在我的情况下-llvm)，这些函数应该是内联的(不像普通函数调用)。这意味着代码生成器有一个函数列表，其中调用与其他函数调用不同。

如何解决这个问题最好？ 更新 Haskell中如何处理类似问题(来自https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Renamer)：

... renamer做了以下几件事：

• 整理修复。解析器将所有中缀应用程序解析为左关联，而不考虑修饰符。例如，“a + b * c”被解析为“(a + b) * c”。重命名器使用模块中声明的修饰符重新关联这些嵌套的运算符应用程序。

- andrybak

---

这是一个清晰易懂的描述您当前思考的方式。您想要得到什么问题的答案？ - Daniel Wagner

我觉得你的困惑源于你将加法视为一种特殊情况。我倾向于将_中缀运算符总体_解析为某些“中缀函数调用”AST元素，并使用其他（更明确且语法导向的）机制来表示函数是否应该内联。我不是编译器专家，所以请对我的想法持保留态度;) - Benjamin Hodgson

@BenjaminHodgson 针对AST的这些更改，操作优先级和结合性是如何处理的？ - andrybak

@andrybak，优先级/结合性不是基本上一个“解析”问题吗？解析器根据它对运算符优先级的了解为您有效地插入括号，但是_结果AST与您自己编写括号时相同_。（再次声明，我不是专家，可能会有人告诉我我所说的一切都是错误的） - Benjamin Hodgson

Answer 1

LLVM支持inline attributes，例如。

define void @f() alwaysinline { ... }

因此，一种选择是将+视为正常的函数调用，并让LLVM进行优化。

- chi

---

这意味着，每个使用二进制运算符的程序的 LLVM 代码将包含多个 alwaysinline 函数，这些函数通常（我猜测）在编译的前一步中被内联。 - andrybak