Name Recipes/Languages/Exp/Combined/Automatic

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

Description Rascal: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:

module demo::lang::Exp::Combined::Automatic::Syntax

lexical LAYOUT = [\t-\n\r\ ];                    

layout LAYOUTLIST = LAYOUT*  !>> [\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 , and 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 ...

module demo::lang::Exp::Combined::Automatic::Parse

import demo::lang::Exp::Combined::Automatic::Syntax;
import ParseTree;

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

... and this is how it works:

rascal>import demo::lang::Exp::Combined::Automatic::Parse;
ok
rascal>parseExp("2+3*4");
Tree: `2+3*4`
Tree: appl(prod(label("add",sort("Exp")),[sort("Exp"),layouts("LAYOUTLIST"),lit("+"),layouts("LAYOUTLIST"),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)])[@loc=|file://-|(0,1,<1,0>,<1,1>)]])[@loc=|file://-|(0,1,<1,0>,<1,1>)]])[@loc=|file://-|(0,1,<1,0>,<1,1>)],appl(prod(layouts("LAYOUTLIST"),[conditional(\iter-star(lex("LAYOUT")),{\not-follow(\char-class([range(9,10),range(13,13),range(32,32)]))})],{}),[appl(regular(\iter-star(lex("LAYOUT"))),[])[@loc=|file://-|(1,0,<1,1>,<1,1>)]])[@loc=|file://-|(1,0,<1,1>,<1,1>)],appl(prod(lit("+"),[\char-class([range(43,43)])],{}),[char(43)]),appl(prod(layouts("LAYOUTLIST"),[conditional(\iter-star(lex("LAYOUT")),{\not-follow(\char-class([range(9,10),range(13,13),range(32,32)]))})],{}),[appl(regular(\iter-star(lex("LAYOUT"))),[])[@loc=|file://-|(2,0,<1,2>,<1,2>)]])[@loc=|file://-|(2,0,<1,2>,<1,2>)],appl(prod(label("mul",sort("Exp")),[sort("Exp"),layouts("LAYOUTLIST"),lit("*"),layouts("LAYOUTLIST"),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)])[@loc=|file://-|(2,1,<1,2>,<1,3>)]])[@loc=|file://-|(2,1,<1,2>,<1,3>)]])[@loc=|file://-|(2,1,<1,2>,<1,3>)],appl(prod(layouts("LAYOUTLIST"),[conditional(\iter-star(lex("LAYOUT")),{\not-follow(\char-class([range(9,10),range(13,13),range(32,32)]))})],{}),[appl(regular(\iter-star(lex("LAYOUT"))),[])[@loc=|file://-|(3,0,<1,3>,<1,3>)]])[@loc=|file://-|(3,0,<1,3>,<1,3>)],appl(prod(lit("*"),[\char-class([range(42,42)])],{}),[char(42)]),appl(prod(layouts("LAYOUTLIST"),[conditional(\iter-star(lex("LAYOUT")),{\not-follow(\char-class([range(9,10),range(13,13),range(32,32)]))})],{}),[appl(regular(\iter-star(lex("LAYOUT"))),[])[@loc=|file://-|(4,0,<1,4>,<1,4>)]])[@loc=|file://-|(4,0,<1,4>,<1,4>)],appl(prod(label("con",sort("Exp"...

We can use parse to define load:

module demo::lang::Exp::Combined::Automatic::Load

import demo::lang::Exp::Combined::Automatic::Parse;  
import demo::lang::Exp::Abstract::Syntax;            
import ParseTree;                                    

public Exp load(str txt) = implode(#Exp, parseExp(txt)); 

Notes:

• We also need the parse function, as defined above.
• We also need the abstract syntax as already defined earlier in Exp/Abstract.
• We need Rascal:ParseTree since it provides the Rascal:implode function.

Let's try it:

rascal>import demo::lang::Exp::Combined::Automatic::Load;
ok
rascal>load("2+3*4");
Exp: add(
  con(2)[
    @location=|file://-|(0,1,<1,0>,<1,1>),
    @comments=()
  ],
  mul(
    con(3)[
      @location=|file://-|(2,1,<1,2>,<1,3>),
      @comments=()
    ],
    con(4)[
      @location=|file://-|(4,1,<1,4>,<1,5>),
      @comments=()
    ])[
    @location=|file://-|(2,3,<1,2>,<1,5>),
    @comments=()
  ])[
  @location=|file://-|(0,5,<1,0>,<1,5>),
  @comments=()
]

Remains the definition of the eval function:

module demo::lang::Exp::Combined::Automatic::Eval

import demo::lang::Exp::Abstract::Syntax;
import demo::lang::Exp::Abstract::Eval;
import demo::lang::Exp::Combined::Automatic::Load;

public int eval(str txt) = eval(load(txt));

public value main(list[value] args){
  return eval("1+2");
}

Here is the end result:

rascal>import demo::lang::Exp::Combined::Automatic::Eval;
ok
rascal>eval("2+3*4");
int: 14

[Edit] | [New Subconcept] | [Recompile Course] | [Warnings]