Parsing

INTRODUCTION

Syntax analyzer is also know as parser.The syntax of a programming language is described by a context free grammar.
A parser works on stream of tokens which are generate by lexical analyser.

Ambiguous Grammar

   For a given input string if string if there exists 'more than one parse tree' then that grammar is called as " ambiguous grammar".

Left Recursion

   The grammar : A→Aɑ|ꞵ is left recursion, Top down parsing techniques cannot handle left recursive grammar , so we convert left recursive grammars into right recursive.



Left Recursive Elimination
  
    Left recursive : A→ Aα|ꞵ   { A→ꞵȂ}
                                                 {Ȃ→αȂ|ε}       ( non left recursion)

 Problem with left recursive grammar is that if such a grammar is used by top down parser (uses Left Most Derivation), then there is a danger of going into "infinite loop" while string is parsing.

Left Factoring

A predictive parser ( a top down parser without backtracking ) insists that the grammar must be left-factored.
Left factoring avoids backtracking in parser but is not a solution for elimination of ambiguity.
If a grammar has common prefixes in r.h.s of non-terminal then such grammar need to be left factored by eliminating common prefixes as follows:

         A→αꞵ1 | αꞵ2         { A→αȂ}
                                         {Ȃ→ꞵ1 | ꞵ2}   (left factored grammar)

Parsers

 1. Top-down parsers : Starting at the root ( the starting symbol) and proceeding to the leaves.This parsers are easy to write,actual code capable of being derived directly from the production rules,but cannot always applied as an approach.
 2. Bottom-up parsers : Starts at the leaves and move up towards the root. Bottom-up parsers, can handle a larger set of grammar.