Computer Science

Dick Grune

The first program I wrote was in 1961, in Algol 60, on an EL X1 in Utrecht, where I studied Experimental Physics. From 1968 to 1970 I worked as a systems programmer at the Technion in Haifa, working with an Elliott 503, Algol 60, assembly code and punched tape, and an IBM-360 in PL/1 and PL/360, on punched cards.

From 1970 to 1982 I worked at the Mathematisch Centrum in Amsterdam, as part of a team trying to implement an Algol68 compiler on an EL-X8. There I gained experience with a CDC-6600 and its assembly language COMPASS. Then the PDP-11 and the VAX came along and I learned Unix, C, Emacs and troff.

After my PhD with Prof A. van Wijngaarden in 1982 I moved to The Vrije Universiteit, also in Amsterdam, where I worked on Andy Tanenbaum's Amsterdam Compiler Kit, taught programming languages and compiler construction, and wrote books on these subjects before and after my retirement in 2004.

After I finished my last CS book in 2012 I took up studying Korean which rekindled my interest in languages.

C and Emacs have stayed with me up to this day, but Unix has become MSDOS+GnuWin and around 2000 I began replacing troff by LaTeX.

* Books

Modern Compiler Design, 2nd Edition (2012)
Detailed exposition of the structure of compilers and the techniques used in them, emphasizing precomputation and closure algorithms.

Parsing Techniques - A Practical Guide, Second Edition (2008)
Based on an intuitive and engineering-like understanding of the processes involved in parsing, this book supplies in-depth understanding of most parsing techniques in existence, simple (e.g. LL(1)), advanced (e.g. Generalized LR), and fringe (e.g. Intersection).

Modern Compiler Design (1st Edition, 2000, out of print)

Programming Language Essentials (1994)
The programming languages of the 1990s explained in a frame work of the imperative, object-oriented, functional, logic, and parallel paradigms.

Parsing Techniques - A Practical Guide (1st Edition, 1990, out of print)

* Project

Teckel — An Interpreter for Abstract Algorithms in LaTeX
An interpreter for non-deterministic and deterministic algorithms written in a mathematical style and expressed in LaTeX. Unfinished.

* Other Writings in Computer Science

ℒ0 = he(ℒ2 ∩ ℒ2): A Most Wonderful Theorem (2014)
Any Chomsky Type 0 language can be made by crossing out a couple of letters from the intersection of two Type 2 (context-free) languages, would you believe.

Two-way Stack Automata and Compiling (2012)
In 1967 Ginsburg, Greibach, and Harrison proposed the 2-way stack automaton as a suitable candidate for context checking and code generation in compiler construction. Some software to play with this idea can be found here, including a program for the 2-way stack machine that produces GGH's detailed example.

* Lecture on Parsing Using Push-Down Automata (2008, Draft) .
Traditionally the language to be used in parsing is specified by a CF grammar. This paper considers the situation in which the language is specified by rules for a push-down automaton.

* "Parsing -- Who Needs It?", Lecture at Markup Technologies '98 Conference, Nov 19-20, 1998, Chicago.
Parsing for html and xml, introduced to a non-compuer-science audience.

Publications
Some of my publications and reports on Computer Science.

* Other Writings on Computer Science

More than 1100 Computer Science Literature Summaries (until 2012)

* Useful Software

* Software Similarity Tester, new release, Version 3.0.4 of 2024-01-11.
Also finds similarities in texts and scripts.

* A LaTeX checker for nesting, syntax, and other problems.
Finds errors before [pdf]latex gets into problems. Very fast.

* A LaTeX error log analyser.
No more wading through depressing .log files! This program reduces the LaTeX error log to a single UNIX/C-style error message suitable for emacs, vi, etc.

* A program explaining LALR (bison) conflicts.
Feed it the .output file from bison and it will tell you what happened.

* Miscellaneous Utilities.
Mainly orientation aids: Where am I, and what was I doing here?

* Nifty Software

* A Two-Level Sentence Generator
Generates all sentences from a 2-level (VW) grammar, and so implicitly from any CF grammar. Works breadth-first, so won't miss a trick.

* A program for printing book signatures from PostScript
Takes a PostScript file representing a book, and produces two PostScript files that will print the fronts and backs of the pages of signatures, which can then be bound. Optionally does signature balancing, avoiding blank pages at the end.

* Gnomesort - The simplest sort program (4 lines in C)
Exploiting the Dutch garden gnome.

* Numerical conversion from binary to mixed base -- without division
Used in the 1960s in the Elliot 503 to convert pennies to £sd.

* Legacy Software and Manuals

* Some documentation of the early Dutch computer ZEBRA (1957)

* Some material on the Dutch computer EL-X8
A simulator in Algol 60, and mauals.

* Some Algol 68 material (from miscellaneous sources)
Reports, test sets, programs large and small, all from the 1970s.

* Concurrent Versions System CVS (original, obsolete, version)

* Magnetic Tape Handling Programs and Routines
Programs that analyzed, deciphered, and often read magnetic tapes until far in the 1990s.

[Home Page]
Computer Science / Dick Grune / dick@dickgrune.com

... and my name is not Richard ...