Let G be a grammar that contains no left-recursive rules, and we use a recursive-descent recognizer that uses full backtracking, using list of results for example, to recognize strings of G.

How can someone show formally that if s is a sentence in G, then R(G), which is the recognizer I just described for G, can recognize s, and it also explores all the paths, i.e., if there are two paths to recognition, both can be explored.

  • 2
    $\begingroup$ Why do you want to do that rather than use dynamic programming which is more efficient, quadratic (for recognition only) rather than exponential, and can accept recursive rules? Also exploring all paths is useless for a recognizer: what is recognized is recognized. $\endgroup$ – babou Sep 9 '14 at 22:07
  • $\begingroup$ My question here is not from a practicality point of view. You are right and there are indeed better options out there. I just would like to know how someone writes such proofs? How to show the correctness of a recursive-descent parser. $\endgroup$ – Wickoo Sep 9 '14 at 22:12
  • 2
    $\begingroup$ Not much time for it just now. Can you get inpiration from what is done to prove non-deterministic PDA recognize CF languages. After all, your backtrack recursive-descent is just mimicking a non-deterministic PDA computation. $\endgroup$ – babou Sep 9 '14 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.