Courses

# PPT - TOP Down Parsing Computer Science Engineering (CSE) Notes | EduRev

## Computer Science Engineering (CSE) : PPT - TOP Down Parsing Computer Science Engineering (CSE) Notes | EduRev

``` Page 1

Top-Down Parsing â€“ 1 Compiler Design â€“ © Muhammed Mudawwar
Top-Down Parsing
v A parser is top-down if it discovers a parse tree top to bottom
­ A top-down parse corresponds to a preorder traversal of the parse tree
­ A leftmost derivation is applied at each derivation step
v Top-down parsers come in two forms
­ Predictive Parsers
² Predict the production rule to be applied using lookahead tokens
­ Backtracking Parsers
² Will try different productions, backing up when a parse fails
v Predictive parsers are much faster than backtracking ones
­ Predictive parsers operate in linear time â€“ will be our focus
­ Backtracking parsers operate in exponential time â€“ will not be considered
v Two kinds of top-down parsing techniques will be studied
­ Recursive-descent parsing
­ LL parsing
Page 2

Top-Down Parsing â€“ 1 Compiler Design â€“ © Muhammed Mudawwar
Top-Down Parsing
v A parser is top-down if it discovers a parse tree top to bottom
­ A top-down parse corresponds to a preorder traversal of the parse tree
­ A leftmost derivation is applied at each derivation step
v Top-down parsers come in two forms
­ Predictive Parsers
² Predict the production rule to be applied using lookahead tokens
­ Backtracking Parsers
² Will try different productions, backing up when a parse fails
v Predictive parsers are much faster than backtracking ones
­ Predictive parsers operate in linear time â€“ will be our focus
­ Backtracking parsers operate in exponential time â€“ will not be considered
v Two kinds of top-down parsing techniques will be studied
­ Recursive-descent parsing
­ LL parsing
Top-Down Parsing â€“ 2 Compiler Design â€“ © Muhammed Mudawwar
Top-Down Parsing by Recursive-Descent
v We view a nonterminal A as a definition of a procedure A
­ Procedure A will match the token sequence generated by nonterminal A
v The RHS of a production of A specifies the code for procedure A
­ Terminals are matched against input tokens
­ Nonterminals produce calls to corresponding procedures
v If multiple production rules exist for a nonterminal A
­ One of them is predicted based on a lookahead token
² The lookahead token is the next input token that should be matched
­ The predicted rule is the only one that applies
² Other rules will NOT be tried
² This is a predictive parsing technique, not a backtracking one
v A syntax error is detected when
­ Next token in the input sequence does NOT match the expected token
Page 3

Top-Down Parsing â€“ 1 Compiler Design â€“ © Muhammed Mudawwar
Top-Down Parsing
v A parser is top-down if it discovers a parse tree top to bottom
­ A top-down parse corresponds to a preorder traversal of the parse tree
­ A leftmost derivation is applied at each derivation step
v Top-down parsers come in two forms
­ Predictive Parsers
² Predict the production rule to be applied using lookahead tokens
­ Backtracking Parsers
² Will try different productions, backing up when a parse fails
v Predictive parsers are much faster than backtracking ones
­ Predictive parsers operate in linear time â€“ will be our focus
­ Backtracking parsers operate in exponential time â€“ will not be considered
v Two kinds of top-down parsing techniques will be studied
­ Recursive-descent parsing
­ LL parsing
Top-Down Parsing â€“ 2 Compiler Design â€“ © Muhammed Mudawwar
Top-Down Parsing by Recursive-Descent
v We view a nonterminal A as a definition of a procedure A
­ Procedure A will match the token sequence generated by nonterminal A
v The RHS of a production of A specifies the code for procedure A
­ Terminals are matched against input tokens
­ Nonterminals produce calls to corresponding procedures
v If multiple production rules exist for a nonterminal A
­ One of them is predicted based on a lookahead token
² The lookahead token is the next input token that should be matched
­ The predicted rule is the only one that applies
² Other rules will NOT be tried
² This is a predictive parsing technique, not a backtracking one
v A syntax error is detected when
­ Next token in the input sequence does NOT match the expected token
Top-Down Parsing â€“ 3 Compiler Design â€“ © Muhammed Mudawwar
Example on Recursive-Descent Parsing
v Consider the following grammar for expressions in EBNF notation
expr ? term  { addop term }
term ? factor  { mulop factor }
factor ? â€˜(â€™ expr â€˜)â€™ |  id |  num
v Since three nonterminals exist, we need three parsing procedures
­ The curly brackets expressing repetition is translated into a while loop
­ The vertical bar expressing alternation is translated into a case statement
procedure expr( )
begin
term( );
term( );
end while;
end expr;
procedure term( )
begin
factor( );
while token = MULOP do
match(MULOP);
factor( );
end while;
end term;
procedure factor( )
begin
case token of
â€˜(â€™: match(â€˜(â€™); expr( ); match(â€˜)â€™);
ID: match(ID);
NUM: match(NUM);
else syntax_error(token);
end case;
end factor;
Page 4

Top-Down Parsing â€“ 1 Compiler Design â€“ © Muhammed Mudawwar
Top-Down Parsing
v A parser is top-down if it discovers a parse tree top to bottom
­ A top-down parse corresponds to a preorder traversal of the parse tree
­ A leftmost derivation is applied at each derivation step
v Top-down parsers come in two forms
­ Predictive Parsers
² Predict the production rule to be applied using lookahead tokens
­ Backtracking Parsers
² Will try different productions, backing up when a parse fails
v Predictive parsers are much faster than backtracking ones
­ Predictive parsers operate in linear time â€“ will be our focus
­ Backtracking parsers operate in exponential time â€“ will not be considered
v Two kinds of top-down parsing techniques will be studied
­ Recursive-descent parsing
­ LL parsing
Top-Down Parsing â€“ 2 Compiler Design â€“ © Muhammed Mudawwar
Top-Down Parsing by Recursive-Descent
v We view a nonterminal A as a definition of a procedure A
­ Procedure A will match the token sequence generated by nonterminal A
v The RHS of a production of A specifies the code for procedure A
­ Terminals are matched against input tokens
­ Nonterminals produce calls to corresponding procedures
v If multiple production rules exist for a nonterminal A
­ One of them is predicted based on a lookahead token
² The lookahead token is the next input token that should be matched
­ The predicted rule is the only one that applies
² Other rules will NOT be tried
² This is a predictive parsing technique, not a backtracking one
v A syntax error is detected when
­ Next token in the input sequence does NOT match the expected token
Top-Down Parsing â€“ 3 Compiler Design â€“ © Muhammed Mudawwar
Example on Recursive-Descent Parsing
v Consider the following grammar for expressions in EBNF notation
expr ? term  { addop term }
term ? factor  { mulop factor }
factor ? â€˜(â€™ expr â€˜)â€™ |  id |  num
v Since three nonterminals exist, we need three parsing procedures
­ The curly brackets expressing repetition is translated into a while loop
­ The vertical bar expressing alternation is translated into a case statement
procedure expr( )
begin
term( );
term( );
end while;
end expr;
procedure term( )
begin
factor( );
while token = MULOP do
match(MULOP);
factor( );
end while;
end term;
procedure factor( )
begin
case token of
â€˜(â€™: match(â€˜(â€™); expr( ); match(â€˜)â€™);
ID: match(ID);
NUM: match(NUM);
else syntax_error(token);
end case;
end factor;
Top-Down Parsing â€“ 4 Compiler Design â€“ © Muhammed Mudawwar
v The recursive-descent procedures use a token variable
v The token variable is the lookahead token
­ Keeps track of the next token in the input sequence
­ Is initialized to the first token before parsing begins
­ Is updated after every call to the match procedure
v The match procedure matches lookahead token with its parameter
­ Is called to match an expected token on the RHS of a production
­ Match succeeds if expected token = lookahead token and fails otherwise
­ Match calls scanner function to update the lookahead token
procedure match ( ExpectedToken )
begin
if token = ExpectedToken then token := scan( ) ;
else syntax_error( token , ExpectedToken ) ;
end if;
end match ;
Page 5

Top-Down Parsing â€“ 1 Compiler Design â€“ © Muhammed Mudawwar
Top-Down Parsing
v A parser is top-down if it discovers a parse tree top to bottom
­ A top-down parse corresponds to a preorder traversal of the parse tree
­ A leftmost derivation is applied at each derivation step
v Top-down parsers come in two forms
­ Predictive Parsers
² Predict the production rule to be applied using lookahead tokens
­ Backtracking Parsers
² Will try different productions, backing up when a parse fails
v Predictive parsers are much faster than backtracking ones
­ Predictive parsers operate in linear time â€“ will be our focus
­ Backtracking parsers operate in exponential time â€“ will not be considered
v Two kinds of top-down parsing techniques will be studied
­ Recursive-descent parsing
­ LL parsing
Top-Down Parsing â€“ 2 Compiler Design â€“ © Muhammed Mudawwar
Top-Down Parsing by Recursive-Descent
v We view a nonterminal A as a definition of a procedure A
­ Procedure A will match the token sequence generated by nonterminal A
v The RHS of a production of A specifies the code for procedure A
­ Terminals are matched against input tokens
­ Nonterminals produce calls to corresponding procedures
v If multiple production rules exist for a nonterminal A
­ One of them is predicted based on a lookahead token
² The lookahead token is the next input token that should be matched
­ The predicted rule is the only one that applies
² Other rules will NOT be tried
² This is a predictive parsing technique, not a backtracking one
v A syntax error is detected when
­ Next token in the input sequence does NOT match the expected token
Top-Down Parsing â€“ 3 Compiler Design â€“ © Muhammed Mudawwar
Example on Recursive-Descent Parsing
v Consider the following grammar for expressions in EBNF notation
expr ? term  { addop term }
term ? factor  { mulop factor }
factor ? â€˜(â€™ expr â€˜)â€™ |  id |  num
v Since three nonterminals exist, we need three parsing procedures
­ The curly brackets expressing repetition is translated into a while loop
­ The vertical bar expressing alternation is translated into a case statement
procedure expr( )
begin
term( );
term( );
end while;
end expr;
procedure term( )
begin
factor( );
while token = MULOP do
match(MULOP);
factor( );
end while;
end term;
procedure factor( )
begin
case token of
â€˜(â€™: match(â€˜(â€™); expr( ); match(â€˜)â€™);
ID: match(ID);
NUM: match(NUM);
else syntax_error(token);
end case;
end factor;
Top-Down Parsing â€“ 4 Compiler Design â€“ © Muhammed Mudawwar
v The recursive-descent procedures use a token variable
v The token variable is the lookahead token
­ Keeps track of the next token in the input sequence
­ Is initialized to the first token before parsing begins
­ Is updated after every call to the match procedure
v The match procedure matches lookahead token with its parameter
­ Is called to match an expected token on the RHS of a production
­ Match succeeds if expected token = lookahead token and fails otherwise
­ Match calls scanner function to update the lookahead token
procedure match ( ExpectedToken )
begin
if token = ExpectedToken then token := scan( ) ;
else syntax_error( token , ExpectedToken ) ;
end if;
end match ;
Top-Down Parsing â€“ 5 Compiler Design â€“ © Muhammed Mudawwar
Syntax Tree Construction for Expressions
v A recursive-descent parser can be used to construct a syntax tree
SyntaxTree := expr ( ) ;  Calling parser function for start symbol
v Parsing functions allocate and return pointers to syntax tree nodes
v Construction of a syntax tree for simple expressions is given below
­ New node allocates a tree node and returns a pointer to it
function expr( ) : TreePtr
begin
left := term( );
right := term( );
left := new node(op, left, right);
end while;
return left;
end expr;
function term( ) : TreePtr
begin
left := factor( );
while token = MULOP do
op := MULOP.op;  match(MULOP);
right := factor( );
left := new node(op, left, right);
end while;
return left;
end term;
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

## Compiler Design

24 videos|35 docs|29 tests

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;