modules/grammar_me/me_vm.man

[comment {-*- tcl -*- doctools manpage}]
[manpage_begin grammar::me_vm n 0.1]
[copyright {2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>}]
[moddesc   {Grammar operations and usage}]
[titledesc {Virtual machine for parsing token streams}]
[category  {Grammars and finite automata}]
[description]
[keywords {virtual machine}]
[keywords parsing grammar]

Please go and read the document [syscmd grammar::me_intro] first for
an overview of the various documents and their relations.

[para]

This document specifies a virtual machine for the controlled matching
and parsing of token streams, creating an

[term {abstract syntax tree}] (short [term AST]) reflecting the
structure of the input. Special machine features are the caching and
reuse of partial results, caching of the encountered input, and the
ability to backtrack in both input and AST creation.

[para]

These features make the specified virtual machine especially useful to
packrat parsers based on parsing expression grammars. It is however
not restricted to this type of parser. Normal LL and LR parsers can be
implemented with it as well.

[para]

The following sections will discuss first the abstract state kept by
ME virtual machines, and then their instruction set.


[section {MACHINE STATE}]

A ME virtual machine manages the following state:

[list_begin definitions]
[def "[term {Current token}] CT"]

The token from the input under consideration by the machine.

[para]

This information is used and modified by the instructions defined in
the section

[sectref {TERMINAL MATCHING}].


[def "[term {Current location}] CL"]

The location of the [term {current token}] in the input stream, as
offset relative to the beginning of the stream. The first token is
considered to be at offset [const 0].

[para]

This information is implicitly used and modified by the instructions
defined in the sections

[sectref {TERMINAL MATCHING}] and
[sectref {NONTERMINAL MATCHING}],

and can be directly queried and modified by the instructions defined
in section

[sectref {INPUT LOCATION HANDLING}].


[def "[term {Location stack}] LS"]

In addition to the above a stack of locations, for backtracking.
Locations can put on the stack, removed from it, and removed with
setting the current location.

[para]

This information is implicitly used and modified by the instructions
defined in the sections

[sectref {TERMINAL MATCHING}] and
[sectref {NONTERMINAL MATCHING}],

and can be directly queried and modified by the instructions defined
in section

[sectref {INPUT LOCATION HANDLING}].


[def "[term {Match status}] OK"]

A boolean value, the result of the last attempt at matching input.
It is set to [const true] if that attempt was successful, and
[const false] otherwise.

[para]

This information is influenced by the instructions defined in the
sections

[sectref {TERMINAL MATCHING}],
[sectref {NONTERMINAL MATCHING}], and
[sectref {UNCONDITIONAL MATCHING}].

It is queried by the instructions defined in the section

[sectref {CONTROL FLOW}].


[def "[term {Semantic value}] SV"]

The semantic value associated with (generated by) the last attempt at
matching input. Contains either the empty string or a node for the
abstract syntax tree constructed from the input.

[para]

This information is influenced by the instructions defined in the
sections

[sectref {SEMANTIC VALUES}], and
[sectref {AST STACK HANDLING}].


[def "[term {AST stack}] AS"]

A stack of partial abstract syntax trees constructed by the machine
during matching.

[para]

This information is influenced by the instructions defined in the
sections

[sectref {SEMANTIC VALUES}], and
[sectref {AST STACK HANDLING}].


[def "[term {AST Marker stack}] MS"]

In addition to the above a stack of stacks, for backtracking. This is
actually a stack of markers into the AST stack, thus implicitly
snapshooting the state of the AST stack at some point in time. Markers
can be put on the stack, dropped from it, and used to roll back the
AST stack to an earlier state.

[para]

This information is influenced by the instructions defined in the
sections

[sectref {SEMANTIC VALUES}], and
[sectref {AST STACK HANDLING}].


[def "[term {Error status}] ER"]

Error information associated with the last attempt at matching
input. Contains either the empty string or a list of 2 elements, a
location in the input and a list of error messages associated with
it, in this order.

[para]

[emph Note] that error information can be set even if the last attempt
at matching input was successful. For example the *-operator (matching
a sub-expression zero or more times) in a parsing expression grammar
is always successful, even if it encounters a problem further in the
input and has to backtrack. Such problems must not be forgotten when
continuing to match.

[para]

This information is queried and influenced by the instructions defined
in the sections

[sectref {TERMINAL MATCHING}],
[sectref {NONTERMINAL MATCHING}], and
[sectref {ERROR HANDLING}].


[def "[term {Error stack}] ES"]

In addition to the above a stack of error information, to allow the
merging of current and older error information when performing
backtracking in choices after an unsucessful match.

[para]

This information is queried and influenced by the instructions defined
in the sections

[sectref {TERMINAL MATCHING}],
[sectref {NONTERMINAL MATCHING}], and
[sectref {ERROR HANDLING}].


[def "[term {Return stack}] RS"]

A stack of program counter values, i.e. locations in the code
controlling the virtual machine, for the management of subroutine
calls, i.e. the matching of nonterminal symbols.

[para]

This information is queried and influenced by the instructions defined
in the section

[sectref {NONTERMINAL MATCHING}].


[def "[term {Nonterminal cache}] NC"]

A cache of machine states (A 4-tuple containing a location in the
input, match status [term OK], semantic value [term SV], and error
status [term ER]) keyed by name of nonterminal symbol and location in
the input stream.

[para]

The key location is where machine started the attempt to match the
named nonterminal symbol, and the location in the value is where
machine ended up after the attempt completed, independent of the
success of the attempt.

[para]

This status is queried and influenced by the instructions defined in
the section

[sectref {NONTERMINAL MATCHING}].

[list_end]


[section {MACHINE INSTRUCTIONS}]

With the machine state specified it is now possible to explain the
instruction set of ME virtual machines. They are grouped roughly by
the machine state they influence and/or query.


[subsection {TERMINAL MATCHING}]

First the instructions to match tokens from the input stream, and
by extension all terminal symbols.

[para]

These instructions are the only ones which may retrieve a new token
from the input stream. This is a [emph may] and not a [emph will]
because the instructions will a retrieve new token if, and only if the
current location [term CL] is at the head of the stream.

If the machine has backtracked (see [cmd icl_rewind]) the instructions
will retrieve the token to compare against from the internal cache.

[para]
[list_begin definitions]

[def "[cmd ict_advance] [arg message]"]

This instruction tries to advance to the next token in the input
stream, i.e. the one after the current location [term CL]. The
instruction will fail if, and only if the end of the input stream is
reached, i.e. if there is no next token.

[para]

The sucess/failure of the instruction is remembered in the match
status [term OK]. In the case of failure the error status [term ER] is
set to the current location and the message [arg message].

In the case of success the error status [term ER] is cleared, the new
token is made the current token [term CT], and the new location is
made the current location [term CL].

[para]

The argument [arg message] is a reference to the string to put into
the error status [term ER], if such is needed.


[def "[cmd ict_match_token] [arg tok] [arg message]"]

This instruction tests the current token [term CT] for equality
with the argument [arg tok] and records the result in the match
status [term OK]. The instruction fails if the current token is
not equal to [arg tok].

[para]

In case of failure the error status [term ER] is set to the current
location [term CL] and the message [arg message], and the
current location [term CL] is moved one token backwards.

Otherwise, i.e. upon success, the error status [term ER] is cleared
and the current location [term CL] is not touched.


[def "[cmd ict_match_tokrange] [arg tokbegin] [arg tokend] [arg message]"]

This instruction tests the current token [term CT] for being in
the range of tokens from [arg tokbegin] to [arg tokend]
(inclusive) and records the result in the match status [term OK]. The
instruction fails if the current token is not inside the range.

[para]

In case of failure the error status [term ER] is set to the current
location [term CL] and the message [arg message], and the current location
[term CL] is moved one token backwards.

Otherwise, i.e. upon success, the error status [term ER] is cleared
and the current location [term CL] is not touched.


[def "[cmd ict_match_tokclass] [arg code] [arg message]"]

This instruction tests the current token [term CT] for being a member
of the token class [arg code] and records the result in the match
status [term OK]. The instruction fails if the current token is not a
member of the specified class.

[para]

In case of failure the error status [term ER] is set to the current
location [term CL] and the message [arg message], and the
current location [term CL] is moved one token backwards.

Otherwise, i.e. upon success, the error status [term ER] is cleared
and the current location [term CL] is not touched.

[para]

Currently the following classes are legal:

[list_begin definitions]
[def alnum]
A token is accepted if it is a unicode alphabetical character, or a digit.
[def alpha]
A token is accepted if it is a unicode alphabetical character.
[def digit]
A token is accepted if it is a unicode digit character.
[def xdigit]
A token is accepted if it is a hexadecimal digit character.
[def punct]
A token is accepted if it is a unicode punctuation character.
[def space]
A token is accepted if it is a unicode space character.
[list_end]

[list_end]
[para]


[subsection {NONTERMINAL MATCHING}]

The instructions in this section handle the matching of nonterminal
symbols. They query the nonterminal cache [term NC] for saved
information, and put such information into the cache.

[para]

The usage of the cache is a performance aid for backtracking parsers,
allowing them to avoid an expensive rematch of complex nonterminal
symbols if they have been encountered before.

[para]

[list_begin definitions]

[def "[cmd inc_restore] [arg branchlabel] [arg nt]"]

This instruction checks if the nonterminal cache [term NC] contains
information about the nonterminal symbol [arg nt], at the current
location [term CL]. If that is the case the instruction will update
the machine state (current location [term CL], match status [term OK],
semantic value [term SV], and error status [term ER]) with the found
information and continue execution at the instruction refered to by
the [arg branchlabel]. The new current location [term CL] will be the
last token matched by the nonterminal symbol, i.e. belonging to it.

[para]

If no information was found the instruction will continue execution at
the next instruction.

[para]

Together with [cmd icf_ntcall] it is possible to generate code for
memoized and non-memoized matching of nonterminal symbols, either as
subroutine calls, or inlined in the caller.


[def "[cmd inc_save] [arg nt]"]

This instruction saves the current state of the machine (current
location [term CL], match status [term OK], semantic value [term SV],
and error status [term ER]), to the nonterminal cache [term NC]. It
will also pop an entry from the location stack [term LS] and save it
as the start location of the match.

[para]

It is expected to be called at the end of matching a nonterminal
symbol, with [arg nt] the name of the nonterminal symbol the code was
working on. This allows the instruction [cmd inc_restore] to check for
and retrieve the data, should we have to match this nonterminal symbol
at the same location again, during backtracking.


[def "[cmd icf_ntcall] [arg branchlabel]"]

This instruction invokes the code for matching the nonterminal symbol
[arg nt] as a subroutine. To this end it stores the current program
counter [term PC] on the return stack [term RS], the current location
[term CL] on the location stack [term LS], and then continues
execution at the address [arg branchlabel].

[para]

The next matching [cmd icf_ntreturn] will cause the execution to
continue at the instruction coming after the call.


[def [cmd icf_ntreturn]]

This instruction will pop an entry from the return stack [term RS],
assign it to the program counter [term PC], and then continue
execution at the new address.

[list_end]
[para]


[subsection {UNCONDITIONAL MATCHING}]

The instructions in this section are the remaining match
operators. They change the match status [term OK] directly and
unconditionally.

[list_begin definitions]

[def [cmd iok_ok]]

This instruction sets the match status [term OK] to [const true],
indicating a successful match.


[def [cmd iok_fail]]

This instruction sets the match status [term OK] to [const false],
indicating a failed match.


[def [cmd iok_negate]]

This instruction negates the match status [term OK], turning a failure
into a success and vice versa.

[list_end]
[para]


[subsection {CONTROL FLOW}]

The instructions in this section implement both conditional and
unconditional control flow. The conditional jumps query the match
status [term OK].

[list_begin definitions]

[def "[cmd icf_jalways] [arg branchlabel]"]

This instruction sets the program counter [term PC] to the address
specified by [arg branchlabel] and then continues execution from
there. This is an unconditional jump.


[def "[cmd icf_jok] [arg branchlabel]"]

This instruction sets the program counter [term PC] to the address
specified by [arg branchlabel]. This happens if, and only if the match
status [term OK] indicates a success. Otherwise it simply continues
execution at the next instruction. This is a conditional jump.


[def "[cmd icf_jfail] [arg branchlabel]"]

This instruction sets the program counter [term PC] to the address
specified by [arg branchlabel]. This happens if, and only if the match
status [term OK] indicates a failure. Otherwise it simply continues
execution at the next instruction. This is a conditional jump.


[def [cmd icf_halt]]

This instruction halts the machine and blocks any further execution.

[list_end]


[subsection {INPUT LOCATION HANDLING}]

The instructions in this section are for backtracking, they manipulate
the current location [term CL] of the machine state.

They allow a user of the machine to query and save locations in the
input, and to rewind the current location [term CL] to saved
locations, making them one of the components enabling the
implementation of backtracking parsers.

[list_begin definitions]

[def [cmd icl_push]]

This instruction pushes a copy of the current location [term CL] on
the location stack [term LS].


[def [cmd icl_rewind]]

This instruction pops an entry from the location stack [term LS] and
then moves the current location [term CL] back to this point in the
input.


[def [cmd icl_pop]]

This instruction pops an entry from the location stack [term LS] and
discards it.

[list_end]
[para]


[subsection {ERROR HANDLING}]

The instructions in this section provide read and write access to the
error status [term ER] of the machine.

[list_begin definitions]

[def [cmd ier_push]]

This instruction pushes a copy of the current error status [term ER]
on the error stack [term ES].


[def [cmd ier_clear]]

This instruction clears the error status [term ER].


[def "[cmd ier_nonterminal] [arg message]"]

This instruction checks if the error status [term ER] contains an
error whose location is just past the location found in the top entry
of the location stack [term LS].

Nothing happens if no such error is found.

Otherwise the found error is replaced by an error at the location
found on the stack, having the message [arg message].


[def [cmd ier_merge]]

This instruction pops an entry from the error stack [term ES], merges
it with the current error status [term ER] and stores the result of
the merge as the new error status [term ER].

[para]

The merge is performed as described below:

[para]

If one of the two error states is empty the other is chosen. If
neither error state is empty, and refering to different locations,
then the error state with the location further in the input is
chosen. If both error states refer to the same location their messages
are merged (with removing duplicates).

[list_end]


[subsection {SEMANTIC VALUES}]

The instructions in this section manipulate the semantic value
[term SV].

[list_begin definitions]

[def [cmd isv_clear]]

This instruction clears the semantic value [term SV].


[def [cmd isv_terminal]]

This instruction creates a terminal AST node for the current token
[term CT], makes it the semantic value [term SV], and also pushes the
node on the AST stack [term AS].


[def "[cmd isv_nonterminal_leaf] [arg nt]"]

This instruction creates a nonterminal AST node without any children
for the nonterminal [arg nt], and makes it the semantic value
[term SV].

[para]

This instruction should be executed if, and only if the match status
[term OK] indicates a success.

In the case of a failure [cmd isv_clear] should be called.


[def "[cmd isv_nonterminal_range] [arg nt]"]

This instruction creates a nonterminal AST node for the nonterminal

[arg nt], with a single terminal node as its child, and makes this AST
the semantic value [term SV]. The terminal node refers to the input
string from the location found on top of the location stack [term LS]
to the current location [term CL] (both inclusive).

[para]

This instruction should be executed if, and only if the match status
[term OK] indicates a success.

In the case of a failure [cmd isv_clear] should be called.


[def "[cmd isv_nonterminal_reduce] [arg nt]"]

This instruction creates a nonterminal AST node for the nonterminal
[arg nt] and makes it the semantic value [term SV].

[para]

All entries on the AST stack [term AS] above the marker found in the
top entry of the AST Marker stack [term MS] become children of the new
node, with the entry at the stack top becoming the rightmost child. If
the AST Marker stack [term MS] is empty the whole stack is used. The
AST marker stack [term MS] is left unchanged.

[para]

This instruction should be executed if, and only if the match status
[term OK] indicates a success.

In the case of a failure [cmd isv_clear] should be called.

[list_end]
[para]


[subsection {AST STACK HANDLING}]

The instructions in this section manipulate the AST stack [term AS],
and the AST Marker stack [term MS].

[list_begin definitions]

[def [cmd ias_push]]

This instruction pushes the semantic value [term SV] on the AST stack
[term AS].


[def [cmd ias_mark]]

This instruction pushes a marker for the current state of the AST
stack [term AS] on the AST Marker stack [term MS].


[def [cmd ias_mrewind]]

This instruction pops an entry from the AST Marker stack [term MS] and
then proceeds to pop entries from the AST stack [term AS] until the
state represented by the popped marker has been reached again.

Nothing is done if the AST stack [term AS] is already smaller than
indicated by the popped marker.


[def [cmd ias_mpop]]

This instruction pops an entry from the AST Marker stack [term MS] and
discards it.

[list_end]

[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]