Re: Algol 68

> [What I'd really like to hear is how you deal with Algol-68's two-level
> grammar without expanding it to a context free grammar the size of a
> small planet. I've heard of no work on parsing such grammars
> directly. -John]


But the context-free grammar of Algol 68 is tiny! I've always thought
that Algol 68 has been grossly misrepresented. This is probably as a
result of the formal definition of A68 which is very hard to read on
account of the new definitional mechanism they used (Two level, or van
Wijngaarden, grammars). But if you delete all the second-level stuff,
which is mostly context-conditions, you're left with a very small
grammar.


You should check out the book by Woodward and Bond (there's a new
edition recently out, but I don't know its title, but it starts with
Algol 68 if I remember rightly). The syntax of A68 takes up less than
two pages of that book, using about 15 syntax rules. Their book is
also good because it teaches you the language in about 80 pages, in a
very readable style.


While I'm defending Algol 68, I might also say that the first Algol 68
compiler I used, in 1973, ran in 36K of 24 bit words, only 4K bigger
than the Pascal compiler (actually, the Pascal compiler expanded as it
compiled, while the Algol 68 compiler stayed at that size). They used
LR(1) to parse the language.


On the subject of two-level grammars, it seems to me a pity that they
receive so little attention. They use an extremely simple mechanism,
and are as powerful as a Turing machine, so you can define the syntax,
context conditions, and semantics with the one formalism. Again I
blame the rather heavy style of the Algol 68 report for giving them a
bad name. For instance, if they'd only used ROWS-OPTION instead of
ROWSETY to indicate an optional ROWS, it would have made it much
easier reading.


There was a reasonable amount of work done on parsing two-level
grammars, mostly in Germany. I can dig out some references if anyone
is interested.


Steven Pemberton, CWI, Amsterdam; steven@cwi.nl
--

Return to the comp.compilers page.
Search the comp.compilers archives again.