Re: Q: Recursive Descent w/Backtracking

ichudov@wiltel.com (Igor Chudov)
Fri, 28 Oct 1994 16:45:47 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: ichudov@wiltel.com (Igor Chudov)
Keywords: parse
Organization: WilTel
References: 94-10-151
Date: Fri, 28 Oct 1994 16:45:47 GMT

SCHMIDTG@iccgcc.cs.hh.ab.com wrote:
: 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.


: One pitfall with RDB is that if not implemented properly, the order of
: productions can affect whether or not a solution is found. For example,
: consider the input string w = cabd with the above grammar. A naive
: implementation might fail as follows:


You can avoid the problems by two ways:


1. Admit that it is LL(2) grammar and just construct the parser for LL(2)
grammar;


2. Rewrite your grammar:
      S -> cAd
      A -> aB
      B ->
      B -> b


I would choose the latter, because this is most probably what the language
semantics really means.
----------------------------------------------------------------------------
Igor Chudov, Resource Solutions Intl office (918)588-2309
Systems Engineer, for WilTel. home (918)585-5862
                                                                                      E-mail: igor_chudov@wiltel.com
                                                                                      Internet: ichudov@shoe.wiltel.com
                                                                          1819 South Jackson #32-P Tulsa OK 74107
--


Post a followup to this message

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