In Thomas Sudkamp's book, Machine and Languages, there is a depth-first top-down parsing algorithm (please see the algorithm here).

My main question is:

1) Is this algorithm a (backtracking) recursive descent top-down parsing? This is because I am confused with the difference between the terms depth-first top-down parsing and recursive descent top-down parsing.

Additionally, I would appreciate it if you would answer these two questions also, as it is related to the algorithm:

2) In Step, why there is a need to assign $i=0$? If we want to backtrack, isn't the correct way is to keep $i$ as it is?

3) Does this algorithm uses a pushdown automaton? Is parsing using pushdown automaton different than just using a stack?

  • $\begingroup$ Please, make your question self-contained, by adding explicitly all elements necessary to understand it. Your post should contain just one question. $\endgroup$ – André Souza Lemos Dec 18 '16 at 16:23
  • $\begingroup$ Do you mean that I should copy the algorithm into the question? I'm really sorry as I don't know how to. Besides, the link provides the algorithm directly, so I think it is better like that to keep it simple. $\endgroup$ – kate Dec 18 '16 at 16:42
  • 1
    $\begingroup$ In step, the algorithm is moving forward, not backtracking. The backtrack is step 2.1, which restores i from the stack. $\endgroup$ – rici Dec 18 '16 at 22:05
  • $\begingroup$ @rici Thank you. Ok, now I understand. But is there a need to assign i=0? Didn't it already been replaced by j? Or is this just necessary to prevent bug in programming? $\endgroup$ – kate Dec 19 '16 at 4:34
  • 1
    $\begingroup$ When you move forward, you need to first try the first rule for the next non-terminal, so yes, you have to reset the rule counter. $\endgroup$ – rici Dec 19 '16 at 4:43

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.