1grammar::me_ast(n) Grammar operations and usage grammar::me_ast(n)
2______________________________________________________________________________
6
8 grammar::me_ast - Various representations of ASTs
9
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 ASTs and all the representations we specify distinguish between two
17 types of nodes, namely:
18 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 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 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 The root of an AS tree can be either a terminal or nonterminal node.
37
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 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
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
55 described by that package, and may support more.
56 Because of this the remainder of the specifications is written using
58 the terms of struct::tree.
59 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 type The type of the AST node. The recognized values are terminal and
65 nonterminal.
66 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 detail This attribute is present only for nonterminal nodes. It con‐
72 tains the name of the nonterminal symbol stored in the node.
73
75 Extended AST objects are like AST objects, with additional information.
76 detail This attribute is now present at all nodes. Its contents are
78 unchanged for nonterminal nodes. For terminal nodes it contains
79 a list describing all tokens from the input which are covered by
80 the node.
81 Each element of the list contains the token name, the associated
83 lexeme attribute, line number, and column index, in this order.
84 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
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 When proposing code changes, please provide unified diffs, i.e the out‐
99 put of diff -u.
100 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
107 AST, abstract syntax tree
108
110 Grammars and finite automata
111
113 Copyright (c) 2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>
114tcllib 0.1 grammar::me_ast(n)