What is the Difference Between Recursive Descent Parsing and Predictive Parsing

The main difference between recursive descent parsing and predictive parsing is that recursive descent parsing may or may not require backtracking while predictive parsing does not require any backtracking.

Compilation process includes several phases. The first phase is lexical analysis. It scans the source code as a stream of characters and converts it into meaningful lexemes. Moreover, it is a representation of tokens. The next step is the syntax analysis. It takes tokens as input and generates a parse tree. Parsing refers to this process. Here, the syntax analyzer checks the production rules defined by the context-free grammar. More importantly, parsing relies on the production rules. One type of parsing is top-down parsing. And, this parsing method creates a parse tree from the root node and moves progressively down to the leaf nodes.

Key Areas Covered

1. What is Recursive Descent Parsing
     – Definition, Functionality
2. What is Predictive Parsing
     – Definition, Functionality
3. What is the Relationship Between Descent Parsing and Predictive Parsing
     – Outline of the Association
4. What is the Difference Between Descent Parsing and Predictive Parsing
     – Comparison of Key Differences

Key Terms

Context-free Grammar, Parsing, Predictive Parsing, Recursive Descent Parsing

What is Recursive Descent Parsing

Recursive descent parsing creates the parse tree starting from the top, and it reads the input from left to right. It uses procedures for every terminal and non-terminal entity. Moreover, it recursively parses the input to make a parse tree.

Furthermore, it may or may not require backtracking, but the associated grammar cannot avoid backtracking. Backtracking is an algorithm to catch some or all solutions to given computational issues. It is used in parsing and other types of logic programming languages.

What is Predictive Parsing

Predictive parsing identifies what production to use to replace the input string. It does not have backtracking. The predicative parser uses a look ahead pointer. It points to the next input symbols. In order to make the parser free of backtracking, it uses some constraints on the grammar. Therefore, it will only accept grammar called LL(k) grammar.

Relationship Between Recursive Descent Parsing and Predictive Parsing

• Predictive parsing is a type of recursive descent.

Difference Between Recursive Descent Parsing and Predictive Parsing

Definition

A recursive descent parsing is a type of top-down parsing built from a set of mutually recursive procedures where each procedure implements one of the non-terminals of the grammar. While, predictive parsing is a type of top-down parsing approach, which is also a type of recursive descent parsing, that does not involve any backtracking. Thus, these definitions explain the fundamental difference between recursive descent parsing and predictive parsing.

Backtracking

Here, the requirement of backtracking is the main difference between recursive descent parsing and predictive parsing. That is; the recursive descent parsing may or may not require backtracking while predictive parsing does not require any backtracking.

Functionality

Moreover, recursive descent parsing uses procedures for every terminal and non-terminal entity while predictive parsing finds out the production to use by replacing the input string. Hence, this is another difference between recursive descent parsing and predictive parsing. 

Conclusion

In conclusion, top-down parsing is a type of parsing that works on the highest level of the parse tree and works down the parse tree by using rewriting rules of the formal grammar. Recursive descent parsing and predictive parsing are two such parsing methods. The main difference between recursive descent parsing and predictive parsing is that recursive descent parsing may or may not require backtracking while predictive parsing does not require any backtracking.

Reference:

1. “Recursive Descent Parser.” Wikipedia, Wikimedia Foundation, 15 Dec. 2018, Available here.
2. “What Is Backtracking? – Definition from Techopedia.” Techopedia.com, Available here.
3. “Top-down Parsing.” Wikipedia, Wikimedia Foundation, 16 Dec. 2018, Available here.
4. Fegaras, Leonidas. “3.2 Predictive Parsing.” Lambda.uta.edu, 20 Jan. 2015, Available here.

Image Courtesy:

1. “Parsing Example” By DevinCook at English Wikipedia – Transferred from en.wikipedia to Commons (Public Domain) via Commons Wikimedia