# Is this depth-first top-down parsing algorithm a recursive descent top-down parsing algorithm?

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?

• Please, make your question self-contained, by adding explicitly all elements necessary to understand it. Your post should contain just one question. Dec 18, 2016 at 16:23
• 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.
– kate
Dec 18, 2016 at 16:42
• 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.
– rici
Dec 18, 2016 at 22:05
• @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?
– kate
Dec 19, 2016 at 4:34
• 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.
– rici
Dec 19, 2016 at 4:43