Top-Down Parsing Predictive Parsing
Top-Down Parsing Predictive Parsing
Top-Down Parsing Predictive Parsing
Predictive Parsers
Some changes like removal of left recursion and left factoring the resultant grammar results in a
grammar that can be parsed by a recursive descent parser that needs no backtracking, called as
predictive parsing. The key problem during top down parsing is, given the current input symbol
‘a’ and the non-terminal A to be expanded, which among the different alternative productions
Aα|β|…….|γ is to be chosen. This problem can be solved with the help of a table constructed
called as the predictive parsing table.
Non-recursive Predictive Parser
A non-recursive predictive parser can be built by maintaining a stack explicitly, rather than
implicitly via recursive calls. The parser mimics a leftmost derivation. If w is the input that has
been matched so far, then the stack holds a sequence of grammar symbols a such that