cg@myrias.UUCP (Chris Gray) (02/03/86)
(This really ought to be in mod.compilers, but for now I'll just leave it
in net.micro.amiga.)
NOW HOLD ON THERE!!!
Mike Meyer, while sort of flaming Matt Dillon's sort of flaming of the
Amiga's OS, says:
"Anybody silly enough to write a recursive descent compiler..."
Mike: have you ever written a recursive descent compiler? I've written four.
All have error handling quite superior to any UNIX C compiler I've seen.
All do quite reasonable jobs of code generation. All run quite quickly. As
an example, my Draco compiler (I invented the language, so don't worry about
what it is), is written in itself using recursive descent. The compiler is
one-pass (reads input source, does conditional compilation, writes out
optimized machine code (NOT assembler source)), and can compile at between
1000 and 1500 lines per minute on an 8 MHz 8085 using one SSDD 8" floppy disk.
The language has everything C has (except bit fields and macros) plus quite
a bit more (proper type checking, overlaying of variables, typed constants,
procedure prototypes, procedures at absolute addresses, etc.). The compiler
produces code that is within one or two percent of anything I've seen claimed
for any 8080/Z80 compiler for any language.
So - why is it that it's silly to write recursive descent compilers? I'm just
dying to know what I've been missing all these years. (By the way, I've
watched people using things like yacc for projects - great fun!! One friend
was writing an interpreted language for UNIX - he tried yacc for a while but
soon switched to recursive descent after a quick demonstration of how it
goes.)
P.S. for anyone interested - I plan to port Draco to my Amiga, but I'm working
full time, and am writing a simple game in Lattice C to learn the Amiga (and
spending some time solving Hacker) so it'll be a while.
Chris Gray {sask,ubc-vision,ihnp4}!alberta!myrias!cgdarryl@ism780c.UUCP (Darryl Richman) (02/06/86)
Recursive descent parsers have many advantages over a bottom up parser. The
best advantage is good error recovery and error messages. Recursive descent
doesn't have to be any slower than bottom up, although it isn't necessarily
faster, either. About the only real advantage to a YACC style parser is that
the language accepted is described in one place, in an abstract fashion that
can be easy to read and maintain (although this doesn't necessarily apply to
the UNIX C compiler). Of course, this is not to say that recursive descent is
hard to maintain.
--Darryl Richman, INTERACTIVE Systems Corp.
...!cca!ima!ism780!darryl
The views expressed above are my opinions only.ma168abq@sdcc7.UUCP (Daniel T. Lau) (02/07/86)
> > Recursive descent parsers have many advantages over a bottom up parser. The > best advantage is good error recovery and error messages. Recursive descent > doesn't have to be any slower than bottom up, although it isn't necessarily > faster, either. HAH!!! Why does recursive descent have better error recovery than LL(1) parsers?? It doesn't. What matters is how the programmer implements error handling/recovery. It is easier to implement error recovery using Recursive Descent parsing, but if you understand LL(1) parsing, error recovery/handling isn't so bad. Just pop off the bad symbols until you get to a known point, and try to continue parsing from there. If you can't continue.. Oh well. >About the only real advantage to a YACC style parser is that > the language accepted is described in one place, in an abstract fashion that > can be easy to read and maintain (although this doesn't necessarily apply to > the UNIX C compiler). Of course, this is not to say that recursive descent is > hard to maintain. THE REAL ADVANTAGE OF AN LL(1) PARSER IS THAT IT ACCEPTS AS INPUT A WIDER RANGE OF LANGUAGES THAN A RECURSIVE DESCENT PARSER WOULD. > The views expressed above are my opinions only. :-)) Larry D. Laus
jec@iuvax.UUCP (02/10/86)
I'm confused. I remember writing a recursive decent parser for an
LL(1) grammar. Is there some other parse method that is assumed with LL(1)
grammars that I'm not aware of? Is my memory faulty?
James E. Conley Usenet: {ihnp4,pur-ee,purdue}!iuvax!jec
I.U. Dept. of Linguistics Phone: (812) 335-8702 [Work]
401 Lindley Hall (812) 333-6702 [Home]
Bloomington, IN. 47405dca@edison.UUCP (David C. Albrecht) (02/11/86)
> > > > Recursive descent parsers have many advantages over a bottom up parser. The > > best advantage is good error recovery and error messages. Recursive descent > > doesn't have to be any slower than bottom up, although it isn't necessarily > > faster, either. > HAH!!! > Why does recursive descent have better error recovery than LL(1) > parsers?? It doesn't. What matters is how the programmer implements > error handling/recovery. It is easier to implement error recovery > using Recursive Descent parsing, but if you understand LL(1) > parsing, error recovery/handling isn't so bad. Just pop off the > bad symbols until you get to a known point, and try to continue > parsing from there. If you can't continue.. Oh well. > > >About the only real advantage to a YACC style parser is that > > the language accepted is described in one place, in an abstract fashion that > > can be easy to read and maintain (although this doesn't necessarily apply to > > the UNIX C compiler). Of course, this is not to say that recursive descent is > > hard to maintain. > THE REAL ADVANTAGE OF AN LL(1) PARSER IS THAT IT ACCEPTS AS INPUT A > WIDER RANGE OF LANGUAGES THAN A RECURSIVE DESCENT PARSER WOULD. > > The views expressed above are my opinions only. > :-)) > > Larry D. Laus First of all let's get our terminology straight. YACC and other bottom up parsers are typically LR(1) not LL(1). LL(1) is usually considered a table driven analogue of a recursive descent parser and as such typically has very similar characteristics. Usually it appears that the wider range of languages accepted by a LR parser is more a theoretical than actual advantage. Most times the recursive descent parser can accept any practical language the LR parser can. A table driven parser either LL or LR is faster than a recursive descent equivalent because the table driven parser will do state transitions in a tight loop accessing array elements rather than in chains of subroutine calls. In addition, a table driven parser typically does a better job of separating rules/actions making it easier to read, maintain, and add new rules. As far as deciding between LL and LR table driven parsers I would say go with the one you have a good parser generator for which is my primary criterion. David Albrecht
coatta@utcsri.UUCP (Terry Coatta) (02/11/86)
In article <256@sdcc7.UUCP> ma168abq@sdcc7.UUCP (Daniel T. Lau) writes: >HAH!!! >Why does recursive descent have better error recovery than LL(1) >parsers?? It doesn't. What matters is how the programmer implements >error handling/recovery. It is easier to implement error recovery >using Recursive Descent parsing, but if you understand LL(1) >THE REAL ADVANTAGE OF AN LL(1) PARSER IS THAT IT ACCEPTS AS INPUT A >WIDER RANGE OF LANGUAGES THAN A RECURSIVE DESCENT PARSER WOULD. > >Larry D. Laus It was my impression that all LL(1) grammars can be parsed by recursive descent -- have I missed something?
dean@scgvaxd.UUCP (Dean Stephan) (02/14/86)
yacc produces an LALR(1) parser (a type of LR parser), not an LL
parser. There is a difference. Also, a recursive descent parser
cannot handle all the grammers that an LR parser can. It can be
shown that an LR parser can parse any language a recursive descent
parser or an LL parser can, but the reverse is not true.
Dean.
--
Dean Stephan
Hughes Aircraft
UUCP: {allegra|ihnp4}!scgvaxd!engvax!dean
Disclimer: I disclaim everything.