1grammar::me_intro(n)     Grammar operations and usage     grammar::me_intro(n)
2
3
4
5______________________________________________________________________________
6

NAME

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

DESCRIPTION

12       This document is an introduction to and overview of the  basic  facili‐
13       ties  for the parsing and/or matching of token streams. One possibility
14       often used for the token domain are characters.
15
16       The packages themselves all provide variants of  one  virtual  machine,
17       called  a  match engine (short ME), which has all the facilities needed
18       for the matching and parsing of a stream, and  which  are  either  con‐
19       trolled  directly,  or are customized with a match program. The virtual
20       machine is basically a pushdown automaton, with additional elements for
21       backtracking  and/or  handling  of  semantic  data  and construction of
22       abstract syntax trees (AST).
23
24       Because of the high degree of similarity in the actual  implementations
25       of  the  aforementioned  virtual  machine  and the data structures they
26       receive and generate these common parts are  specified  in  a  separate
27       document  which  will  be  referenced by the documentation for packages
28       actually implementing it.
29
30       The relevant documents are:
31
32       grammar::me_vm
33              Virtual machine specification.
34
35       grammar::me_ast
36              Specification of various representations used for abstract  syn‐
37              tax trees.
38
39       grammar::me::util
40              Utility commands.
41
42       grammar::me::tcl
43              Singleton ME virtual machine implementation tied to Tcl for con‐
44              trol flow and stacks. Hardwired for pull operation.  Uninterupt‐
45              ible during processing.
46
47       grammar::me::cpu
48              Object-based  ME  virtual  machine  implementation with explicit
49              control flow, and stacks,  using  bytecodes.  Suspend/Resumable.
50              Push/pull operation.
51
52       grammar::me::cpu::core
53              Core  functionality  for state manipulation and stepping used in
54              the bytecode based implementation of ME virtual machines.
55

BUGS, IDEAS, FEEDBACK

57       This document, and the package it describes, will  undoubtedly  contain
58       bugs and other problems.  Please report such in the category grammar_me
59       of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].   Please
60       also  report any ideas for enhancements you may have for either package
61       and/or documentation.
62
63       When proposing code changes, please provide unified diffs, i.e the out‐
64       put of diff -u.
65
66       Note  further  that  attachments  are  strongly  preferred over inlined
67       patches. Attachments can be made by going  to  the  Edit  form  of  the
68       ticket  immediately  after  its  creation, and then using the left-most
69       button in the secondary navigation bar.
70

KEYWORDS

72       CFG, CFL, LL(k), PEG, TPDL,  context-free  grammar,  context-free  lan‐
73       guages,  expression,  grammar,  matching,  parsing,  parsing expression
74       grammar, push down automaton, recursive descent, top-down parsing  lan‐
75       guages, transducer, virtual machine
76

CATEGORY

78       Grammars and finite automata
79

81       Copyright (c) 2005 Andreas Kupries <andreas_kupries@users.sourceforge.net>
82
83
84
85
86tcllib                                0.1                 grammar::me_intro(n)
Impressum