Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!utgpu!water!watmath!clyde!ima!johnl From: johnl@ima.UUCP Newsgroups: comp.compilers Subject: Re: Algol 68 Message-ID: <656@ima.ISC.COM> Date: Sat, 15-Aug-87 02:33:53 EDT Article-I.D.: ima.656 Posted: Sat Aug 15 02:33:53 1987 Date-Received: Sun, 16-Aug-87 09:44:43 EDT Sender: johnl@ima.ISC.COM Reply-To: harvard!seismo!calgary!alberta!myrias!cmt@husc6.harvard.edu (Chris Thomson) Lines: 50 Approved: compilers@ima.UUCP In-Reply-To: USENET article <648@ima.ISC.COM> > > [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 -- Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.ARPA Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | cca}!ima Please send responses to the originator of the message -- I cannot forward mail accidentally sent back to compilers. Meta-mail to ima!compilers-request