15-09-2021

Slr Parsing Table Program In C

/* C program to implement Simple LR Parser. */
#include<stdio.h>
#include<string.h>
int i,j,k,m,n=0,o,p,ns=0,tn=0,rr=0,ch=0;
char read[15][10],gl[15],gr[15][10],temp,templ[15],tempr[15][10],*ptr,temp2[5],dfa[15][15];
struct states
{
char lhs[15],rhs[15][10];
int n;
}I[15];
int compstruct(struct states s1,struct states s2)
{
int t;
if(s1.n!=s2.n)
return 0;
if( strcmp(s1.lhs,s2.lhs)!=0 )
return 0;
for(t=0;t<s1.n;t++)
if( strcmp(s1.rhs[t],s2.rhs[t])!=0 )
return 0;
return 1;
}
void moreprod()
{
int r,s,t,l1=0,rr1=0;
char *ptr1,read1[15][10];
for(r=0;r<I[ns].n;r++)
{
ptr1=strchr(I[ns].rhs[l1],'.');
t=ptr1-I[ns].rhs[l1];
if( t+1strlen(I[ns].rhs[l1]) )
{
l1++;
continue;
}
temp=I[ns].rhs[l1][t+1];
l1++;
for(s=0;s<rr1;s++)
if( tempread1[s][0] )
break;
if(srr1)
{
read1[rr1][0]=temp;
rr1++;
}
else
continue;
for(s=0;s<n;s++)
{
if(gl[s]temp)
{
I[ns].rhs[I[ns].n][0]='.';
I[ns].rhs[I[ns].n][1]=NULL;
strcat(I[ns].rhs[I[ns].n],gr[s]);
I[ns].lhs[I[ns].n]=gl[s];
I[ns].lhs[I[ns].n+1]=NULL;
I[ns].n++;
}
}
}
}
void canonical(int l)
{
int t1;
char read1[15][10],rr1=0,*ptr1;
for(i=0;i<I[l].n;i++)
{
temp2[0]='.';
ptr1=strchr(I[l].rhs[i],'.');
t1=ptr1-I[l].rhs[i];
if( t1+1strlen(I[l].rhs[i]) )
continue;
temp2[1]=I[l].rhs[i][t1+1];
temp2[2]=NULL;
for(j=0;j<rr1;j++)
if( strcmp(temp2,read1[j])0 )
break;
if(jrr1)
{
strcpy(read1[rr1],temp2);
read1[rr1][2]=NULL;
rr1++;
}
else
continue;
for(j=0;j<I[0].n;j++)
{
ptr=strstr(I[l].rhs[j],temp2);
if( ptr )
{
templ[tn]=I[l].lhs[j];
templ[tn+1]=NULL;
strcpy(tempr[tn],I[l].rhs[j]);
tn++;
}
}
for(j=0;j<tn;j++)
{
ptr=strchr(tempr[j],'.');
p=ptr-tempr[j];
tempr[j][p]=tempr[j][p+1];
tempr[j][p+1]='.';
I[ns].lhs[I[ns].n]=templ[j];
I[ns].lhs[I[ns].n+1]=NULL;
strcpy(I[ns].rhs[I[ns].n],tempr[j]);
I[ns].n++;
}
moreprod();
for(j=0;j<ns;j++)
{
//if ( memcmp(&I[ns],&I[j],sizeof(struct states))1 )
if( compstruct(I[ns],I[j])1 )
{
I[ns].lhs[0]=NULL;
for(k=0;k<I[ns].n;k++)
I[ns].rhs[k][0]=NULL;
I[ns].n=0;
dfa[l][j]=temp2[1];
break;
}
}
if(j<ns)
{
tn=0;
for(j=0;j<15;j++)
{
templ[j]=NULL;
tempr[j][0]=NULL;
}
continue;
}
dfa[l][j]=temp2[1];
printf('nnI%d :',ns);
for(j=0;j<I[ns].n;j++)
printf('nt%c -> %s',I[ns].lhs[j],I[ns].rhs[j]);
getch();
ns++;
tn=0;
for(j=0;j<15;j++)
{
templ[j]=NULL;
tempr[j][0]=NULL;
}
}
}
void main()
{
FILE *f;
int l;
clrscr();
for(i=0;i<15;i++)
{
I[i].n=0;
I[i].lhs[0]=NULL;
I[i].rhs[0][0]=NULL;
dfa[i][0]=NULL;
}
f=fopen('tab6.txt','r');
while(!feof(f))
{
fscanf(f,'%c',&gl[n]);
fscanf(f,'%sn',gr[n]);
n++;
}
printf('THE GRAMMAR IS AS FOLLOWSn');
for(i=0;i<n;i++)
printf('tttt%c -> %sn',gl[i],gr[i]);
I[0].lhs[0]='Z';
strcpy(I[0].rhs[0],'.S');
I[0].n++;
l=0;
for(i=0;i<n;i++)
{
temp=I[0].rhs[l][1];
l++;
for(j=0;j<rr;j++)
if( tempread[j][0] )
break;
if(jrr)
{
read[rr][0]=temp;
rr++;
}
else
continue;
for(j=0;j<n;j++)
{
if(gl[j]temp)
{
I[0].rhs[I[0].n][0]='.';
strcat(I[0].rhs[I[0].n],gr[j]);
I[0].lhs[I[0].n]=gl[j];
I[0].n++;
}
}
}
ns++;
printf('nI%d :n',ns-1);
for(i=0;i<I[0].n;i++)
printf('t%c -> %sn',I[0].lhs[i],I[0].rhs[i]);
for(l=0;l<ns;l++)
canonical(l);
printf('nnttPRESS ANY KEY FOR DFA TABLE');
getch();
clrscr();
printf('tttDFA TABLE IS AS FOLLOWSnnn');
for(i=0;i<ns;i++)
{
printf('I%d : ',i);
for(j=0;j<ns;j++)
if(dfa[i][j]!='0')
printf('%c'->I%d | ',dfa[i][j],j);
printf('nnn');
}
printf('nnnttPRESS ANY KEY TO EXIT');
getch();
}
Input File For SLR Parser:
S S+T
S T
T T*F
T F
F (S)
F t


Rules to Build LL(1) Parsing Table. To construct LL(1) Parsing Table, we must have knowledge of FIRST and FOLLOW of a grammar. For all terminal in insert to; If contains ‘Є’, then for all terminal in add to; LL(1) Parsing Table Program in C. The program reads grammar from a file “text.txt”. “^” is used to represent epsilon. The program assumes that the input grammar is LL(1). C PROGRAM - OPERATOR PRECEDENCE PARSER /.OPERATOR PRECEDENCE PARSER./ #include. OPERATOR PRECEDENCE TABLE; SLR PARSING TABLE; C program- LL1 grammar.

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

SlrSlr Parsing Table Program In C

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

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)

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

Slr Parsing Table Program In C

Productions are numbered as follows:

E =>BB (1)

B => cB (2)

B => d (3)

Drawing DFA

SLR(1) Table

C Parsing String

Explanations:

Slr Parsing Table Program In C++

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.
Slr Parsing Table Program In CSlr

NOTE:

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

Slr Parsing Table Program In C Compiler

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

Slr Parsing Table Program In California

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