Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site edison.UUCP
Path: utzoo!linus!decvax!mcnc!ncsu!uvacs!edison!dca
From: dca@edison.UUCP (David C. Albrecht)
Newsgroups: net.micro.amiga
Subject: Re: Re: Recursive descent compilers (from Re: Amiga OS)
Message-ID: <654@edison.UUCP>
Date: Tue, 11-Feb-86 08:40:33 EST
Article-I.D.: edison.654
Posted: Tue Feb 11 08:40:33 1986
Date-Received: Thu, 13-Feb-86 19:51:45 EST
References: <256@sdcc7.UUCP>
Organization: General Electric Company, Charlottesville, VA
Lines: 43

> > 
> > 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