1. Manuals
  2. Tumbleweed
  3. tcllib
  4. me_intro(n)

Scroll to navigation

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





NAME


grammar::me_intro - Introduction to virtual machines for parsing
    token streams






DESCRIPTION


This document is an introduction to and overview of the basic
    facilities for the parsing and/or matching of token streams. One
    possibility often used for the token domain are characters.


The packages themselves all provide variants of one virtual
    machine, called a match engine (short ME), which has all
    the facilities needed for the matching and parsing of a stream, and which
    are either controlled directly, or are customized with a match program. The
    virtual machine is basically a pushdown automaton, with additional elements
    for backtracking and/or handling of semantic data and construction of
    abstract syntax trees (AST).


Because of the high degree of similarity in the actual
    implementations of the aforementioned virtual machine and the data
    structures they receive and generate these common parts are specified in a
    separate document which will be referenced by the documentation for packages
    actually implementing it.


The relevant documents are:



  

  
Virtual machine specification.

  

  
Specification of various representations used for abstract syntax
    trees.

  

  
Utility commands.

  

  
Singleton ME virtual machine implementation tied to Tcl for control flow
      and stacks. Hardwired for pull operation. Uninteruptible during
      processing.

  

  
Object-based ME virtual machine implementation with explicit control flow,
      and stacks, using bytecodes. Suspend/Resumable. Push/pull operation.

  

  
Core functionality for state manipulation and stepping used in the
      bytecode based implementation of ME virtual machines.








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 Trackers
    [http://core.tcl.tk/tcllib/reportlist]. Please also report any ideas for
    enhancements you may have for either package and/or documentation.


When proposing code changes, please provide unified diffs,
    i.e the output of diff -u.


Note further that attachments are strongly preferred over
    inlined patches. Attachments can be made by going to the Edit form of
    the ticket immediately after its creation, and then using the left-most
    button in the secondary navigation bar.






KEYWORDS


CFG, CFL, LL(k), PEG, TPDL, context-free grammar, context-free
    languages, expression, grammar, matching, parsing, parsing expression
    grammar, push down automaton, recursive descent, top-down parsing languages,
    transducer, virtual machine






CATEGORY


Grammars and finite automata






COPYRIGHT


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








  

    0.1
    tcllib