2

I am working on Context Free Grammars and I am stuck into the first step: understanding how Top-Down parsing algorithms are structured.

My problem revolves around top-down parsers. And I have three algorithms that were introduced to me:

  • Recursive Descent
  • Predictive
  • Predictive Recursive Descent

Questions

But do not understand how to relate them. So please answer the following questions:

  • Is it true that Recursive Descent is based on backtracking and inefficient?
  • Is it true that Predictive parsing is a completely different algorithm from the other two?
  • Is it true that Predictive Recursive Descent is a particular kind of recursive descent algorithm but without backtracking?
  • Is it true that Predictive algorithms use parse-tables and Recursive Descent do not? Is it true that Predictive Recursive Descent algorithms use a predictive parse table (sort of enhanced parse table)?

Also please answer this question:

  • Which algorithm LL parsers use? Predictive, Predictive Recursive Descent or Recursive Descent?

Thank you

Community
  • 1
  • 1
Andry
  • 16,172
  • 27
  • 138
  • 246

2 Answers2

4

Recursive descent allows you to implement a certain range of formal parsers. For example, it allows to develop LL(k) parsers. In the LL case, recursive descent does not need backtracking, that is, given the nature of LL, the parser will not realize that it missed some parsing rule. On the other hand, recursive descent also allows you to implement parsers that use backtracking. So you can use backtracking or not and you can acommodate a range of parser families using recursive descent.

Recursive descent has no built-in efficiency guarantees. It depends on what you code and what's the problem you're solving. clang parser for the C family of languages is recursive, does backtracking and is considered by the authors to be a proper way to parse the C language.

I'm not sure about the terminology concerning predictive parsing, wikipedia suggests that it's a recursive descent parser that does no backtracking, like the example above, but that case makes more sense to be called a predictive recursive descent parser. There are some lecture notes that suggest that a predictive parser is one that does not implicitly uses the stack to hold the parser state. In this case, a predictive parser, for example, uses an explicitly managed stack, possibly being driven by a table with parsing rules.

Given the contrast between recursive descent and predictive parsing as two implementation techniques for parsing, I'd say that the recursive parser is a way to implement parsers using recursive functions (and implicitly use the stack), while predictive parsing in a way to implement parsers using tables and an explicit stack (but no recursive functions). The predictive recursive descent suggests that there is a parser using tables and recursive functions, which look strange to me. Worst case, a predictive recursive descent parser is a recursive descent parser (and not a predictive parser) that does no backtracking, having an ugly name.

The conceptual LL parser can be converted both to a recursive descent parser (that is, a set of recursive functions), which won't do any backtracking, because LL doesn't need it, or to a predictive parser (that is, a while loop + a stack + a table).

Best way to learn about recursive descent parsers is to do the kaleidoscope language tutorial: http://llvm.org/docs/tutorial/LangImpl2.html

http://en.wikipedia.org/wiki/LL_parser

http://en.wikipedia.org/wiki/Recursive_descent_parser

Are GCC and Clang parsers really handwritten?

http://www.cs.purdue.edu/homes/xyzhang/spring09/notes/ll.pdf

Community
  • 1
  • 1
hdante
  • 7,685
  • 3
  • 31
  • 36
3

Predictive parsers are a general family of parsers that come in many forms (LL and LR parsers are the more prominent examples). Predictive parsers typically work by trying to "predict" which productions to use (or which reductions to apply) by using some knowledge of the current state of the parse. For example, in LL parsing, the parser tries to predict which production to apply based on the current nonterminal and the next few characters of input. In LR parsing, the predictions are which reductions, if any, should be performed at a particular point in time based on the next terminals of input and the current configuration of the parser.

Many, but not all, predictive parsers are table-driven. LR parsers are commonly implemented using tables, as are some LL parsers, though this isn't always the case. Many LL parsers are implemented using recursive descent and many LR parsers are implemented using recursive ascent.

Recursive-descent parsing typically refers to top-down parsing algorithms that work by guessing which productions to use by having different recursive functions for each terminal and nonterminal. They typically employ some amount of backtracking based on the grammar and typically fail on left-recursive grammars. Typically, hand-written LL parsers are written using recursive descent with no backtracking, which is possible because the grammar is specifically constructed to not require any backtracking. This is predictive recursive descent.

With backtracking, recursive descent can be terribly inefficient. Typically, you wouldn't use recursive descent on grammars that would require backtracking like this.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065