grammar::me_intro(3tcl) Grammar operations and usage grammar::me_intro(3tcl)
______________________________________________________________________________
NAME
grammar::me_intro - Introduction to virtual machines for parsing token
streams
DESCRIPTION
This document is an introduction to and overview of the basic facili-
ties for the parsing and/or matching of token streams. One possibility
often used for the token domain are characters.
The packages themselves all provide variants of one virtual machine,
called a match engine (short ME), which has all the facilities needed
for the matching and parsing of a stream, and which are either con-
trolled 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 ab-
stract syntax trees (AST).
Because of the high degree of similarity in the actual implementations
of the aforementioned virtual machine and the data structures they re-
ceive and generate these common parts are specified in a separate docu-
ment which will be referenced by the documentation for packages actu-
ally implementing it.
The relevant documents are:
grammar::me_vm
Virtual machine specification.
grammar::me_ast
Specification of various representations used for abstract syn-
tax trees.
grammar::me::util
Utility commands.
grammar::me::tcl
Singleton ME virtual machine implementation tied to Tcl for con-
trol flow and stacks. Hardwired for pull operation. Uninterupt-
ible during processing.
grammar::me::cpu
Object-based ME virtual machine implementation with explicit
control flow, and stacks, using bytecodes. Suspend/Resumable.
Push/pull operation.
grammar::me::cpu::core
Core functionality for state manipulation and stepping used in
the bytecode based implementation of ME virtual machines.
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 out-
put 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
CFG, CFL, LL(k), PEG, TPDL, context-free grammar, context-free lan-
guages, expression, grammar, matching, parsing, parsing expression
grammar, push down automaton, recursive descent, top-down parsing lan-
guages, transducer, virtual machine
CATEGORY
Grammars and finite automata
COPYRIGHT
Copyright (c) 2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>
tcllib 0.1 grammar::me_intro(3tcl)