Synopsis A version of Exp based on concrete syntax.
Description We describe howto write a grammar for Exp and how to use it to implement an evaluator.
Examples Here is the grammar for Exp:
module demo::lang::Exp::Concrete::NoLayout::Syntax
lexical IntegerLiteral = [0-9]+;           

start syntax Exp            
  = IntegerLiteral          
  | bracket "(" Exp ")"     
  > left Exp "*" Exp        
  > left Exp "+" Exp        
  • defines a lexical syntax rule for IntegerLiterals; they consist of one or more digits.
  • defines the alternatives for Exp. The keyword start means that this is a start symbol of the grammar.
  • defines alternative #1: an IntegerLiteral.
  • defines alternative #2: parentheses. The | says that this alternative has the same priority as the previous one. The keyword bracket marks this as an alternative that defines parentheses.
  • defines alternative #3: multiplication. The > says that the previous rule has a higher priorrity than the current one. The keyword left marks this as a left-associative rule.
  • defines alternative #4: addition. The > says again that the previous rule has a higher priorrity than the current one. The keyword left marks this as a left-associative rule.
Now that the grammar is in place we want to use it to build an evaluator. Here is how:
module demo::lang::Exp::Concrete::NoLayout::Eval
import demo::lang::Exp::Concrete::NoLayout::Syntax;

import String;
import ParseTree;                                                 

public int eval(str txt) = eval(parse(#Exp, txt));                

public int eval((Exp)`<IntegerLiteral l>`) = toInt("<l>");        
public int eval((Exp)`<Exp e1>*<Exp e2>`) = eval(e1) * eval(e2);  
public int eval((Exp)`<Exp e1>+<Exp e2>`) = eval(e1) + eval(e2);  
public int eval((Exp)`(<Exp e>)`) = eval(e);                      
  • We import Rascal:ParseTree because we will need the parse function below.
  • The main function eval that evaluates an expression as string to an integer. It proceeds in two steps:
    • parse(#Exp, txt) parses the given txt according to non-terminal Exp as defined by the grammar. The result is a parse tree.
    • This parse tree is given to another eval function that will reduce the tree to an integer.
  • Converts an IntegerLiteral to an integer. Let's dissect this further:
    • The Exp preceding the concrete pattern, unambiguously defines the type of the pattern. This is good practice to avoid ambiguities.
    • <IntegerLiteral l> matches an IntegerLiteral and binds it (a parse tree fragment) to variable l.
    • In the function body, toInt("<l>"), the parse tree fragment is inserted in a string -- effectively unparsing it -- and that string is converted to an integer.
  • and handle the multiplication and addition cases.
  • handles the case of parentheses.
What remains, is to check that eval works as expected.
rascal>import demo::lang::Exp::Concrete::NoLayout::Syntax;
rascal>import ParseTree;
Just checking that parse returns a sort of parse tree:
rascal>parse(#Exp, "2+3");
sort("Exp"): `2+3`
Tree: appl(prod(sort("Exp"),[sort("Exp"),layouts("default"),lit("+"),layouts("default"),sort("Exp")],{assoc(left())}),[appl(prod(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("default"),[],{}),[])[@loc=|file://-|(1,0,<1,1>,<1,1>)],appl(prod(lit("+"),[\char-class([range(43,43)])],{}),[char(43)]),appl(prod(layouts("default"),[],{}),[])[@loc=|file://-|(2,0,<1,2>,<1,2>)],appl(prod(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>)]])[@loc=|file://-|(0,3,<1,0>,<1,3>)]
You will see such parse trees only once, unless you are a researcher in parsing ;-) Here is a demonstration of eval:
rascal>import demo::lang::Exp::Concrete::NoLayout::Eval;
int: 5
int: 14
int: 20
Is this page unclear, or have you spotted an error? Please add a comment below and help us to improve it. For all other questions and remarks, visit