1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383
|
'\"
'\" Generated from file 'me_ast\&.man' by tcllib/doctools with format 'nroff'
'\" Copyright (c) 2005 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>
'\"
.TH "grammar::me_ast" n 0\&.2 tcllib "Grammar operations and usage"
.\" The -*- nroff -*- definitions below are for supplemental macros used
.\" in Tcl/Tk manual entries.
.\"
.\" .AP type name in/out ?indent?
.\" Start paragraph describing an argument to a library procedure.
.\" type is type of argument (int, etc.), in/out is either "in", "out",
.\" or "in/out" to describe whether procedure reads or modifies arg,
.\" and indent is equivalent to second arg of .IP (shouldn't ever be
.\" needed; use .AS below instead)
.\"
.\" .AS ?type? ?name?
.\" Give maximum sizes of arguments for setting tab stops. Type and
.\" name are examples of largest possible arguments that will be passed
.\" to .AP later. If args are omitted, default tab stops are used.
.\"
.\" .BS
.\" Start box enclosure. From here until next .BE, everything will be
.\" enclosed in one large box.
.\"
.\" .BE
.\" End of box enclosure.
.\"
.\" .CS
.\" Begin code excerpt.
.\"
.\" .CE
.\" End code excerpt.
.\"
.\" .VS ?version? ?br?
.\" Begin vertical sidebar, for use in marking newly-changed parts
.\" of man pages. The first argument is ignored and used for recording
.\" the version when the .VS was added, so that the sidebars can be
.\" found and removed when they reach a certain age. If another argument
.\" is present, then a line break is forced before starting the sidebar.
.\"
.\" .VE
.\" End of vertical sidebar.
.\"
.\" .DS
.\" Begin an indented unfilled display.
.\"
.\" .DE
.\" End of indented unfilled display.
.\"
.\" .SO ?manpage?
.\" Start of list of standard options for a Tk widget. The manpage
.\" argument defines where to look up the standard options; if
.\" omitted, defaults to "options". The options follow on successive
.\" lines, in three columns separated by tabs.
.\"
.\" .SE
.\" End of list of standard options for a Tk widget.
.\"
.\" .OP cmdName dbName dbClass
.\" Start of description of a specific option. cmdName gives the
.\" option's name as specified in the class command, dbName gives
.\" the option's name in the option database, and dbClass gives
.\" the option's class in the option database.
.\"
.\" .UL arg1 arg2
.\" Print arg1 underlined, then print arg2 normally.
.\"
.\" .QW arg1 ?arg2?
.\" Print arg1 in quotes, then arg2 normally (for trailing punctuation).
.\"
.\" .PQ arg1 ?arg2?
.\" Print an open parenthesis, arg1 in quotes, then arg2 normally
.\" (for trailing punctuation) and then a closing parenthesis.
.\"
.\" # Set up traps and other miscellaneous stuff for Tcl/Tk man pages.
.if t .wh -1.3i ^B
.nr ^l \n(.l
.ad b
.\" # Start an argument description
.de AP
.ie !"\\$4"" .TP \\$4
.el \{\
. ie !"\\$2"" .TP \\n()Cu
. el .TP 15
.\}
.ta \\n()Au \\n()Bu
.ie !"\\$3"" \{\
\&\\$1 \\fI\\$2\\fP (\\$3)
.\".b
.\}
.el \{\
.br
.ie !"\\$2"" \{\
\&\\$1 \\fI\\$2\\fP
.\}
.el \{\
\&\\fI\\$1\\fP
.\}
.\}
..
.\" # define tabbing values for .AP
.de AS
.nr )A 10n
.if !"\\$1"" .nr )A \\w'\\$1'u+3n
.nr )B \\n()Au+15n
.\"
.if !"\\$2"" .nr )B \\w'\\$2'u+\\n()Au+3n
.nr )C \\n()Bu+\\w'(in/out)'u+2n
..
.AS Tcl_Interp Tcl_CreateInterp in/out
.\" # BS - start boxed text
.\" # ^y = starting y location
.\" # ^b = 1
.de BS
.br
.mk ^y
.nr ^b 1u
.if n .nf
.if n .ti 0
.if n \l'\\n(.lu\(ul'
.if n .fi
..
.\" # BE - end boxed text (draw box now)
.de BE
.nf
.ti 0
.mk ^t
.ie n \l'\\n(^lu\(ul'
.el \{\
.\" Draw four-sided box normally, but don't draw top of
.\" box if the box started on an earlier page.
.ie !\\n(^b-1 \{\
\h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.el \}\
\h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.\}
.fi
.br
.nr ^b 0
..
.\" # VS - start vertical sidebar
.\" # ^Y = starting y location
.\" # ^v = 1 (for troff; for nroff this doesn't matter)
.de VS
.if !"\\$2"" .br
.mk ^Y
.ie n 'mc \s12\(br\s0
.el .nr ^v 1u
..
.\" # VE - end of vertical sidebar
.de VE
.ie n 'mc
.el \{\
.ev 2
.nf
.ti 0
.mk ^t
\h'|\\n(^lu+3n'\L'|\\n(^Yu-1v\(bv'\v'\\n(^tu+1v-\\n(^Yu'\h'-|\\n(^lu+3n'
.sp -1
.fi
.ev
.\}
.nr ^v 0
..
.\" # Special macro to handle page bottom: finish off current
.\" # box/sidebar if in box/sidebar mode, then invoked standard
.\" # page bottom macro.
.de ^B
.ev 2
'ti 0
'nf
.mk ^t
.if \\n(^b \{\
.\" Draw three-sided box if this is the box's first page,
.\" draw two sides but no top otherwise.
.ie !\\n(^b-1 \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.el \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.\}
.if \\n(^v \{\
.nr ^x \\n(^tu+1v-\\n(^Yu
\kx\h'-\\nxu'\h'|\\n(^lu+3n'\ky\L'-\\n(^xu'\v'\\n(^xu'\h'|0u'\c
.\}
.bp
'fi
.ev
.if \\n(^b \{\
.mk ^y
.nr ^b 2
.\}
.if \\n(^v \{\
.mk ^Y
.\}
..
.\" # DS - begin display
.de DS
.RS
.nf
.sp
..
.\" # DE - end display
.de DE
.fi
.RE
.sp
..
.\" # SO - start of list of standard options
.de SO
'ie '\\$1'' .ds So \\fBoptions\\fR
'el .ds So \\fB\\$1\\fR
.SH "STANDARD OPTIONS"
.LP
.nf
.ta 5.5c 11c
.ft B
..
.\" # SE - end of list of standard options
.de SE
.fi
.ft R
.LP
See the \\*(So manual entry for details on the standard options.
..
.\" # OP - start of full description for a single option
.de OP
.LP
.nf
.ta 4c
Command-Line Name: \\fB\\$1\\fR
Database Name: \\fB\\$2\\fR
Database Class: \\fB\\$3\\fR
.fi
.IP
..
.\" # CS - begin code excerpt
.de CS
.RS
.nf
.ta .25i .5i .75i 1i
..
.\" # CE - end code excerpt
.de CE
.fi
.RE
..
.\" # UL - underline word
.de UL
\\$1\l'|0\(ul'\\$2
..
.\" # QW - apply quotation marks to word
.de QW
.ie '\\*(lq'"' ``\\$1''\\$2
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\$2
..
.\" # PQ - apply parens and quotation marks to word
.de PQ
.ie '\\*(lq'"' (``\\$1''\\$2)\\$3
.\"" fix emacs highlighting
.el (\\*(lq\\$1\\*(rq\\$2)\\$3
..
.\" # QR - quoted range
.de QR
.ie '\\*(lq'"' ``\\$1''\\-``\\$2''\\$3
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\-\\*(lq\\$2\\*(rq\\$3
..
.\" # MT - "empty" string
.de MT
.QW ""
..
.BS
.SH NAME
grammar::me_ast \- Various representations of ASTs
.SH DESCRIPTION
This document specifies various representations for the
\fIabstract syntax tree\fRs (short \fIAST\fR) generated by
instances of ME virtual machines, independent of variant\&.
Please go and read the document \fBgrammar::me_intro\fR first if
you do not know what a ME virtual machine is\&.
.PP
ASTs and all the representations we specify distinguish between two
types of nodes, namely:
.PP
.TP
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\&.
.TP
Nonterminal
Nonterminal nodes represent a nonterminal symbol of the grammar used
during parsing\&. They can occur as leaf and inner nodes of the
tree\&.
.PP
.PP
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)\&.
.PP
The root of an AS tree can be either a terminal or nonterminal node\&.
.SH "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\&.
.PP
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\&.
.SH "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
\fBstruct::tree\fR\&. I\&.e it has to support at least all of the
methods described by that package, and may support more\&.
.PP
Because of this the remainder of the specifications is written using
the terms of \fBstruct::tree\fR\&.
.PP
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:
.TP
type
The type of the AST node\&. The recognized values are \fBterminal\fR
and \fBnonterminal\fR\&.
.TP
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\&.
.TP
detail
This attribute is present only for nonterminal nodes\&. It contains the
name of the nonterminal symbol stored in the node\&.
.PP
.SH "EXTENDED AST OBJECTS"
Extended AST objects are like AST objects, with additional
information\&.
.TP
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\&.
.sp
Each element of the list contains the token name, the associated
lexeme attribute, line number, and column index, in this order\&.
.TP
range_lc
This new attribute is defined for all nodes, and contains the
locations from attribute \fIrange\fR translated into line number and
column index\&. Lines are counted from 1, columns are counted from 0\&.
.PP
.SH "BUGS, IDEAS, FEEDBACK"
This document, and the package it describes, will undoubtedly contain
bugs and other problems\&.
Please report such in the category \fIgrammar_me\fR of the
\fITcllib Trackers\fR [http://core\&.tcl\&.tk/tcllib/reportlist]\&.
Please also report any ideas for enhancements you may have for either
package and/or documentation\&.
.PP
When proposing code changes, please provide \fIunified diffs\fR,
i\&.e the output of \fBdiff -u\fR\&.
.PP
Note further that \fIattachments\fR are strongly preferred over
inlined patches\&. Attachments can be made by going to the \fBEdit\fR
form of the ticket immediately after its creation, and then using the
left-most button in the secondary navigation bar\&.
.SH KEYWORDS
AST, abstract syntax tree
.SH CATEGORY
Grammars and finite automata
.SH COPYRIGHT
.nf
Copyright (c) 2005 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>
.fi
|