Papers of Low Availability 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.


Some papers referred to in the book or the complete literature references are not easily accessible; some of them can be found through this page.

* Deudekom, A. van and Kooiman, P. Top-down non-correcting error recovery in LLgen.
Technical Report IR 338, Vrije Universiteit, Faculteit Wiskunde en Informatica, Amsterdam, Oct. 1993.
(in PostScript)
First paper to report about Generalized LL (without calling it so). See Section 11.2.

* de Wilde, F.J., Error Recovery in a Natural-Language Parser.
Master Thesis, Vrije Universiteit, Faculteit Wiskunde en Informatica, Amsterdam, March 1990.
(in PostScript)
Applies Lyon's technique of keeping least-error parsings of substrings to a CYK parser.

* Snelling, Michel. General Context-Free Parsing in Time $n^2$,
in International Computing Symposium 1973, pages 19-24, Amsterdam, 1974. North-Holland.

It is extremely unlikely that the claim in the title holds, but no refutation has been published to date; in fact, the paper does not seem to be referenced anywhere. The algorithm is described in reasonable detail, but not completely. Filling in the last details allows some examples in the paper to be reproduced, but not all at the same time, it seems. Attempts at implementations can be found in this zip file. Further clarification would be most welcome.

... and Finally Resurfaced!

* L. Meertens and K. Koster, Basic English, a Generative Grammar for a Part of English,
Euratom Seminar ``Machine en Talen'' of E.W. Beth, University of Amsterdam, 1962.

First paper on two-level grammars. See Section 15.2.
It was feared that this paper was lost; however, in the autumn of 2010 it has resurfaced! Two copies are now known; one is the original manuscript (6 MB) in a copy book; the other is a photocopy of the Flexowriter printout that was handed out at the Euratom Seminar.
The instructions for the use of the two-level grammar are in Dutch; a translation is provided.

* Back to the Complete Literature References and Additional Material page.


Papers of Low Availability / Dick Grune / dick@dickgrune.com