Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!henry
From: henry@utzoo.UUCP (Henry Spencer)
Newsgroups: net.micro.apple
Subject: Re: C compiler
Message-ID: <3864@utzoo.UUCP>
Date: Wed, 16-May-84 17:53:56 EDT
Article-I.D.: utzoo.3864
Posted: Wed May 16 17:53:56 1984
Date-Received: Wed, 16-May-84 17:53:56 EDT
References: <288@sjuvax.UUCP>, <470@spuxll.UUCP>
Organization: U of Toronto Zoology
Lines: 41

spuxll!ech comments:

   What possible reason would you have to USE an LL(k)-based parser generator?
   (given that you can use yacc, that is.)  Yacc is based on LALR(1), see
   the paper by Aho and Johnson (Computing Surveys, 1974 -- happy 10th 
   anniversary!), and is far and away the easiest tool for HUMANS to use to
   construct parsers; by contrast, LL(1) is much more restrictive, and
   operator precedence is a REAL bear.
   
   Sorry, didn't mean to come on so strong, there.  IS there any good reason
   to use any top-down method?

Yes.  The *only* thing bottom-up has going for it (aside from being more
"fashionable") is that one can build bottom-up parser generators that
accept a very wide range of grammars and make it very easy to throw a
parser together quickly.  This is important, particularly when the parser
is secondary to some other objective, but it isn't everything.

Top-down schemes, in general, can do better error handling/repair (see
my other followup for comments on this), are easier to fit semantics
into, cope better with situations where odd parsing methods are needed
for some special component of the language, and are easier to understand
and work with.  Their one problem is that it's often harder to cast a
given language into a suitable form.  Note that there are better ways
of specifying top-down parsers than LL(1) grammars:  LL(1) grammars
are incredibly difficult to come up with, but tables for table-driven
analogs to recursive descent are very easy to write.  Even so, it's not
quite as simple as throwing together a yacc grammar.

In short, top-down methods show up much better when the problem is to
write a "production" compiler/whatever and one is willing to expend
considerable effort on getting things just right.  Bottom-up methods
work much better -- **IF** you have yacc or the equivalent already
written! -- for quick experimenting and throwing together a parser
for a user interface to some other tool.

It is unfortunate that top-down parsing methods are badly neglected
in current textbooks and courses.
-- 
				Henry Spencer @ U of Toronto Zoology
				{allegra,ihnp4,linus,decvax}!utzoo!henry