grammar::me::tcl(n) Grammar operations and usage grammar::me::tcl(n) 







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








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::iok_ok


::grammar::me::tcl::iok_fail


::grammar::me::tcl::iok_negate


::grammar::me::tcl::icl_get


::grammar::me::tcl::icl_rewind oldlocation


::grammar::me::tcl::ier_get


::grammar::me::tcl::ier_clear


::grammar::me::tcl::ier_nonterminal message
    location


::grammar::me::tcl::ier_merge olderror


::grammar::me::tcl::isv_clear


::grammar::me::tcl::isv_terminal


::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_push


::grammar::me::tcl::ias_mark


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



  
::grammar::me::tcl cmd ...

  
This is an ensemble command providing access to the commands listed in
      this section. See the methods themselves for detailed specifications.

  
::grammar::me::tcl init nextcmd ?tokmap?

  
This command (re)initializes the machine. It returns the empty string.
      This command has to be invoked before any other command of this package.
    
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 optional dictionary tokmap maps from tokens to
        integer numbers. If present the numbers impose an order on the tokens,
        which is subsequently used by ict_match_tokrange to determine if
        a token is in the specified range or not. If no token map is specified
        the lexicographic order of th token names will be used instead. This
        choice is especially asensible when using characters as tokens.

  

  
::grammar::me::tcl lc location

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

    
After a call of init the state used for the conversion
        is cleared, making further conversions impossible until the machine has
        read tokens again.

  

  
::grammar::me::tcl tok from ?to?

  
This command 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.
    
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. In other words, each element has the same structure as the result
        of the nextcmd callback given to
      ::grammar::me::tcl::init

    
This command places the same restrictions on its location
        arguments as ::grammar::me::tcl::lc.

  

  
::grammar::me::tcl tokens

  
This command returns the number of tokens currently known to the ME
      virtual machine.

  
::grammar::me::tcl 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.

  
::grammar::me::tcl ast

  
This method returns the abstract syntax tree currently at the top of the
      AST stack of the ME virtual machine. This is an abstract syntax tree as
      specified in the document grammar::me_ast, section AST
      VALUES.

  
::grammar::me::tcl astall

  
This method returns the whole stack of abstract syntax trees currently
      known to the ME virtual machine. Each element of the returned list is an
      abstract syntax tree as specified in the document grammar::me_ast,
      section AST VALUES. The top of the stack resides at the end of the
      list.

  
::grammar::me::tcl ctok

  
This method returns the current token considered by the ME virtual
      machine.

  
::grammar::me::tcl nc

  
This method returns the contents of the nonterminal cache as a dictionary
      mapping from "symbol,location" to match
      information.

  
::grammar::me::tcl next

  
This method returns the next token callback as specified during
      initialization of the ME virtual machine.

  
::grammar::me::tcl ord

  
This method returns a dictionary containing the tokmap specified
      during initialization of the ME virtual machine.
      ::grammar::me::tcl::ok This variable contains the current
      match status OK. It is provided as variable instead of a command
      because that makes access to this information faster, and the speed of
      access is considered very important here as this information is used
      constantly to determine the control flow.










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.



  
::grammar::me::tcl::ict_advance message

  
No changes.

  
::grammar::me::tcl::ict_match_token tok message

  
No changes.

  
::grammar::me::tcl::ict_match_tokrange tokbegin
    tokend message

  
If, and only if a token map was specified during initialization then the
      arguments are the numeric representations of the smallest and largest
      tokens in the range. Otherwise they are the relevant tokens themselves and
      lexicographic comparison is used.

  
::grammar::me::tcl::ict_match_tokclass code
    message

  
No changes.

  
::grammar::me::tcl::inc_restore nt

  
Instead of taking a branchlabel the command returns a boolean value. The
      result will be true if and only if cached information was found.
      The caller has to perform the appropriate branching.

  
::grammar::me::tcl::inc_save nt startlocation

  
The command takes the start location as additional argument, as it is
      managed on the Tcl stack, and not in the machine state.

  

  

  

  
These two instructions are not mapped to commands. They are control flow
      instructions and handled in Tcl.

  
::grammar::me::tcl::iok_ok

  
No changes.

  
::grammar::me::tcl::iok_fail

  
No changes.

  
::grammar::me::tcl::iok_negate

  
No changes.

  

  

  

  

  

  

  

  
These four instructions are not mapped to commands. They are control flow
      instructions and handled in Tcl.

  
::grammar::me::tcl::icl_get

  
This command returns the current location CL in the input. It
      replaces icl_push.

  
::grammar::me::tcl::icl_rewind oldlocation

  
The command takes the location as argument as it comes from the Tcl stack,
      not the machine state.

  

  
Not mapped, the stacks are not managed by the package.

  
::grammar::me::tcl::ier_get

  
This command returns the current error state ER. It replaces
      ier_push.

  
::grammar::me::tcl::ier_clear

  
No changes.

  
::grammar::me::tcl::ier_nonterminal message
    location

  
The command takes the location as argument as it comes from the Tcl stack,
      not the machine state.

  
::grammar::me::tcl::ier_merge olderror

  
The command takes the second error state to merge as argument as it comes
      from the Tcl stack, not the machine state.

  
::grammar::me::tcl::isv_clear

  
No changes.

  
::grammar::me::tcl::isv_terminal

  
No changes.

  
::grammar::me::tcl::isv_nonterminal_leaf nt
    startlocation

  
The command takes the start location as argument as it comes from the Tcl
      stack, not the machine state.

  
::grammar::me::tcl::isv_nonterminal_range nt
    startlocation

  
The command takes the start location as argument as it comes from the Tcl
      stack, not the machine state.

  
::grammar::me::tcl::isv_nonterminal_reduce nt
    startlocation ?marker?

  
The command takes start location and marker as argument as it comes from
      the Tcl stack, not the machine state.

  
::grammar::me::tcl::ias_push

  
No changes.

  
::grammar::me::tcl::ias_mark

  
This command returns a marker for the current state of the AST stack
      AS. The marker stack is not managed by the machine.

  
::grammar::me::tcl::ias_pop2mark marker

  
The command takes the marker as argument as it comes from the Tcl stack,
      not the machine state. It replaces ias_mpop.










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