Top-down parser classification

Question

I've watched this course by Alex Aiken and read through many other resources. But I'm struggling to find clear classification of top-down parsers.

This document doesn't provide a clear classification either but at least gives some definitions I'll use in the post. So here is the classification I've come up so far:

Backtracking VS Predictive

Backtracking

One solution to parsing would be to implement backtracking.  Based on the information  the parser currently has about the input, a decision is made to go with one particular  production.  If this choice leads to a dead end, the parser would have to backtrack to that decision point, moving backwards through the input, and start again making a different  choice and so on until it either found the production that was the appropriate one or ran  out of choices.

Predictive

A predictive  parser is characterized by its ability to choose the production to apply solely on the basis  of the next input symbol and the current nonterminal being processed.

Recursive descent VS table-driven

Recursive descent

A  recursive-descent parser consists of several small functions, one for each nonterminal in  the grammar.  As we parse a sentence, we call the functions that correspond to the left  side nonterminal of the productions we are applying.  If these productions are recursive,  we end up calling the functions recursively.

Table driven

There is another method for implementing a predictive parser that uses a table to store that production along with an explicit stack to keep track of where we are in the parse

As I understand now I have four different types of parsers:

• Recursive descent + backtracking
• Recursive descent + prediction
• Table-driven + backtracking
• Table-driven + prediction

If I'm correct, can some also tell me where in the following 4 types of parsers the LL(k) parser falls?

Answer 1

No. You have:

• backtracking vs predictive
• recursive descent vs table-driven

So you can have:

• recursive descent backtracking
• recursive descent predictive
• table-driven with backtracking
• table-driven predictive.

To be specific, 'Recursive descent with table/stack implementation' is a contradiction in terms.

All table-driven parser implementations need a stack. This is not a dichotomy.

where in the following 4 types of parsers the LL(k) parser falls?

Anywhere.