University of Toronto
| CSC467F Compilers and Interpreters |
Fall 2005 |
Output Format for Abstract Syntax Tree
The representation of the abstract syntax tree will have the following
format:
Name (optional description)
Argument 1
Argument 2
Subargument 2,1
Subargument 2,2
Argument 3
...
where Name corresponds to the LHS of a grammar rule (a node in the
AST), the optional description contains some (usually semantic) information
about Name contained between round brackets '(' and ')', and
Argument 1, Argument 2, etc. are symbols on the RHS of the
rule (children of the node) which have non-trivial content. Descent through the
tree is represented by indentation (exactly 1 tab per level), and ascent
by removal of indentation.
The grammar productions which will be in the representation are given
below. You can use these as an indication of what kind of data structure
the nodes of your tree will be made of, but they are not meant to be any
restriction on your implementation of the actual AST.
Notes on the representation:
- Single or double asterisks '*' denote that the following or contained
text is commentary on the output format, rather than part of it.
- Text in typewriter font will denote specific
formatting/wording which should be followed verbatim.
- Text in italics will denote general descriptions of
arguments, instructions as to when arguments apply, or the semantic
value of the node rather than specific formatting e.g. (id name)
means print the name of the identifier inside the round brackets.
- Alternative values for the information in round brackets are separated
by an uppercase italic OR.
**PARTICULAR STATEMENTS**
* Declarations and Statements can both be followed
by the modifier (none), in which case no list of particular
declarations and/or statements follow.
Assignment
Variable (scalar OR array)
see Variable expression below
Expression
If Statement
Condition
Then Statements
if not = (none), particular statements
Elseif Condition
Then Statements
if not = (none), particular statements
...
Else Statements
if not = (none), particular statements
* If either the elseif or else part is missing it should
be omitted; (none) refers to the situation when the
elseif condition is present but there are no actual statements
following the then keyword.
While Statement
Condition
Statements
if not = (none), particular statements
Return Statement
Expression
if not = (none), particular expression
Procedure Statement
Identifier (id name)
Arguments
if not = (none), particular expressions
**PARTICULAR EXPRESSIONS**
Integer Constant (int value)
Boolean Constant (true OR false)
Variable (scalar OR array)
Identifier (id name)
Expression (only if Variable = (array))
Function Call
Identifier (id name)
Arguments
if not = (none), particular expressions
Binary Math (+ OR - OR * OR / OR ^)
particular subexpression
particular subexpression
Binary Logic (& OR |)
particular subexpression
particular subexpression
Comparison (= OR != OR < OR <= OR > OR >=)
particular subexpression
particular subexpression
**PARTICULAR DECLARATIONS AND PARAMETERS**
Scalar Variable
Type (integer OR boolean)
Identifier (id name)
Expression
if not = (none), particular expression
Array
Type (integer OR boolean)
Identifier (id name)
Expression
Constant
Type (integer OR boolean)
Identifier (id name)
Expression
Function
Type (integer OR boolean)
Identifier (id name)
Parameters
if not = (none), particular parameters
Scope
Procedure
Identifier (id name)
Parameters
if not = (none), particular parameters
Scope
Scalar Parameter
Type (integer OR boolean)
Identifier (id name)
Var Parameter
Type (integer OR boolean)
Identifier (id name)
Array Parameter
Type (integer OR boolean)
Identifier (id name)
**PARTICULAR OUTPUTS**
Text (text string stripped of outer quotation marks etc.)
**PARTICULAR INPUTS**
Variable (scalar OR array)
Frank Van Bussel
Last modified October, 2005