 |
ActiveTcl User Guide |
|
[ Main table Of Contents | Tcllib Table Of Contents | Tcllib Index ]
grammar::me_vm(n) 0.1 "Grammar operations and usage"
grammar::me_vm - Virtual machine for parsing token streams
TABLE OF
CONTENTS
DESCRIPTION
MACHINE
STATE
MACHINE
INSTRUCTIONS
TERMINAL MATCHING
NONTERMINAL MATCHING
UNCONDITIONAL MATCHING
CONTROL FLOW
INPUT LOCATION HANDLING
ERROR HANDLING
SEMANTIC VALUES
AST STACK HANDLING
KEYWORDS
COPYRIGHT
Please go and read the document grammar::me_intro first for an
overview of the various documents and their relations.
This document specifies a virtual machine for the controlled
matching and parsing of token streams, creating an abstract syntax tree (short 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.
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.
The following sections will discuss first the abstract state
kept by ME virtual machines, and then their instruction set.
A ME virtual machine manages the following state:
- Current token CT
- The token from the input under consideration by the
machine.
This information is used and modified by the instructions defined
in the section TERMINAL
MATCHING.
- Current location CL
- The location of the current token in the input stream,
as offset relative to the beginning of the stream. The first token
is considered to be at offset 0.
This information is implicitly used and modified by the
instructions defined in the sections TERMINAL MATCHING and NONTERMINAL MATCHING, and can be
directly queried and modified by the instructions defined in
section INPUT LOCATION
HANDLING.
- 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.
This information is implicitly used and modified by the
instructions defined in the sections TERMINAL MATCHING and NONTERMINAL MATCHING, and can be
directly queried and modified by the instructions defined in
section INPUT LOCATION
HANDLING.
- Match status OK
- A boolean value, the result of the last attempt at matching
input. It is set to true if that attempt was
successful, and false otherwise.
This information is influenced by the instructions defined in the
sections TERMINAL MATCHING, NONTERMINAL MATCHING, and UNCONDITIONAL MATCHING. It is queried
by the instructions defined in the section CONTROL FLOW.
- 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.
This information is influenced by the instructions defined in the
sections SEMANTIC VALUES, and AST STACK HANDLING.
- AST stack AS
- A stack of partial abstract syntax trees constructed by the
machine during matching.
This information is influenced by the instructions defined in the
sections SEMANTIC VALUES, and AST STACK HANDLING.
- 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.
This information is influenced by the instructions defined in the
sections SEMANTIC VALUES, and AST STACK HANDLING.
- 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.
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.
This information is queried and influenced by the instructions
defined in the sections TERMINAL
MATCHING, NONTERMINAL
MATCHING, and ERROR HANDLING.
- 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.
This information is queried and influenced by the instructions
defined in the sections TERMINAL
MATCHING, NONTERMINAL
MATCHING, and ERROR HANDLING.
- 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.
This information is queried and influenced by the instructions
defined in the section NONTERMINAL
MATCHING.
- Nonterminal cache NC
- A cache of machine states (A 4-tuple containing a location in
the input, match status OK, semantic value SV,
and error status ER) keyed by name of nonterminal symbol
and location in the input stream.
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.
This status is queried and influenced by the instructions defined
in the section NONTERMINAL
MATCHING.
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.
First the instructions to match tokens from the input stream,
and by extension all terminal symbols.
These instructions are the only ones which may retrieve a new
token from the input stream. This is a may and not a
will because the instructions will a retrieve new token
if, and only if the current location CL is at the head of
the stream. If the machine has backtracked (see icl_rewind) the instructions will retrieve the token to
compare against from the internal cache.
- ict_advance message
- This instruction tries to advance to the next token in the
input stream, i.e. the one after the current location 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.
The sucess/failure of the instruction is remembered in the match
status OK. In the case of failure the error status
ER is set to the current location and the message message. In the case of success the error status
ER is cleared, the new token is made the current token
CT, and the new location is made the current location
CL.
The argument message is a reference to the
string to put into the error status ER, if such is
needed.
- ict_match_token tok message
- This instruction tests the current token CT for
equality with the argument tok and records the
result in the match status OK. The instruction fails if
the current token is not equal to tok.
In case of failure the error status ER is set to the
current location CL and the message message, and the current location CL is moved
one token backwards. Otherwise, i.e. upon success, the error status
ER is cleared and the current location CL is not
touched.
- ict_match_tokrange tokbegin tokend message
- This instruction tests the current token CT for being
in the range of tokens from tokbegin to tokend (inclusive) and records the result in the
match status OK. The instruction fails if the current
token is not inside the range.
In case of failure the error status ER is set to the
current location CL and the message message, and the current location CL is moved
one token backwards. Otherwise, i.e. upon success, the error status
ER is cleared and the current location CL is not
touched.
- ict_match_tokclass code
message
- This instruction tests the current token CT for being
a member of the token class code and records the
result in the match status OK. The instruction fails if
the current token is not a member of the specified class.
In case of failure the error status ER is set to the
current location CL and the message message, and the current location CL is moved
one token backwards. Otherwise, i.e. upon success, the error status
ER is cleared and the current location CL is not
touched.
Currently the following classes are legal:
- alnum
- A token is accepted if it is a unicode alphabetical character,
or a digit.
- alpha
- A token is accepted if it is a unicode alphabetical
character.
- digit
- A token is accepted if it is a unicode digit character.
- xdigit
- A token is accepted if it is a hexadecimal digit character.
- punct
- A token is accepted if it is a unicode punctuation
character.
- space
- A token is accepted if it is a unicode space character.
The instructions in this section handle the matching of
nonterminal symbols. They query the nonterminal cache NC
for saved information, and put such information into the cache.
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.
- inc_restore branchlabel
nt
- This instruction checks if the nonterminal cache NC
contains information about the nonterminal symbol nt, at the current location CL. If that is the
case the instruction will update the machine state (current
location CL, match status OK, semantic value
SV, and error status ER) with the found
information and continue execution at the instruction refered to by
the branchlabel. The new current location
CL will be the last token matched by the nonterminal
symbol, i.e. belonging to it.
If no information was found the instruction will continue
execution at the next instruction.
Together with 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.
- inc_save nt
- This instruction saves the current state of the machine
(current location CL, match status OK, semantic
value SV, and error status ER), to the
nonterminal cache NC. It will also pop an entry from the
location stack LS and save it as the start location of the
match.
It is expected to be called at the end of matching a nonterminal
symbol, with nt the name of the nonterminal
symbol the code was working on. This allows the instruction inc_restore to check for and retrieve the data,
should we have to match this nonterminal symbol at the same
location again, during backtracking.
- icf_ntcall branchlabel
- This instruction invokes the code for matching the nonterminal
symbol nt as a subroutine. To this end it stores
the current program counter PC on the return stack
RS, the current location CL on the location stack
LS, and then continues execution at the address branchlabel.
The next matching icf_ntreturn will cause the
execution to continue at the instruction coming after the call.
- icf_ntreturn
- This instruction will pop an entry from the return stack
RS, assign it to the program counter PC, and then
continue execution at the new address.
The instructions in this section are the remaining match
operators. They change the match status OK directly and
unconditionally.
- iok_ok
- This instruction sets the match status OK to
true, indicating a successful match.
- iok_fail
- This instruction sets the match status OK to
false, indicating a failed match.
- iok_negate
- This instruction negates the match status OK, turning
a failure into a success and vice versa.
The instructions in this section implement both conditional and
unconditional control flow. The conditional jumps query the match
status OK.
- icf_jalways branchlabel
- This instruction sets the program counter PC to the
address specified by branchlabel and then
continues execution from there. This is an unconditional jump.
- icf_jok branchlabel
- This instruction sets the program counter PC to the
address specified by branchlabel. This happens
if, and only if the match status OK indicates a success.
Otherwise it simply continues execution at the next instruction.
This is a conditional jump.
- icf_jfail branchlabel
- This instruction sets the program counter PC to the
address specified by branchlabel. This happens
if, and only if the match status OK indicates a failure.
Otherwise it simply continues execution at the next instruction.
This is a conditional jump.
- icf_halt
- This instruction halts the machine and blocks any further
execution.
The instructions in this section are for backtracking, they
manipulate the current location 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 CL to saved
locations, making them one of the components enabling the
implementation of backtracking parsers.
- icl_push
- This instruction pushes a copy of the current location
CL on the location stack LS.
- icl_rewind
- This instruction pops an entry from the location stack
LS and then moves the current location CL back to
this point in the input.
- icl_pop
- This instruction pops an entry from the location stack
LS and discards it.
The instructions in this section provide read and write access
to the error status ER of the machine.
- ier_push
- This instruction pushes a copy of the current error status
ER on the error stack ES.
- ier_clear
- This instruction clears the error status ER.
- ier_nonterminal message
- This instruction checks if the error status ER
contains an error whose location is just past the location found in
the top entry of the location stack 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 message.
- ier_merge
- This instruction pops an entry from the error stack
ES, merges it with the current error status ER
and stores the result of the merge as the new error status
ER.
The merge is performed as described below:
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).
The instructions in this section manipulate the semantic value
SV.
- isv_clear
- This instruction clears the semantic value SV.
- isv_terminal
- This instruction creates a terminal AST node for the current
token CT, makes it the semantic value SV, and
also pushes the node on the AST stack AS.
- isv_nonterminal_leaf nt
- This instruction creates a nonterminal AST node without any
children for the nonterminal nt, and makes it
the semantic value SV.
This instruction should be executed if, and only if the match
status OK indicates a success. In the case of a failure isv_clear should be called.
- isv_nonterminal_range nt
- This instruction creates a nonterminal AST node for the
nonterminal nt, with a single terminal node as
its child, and makes this AST the semantic value SV. The
terminal node refers to the input string from the location found on
top of the location stack LS to the current location
CL (both inclusive).
This instruction should be executed if, and only if the match
status OK indicates a success. In the case of a failure isv_clear should be called.
- isv_nonterminal_reduce nt
- This instruction creates a nonterminal AST node for the
nonterminal nt and makes it the semantic value
SV.
All entries on the AST stack AS above the marker found in
the top entry of the AST Marker stack MS become children
of the new node, with the entry at the stack top becoming the
rightmost child. If the AST Marker stack MS is empty the
whole stack is used. The AST marker stack MS is left
unchanged.
This instruction should be executed if, and only if the match
status OK indicates a success. In the case of a failure isv_clear should be called.
The instructions in this section manipulate the AST stack
AS, and the AST Marker stack MS.
- ias_push
- This instruction pushes the semantic value SV on the
AST stack AS.
- ias_mark
- This instruction pushes a marker for the current state of the
AST stack AS on the AST Marker stack MS.
- ias_mrewind
- This instruction pops an entry from the AST Marker stack
MS and then proceeds to pop entries from the AST stack
AS until the state represented by the popped marker has
been reached again. Nothing is done if the AST stack AS is
already smaller than indicated by the popped marker.
- ias_mpop
- This instruction pops an entry from the AST Marker stack
MS and discards it.
grammar , parsing , virtual machine
Copyright © 2005 Andreas Kupries
<andreas_kupries@users.sourceforge.net>