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
|
[comment {-*- tcl -*- doctools manpage}]
[manpage_begin grammar::me_intro n 0.1]
[copyright {2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>}]
[moddesc {Grammar operations and usage}]
[titledesc {Introduction to virtual machines for parsing token streams}]
[description]
[keywords {virtual machine}]
[keywords {push down automaton}]
[keywords matching parsing transducer grammar expression]
[keywords {context-free languages} CFL {context-free grammar} CFG]
[keywords {top-down parsing languages} TPDL {parsing expression grammar} PEG]
[keywords {recursive descent} LL(k)]
This document is an introduction to and overview of the basic
facilities for the parsing and/or matching of [term token]
streams. One possibility often used for the token domain are
characters.
[para]
The packages themselves all provide variants of one
[term {virtual machine}], called a [term {match engine}] (short
[term ME]), which has all the facilities needed for the matching and
parsing of a stream, and which are either controlled directly, or are
customized with a match program. The virtual machine is basically a
pushdown automaton, with additional elements for backtracking and/or
handling of semantic data and construction of abstract syntax trees
([term AST]).
[para]
Because of the high degree of similarity in the actual implementations
of the aforementioned virtual machine and the data structures they
receive and generate these common parts are specified in a separate
document which will be referenced by the documentation for packages
actually implementing it.
[para]
The relevant documents are:
[para]
[list_begin definitions]
[def [package grammar::me_vm]]
Virtual machine specification.
[def [package grammar::me_ast]]
Specification of various representations used for abstract syntax
trees.
[def [package grammar::me::util]]
Utility commands.
[def [package grammar::me::tcl]]
Singleton ME virtual machine implementation tied to Tcl for control
flow and stacks. Hardwired for pull operation. Uninteruptible during
processing.
[def [package grammar::me::cpu]]
Object-based ME virtual machine implementation with explicit control
flow, and stacks, using bytecodes. Suspend/Resumable. Push/pull
operation.
[def [package grammar::me::cpu::core]]
Core functionality for state manipulation and stepping used in the
bytecode based implementation of ME virtual machines.
[list_end]
[para]
[section {BUGS, IDEAS, FEEDBACK}]
This document, and the package it describes, will undoubtedly contain
bugs and other problems.
Please report such in the category [emph grammar_me] of the
[uri {http://sourceforge.net/tracker/?group_id=12883} {Tcllib SF Trackers}].
Please also report any ideas for enhancements you may have for either
package and/or documentation.
[manpage_end]
|
