---
name: "me_intro"
section: "3tcl"
platform: "linux"
package: "tcllib"
version: "2.0+dfsg-4"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/me_intro"
---

# me\_intro(3tcl)

Introduction to virtual machines for parsing token streams

```

```

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

- **grammar::me\_vm**

  Virtual machine specification.

- **grammar::me\_ast**

  Specification of various representations used for abstract syntax trees.

- **grammar::me::util**

  Utility commands.

- **grammar::me::tcl**

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

- **grammar::me::cpu**

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

- **grammar::me::cpu::core**

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