Re: Algol 68

In article <648@ima.ISC.COM> steven@cwi.nl (Steven Pemberton) writes:
>[...]
>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.


Two-level grammars have the same problem that attribute grammars do -
they are based on the belief that the world is linear strings of tokens.
Sooner or later, simple grammars don't work, so people have introduced
some pretty bizarre schemes to patch things up. (My first response to
attribute grammars was the word "kludge".) The schemes inevitably go all
the way to Turing equivalence, which should be a warning signal that
you're no longer dealing with strings of tokens, except in a purely
formal sense, and that other general computational mechanisms are worth
thinking about (recursive functions, logic, term rewriting, etc).


Of course, the fact that I've been hacking Lisp for the past five years
has nothing to do with this view of grammars. :-)


stan shebs
shebs@cs.utah.edu
--

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