Re: Recursive Descent Parser

Fred J. Scipione (fjscipio@rochester.rr.com) wrote:


: What about a semi-automated approach, such as using the RDP
: package by Adrian Johnstone?


Well, thanks for the advert...


My 5 euro-cents worth:


I started writing parsers as a grad student after reading Chapter 5 of
Algorithms+Data Structures = Programs, which I still think is the most
concentrated dose of practical compiler-writing advice ever
published. I starting writing RDP whilst stuck at Madrid Airport with
a friend who wanted me to explain grammars to him. Later I got a tame
mathematician to break RDP for me, and boy did it break. Even today,
six versions later, there are still some subtle nested EBNF constructs
which are quietly accepted by RDP even though they are not strictly
LL(1).


Nowadays we research generalised parsing and backtrack parsers,
amongst other things, and the number one lesson that I have learnt is
that _everything_ is more subtle than it looks. Parser generators that
I have worked with (including my own) often have pathological problems
arising from incomplete understanding of the theory of context free
grammars on the part of the authors. This is discouraging, but it is
also a warning to hand coders... If people that write parser
generators (who are, after all, steeped in parsing and parsing
algorithms) can screw up then neophytes beware. (Of course, the
alternative hypothesis is that people who write parser generators are
insufficiently bright, and should get a life.)


Writing parsers by hand is excellent for educational purposes but
highly dubious for production purposes. It is delightfully easy to
write recursive descent parsers that do what you have thought of. It
is harder than you might think to make sure that they don't do things
that you haven't thought of...


So, if you are not time-bound I would suggest writing a simple parser
for a small language by hand, then use a tool like PCCTS (ANTLR) or
RDP to do the same job by machine, and then get on with your real
project using a tool. After all, parsing is the least of your
worries. Making sure the translated code is plausible is still pretty
much black art, after all.


                                                                  Adrian


--
Dr Adrian Johnstone, Senior Lecturer in Computing, Computer Science Dep,
Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.
Email a.johnstone@rhbnc.ac.uk Tel:+44(0)1784 443425 Fax:+44(0)1784 439786

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