Re: Recursive Descent Parser

Unfortunately, I seen to have started a thread that won't die
in which Mike Larson asked:


> Hmm... I am wrtting a shading language compiler for Renderman.... I
> have been having some problems with the language and putting various
> work arounds in to fix problems with yacc.... If the language is
> small enough and I am comfortable with recursive routines, should I
> try the recursive decent approach first?


This gets generally to the heart of the issue. If you are designing a
language (extension), and you find that you are having trouble getting
your parser generator be it yacc, pccts, or whatever, then the chances
are that your language design is not thought out. With hand-written
recursive descent you won't even know that you have a problem, you'll
just get a language that has hidden quirks.


However, most languages that one designs should trivially be both
LL(1) and SLR(1). It's very simple to guarantee that, simply start
each new construct with a unique keyword and then follow that with a
list of items (and if there are optional items at the end, have a
unique closing keyword). Languages which follow that simple
prescription are usually easy to parse and easy for readers to
understand since things are nicely unambiguous.


language: (decl-1 | decl-2 | ... | stmt-1 | stmt-2 | ...)* ;
decl-1: "var" id ("," id)* ":" type ";"
                                // var is unique starting keyword
                                                                  // : provides closing keyword to id list
                if-stmt: "if" cond "then" stmt ("else" stmt) "fi"
                                  // fi provides unique closing keyword to make else
// unambiguous


It's a little more subtle if you are writing a compiler for a language
whose grammar is already defined, as it may already have quirks that
you just have to implement, and then hacks to your parser generator or
using recursive descent is more defensible (in my opinion). In such
cases, asking in this forum will often get advice from people who have
solved the same problem before.


Hope this helps,
-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

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