Sample Parsers to

Parsing Techniques: A Practical Guide - Second Edition

Authored by Dick Grune and Ceriel J.H. Jacobs,
VU University Amsterdam, Amsterdam, The Netherlands.

Published by Springer (ISBN: 978-0-387-20248-8) 2007.

The demo/toy programs presented here were written to support the writing of the book, and are very diverse. Most of them are parsers, but some are about push-down automata or other related subjects. The parsers may be interpreters or samples of code a parser generator could generate. The code size of the programs varies between 70 and 1500 lines of code. Some just show the code from the book. All work correctly to the best of our knowledge, but none is of product-quality strength; for example, almost all support one-character non-terminal names only, and grammar and data input is ad hoc. Their sole purpose is the demonstration of the basic algorithms.

All programs are in (GNU) C, unless indicated otherwise.

Chapter 2

The uvwxy Theorem: Program for producing all original sentences from a CF grammar; download CODE, view READ_ME.
A sentence is "original" if it has a derivation in which no grammar rule is used more than once.

Chapter 3

Context-Sensitive Parsing: Woods' CS parser; download CODE, view READ_ME.

Context-Sensitive Sentence Generation: download CODE, view READ_ME.

Chapter 4

Unger Parser in Java: Interpreter for the Top-Down Unger Parser, in Java; download CODE, view READ_ME.

Unger Parser in C: Interpreter for the Top-Down Unger Parser, in C; download CODE, view READ_ME.

Unger Parser in Pascal: Interpreter for the Top-Down Unger Parser, in Pascal; download CODE, view READ_ME.
This is the simplest of the three, since Pascal features local procedures, allowing a simple implementation of exhaustive depth-first search.

Chapter 6

Irons, 1961: The first (almost-)general CF parser; download CODE, view READ_ME.

Exhaustive Recursive Descent in C: The exhaustive Recursive Descent parser from Chapter 6; download CODE, view READ_ME.

Exhaustive Recursive Descent in Pascal: The exhaustive Recursive Descent parser from Chapter 6, in Pascal; download CODE, view READ_ME.

Parsing using Prolog: Various small parsers and DCG demos in Prolog (Chapter 6); download CODE, view READ_ME.

Chapter 7

Breadth-first Bottom-up: An implementation of Hext's rewrite of Dömölki's algorithm; download CODE, view READ_ME.

Chapter 9

Precedence: A precedence parser, precedence table generator, and table interpreter; download CODE, view READ_ME.

Improved Precedence: Shyamasundar: precedence improved by FS information; download CODE, view READ_ME.

Bounded Context, BC(2,1): A BC(2,1) parse table interpreter (no computation of the table); download CODE, view READ_ME.

Bounded Right Context, BRC(2,1): The BRC(2,1) parser of Eickel, Paul, Bauer, and Samelson; download CODE, view READ_ME.

Chapter 10

Left Corner: Samples of LC(1) grammars converted to LL(1) and run on LLgen; download CODE, view READ_ME.

Partitioned LL: Sample parsing code for a PLL(1) grammar; download CODE, view READ_ME.

LR(k, inf): Implementation of Szymanski's LR(k,inf) parser; download CODE, view READ_ME.

Chapter 11

Generalized LL: Generalized LL parser from van Deudekom and Kooiman, extended to handle infinite ambiguity; download CODE, view READ_ME.

Chapter 13

Parsing as Intersection: Program for the intersection of a CF grammar and a FS automaton (Bar-Hillel et al.); download CODE, view READ_ME.

Chapter 14

Parallel parsing: Simulation of the parallel Rytter parser from Chapter 14, in Java; download CODE, view READ_ME.

Chapter 17

A Simple General Context-Free Parser: Interpreter for the Top-Down Unger Parser, in Java (same as under "Chapter 4" above); download CODE, view READ_ME.

A Problematic Parser

Improved Earley?: A tentative implementation of Snelling's algorithm; download CODE, view READ_ME.
Click here to read more.

Related Programs

Non-Deterministic Pushdown Automata: Simulations of LL and LR Non-Deterministic Pushdown Automata; download CODE, view READ_ME.

2-way Pushdown Automaton: A simple implementation of a deterministic 2-way PDA interpreter; download CODE, view READ_ME.

Back to the Parsing Techniques - Second Edition home page.