Q: Recursive Descent w/Backtracking

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:


S -> cAd -> cad (REJECT)


                        S
                      /|\
                    / | \
                  c A d
                        |
                        a


The problem is that the production for 'A' succeeded with a match on 'a', we
then try to match a 'b' with a 'd' and fail. What needs to happen is that
we go back to 'A' and try the second alternative 'ab'. This problem
would not have occurred if the order alternatives for 'A' were reversed:


S -> cAd
A -> ab | a


S -> cAd -> cabd (ACCEPT)


                        S
                      /|\
                    / | \
                  c A d
                        |
                        ab


(the older "Dragon Book" discusses this problem)


This type of backtracking over a tree is difficult to implement using
recursive precedures to represent each production, since if we had a
procedure called 'A' which attempts to match either 'a' or 'ab', we
would have to remember that we called 'A' and then call 'A' again
telling it this time to ignore the first alternative.


I have a rough outline of an algorithm that is designed to handle this
case. It uses a stack to keep track of the set of production choices
which have been applied and the current input pointer (to string w)
in case backtracking has to move the pointer back. The key to the algorithm
is that it also maintains a set of unexpanded nodes (in leftmost order)
yet to be expanded (matched against). Unfortunately, the algorithm is
very unclear as to how the unexplored the nodes are managed so that the
proper node is always explored at the right point in time.


So does anyone have a lucid description of an algorithm which will handle
backtracking over all possibilites of a grammar tree?


Thanks in advance,


-- Greg Schmid schmidtg@iccgcc.decnet.ab.com
--

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