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.
lowry@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.
leblanc@rochester.UUCP (Tom LeBlanc) (08/29/84)
From: Tom LeBlanc <leblanc>
We're running some statistical tests on LL(1) grammars and would like
to have some additional data points. We would like to receive any
LL(1) grammars you might have available. C, Ada, and Modula-2 would
be especially useful. The format is not important as long as it is
machine readable. Thank you.
Tom LeBlanc
{seismo,allegra}!rochester!leblanc
leblanc@rochester