Name Recipes/Languages/Exp/Concrete/NoLayout

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        
  ;

Notes:

• 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);                      

Notes:

• 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;
ok
rascal>import ParseTree;
ok

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;
ok
rascal>eval("2+3");
int: 5
rascal>eval("2+3*4");
int: 14
rascal>eval("(2+3)*4");
int: 20

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