Top-Down Parsing Classification

Question

I looked at this course from Alex Aiken and read many other resources. But I try my best to find a clear classification of parsers from top to bottom.

This document does not contain a clear classification, but at least gives some definitions that I will use in the message. So, here is the classification that I have come up with so far:

Backtracking VS Predictive

Rollback

One of the parsing solutions will be rollbacks. Based on the information, the CA currently has near the entrance, a decision is made to go with one specific production. If this choice leads to a dead end, the analyzer should return to the point that the solution is moving backwards through the input, and start again making another choice and so on, until it either finds the production that is the proper one or ran out of options.

prediction

The Predictive Analyzer is characterized by the ability to select products for use solely on the basis of the next input symbol and the current processed non-terminal.

VS Recursive Descent with Table Control

Recursive descent

and the recursive descent analyzer consists of several small functions, one for each nonterminal in the grammar. How to parse a sentence, we call the functions that correspond to the left side of the non-terminal from the productions we apply. If these products are recursive, we end up calling the function recursively.

Table driven

There is another way to implement an intelligent parser that uses a table to store these products along with an explicit stack to track where we are in parsing.

As I understand it, I have four different types of parsers:

• Recursive descent + reverse search
• Recursive descent + forecast
• Table-driven + backtracking
• Table + forecast

If I'm right, can someone tell me where in the next 4 types of parsers the LL(k) parser falls?

Answer 1

No. You have:

• backtracking vs predive
• recursive descent versus table control

So you can have:

• recursive descent back
• predictive descent recursive
• reverse traced table control
• table driven forecast.

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

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

where in the next 4 types of parsers does the LL (k) parser fall?

Anywhere