parser and Types of parser(Top down and Bottom-up parser)

 

Process of compilation is divided into sub-task .So after  receive token as its input generated from previous phase and produce a hierarchical structure called syntax tree or parse tree.

Parser or syntax analysis is the second phase of compilation. Lexical analyzer generates taken from the source code string and that token is collect parser and convert into syntax tree.

The process of deriving the string from a given grammar using the production of the grammar is known as parsing . Here input is stream of tokens and output will be the parse tree. if we get a success in generating the syntax tree then it means there is no grammatical mistakes in the string otherwise it means a grammatical error.

Types of  parser

• Top-Down Parser
• Bottom up parser

Types of  Top Down Parser

• Top Down parsing without backtracking.
• Top down parser with backtracking. 

Types of Bottom-up parser

• Shift reduce parser
• Operator precedence parser.
• LR parser.

Top down parser

Top down parser generates the parse tree from root to leaves.It construct parse tree containing root as the starting symbol of the grammar and perform leftmost derivation at each step.

Top down parser are two types.

Top Down parser without backtracking

Top down parser with backtracking can make repeated scan of input.I required string not achieved by applying one production rule then another production rule can be applied at each step to get required string.

• Parser can try all alternatives in any order till it successfully parses the string.
• exponential time to perform parsing because backtracking takes lot of time.
• A grammar can have left recursion.
• Lot of overhead .
• Difficult to find error.
• Information once inserted will be removed from symbol table while backtracking.

Top down parser  without backtracking

Main limitation of  Top down parser with backtracking is that that parser take exponential time parse the string.Backtracking cannot be applied or implemented so easily in parsing.So to avoid this limitation use Top down parser without backtracking.

• Top down parser without backtracking take less time.
• Left  recursion will be removed before doing parsing.
• No backtracking so less overhead.
• Easily find error in Top down parser without backtracking.
• Information once inserted will not be  removed from symbol table because no backtracking.
• Parser can select correct alternative at each step because no left recursion or no left factor.

Types of Top down parser without backtracking.

• Predictive parser.
• Recursive decent parser.

Predictive parser

predictive parser is Top down parser without backtracking. That use stack ,parsing table .That is also called Non-recursive predictive parser.

Steps while parsing using predictive parser

• Computation of FIRST and FOLLOW for different symbol of grammar.
• Construct predictive parsing table using FIRST and FOLLOW.
• Perform parsing of input string with the help of predictive parsing table.

Recursive decent parser

Recursive decent is top down parser without backtracking.That uses recursive procedures to process the input string.

Bottom-up parser

Bottom up parser from leaves to root for a given string.In grammar the input string will be reduced to the starting symbol.

Types of  Bottom-up parser

• Shift reduce parser.
• Operator Precedence Parser.
• LR parser.

Shift reduce Parser

Shift reduce parser is Bottom up parser.In Shift reduce parser input string will be reduce to the starting symbol.Reduction can be applying rightmost derivation in reverse. That use Input Buffer and Stack data-structure.

Operator Precedence Parser

That is also Bottom up parser in this parser parsing is done depending upon the precedence relation between input symbol of string and handle on the top of stack.In this parser parsing can be applied on operator grammar.

Operator grammar is if the production of grammar do not contain two adjacent non-terminal and null on its right side.

LR parser

LR parser is bottom up parser that recognize all programming language written with CFG. That parser use Input buffer,Stack,Parsing table,Parsing Program to parse a input string. L means Left to Right scanning of input and R means Rightmost derivation.That bottom up parser is detect syntax error more quickly.

Types of  LR (Left to right input scanning and rightmost derivation)Parser

• SLR parser.
• CLR parser.
• LALR parser.

SLR parser

SLR parser is easy to implement but that parser fails to produce table for some classes of grammar.

• That is Simple LR parser . But that is not more powerful because that is fails to produce parsing table for some class of grammar.
• SLR parser require less time and less space to parse the input string.
• That parser is easy to implement.

LALR Parser(Look ahead LR parser)

LALR parser is intermediate power between SLR  and CLR parser.

• SLR<=LALR<=CR.
• LALR is easy and cheap to implement.
• Error detection in LALR is not immediate.
• LALR parser require more time and space complexity.
• It is easy and cheap to implement.

CLR parser(Canonical LR parser)

SLR failed for some unambiguous grammar to remove that limitation more powerful parser called CLR(Canonical LR parser).It parse string using a look ahead symbol generated while constructing set of  items.That is more powerful parser and work on large classes of grammar.

• CLR parser is largest in size. Number of states are very large.
• It is more powerful and work large class of grammar.
• Error detection can be done immediately  in CLR parser.
• It is expensive and difficult to implement. 
• More space and time complexity.