Incremental LR(1) Parser Construction as an Aid to Syntactical Extensibility


In 1974/75 I already wrote an SLR(1) parser generator for my diploma thesis at the Technical University of Munich. After 15 months of project work as a software engineer with Softlab AG I started in a research project at the University of Dortmund, Germany in cooperation with Kienzle. I planned to combine my work in the project with a promotion in the field of compiler construction.

After a series of preparations, among them

I wrote the Ph.D. thesis below in the the first months of 1980. The presentation was held in the last hours of my project contract at June 30th, 1980. I fulfilled the duty to deliver 150 copies of the dissertation ti the university's library by a corresponding set of microfiches (which were a lot cheaper).

Except for the members of the examination team, few people have probably read the document. Therefore I was pleased that the WWW shows a reference which states that it was one of the first attempts to incremental LR(1) parser generation.

Text Processing System

I keyed the whole text of the document (except for the graph on page 37) on a terminal, and I printed the document on a chain printer in the computer centre. Bold face, underlining and a series of mathematical symbols were produced by overprinting of two successive print lines.

To achieve this, I developed a simple form of text control language. With a PL/1 programm called ARBEIT I could transform this representation in appropriate print lines with form feed control characters.

Reconstruction - 22 years later

At that time, I stored the document in 28 files on a Siemens AMBOSS system, which was used as front-end to the BS2000 machine, on 8" floppy disks in IBM Format 2 (in EBCDIC). At the beginning of the 1990s I managed to read these floppies in a drive which was connected to an IBM compatible PC, with the aid of a converter program ptIBM which I developed and distributed at that time.

The original PL/1 program ARBEIT went lost in a heap of several thousand other programs. Therefore in June 2002 I wrote a perl program arbeit.pl,

which simulates the former behaviour. It transforms the form feed codes for overprinting in mathematical symbols, bold print and underlining, but this time t produces HTML. In addition, the program now inserts several hyperlinks (the WWW did not yet exist at that time) into the table of contents. Please use a modern browser like Mozilla in order to properly display mathematical symbols like for example the all quantor ∀ (∀).

With an appropriate makefile kann ich nun I can now reproduce the original work almost identical with the printed version:

Forschungsbericht Nr. 102, 1980

Abteilung Informatik, Universität Dortmund
Forschungsbericht Nr. 102, 1980

Last modification: 2-Oct-2002
Please direct any questions or comments to: <punctum@punctum.com>, Dr. Georg Fischer.