/* 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

Compiler Design Tutorial

/. SLR parser for the grammar E-E+T (1) E-T (2) T-T.F (3) T-F (4) F-(E) (5) F-ID (6)./ /. Stack structure and fuctions./ /. The only thing important here is that the value associated with each name of the macro should be unique. They have no realtion to the states in.

Compiler Design Useful Resources

Program to Construct LL (1) Parsing Table in c. LL (1) Parser is Top-Down Parser. It deals with a class of grammar called LL (1). The first ‘L’ denotes the input is scanned from left to right, second ‘L’ denotes leftmost derivation of input and ‘1’ denotes the number of lookaheads used to make the decision. Before building LL (1.
D) Differentiate SLR and canonical LR parsing. Ans: In order to construct the SLR parsing table, Construct the sets of LR(0) items using CLOSURE function and GOTO function and construct parsing table using LR(0) items. In CLR, the construction of parsing table is done with LR(1) items. CLR parser is more powerful than SLR. E) What is left.
SLR Parser Examples. Example 1: Parsing of the input string id. id + id using the SLR parser table for the grammar.

Selected Reading

In the previous chapter, we understood the basic concepts involved in parsing. In this chapter, we will learn the various types of parser construction methods available.

Parsing can be defined as top-down or bottom-up based on how the parse-tree is constructed.

Top-Down Parsing

We have learnt in the last chapter that the top-down parsing technique parses the input, and starts constructing a parse tree from the root node gradually moving down to the leaf nodes. The types of top-down parsing are depicted below:

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.

This parsing technique is regarded recursive as it uses context-free grammar which is recursive in nature.

Back-tracking

Top- down parsers start from the root node (start symbol) and match the input string against the production rules to replace them (if matched). To understand this, take the following example of CFG:

For an input string: read, a top-down parser, will behave like this:

It will start with S from the production rules and will match its yield to the left-most letter of the input, i.e. ‘r’. The very production of S (S → rXd) matches with it. So the top-down parser advances to the next input letter (i.e. ‘e’). The parser tries to expand non-terminal ‘X’ and checks its production from the left (X → oa). It does not match with the next input symbol. So the top-down parser backtracks to obtain the next production rule of X, (X → ea).

Now the parser matches all the input letters in an ordered manner. The string is accepted.

Predictive Parser

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

In recursive descent parsing, the parser may have more than one production to choose from for a single instance of input, whereas in predictive parser, each step has at most one production to choose. There might be instances where there is no production matching the input string, making the parsing procedure to fail.

LL Parser

An LL Parser accepts LL grammar. LL grammar is a subset of context-free grammar but with some restrictions to get the simplified version, in order to achieve easy implementation. LL grammar can be implemented by means of

Slr Parsing Table Program In C