Automatic

rascal-0.34.0

Synopsis

Use implode to translate an Exp parse tree to an abstract syntax tree.

Description

implode is a function that automates the mapping between parse trees and abstract syntax trees. It takes two arguments:

• The reified type of the desired abstract syntax. (In Rascal, types can not be used freely as values. A reified type, is a type that is wrapped in such a way that it can be passed as an argument to a function.)
• The parse tree to be converted.

implode is smart in trying to find a mapping, but it needs some guidance. A necessary step is therefore to label the rules in the grammar with the name of the constructor to which it has to be mapped.

Examples

Let's first label the syntax rules of the Exp grammar with constructor names:

layout Whitespace = [\t-\n\r\ ]*;                    

lexical IntegerLiteral = [0-9]+;           

start syntax Exp 
    = con: IntegerLiteral        ❶  
    | bracket "(" Exp ")"     
    > left mul: Exp "*" Exp      ❷    
    > left add: Exp "+" Exp      ❸     
    ;

Observe that at 1, 2, 3 these labels have been added.

It is good practice to introduce separate modules for parsing and for the conversion itself:

• A Parse module defines a parse function and returns a parse tree. It imports only the concrete syntax.
• A Load module defines a load function that first calls the above parse function and then applies implode to it. This is the only module that imports both concrete and abstract syntax at the same time and is therefore the only place to be concerned about name clashes. (If I mention Exp, do you know which one I mean?).

Here is the Parse module for Exp ...

import ParseTree;

Tree parseExp(str txt) = parse(#Exp, txt); 

and this is how it works:

rascal>example = parseExp("2+3*4");
Tree: appl(
  prod(
    label(
      "add",
      sort("Exp")),
    [
      sort("Exp"),
      layouts("Whitespace"),
      lit("+"),
      layouts("Whitespace"),
      sort("Exp")
    ],
    {assoc(left())}),
  [appl(
      prod(
        label(
          "con",
          sort("Exp")),
        [lex("IntegerLiteral")],
        {}),
      [appl(
          prod(
            lex("IntegerLiteral"),
            [iter(\char-class([range(48,57)]))],
            {}),
          [appl(
              regular(iter(\char-class([range(48,57)]))),
              [char(50)],
              src=|unknown:///|(0,1,<1,0>,<1,1>))],
          src=|unknown:///|(0,1,<1,0>,<1,1>))],
      src=|unknown:///|(0,1,<1,0>,<1,1>)),appl(
      prod(
        layouts("Whitespace"),
        [\iter-star(\char-class([
                range(9,10),
                range(13,13),
                range(32,32)
              ]))],
        {}),
      [appl(
          regular(\iter-star(\char-class([
                  range(9,10),
                  range(13,13),
                  range(32,32)
                ]))),
          [],
          src=|unknown:///|(1,0,<1,1>,<1,1>))],
      src=|unknown:///|(1,0,<1,1>,<1,1>)),appl(
      prod(
        lit("+"),
        [\char-class([range(43,43)])],
        {}),
      [char(43)]),appl(
      prod(
        layouts("Whitespace"),
        [\iter-star(\char-class([
                range(9,10),
                range(13,13),
                range(32,32)
              ]))],
        {}),
      [appl(
          regular(\iter-star(\char-class([
                  range(9,10),
                  range(13,13),
                  range(32,32)
                ]))),
          [],
          src=|unknown:///|(2,0,<1,2>,<1,2>))],
      src=|unknown:///|(2,0,<1,2>,<1,2>)),appl(
      prod(
        label(
          "mul",
          sort("Exp")),
        [
          sort("Exp"),
          layouts("Whitespace"),
          lit("*"),
          layouts("Whitespace"),
          sort("Exp")
        ],
        {assoc(left())}),
      [appl(
          prod(
            label(
              "con",
              sort("Exp")),
            [lex("IntegerLiteral")],
            {}),
          [appl(
              prod(
                lex("IntegerLiteral"),
                [iter(\char-class([range(48,57)]))],
                {}),
              [appl(
                  regular(iter(\char-class([range(48,57)]))),
                  [char(51)],
                  src=|unknown:///|(2,1,<1,2>,<1,3>))],
              src=|unknown:///|(2,1,<1,2>,<1,3>))],
          src=|unknown:///|(2,1,<1,2>,<1,3>)),appl(
          prod(
            layouts("Whitespace"),
            [\iter-star(\char-class([
                    range(9,10),
                    range(13,13),
                    range(32,32)
                  ]))],
            {}),
          [appl(
              regular(\iter-star(\char-class([
                      range(9,10),
                      range(13,13),
                      range(32,32)
                    ]))),
              [],
              src=|unknown:///|(3,0,<1,3>,<1,3>))],
          src=|unknown:///|(3,0,<1,3>,<1,3>)),appl(
          prod(
            lit("*"),
            [\char-class([range(42,42)])],
            {}),
          [char(42)]),appl(
          prod(
            layouts("Whitespace"),
            [\iter-star(\char-class([
                    range(9,10),
                    range(13,13),
                    range(32,32)
                  ]))],
            {}),
          [appl(
              regular(\iter-star(\char-class([
                      range(9,10),
                      range(13,13),
                      range(32,32)
                    ]))),
              [],
              src=|unknown:///|(4,0,<1,4>,<1,4>))],
          src=|unknown:///|(4,0,<1,4>,<1,4>)),appl(
          prod(
            label(
              "con",
              sort("Exp")),
            [lex("IntegerLiteral")],
            {}),
          [appl(
              prod(
           ...

We can use parse to define load:

data Exp       ❷  
    = con(int n)                 
    | mul(Exp e1, Exp e2)        
    | add(Exp e1, Exp e2)        
    ;

import ParseTree;      ❸  

Exp load(Tree t) = implode(#Exp, t); 

Notes:

• ❶ We also need the parse function, as defined above.
• ❷ We also need the abstract syntax, show directly here. Note that in order to separate Exp the syntax type clearly from Exp the data type, you must position their definitions in separate modules.
• ❸ We need Parse Tree since it provides the Implode function.

Let's try it:

rascal>example2 = load(example);
Exp: add(
  con(
    2,
    src=|unknown:///|(0,1,<1,0>,<1,1>),
    comments=()),
  mul(
    con(
      3,
      src=|unknown:///|(2,1,<1,2>,<1,3>),
      comments=()),
    con(
      4,
      src=|unknown:///|(4,1,<1,4>,<1,5>),
      comments=()),
    src=|unknown:///|(2,3,<1,2>,<1,5>),
    comments=()),
  src=|unknown:///|(0,5,<1,0>,<1,5>),
  comments=())

Remains the definition of the eval function:

int eval(con(int n)) = n;                            
int eval(mul(Exp e1, Exp e2)) = eval(e1) * eval(e2); 
int eval(add(Exp e1, Exp e2)) = eval(e1) + eval(e2); 

Here is the end result:

rascal>eval(example2);
int: 14