Generate three address code for following code,

While (a-b)     do
If (cod)    then
x=y+2 
else
x=y-2

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 → r X d | 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.

  • Stack

    It consist \$ to indicate end of stack.

  • Driver Routine

    It is a function that drives the Parser.

  • 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.

  • eliminate left recursion, and
  • Perform left factoring.

Steps for designing Predictive Parser:

• Make the grammar suitable for top-down parser. By performing the elimination of left recursion. And by performing left factoring.
• Find the FIRST and FOLLOW of the variables
• Design predictive parser table
• Write predictive parsing algorithm
• 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

i.Pop X from stack

ii. 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()
  }