## Pages

### Recursive descent parser

RECURSIVE DESCENT PARSER

A parser that uses collection of recursive procedures for parsing the given input string is called Recursive Descent (RD) Parser.

Basic steps for construction of RD parser:

• The R.H.S. of the rule is directly converted into program code symbol by symbol.
•  If the input is non-terminal then a call to the procedure corresponding to the non-terminal is made.
• If the input is terminal then it is matched with the look ahead from input. The look- ahead pointer has to be advanced on matching of the input symbol.
• If the production rule has many alternates then all these alternates has to be combine into a single body of procedure.
• The parser should be activated by a procedure corresponding to the start symbol.

Predictive LL (1) parser

This top down parsing algorithm is of non- recursive type. In this type of parsing a table is built. for LL(1):

• The first L means the input is scanned from left to right.
• The second L means it uses left most derivation for input string. & the number 1 in the input symbol (look-ahead) to predict the parsing process.

The simple block diagram of LL (1) parser is as given below:-

The data structure used by LL(1) are:

1. Input Buffer
2. stack
3. parsing table

Construction of Predictive LL (1) Parser

This parser is based on two very important function & those are FIRST and FOLLOW.

For construction of predictive LL(1) parser we have to follow the following steps-

• Computation of FIRST and FOLLOW function.
• Construct the predictive parsing table using FIRST and FOLLOW functions.
• Parse the input string with the help of predictive parsing table.

FIRST function

Following are the rules used to compute the FIRST functions.

•  If the terminal symbol a the FIRST (a) = {a}.
• If there is a rule Xà e then FIRST (X) = {e}.
• For the rule AàX1 X2 X3 .....Xk FIRST (A) = (FIRST (X1) U FIRST (X2) U FIRST (X3) .... U FIRST (Xk).
Where K Xj <= n such that 1<= j <= k-1.

The rule of computing FOLLOW function are as given below-

• For the start symbol S place \$ in FOLLOW(S).
• If there is a production A à aBb then everything in FIRST(b) without e is to be placed in FOLLOW(B).
• If there is a production Aà aBb or Aà aB and FIRST (b) ={e} then FOLLOW (A) = FOLLOW(B) or FOLLOW(B) = FOLLOW (A). That means everything in FOLLOW (A) is in FOLLOW (B).

BY:
KOMAL S. MAHAJAN
TSEC BURHANPUR

## Professor Jayesh video tutorial

Please use contact page in this website if you find anything incorrect or you want to share more information about the topic discussed above.