Daniel Hulme wrote:
> Someone has just asked me why the POV-Ray parser is written the way it
> is rather than using a standard lexer-/parser-generator. I was unable to
> give a useful answer. OOC, does anyone know, or is it just one of those
> things that made sense at the time for reasons lost in the mists of
> eternity?

Well, you have to keep in mind that parser generators are an impossible to 
maintain technology for any non-trivial language.  A shortlist of many of 
the serious problems of parser generators in production use can be found in:
<http://gcc.gnu.org/ml/gcc/2000-10/msg00573.html>
<http://gcc.gnu.org/ml/gcc/2000-10/msg00574.html>

Occasionally you will find people claiming that a parser generator produces 
a faster parser, but this is simply not true (at least today, if it ever 
was).  In fact, for any sane language -- that is any real-world and used 
language not constructed to explicitly to show the "slowness" of a 
particular parsing algorithm -- the complexity of both recursive-descent and 
shift-reduce parsing algorithms is O(n).

Of course, a poorly written recursive-descent parser will perform badly 
compared to the well-optimised output of a parser generator, but with C++ it 
is much easier to write fast, compact and efficient recursive-descent 
parsers.  And with lots of discipline, this also goes for recursive-descent 
parsers written in C, as the gcc design shows.

As such, short of the heavy use of macros (which one would avoid today), the 
POV-Ray parser is fairly easy to maintain.  However, this does *not* go for 
the preprocessor that is more or less patched into a non-existing 
intermediate level between the parser and the scanner, nor for the way 
scene-level objects are constructed directly from within the parser. 
Nevertheless, a parser generator would only have made both these problems 
worse, and certainly could not have prevented them at all.

So it is a good thing we don't use one.  Of course, it is simply a historic 
fact that POV-Ray uses a hand-written recursive-descent parser as the issues 
that have (over time) been found with parser generators were probably not 
even all foreseeable 15 years ago.

Does this imply the POV-Ray parser as it is is perfect?  By no means!!!  But 
that is another story... :-)

	Thorsten

Post a reply to this message