Haskell AST 中的非关联性

Question

我的任务是编写一个解析器，我将能够为其编写一个复合函数

f(x)(y)

。在我要编写的特定解析器中，这与大多数语言中的函数不同，是非关联函数。最好表示为

(f(x))(y)

，而

f(x)(y)

是不允许的。如果我有以下 AST，那么非关联解析会是什么样子？

据我了解，非关联概念意味着它既不是左关联也不是右关联。我查看了不同的网页以更好地理解非关联运算符，但我仍然对这个概念感到非常困惑。

AST：

data Expr =
 |Var String
 |Func Expr [Expr]

type FName = String

正确解析的非关联表达式会计算为：

(Func (Var "f") [Func (Var "x") [Var "y"]])

或

(Func (Func (Var "f") [Var "x"]) [Var "y"])

或以完全不同的方式？

Answer 1

关联性和括号都用于帮助解析器从给定的标记流中明确地生成 AST。

顺便说一句，你的

Func

构造函数看起来更像是代表函数 definition 的东西。函数应用程序将用另一个构造函数表示，例如

Apply Expr Expr

。

因此，在指定函数应用程序是左关联的语言中，我希望

f(x)(y)

看起来像

Apply (Apply (Var "f") (Var "x")) (Var "y")

同样，如果你的语法定义了非关联函数应用，那么

(f(x))(y)

会 still 产生相同的 AST，因为你的表达式仍然代表将

f

应用于

x

，then 将结果应用于

y

。

---

您的

Func

规则看起来像您用来表示定义的东西。继续使用仅具有变量和函数应用程序的语言，您的语法可能允许像

这样的表达式

lambda x: x(y)

它将解析为

Func (Var "x") (Apply (Var "x") (Var "y"))

定义并立即应用函数的表达式示例

(lambda x: x(y))(z)

然后会产生 AST

(Apply (Func (Var "x") (Apply (Var "x") (Var "y"))) (Var "z"))