1grammar::me_ast(n)       Grammar operations and usage       grammar::me_ast(n)
2
3
4
5______________________________________________________________________________
6

NAME

8       grammar::me_ast - Various representations of ASTs
9

DESCRIPTION

11       This document specifies various representations for the abstract syntax
12       trees (short AST) generated by instances of ME virtual machines,  inde‐
13       pendent  of variant.  Please go and read the document grammar::me_intro
14       first if you do not know what a ME virtual machine is.
15
16       ASTs and all the representations we  specify  distinguish  between  two
17       types of nodes, namely:
18
19       Terminal
20              Terminal  nodes refer to the terminal symbols found in the token
21              stream. They are always leaf nodes. I.e.  terminal  nodes  never
22              have children.
23
24       Nonterminal
25              Nonterminal  nodes represent a nonterminal symbol of the grammar
26              used during parsing. They can occur as leaf and inner  nodes  of
27              the tree.
28
29       Both  types of nodes carry basic range information telling a user which
30       parts of the input are covered by the node by providing the location of
31       the  first  and  last tokens found within the range. Locations are pro‐
32       vided as non-negative integer offsets from the beginning of  the  token
33       stream,  with  the  first token found in the stream located at offset 0
34       (zero).
35
36       The root of an AS tree can be either a terminal or nonterminal node.
37

AST VALUES

39       This representation of ASTs is a Tcl list. The main list represents the
40       root  node of the tree, with the representations of the children nested
41       within.
42
43       Each node is represented by a single Tcl list containing three or  more
44       elements. The first element is either the empty string or the name of a
45       nonterminal symbol (which is never the empty string).  The  second  and
46       third  elements  are  then  the locations of the first and last tokens.
47       Any additional elements after the third are then the representations of
48       the children, with the leftmost child first, i.e. as the fourth element
49       of the list representing the node.
50

AST OBJECTS

52       In this representation an AST is represented by a  Tcl  object  command
53       whose  API  is  compatible  to the tree objects provided by the package
54       struct::tree. I.e it has to support at least all  of  the  methods  de‐
55       scribed by that package, and may support more.
56
57       Because  of  this  the remainder of the specifications is written using
58       the terms of struct::tree.
59
60       Each node of the AST directly maps to a node in the  tree  object.  All
61       data  beyond  the  child nodes, i.e. node type and input locations, are
62       stored in attributes of the node in the tree object. They are:
63
64       type   The type of the AST node. The recognized values are terminal and
65              nonterminal.
66
67       range  The  locations  of the first and last token of the terminal data
68              in the input covered by the node. This is a list containing  two
69              locations.
70
71       detail This  attribute  is  present only for nonterminal nodes. It con‐
72              tains the name of the nonterminal symbol stored in the node.
73

EXTENDED AST OBJECTS

75       Extended AST objects are like AST objects, with additional information.
76
77       detail This attribute is now present at all nodes. Its contents are un‐
78              changed  for nonterminal nodes. For terminal nodes it contains a
79              list describing all tokens from the input which are  covered  by
80              the node.
81
82              Each element of the list contains the token name, the associated
83              lexeme attribute, line number, and column index, in this order.
84
85       range_lc
86              This new attribute is defined for all nodes,  and  contains  the
87              locations  from  attribute range translated into line number and
88              column index. Lines are counted from 1, columns are counted from
89              0.
90

BUGS, IDEAS, FEEDBACK

92       This  document,  and the package it describes, will undoubtedly contain
93       bugs and other problems.  Please report such in the category grammar_me
94       of  the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].  Please
95       also report any ideas for enhancements you may have for either  package
96       and/or documentation.
97
98       When proposing code changes, please provide unified diffs, i.e the out‐
99       put of diff -u.
100
101       Note further that  attachments  are  strongly  preferred  over  inlined
102       patches.  Attachments  can  be  made  by  going to the Edit form of the
103       ticket immediately after its creation, and  then  using  the  left-most
104       button in the secondary navigation bar.
105

KEYWORDS

107       AST, abstract syntax tree
108

CATEGORY

110       Grammars and finite automata
111
113       Copyright (c) 2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>
114
115
116
117
118tcllib                                0.1                   grammar::me_ast(n)
Impressum