
[//000000001]: # (grammar::me\_ast \- Grammar operations and usage)
[//000000002]: # (Generated from file 'me\_ast\.man' by tcllib/doctools with format 'markdown')
[//000000003]: # (Copyright &copy; 2005 Andreas Kupries <andreas\_kupries@users\.sourceforge\.net>)
[//000000004]: # (grammar::me\_ast\(n\) 0\.1 tcllib "Grammar operations and usage")

<hr> [ <a href="../../../../toc.md">Main Table Of Contents</a> &#124; <a
href="../../../toc.md">Table Of Contents</a> &#124; <a
href="../../../../index.md">Keyword Index</a> &#124; <a
href="../../../../toc0.md">Categories</a> &#124; <a
href="../../../../toc1.md">Modules</a> &#124; <a
href="../../../../toc2.md">Applications</a> ] <hr>

# NAME

grammar::me\_ast \- Various representations of ASTs

# <a name='toc'></a>Table Of Contents

  - [Table Of Contents](#toc)

  - [Description](#section1)

  - [AST VALUES](#section2)

  - [AST OBJECTS](#section3)

  - [EXTENDED AST OBJECTS](#section4)

  - [Bugs, Ideas, Feedback](#section5)

  - [Keywords](#keywords)

  - [Category](#category)

  - [Copyright](#copyright)

# <a name='description'></a>DESCRIPTION

This document specifies various representations for the *[abstract syntax
tree](\.\./\.\./\.\./\.\./index\.md\#abstract\_syntax\_tree)*s \(short
*[AST](\.\./\.\./\.\./\.\./index\.md\#ast)*\) generated by instances of ME virtual
machines, independent of variant\. Please go and read the document
__[grammar::me\_intro](me\_intro\.md)__ 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\.

# <a name='section2'></a>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\.

# <a name='section3'></a>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](\.\./struct/struct\_tree\.md)__\. 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](\.\./struct/struct\_tree\.md)__\.

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\.

# <a name='section4'></a>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\.

# <a name='section5'></a>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](http://core\.tcl\.tk/tcllib/reportlist)\. 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\.

# <a name='keywords'></a>KEYWORDS

[AST](\.\./\.\./\.\./\.\./index\.md\#ast), [abstract syntax
tree](\.\./\.\./\.\./\.\./index\.md\#abstract\_syntax\_tree)

# <a name='category'></a>CATEGORY

Grammars and finite automata

# <a name='copyright'></a>COPYRIGHT

Copyright &copy; 2005 Andreas Kupries <andreas\_kupries@users\.sourceforge\.net>
