Re: Q: Recursive Descent w/Backtracking

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
--

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