Marpa 2.8 -- Earley's Parser as a TCL Extension
Fri, 28 Apr 1995 19:05:49 GMT

          From comp.compilers

Related articles
Marpa 2.8 -- Earley's Parser as a TCL Extension (1995-04-28)
| List of all articles for this month |

Newsgroups: comp.compilers
Organization: Compilers Central
Date: Fri, 28 Apr 1995 19:05:49 GMT

A new release of Marpa is available via ftp at Marpa is TCL
extended with an enhanced version of Earley's algorithm for general
parsing. The major change is greatly simplified specification of
the parse actions. The README follows:

language: Marpa
package: Marpa is TCL 7.3 extended with an enhanced Earley's Algorithm
version: Alpha 2.8
parts: parser-generator, examples, document
author: Jeffrey Kegler <>
location: via anonymous ftp at either
or at in the directory /pub/marpa/
legalities: freely redistributable without warranty under GNU Public
                                License Version 2

Description: Marpa is a TCL 7.3 extended with an ambiguous context-free
parser which uses Earley's algorithm. It is hacker friendly, with a
variety of handy features. It is intended for use in implementing
parsers that use the same crude but effective approaches to parsing that
humans use, whether these humans be reading natural language or computer
code. TCL code is attached to every production, explicitly or by
default, and this is used to evaluate the result of the parse. The
grammar is specified directly in BNF, extended with Kleene star
sequences. The parse logic follows directly from the BNF. It handles
ambiguous grammars, ambiguous tokens (tokens which were not positively
identified by the lexer) and allows the programmer to change the start
symbol. The input must be divided into "chunks" of tokens for best
results. There is no limit enforced on chunks, but once they get larger
than 500 tokens things slow down. There is no fixed distinction between
terminals and non-terminals, that is, a symbol can both match the input
AND be on the left hand side of a production. Multiple Marpa grammars
are allowed in a single TCL interpreter, and multiple Marpa-extended TCL
interpreters can run in a single program.

Speed is reasonable if not blinding, and Marpa is in use in some
applications. Marpa is the outcome of the Milarepa prototype which
implemented a different general parsing algorithm in Perl.

requires: TCL 7.3, GNU C compiler, GNU Make
updated: 1995/04/19

Jeffrey Kegler
Algorists, Inc.
743 East El Camino Real, #338
Sunnyvale CA 94087


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.