Parser obtains a string of tokens from the lexical analyzer and verifies that it can be generated by the language for the source program. The parser should report any syntax errors in an intelligible fashion.
The two types of parsers employed are:
Therefore there are two types of parsing methods– top-down parsing and bottom-up parsing
Recursive descent parsing: corresponds to finding a leftmost derivation for an input string
Equivalent to constructing parse tree in pre-order
Example:
Grammar: S |cAd A | ab | a
Input: cad
Problems:
1. backtracking involved ()buffering of tokens required)
2. left recursion will lead to infinite looping
3. left factors may cause several backtracking steps
Top Down Parsing
Predictive Parsing
A special case of recursive-descent parsing that does not require backtracking
Must always know which production to use based on current input symbol
Can often create appropriate grammar:
removing left-recursion
left factoring the resulting grammar