Re: Ambiguous recursive-descent parsing

Chris F Clark <cfc@world.std.com>
30 Mar 2003 00:36:23 -0500

          From comp.compilers

Related articles
Ambiguous recursive-descent parsing stodghil@cs.cornell.edu (Paul Stodghill) (2003-03-24)
Re: Ambiguous recursive-descent parsing cfc@world.std.com (Chris F Clark) (2003-03-30)
Re: Ambiguous recursive-descent parsing rivers@dignus.com (Thomas David Rivers) (2003-03-30)
Re: Ambiguous recursive-descent parsing slk14@earthlink.net (SLK Parsers) (2003-03-30)
Re: Ambiguous recursive-descent parsing oliver@zeigermann.de (Oliver Zeigermann) (2003-04-13)
Re: Ambiguous recursive-descent parsing gopi@sankhya.com (2003-04-27)
| List of all articles for this month |

From: Chris F Clark <cfc@world.std.com>
Newsgroups: comp.compilers
Date: 30 Mar 2003 00:36:23 -0500
Organization: The World Public Access UNIX, Brookline, MA
References: 03-03-148
Keywords: parse, LL(1)
Posted-Date: 30 Mar 2003 00:36:23 EST

> I have some ideas for how Tomita-style techniques for managing
> multiple parse "states" can be combined with LL(1) parsing to easily
> parse languages like C++, but I want to make sure that I am not
> re-inventing the wheel.


I have to agree with our moderator that I've never heard of anyone
doing exactly that. Hopefully Adrian Johnstone will pipe in, for if
anyone has heard of someone doing that, I would think it would have
been him--he has worked in the area of "extending" LL parsing
techniques to make them more capable, someone once termed the parsers
generated by his tool RDP as "recursively decent" :-). His later
work, grdp may have been headed down the path you are suggesting. One
of Elizabeth Scott and his students, Sadaf Husain, wrote a very good
thesis detailing the Tomita algorithm which was just recent referenced
on this newsgroup.


So, while I cannot guarantee that your work is completely original, I
think it is most likely to be so. However, what I know of the field
suggests that what you are proposing is do-able and that given the
right effort, you should be able to be sucessful. The major question
is whether you can do it and preserve the most important LL attribute,
the ability to generate readable recursive descent parsers (i.e. where
the control flow through the parser is all explicit in the code) or
whether your resulting parsers will have to be interpreted and have
some sort of state machine ala the LR techniques.


Best of luck,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)


Post a followup to this message

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