Bottom up Parsing

The process of constructing the parse tree starting from input string and reaching the start symbol of the grammar is know as Bottom Up Parsing.
Handle : The part of the input string that matches with RHS of any production is called as handle.
Handle pruning : The process of finding the handle and replacing the handle by LHS of corresponding is called " handle Priority ".
Bottom up parsing is also know as shift reduce parser.
Bottom up parsing can be constructed for both ambiguous and unambiguous grammar.
For unambiguous grammar , LR parser can be constructed and operator Precedence Parser ( OPP ) can be constructed for both ambiguous and unambiguous grammar.
Bottom up parsing is more powerful than top down parser.
Average time complexity is O( n³ ) and handle pruning is major

 overhead for bottom up parsing.

Bottom up parser simulates the reverse of right mot derivation.

LR (k) Parser : 

     L = Left to Right Scanning.

     R = Reverse of right most derivation

     (k) = Number of Look Ahead Symbols = k

Shift Reduce Parsers

  Operator Precedence Parser (OPP)

    Constructed for 'operator precedence grammar', a grammar which do not contain epsilon productions and do not contain two adjacent non-terminals on R.H.S. of any productions. Operator precedence parser grammar is provided with precedence rules.

Operator Precedence Parsing Algorithm : Let 'a' is top of stack symbol and 'b' is symbol pointed by input pointer.

 (i) If  a ≛ b ≛ $ , successfully completion of parsing.

(ii) If a ⋖ b or a ≛ b then push 'b' onto stack and advance input points to next symbol.

(iii) If a ⋗ b then pop 'a' and reduction takes place for 'a'.

Operator precedence grammar may be either ambiguous or unambiguous grammar.

LR parsers 

 LR(0) Parser :

  (i) LR(0) parser is constructed for LR(0) grammar in which the parser table is free from multiple entries (conflicts).

  (ii) Conflict in LR(0) parser: 

        (a) Shift reduce (SR) conflict: When the same state in DFA contains both shift and reduced items.

         (b) Reduce Reduce (RR) conflict :

                  A→α . (reduced)  }

                  B→𝜸 . (reduced)  }  Both are in same state of DFA

   (iii) Closure ( ) and goto ( ) functions are used to create canonical collection of LR items.

   (iv) LR(0) parsing table construction :

             (a) If goto ( I_i , a ) = I_j , then set action [i,a] = S_j ( shift entry )

             (b) If goto ( I_i , A ) = I_j , then set action [i,A] = J ( shift entry )

              (c) If  I_i contains A→α (reduced production) then action [ i, all entries ] = Rp (reduced entry), where 'P' is production number ( P : A→α)

              (d) If  S→S. is in  I_i , then set action [i,$] to accept.

  (v) If a state contains either SR or RR conflicts then that state is called 'Inadequate State'.

Simple LR(1) Parser :

 (i) Conflicts in SLR(1) Parser:

       (a) Shift Reduce (SR) parser:

             A→α . xꞵ (shift)

             B→𝜸.   (reduce)

             If   FOLLOW(B) ⋂ {x} ≠ Ф

        (b) Reduce Reduce (RR) conflict :

               A→α.

               B→𝜸.  If   FOLLOW(A) ⋂ FOLLOW(B) ≠ Ф

  (ii) SLR(1) parsing table construction:

        (a) SLR(1) parsing table construction is sane as LR(0) except reduced entries.

        (b) If I_i contains A→α (reduced production), then find FOLLOW(A) and for every a in FOLLOW(A),set action [i,a] = Rp ( P is production number }

  (iii) SLR(1) is powerful then LR(0)

  (iv) Size of SLR(1) parse table is same as size of LR(0) parse table.

  (v) Every LR(0) grammar is SLR(1) but every SLR(1) need not be LR(0).

Canonical LR(1) or LR(1) Parser:

  (i) CLR(1) parsing table construction: Except reduced entries,remaining entries are same as SLR(1).

  (ii) If I_i contains A→α . $ |a| b then reduced entry (Rp) A→α in row 'i' under the terminals given by look ahead ( $ , a , b) in LR(1) items [ Rp entry entered into [i,$] , [i,a] and [i,b]]

Look ahead LR(1)  Parser :

  (i) It is constructed from CLR(1), if two states are having same production but may contain different look ahead, those two states of CLR(1) are combined into a single state in LALR(1).

  (ii) There is no chance of SR conflict but there may be chance for RR conflicts LALR(1) after combining the states of CLR(1) parser.

  (iii) Every LALR(1) grammar is CLR(1) but every CLR(1) grammar need not be LALR(1).

  (iv) LALR(1) parsers are often used in practice as parsing tables are smaller then CLR(1) parsing.