1.

Implementation of LEXICAL ANALYZER for IF STATEMEN

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>

int isKeyword(char buffer[]){

char keywords[32][10] = {"auto","break","case","char","const","continue","default",
"do","double","else","enum","extern","float","for","goto",
"if","int","long","register","return","short","signed",
"sizeof","static","struct","switch","typedef","union",
"unsigned","void","volatile","while"};
int i, flag = 0;
for(i = 0; i < 32; ++i){
if(strcmp(keywords[i], buffer) == 0){
flag = 1;
break;
}
}
return flag;
}
int main(){
char ch, buffer[15], operators[] = "+-*/%=";
FILE *fp;
int i,j=0;

fp = fopen("program.txt","r");

if(fp == NULL){
printf("error while opening the file\n");
exit(0);
}

while((ch = fgetc(fp)) != EOF){

for(i = 0; i < 6; ++i){
if(ch == operators[i])
printf("%c is operator\n", ch);
}

if(isalnum(ch)){
buffer[j++] = ch;
}
else if((ch == ' ' || ch == '\n') && (j != 0)){
buffer[j] = '\0';
j = 0;

if(isKeyword(buffer) == 1)
printf("%s is keyword\n", buffer);
else
printf("%s is indentifier\n", buffer);
}
}
fclose(fp);
return 0;}
Output:
 2. Implementation of LEXICAL ANALYZER for ARITHMETIC EXPRESSION

#include<stdio.h>
#include<conio.h>
void main()
{ char s[5];
clrscr();
printf("\n Enter any operator:");
gets(s);
switch(s[0])
{
case'>': if(s[1]=='=')
printf("\n Greater than or equal");
else
printf("\n Greater than");
break;

case'<': if(s[1]=='=')
printf("\n Less than or equal");
else
printf("\nLess than");
break;
case'=': if(s[1]=='=')
printf("\nEqual to");
else
printf("\nAssignment");
break;
case'!': if(s[1]=='=')
printf("\nNot Equal");
else
printf("\n Bit Not");
break;
case'&': if(s[1]=='&')
printf("\nLogical AND");
else
printf("\n Bitwise AND");
break;
case'|': if(s[1]=='|')
printf("\nLogical OR");
else
printf("\nBitwise OR");
break;
case'+': printf("\n Addition");
break;
case'-': printf("\nSubstraction");
break;
case'*': printf("\nMultiplication");
break;
case'/': printf("\nDivision");
break;
case'%': printf("Modulus");
break;
default: printf("\n Not a operator"); } getch(); }
Output:
3. Construction of NFA from REGULAR EXPRESSION

# include <stdio.h>
# include <conio.h>
# include <string.h>
# include <ctype.h>
int ret[100];
static int pos=0;
static int sc=0;
void nfa(int st,int p,char *s)
{ int i,sp,fs[15],fsc=0;
sp=st;pos=p;sc=st;
while(*s!=NULL)
{if(isalpha(*s))
{ret[pos++]=sp;
ret[pos++]=*s;
ret[pos++]=++sc;}
if(*s=='.')
{sp=sc;
ret[pos++]=sc;
ret[pos++]=238;
ret[pos++]=++sc;
sp=sc;}
if(*s=='|')
{sp=st;
fs[fsc++]=sc;}
if(*s=='*')
{ret[pos++]=sc;
ret[pos++]=238;
ret[pos++]=sp;
ret[pos++]=sp;
ret[pos++]=238;
ret[pos++]=sc;
}
if (*s=='(')
{char ps[50];
int i=0,flag=1;
s++;
while(flag!=0)
{ps[i++]=*s;
if (*s=='(')
flag++;
if (*s==')')
flag--;
s++;}
ps[--i]='\0';
nfa(sc,pos,ps);
s--;
}
s++;
}
 sc++;
for(i=0;i<fsc;i++)
{ret[pos++]=fs[i];
ret[pos++]=238;
ret[pos++]=sc;
}
ret[pos++]=sc-1;
ret[pos++]=238;
ret[pos++]=sc;
}
void main()
{ int i;
char *inp;
clrscr();
printf("enter the regular expression :");
gets(inp);
nfa(1,0,inp);
printf("\nstate input state\n");
for(i=0;i<pos;i=i+3)
printf("%d --%c--> %d\n",ret[i],ret[i+1],ret[i+2]);
printf("\n");
getch();
}
 4. Construction of DFA from NFA

#include <stdio.h>
#include <string.h>

#define STATES 256

#define SYMBOLS 20

int N_symbols;
int NFA_state;

char *NFAtab[STATES][SYMBOLS];

int DFA_states; /* number of DFA states */

int DFAtab[STATES][SYMBOLS];

/*Print state-transition table.*/

void put_dfa_table(

int tab[][SYMBOLS], /* DFA table */

int nstates, /* number of states */

int nsymbols) /* number of input symbols */

int i, j;

puts("STATE TRANSITION TABLE");

/* input symbols: '0', '1', ... */

printf(" | ");
 for (i = 0; i < nsymbols; i++) printf(" %c ", '0'+i);

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

for (i = 0; i < nsymbols; i++) printf("-----");

printf("\n");

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

printf(" %c | ", 'A'+i); /* state */

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

printf(" %c ", 'A'+tab[i][j]);

printf("\n");

/*Initialize NFA table.*/

void init_NFA_table()

/*

NFA table for ex.21 at p.76

NFAtab[0][0] = "01";

NFAtab[0][1] = "0";

NFAtab[1][0] = "";

NFAtab[1][1] = "01";
 NFA_states = 2;

DFA_states = 0;

N_symbols = 2;

*/

/*

NFA table for ex.17 at p.72

*/

NFAtab[0][0] = "12";

NFAtab[0][1] = "13";

NFAtab[1][0] = "12";

NFAtab[1][1] = "13";

NFAtab[2][0] = "4";

NFAtab[2][1] = "";

NFAtab[3][0] = "";

NFAtab[3][1] = "4";

NFAtab[4][0] = "4";

NFAtab[4][1] = "4";

NFA_states = 5;

DFA_states = 0;

N_symbols = 2;

}
/*String 't' is merged into 's' in an alphabetical order.*/

void string_merge(char *s, char *t)

char temp[STATES], *r=temp, *p=s;

while (*p && *t) {

if (*p == *t) {

*r++ = *p++; t++;

} else if (*p < *t) {

*r++ = *p++;

} else

*r++ = *t++;

*r = '\0';

if (*p) strcat(r, p);

else if (*t) strcat(r, t);

strcpy(s, temp);

/*Get next-state string for current-state string.*/

void get_next_state(char *nextstates, char *cur_states,

char *nfa[STATES][SYMBOLS], int n_nfa, int symbol)

{

int i;

char temp[STATES];

temp[0] = '\0';

for (i = 0; i < strlen(cur_states); i++)

string_merge(temp, nfa[cur_states[i]-'0'][symbol]);

strcpy(nextstates, temp);

int state_index(char *state, char statename[][STATES], int *pn)

int i;

if (!*state) return -1; /* no next state */

for (i = 0; i < *pn; i++)

if (!strcmp(state, statename[i])) return i;

strcpy(statename[i], state); /* new state-name */

return (*pn)++;
}

/*

Convert NFA table to DFA table.

Return value: number of DFA states.

*/

int nfa_to_dfa(char *nfa[STATES][SYMBOLS], int n_nfa,

int n_sym, int dfa[][SYMBOLS])

{
char statename[STATES][STATES]
;
int i = 0; /* current index of DFA*/
int n = 1; /* number of DFA states */

char nextstate[STATES];
int j;

strcpy(statename[0], "0"); /* start state */

for (i = 0; i < n; i++) { /* for each DFA state */

for (j = 0; j < n_sym; j++) { /* for each input symbol */

get_next_state(nextstate, statename[i], nfa, n_nfa, j);

dfa[i][j] = state_index(nextstate, statename, &n);

return n; /* number of DFA states */

}

void main()
{
init_NFA_table();
DFA_states = nfa_to_dfa(NFAtab, NFA_states, N_symbols, DFAtab);
put_dfa_table(DFAtab, DFA_states, N_symbols);
}
 5. Implementation of SHIFT REDUCE PARSING ALGORITHM

#include"stdio.h"
#include"stdlib.h"
#include"conio.h"
#include"string.h"
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
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;
}
Output:
 6. Implementation of OPERATOR PRECEDENCE PARSER

#include<stdio.h>
#include<conio.h>
void main(){
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 :\n");
scanf("%d",&n);
printf("\nEnter the terminals :\n");
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("\n**** OPERATOR 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("\nSTACK\t\t\tINPUT STRING\t\t\tACTION\n");
printf("\n%s\t\t\t%s\t\t\t",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\n");
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("\t\t\t");
for(k=i;k<strlen(ip);k++){
printf("%c",ip[k]);
}
printf("\t\t\t");
}
getch();
}
/*OPERATOR PRECEDENCE PARSER*/
char stack[20],ip[20],opt[10][10][1],ter[10]
 7. Implementation of RECURSIVE DESCENT PARSER

#include<stdio.h>
#include<ctype.h>
#include<string.h>

void Tprime();
void Eprime();
void E();
void check();
void T();

char expression[10];
int count, flag;

int main()
{
count = 0;
flag = 0;
printf("\nEnter an Algebraic Expression:\t");
scanf("%s", expression);
E();
if((strlen(expression) == count) && (flag == 0))
{
printf("\nThe Expression %s is Valid\n", expression);
}
else
{
printf("\nThe Expression %s is Invalid\n", expression);
}
}

void E()
{
T();
Eprime();
}

void T()
{
check();
Tprime();
}

void Tprime()
{
if(expression[count] == '*')
{
count++;
check();
Tprime();
}
}

void check()
{
if(isalnum(expression[count]))
{
count++;
}
else if(expression[count] == '(')
{
count++;
E();
if(expression[count] == ')')
{
count++;
}
else
{
flag = 1;
}
}
else
{
flag = 1;
}
}

void Eprime()
{
if(expression[count] == '+')
{
count++;
T();
Eprime();
}
}

Output : enter algebraic expression

The expression (a+b)*c is valid

 8. Implementation of CODE OPTIMIZATION TECHNIQUES

#include<iostream.h>
#include <conio.h>
int main()
{
int i, n;
int fact=1;
cout<<"\nEnter a number: ";
cin>>n;
for(i=n;i>=1;i--)
fact=fact *i;
cout<<"The factoral value is: "<<fact;
getch();
return 0;
}

Output:
 9. Implementation of CODE GENERATOR

#include"stdio.h"
#include"conio.h"
#include"string.h"
#include"stdlib.h"
struct quadraple
{
int pos;
char op;
char arg1[5];
char arg2[5];
char result[5];
}quad[15];
int n=0;
void assignment(int);
void uminus(int );
void explore();
void codegen(char op[5],int);
char tuple[15][15];
int main(void)
{
FILE *src;
int nRetInd,i;
char str[15];
clrscr();
src=fopen("int.txt","r");
fscanf(src,"%s",str);
while(!feof(src))
{
strcpy(tuple[n++],str);
fscanf(src,"%s",str);
}
printf("INPUT:\nIntermiate codes:\n");
for(i=0;i< n;i++)
printf("%s\n",tuple[i]);
explore();
getch();
clrscr();
printf("OUTPUT:\n");
printf("Quadruple: \n");
printf("pos\topr\targ1\targ2\tresult\n");
for(i=0;i< n;i++)
printf("\n%d\t%c\t%s\t%s\t%s",quad[i].pos,quad[i].op,quad[i].arg1,quad[i].arg2,quad[i].result);
i=0;
printf("\n\ncode generated :\n");
while(i< n)
{
if(quad[i].op=='+')
codegen("ADD",i);
if(quad[i].op=='=')
assignment(i);
 if(quad[i].op=='-')
if(!strcmp(quad[i].arg2,"\0"))
uminus(i);
else
codegen("SUB",i);
if(quad[i].op=='*')
codegen("MUL",i);
if(quad[i].op=='/')
codegen("DIV",i);
i++;
}
getch();
fcloseall();
return 0;
}
void codegen(char op[5],int t)
{
char str[25];
printf("MOV %s,R0\n",quad[t].arg1);
printf("%s %s,R0\n",op,quad[t].arg2);
printf("MOV R0,%s\n",quad[t].result);
}
void assignment(int t)
{
char str[25];
printf("MOV %s,%s\n",quad[t].result,quad[t].arg1);
}
void uminus(int t)
{
char str[25];
printf("MOV R0,0\n");
printf("SUB %s,R0\n",quad[t].arg1);
printf("MOV R0,%s\n",quad[t].result);
}

void explore()
{
int i,j,t,t1,t2;
for(i=0;i < n;i++)
{
quad[i].pos=i;
for(j=0,t=0;j < strlen(tuple[i])&&tuple[i][j]!='=';j++)<strlen(tuple[i])&&tuple[i][j]!='=';j++)
style="color: rgb(41, 48, 59); font-family: Georgia, "Times New Roman", sans-serif; font-size: 13px;
font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-
spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; white-space:
normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255,
243, 219); text-decoration-style: initial; text-decoration-color:
initial;"></strlen(tuple[i])&&tuple[i][j]!='=';j++)>
{
quad[i].result[t++]=tuple[i][j];
}
t1=j;
quad[i].result[t]='\0';
if(tuple[i][j]=='=')
{
 quad[i].op='=';
}
if(tuple[i][j+1]=='+'||tuple[i][j+1]=='-'||tuple[i][j+1]=='*'||tuple[i][j+1]=='/')
{
quad[i].op=tuple[i][j+1];
t1=j+1;
}
for(j=t1+1,t=0;j< strlen(tuple[i])&&tuple[i][j]!='+'&&tuple[i][j]!='-
'&&tuple[i][j]!='*'&&tuple[i][j]!='/';j++)
{
quad[i].arg1[t++]=tuple[i][j];
}
t2=j;
quad[i].arg1[t]='\0';
if(tuple[i][j]=='+'||tuple[i][j]=='-'||tuple[i][j]=='*'||tuple[i][j]=='/')
{
quad[i].op=tuple[i][j];
}
for(j=t2+1,t=0;j< strlen(tuple[i]);j++)
{
quad[i].arg2[t++]=tuple[i][j];
}
quad[i].arg2[t]='\0';
}
}

Output:
 Compiler Design Lab

1. Implementation of LEXICAL ANALYZER for IF STATEMEN

2. Implementation of LEXICAL ANALYZER for ARITHMETIC EXPRESSION

3. Construction of NFA from REGULAR EXPRESSION

4. Construction of DFA from NFA

5. Implementation of SHIFT REDUCE PARSING ALGORITHM

6. Implementation of OPERATOR PRECEDENCE PARSER

7. Implementation of RECURSIVE DESCENT PARSER

8. Implementation of CODE OPTIMIZATION TECHNIQUES

9. Implementation of CODE GENERATOR