S-> A

A-> aB| Ad

B->bBC|f

C→g

This question appears in Mumbai University > System programming and compiler construction subject

Marks: 10 M

Year: May 2015

Recursive decent parsing

• Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right.
• It uses procedures for every terminal and non-terminal entity.
• This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking.
• But the grammar associated with it (if not left factored) cannot avoid back-tracking.
• A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.
• This parsing technique is regarded recursive as it uses context-free grammar which is recursive in nature.

Back Tracking

• Top- down parsers start from the root node (start symbol) and match the input string against the production rules to replace them (if matched).

• To understand this, take the following example of CFG:

• S → rXd | rZd

  X → oa | ea

  Z → ai

• For an input string: read, a top-down parser, will behave like this:
• It will start with S from the production rules and will match its yield to the left-most letter of the input, i.e. ‘r’.
• The very production of S (S → rXd) matches with it. So the top-down parser advances to the next input letter (i.e. ‘e’).
• The parser tries to expand non-terminal ‘X’ and checks its production from the left (X → oa).
• It does not match with the next input symbol. So the top-down parser backtracks to obtain the next production rule of X, (X → ea).
• Now the parser matches all the input letters in an ordered manner. The string is accepted.

Predictive Parsing

• Predictive parser is a recursive descent parser, which has the capability to predict which production is to be used to replace the input string.
• The predictive parser does not suffer from backtracking.
• To accomplish its tasks, the predictive parser uses a look-ahead pointer, which points to the next input symbols.
• To make the parser back-tracking free, the predictive parser puts some constraints on the grammar and accepts only a class of grammar known as LL(k) grammar.

• Predictive parser consists of following components:
• Input Buffer:- It consists $ to indicated end of input.

1. Stack:- It consist $ to indicate end of stack.

2. Driver Routine:- It is a function that drives the Parser.

3. Parser Table:- It determines the actions to be carried out by the parser

• Predictive parsing uses a stack and a parsing table to parse the input and generate a parse tree.
• Both the stack and the input contains an end symbol $to denote that the stack is empty and the input is consumed.
• The parser refers to the parsing table to take any decision on the input and stack element combination.

The goal of predictive parsing is to construct a top-down parser that never backtracks. To do so, we must transform a grammar in two ways:

1. eliminate left recursion, and
2. Perform left factoring.

Steps for designing Predictive Parser:

1. Make the grammar suitable for top-down parser. By performing the elimination of left recursion. And by performing left factoring.
2. Find the FIRST and FOLLOW of the variables
3. Design predictive parser table
4. Write predictive parsing algorithm
5. Give some examples.

Example:

• S-> A

  A-> aB| Ad

  B->bBC|f

  C→g

Step 1:

A -> Ad/aB

LR

A -> aBA’

A’-> dA’|€

S -> A

B -> bBC|f

C -> g

Step 2

FIRST

FOLLOW

Step 3

Step 4

Repeat forever

{ Lest ‘X’ be the stack top symbol

And ‘a’ be the input symbol

If X=a=$ then accept and break

else if X=a=$

then

1. Pop X from stack

2. Remove a from input

Else

If M[X,a] = x y1,y2…….yk

Then

1. Pop X from stack

2. Push yk,yk+1…….y2,y1 on the stack

Else

ERROR()

}