Tcl Library Source Code

Bounty program for improvements to Tcl and certain Tcl packages.

[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]


grammar::me::tcl - Virtual machine implementation I for parsing token streams

Table Of Contents


package require Tcl 8.4
package require grammar::me::tcl ?0.1?

::grammar::me::tcl cmd ...
::grammar::me::tcl init nextcmd ?tokmap?
::grammar::me::tcl lc location
::grammar::me::tcl tok from ?to?
::grammar::me::tcl tokens
::grammar::me::tcl sv
::grammar::me::tcl ast
::grammar::me::tcl astall
::grammar::me::tcl ctok
::grammar::me::tcl nc
::grammar::me::tcl next
::grammar::me::tcl ord
::grammar::me::tcl::ict_advance message
::grammar::me::tcl::ict_match_token tok message
::grammar::me::tcl::ict_match_tokrange tokbegin tokend message
::grammar::me::tcl::ict_match_tokclass code message
::grammar::me::tcl::inc_restore nt
::grammar::me::tcl::inc_save nt startlocation
::grammar::me::tcl::icl_rewind oldlocation
::grammar::me::tcl::ier_nonterminal message location
::grammar::me::tcl::ier_merge olderror
::grammar::me::tcl::isv_nonterminal_leaf nt startlocation
::grammar::me::tcl::isv_nonterminal_range nt startlocation
::grammar::me::tcl::isv_nonterminal_reduce nt startlocation ?marker?
::grammar::me::tcl::ias_pop2mark marker


This package provides an implementation of the ME virtual machine. Please go and read the document grammar::me_intro first if you do not know what a ME virtual machine is.

This implementation is tied very strongly to Tcl. All the stacks in the machine state are handled through the Tcl stack, all control flow is handled by Tcl commands, and the remaining machine instructions are directly mapped to Tcl commands. Especially the matching of nonterminal symbols is handled by Tcl procedures as well, essentially extending the machine implementation with custom instructions.

Further on the implementation handles only a single machine which is uninteruptible during execution and hardwired for pull operation. I.e. it explicitly requests each new token through a callback, pulling them into its state.

A related package is grammar::peg::interp which provides a generic interpreter / parser for parsing expression grammars (PEGs), implemented on top of this implementation of the ME virtual machine.


The commands documented in this section do not implement any of the instructions of the ME virtual machine. They provide the facilities for the initialization of the machine and the retrieval of important information.


Please go and read the document grammar::me_vm first for a specification of the basic ME virtual machine and its state.

This implementation manages the state described in that document, except for the stacks minus the AST stack. In other words, location stack, error stack, return stack, and ast marker stack are implicitly managed through standard Tcl scoping, i.e. Tcl variables in procedures, outside of this implementation.


Please go and read the document grammar::me_vm first for a specification of the basic ME virtual machine and its instruction set.

This implementation maps all instructions to Tcl commands in the namespace "::grammar::me::tcl", except for the stack related commands, nonterminal symbols and control flow. Here we simply list the commands and explain the differences to the specified instructions, if there are any. For their semantics see the aforementioned specification. The machine commands are not reachable through the ensemble command ::grammar::me::tcl.

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. 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 output 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.


grammar, parsing, virtual machine


Grammars and finite automata


Copyright © 2005 Andreas Kupries