Package: tcllib, Version: CVS HEAD
Introduction to virtual machines for parsing token streams
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 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 (AST).
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.
The relevant documents are:
http://sourceforge.net/tracker/?group_id=12883. Please also report any ideas for enhancements you may have for either package and/or documentation.
virtual machine, push down automaton, matching, parsing, transducer, grammar, expression, context-free languages, CFL, context-free grammar, CFG, top-down parsing languages, TPDL, parsing expression grammar, PEG, recursive descent, LL(k)