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?

Cathar

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.

Watersick

thanks, so it seems I got it right. Hooray! I wanted to write table driven but then saw some implementions with stack. Are you saying there's a contradiction here table/stack implementation? Why? Also, where do LL,LL(1), LL(k) parsers go in this classification? – Cathar

It seems like you got it wrong, by uttering a contradiction in terms: recursive descent table-driven. All top down parsers are LL. k is just the degree of lookahead. Usually it is 1, as k > 1 can always be reduced to k = 1. – Watersick

ah, I see now what you mean, I made a mistake when making the 4 categories out of 2 possible sets. Thanks. I've made the change in the post. But the two main categories I got right, correct? – Cathar

also, you're saying that all LL top-down parsers are LL. So if there's a lookeahed it's LL(1) which is Recursive descent + prediction and Table-driven + prediction. If there's lookahead, it's LL(k) which is Recursive descent + backtracking and Table-driven + backtracking. Is it correct? – Cathar

@MaximKoretskyi No. I said what I said. All LL parsers are LL. I didn't say it, but I didn't need to: it is a tautology. An LL parser is either recursive descent or table-driven: not both at the same time. It is a contradiction in terms. For the third time. You're talking nonsense. – Watersick

Personal remarks are out of place here. Avoid them. I don't how you regard telling people they've said things they haven't said, and didn't need to, or uttering tautologies and contradictions, but it is all nonsense, and saying so is merely factual. – Watersick

okay, so if An LL parser is either recursive descent or table-driven - this question's title doesn't make much sense as well? and the accepted answer – Cathar

@EJP, I think I know where I got confused. I thought that LL is a kind of parser, whereas it's a kind of grammar. And when you say that all 4 types are LL parsers you mean that either one of them can parse LL grammar. Is it correct? – Cathar

@MaximKoretskyi 1. I agree. That questions's title doesn't make sense, or the answer. 2. That is correct: LL is a grammar class. You also got confused between table-driven, which is one possible implementation, and recursive descent, which is another. – Watersick

got it, thanks. It seems that for some reason wikipedia associates LL parsers with table-based parsers - "LL parsers are table-based parsers". Although it also states that LL grammar can be parsed by recursive-descent parser. After reading many resources it seems that most people also associate LL parsers with predictive technique. – Cathar

So probably the conclusion is that LL grammar can be parsed by any top-down parser, but "usually" parser that is implemented as table-driven predictive parser is referred to as "LL" parser – Cathar

@AngularInDepth.com OMG. Both LL and LR parsers are predictive. – Watersick

I have a question about the table-driven predictive parser, I wonder how to create an AST from the algorithm. Where do I put my node building functions ? – Papua