0
$\begingroup$

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 2.3.3.3, 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?

Improve this question
$\endgroup$
6
  • $\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, 2016 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, 2016 at 16:42
  • 1
    $\begingroup$ In step 2.3.3.3, the algorithm is moving forward, not backtracking. The backtrack is step 2.1, which restores i from the stack. $\endgroup$
    – rici
    Dec 18, 2016 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, 2016 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, 2016 at 4:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.