Tcl Library Source Code

Documentation
Login
Bounty program for improvements to Tcl and certain Tcl packages.
Tcl 2019 Conference, Houston/TX, US, Nov 4-8
Send your abstracts to [email protected]
or submit via the online form by Sep 9.


[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]

NAME

grammar::me_ast - Various representations of ASTs

Table Of Contents

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:

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:

EXTENDED AST OBJECTS

Extended AST objects are like AST objects, with additional information.

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 Trackers. Please also report any ideas for enhancements you may have for either package and/or documentation.

When proposing code changes, please provide unified diffs, i.e the output of diff -u.

Note further that attachments are strongly preferred over inlined patches. Attachments can be made by going to the Edit form of the ticket immediately after its creation, and then using the left-most button in the secondary navigation bar.

KEYWORDS

AST, abstract syntax tree

CATEGORY

Grammars and finite automata

COPYRIGHT

Copyright © 2005 Andreas Kupries