NAME¶
grammar::me::cpu - Virtual machine implementation II for parsing token streams
SYNOPSIS¶
package require
Tcl 8.4
package require
grammar::me::cpu ?0.2?
::grammar::me::cpu meName matchcode
meName option ?
arg arg ...?
meName lc location
meName tok ?
from ?
to??
meName pc state
meName iseof state
meName at state
meName cc state
meName sv
meName ok
meName error
meName lstk state
meName astk state
meName mstk state
meName estk state
meName rstk state
meName nc state
meName ast
meName halted
meName code
meName eof
meName put tok lex line col
meName putstring string lvar cvar
meName run ?
n?
meName pull nextcmd
meName reset
meName destroy
DESCRIPTION¶
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 provides an object-based API and the machines are not truly
tied to Tcl. A C implementation of the same API is quite possible.
Internally the package actually uses the value-based machine manipulation
commands as provided by the package
grammar::me::cpu::core to perform
its duties.
API¶
CLASS API¶
The package directly provides only a single command for the construction of ME
virtual machines.
- ::grammar::me::cpu meName
matchcode
- The command creates a new ME machine object with an
associated global Tcl command whose name is meName. This command
may be used to invoke various operations on the machine. It has the
following general form:
- meName option ?arg arg ...?
- Option and the args determine the exact
behavior of the command.
The argument
matchcode contains the match instructions the machine has to
execute while parsing the input stream. Please read section
MATCH CODE
REPRESENTATION of the documentation for the package
grammar::me::cpu::core for the specification of the structure of this
value.
The
tokmap argument taken by the implementation provided by the package
grammar::me::tcl is here hidden inside of the match instructions and
therefore not needed.
OBJECT API¶
All ME virtual machine objects created by the class command specified in section
CLASS API support the methods listed below.
The machines provided by this package provide methods for operation in both
push- and pull-styles. Push-style means that tokens are pushed into the
machine state when they arrive, triggering further execution until they are
consumed. In other words, this allows the machine to be suspended and resumed
at will and an arbitrary number of times, the quasi-parallel operation of
several machines, and the operation as part of the event loop.
- meName lc location
- This method converts the location of a token given as
offset in the input stream into the associated line number and column
index. The result of the command is a 2-element list containing the two
values, in the order mentioned in the previous sentence. This allows
higher levels to convert the location information found in the error
status and the generated AST into more human readable data.
Note that the command is not able to convert locations which have
not been reached by the machine yet. In other words, if the machine has
read 7 tokens the command is able to convert the offsets 0 to
6, but nothing beyond that. This also shows that it is not possible
to convert offsets which refer to locations before the beginning of the
stream.
- meName tok ?from ?to??
- This method returns a Tcl list containing the part of the
input stream between the locations from and to (both
inclusive). If to is not specified it will default to the value of
from. If from is not specified either the whole input stream
is returned.
Each element of the returned list is a list of four elements, the token, its
associated lexeme, line number, and column index, in this order. This
command places the same restrictions on its location arguments as the
method lc.
- meName pc state
- This method takes the state value of a ME virtual machine
and returns the current value of the stored program counter.
- meName iseof state
- This method takes the state value of a ME virtual machine
and returns the current value of the stored eof flag.
- meName at state
- This method takes the state value of a ME virtual machine
and returns the current location in the input stream.
- meName cc state
- This method takes the state value of a ME virtual machine
and returns the current token.
- meName sv
- This command returns the current semantic value SV
stored in the machine. This is an abstract syntax tree as specified in the
document grammar::me_ast, section AST VALUES.
- meName ok
- This method returns the current match status
OK.
- meName error
- This method returns the current error status
ER.
- meName lstk state
- This method takes the state value of a ME virtual machine
and returns the location stack.
- meName astk state
- This method takes the state value of a ME virtual machine
and returns the AST stack.
- meName mstk state
- This method takes the state value of a ME virtual machine
and returns the AST marker stack.
- meName estk state
- This method takes the state value of a ME virtual machine
and returns the error stack.
- meName rstk state
- This method takes the state value of a ME virtual machine
and returns the subroutine return stack.
- meName nc state
- This method takes the state value of a ME virtual machine
and returns the nonterminal match cache as a dictionary.
- meName ast
- This method returns the current top entry of the AST stack
AS. This is an abstract syntax tree as specified in the document
grammar::me_ast, section AST VALUES.
- meName halted
- This method returns a boolean value telling the caller
whether the engine has halted execution or not. Halt means that no further
matching is possible, and the information retrieved via the other method
is final. Attempts to run the engine will be ignored, until a
reset is made.
- meName code
- This method returns the code information used to
construct the object. In other words, the match program executed by the
machine.
- meName eof
- This method adds an end of file marker to the end of the
input stream. This signals the machine that the current contents of the
input queue are the final parts of the input and nothing will come after.
Attempts to put more characters into the queue will fail.
- meName put tok lex line
col
- This method adds the token tok to the end of the
input stream, with associated lexeme data lex and
line/column information.
- meName putstring string lvar
cvar
- This method adds each individual character in the
string as a token to the end of the input stream, from first to
last. The lexemes will be empty and the line/col information is computed
based on the characters encountered and the data in the variables
lvar and cvar.
- meName run ?n?
- This methods causes the engine to execute match
instructions until either
- •
- n instructions have been executed, or
- •
- a halt instruction was executed, or
- •
- the input queue is empty and the code is asking for more
tokens to process.
If no limit
n was set only the last two conditions are checked for.
- meName pull nextcmd
- This method implements pull-style operation of the machine.
It causes it to execute match instructions until either a halt instruction
is reached, or the command prefix nextcmd ceases to deliver more
tokens.
The command prefix nextcmd represents the input stream of characters
and is invoked by the machine whenever the a new character from the stream
is required. The instruction for handling this is ict_advance. The
callback has to return either the empty list, or a list of 4 elements
containing the token, its lexeme attribute, and its location as line
number and column index, in this order. The empty list is the signal that
the end of the input stream has been reached. The lexeme attribute is
stored in the terminal cache, but otherwise not used by the machine.
The end of the input stream for this method does not imply that method
eof is called for the machine as a whole. By avoiding this and
still asking for an explicit call of the method it is possible to mix
push- and pull-style operation during the lifetime of the machine.
- meName reset
- This method resets the machine to its initial state,
discarding any state it may have.
- meName destroy
- This method deletes the object and releases all resurces it
claimed.
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 SF Trackers [
http://sourceforge.net/tracker/?group_id=12883].
Please also report any ideas for enhancements you may have for either package
and/or documentation.
KEYWORDS¶
grammar, parsing, virtual machine
CATEGORY¶
Grammars and finite automata
COPYRIGHT¶
Copyright (c) 2005-2006 Andreas Kupries <andreas_kupries@users.sourceforge.net>