•  Accepts string of tokens from lexical analyzer (usually one token at a time)
  •  Verifies whether or not string can be generated by grammar
  • Reports syntax errors (recovers if possible)


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:

  1.   Top down parser: which build parse trees from top(root) to bottom(leaves)
  2.   Bottom up parser: which build parse trees from leaves and work up the root.

Therefore there are two types of parsing methods– top-down parsing and bottom-up parsing

Parse Trees

  • Nodes are non-terminals.
  •  Leaves are terminals.
  •  Branching corresponds to rules of the grammar.
  •  The leaves give a sentence of the input language.
  •  For every sentence of the language there is at least one parse tree.
  •  Sometimes we have more then one parse tree for a sentence.
  •  Grammars which allow more than one parse tree for some sentences are called ambiguous and are usually not good for compilation.


Recursive descent parsing:  corresponds to finding a leftmost  derivation for an input string

Equivalent to constructing parse tree in pre-order


Grammar: S |cAd A | ab | a

Input: cad


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

  •   Can be viewed two ways:
  •  Attempt to find leftmost derivation for input string
  •  Attempt to create parse tree, starting from at root, creating nodes in preorder
  •   General form is recursive descent parsing

Predictive Parsing

  • May require backtracking
  • Backtracking parsers not used frequently because not needed

     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