12 Appendix C: Expression Grammar Example

This appendix contains an example of use of the metaprogramming system for generating an expression calculator, enabling the user to enter expressions from the keyboard, which are then parser and the resulting AST is then evaluated by an interpreter (actually a recursive traversal of the AST, eveluating sunexpressions), and the calculated result is then printed on the screen. To give an impression of the application, the following is an example of an execution of the calculator (the underlined text is entered by the user Ñ expreval is the name of the calculator):

expreval
Eval? 3+4
7
Eval? (3+4)*(20+2)/4
38
Eval? (3+4
PARSE-ERRORS
#   1 (3+4
# ****** ^
#  Expected symbols:  / mod ) * +
Eval? 22 mod 5
2
Eval? .

This application consists of five files:

We will in the following present the five files along with a few comments on the important aspects of the particular file.

12.1 The Expression Grammar

This file contains the grammar that are used to check the syntax of the expressions of the calculator. The grammar is a fairly ordinary expression grammar, except that assignment statements are part of the legal syntax of the calculator, making the use of variables valid in the calculator. Please note the declaration of the substanceSlot and the attribute part.

--- expr: AGrammar: metagrammar ---
Grammar expr:
option 
    string = unused
    substanceSlot = dcAtt
Rule
  <stat> ::| <assignment> | <evalStatement> | <quit>;
  <assignment> ::= <name : nameDecl> '=' <expression>;
  <evalStatement> ::= <expression>;
  <quit> ::= '.';
  <expression> ::| <Term> | <addExpression>;
  <term> ::| <factor> | <multExpression>;
  <factor> ::| <number> | <bracketExpression> | <variable>;
  <bracketExpression> ::= '(' <expression> ')';
  <MultExpression> ::= <Operand1 : Term> <MultOperator> <Operand2 : Factor>;
  <AddExpression> ::= <Operand1 : Expression> <AddOperator> <Operand2 : Term>;
  <MultOperator> ::| <TimesOp> | <DivOp> | <ModOp>;
  <AddOperator> ::| <PlusOp> | <MinusOp>;
  <Number> ::= <Const>;
  <Variable> ::= <NameAppl>;
  <TimesOp> ::= '*';
  <DivOp> ::= '/';
  <ModOp> ::= 'mod';
  <plusOp> ::= '+';
  <minusOp> ::= '-'
attribute
  (* the following definitions will trigger the generator to make
   *  semantic attribute slots for the generated context free level
   *)
  <expression> : 0

12.2 The Expression Pretty-Print Grammar

This file contains the pretty-pring grammar, used by the calculator. Strictly speaking this pretty-print grammar is not used by the calculator.

--- expr : prettyprint : prettyprint --- 
PrettyPrintScheme exprSpec
for expr:
stat    =  N:1 ;
assignment      = [c  N:1 $1,0 T:1 $1,0 * $1,2 N:2];
evalStatement   =  N:1;
quit    =  T:1 $1,0 *;
expression      =  N:1 ;
term    =  N:1 ;
factor  =  N:1 ;
bracketExpression       = [c  T:1 $1,0 * $1,2 N:1 $1,0 T:2];
MultExpression  = [c  N:1 $1,2 N:2 $1,2 N:3];
AddExpression   = [c  N:1 $1,2 N:2 $1,2 N:3];
MultOperator    =  N:1 ;
AddOperator     =  N:1 ;
Number  =  N:1;
Variable        =  N:1;
TimesOp =  T:1 $1,0 *;
DivOp   =  T:1 $1,0 *;
ModOp   =  T:1 $1,0 *;
plusOp  =  T:1 $1,0 *;
minusOp =  T:1 $1,0 *

12.3 The Expression Context-Free Level Interface

This file contains the generated context-free level interface. Please note the effects of the substanceSlot and attribute part specifications in the grammar. The init routine only contains initializations that can be ignored.

ORIGIN '~beta/mps/astlevel'
--- astInterfaceLib: attributes---
expr: TreeLevel
  (# stat: cons
       (# <<SLOT statAttributes: attributes>> #);
     expression: cons
       (# <<SLOT expressionAttributes: attributes>> #);
     term: expression
       (# #);
     factor: term
       (# #);
     MultOperator: cons
       (# #);
     AddOperator: cons
       (# #);
     assignment: stat
       (# getname: getson1(# #);
          putname: putson1(# #);
          getexpression: getson2(# #);
          putexpression: putson2(# #);
       exit 2
       #);
     evalStatement: stat
       (# getexpression: getson1(# #);
          putexpression: putson1(# #);
       exit 3
       #);
     quit: stat
       (# exit 4 #);
     bracketExpression: factor
       (# getexpression: getson1(# #);
          putexpression: putson1(# #);
       exit 8
       #);
     MultExpression: term
       (# getOperand1: getson1(# #);
          putOperand1: putson1(# #);
          getMultOperator: getson2(# #);
          putMultOperator: putson2(# #);
          getOperand2: getson3(# #);
          putOperand2: putson3(# #);
       exit 9
       #);
     AddExpression: expression
       (# getOperand1: getson1(# #);
          putOperand1: putson1(# #);
          getAddOperator: getson2(# #);
          putAddOperator: putson2(# #);
          getOperand2: getson3(# #);
          putOperand2: putson3(# #);
       exit 10
       #);
     Number: factor
       (# getConst: getson1(# #);
          putConst: putson1(# #);
       exit 13
       #);
     Variable: factor
       (# getNameAppl: getson1(# #);
          putNameAppl: putson1(# #);
       exit 14
       #);
     TimesOp: MultOperator
       (# exit 15 #);
     DivOp: MultOperator
       (# exit 16 #);
     ModOp: MultOperator
       (# exit 17 #);
     plusOp: AddOperator
       (# exit 18 #);
     minusOp: AddOperator
       (# exit 19 #);
     grammarIdentification::<
       (# do 'expr'->theGrammarName #);
     version::< 
       (# do -1->value #);
     suffix::<
       (# do '.text'->theSuffix #);
     maxproductions::<
       (# do 19->value #);
     dcAtt: @
       <<SLOT dcAtt: descriptor>>;
     init::< 
       (# ... #);
  #)

12.4 The Expression Semantic Level Interface

This file contains the semantic level interface, written for the calculator. Please note the utilization of the SLOTs, generated as the result of the substanceSlot and attribute part of the grammar.

ORIGIN 'exprcfl';
INCLUDE '~beta/containers/hashTable'
--- expressionAttributes: attributes ---
eval: 
  (# value: @integer ;
     n: ^number;
     cnst: ^const;
     m: ^multExpression;
     a: ^addExpression;
     anAst: ^ast;
     be: ^bracketExpression;
     e1,e2: ^expression;
     var: ^variable;
     na: ^nameAppl;
  do (if symbol
      //bracketExpression then 
         this(expression)[] -> be[]; be.getExpression -> e1[]; e1.eval -> value
      //multexpression then 
         this(expression)[] -> m[];
         m.getOperand1 -> e1[]; m.getoperand2 -> e2[];
         m.getMultOperator -> anAst[];
         (if anAst.symbol
          //timesop then e1.eval * e2.eval -> value
          //divop then e1.eval div e2.eval -> value
          //modOp then e1.eval mod e2.eval -> value
         if);
      //addexpression then
         this(expression)[] -> a[];
         a.getOperand1 -> e1[]; a.getOperand2 -> e2[];
         a.getAddOperator -> anAst[];
         (if anAst.symbol
          //plusOp then e1.eval + e2.eval -> value
          //minusOp then e1.eval - e2.eval -> value
         if)
      //number then this(expression)[]->n[];
                    n.getConst->cnst[]; cnst.getValue -> value
      //variable then this(expression)[] -> var[];
         var.getnameAppl -> na[];
         (# e: ^dcAtt.symbolTable.element
         do na[] -> dcAtt.symbolTable.findKey -> e[];
            (if e[]//none then
                na.getText -> screen.putText;
                ' is not declared ' -> screen.putLine;
             else e.e.eval -> value
            if);
         #);
     if)  
  exit value
  #)

--- dcAtt: descriptor ---
(# symbolTable: @hashTable
     (# element::< (# id: ^lexemText; e: ^expression #);
        hashFunction::< 
          (# t: ^text 
          do e.id.getText -> t[];
             t.scan(# do (ch->ascii.lowCase)+133*value -> value #);
          #);
        equal::< 
          (# equalText:
               (# t1,t2: ^text enter (t1[],t2[]) exit t1[] -> t2.equalNCS #)
          do (left.id.getText,right.id.getText) -> equalText -> value
          #);
        findKey: 
          (# e: @element; found: ^element
          enter e.id[]
          do scan(# where::< (# do (e[],current[]) -> equal -> value #)
                 do current[] -> found[] #)
          exit found[]
          #);
     #);
   init: (# do symbolTable.init #);
#)

------ statAttributes: attributes ------
run: 
  (# expr: ^expression;
     eval: ^evalStatement;
     let: ^assignment;
     elm: ^dcAtt.symbolTable.element
  do (if symbol
      //assignment then 
         this(stat)[] -> let[];
         &amp;dcAtt.symbolTable.element[] -> elm[];
         let.getName -> elm.id[];
         let.getExpression -> elm.e[];
         elm[] -> dcAtt.symbolTable.insert;
      //evalStatement then
         this(stat)[] -> eval[];
         eval.getExpression -> expr[];
         expr.eval -> screen.putInt;
         screen.newLine 
      //quit then (normal,'') -> stop
     if);

12.5 The Expression Evaluator Program

This file contains the initialization of the metaprogramming system and the handling of the keybroard and screen. Please note the use of the parser, the handling of parse errors, and the evaluation of the ASTs, resulting from successful parsing of the input.

ORIGIN 'exprcfl';
INCLUDE 'exprsematt'
--- program: descriptor ---
(# (* This is a small demo-program of how to use the MetaProgrammingSystem.
    * The program implements a small desc-calculator a la dc in unix.  The
    * grammar for expressions is on the file expr-meta.gram.  The generated
    * context free level is on exprCfl.  Exprsematt contains semantic
    * attributes for expr.
    *)
   ast: @astinterface;
   expr: @ast.expr; (* the cfl of the grammar *)
   exprFragment: ^ast.fragmentForm;
   evalString: ^text;
   stat: ^expr.stat;
   ok: @boolean;
   btabFile: ^text;
do ast.astLevelInit; (* initialize astlevel *)
   expr.init;        (* and the context free level of the generated grammar *)
   'expr-parser' -> btabFile[];
   ast.parserFileExtension->btabFile.puttext;
   btabFile[] -> expr.parser.initialize; (* and the parser *)
   expr[] -> ast.newFragmentForm -> exprFragment[]
   (* create a fragmentform which can contain the asts *);
   cycle
   (# do
      'Eval? ' -> screen.putText;
      keyBoard.getLine -> evalString[]; (* read a string from keyboard *)
      evalString.newLine; (* add a newline to the string *)
      0 -> evalString.setPos;  (* reset evalString to start *)
      (1,evalString[],screen[],exprFragment[]) -> expr.parser -> ok;
      (* 1: goalSymbol,
       * evalString: input,
       * exprFragment: the fragmentform to contains the asts 
       *)
      (if ok 
       //false then 
          'PARSE-ERRORS' -> screen.putLine;
          0 -> evalString.setPos; (* reset evalString to start *)
          (evalString[],screen[]) -> expr.parser.ErrorReport;
       else  (* there was no parse-errors *)
          exprFragment.root[] -> stat[];
          (* the parser returns the root of the parsed ast in fragment.root *)
          stat.run; 
      if);
   #)


The Metaprogramming System - Reference Manual
© 1991-2004 Mjølner Informatics
[Modified: Thursday October 19th 2000 at 12:04]