For the following grammar construct LL(1) parser table

S → F $\hspace {1 cm}$ S-э (8 — F) $\hspace {1 cm}$ F-»a

And Parse hesfing (a-a). Show contents of stack and i/p buffer and action after each step.

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:

1. Input Buffer

   It consists \$ to indicated end of input.

2. Stack

   It consist \$ to indicate end of stack.

3. Driver Routine

   It is a function that drives the Parser.

4. 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:

i. eliminate left recursion, and

ii. 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 -> F

  S -> (S-F)

  F -> a

  Above grammar can be written as,

  S -> F | (S-F)

  F -> a

To solve the above grammar using LL(1) parser we have to follow three steps :-

Step 1 : Remove Left and Right recursion.

Above grammar does not contain any left or right recursion hence we follow step 2 directly.

Step 2 : Finding first & follow

First (S) = S -> F

$\hspace{1 cm}$ First (S) is First (F)

$\hspace{1 cm}$ First (F) = a

$\hspace{1 cm}$ First (S) = {a}

Now,

S -> (S-F)

$\hspace{1 cm}$ First (S) = ( Since, ( is terminal symbol.

$\hspace{1 cm}$ First (S) = { a, ( }

$\hspace{1 cm}$ First (F) = {a}

Now, Lets find follow of each variable

$\hspace{1 cm}$ Follow (F) = { \$, - }

$\hspace{1 cm}$ Follow (F) = { }

$\hspace{1 cm}$ S -> F

Here, F is not followed by any variable or symbol. (In follow of F we put follow of S )

            Therefore, Follow (F) ={ S, - } 
         Again,
    S -> (S-F)
    Therefore, Follow (F) = { \$, - , ) }
    Follow (S) = { \$, - }
             Follow (F) = { \$, - , ) }

Step 3:- Generating Parse Table.

Step 4 :-

Therefore, (a-a) is Accepted.