grammar::me_ast(n) Grammar operations and usage grammar::me_ast(n) 







grammar::me_ast - Various representations of ASTs








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 nodes refer to the terminal symbols found in the token stream.
      They are always leaf nodes. I.e. terminal nodes never have children.

  

  
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.








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.








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:



  

  
The type of the AST node. The recognized values are terminal and
      nonterminal.

  

  
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.

  

  
This attribute is present only for nonterminal nodes. It contains the name
      of the nonterminal symbol stored in the node.










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



  

  
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.

  

  

  
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.










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.








AST, abstract syntax tree








Grammars and finite automata








Copyright (c) 2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>








  

    0.1
    grammar_me