Example: A language for arithmetic constructs
Specifying the Syntax
An arithmetic expression either consists of numbers or boolean values or expressions with primary operators/apps like +,-,/,* etc and operands. Thus, the grammar of such a language can be written as:
ast ::= num-ast | bool-ast | prim-app-ast
num-ast implies an ast consisting of just numbers, for example: 5, 6, 2, 0 etc.
bool-ast implies an ast consisting of just boolean values, i.e. 0 and 1.
prim-app-ast consists of an arithmetic operator and its operands (which in turn are again of the form - ast)
In order to come up with an abstract syntax, for a given concrete syntax, we must name each production of the concrete syntax and each occurrence of a nonterminal in each production. Thus we’d have to create one define-datatype for each nonterminal, with one variant for each production.
Hence, the abstract syntax of this language would be:
|(define-datatype ast ast?
| [number (datum number?)]
| [boolean (datum boolean?)]
| [prim-app (op op-symbol?) (rands (list-of ast?))])
Specification of Values
While designing any programming language, its highly important to specify the set of values that the language manipulates.
Each language has, the following sets of values:
Expressible Values : set of values that are the results of evaluation of expressions (ASTs).
In our case, since any expression evaluates to either a number or a boolean, the set of expressible values would be (number, boolean). Thus, we can also define a predicate to test for expressible-values as follows:
(or (number? thing)
Denotable Values : set of values which are bound to variables.
NOTE: the set of expressible and denotable values can be different.
Designing the Parser
The concrete syntax of this language is as follows:
exp ::= <number> | <boolean> | (<op> exp ...)
op ::= one of <op-symbols>
where <op-symbols> = (+,-,/,*, <, <=, eq?, 0?)
As discussed earlier, the task of a parser is to convert any given program sequence into an ast. Hence, the signature of our parser procedure would be:
(parse code) → ast?
code : any/c?
Now, while going through the input sequence if we find the current literal to be a terminal i.e. a boolean or a number, then we output the corresponding node of the ast i.e. (number literal) or (boolean literal). In case of an operator expression, we parse the operator as (prim-app op), and then call the parse function for the list of expressions (i.e. the operands).
Designing the Evaluator
The evaluator takes an ast and returns the value obtained by evaluating the ast, i.e. an expressible value. Hence its signature would look like:
(eval-ast ast) → expressible-value? ast : ast?
For the naive case, where the ast consists of just a number or a boolean, the returned value would necessarily be the value of the number or the boolean. However, in the case of an expression, we’d need first evaluate each of the operands and then apply the operator on the obtained evaluated values. Thus, we’d need a procedure apply-prim-op which takes an operator and a list of expressible values, and applies the operator on them, i.e.