Slr Parsing Table Program In C

Slr Parsing Table Program In C - lasopaepi. Must Read: C Program For Recursive Descent Parsing Note: This C program to find First and Follow sets of a Grammar using Array is compiled with GNU GCC compiler and developed using gEdit Editor in Linux Ubuntu operating system. C Program To Find First of a Given Grammar using Array. Must Read: C Program For Recursive Descent Parsing Note: This C program to find First and Follow sets of a Grammar using Array is compiled with GNU GCC compiler and developed using gEdit Editor in Linux Ubuntu operating system. C Program To Find First of a Given Grammar using Array. Please like & subscribe for more CS based tutorials!:). To parse a string using First and Follow algorithm and LL-1 parser: Dec 26: To parse a string using First and Follow algorithm and LL-1 parser: Dec 25: Program that prompts the user to enter a character, and on subsequent lines prin. Sep 28: Program to show the implementation of Bottom-Up Parsing: Sep 13: Stacks code in C: Dec 06.

SLR(1) Parsing

It is a simple LR parsing. Most of the function of this parsing is the same as LR(0) parsing. The parsing table for both the parser vary. The SLR(1) parsing use canonical LR(0) item. The reduce move is placed only in the FOLLOW of those variables whose production is reduced.

The step involves in SLR(1) parsing is given below:

  • Write a CFG for the given input string
  • Check if the grammar is ambiguous or not.
  • Add an augmented grammar.
  • Create a canonical LR(0) item.
  • Draw DFA
  • Construct an SLR(1) parsing table.

Example

E => BB

B => cB / d

Add augment production and insert ‘.’ symbol in the first position for every production in G.

E’ => .E

E => .BB

B => .cB

B => .d

I0 state

Add starting production to the I0 State and Compute the Closure.

I0 = closure (E’ => .E)

Since “.” is on the left side of the symbol. It means we have not seen anything on the right-hand side. Therefore, all productions beginning with E will be added in the I0 State because “.” is followed by the non-terminal. So, the modified I0 State will be:

I0 = E’ => .E

E => .BB

Here we can see that “.” is on the left of the variable B. Therefore, all productions beginning with B will be added in the I0 State because “•” is followed by the non-terminal. So, the modified I0 State becomes:

E’ => .E

E => .BB

B => .cB

B => .d

I1 = Here we have applied Goto on (I0 E) = closure (E’ => E.)

Here, the “.” is on the right side of the symbol, so production is reduced so close the state.

I1 becomes E’ => E.

I2 = we have applied Goto on (I0 B) = Closure (E => B.B)

We apply closure and will get all the A production with “.” in the beginning. So I2 becomes:

E => B.B

B => .cB

B => .d

Goto (I2 c) = Closure (B => c.B) (Same as I3)

Goto on (I2 d) = Closure (B => .d) (Same as I4)

I3 = Goto on (I0 c) = Closure (B => c.B)

Add productions starting with B in I3.

B => c.B

Slr Parsing Table Program In C

B => .cB

B => .d

Go to on (I3 c) = Closure (B => c. B) (Same as I3)

Go to on (I3 d) = Closure (B => d.) (Same as I4)

C++ Parsing File

I4 = Go to on (I0 d) = Closure (B => d.) = B => d.

I5 = Go to on (I2 B) = Closure (E => BB.)

I6 = Go to on (I3 B) = Closure (B =>cB.)

Productions are numbered as follows:

E =>BB (1)

B => cB (2)

B => d (3)

C Programming String Parsing

Drawing DFA

SLR(1) Table

Explanations:

Slr Parsing Table Program In C Language

Follow of B = First of B = c and d and Follow of E = $

  • I1 state have the final item which drives E => E and follow(E) = ($), so action (I1 $) = Accept
  • I4 state have the final item which drives B => d and follow(B) = c, d and follow(E) = $ , So action c, d, and $ will be r3
  • I5 state have the final item which drives E => BB and follow(E) = $, So action $ in I5 will be r1
  • I6 state have the final item which drives B => cB and follow(B) = c, d and follow(E) =$, So action c, d, and $ in I6 will be r2.

NOTE:

When a state moves to some other state on terminals, it will correspond to a shift move in the action part.

When a state moves to another state on a variable, it will correspond to the goto move in the go-to part.

When a state has a final item with no transition to the next state, the production is known as reduce production.

/*OPERATOR PRECEDENCE PARSER*/
#include<stdio.h>
#include<conio.h>
void main()
{
char stack[20],ip[20],opt[10][10][1],ter[10];
int i,j,k,n,top=0,col,row;
clrscr();
for(i=0;i<10;i++){stack[i]=NULL; ip[i]=NULL;
for(j=0;j<10;j++){opt[i][j][1]=NULL;}}
printf('Enter the no.of terminals:');
scanf('%d',&n);
printf('nEnter the terminals:');
scanf('%s',ter);
printf('nEnter the table values:n');
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf('Enter the value for %c %c:',ter[i],ter[j]);
scanf('%s',opt[i][j]);
}
}
printf('nOPERATOR PRECEDENCE TABLE:n');
for(i=0;i<n;i++){printf('t%c',ter[i]);}
printf('n');
for(i=0;i<n;i++){printf('n%c',ter[i]);
for(j=0;j<n;j++){printf('t%c',opt[i][j][0]);}}
stack[top]='$';
printf('nEnter the input string:');
scanf('%s',ip);
i=0;
printf('nSTACKtttINPUT STRINGtttACTIONn');
printf('n%sttt%sttt',stack,ip);
while(i<=strlen(ip))
{
for(k=0;k<n;k++)
{
if(stack[top]ter[k])
col=k;
if(ip[i]ter[k])
row=k;
}
if((stack[top]'$')&&(ip[i]'$')){
printf('String is accepted');
break;}
else if((opt[col][row][0]'<') ||(opt[col][row][0]'='))
{ stack[++top]=opt[col][row][0];
stack[++top]=ip[i];
printf('Shift %c',ip[i]);
i++;
}
else{
if(opt[col][row][0]'>')
{
while(stack[top]!='<'){--top;}
top=top-1;
printf('Reduce');
}
else
{
printf('nString is not accepted');
break;
}
}
printf('n');
for(k=0;k<=top;k++)
{
printf('%c',stack[k]);
}
printf('ttt');
for(k=i;k<strlen(ip);k++){
printf('%c',ip[k]);
}
printf('ttt');
}
getch();
}