bionic (3) me_ast.3tcl.gz

Provided by: tcllib_1.19-dfsg-2_all bug

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 (c) 2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>