Resources » Articles/Knowledge Sharing » Computer & Technology

Compiler Design Lab Programs for B.Tech Computer Science and Engineering (CSE)


Posted Date: 22-Mar-2012  Last Updated:   Category: Computer & Technology    
Author: Member Level: Gold    Points: 60


This article on Compiler Design Lab Programs for B.Tech Computer Science is exclusively written to provide JNTU students with one of the difficult to implement programs, i.e. First and Follow functions including the predictive parser table which almost completes 50% of the syllabus from compiler design subject. Hence I have written them on the C compiler, executed them and even provided the obtained also.



Aim: Simulate First and Follow of a Grammar.


Theory:
FIRST function is used to find out the terminal symbols that are possible from both terminal and non-terminal symbols. The application of this function is widely seen in designing the Predictive parser tables that are used in designing compilers for various languages. Even the first compiler C, has an in built predictive parser which is operated through the calculation of the first and follow functions.

Description:
FIRST function is applied to both terminal symbols and non-terminal symbols such that its definition has certain rules to be employed. They are as follows:

1)FIRST of any terminal symbol ‘a’ is the terminal ‘a’ itself.
2)FIRST of non terminal ‘A’ = FIRST of ‘@’, where A -> @ such that @ is a string containing terminals and non-terminals.

FIRST of any entinty is given by FIRST(a) for terminal ‘a’ and FIRST(A) for non-terminal ‘A’. The following program code simulates and computes the FIRST of the Grammar defined by the user at the compile time.

Program for finding only FIRST:

/* Terminals of the grammar */
char T[20];
/* Non Terminals of the grammar */
char NT[20];
/* Table consisting of the FIRST of allNon Terminals */
char FT[10][20];
/* Array consisting of productions of the grammar */
char P[20][10];
/* Number of Productions */
int NOP=0;
/* Number of Non Terminals */
int NONT;
/* Number of Terminals */
int NOT;


/* Function to read grammar from the user */
void getGrammar()
{
int i;
/* Production */
char prod[30];
printf("Enter the grammar::(Type e for epsilon)\n");
printf("Press Enter when completed::\n");

while(1)
{
gets(prod);
if(strcmp(prod,"")==0)
{
break;
}
strcpy(P[NOP++],prod);
}
}

/* Function to get all the terminals and Non terminals of the grammar */
void getTerminalsAndNonTerminals()
{
printf("Enter the Non Terminal symbols used in the grammar::\n");
printf("Dont use any seperators in between::\n");
gets(NT);
NONT = strlen(NT);
printf("Enter the Terminal symbols used in the grammar::\n");
printf("Dont use any seperators in between::\n");
gets(T);
strcat(T,"e");
NOT = strlen(T);
}


int getIndex(char A[],char c)
{
int i=0;
for(i=0;i {
if(A[i]==c)
return i;
}
return -1;
}

void addEpsilon(char c)
{
FT[getIndex(NT,c)][strlen(T)-1]='e';
}

int hasEpsilon(char c)
{
if(FT[getIndex(NT,c)][strlen(T)-1]=='e')
return(1);
return(0);
}

int isNonTerminal(char c)
{
int i;
for(i=0;i {
if(NT[i]==c)
{
return 1;
}
}
return 0;
}

int isTerminal(char c)
{
int i=0;
for(i=0;i {
if(T[i]==c)
return 1;
}
return 0;
}

void computeFirst()
{
int added=0,i,j,k;
char X,elm1,elm2;
clrscr();

for(i=0;i {
for(j=0;j {
FT[i][j]='\0';
}
}

for(i=0;i {
X = P[i][3];
if(X=='e')
{
addEpsilon(P[i][0]);
}

else if(isTerminal(X))
{
FT[getIndex(NT,P[i][0])][getIndex(T,X)]=X;
}
}

for(i=0;i {
X = P[i][3];
if(isNonTerminal(X))
{
for(j=3;j {
X=P[i][j];
if(isTerminal(X))
{
FT[getIndex(NT,P[i][0])][getIndex(T,X)]=X;
break;
}
for(k=0;k {
elm1=FT[getIndex(NT,P[i][0])][k];
elm2=FT[getIndex(NT,X)][k];
if((elm1!=elm2) && elm2!='e')
{
if(elm2!='\0')
{
added=1;
FT[getIndex(NT,P[i][0])][k]=elm2;
}
}
}
if(!hasEpsilon(X))
{
break;
}
}
if(j==strlen(P[i]))
{
added=1;
FT[getIndex(NT,P[i][0])][5]='e';
}
}
if(i==(NOP-1))
{
if(added)
{
i=-1;
added=0;
}
}
}
}

void main()
{
int i,j,k;
clrscr();
getGrammar();
getTerminalsAndNonTerminals();
computeFirst();
printf("THE GIVEN GRAMMAR IS::\n");
for(i=0;i {
printf("%s\n",P[i]);
}

printf("\nThe FIRST for all grammar symbols::\n");
for(i=0;i {
printf("FIRST(%c)={",NT[i]);
for(j=0;j {
if(FT[i][j]!='\0')
printf("%c,",FT[i][j]);
}
printf("\b}\n");
}
getch();
}

Output:
First of a given Grammar

Theory:
FOLLOW function is used to find out the following symbols that are possible from both terminal and non-terminal symbols and these are the symbols that lead the next variables into the operation being done. The application of this function is widely seen in designing the Predictive parser tables that are used in designing compilers for various languages. Even the first compiler C, has an in built predictive parser which is operated through the calculation of the first and follow functions.

Description:
FOLLOW function is applied to non-terminal symbols only such that its definition has certain rules to be employed. They are as follows:

1)FOLLOW of any non-terminal symbol ‘A’ is ‘$’ iff A is the Starting symbol of the Grammar.
2)FOLLOW of non terminal ‘B’ = FIRST of ‘@’, where A -> @B& such that ‘@’ and ‘&’ is a string containing terminals and non-terminals with FIRST (B) not containing EPSILON (e).
3)FOLLOW of non terminal ‘B’ = FOLLOW of ‘A’, where A -> @B& such that ‘@’ and ‘&’ is a string containing terminals and non-terminals with FIRST (B) contains EPSILON (e).

FOLLOW of any entinty is given by FOLLOW(A) for non-terminal ‘A’. The following program code simulates and computes the FOLLOW of the Grammar defined by the user at the compile time.

Program for calculating only FOLLOW:

#include
/* Terminals of the grammar */
char T[20];
/* Non Terminals of the grammar */
char NT[20];
/* Table consisting of the FIRST of allNon Terminals */
char FT[10][20];
/* Array consisting of productions of the grammar */
char P[20][10];
/* Number of Productions */
int NOP=0;
/* Number of Non Terminals */
int NONT;
/* Number of Terminals */
int NOT;
char FLWT[20][10];

/* Function to read grammar from the user */
void getGrammar()
{
int i;
/* Production */
char prod[30];
printf("Enter the grammar::(Type e for epsilon)\n");
printf("Press Enter when completed::\n");

while(1)
{
gets(prod);
if(strcmp(prod,"")==0)
{
break;
}
strcpy(P[NOP++],prod);
}
}

/* Function to get all the terminals and Non terminals of the grammar */
void getTerminalsAndNonTerminals()
{
printf("Enter the Non Terminal symbols used in the grammar::\n");
printf("Dont use any seperators in between::\n");
gets(NT);
NONT = strlen(NT);
printf("Enter the Terminal symbols used in the grammar::\n");
printf("Dont use any seperators in between::\n");
gets(T);
strcat(T,"e");
NOT = strlen(T);
}

void getFirst()
{
int i,c,rindex;

for(i=0;i {
rindex = getIndex(NT,NT[i]);
printf("Enter the symbols in FIRST(%c)(Press cntrl+Z at the end)::\n",NT[i]);
while((c=getchar())!=EOF)
{
FT[rindex][getIndex(T,c)]=c;
}
}
}

int getIndex(char A[],char c)
{
int i=0;
for(i=0;i {
if(A[i]==c)
return i;
}
return -1;
}

int hasEpsilon(char c)
{
if(FT[getIndex(NT,c)][strlen(T)-1]=='e')
return(1);
return(0);
}

int isNonTerminal(char c)
{
int i;
for(i=0;i {
if(NT[i]==c)
{
return 1;
}
}
return 0;
}

int isTerminal(char c)
{
int i=0;
for(i=0;i {
if(T[i]==c)
return 1;
}
return 0;
}

void computeFollow()
{
int len,i,j,k,added=0;
char sym1,sym2,elm1,elm2,sym;
printf("What is the start symbol of the grammar?::\n");
FLWT[getIndex(NT,getchar())][NOT-1]='$';

for(i=0;i {
len=strlen(P[i]);
for(j=3;j {
sym1=P[i][j];
sym2=P[i][j+1];
if(isNonTerminal(sym1) && isTerminal(sym2))
{
FLWT[getIndex(NT,sym1)][getIndex(T,sym2)]=sym2;
}
}
}

for(i=0;i {
len=strlen(P[i]);
for(j=3;j {
sym1=P[i][j];
sym2=P[i][j+1];
if(isNonTerminal(sym1) && isNonTerminal(sym2))
{
for(k=0;k {
elm1=FLWT[getIndex(NT,sym1)][k];
elm2=FT[getIndex(NT,sym2)][k];
if(elm1!=elm2)
{
if(elm2!='\0' && elm2!='e')
{
FLWT[getIndex(NT,sym1)][k]=elm2;
}
}
}
}
}
}

for(i=0;i {
sym1=P[i][strlen(P[i])-1];
if(isNonTerminal(sym1))
{
sym2=P[i][0];
for(k=0;k {
elm1=FLWT[getIndex(NT,sym1)][k];
elm2=FLWT[getIndex(NT,sym2)][k];
if(elm1!=elm2)
{
if(elm2!='\0' && elm2!='e')
{
added=1;
FLWT[getIndex(NT,sym1)][k]=elm2;
}
}
}
}

sym=P[i][strlen(P[i])-1];
if(isNonTerminal(sym) && hasEpsilon(sym))
{
sym1=P[i][strlen(P[i])-2];
if(isNonTerminal(sym1))
{
sym2=P[i][0];
for(k=0;k {
elm1=FLWT[getIndex(NT,sym1)][k];
elm2=FLWT[getIndex(NT,sym2)][k];
if(elm1!=elm2)
{
if(elm2!='\0' && elm2!='e')
{
added=1;
FLWT[getIndex(NT,sym1)][k]=elm2;
}
}
}
}
}
if(i==(NOP-1))
{
if(added)
{
i=-1;
added=0;
}
}
}
}

void main()
{
int i,j,k;
clrscr();
getGrammar();
getTerminalsAndNonTerminals();
getFirst();
printf("THE GIVEN GRAMMAR IS::\n");
for(i=0;i {
printf("%s\n",P[i]);
}

printf("\nThe FIRST for all grammar symbols::\n");
for(i=0;i {
printf("FIRST(%c)={",NT[i]);
for(j=0;j {
if(FT[i][j]!='\0')
printf("%c,",FT[i][j]);
}
printf("\b}\n");
}

computeFollow();
printf("\nThe FOLLOW for all grammar symbols::\n");
for(i=0;i {
printf("FOLLOW(%c)={",NT[i]);
for(j=0;j {
if(FLWT[i][j]!='\0')
printf("%c,",FLWT[i][j]);
}
printf("\b}\n");
}
getch();
}

Output:
Follow of a given Grammar

Program to compute FIRST and FOLLOW within the same program

char T[]="+*()de";
char NT[]="EATBF";
char FT[5][6];
char FLWT[5][6];
char P[8][10]={ "E->TA",
"A->+TA",
"A->e",
"T->FB",
"B->*FB",
"B->e",
"F->(E)",
"F->d" };

int getIndex(char A[],char c)
{
int i=0;
for(i=0;i {
if(A[i]==c)
return i;
}
return -1;
}

void addEpsilon(char c)
{
FT[getIndex(NT,c)][5]='e';
}

int hasEpsilon(char c)
{
if(FT[getIndex(NT,c)][5]=='e')
return(1);
return(0);
}

int isNonTerminal(char c)
{
int i;
for(i=0;i {
if(NT[i]==c)
{
return 1;
}
}
return 0;
}

int isTerminal(char c)
{
int i=0;
for(i=0;i {
if(T[i]==c)
return 1;
}
return 0;
}

void ComputeFollow()
{
int len,i,j,k,added=0;
char sym1,sym2,elm1,elm2,sym;
FLWT[getIndex(NT,'E')][5]='$';
for(i=0;i<8;i++)
{
len=strlen(P[i]);
for(j=3;j {
sym1=P[i][j];
sym2=P[i][j+1];
if(isNonTerminal(sym1) && isTerminal(sym2))
{
FLWT[getIndex(NT,sym1)][getIndex(T,sym2)]=sym2;
}
}
}

for(i=0;i<8;i++)
{
len=strlen(P[i]);
for(j=3;j {
sym1=P[i][j];
sym2=P[i][j+1];
if(isNonTerminal(sym1) && isNonTerminal(sym2))
{
for(k=0;k<6;k++)
{
elm1=FLWT[getIndex(NT,sym1)][k];
elm2=FT[getIndex(NT,sym2)][k];
if(elm1!=elm2)
{
if(elm2!='\0' && elm2!='e')
{
FLWT[getIndex(NT,sym1)][k]=elm2;
}
}
}
}
}
}

for(i=0;i<8;i++)
{
sym1=P[i][strlen(P[i])-1];
if(isNonTerminal(sym1))
{
sym2=P[i][0];
for(k=0;k<6;k++)
{
elm1=FLWT[getIndex(NT,sym1)][k];
elm2=FLWT[getIndex(NT,sym2)][k];
if(elm1!=elm2)
{
if(elm2!='\0' && elm2!='e')
{
added=1;
FLWT[getIndex(NT,sym1)][k]=elm2;
}
}
}
}

sym=P[i][strlen(P[i])-1];
if(isNonTerminal(sym) && hasEpsilon(sym))
{
sym1=P[i][strlen(P[i])-2];
if(isNonTerminal(sym1))
{
sym2=P[i][0];
for(k=0;k<6;k++)
{
elm1=FLWT[getIndex(NT,sym1)][k];
elm2=FLWT[getIndex(NT,sym2)][k];
if(elm1!=elm2)
{
if(elm2!='\0' && elm2!='e')
{
added=1;
FLWT[getIndex(NT,sym1)][k]=elm2;
}
}
}
}

if(i==7)
{
if(added)
{
i=-1;
added=0;
}
}
}
}
}

void ComputeFirst()
{
int added=0,i,j,k;
char X,elm1,elm2;
clrscr();

for(i=0;i<5;i++)
{
for(j=0;j<6;j++)
{
FT[i][j]='\0';
}
}

for(i=0;i<8;i++)
{
X = P[i][3];
if(X=='e')
{
addEpsilon(P[i][0]);
}

else if(isTerminal(X))
{
FT[getIndex(NT,P[i][0])][getIndex(T,X)]=X;
}
}

for(i=0;i<8;i++)
{
X = P[i][3];
if(isNonTerminal(X))
{
for(j=3;j {
X=P[i][j];
for(k=0;k<5;k++)
{
elm1=FT[getIndex(NT,P[i][0])][k];
elm2=FT[getIndex(NT,X)][k];
if(elm1!=elm2)
{
if(elm2!='\0')
{
added=1;
FT[getIndex(NT,P[i][0])][k]=elm2;
}
}
}
if(!hasEpsilon(X))
{
break;
}
}
if(j==strlen(P[i]))
{
added=1;
FT[getIndex(NT,P[i][0])][5]='e';
}
}
if(i==7)
{
if(added)
{
i=-1;
added=0;
}
}
}
}
void main()
{
int i,j;
ComputeFirst();
printf("THE GIVEN GRAMMAR IS::\n");
for(i=0;i<8;i++)
{
printf("%s\n",P[i]);
}

printf("\nThe FIRST for all grammar symbols::\n");
for(i=0;i<5;i++)
{
printf("FIRST(%c)={",NT[i]);
for(j=0;j<6;j++)
{
if(FT[i][j]!='\0')
printf("%c,",FT[i][j]);
}
printf("\b}\n");
}

ComputeFollow();
printf("\nThe FOLLOW for all grammar symbols::\n");
for(i=0;i<5;i++)
{
printf("FOLLOW(%c)={",NT[i]);
for(j=0;j<6;j++)
{
if(FLWT[i][j]!='\0')
printf("%c,",FLWT[i][j]);
}
printf("\b}\n");
}
getch();
}

Output:
First and Follow of a given Grammar

Aim: Simulate a Predictive Parser table for a given Grammar:


Theory:
Predictive parse table is used in designing compilers for various languages through one of the most prominent and widely used compiler namely predictive parser. We use the parsing technique developed through the predictive to detect whether a given string can be accepted or not. Even the first compiler C, has an in built predictive parser which is operated through the calculation of the first and follow functions. Not only C compiler, many other modern compilers are being developed based on the action sequence generated through a predictive parser.

Description:
The following program is to represent the moves of a Parser through a Parsing Table. There are some predefined rules to configure the moves of a parser. We need to maintain a stack array for defning the productions and an input buffer array to accept the input string in a sequential manner. The conditions for deciding whether an input operation is syntactically right or not are:

1)If the element in the top of stack is equal to ‘$’ and also the present element in the input buffer is ‘$’, then directly convey that the string is syntactically valid one.
2)If th element in the top of the stack is equal to the present element in the input buffer other that ‘$’, then POP out the top most element of the stack and increment the input buffer’s current position, i.e. make the current element as the next element in the sequence.
3)If the element in the top of the stack is not equal to the presnt element in the input buffer, then, move all the elements of the input buffer in reverse order to the stack.

The program that follows does all the above verifications and finally conveys whether a given input string of a respective Grammar is valid with respect to syntax or not.

Program:

char stck[20],ibuff[30];
int top=-1,ip=0;

void printLine()
{
int i=0;
printf("\n\t\t");
for(i=0;i<40;i++)
printf("-");
printf("\n");
}
void printStack()
{
int i=0;
printf("\n\t\t");
for(i=0;i<=top;i++)
{
printf("%c",stck[i]);
}
printf("\t\t");
}

void printInputBuffer()
{
int i=0;
for(i=0;i printf(" ");
for(i=ip;i {
printf("%c",ibuff[i]);
}
printf("\t\t");
}

void printOutput(char P[])
{
printf("%s",P);
}

int getIndex(char arr[],char c)
{
int i=0;
while(i {
if(arr[i]==c)
return i;
i++;
}
return -1;
}

void main()
{
char NT[5]="EATBF";
char T[6]="i+*()$";
char P[8][10]={"E->TA",
"A->+TA",
"A->e",
"T->FB",
"B->*FB",
"B->e",
"F->(E)",
"F->i"};
char PT[5][6]={{0,-1,-1,0,-1,-1},
{-1,1,-1,-1,2,2},
{3,-1,-1,3,-1,-1},
{-1,5,4,-1,5,5},
{7,-1,-1,6,-1,-1}};
int ptentry,i;
clrscr();
stck[++top]='$';
stck[++top]='E';
printf("Enter the string to be parsed:(Type $ at the end)\n");
gets(ibuff);
ip=0;
printLine();
printf("\t\t\tTHE GIVEN GRAMMAR\n");
printLine();
for(i=0;i<8;i++)
printf("\t\t%s\n",P[i]);
printf("\n");
printf("\n");
printf("\t\tMoves of the Parser are:\n");
printLine();
printf("\t\tSTACK\t\tINPUT\t\tOUTPUT\n");
printLine();
printStack();
printInputBuffer();

while(1)
{
if(stck[top]== '$' && ibuff[ip]=='$')
{
printf("\n\n\t\tGiven string is syntactically valid::\n");
exit(0);
}

else if(stck[top]==ibuff[ip])
{
top--;
ip++;
printStack();
printInputBuffer();
}

else if(stck[top] >= 'A' && stck[top]<= 'Z')
{
ptentry = PT[getIndex(NT,stck[top])][getIndex(T,ibuff[ip])];
if(ptentry==-1)
{
printStack();
printInputBuffer();
printOutput("ERROR");
printf("\n\n\t\tGiven string is syntactically invalid:\n");
exit(0);
}

else
{
top--;
for(i=strlen(P[ptentry])-1;i>=3;i--)
{
if(P[ptentry][i]!='e')
{
stck[++top]=P[ptentry][i];
}
}
printStack();
printInputBuffer();
printOutput(P[ptentry]);
}
}
else
{
printf("\n\n\t\tGiven string is syntactically invalid:\n");
exit(-1);
}
}
}

Aim: Program to design and simulate a FA that accepts keywords like char, case, int etc.


Theory:
This program is just a simulation of a finite machine which is the predecessor of the compiler designing. Basically, CD is developed from the deterministic finite automation and non-deterministic finite automation techniques in combination with the concept of the regular expressions, context free grammars, etc. So, this program is highly useful to understand the way a machine changes its states to finally attain its final state, thus deciding whether the string is valid under the prescribed grammar conditions designed or not.

Description:
This program simulates a finite automata that accepts only C identified keywords. Identified keywords in C means those keywords that cannot be used as variable names in declaration part of a program. We simulate the requirement in the following way meantioned here. Firstly we gather all the information regarding the states and the transitions which need to be done from one state to the another. Consider the case of the keyword, “char”, to move from intial state 0 to 1, we need to check whether the first input variable given is “c” or not and then we move to state 2 if the next variable in sequence is “h”. Similarly, we check up to the last input symbol such that if the State Transition of the last input symbol fetches to a Final State, then, we can say that the input sent by the user is accepted and hence we give a justification to our program. The same concept is programmaticall achieved as shown below.

Program:

#include
#include
int main()
{
int t[10][26],i,j,q,n,a;
char c,ch[10];
clrscr();
for(i=0;i<10;i++)
for(j=0;j<26;j++)
t[i][j]=-1;
q=0;
c='c';
t[0][c%97]=1;
c='h';
t[1][c%97]=2;
c='a';
t[2][c%97]=3;
c='r';
t[3][c%97]=4;
c='a';
t[1][c%97]=5;
c='s';
t[5][c%97]=6;
c='e';
t[6][c%97]=7;
c='i';
t[0][c%97]=8;
c='n';
t[8][c%97]=9;
c='t';
t[9][c%97]=10;
printf("\n enter the string of characters:");
gets(ch);
n=strlen(ch);
for(i=0;i{
a=ch[i]%97;
if(t[q][a]==-1)
{
}
else {
q=t[q][a];
printf("%c next state is :%d\n",ch[i],q);
}
}
if(q==4 || q==7 || q==10)
printf("\n the string is accepted");
else{
printf("\n the string is not accepeted");
}
getch();
return 0;
}

output:
DFA To accept Keywords

For Lab programs of Operating Systems(OS), please visit the following page:
Operating Systems Lab Programs for B.Tech Computer Science and Engineering (CSE)


Did you like this resource? Share it with your friends and show your love!




Responses to "Compiler Design Lab Programs for B.Tech Computer Science and Engineering (CSE)"
Feedbacks      

Post Comment:




  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:   Sign In to fill automatically.
    Email: (Will not be published, but required to validate comment)



    Type the numbers and letters shown on the left.


    Submit Article     Return to Article Index

    Awards & Gifts
    Active Members
    TodayLast 7 Daysmore...

    ISC Technologies, Kochi - India. Copyright © All Rights Reserved.