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:

• expr-meta.gram: Contains the grammar specification for the valid expressions.
• expr-pretty.pgram: Contains the pretty-printer specification.
• exprcfl.bet: Contains the generated context-free level interface.
• exprsematt.bet: Contains the additional semantic level interface. Primerily the eval routine.
• expreval.bet: Contains the initialization, and keyboard and screen handling code.

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