bbanerje@sjuvax.UUCP (B. Banerjee) (05/15/84)
This is a followup to two articles actually. As this discussion is leaving the original topic (availability of a C compiler for apple) and is going into issues which are of further interest to net.lang only, I am cross posting this to that newsgroup. Anyone following up on this should remove net.micro.apple from the list of newsgroups. The two articles in question are (partially) reproduced below... >> In response to "why would anyone want to write a recursive descent >> parser" >> Okay, well gee, as i understand it, as told to me by the gentleman in >> hawaii, the ll(1) parse tables are not easy to fill in. >> I suppose you should ask Per Brinch Hansen or >> Hoare, why they recommend recursive descent for >> micro computers. >> >> It seems that the only feasible way to write a parser for >> a MICRO-COMPUTER is to use recursive descent. This saves >> the time that would be spent figuring out the parse tables >> for ll(1). Also, there are a zillion states for even a moderate >> sized language. >> Also ... >> If you have access to a parser generator such as yacc, use it and don't >> worry about what kind of parser it generates. >> >> Yacc happens to generate an LALR(1) parser. A book on my shelf claims >> that an LALR(1) parser table for Algol 60 occupies less than 3000 bytes. >> I would guess that an LL(1) parser table would be about the same size. >> >> A true recursive descent parser is just an LL(1) parser in which the >> parser table is encoded procedurally. I would expect table-driven LL(1) >> parsers to be more compact than recursive descent parsers. >> >> If you don't have access to a parser generator, use table-driven LL(1) >> or recursive descent. Just be careful as you transform the grammar into >> LL(1) form. Consult a good textbook on compiler construction such as >> Aho & Ullman or Hunter. Regarding the second article. LALR parsers are incredibly difficult to write by hand. Try and write a table for the 5 line grammar in Aho and Ullman. I don't have it handy, so I can't refer you to a page number. However, it is in the section on writing LALR grammars (what else). Now, the first article was a followup to one of mine advocating table driven LL(1) over recursive descent. The points raised (in order) are - 1. Recursive descent is easier to write than table driven LL(1) This is probably true. However LL(1) tables are by no means difficult to write. An algorithm suitable for machine encoding (very easily) can be found in the book by Rosencrantz, Lewis & Stearns. It can be done by hand quite easily. Also, with a little bit of effort, one can rewrite an LL(1) grammar as a Q grammar (Non terminals directly derive either null, or a right hand side that begins with a terminal). Finding the selection sets for Q grammars is a relatively trivial operation. 2. Recursive descent is more "naturally" suited to micro- computers. This, I don't buy. With a micro, you usually have memory constraints. Recursive descent automatically requires use of a higher level language supporting recursion. It also requires that you add in the overhead for recursion. Table driven LL(1) is likely to be *much* smaller. The driver for this is also relatively simple, and could be written in assembler (far more easily than that for a recursive descent parser). A further advantage is that changes to the grammar only require changes to the table. I submit that this is "better" (subjective) than recoding as must be done with a recursive descent parser. LL(1) parsers (in general) also have the "prefix property" of catching an error as soon as it occurs, rather than at some later stage. LALR parsers don't. An ambiguous operator precedence grammar is probably better for parsing expressions. Regards, -- Binayak Banerjee {allegra | astrovax | bpa | burdvax}!sjuvax!bbanerje P.S. Send Flames, I love mail.
rpw3@fortune.UUCP (05/16/84)
#R:sdccs7:-121900:fortune:22000002:000:1080
fortune!rpw3 May 15 17:03:00 1984
It also happens to be the case that IF the grammar is LL(1) or even
reasonably close, a recursive-descent parser is:
1. Fast
2. Easy to write, understand, and maintain
3. Easy to embed semantics (and other misc. functions) at
the right point
4. Capable of acceptable error-handling (assuming you want to
detect erros, not "fix" them)
5. It mixes well with other parsing techniques which may want to
be used in parts of the language that may not be strictly LL(1).
The BLISS family of languages/compilers all (to my knowledge) use
recursive-descent for declarations and control structures, and
operator-precedence for expressions. They are also some of the
best optimizing compilers ever built. (It's not a complete non-sequitor,
as the common sub-expression recognition was done during syntax analysis.)
See Wulf, et. al., "The Design of an Optimizing Compiler" (Addison-Wesley).
Rob Warnock
UUCP: {ihnp4,ucbvax!amd70,hpda,harpo,sri-unix,allegra}!fortune!rpw3
DDD: (415)595-8444
USPS: Fortune Systems Corp, 101 Twin Dolphin Drive, Redwood City, CA 94065rpw3@fortune.UUCP (05/16/84)
#R:sdccs7:-121900:fortune:22000003:000:1135
fortune!rpw3 May 15 17:12:00 1984
It also happens to be the case that IF the grammar is LL(1) or even
reasonably close, a recursive-descent parser is:
1. Fast
2. Easy to write, understand, and maintain
3. Easy to embed semantics (and other misc. functions) at
the right point
4. Capable of acceptable error-handling (assuming you want to
detect errors, not "fix" them)
5. It mixes well with other parsing techniques which may want to
be used in parts of the language that may not be strictly LL(1),
or where other techniques may be more convenient.
The BLISS family of languages/compilers all (to my knowledge) use
recursive-descent for declarations and control structures, and
operator-precedence for expressions. They are also some of the
best optimizing compilers ever built. (It's not a complete non-sequitor,
as the common sub-expression recognition was done during syntax analysis.)
See Wulf, et. al., "The Design of an Optimizing Compiler" (Addison-Wesley).
Rob Warnock
UUCP: {ihnp4,ucbvax!amd70,hpda,harpo,sri-unix,allegra}!fortune!rpw3
DDD: (415)595-8444
USPS: Fortune Systems Corp, 101 Twin Dolphin Drive, Redwood City, CA 94065ee163ahp@sdccs7.UUCP (GALACTUS) (05/16/84)
In response to "why would anyone want to write a recursive descent parser" Okay, well gee, as i understand it, as told to me by the gentleman in hawaii, the ll(1) parse tables are not easy to fill in. I suppose you should ask Per Brinch Hansen or Hoare, why they recommend recursive descent for micro computers. It seems that the only feasible way to write a parser for a MICRO-COMPUTER is to use recursive descent. This saves the time that would be spent figuring out the parse tables for ll(1). Also, there are a zillion states for even a moderate sized language. Nick. .
henry@utzoo.UUCP (Henry Spencer) (05/17/84)
Rob Warnock says, in part:
It also happens to be the case that IF the grammar is LL(1) or even
reasonably close, a recursive-descent parser is:
...
4. Capable of acceptable error-handling (assuming you want to
detect errors, not "fix" them)
This is actually an understatement. Error-handling is much easier in
recursive-descent/LL(1) than in LALR systems like yacc. It is possible
to build an error-handling module which fits between the parser and the
scanner which does all the work. The parser has to be specific about
what it wants -- this just means a slightly unusual-looking "scanner"
interface for the parser -- but the parser then sees a syntactically-
correct program regardless of what the user feeds in. The key feature
of top-down parsing, for this and other purposes, is that the software
"knows what it wants": it has a fairly specific idea of what sort of
input it's expecting at a given instant, and can take intelligent action
if there is a mismatch. Bottom-up methods like yacc don't give you this
sort of detailed context to work in, which is why error repair is such
a headache for them.
The above is not theory; such an error-repair system was built here at
U of T years ago for the SP/k compiler, and several similar things for
other languages have been done since. It really works well.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henrylowry@fortune.UUCP (05/24/84)
Regarding the comment that recursive desecent "automatically" requires the use of a hiagher level langauge---not true. If you manage your own stack of local variables, you can do it in assembly language. I know; I did it once. On an apple, no less.
nessus@mit-eddie.UUCP (Doug Alan) (06/06/84)
> From: henry@utzoo.UUCP > This is actually an understatement. Error-handling is much > easier in recursive-descent/LL(1) than in LALR systems like > yacc. I find this extremely hard to believe. It is amazingly easy to write a very good error recovery system for an LALR parser. In fact, I was able to write an error recovery system for an LALR Modula 2 parser in less than a day. And not only that, it worked much better than the error recovery in any other compiler I've ever seen. How much easier can you get? What makes it so easy to do good and easy error recovery systems for LALR parsers is that you have the parse stack directly available to you and you can copy it and fiddle with it until you get something that works. You can't do this with a recursive decent parser. Though, of course, there are ways of doing error recovery with a recursive decent parser, I can't imagine that any of them are easier. -- -Doug Alan mit-eddie!nessus Nessus@MIT-MC "What does 'I' mean"?