Klaas Sikkel's home page

(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 well-defined 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 Left-Corner and Head-Corner 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 cross-fertilizing a parallel Earley parser with Tomita's graph-structured stack.
• Parsing schemata can be implemented straightforwardly by boolean circuits. This means that, in principle, parsing schemata can be coded directly into hardware.

A 19-page 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 126-94, Dipartimento di Scienze dell'Informazione, Università di Milano, pp. 21-39. (PDF)

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

K. Sikkel, A. Nijholt. Parsing of Context-Free Languages. Technical Report 96-32, 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 ...