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!


Au contraire, the context free grammar for Algol 68 is infinite. It is also
not LR(k) for any k. But that doesn't matter, you see, if you do parsing in
two passes: one that matches parentheses and a second, traditional parse.


Nonetheless, the portion of the grammar solely related to syntax (as that
term is commonly used) is quite small; much smaller than Ada, PL/I or
Fortran 8x.


A few things in Algol 68 require some invention to parse. The compiler
efforts based on formal methods (and there were a lot) generally failed.
Both of the commercially-available compilers use multipass recursive
descent parsers.


Steve Pemberton is quite right in bemoaning the unnecessary maligning both
Algol 68 and W-grammars have received over the years. It seems that the
world of computing science professors was ready for Pascal but not Algol 68.
It was just too much work. Having such outspoken enemies as Wirth,
Dijkstra and Hoare didn't help either.


To respond to John's question about mechanically parsing a W-grammar, some
work was done on this topic, but it quickly proved infeasible for all but
the most trivial cases. The problem is, the only time you use a W-grammar
is when you want to embed semantic information in the grammar (or when you
are lazy; they are easy to write). But the way this is done is based on
a Turing-machine-like model of computation which, while bounded in its
execution time, usually has some horrible running order (like exponential
in the number of nonterminals).


W-grammars are extraordinarily powerful descriptive tools (used with some
care), but automating them is out of the question.


As a reference on W-grammars, nothing can compare with the delightful book
"Grammars for Programming Languages" by Cleaveland and Uzgalis, published
(for a while) by Elsevier. Unfortunately, this book is out of print. A
good library might have it.
--
Chris Thomson, Myrias Research Corporation alberta!myrias!cmt
200 10328 81 Ave, Edmonton Alberta, Canada 403-432-1616
--

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