Re: Recursive Descent Parser

Chris F Clark <world!cfc@uunet.uu.net>
12 Jan 2000 03:45:10 -0500

          From comp.compilers

Related articles
Recursive Descent Parser e8rasmus@etek.chalmers.se (Rasmus Anthin) (2000-01-09)
Re: Recursive Descent Parser world!cfc@uunet.uu.net (Chris F Clark) (2000-01-12)
Re: Recursive Descent Parser biocyn@erols.com (2000-01-25)
Re: Recursive Descent Parser chstapfer@bluewin.ch (Christian Stapfer) (2000-02-10)
Re: Recursive Descent Parser rhyde@shoe-size.com (Randall Hyde) (2000-02-12)
Re: Recursive Descent Parser mklarson@gte.net (Michael Larson) (2000-02-22)
Re: Recursive Descent Parser paulyg@clara.net (2000-02-22)
Re: Recursive Descent Parser world!cfc@uunet.uu.net (Chris F Clark) (2000-02-22)
[3 later articles]
| List of all articles for this month |

From: Chris F Clark <world!cfc@uunet.uu.net>
Newsgroups: comp.compilers
Date: 12 Jan 2000 03:45:10 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 00-01-027
Keywords: parse, practice, comment

The problem in the parser lies in the fact that the routine that
stores the number does not put the information in the node it is
passed in, but the left child of the node.


Now, please, excuse the following tirade, but I previously contacted
this poster privately about this and now feel iritated enough to
kvetch publicly about this. The essential problem here is that the
poster is trying to write their first parser by hand. This is a
TERRIBLE idea. No one should learn how to parse by writing
hand-written parsers. (And this is not a diatribe against recursive
descent, which is a fine parsing method, only against writing such
parsers by hand.) The reason for this is the following.


It is human nature to work on a program until it appears to be correct
and then stop. As a result, the program only works for those test
cases the programmer has thought to try. Now, this technique is
adequate for very simple cases. However, it doesn't scale well. In
this case, the author remember to try both forms of recursion.
However, what if one of the forms wasn't checked? Well, then the
author would not have noticed the deficiency in the program (and some
user would have eventually found it)--if that were the case, the author
would have gone on thinking that their method was sound and applied it
to another program also--the result more than one program with the
same flaw.


Now, assume the author had used one of the fine parser generators that
builds AST trees. Since we want a recursive descent parser for
comparison and the author is a student strapped for cash, there are at
least 3 choices (ANTLR, JavaCC, and RDP). The author would have
written rules (productions) that described the recursion (with JavaCC
the rules would even look vaguely like the code the author has posted)
and the tool would have generated the code (without the bugs and also
without the toklen hack in the authors previous post etc.). More
importantly, if there were problems in the grammar (e.g. it wasn't
LL), the tool would have told the author and forced the author to fix
it. While, this might not be sufficient to guarantee a completely
bug-free specification, it would have guaranteed that the language
described met some minimal criteria (and if using a tool like ANTLR or
RDP the input to the tool would have been BNF so that others could
understand it also). Equally importantly, the program would have been
put together with supporting code (class libraries) that are well-
tested and debugged, so that problems in those areas would not be an
issue either.


So, please excuse the strident nature of this post, but this is an
issue I feel strongly about. Why? Because I spend a good portion of
my life cleaning up (or, more often, living with, as I can't fix them)
hand-written messes.


-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------
Web Site in Progress: Web Site : http://world.std.com/~compres
[I've often told people that one of the best things about mechanically
generated parsers is that you know what they won't parse as well as what
they will parse. I agree, hand written parsers generally fail to reject
lots of erroneous input. -John]


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.