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

KEYWORDS

       AST, abstract syntax tree

CATEGORY

       Grammars and finite automata

COPYRIGHT

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