NAME¶
grammar::me_ast - Various representations of ASTs
DESCRIPTION¶
This document specifies various representations for the
abstract syntax
trees (short
AST) generated by instances of ME virtual machines,
independent of variant. Please go and read the document
grammar::me_intro first if you do not know what a ME virtual machine
is.
ASTs and all the representations we specify distinguish between two types of
nodes, namely:
- Terminal
- Terminal nodes refer to the terminal symbols found in the
token stream. They are always leaf nodes. I.e. terminal nodes never have
children.
- Nonterminal
- Nonterminal nodes represent a nonterminal symbol of the
grammar used during parsing. They can occur as leaf and inner nodes of the
tree.
Both types of nodes carry basic range information telling a user which parts of
the input are covered by the node by providing the location of the first and
last tokens found within the range. Locations are provided as non-negative
integer offsets from the beginning of the token stream, with the first token
found in the stream located at offset 0 (zero).
The root of an AS tree can be either a terminal or nonterminal node.
AST VALUES¶
This representation of ASTs is a Tcl list. The main list represents the root
node of the tree, with the representations of the children nested within.
Each node is represented by a single Tcl list containing three or more elements.
The first element is either the empty string or the name of a nonterminal
symbol (which is never the empty string). The second and third elements are
then the locations of the first and last tokens. Any additional elements after
the third are then the representations of the children, with the leftmost
child first, i.e. as the fourth element of the list representing the node.
AST OBJECTS¶
In this representation an AST is represented by a Tcl object command whose API
is compatible to the tree objects provided by the package
struct::tree.
I.e it has to support at least all of the methods described by that package,
and may support more.
Because of this the remainder of the specifications is written using the terms
of
struct::tree.
Each node of the AST directly maps to a node in the tree object. All data beyond
the child nodes, i.e. node type and input locations, are stored in attributes
of the node in the tree object. They are:
- type
- The type of the AST node. The recognized values are
terminal and nonterminal.
- range
- The locations of the first and last token of the terminal
data in the input covered by the node. This is a list containing two
locations.
- detail
- This attribute is present only for nonterminal nodes. It
contains the name of the nonterminal symbol stored in the node.
EXTENDED AST OBJECTS¶
Extended AST objects are like AST objects, with additional information.
- detail
- This attribute is now present at all nodes. Its contents
are unchanged for nonterminal nodes. For terminal nodes it contains a list
describing all tokens from the input which are covered by the node.
Each element of the list contains the token name, the associated lexeme
attribute, line number, and column index, in this order.
- range_lc
- This new attribute is defined for all nodes, and contains
the locations from attribute range translated into line number and
column index. Lines are counted from 1, columns are counted from 0.
BUGS, IDEAS, FEEDBACK¶
This document, and the package it describes, will undoubtedly contain bugs and
other problems. Please report such in the category
grammar_me of the
Tcllib SF Trackers [
http://sourceforge.net/tracker/?group_id=12883].
Please also report any ideas for enhancements you may have for either package
and/or documentation.
KEYWORDS¶
AST, abstract syntax tree
CATEGORY¶
Grammars and finite automata
COPYRIGHT¶
Copyright (c) 2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>