johnl@ima.UUCP (04/22/87)
Are there any Algol 68 compilers out there, particularly for Un*x
environments?
Please reply by e-mail, as I don't read this newsgroup. I will send
or post a summary if people are interested.
Dale
[I know that Steve Bourne was working on one at Bell Labs a while ago, but
have never seen an actual compiler. -John]
--
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-requeststeven@cwi.nl (Steven Pemberton) (08/13/87)
> [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 -- 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
johnl@ima.UUCP (08/14/87)
Original-sender: 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 -- 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
johnl@ima.UUCP (08/15/87)
> > [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
johnl@ima.UUCP (08/20/87)
In article <652@ima.ISC.COM> Stanley Shebs writes: >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".) It has always seemed to me that attribute grammars, based as they are on the parse tree, are a step up from linear strings of tokens. My two complaints about AG are: 1) Because they generate long-distance dependencies (e.g. the type of an identifier depends on a declaration, *somewhere*) the evaluation is expensive (without optimizing tricks). 2) Attribute evaluator generators that I have seen have been too closely tied to particular languages. For instance, one that I know of generates a monolithic Pascal program. Suppose you would prefer Modula 2, in several compilation units, or Ada, or C...? Too bad. Can someone propose an alternative to attribute grammars, as a way to specify context-sensitive syntax in a form suitable for machine processing? I would be interested to know. The answer doesn't have to solve the *whole* problem of compilation; if you can bite off a substantial chunk, that's worth while. Regards, Chris -- Full-Name: Christopher J. Henrich UUCP: ...!hjuxa!petsd!cjh US Mail: MS 313; Concurrent Computer Corporation; 106 Apple St; Tinton Falls, NJ 07724 Phone: (201) 758-7288 Concurrent Computer Corporation is a Perkin-Elmer company. -- 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
johnl@ima.UUCP (08/26/87)
In article <675@ima.ISC.COM> harvard!rutgers!petsd!cjh writes: >Can someone propose an alternative to attribute grammars, as a >way to specify context-sensitive syntax in a form suitable >for machine processing? I would be interested to know. The >answer doesn't have to solve the *whole* problem of compilation; >if you can bite off a substantial chunk, that's worth while. Definite Clause Grammars, or Metamorphosis Grammars to use an earlier title, do pretty well. They are just a wrapped up form of Prolog (i.e. they have full unification). Before you say that's even worse than AGs, I've been comparing YACC/Modula runtimes with compiled Prolog times for a small compiler recently and they aren't too different. (I'm not making any claims about space! :-). For details see my thesis (I.C. 1981) or paper in Lisp&FunPL Conf 1982. Chris Moss. -- 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