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
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