Top Down Parsing Methods

Top down approach tries to construct a leftmost derivation for the given string

Top down parsing is constructing a parse tree for the input starting from the root and create nodes of the parse tree in preorder (depth first)

A general form of Top Down Parsing is the recursive descent parsing

Top Down Parsing Algorithm

Construct the root node of the parse tree

Repeat until the leaves of the parse tree matches the input string

• At a node labeled A, select a production with A on its left hand side and for each symbol on its right hand side, construct the appropriate child
• When a terminal symbol is added to the fringe and it doesn't match the fringe, backtrack
• Find the next node to expand

Top down parsing methods:

This method is broadly divided into

                Backtracking (Brute Force Method)

                Predictive Parser (without Backtrack)

                                Recursive Descent

                                LL(1) Parser

Example: 
Input: ID + (ID + ID)
Build parse tree:
Start from start symbol to invoke: int input (void)

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.