2

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?

Community
  • 1
  • 1
Max Koretskyi
  • 101,079
  • 60
  • 333
  • 488

1 Answers1

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.

user207421
  • 305,947
  • 44
  • 307
  • 483
  • 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? – Max Koretskyi Aug 31 '17 at 09:29
  • 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*. – user207421 Aug 31 '17 at 10:24
  • 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? – Max Koretskyi Aug 31 '17 at 10:37
  • 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? – Max Koretskyi Aug 31 '17 at 10:39
  • @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. – user207421 Aug 31 '17 at 11:31
  • 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. – user207421 Aug 31 '17 at 12:45
  • okay, so if _An LL parser is either recursive descent or table-driven_ - [this](https://stackoverflow.com/q/1044600/2545680) question's title doesn't make much sense as well? and the accepted answer – Max Koretskyi Aug 31 '17 at 12:51
  • @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? – Max Koretskyi Aug 31 '17 at 14:26
  • @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. – user207421 Sep 01 '17 at 00:08
  • got it, thanks. It seems that for some reason [wikipedia](https://en.wikipedia.org/wiki/LL_parser) 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. – Max Koretskyi Sep 01 '17 at 16:05
  • 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 – Max Koretskyi Sep 02 '17 at 13:48
  • @AngularInDepth.com OMG. Both LL and LR parsers are predictive. – user207421 Jan 01 '18 at 22:23
  • 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 ? – explogx Feb 15 '19 at 15:34