Madhav Institute of Technology and Science, Gwalior

(A Govt. Aided UGC Autonomous Institute, affiliated to R.G.P.V, Bhopal, M.P)

Department of Computer Science& Engineering and

Information Technology

Practical File
On

Compiler Design
Session: Jan – Jun 2020

Submitted To: Submitted By:

Prof. Julie Kumari Krati Saxena

CSE 3rd Year
0901CS171057
 INDEX
S.No. Name of Program Date of Faculty’s Signature
Submission
1 Write a Program to convert NFA to DFA.

2 Write a program to minimize dfa

3 Develop a lexical analyzer to recognize a

few patterns
4 Write a program to parse using brute force
technique of top down parsing
5 Develop LL(1) parser

6 Develop an operator precedence parser

7 Develop a recursive descent parser

8 Write a program for generating for various

intermediate code forms.
(1)Three address code
(2.)Polish notation
9 Write a program to simulate heap storage
allocation strategy
10 Generate lexical analyzer using lex

11 Generate YACC specification for a

syntactic categories
12 Given any intermediate code form
implement code optimization techniques.
 Program 1
Write a Program to convert NFA to DFA.

#include<stdio.h>
#include<string.h>
#include<math.h>
int ninputs;
int dfa[100][2][100] = {0};
int state[10000] = {0};
char ch[10], str[1000];
int go[10000][2] = {0};
int arr[10000] = {0};
int main()
{
int st, fin, in;
int f[10];
int i,j=3,s=0,final=0,flag=0,curr1,curr2,k,l;
int c;
printf("\nFollow the one based indexing\n");
printf("\nEnter the number of states::");
scanf("%d",&st);
printf("\nGive state numbers from 0 to %d",st-1);
for(i=0;i<st;i++)
state[(int)(pow(2,i))] = 1;
printf("\nEnter number of final states\t");
scanf("%d",&fin);
printf("\nEnter final states::");
for(i=0;i<fin;i++)
scanf("%d",&f[i]);
int p,q,r,rel;
printf("\nEnter the number of rules according to NFA::");
scanf("%d",&rel);
printf("\n\nDefine transition rule as \"initial state input symbol final state\"\n");

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

scanf("%d%d%d",&p,&q,&r);
if (q==0)
dfa[p][0][r] = 1;
else
dfa[p][1][r] = 1;
}
printf("\nEnter initial state::");
scanf("%d",&in);
in = pow(2,in);
i=0;
printf("\nSolving according to DFA");
int x=0;
for(i=0;i<st;i++){
for(j=0;j<2;j++){
int stf=0;
for(k=0;k<st;k++){
if(dfa[i][j][k]==1)
stf = stf + pow(2,k);}
go[(int)(pow(2,i))][j] = stf;
printf("%d-%d-->%d\n",(int)(pow(2,i)),j,stf);
if(state[stf]==0)
arr[x++] = stf;
state[stf] = 1;}}
for(i=0;i<x;i++){
printf("for %d ---- ",arr[x]);
for(j=0;j<2;j++){
int new=0;
for(k=0;k<st;k++){
 if(arr[i] & (1<<k)){
int h = pow(2,k);
if(new==0)
new = go[h]
[j];
new = new | (go[h][j]);
}}
if(state[new]==0)}
arr[x++] = new;
state[new] = 1;
}}}
printf("\nThe total number of distinct states are::\n");
printf("STATE 0 1\n");
for(i=0;i<10000;i++){
if(state[i]==1){
int y=0;
if(i==0)
printf("q0 ");
else
for(j=0;j<st;j++){
int x = 1<<j;
if(x&i){
printf("q%d ",j);
y = y+pow(2,j);
//printf("y=%d ",y);
}}
printf(" %d %d",go[y][0],go[y][1]);
}}
j=3;
while(j--)
{
printf("\nEnter string");
 scanf("%s",str);
l = strlen(str);
curr1 = in;
flag = 0;
printf("\nString takes the following path-->\n");
printf("%d-",curr1);
for(i=0;i<l;i++)
{
curr1 = go[curr1][str[i]-'0'];
printf("%d-",curr1);
}
printf("\nFinal state - %d\n",curr1);
for(i=0;i<fin;i++)
{
if(curr1 & (1<<f[i]))
{
flag = 1;
break;
}
}
if(flag)
printf("\nString Accepted");
Else
printf("\nString Rejected");
} return 0;
}

Input :

9
2
- - BH
- - CE
D--
--G
-F-
--G
- - BH
I--
-- -

OUTPUT:
STATES OF NFA : A, B, C, D, E, F, G, H, I,
GIVEN SYMBOLS FOR NFA: 0, 1, eps
NFA STATE TRANSITION TABLE
STATES |0 |1 eps
--------+------------------------------------

A |- |- |BH

B |- |- |CE

C |D |- |-

D |- |- |G

E |- |F |-

F |- |- |G

G |- |- |BH

H |I |- |-

I |- |- |-

e-Closure (A) : ABCEH

e-Closure (B) : BCE

e-Closure (C) : C

e-Closure (D) : BCDEGH

e-Closure (E) : E

e-Closure (F) : BCEFGH

e-Closure (G) : BCEGH

e-Closure (H) : H

e-Closure (I) : I
 Program 2
Write a program to minimize dfa

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

#define STATES 99
#define SYMBOLS 20

int N_symbols; /* number of input symbols */

int N_DFA_states; /* number of DFA states */
char *DFA_finals; /* final-state string */
int DFAtab[STATES][SYMBOLS];

char StateName[STATES][STATES+1]; /* state-name table */

int N_optDFA_states; /* number of optimized DFA states */

int OptDFA[STATES][SYMBOLS];
char NEW_finals[STATES+1];
void print_dfa_table(
int tab[][SYMBOLS], /* DFA table */
int nstates, /* number of states */
int nsymbols, /* number of input symbols */
char *finals)
{
int i, j;

puts("\nDFA: 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 ", tab[i][j]); /* next state */
printf("\n");
}
printf("Final states = %s\n", finals);
}

void load_DFA_table()
{

void get_next_state(char *nextstates, char *cur_states,

int dfa[STATES][SYMBOLS], int symbol)
{
int i, ch;

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

*nextstates++ = dfa[cur_states[i]-'A'][symbol];
*nextstates = '\0';
}
char equiv_class_ndx(char ch, char stnt[][STATES+1], int n)
{
int i;

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

if (strchr(stnt[i], ch)) return i+'0';
return -1; /* next state is NOT defined */
}
char is_one_nextstate(char *s)
{
char equiv_class; /* first equiv. class */

while (*s == '@') s++;

equiv_class = *s++; /* index of equiv. class */

while (*s) {
if (*s != '@' && *s != equiv_class) return 0;
s++;
}

return equiv_class; /* next state: char type */

}

int state_index(char *state, char stnt[][STATES+1], int n, int *pn,

int cur) /* 'cur' is added only for 'printf()' */
{
int i;
char state_flags[STATES+1]; /* next state info. */

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

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

state_flags[i] = equiv_class_ndx(state[i], stnt, n);
state_flags[i] = '\0';

printf(" %d:[%s]\t--> [%s] (%s)\n",

cur, stnt[cur], state, state_flags);

if (i=is_one_nextstate(state_flags))
return i-'0'; /* deterministic next states */
else {
strcpy(stnt[*pn], state_flags);
return (*pn)++;
}
}
int init_equiv_class(char statename[][STATES+1], int n, char *finals)
{
int i, j;

if (strlen(finals) == n) { /* all states are final states */

strcpy(statename[0], finals);
return 1;
}

strcpy(statename[1], finals); /* final state group */

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

if (i == *finals-'A') {
finals++;
 } else statename[0][j++] = i+'A';
}
statename[0][j] = '\0';

return 2;
}
int get_optimized_DFA(char stnt[][STATES+1], int n,
int dfa[][SYMBOLS], int n_sym, int newdfa[][SYMBOLS])
{
int n2=n; /* 'n' + <num. of state-division info> */
int i, j;
char nextstate[STATES+1];

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

for (j = 0; j < n_sym; j++) { /* for each input symbol */
get_next_state(nextstate, stnt[i], dfa, j);
newdfa[i][j] = state_index(nextstate, stnt, n, &n2, i)+'A';
}
}

return n2;
}

void chr_append(char *s, char ch)

{
int n=strlen(s);

*(s+n) = ch;
*(s+n+1) = '\0';
}

void sort(char stnt[][STATES+1], int n)

{
int i, j;
char temp[STATES+1];

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

for (j = i+1; j < n; j++)
if (stnt[i][0] > stnt[j][0]) {
strcpy(temp, stnt[i]);
strcpy(stnt[i], stnt[j]);
strcpy(stnt[j], temp);
}
}

int split_equiv_class(char stnt[][STATES+1],

int i1, /* index of 'i1'-th equiv. class */
int i2, /* index of equiv. vector for 'i1'-th class */
int n, /* number of entries in 'stnt' */
int n_dfa) /* number of source DFA entries */
{
char *old=stnt[i1], *vec=stnt[i2];
int i, n2, flag=0;
char newstates[STATES][STATES+1]; /* max. 'n' subclasses */

for (i=0; i < STATES; i++) newstates[i][0] = '\0';

for (i=0; vec[i]; i++)

chr_append(newstates[vec[i]-'0'], old[i]);
 for (i=0, n2=n; i < n_dfa; i++) {
if (newstates[i][0]) {
if (!flag) { /* stnt[i1] = s1 */
strcpy(stnt[i1], newstates[i]);
flag = 1; /* overwrite parent class */
} else /* newstate is appended in 'stnt' */
strcpy(stnt[n2++], newstates[i]);
}
}

sort(stnt, n2); /* sort equiv. classes */

return n2; /* number of NEW states(equiv. classes) */

}

int set_new_equiv_class(char stnt[][STATES+1], int n,

int newdfa[][SYMBOLS], int n_sym, int n_dfa)
{
int i, j, k;

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

for (j = 0; j < n_sym; j++) {
k = newdfa[i][j]-'A'; /* index of equiv. vector */
if (k >= n)
return split_equiv_class(stnt, i, k, n, n_dfa);
}
}

return n;
}

void print_equiv_classes(char stnt[][STATES+1], int n)

{
int i;

printf("\nEQUIV. CLASS CANDIDATE ==>");

for (i = 0; i < n; i++)
printf(" %d:[%s]", i, stnt[i]);
printf("\n");
}
int optimize_DFA(
int dfa[][SYMBOLS], /* DFA state-transition table */
int n_dfa, /* number of DFA states */
int n_sym, /* number of input symbols */
char *finals, /* final states of DFA */
char stnt[][STATES+1], /* state name table */
int newdfa[][SYMBOLS]) /* reduced DFA table */
{
char nextstate[STATES+1];
int n; /* number of new DFA states */
int n2; /* 'n' + <num. of state-dividing info> */

n = init_equiv_class(stnt, n_dfa, finals);

while (1) {
print_equiv_classes(stnt, n);
n2 = get_optimized_DFA(stnt, n, dfa, n_sym, newdfa);
if (n != n2)
n = set_new_equiv_class(stnt, n, newdfa, n_sym, n_dfa);
else break; /* equiv. class segmentation ended!!! */
 }

return n; /* number of DFA states */

}
int is_subset(char *s, char *t)
{
int i;

for (i = 0; *t; i++)

if (!strchr(s, *t++)) return 0;
return 1;
}
void get_NEW_finals(
char *newfinals, /* new DFA finals */
char *oldfinals, /* source DFA finals */
char stnt[][STATES+1], /* state name table */
int n) /* number of states in 'stnt' */
{
int i;

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

if (is_subset(oldfinals, stnt[i])) *newfinals++ = i+'A';
*newfinals++ = '\0';
}

void main()
{
load_DFA_table();
print_dfa_table(DFAtab, N_DFA_states, N_symbols, DFA_finals);

N_optDFA_states = optimize_DFA(DFAtab, N_DFA_states,

N_symbols, DFA_finals, StateName, OptDFA);
get_NEW_finals(NEW_finals, DFA_finals, StateName, N_optDFA_states);

print_dfa_table(OptDFA, N_optDFA_states, N_symbols, NEW_finals);

}
 Program 3
Develop a lexical analyzer to recognize a few patterns
#include<string.h>

#include<ctype.h>

#include<stdio.h>

#include<stdlib.h>

void keyword(char str[10])

if(strcmp("for",str)==0||strcmp("while",str)==0||strcmp("do",str)==0||strcmp("int",str)==0||
strcmp("float",str)==0||strcmp("char",str)==0||strcmp("double",str)==0||strcmp("printf",str)==0||
strcmp("switch",str)==0||strcmp("case",str)==0)

printf("\n%s is a keyword",str);

else

printf("\n%s is an identifier",str);

void main()

FILE *f1,*f2,*f3;

char c,str[10],st1[10];

int num[100],lineno=0,tokenvalue=0,i=0,j=0,k=0;

f1=fopen("input","r");

f2=fopen("identifier","w");

f3=fopen("specialchar","w");

while((c=getc(f1))!=EOF)

if(isdigit(c))

tokenvalue=c-'0';

c=getc(f1);

while(isdigit(c))

tokenvalue*=10+c-'0';
 c=getc(f1);

} num[i++]=tokenvalue;

ungetc(c,f1);

} else

if(isalpha(c))

{ putc(c,f2);

c=getc(f1);

while(isdigit(c)||isalpha(c)||c=='_'||c=='$')

{ putc(c,f2);

c=getc(f1);

} putc(' ',f2);

ungetc(c,f1);

} else

if(c==' '||c=='\t')

printf(" ");

else if(c=='\n')

lineno++;

else

putc(c,f3);

} fclose(f2);

fclose(f3);

fclose(f1);

printf("\n the no's in the program are:");

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

printf("\t%d",num[j]);

printf("\n");

f2=fopen("identifier","r");

k=0;

printf("the keywords and identifier are:");

while((c=getc(f2))!=EOF)

if(c!=' ')
str[k++]=c;

else

{ str[k]='\0';

keyword(str);

k=0;

} fclose(f2);

f3=fopen("specialchar","r");

printf("\n Special Characters are");

while((c=getc(f3))!=EOF)

printf("\t%c",c);

printf("\n");

fclose(f3);

printf("Total no of lines are:%d",lineno);

OUTPUT
 Program 4
Write a program to parse using brute force technique of top down parsing
#include<stdio.h>

#include<conio.h>

#include<iostream.h>

void main()

{int a[30];

clrscr();

int min=10000,temp=0,i,lev,n,noofc,z;

printf("please enter how many number");

cin>>n;

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

a[i]=0;

cout<<"enter value of root";

cin>>a[0];

for(i=1;i<=n/2;i++)

{cout<<"please enter no of child of parent with value"<<a[i-1]<<":";

cin>>noofc;

for(int j=1;j<=noofc;j++)

{z=(i)*2+j-2;

cout<<"please enter value of child";

cin>>a[z];

}for(i=n-1;i>=n/2;i--)

{temp=0;

for(int j=i+1;j>=1;j=j/2)

temp=temp+a[j-1];

if(temp<min)

min=temp;
cout<<"temp min is"<<temp<<"\n";

}cout<<"min is"<<min;

getch();

}
 Program 5
Develop LL(1) parser
#include<stdio.h>

#include<conio.h>

void main()

char pro[10][10],first[10][10],follow[10][10],nt[10],ter[10],res[10][10][10],temp[10];

int npro,noter=0,nont=0,i,j,k,flag=0,count[10][10],row,col,l,m,n,index;

clrscr();

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

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

count[i][j]=NULL;

for(k=0;k<10;k++){

res[i][j][k]=NULL; }

printf("Enter the no of productions:");

scanf("%d",&npro);

printf("Enter the productions:");

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

scanf("%s",pro[i]);

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

flag=0;

for(j=0;j<nont;j++)
{

if(nt[j]==pro[i][0])

flag=1;

if(flag==0)

nt[nont]=pro[i][0];

nont++;

printf("\nEnter the first values:\n");

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

printf("First value(%c):",nt[i]);

scanf("%s",first[i]);

printf("\nEnter the follow values:\n");

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

printf("Follow value(%c):",nt[i]);

scanf("%s",follow[i]);

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

flag=0;

for(j=0;j<strlen(first[i]);j++)
{

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

if(ter[k]==first[i][j])

flag=1;

if(flag==0)

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

ter[noter]=first[i][j];

noter++;

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

flag=0;

for(j=0;j<strlen(follow[i]);j++)

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

if(ter[k]==follow[i][j])

flag=1;
}

if(flag==0)

ter[noter]=follow[i][j];

noter++;

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

for(j=0;j<strlen(first[i]);j++)

flag=0;

if(first[i][j]=='#')

col=i;

for(m=0;m<strlen(follow[col]);m++)

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

if(ter[l]==follow[col][m])

row=l;

temp[0]=nt[col];

temp[1]='-' ;
 temp[2]='>';

temp[3]='#';

temp[4]='\0';

printf("temp %s",temp);

strcpy(res[col][row],temp);

count[col][row]+=1;

for(k=0;k<10;k++){

temp[k]=NULL; }

else{

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

if(ter[l]==first[i][j])

row=l;

for(k=0;k<npro;k++){

if(nt[i]==pro[k][0])

col=i;

if((pro[k][3]==first[i][j])&&(pro[k][0]==nt[col]))

strcpy(res[col][row],pro[k]);

count[col][row]+=1;

}
 else

if((isupper(pro[k][3]))&&(pro[k][0]==nt[col]))

flag=0;

for(m=0;m<nont;m++)

if(nt[m]==pro[k][3]){index=m;flag=1;}

if(flag==1){

for(m=0;m<strlen(first[index]);m++)

{if(first[i][j]==first[index][m])

{strcpy(res[col][row],pro[k]);

count[col][row]+=1;}

}}}}}

}}

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

flag=0;

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

printf("\t%c",ter[i]);

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

printf("\n\n%c",nt[j]);

for(k=0;k<noter;k++)
{

printf("\t%s",res[j][k]);

if(count[j][k]>1){flag=1;}

if(flag==1){printf("\nThe given grammar is not LL1");}

else{printf("\nThe given grammar is LL1");}

getch();
 Program 6
Develop an operator precedence parser
#include <stdio.h>
#include <string.h>
  
// function f to exit from the loop
// if given condition is not true
void f()
{
    printf("Not operator grammar");
    exit(0);
}
  
void main()
{
    char grm[20][20], c;
    int i, n, j = 2, flag = 0;
  
    // taking number of productions from user
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%s", grm[i]);   
    for (i = 0; i < n; i++) {
        c = grm[i][2];
  
        while (c != '\0') {
  
            if (grm[i][3] == '+' || grm[i][3] == '-'
                || grm[i][3] == '*' || grm[i][3] == '/')
                 flag = 1;
  
            else { flag = 0;
                f();
            }   
            if (c == '$') { flag = 0;
                f();}   
            c = grm[i][++j];
        }
    }
  
    if (flag == 1)
        printf("Operator grammar");
}}

Input :3
A=A*A
B=AA
A=$
Output : Not operator grammar

Input :2
A=A/A
B=A+A
Output : Operator grammar
 Program 7
Develop a recursive descent parser

int main()
{
    // E is a start symbol.
    E();
  
    // if lookahead = $, it represents the end of the string
    // Here l is lookahead.
    if (l == '$')
        printf("Parsing Successful");
}
  
// Definition of E, as per the given production
E()
{
    if (l == 'i') {
        match('i');
        E'();
    }
}
  
// Definition of E' as per the given production
E'()   
{
    if (l == '+') {
        match('+');
        match('i');
        E'();
    }
    else
        return ();
}
  
// Match function
match(char t)
{
    if (l == t) {
        l = getchar();
    }
    else
        printf("Error");
}

Example:

Grammar: E --> i E'

E' --> + i E' | e

OUTPUT
Parsing Successful
 Program 8

Write a program for generating for various intermediate code forms.

(1)Three address code

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

struct three
{
char data[10],temp[7];
}s[30];
void main()
{
char d1[7],d2[7]="t";
int i=0,j=1,len=0;
FILE *f1,*f2;
clrscr();
f1=fopen("sum.txt","r");
f2=fopen("out.txt","w");
while(fscanf(f1,"%s",s[len].data)!=EOF)
len++;
itoa(j,d1,7);
strcat(d2,d1);
strcpy(s[j].temp,d2);
strcpy(d1,"");
strcpy(d2,"t");
if(!strcmp(s[3].data,"+"))
{
fprintf(f2,"%s=%s+%s",s[j].temp,s[i+2].data,s[i+4].data);
j++;
}
else if(!strcmp(s[3].data,"-"))
{
fprintf(f2,"%s=%s-%s",s[j].temp,s[i+2].data,s[i+4].data);
j++;
}
for(i=4;i<len-2;i+=2)
{
itoa(j,d1,7);
strcat(d2,d1);
strcpy(s[j].temp,d2);
if(!strcmp(s[i+1].data,"+"))
fprintf(f2,"\n%s=%s+%s",s[j].temp,s[j-1].temp,s[i+2].data);
else if(!strcmp(s[i+1].data,"-"))
fprintf(f2,"\n%s=%s-%s",s[j].temp,s[j-1].temp,s[i+2].data);
strcpy(d1,"");
strcpy(d2,"t");
j++;
}
fprintf(f2,"\n%s=%s",s[0].data,s[j-1].temp);
fclose(f1);
fclose(f2);
getch();
}
Input:  sum.txt

out = in1 + in2 + in3 - in4

OUTPUT:       out.txt
t1=in1+in2
t2=t1+in3
t3=t2-in4
out=t3

(2.)Polish notation
#include<stdio.h>
char stack[20];
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;
}
 
Void main()
{
    char exp[20];
    char *e, x;
    printf("Enter the expression :: ");
    scanf("%s",exp);
    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());
    }
}

Output:
Enter the expression :: a+b*c

abc*+
 Program 10
Write a program to simulate heap storage allocation strategy
#include<stdio.h>

#include<stdlib.h>

#define TRUE 1

#define FALSE 0

typedef struct Heap

{int data;

struct Heap *next;

}node;

node *create();

void main()

{int choice,val;

char ans;

node *head;

void display(node *);

node *search(node *,int);

node *insert(node *);

void dele(node **);

head=NULL;

do

{printf("\nprogram to perform various operations on heap using dynamic memory management");

printf("\n1.create");

printf("\n2.display");

printf("\n3.insert an element in a list");

printf("\n4.delete an element from list");

printf("\n5.quit");

printf("\nenter your chioce(1-5)");

scanf("%d",&choice);

switch(choice)

{case 1:head=create();break;
case 2:display(head);break;

case 3:head=insert(head);break;

case 4:dele(&head);

break;

case 5:exit(0);

default:

printf("invalid choice,try again");}}

while(choice!=5);}

node* create(){

node *temp,*New,*head;

int val,flag;

char ans='y';

node *get_node();

temp=NULL;

flag=TRUE;

do{

printf("\n enter the element:");

scanf("%d",&val);

New=get_node();

if(New==NULL)

printf("\nmemory is not allocated");

New->data=val;

if(flag==TRUE)

{head=New;

temp=head;

flag=FALSE;

}else

{temp->next=New;

temp=New;

printf("\ndo you want to enter more elements?(y/n)");

}

while(ans=='y');

printf("\nthe list is created\n");

return head;

}node *get_node()

{node *temp;

temp=(node*)malloc(sizeof(node));

temp->next=NULL;

return temp;

}void display(node *head)

{node *temp;

temp=head;

if(temp==NULL)

{printf("\nthe list is empty\n");

return;

}while(temp!=NULL)

{printf("%d->",temp->data);

temp=temp->next;

}printf("NULL");

}node *search(node *head,int key)

{node *temp;

int found;temp=head;

if(temp==NULL)

{printf("the linked list is empty\n");

return NULL;}found=FALSE;

while(temp!=NULL && found==FALSE)

{if(temp->data!=key)

temp=temp->next;

else found=TRUE;

}if(found==TRUE)

{printf("\nthe element is present in the list\n");

return temp;

}else{printf("the element is not present in the list\n");

return NULL;}}node *insert(node *head)

{int choice;node *insert_head(node *);

void insert_after(node *);

void insert_last(node *);

printf("n1.insert a node as a head node");

printf("n2.insert a node as a head node");

printf("n3.insert a node at intermediate position in t6he list");

printf("\nenter your choice for insertion of node:");

scanf("%d",&choice);

switch(choice)

{case 1:head=insert_head(head);break;

case 2:insert_last(head);break;

case 3:insert_after(head);break;

}return head;

}node *insert_head(node *head)

{node *New,*temp;

New=get_node();

printf("\nEnter the element which you want to insert");

scanf("%d",&New->data);

if(head==NULL)

head=New;

else

{temp=head;

New->next=temp;

head=New;}

return head;

}void insert_last(node *head)

{node *New,*temp;

New=get_node();
printf("\nenter the element which you want to insert");

scanf("%d",&New->data);

if(head==NULL)

head=New;

else

{temp=head;

while(temp->next!=NULL)

temp=temp->next;

temp->next=New;

New->next=NULL;

}}void insert_after(node *head)

{int key;

node *New,*temp;

New=get_node();

printf("\nenter the elements which you want to insert");

scanf("%d",&New->data);

if(head==NULL)

{head=New;

}else

{printf("\enter the element which you want to insert the node");

scanf("%d",&key);

temp=head;

do

{if(temp->data==key)

{New->next-temp->next;

temp->next=New;

return;

}else

temp=temp->next;

}while(temp!=NULL);

}}node *get_prev(node *head,int val)

{node *temp,*prev;

int flag;

temp=head;

if(temp==NULL)

return NULL;

flag=FALSE;

prev=NULL;

while(temp!=NULL && ! flag)

{if(temp->data!=val)

{prev=temp;

temp=temp->next;

}else

flag=TRUE;

}if(flag)

return prev;

else

return NULL;

}void dele(node **head)

{node *temp,*prev;

int key;

temp=*head;

if(temp==NULL)

{printf("\nthe list is empty\n");

return;

}printf("\nenter the element you want to delete:");

scanf("%d",&key);

temp=search(*head,key);

if(temp!=NULL)

{prev=get_prev(*head,key);

if(prev!=NULL)

{prev->next=temp->next;
free(temp);}

else

{*head=temp->next;

free(temp);}

printf("\nthe element is deleted\n");}}

OUTPUT
 Program 11

Generate lexical analyzer using lex

%{

int COMMENT=0;

%}

identifier [a-zA-Z][a-zA-Z0-9]*

%%

#.* {printf("\n%s is a preprocessor directive",yytext);}

int |

float |

char |

double |

while |

for |

struct |

typedef |

do |

if |

break |

continue |

void |

switch |

return |

else |

goto {printf("\n\t%s is a keyword",yytext);}

"/*" {COMMENT=1;}{printf("\n\t %s is a COMMENT",yytext);}

{identifier}\( {if(!COMMENT)printf("\nFUNCTION \n\t%s",yytext);}

\{ {if(!COMMENT)printf("\n BLOCK BEGINS");}

\} {if(!COMMENT)printf("BLOCK ENDS ");}

{identifier}(\[[0-9]*\])? {if(!COMMENT) printf("\n %s IDENTIFIER",yytext);}

\".*\" {if(!COMMENT)printf("\n\t %s is a STRING",yytext);}

[0-9]+ {if(!COMMENT) printf("\n %s is a NUMBER ",yytext);}

\)(\:)? {if(!COMMENT)printf("\n\t");ECHO;printf("\n");}

\( ECHO;

= {if(!COMMENT)printf("\n\t %s is an ASSIGNMENT OPERATOR",yytext);}

\<= |

\>= |

\< |

== |

\> {if(!COMMENT) printf("\n\t%s is a RELATIONAL OPERATOR",yytext);}

%%

int main(int argc, char **argv)

FILE *file;

file=fopen("var.c","r");

if(!file)

printf("could not open the file");

exit(0);

yyin=file;

yylex();

printf("\n");

return(0);

int yywrap()
{

return(1);

INPUT:

//var.c

#include<stdio.h>

#include<conio.h>

void main()

int a,b,c;

a=1;

b=2;

c=a+b;

printf("Sum:%d",c);

OUTPUT
11. Generate YACC specification for a syntactic categories

Program name:arith_id.l

%{

/* This LEX program returns the tokens for the expression */

#include “y.tab.h”

%}

%%

“=” {printf(“\n Operator is EQUAL”);}

“+” {printf(“\n Operator is PLUS”);}

“-“ {printf(“\n Operator is MINUS”);}

“/” {printf(“\n Operator is DIVISION”);}

“*” {printf(“\n Operator is MULTIPLICATION”);}

[a-z A-Z]*[0-9]* {

printf(“\n Identifier is %s”,yytext);

return ID;

return yytext[0];

\n return 0;

%%

int yywrap()

return 1;

Program Name : arith_id.y

%{
#include

/* This YYAC program is for recognizing the Expression */

%}

%%

statement: A’=’E

|E{

printf(“\n Valid arithmetic expression”);

$$ = $1;

};

E: E’+’ID

| E’-’ID

| E’*’ID

| E’/’ID

| ID

%%

extern FILE *yyin;

main()

do

yyparse();

}while(!feof(yyin));

yyerror(char*s)

{
}

OUTPUT
[root@localhost]# lex arith_id.1

[root@localhost]# yacc –d arith_id.y

[root@localhost]# gcc lex.yy.c y.tab.c

[root@localhost]# ./a.out

x=a+b;

Identifier is x

Operator is EQUAL

Identifier is a

Operator is PLUS

Identifier is b
 Program 12

Given any intermediate code form implement code optimization

techniques.

//Code Optimization Technique

#include<stdio.h>
#include<string.h>
struct op
{
char l;
char r[20];
}
op[10],pr[10];
void main()
{
int a,i,k,j,n,z=0,m,q;
char *p,*l;
char temp,t;
char *tem;
printf("Enter the Number of Values:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("left: ");
scanf(" %c",&op[i].l);
printf("right: ");
scanf(" %s",&op[i].r);
}
printf("Intermediate Code\n") ;
for(i=0;i<n;i++)
{
printf("%c=",op[i].l);
printf("%s\n",op[i].r);
}
for(i=0;i<n-1;i++)
{
temp=op[i].l;
for(j=0;j<n;j++)
{
p=strchr(op[j].r,temp);
if(p)
{
pr[z].l=op[i].l;
strcpy(pr[z].r,op[i].
r);
z++;
}
}
}
pr[z].l=op[n-1].l;
strcpy(pr[z].r,op[n-1].r);
z++;
printf("\nAfter Dead Code Elimination\n");
for(k=0;k<z;k++)
{
printf("%c\t=",pr[k].l);
printf("%s\n",pr[k].r);
}
for(m=0;m<z;m++)
{
tem=pr[m].r;
for(j=m+1;j<z;j++)
{
p=strstr(tem,pr[j].r);
if(p)
{
t=pr[j].l;
pr[j].l=pr[m].l;
for(i=0;i<z;i++)
{
l=strchr(pr[i].r,t) ;
if(l)
{
a=l-pr[i].r;
printf("pos: %d\n",a);
pr[i].r[a]=pr[m].l;
}}}}}
printf("Eliminate Common Expression\n");
for(i=0;i<z;i++)
{
printf("%c\t=",pr[i].l);
printf("%s\n",pr[i].r);
}
for(i=0;i<z;i++)
{
for(j=i+1;j<z;j++)
{
q=strcmp(pr[i].r,pr[j].r);
if((pr[i].l==pr[j].l)&&!q)
{
pr[i].l='\0';
}
}
}
printf("Optimized Code\n");
for(i=0;i<z;i++)
{
if(pr[i].l!='\0')
{
printf("%c=",pr[i].l);
printf("%s\n",pr[i].r);
}
}
}
OUTPUT: