3
$\begingroup$

There are four types of top-down parsers according to this answer:

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

Also the author says that:

All top down parsers are LL

However, in this answer the author seem to associate the LL parser with table-driven parsers:

LL is usually a more efficient parsing technique than recursive-descent.

And the OP:

[one category]... seem to be the LL parser (using stack/parse table)

Also this article states:

LL parsers are also called predictive, because it's possible predict the exact path to take by a certain amount of lookup symbols, without backtracking.

which associates LL parsers with predictive parsers, which can be either recursive descent or table-driven.

So I'm at loss here. Can you guys help?

$\endgroup$
2
$\begingroup$

First let's make some general remarks about nomenclature. They are not all relevant here, but they may help you in the future.

  1. not all authors are using the same precise definition. Sometimes the differences are irrelevant for the current points, sometimes one wonder way such different things are named in the same way by different authors. Sometimes authors give the definition they are using, but that's not always true. Sometimes there are well accepted definition that you can take for granted in about any context, sometimes every group tend to have its own and you have to know of which group the author is a member. (Ask a Java and a ML programmer what polymorphism is)

  2. Nomenclature are about classification. Classification is emphasizing some aspects while ignoring other, even if you think it should be (For instance L. Cardelli and P. Wegner do not consider the static or dynamic aspect in their analysis of polymorphism)

Now you are somewhat lucky, as some of the terms here have quasi-universal definitions (that is not that some are not using other one, especially in blogs and QA sites, but they are trying to intuit a definition from the terms instead of looking at the definitions given by text books).

A top-down parser is a parser which start from the start symbol, guess which production to use, and then repeat the process for a non terminal symbol. If it is able to second guess its choice, it is also a back-tracking parser. If it never second guess its choice, it is a deterministic parser.

A LL(k) parser is a deterministic top-down parser which will always determine the production to use for the left-most non-terminal not yet determined (that's what the second L means) and will consider only the text from left to right (that's what the first L means) and will never use more than $k$ terminal symbols not predicted.

Thus

There are four types of top-down parsers:

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

deterministic seems more common than predictive but that division seems correct. I'll emphasize the fact that the division backtracking/predictive characterizes the algorithm, while the division recursive/table-driven characterizes the implementation. So although the classification is correct, it is mixing different aspects something which tend to introduce confusion.

All top down parsers are LL

That is false. Some are not deterministic (the recursive descent backtracking one of your first list). Some are scanning the text from right to left (AFAIK, the only interest is academic here but it would not surprise me that there is someone somewhere which found a use for it). Some are trying to determine the production to use for another non-terminal than the next one (it's a formalization of the good old find the next matching parenthesis before trying to parse what is between them).

LL is usually a more efficient parsing technique than recursive-descent.

LL can be implemented as recursive-descent (and is the easiest way to do so), opposing the two does not really make sense to me. Recursive/table driven is an implementation choice. (I've written both, I'd use the table driven approach only as part of a parser generator but I'll never say they are different algorithms).

LL parsers are also called predictive

This could be misleading. They are not the only class of parser which could be called predictive.

$\endgroup$
  • $\begingroup$ thanks a lot for your answer! It's still fuzzy, but a bit more clear now. So if LL parsers are always deterministic/predictive and can be implemented as recursive-descent or table-driven, the recursive descent predictive and table-driven predictive are LL parsers. Correct? $\endgroup$ – Maxim Koretskyi Aug 31 '17 at 19:35
  • $\begingroup$ also, can you maybe post your answer here as well and I'd be happy to accept it? The answer given there is misleading. $\endgroup$ – Maxim Koretskyi Aug 31 '17 at 19:36
  • $\begingroup$ No, recursive descent and table-driven are very generic description of implementation methods for parsers. As a matter of fact, non LL recursive descent parser are common (for C to handle typedef) and LR parsers can be described as predictive as well and are often implemented in a table-driven way. You could have other top-down deterministic parsers implemented in table-driven way (although I've not seen them) $\endgroup$ – AProgrammer Sep 1 '17 at 8:52
  • $\begingroup$ okay, thanks, another try. LL means that input is processed left to right and productions are tried left to write. This can be done with both recursive descent and table driven. But then you can use backtracking which will be LL parser, or use can use lookahead/prediction which makes LL(k) parser. So can we distinguish between LL parsers and LL(k) parsers? The wikipedia states that An LL parser is called an LL(k) parser if it uses k tokens of lookahead when parsing a sentence. So it seems that LL(k) parser is subcategory of LL parsers used with prediction instead of backtracking? $\endgroup$ – Maxim Koretskyi Sep 1 '17 at 9:03
  • $\begingroup$ For me using LL to describe an algorithm using back-tracking is playing loose with definitions and should not be done. I've never seen a scientific paper doing this. $\endgroup$ – AProgrammer Sep 2 '17 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.