grammar::me_vm(n) Grammar operations and usage grammar::me_vm(n) 







grammar::me_vm - Virtual machine for parsing token streams








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:



  

  
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.

  

  

  
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.

  

  

  
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.

  

  

  
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.

  

  

  
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.

  

  

  
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.

  

  

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

  

  

  
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.

  

  

  
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.

  

  

  
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.



  

  
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.

  

  

  
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.

  

  

  
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.

  

  

  
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:

  







  

  
A token is accepted if it is a unicode alphabetical character, or a
    digit.

  

  
A token is accepted if it is a unicode alphabetical character.

  

  
A token is accepted if it is a unicode digit character.

  

  
A token is accepted if it is a hexadecimal digit character.

  

  
A token is accepted if it is a unicode punctuation character.

  

  
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.



  

  
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.

  

  

  
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.

  

  

  
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.

  

  

  
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.



  

  
This instruction sets the match status OK to true,
      indicating a successful match.

  

  
This instruction sets the match status OK to false,
      indicating a failed match.

  

  
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.



  

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

  

  
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.

  

  
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.

  

  
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.



  

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

  

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

  

  
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.



  

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

  

  
This instruction clears the error status ER.

  

  
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.

  

  
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.



  

  
This instruction clears the semantic value SV.

  

  
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.

  

  
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.

  

  

  
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.

  

  

  
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.



  

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

  

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

  

  
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.

  

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












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.








grammar, parsing, virtual machine








Grammars and finite automata








Copyright (c) 2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>








  

    0.1
    grammar_me