Parsing Schemata
K. Sikkel.
Parsing Schemata  a framework for specification
and analysis of parsing algorithms.
Texts in Theoretical Computer Science  An EATCS Series.
ISBN 3540616500,
SpringerVerlag, Berlin / Heidelberg / New York (1997).
XVI + 365 pages, DM 68, / US$ 54.95
(Revised and updated version of my
Ph.D. Thesis,
Parsing Schemata,
Dept. of Computer Science,
University of Twente, Enschede, The Netherlands, December 1993.)
Abstract
Parsing schemata
provide a general framework for specification,
analysis and comparison of (sequential and/or parallel) parsing
algorithms.
A grammar specifies implicitly what the valid parses of a
sentence are; a parsing algorithm specifies explicitly how to
compute these.
Parsing schemata form a welldefined level of abstraction in between
grammars and parsing algorithms.
A parsing schema specifies the types of intermediate results that
can be computed by a parser, and the rules that allow to
expand a given set of such results with new results.
A parsing schema does not specify the data structures,
control structures, and (in case of parallel processing)
communication structures that are to be used by a parser.
Part I, Exposition, gives a general introduction
to the ideas that are worked out in the following parts.
Part II, Foundation, unfolds a mathematical
theory of parsing schemata.
Different kinds of relations between parsing schemata
are formally introduced and illustrated with examples drawn from
the parsing literature.
Part III, Application, discusses a series of applications
of parsing schemata.

Feature percolation in unification grammar parsing can be
described in an elegant, legible notation.

Because of the absence of algorithmic detail, parsing schemata
can be used to get a formal grip on highly complicated algorithms.
We give substance to this claim by means of a thorough
analysis of LeftCorner and HeadCorner chart parsing.

As an example of structural similarity of parsers, despite
differences in form and appearance, we show that the underlying
parsing schemata of Earley's algorithm and Tomita's algorithm
are virtually identical.
Using this structural correspondence we can obtain a novel parallel
parser by crossfertilizing a parallel Earley parser with Tomita's
graphstructured stack.

Parsing schemata can be implemented straightforwardly by
boolean circuits. This means that, in principle, parsing
schemata can be coded directly into hardware.

A 19page
extended introduction to the parsing schemata framework is
presented in

K. Sikkel.
How to compare the structure of parsing algorithms.
In: G. Pighizzini, P. San Pietro (Eds.), Proc. ASMICS
Workshop on Parsing Theory, Milano, Italy, October 1994.
Technical Report 12694,
Dipartimento di Scienze dell'Informazione,
Università di Milano, pp. 2139.
(PDF)

A more substantial introduction (40 pages) can also be found in

K. Sikkel, A. Nijholt.
Parsing of ContextFree Languages.
Technical Report 9632,
Center for Telematics and Information Technology,
University of Twente, Enschede, the Netherlands
(PDF)
Not included in the book are the
Prologue and Epilogue to my
Ph.D. Thesis (about the Maya)
 but these had nothing to do with Parsing Schemata, really ...
