在 Rascal 中解析和实现 lambda 演算

Question

我正在尝试在 Rascal 内部实现 lambda 演算，但无法按照我希望的方式获得优先级和解析。目前我的语法看起来像：

keyword Keywords= "if" | "then" | "else"  | "end" | "fun";

lexical Ident = [a-zA-Z] !>> [a-zA-Z]+ !>> [a-zA-Z0-9] \ Keywords;
lexical Natural = [0-9]+  !>> [0-9];
lexical LAYOUT = [\t-\n\r\ ];
layout LAYOUTLIST = LAYOUT*  !>> [\t-\n\r\ ];

start syntax Prog = prog: Exp LAYOUTLIST;

syntax Exp =
    var: Ident
    | nat: Natural
    | bracket "(" Exp ")"
    > left app: Exp Exp
    > right func: "fun" Ident "-\>" Exp

当我解析以下形式的程序时：

(fun x -> fun y -> x) 1 2

生成的树是：

prog(app(
    app(
      func(
        "x",
        func(
          "y",
          var("x")
      nat(1),
    nat(2))))))

我真的在哪里寻找这样的东西（我认为）：

prog(app(
    func(
      "x",
      app(
        func(
          "y",
          var("x")),
        nat(2))),
    nat(1)))

我尝试了语法中优先级的多种变体，我尝试了将 App 规则括在括号中，以及许多其他变体。这里似乎发生了一些我不明白的事情。非常感激任何的帮助。谢谢

Answer 1

我使用了以下语法，它删除了多余的 LAYOUTLIST 和死的 right，但这应该没有什么区别。当我使用通用 implode 函数时，它似乎如你所愿地工作：

keyword Keywords= "if" | "then" | "else"  | "end" | "fun";

lexical Ident = [a-zA-Z] !>> [a-zA-Z]+ !>> [a-zA-Z0-9] \ Keywords;
lexical Natural = [0-9]+  !>> [0-9];
lexical LAYOUT = [\t-\n\r\ ];
layout LAYOUTLIST = LAYOUT*  !>> [\t-\n\r\ ];

start syntax Prog = prog: Exp;

syntax Exp =
    var: Ident
    | nat: Natural
    | bracket "(" Exp ")"
    > left app: Exp Exp
    > func: "fun" Ident "-\>" Exp
    ;

然后调用解析器并分解为无类型的 AST（为了便于阅读，我删除了位置注释）：

rascal>import ParseTree;
ok
rascal>implode(#node, parse(#start[Prog], "(fun x -\> fun y -\> x) 1 2"))
node: "prog"("app"(
        "app"(
          "func"(
            "x",
            "func"(
              "y",
              "var"("x"))),
          "nat"("1")),
        "nat"("2")))

所以，我猜你的语法适合你想要的树的形状。你如何从具体的解析树到抽象的 AST？也许那里发生了一些有趣的事情。

在 Rascal 中解析和实现 lambda 演算

Parsing and implementing a lambda calculus in Rascal

lambda

parsing

lambda-calculus

rascal