Parsing and implementing a lambda calculus in Rascal

Question

I am trying to implement a lambda calculus inside of Rascal but am having trouble getting the precedence and parsing to work the way I would like it to. Currently I have a grammar that looks something like:

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

When I parse a program of the form:

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

The resulting tree is:

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

Where really I am looking for something like this (I think):

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

I've tried a number of variations of the precedence in the grammar, I've tried wrapping the App rule in parenthesis, and a number of other variations. There seems to be something going on here I don't understand. Any help would be most appreciated. Thanks.

Answer 1

I've used the following grammar, which removes the extra LAYOUTLIST and the dead right, but this should not make a difference. It seems to work as you want when I use the generic implode function :

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
    ;

Then calling the parser and imploding to an untyped AST (I've removed the location annotations for readability):

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")))

So, I am guessing you got the grammar right for the shape of tree you want. How do you go from concrete parse tree to abstract AST? Perhaps there is something funny going on there.