Tree Builders
Visitors
This appendix contains tables which index the tree builders, interpreters, type checkers, and stack machine code generators for the little language developed in chapter eleven. The table entries are linked to the examples, to the documentation, and from there to the sources.
All code is structured as mix-ins which are mostly independent of each other
to be combined for different types of language processing.
All classes and mix-ins are contained in module Eleven.
The method browser described in appendix C can be used to compare the action methods for the tree builders and the processing methods in the visitors.
Tree Builders
Trees are built during recognition, i.e., in action methods.
Tree builder mix-ins are applied to the base class Build
which provides a small amount of infrastructure.
Tree building employs an SLR(1) grammar with a precedence table which allows a symmetric definition of the operations in expressions. This table links the precedence levels to the builders and examples which require them:
| precedence |
builder mix-in |
used in |
|---|---|---|
%left 'or';%left 'and'; |
Build_Bool |
06 07 08 09 12 |
%nonassoc '=' '<>' '>' '>=' '<' '<='; |
Build_Cmps |
04 05 06 07 08 09 11 12 |
%left '+' '-';%left '*' '/';%right '**';%right Number; |
Build_Number |
02 03 04 05 06 07 08 09 10 11 12 |
The following table links tree builder mix-ins to the examples which use them, lists their grammar rules and links them to the builder actions and from there to the sources, and specifies the resulting tree nodes or values. The table in the next section of this appendix relates the tree nodes to visitor mix-ins which can process them and to the examples which use the visitors.
The Main mix-in
supports a build rule main: tree; which applies a list of visitors,
specified as mix-in arguments, to the tree and returns a function which will apply the last visitor.
Convenience methods support build rules dump: tree; to dump a tree and run: function; to execute the function.
The Compile mix-in
supports a build rule compile: tree; which applies a list of visitors,
specified as mix-in arguments, to the tree
and returns the executable created by the last visitor which must be a code generator.
Operations on names require a symbol table which is supported by the
Symbols mix-in
and forwarded from one visitor to the next.
Compile, used in 10 11 12 |
action | returns |
|---|---|---|
compile: tree; |
compile() |
(memory, steps) => StackMachine(memory, steps) |
Main, used in 03 05 06 07 08 09 10 11 12 |
action | returns |
run: function; |
run() |
function's result |
main: tree; |
main() |
() => last visitor(tree) |
dump: tree; |
dump() |
tree |
Build_Dcl, used in 08 09 12 |
action | returns |
block: item [{ ';' item }]; |
block() |
[ 'block' dcl ... stmt ... ] |
item: dcl | stmt; |
||
dcl: type Name [{ ',' Name }]; |
dcl() |
[ 'dcl' type Name ... ] |
Build_Stmts, used in 04 05 08 09 11 12 |
action | returns |
stmts: stmt [{ ';' stmt }]; |
stmts() |
stmt | [ 'stmts' stmt ... ] |
stmt: print | ...; |
stmt() |
tree |
print: 'print' expr [{ ',' expr }]; |
print() |
[ 'print' expr ... ] |
loop: 'while' expr 'do' stmts 'od'; |
loop() |
[ 'loop' expr stmts ] |
select: 'if' expr 'then' stmts [ 'else' stmts ] 'fi'; |
select() |
[ 'if' expr stmts stmts? ] |
Build_Names, used in 04 05 08 09 11 12 |
action | returns |
assign: Name '=' expr; |
assign() |
[ 'assign' Name expr ] |
name: Name; |
name() |
[ 'name' Name ] |
Build_Cast, used in 06 07 08 09 12 |
action | returns |
type: 'bool' | 'number' | 'string'; |
type() |
typename |
cast: '(' type ')' expr %prec Number; |
cast() |
[ 'cast' type expr ] |
Build_String, used in 06 07 08 09 12 |
action | returns |
input: 'input' [ String String ]; |
input() |
[ 'input' String? String? ] |
len: 'len' expr %prec Number; |
len() |
[ 'len' expr ] |
string: String; |
string() |
[ 'string' String ] |
Build_Bool, used in 06 07 08 09 12 |
action | returns |
or: expr 'or' expr; |
or() |
[ 'or' expr expr ] |
and: expr 'and' expr; |
and() |
[ 'and' expr expr ] |
not: 'not' expr %prec Number; |
not() |
[ 'not' expr ] |
bool: 'true' | 'false'; |
bool() |
[ 'bool' Boolean ] |
Build_Cmps, used in 04 05 06 07 08 09 11 12 |
action | returns |
eq: expr '=' expr; |
eq() |
[ 'eq' expr expr ] |
ne: expr '<>' expr; |
ne() |
[ 'ne' expr expr ] |
gt: expr '>' expr; |
gt() |
[ 'gt' expr expr ] |
ge: expr '>=' expr; |
ge() |
[ 'ge' expr expr ] |
lt: expr '<' expr; |
lt() |
[ 'lt' expr expr ] |
le: expr '<=' expr; |
le() |
[ 'le' expr expr ] |
Build_Number, used in 02 03 04 05 06 07 08 09 10 11 12 |
action | returns |
expr: add | ... | '(' expr ')'; |
expr() |
tree |
add: expr '+' expr; |
add() |
[ 'add' expr expr ] |
subtract: expr '+' expr; |
subtract() |
[ 'subtract' expr expr ] |
multiply: expr '+' expr; |
multiply() |
[ 'multiply' expr expr ] |
divide: expr '+' expr; |
divide() |
[ 'divide' expr expr ] |
power: expr '+' expr; |
power() |
[ 'power' expr expr ] |
minus: '-' expr %prec Number; |
minus() |
[ 'minus' expr ] |
number: Number; |
number() |
[ 'number' Number ] |
Visitors
The visitor pattern is useful to process trees.
Module Eleven implements three kinds of visitors:
-
Ⓔ Interpreters visit trees and evaluate the nodes — basically in postorder. Interpreter mix-ins are applied to the base class
Visitwhich implements the visitor pattern and provides tracing. -
Ⓒ Type Checkers visit, annotate, and modify trees in place prior to interpretation or code generation. Type checker mix-ins are applied to the base class
Checkwhich extendsVisitand implements convenience methods. -
Ⓖ Code generators visit trees, perhaps modified by type checking. Code generators use a stack machine generator ultimately based on
Machine10to generate code and create a stack machine executable. Code generator mix-ins are applied to the base classCodewhich extendsVisit, implements convenience methods, and by default importsMachine10.
Visiting names requires a symbol table which is supported by the
Symbols mix-in
and forwarded from one visitor to the next.
The following table links visitor mix-ins to the examples which use them, lists their tree nodes and links them to the visitor methods and from there to the source code, and specifies the results.