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?

Daniel

-- 
Take these broken links,         ... apologies to Page, George, and Lang
And learn to follow them, Learn to use ext3               keyid 885b170d
And when we hear the inodes sing,              http://surreal.istic.org/
The filesystem will open up and let us in      It's like a DEATH CIRCUS!

Post a reply to this message

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

OK, thank you for filling me in.

Daniel

-- 
Take these broken links,         ... apologies to Page, George, and Lang
And learn to follow them, Learn to use ext3               keyid 885b170d
And when we hear the inodes sing,              http://surreal.istic.org/
The filesystem will open up and let us in      It's like a DEATH CIRCUS!

Post a reply to this message

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?
> 
> Daniel
> 
Remember that, when you are skilled, you write a top-down parser right 
from the BNF grammar; the technique is to write 1 procedure for each BNF 
production, so there is a 1-1 correspondence between BNF and code.

The resulting parser is, from my experiece, very easily maintanable 
without the skills you need when you use lex/yacc like tools.

Bye!!!

Alessandro Coppo

Post a reply to this message

"Daniel Hulme" <pho### [at] isticorg> 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?

There are a few reasons I can imagine:
1) Age of the code (probably the primary reason, as parser generators might
not have been as popular when DKB Trace was originally created)
2) Simplicity of the original scene description language (SDL) (i.e. no
loops, conditions, or variables)
3) Very close connection between SDL and renderer
4) Many small, compounding changes over time, favoring backwards
compatibility
5) It works; nobody's found a compelling reason to rewrite it

-Nathan

Post a reply to this message

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Nathan Kopp wrote:
> "Daniel Hulme" <pho### [at] isticorg> 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?
> 
> 
> There are a few reasons I can imagine:
> 1) Age of the code (probably the primary reason, as parser generators might
> not have been as popular when DKB Trace was originally created)
> 2) Simplicity of the original scene description language (SDL) (i.e. no
> loops, conditions, or variables)
> 3) Very close connection between SDL and renderer
> 4) Many small, compounding changes over time, favoring backwards
> compatibility
> 5) It works; nobody's found a compelling reason to rewrite it

You might add:
 6) Modularity, as most part of the SDL is only possible in some
"context" (a finish is only possible in the right block...)
 7) Easy extensibility, no need to mangle the whole lex syntax to add a
new kind of block (usually, it's a new object or a new pattern...)

The povray parser works like a XML-SAM parser, they are really a
nightmare to write within a single dispatch loop...
A DOM like parser would be interesting, but would be far more heavier.
(but that's nearly what you ask when asking a lex parser)

Moreover, before jumping on the rewrite, beware of:
 - variables identifier
 - expressions
they will already make writing the lex source 'interesting'.

Then you could add macro, include and loop support, for more fun...

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (MingW32)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFCfy0Os/YJ43cSjHIRAhUjAJ40eH5z/mBT1SPNg8XOgoNXdh5RPgCgyzfW
j9yxa/cCWvwVHVfiephLiRw=
=ThLm
-----END PGP SIGNATURE-----

Post a reply to this message

> Moreover, before jumping on the rewrite, beware of:
>  - variables identifier
>  - expressions
> they will already make writing the lex source 'interesting'.
> 
> Then you could add macro, include and loop support, for more fun...

Don't worry, that's not why I asked. No rewriting here, thank you very
much. I've had enough fun with my fur synthesis project. :-)

Daniel

-- 
Now  as he walked by the sea  of Galilee,  he saw  Simon and Andrew  his
brother casting a spam into the net:  for they were phishers.  And Jesus
said unto them, Come ye after me, and I will make you to become phishers
of men.  And  straightway  they forsook  their  nets,  and followed him.

Post a reply to this message