0
6.2kviews
Show contents of stack and i/p buffer and action after each step.

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.


1 Answer
0
219views

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.

enter image description here

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

enter image description here

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 )

enter image description here

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

Step 3:- Generating Parse Table.

  ( - ) a \$
S S -> (S-F)     S -> F  
F       F -> a  

Above grammar is in LL(1). Because each cell contain only one entry. Now, Parsing the given string that is ( a-a).

Step 4 :-

Stack Input Action
\$S (a-a)\$  
\$)F-SC (a-a)\$ S -> (S-F)
\$)F-S a-a)\$ S -> F
\$)F-a a-a)\$ F -> a , Pop a
\$)F- -a)\$ Pop -
\$)F a)\$  
\$)a a)\$ F -> a , Pop a
\$) )\$ Pop )
\$ \$  
  Accepted  

Therefore, (a-a) is Accepted.

Please log in to add an answer.