Compiler Source Code

//AIM: Construction of Recursive Descent Parser

#include<stdio.h>

#include<conio.h>

char input[100];

int i,l;

void main()

{

clrscr();

printf("\nRecursive descent parsing for the following grammar\n"); printf("\nE->TE'\nE'->+TE'/@\nT->FT'\nT'->*FT'/@\nF->(E)/ID\n"); printf("\nEnter the string to be checked:"); gets(input);

if(E())

{

if(input[i+1]=='\0')

printf("\nString is accepted");

else

printf("\nString is not accepted");

}

else

printf("\nString not accepted");

getch();

}

E()

{

if(T())

{

if(EP())

return(1);

else

return(0);

}

else

return(0);

}

EP()

{

if(input[i]=='+')

{

i++;

if(T())

{

if(EP())

return(1);

else

return(0);

}

else

return(0);

}

else

return(1);

}

T()

{

if(F())

{

if(TP())

return(1);

else

return(0);

}

else

return(0);

}

TP()

{

if(input[i]=='*')

{

i++;

if(F())

{

if(TP())

return(1);

else

return(0);

}

else

return(0);

}

else

return(1);

}

F()

{

if(input[i]=='(')

{

i++;

if(E())

{

if(input[i]==')')

{

i++;

return(1);

}

else

return(0);

}

else

return(0);

}

else if(input[i]>='a'&&input[i]<='z'||input[i]>='A'&&input[i]<='Z')

{

i++;

return(1);

}

else

return(0);

}

/******************OUTPUT******************

Recursive descent parsing for the following grammar

E->TE'

E'->+TE'/@

T->FT'

T'->*FT'/@

F->(E)/ID

Enter the string to be checked:T+F*F

String is accepted

***************************************/

/*lex program to count number of words*/

#include<stdio.h>

#include<string.h>

int i = 0;

/* Rules Section*/

([a-zA-Z0-9])* {i++;} /* Rule for counting

number of words*/

"\n" {printf("%d Number of Words Count \n", i); i = 0;}

int yywrap(void){}

int main()

{

// The function that starts the analysis

yylex();

return 0;

}

//Construction of Shift-Reduce Parser

#include<stdio.h>

#include<conio.h>

#include<string.h>

//#include

char ip_sym[15],stack[15];

int ip_ptr=0,st_ptr=0,len,i;

char temp[2],temp2[2];

char act[15];

void check();

void main()

{

clrscr();

printf("\n\t\t SHIFT REDUCE PARSER\n");

printf("\n GRAMMER\n");

printf("\n E->E+E\n E->E/E");

printf("\n E->E*E\n E->a/b");

printf("\n enter the input symbol:\t");

gets(ip_sym);

printf("\n\t stack implementation table");

printf("\n stack \t\t input symbol\t\t action");

printf("\n________\t\t____________\t\t____________\n");

printf("\n $\t\t%s$\t\t\t--",ip_sym);

strcpy(act,"shift");

temp[0]=ip_sym[ip_ptr];

temp[1]='\0';

strcat(act,temp);

len=strlen(ip_sym);

for(i=0;i<=len-1;i++)

{

stack[st_ptr]=ip_sym[ip_ptr];

stack[st_ptr+1]='\0';

ip_sym[ip_ptr]=' ';

ip_ptr++;

printf("\n $%s\t\t%s$\t\t\t%s",stack,ip_sym,act);

strcpy(act,"shift");

temp[0]=ip_sym[ip_ptr];

temp[1]='\0';

strcat(act,temp);

check();

st_ptr++;

}

st_ptr++;

check();

}

void check()

{

int flag=0;

temp2[0]=stack[st_ptr];

temp2[1]='\0';

if((!strcmpi(temp2,"a"))||(!strcmpi(temp2,"b")))

{

stack[st_ptr]='E';

if(!strcmpi(temp2,"a"))

printf("\n $%s\t\t%s$\t\t\tE->a",stack,ip_sym);

else

printf("\n $%s\t\t%s$\t\t\tE->b",stack,ip_sym);

flag=1;

}

if((!strcmpi(temp2,"+"))||(strcmpi(temp2,"*"))||(!strcmpi(temp2,"/")))

{

flag=1;

}

if((!strcmpi(stack,"E+E"))||(!strcmpi(stack,"E\E"))||(!strcmpi(stack,"E*E")))

{

strcpy(stack,"E");

st_ptr=0;

if(!strcmpi(stack,"E+E"))

printf("\n $%s\t\t%s$\t\t\tE->E+E",stack,ip_sym);

else

if(!strcmpi(stack,"E\E"))

printf("\n $%s\t\t%s$\t\t\tE->E\E",stack,ip_sym);

else

if(!strcmpi(stack,"E*E"))

printf("\n $%s\t\t%s$\t\t\tE->E*E",stack,ip_sym);

else

printf("\n $%s\t\t%s$\t\t\tE->E+E",stack,ip_sym);

flag=1;

}

if(!strcmpi(stack,"E")&&ip_ptr==len)

{

printf("\n $%s\t\t%s$\t\t\tACCEPT",stack,ip_sym);

getch();

exit(0);

}

if(flag==0)

{

printf("\n%s\t\t\t%s\t\t reject",stack,ip_sym);

exit(0);

}

return;

}

SHIFT REDUCE PARSER

GRAMMER

E->E+E

E->E/E

E->E*E

E->a/b

enter the input symbol: a+b

stack implementation table

stack input symbol action

________ ____________ ____________

$ a+b$ --

$a +b$ shifta

$E +b$ E->a

$E+ b$ shift+

$E+b $ shiftb

$E+E $ E->b

$E $ E->E+E

$E $ ACCEPT

**********************/

/*****DFA exp-2********************************/

#include<stdio.h>

#include<conio.h>

#include<strings.h>

void main() {

int table[2][2],i,j,l,status=0,success;

char input[100];

printf("To implementing DFA of language (a+aa*b)*\n Enter Input String:”);

table[0][0]=1;

table[0][1]=-1;

table[1][0]=1;

table[1][1]=0;

scanf("%s",input);

l=strlen(input);

for (i=0;i<l;i++) {

if(input[i]!='a'&&input[i]!='b') {

printf("The entered Value is wrong");

getch();

exit(0);

}

if(input[i]=='a')

status=table[status][0]; else

status=table[status][1];

if(status==-1) {

printf("String not Accepted");

break;

}

if(i==l)

printf("String Accepted");

getch();

}

/*****************INFIX EXP-1*************************/

#include<stdio.h>

#include<ctype.h>

char stack[100];

int top = -1;

void push(char x)

{

stack[++top] = x;

}

char pop()

{

if(top == -1)

return -1;

else

return stack[top--];

}

int priority(char x)

{

if(x == '(')

return 0;

if(x == '+' || x == '-')

return 1;

if(x == '*' || x == '/')

return 2;

return 0;

}

int main()

{

char exp[100];

char *e, x;

printf("Enter the expression : ");

scanf("%s",exp);

printf("\n");

e = exp;

while(*e != '\0')

{

if(isalnum(*e))

printf("%c ",*e);

else if(*e == '(')

push(*e);

else if(*e == ')')

{

while((x = pop()) != '(')

printf("%c ", x);

}

else

{

while(priority(stack[top]) >= priority(*e))

printf("%c ",pop());

push(*e);

}

e++;

}

while(top != -1)

{

printf("%c ",pop());

}

getch();

return 0;

}

/******************Recursive exp-4***************************/

#include<stdio.h>

#include<conio.h>

char input[100];

int i,l;

void main()

{

clrscr();

printf("\nRecursive descent parsing for the following grammar\n"); printf("\nE->TE'\nE'->+TE'/@\nT->FT'\nT'->*FT'/@\nF->(E)/ID\n"); printf("\nEnter the string to be checked:"); gets(input);

if(E())

{

if(input[i+1]=='\0')

printf("\nString is accepted");

else

printf("\nString is not accepted");

}

else

printf("\nString not accepted");

getch();

}

E()

{

if(T())

{

if(EP())

return(1);

else

return(0);

}

else

return(0);

}

EP()

{

if(input[i]=='+')

{

i++;

if(T())

{

if(EP())

return(1);

else

return(0);

}

else

return(0);

}

else

return(1);

}

T()

{

if(F())

{

if(TP())

return(1);

else

return(0);

}

else

return(0);

}

TP()

{

if(input[i]=='*')

{

i++;

if(F())

{

if(TP())

return(1);

else

return(0);

}

else

return(0);

}

else

return(1);

}

F()

{

if(input[i]=='(')

{

i++;

if(E())

{

if(input[i]==')')

{

i++;

return(1);

}

else

return(0);

}

else

return(0);

}

else if(input[i]>='a'&&input[i]<='z'||input[i]>='A'&&input[i]<='Z')

{

i++;

return(1);

}

else

return(0);

}

/*********Shift Reduce Exp-5***********************/

#include<stdio.h>

#include<conio.h>

#include<string.h>

//#include

char ip_sym[15],stack[15];

int ip_ptr=0,st_ptr=0,len,i;

char temp[2],temp2[2];

char act[15];

void check();

void main()

{

clrscr();

printf("\n\t\t SHIFT REDUCE PARSER\n");

printf("\n GRAMMER\n");

printf("\n E->E+E\n E->E/E");

printf("\n E->E*E\n E->a/b");

printf("\n enter the input symbol:\t");

gets(ip_sym);

printf("\n\t stack implementation table");

printf("\n stack \t\t input symbol\t\t action");

printf("\n________\t\t____________\t\t____________\n");

printf("\n $\t\t%s$\t\t\t--",ip_sym);

strcpy(act,"shift");

temp[0]=ip_sym[ip_ptr];

temp[1]='\0';

strcat(act,temp);

len=strlen(ip_sym);

for(i=0;i<=len-1;i++)

{

stack[st_ptr]=ip_sym[ip_ptr];

stack[st_ptr+1]='\0';

ip_sym[ip_ptr]=' ';

ip_ptr++;

printf("\n $%s\t\t%s$\t\t\t%s",stack,ip_sym,act);

strcpy(act,"shift");

temp[0]=ip_sym[ip_ptr];

temp[1]='\0';

strcat(act,temp);

check();

st_ptr++;

}

st_ptr++;

check();

}

void check()

{

int flag=0;

temp2[0]=stack[st_ptr];

temp2[1]='\0';

if((!strcmpi(temp2,"a"))||(!strcmpi(temp2,"b")))

{

stack[st_ptr]='E';

if(!strcmpi(temp2,"a"))

printf("\n $%s\t\t%s$\t\t\tE->a",stack,ip_sym);

else

printf("\n $%s\t\t%s$\t\t\tE->b",stack,ip_sym);

flag=1;

}

if((!strcmpi(temp2,"+"))||(strcmpi(temp2,"*"))||(!strcmpi(temp2,"/")))

{

flag=1;

}

if((!strcmpi(stack,"E+E"))||(!strcmpi(stack,"E\E"))||(!strcmpi(stack,"E*E")))

{

strcpy(stack,"E");

st_ptr=0;

if(!strcmpi(stack,"E+E"))

printf("\n $%s\t\t%s$\t\t\tE->E+E",stack,ip_sym);

else

if(!strcmpi(stack,"E\E"))

printf("\n $%s\t\t%s$\t\t\tE->E\E",stack,ip_sym);

else

if(!strcmpi(stack,"E*E"))

printf("\n $%s\t\t%s$\t\t\tE->E*E",stack,ip_sym);

else

printf("\n $%s\t\t%s$\t\t\tE->E+E",stack,ip_sym);

flag=1;

}

if(!strcmpi(stack,"E")&&ip_ptr==len)

{

printf("\n $%s\t\t%s$\t\t\tACCEPT",stack,ip_sym);

getch();

exit(0);

}

if(flag==0)

{

printf("\n%s\t\t\t%s\t\t reject",stack,ip_sym);

exit(0);

}

return;

}

//7.Calculation of FOLLOW set of all non-terminals in a given grammar

#include<stdio.h>

#include<string.h>

int i,j,l,m,n=0,o,p,nv,z=0,x=0;

char str[10],temp,temp2[10],temp3[20],*ptr;

struct prod

{

char lhs[10],rhs[10][10],ft[10],fol[10];

int n;

}pro[10];

void findter()

{

int k,t;

for(k=0;k<n;k++)

{

if(temp==pro[k].lhs[0])

{

for(t=0;t<pro[k].n;t++)

{

if( pro[k].rhs[t][0]<65 || pro[k].rhs[t][0]>90 )

pro[i].ft[strlen(pro[i].ft)]=pro[k].rhs[t][0];

else if( pro[k].rhs[t][0]>=65 && pro[k].rhs[t][0]<=90 )

{

temp=pro[k].rhs[t][0];

if(temp=='S')

pro[i].ft[strlen(pro[i].ft)]='#';

findter();

}

break;

}

void findfol()

{

int k,t,p1,o1,chk;

char *ptr1;

for(k=0;k<n;k++)

{

chk=0;

for(t=0;t<pro[k].n;t++)

{

ptr1=strchr(pro[k].rhs[t],temp);

if( ptr1 )

{

p1=ptr1-pro[k].rhs[t];

if(pro[k].rhs[t][p1+1]>=65 && pro[k].rhs[t][p1+1]<=90)

{

for(o1=0;o1<n;o1++)

if(pro[o1].lhs[0]==pro[k].rhs[t][p1+1])

{

strcat(pro[i].fol,pro[o1].ft);

chk++;

}

else if(pro[k].rhs[t][p1+1]=='\0')

{

temp=pro[k].lhs[0];

if(pro[l].rhs[j][p]==temp)

continue;

if(temp=='S')

strcat(pro[i].fol,"$");

findfol();

chk++;

}

else

{

pro[i].fol[strlen(pro[i].fol)]=pro[k].rhs[t][p1+1];

chk++;

}

if(chk>0)

break;

}

int main()

{

FILE *f;

//clrscr();

for(i=0;i<10;i++)

pro[i].n=0;

f=fopen("tab5.txt","r");

while(!feof(f))

{

fscanf(f,"%s",pro[n].lhs);

if(n>0)

{

if( strcmp(pro[n].lhs,pro[n-1].lhs) == 0 )

{

pro[n].lhs[0]='\0';

fscanf(f,"%s",pro[n-1].rhs[pro[n-1].n]);

pro[n-1].n++;

continue;

}

fscanf(f,"%s",pro[n].rhs[pro[n].n]);

pro[n].n++;

n++;

}

printf("\n\nTHE GRAMMAR IS AS FOLLOWS\n\n");

for(i=0;i<n;i++)

for(j=0;j<pro[i].n;j++)

printf("%s -> %s\n",pro[i].lhs,pro[i].rhs[j]);

pro[0].ft[0]='#';

for(i=0;i<n;i++)

{

for(j=0;j<pro[i].n;j++)

{

if( pro[i].rhs[j][0]<65 || pro[i].rhs[j][0]>90 )

{

pro[i].ft[strlen(pro[i].ft)]=pro[i].rhs[j][0];

}

else if( pro[i].rhs[j][0]>=65 && pro[i].rhs[j][0]<=90 )

{

temp=pro[i].rhs[j][0];

if(temp=='S')

pro[i].ft[strlen(pro[i].ft)]='#';

findter();

}

printf("\n\nFIRST\n");

for(i=0;i<n;i++)

{

printf("\n%s -> ",pro[i].lhs);

for(j=0;j<strlen(pro[i].ft);j++)

{

for(l=j-1;l>=0;l--)

if(pro[i].ft[l]==pro[i].ft[j])

break;

if(l==-1)

printf("%c",pro[i].ft[j]);

}

for(i=0;i<n;i++)

temp2[i]=pro[i].lhs[0];

pro[0].fol[0]='$';

for(i=0;i<n;i++)

{

for(l=0;l<n;l++)

{

for(j=0;j<pro[i].n;j++)

{

ptr=strchr(pro[l].rhs[j],temp2[i]);

if( ptr )

{

p=ptr-pro[l].rhs[j];

if(pro[l].rhs[j][p+1]>=65 && pro[l].rhs[j][p+1]<=90)

{

for(o=0;o<n;o++)

if(pro[o].lhs[0]==pro[l].rhs[j][p+1])

strcat(pro[i].fol,pro[o].ft);

}

else if(pro[l].rhs[j][p+1]=='\0')

{

temp=pro[l].lhs[0];

if(pro[l].rhs[j][p]==temp)

continue;

if(temp=='S')

strcat(pro[i].fol,"$");

findfol();

}

else

pro[i].fol[strlen(pro[i].fol)]=pro[l].rhs[j][p+1];

}

printf("\n\nFOLLOW\n");

for(i=0;i<n;i++)

{

printf("\n%s -> ",pro[i].lhs);

for(j=0;j<strlen(pro[i].fol);j++)

{

for(l=j-1;l>=0;l--)

if(pro[i].fol[l]==pro[i].fol[j])

break;

if(l==-1)

printf("%c",pro[i].fol[ j]);

}

printf("\n");

//getch();

//return(0);

}

// Pract.8.Construction of predictive top-down parsing table.

#include <stdio.h>

#include <string.h>

char prol[7][10] = { "S", "A", "A", "B", "B", "C", "C" };

char pror[7][10] = { "A", "Bb", "Cd", "aB", "@", "Cc", "@" };

char prod[7][10] = { "S->A", "A->Bb", "A->Cd", "B->aB", "B->@", "C->Cc", "C->@" };

char first[7][10] = { "abcd", "ab", "cd", "a@", "@", "c@", "@" };

char follow[7][10] = { "$", "$", "$", "a$", "b$", "c$", "d$" };

char table[5][6][10];

int numr(char c)

{

switch (c)

{

case 'S':

return 0;

case 'A':

return 1;

case 'B':

return 2;

case 'C':

return 3;

case 'a':

return 0;

case 'b':

return 1;

case 'c':

return 2;

case 'd':

return 3;

case '$':

return 4;

}

return (2);

}

int main()

{

int i, j, k;

for (i = 0; i < 5; i++)

for (j = 0; j < 6; j++)

strcpy(table[i][j], " ");

printf("The following grammar is used for Parsing Table:\n");

for (i = 0; i < 7; i++)

printf("%s\n", prod[i]);

printf("\nPredictive parsing table:\n");

fflush(stdin);

for (i = 0; i < 7; i++)

{

k = strlen(first[i]);

for (j = 0; j < 10; j++)

if (first[i][j] != '@')

strcpy(table[numr(prol[i][0]) + 1][numr(first[i][j]) + 1], prod[i]);

}

for (i = 0; i < 7; i++)

{

if (strlen(pror[i]) == 1)

{

if (pror[i][0] == '@')

{

k = strlen(follow[i]);

for (j = 0; j < k; j++)

strcpy(table[numr(prol[i][0]) + 1][numr(follow[i][j]) + 1], prod[i]);

}

strcpy(table[0][0], " ");

strcpy(table[0][1], "a");

strcpy(table[0][2], "b");

strcpy(table[0][3], "c");

strcpy(table[0][4], "d");

strcpy(table[0][5], "$");

strcpy(table[1][0], "S");

strcpy(table[2][0], "A");

strcpy(table[3][0], "B");

strcpy(table[4][0], "C");

printf("\n--------------------------------------------------------\n");

for (i = 0; i < 5; i++)

for (j = 0; j < 6; j++)

{

printf("%-10s", table[i][j]);

if (j == 5)

printf("\n--------------------------------------------------------\n");

}

//P9. Program to identify basic blocks from three address code segments.

#include<stdio.h>

#include<string.h>

void pm();

void plus();

void div();

int i,ch,j,l;

char ex[10],ex1[10],exp1[10],ex2[10];

main()

{

while(1)

{

printf("\n 1.Assignment\n 2.Arithmatic\n 3.exit\n ENTER THE CHOICE:");

scanf("%d",&ch);

switch(ch)

{

case 1:printf("\n enter the expression with assignment operator:");

scanf("%s",ex1);

l=strlen(ex1);

ex2[0]='\0';

i=0;

while(ex1[i]!='=')

{

i++;

}

strncat(ex2,ex1,i);

strrev(ex1);

exp1[0]='\0';

strncat(exp1,ex1,l-(i+1));

strrev(exp1);

printf("3 address code:\n temp=%s \n %s=temp\n",exp1,ex2);

break;

case 2:printf("\n enter the expression with arithmatic operator:");

scanf("%s",ex);

strcpy(ex1,ex);

l=strlen(ex1);

exp1[0]='\0';

for(i=0;i<l;i++)

{

if(ex1[i]=='+'||ex1[i]=='-')

{

if(ex1[i+2]=='/'||ex1[i+2]=='*')

{

pm();

break;

}

else

{

plus();

break;

}

else if(ex1[i]=='/'||ex1[i]=='*')

{

div();

break;

}

// break;

// }

//}

break;

case 3:exit(0);

}

void pm()

{

strrev(exp1);

j=l-i-1;

strncat(exp1,ex1,j);

strrev(exp1);

printf("3 address code:\n temp=%s\n temp1=%c%c temp\n",exp1,ex1[j+2],ex1[j]);

}

void div()

{

strncat(exp1,ex1,i+2);

printf("3 address code:\n temp=%s\n temp1=temp%c%c\n",exp1,ex1[l+2],ex1[i+3]);

}

void plus()

{

strncat(exp1,ex1,i+2);

printf("3 address code:\n temp=%s\n temp1=temp%c%c\n",exp1,ex1[l+2],ex1[i+3]);

}

//P10.Implementation of Symbol Table

#include<stdio.h>

#include<ctype.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

void main()

{

int i=0,j=0,x=0,n;

void *p,*add[5];

char ch,srch,b[15],d[15],c;

printf("Expression terminated by $:");

while((c=getchar())!='$')

{

b[i]=c;

i++;

}

n=i-1;

printf("Given Expression:");

i=0;

while(i<=n)

{

printf("%c",b[i]);

i++;

}

printf("\n Symbol Table\n");

printf("Symbol \t addr \t type");

while(j<=n)

{

c=b[j];

if(isalpha(toascii(c)))

{

p=malloc(c);

add[x]=p;

d[x]=c;

printf("\n%c \t %d \t identifier\n",c,p);

x++;

j++;

}

else

{

ch=c;

if(ch=='+'||ch=='-'||ch=='*'||ch=='=')

{

p=malloc(ch);

add[x]=p;

d[x]=ch;

printf("\n %c \t %d \t operator\n",ch,p);

x++;

j++;

}}}}

First set.

#include<stdio.h>
#include<ctype.h>
void FIRST(char[],char );
void addToResultSet(char[],char);
int numOfProductions;
char productionSet[10][10];
main()
{
    int i;
    char choice; 
    char c;
    char result[20];
    printf("How many number of productions ? :");
    scanf(" %d",&numOfProductions);
    for(i=0;i<numOfProductions;i++)
    {
        printf("Enter productions Number %d : ",i+1);
        scanf(" %s",productionSet[i]);
    }
    do
    {
        printf("\n Find the FIRST of  :");
        scanf(" %c",&c);
        FIRST(result,c); 
        printf("\n FIRST(%c)= { ",c);
        for(i=0;result[i]!='\0';i++)
        printf(" %c ",result[i]);       
        printf("}\n");
        printf("press 'y' to continue : ");
        scanf(" %c",&choice);
    }
    while(choice=='y'||choice =='Y');
}
void FIRST(char* Result,char c)
{
    int i,j,k;
    char subResult[20];
    int foundEpsilon;
    subResult[0]='\0';
    Result[0]='\0';
    if(!(isupper(c)))
    {
        addToResultSet(Result,c);
               return ;
    }
    for(i=0;i<numOfProductions;i++)
    {
        if(productionSet[i][0]==c)
        {
 if(productionSet[i][2]=='$') addToResultSet(Result,'$');

      else
            {
                j=2;
                while(productionSet[i][j]!='\0')
                {
                foundEpsilon=0;
                FIRST(subResult,productionSet[i][j]);
                for(k=0;subResult[k]!='\0';k++)
                    addToResultSet(Result,subResult[k]);
                 for(k=0;subResult[k]!='\0';k++)
                     if(subResult[k]=='$')
                     {
                         foundEpsilon=1;
                         break;
                     }
                 if(!foundEpsilon)
                     break;
                 j++;
                }
            }
    }
}
    return ;
}
void addToResultSet(char Result[],char val)
{
    int k;
    for(k=0 ;Result[k]!='\0';k++)
        if(Result[k]==val)
            return;
    Result[k]=val;
    Result[k+1]='\0';
}

Gate met

Compiler Source Code

Posted by Jayesh Mirashe

Post a Comment

0 Comments

Popular Posts

Most Popular

Main Memory

CIS practicals

Intellectual Property

Menu Footer Widget

Gate met

Advertisement

Compiler Source Code

Posted by Jayesh Mirashe

You may like these posts

Post a Comment

0 Comments

Popular Posts

Most Popular

Main Memory

CIS practicals

Intellectual Property

Menu Footer Widget