Re: Q: Recursive Descent w/Backtracking

davidm@Rational.COM (David Moore)
Tue, 25 Oct 1994 04:00:32 GMT

          From comp.compilers
Related articles
Q: Recursive Descent w/Backtracking SCHMIDTG@iccgcc.cs.hh.ab.com (1994-10-21)
Re: Q: Recursive Descent w/Backtracking rockwell@nova.umd.edu (1994-10-28)
Re: Q: Recursive Descent w/Backtracking ichudov@wiltel.com (1994-10-28)
Re: Q: Recursive Descent w/Backtracking davidm@Rational.COM (1994-10-25)
Re: Q: Recursive Descent w/Backtracking bevan@cs.man.ac.uk (1994-10-31)
Re: Q: Recursive Descent w/Backtracking pjj@cs.man.ac.uk (1994-10-28)
Re: Q: Recursive Descent w/Backtracking hbaker@netcom.com (1994-11-03)
Re: Q: Recursive Descent w/Backtracking ridoux@irisa.fr (1994-11-07)
| List of all articles for this month |
Newsgroups: comp.compilers
From: davidm@Rational.COM (David Moore)
Keywords: parse, LL(1)
Organization: Rational Software Corporation
References: 94-10-151
Date: Tue, 25 Oct 1994 04:00:32 GMT

SCHMIDTG@iccgcc.cs.hh.ab.com writes:


>Hello,


>I'm attempting to write a recursive descent parser with backtracking (RDB).
>So for example given the following grammar:


>S -> cAd
>A -> a | ab


>It would be able to correctly parse the sentences of this language.


Look at the programming language Icon:


"The Icon Programming Language" Griswold and Griswold,
Prentice Hall 1971 (ISBN 0-13-449777-5)


This language introduces the idea of a "generator" which is (essentially)
a function that can be backed up into to produce a second result if
you do not like the first one.


You can probably get Icon from an FTP site. Once you understand the
principles, actually implementing what you want in some other language
is not hard. It comes down to keeping a tree of "activation segments"
rather than just a stack, so that you can revisit an activation (pruning
to the right as you go)
--

Post a followup to this message

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