Compiler Design Lab Practicals with Solution Computer Science and Engineering

Compiler Design Lab Practicals with Solution Computer Science and Engineering



Exp. No.
Experiment Name
Date
Remarks
1
Develop a lexical analyzer to recognize a few patterns.


2
Write a program to parse using Brute force technique of Top down parsing.


3
Develop LL (1) parser (Construct parse table also).


4
Develop an operator precedence parser (Construct parse table also)


5
Develop a recursive descent parser


6
Write a program for generating for various intermediate code forms
(1)   Three address code (2) Input string into postfix notation.


7
Write a program to simulate Heap storage allocation strategy.


8
Generate Lexical analyzer using LEX


9
Generate YACC specification for a few syntactic categories.


10
Given any intermediate code form implement code optimization techniques.                                                         


11
Study of an Object Oriented Compiler.








Experiment No. 1
Develop a lexical analyzer to recognize a few patterns.

#include<stdio.h> 
#include<conio.h>
#include<iostream.h>
#define SIZE 128
#define NONE -1
#define EOS ‘\0’
#define NUM 256
#define KEYWORD 257
#define PAREN 258
#define ID 259
#define ASSIGN 260
#define REL_OP 261
#define DONE 262
#define MAX 999
char lexemes[MAX];
char buffer[SIZE];
int lastchar = -1;
int lastentry = 0;
int tokenval=NONE;
int lineno=1;
struct entry
{
char *lexptr;
int token;
}symtable[100];
struct entry keywords[]={“if”,KEYWORD,”else”,KEYWORD,”for”,KEYWORD,
“int”,KEYWORD,”float”,KEYWORD,”double”,KEYWORD,”char”,KEYWORD, “struct”,KEYWORD,”return”,KEYWORD,0,0};
void Error_Message(char *m)
{
fprint(stderr,”line %d: %s”,lineno,m);
exit(1);
}
int look_up(char s[])
{
int k;
for(k=lastentry;k>0;k--)
if(strcmp(symtable[k].lexptr,s)==0)
return k;
return 0;
}
int insert(chars[],int tok)
{
int len;
len=strlen(s);
if(lastentry+1>=MAX)
Error_Message(“Symbol Table is Full”);
if(lastchar+len+1>=MAX)
Error_Message(“Lexemes Array is Full”);
lastentry++;
symtable[lastentry].token=tok;
symtable[lastentry].lexptr=&lexemes[lastcher+1];
lastchar = lastchar + len + 1;
strcpy(smtable[lastentry].lexptr,s);
return lastentry;
}
void Initialize()

{

struct entry *ptr;

for(ptr=keywords;ptr->token;ptr++)

insert(ptr->lexptr,ptr->token);

}


int lexer()

{

int t;

int val,i=0;

while(1)

{

t=getchar();

if(t == ’’ || t==’\t’);

else if(t==’\n’)

lineno++;

else if(t == ’(‘ || t == ‘)’)

return PAREN;

else if(t==‘<’ ||t==‘>’ ||t==‘<=’ ||t==‘>=’ ||t == ‘!=’)

return REL_OP;

else if(t == ’=’)

return ASSIGN;

else if(isdigit(t))

{

ungetc(t,stdin);

scanf(“%d”,&tokenval);

return NUM;

}

else if(isalpha(t))

{

while(isalnum(t))

{

buffer[i]=t;

t=getchar();

i++;

if(i>=SIZE)

Error_Message(“compiler error”);

}

buffer[i]=EOS;

if(t!=EOF)

ungetc(t,stdin);

val=look_up(buffer);

if(val==0)

val=insert(buffer,ID);

tokenval=val;

return symtable[val].token;

}

else if(t==EOF)

return DONE;

else

{

tokenval=NONE;

return t;

}

}

}


void main()

{

int lookahead;

char ans;

clrscr();

printf(“\n]t]t Program for Lexical Analysis \n”);

Initialize();

printf(“\n Enter the expression and put ; at the end”);

printf(“\n Press Ctrl + Z to terminate... \n”);

lookahead=lexer();

while(lookahead!=DONE)

{

if(lookahead==NUM)

printf(“\n Number: %d”,tokenval);

if(lookahead==’+’|| lookahead==’-’|| lookahead==’*’|| lookahead==’/’)

printf(“\n Operator”);

if(lookahead==PAREN)

printf(“\n Parentesis”);

if(lookahead==ID)

printf(“\n Identifier: %s“,

symtable[tokenval].lexptr);

if(lookahead==KEYWORD)

printf(“\n Keyword);

if(lookahead==ASSIGN)

printf(“\n Assignment Operator”);

if(lookahead==REL_OP)

printf(“\n Relataional Operator”);

lookahead=lexer();

}

}













OUTPUT:


Program for Lexical Analysis

Enter the expression and put; at the end

Press Ctrl + Z to terminate...

2+3

Number: 2

Operator

Number: 3

if(a


Keyword

Parenthesis

Identifier: a

Relational Operator

Identifier: b

Parenthesis

Identifier: a

Assigment Operator

Identifier: a

Operator

Identifier: b



Experiment No. 2
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();
}



OUTPUT

please enter how many number

4
enter value of root
2

please enter no of child of parent with value
2

temp min is
16

min is
2




 
Experiment No. 3

 Develop LL (1) parser (Construct parse table also).

#include <iostream.h>
#include <conio.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
void main()
{
    clrscr();
    int i=0,j=0,k=0,m=0,n=0,o=0,o1=0,var=0,l=0,f=0,c=0,f1=0;
    char     str[30],str1[40]="E",temp[20],temp1[20],temp2[20],tt[20],t3[20];
    strcpy(temp1,'\0');
    strcpy(temp2,'\0');
    char t[10];
    char array[6][5][10] = {
                 "NT", "<id>","+","*",";",
                 "E", "Te","Error","Error","Error",
                 "e", "Error","+Te","Error","\0",
                 "T", "Vt","Error","Error","Error",
                 "t", "Error","\0","*Vt","\0",
                 "V", "<id>","Error","Error","Error"
                  };
    cout << "\n\tLL(1)  PARSER  TABLE \n";
    for(i=0;i<6;i++)
    {
        for(j=0;j<5;j++)
        {
            cout.setf(ios::right);
            cout.width(10);
            cout<<array[i][j];
        }
        cout<<endl;
    }
    cout << endl;
    cout << "\n\tENTER THE STRING :";
    gets(str);
    if(str[strlen(str)-1] != ';')
    {
          cout << "END OF STRING MARKER SHOULD BE ';'";
          getch();
          exit(1);
    }
    cout << "\n\tCHECKING VALIDATION OF THE STRING ";
    cout <<"\n\t" << str1;
    i=0;
   
while(i<strlen(str))
    {
     again:
          if(str[i] == ' ' && i<strlen(str))
          {
               cout << "\n\tSPACES IS NOT ALLOWED IN SOURSE STRING ";
               getch();
               exit(1);
          }
          temp[k]=str[i];
          temp[k+1]='\0';
          f1=0;
     again1:
          if(i>=strlen(str))
          {
               getch();
               exit(1);
          }
          for(int l=1;l<=4;l++)
          {
            if(strcmp(temp,array[0][l])==0)
            {
                f1=1;
                m=0,o=0,var=0,o1=0;
                strcpy(temp1,'\0');
                strcpy(temp2,'\0');
                int len=strlen(str1);
                while(m<strlen(str1) && m<strlen(str))
                {
                      if(str1[m]==str[m])
                      {
                           var=m+1;
                           temp2[o1]=str1[m];
                           m++;
                           o1++;
                      }
                      else
                      {
                           if((m+1)<strlen(str1))
                           {
                               m++;
                               temp1[o]=str1[m];
                               o++;
                           }
                           else
                               m++;
                      }

                }
                temp2[o1] = '\0';
                temp1[o] = '\0';
                t[0] = str1[var];
                t[1] = '\0';
                for(n=1;n<=5;n++)
                {
                    if(strcmp(array[n][0],t)==0)
                        break;
                }
                strcpy(str1,temp2);
                strcat(str1,array[n][l]);
                strcat(str1,temp1);
                cout << "\n\t" <<str1;
                getch();

                if(strcmp(array[n][l],'\0')==0)
                {
                    if(i==(strlen(str)-1))
                    {
                          int len=strlen(str1);
                          str1[len-1]='\0';
                          cout << "\n\t"<<str1;
                          cout << "\n\n\tENTERED STRING IS                      VALID";
                          getch();
                          exit(1);
                      }
                      strcpy(temp1,'\0');
                      strcpy(temp2,'\0');
                      strcpy(t,'\0');
                      goto again1;
                }
                if(strcmp(array[n][l],"Error")==0)
                {
                      cout << "\n\tERROR IN YOUR SOURCE STRING";
                      getch();
                      exit(1);
                }
                strcpy(tt,'\0');
                strcpy(tt,array[n][l]);
                strcpy(t3,'\0');
                f=0;
                for(c=0;c<strlen(tt);c++)
                {
                     t3[c]=tt[c];
                     t3[c+1]='\0';
                     if(strcmp(t3,temp)==0)
                     {
                           f=0;
                           break;
                     }
                     else
                           f=1;
                 }

                 if(f==0)
                 {
                    strcpy(temp,'\0');
                    strcpy(temp1,'\0');
                    strcpy(temp2,'\0');
                    strcpy(t,'\0');
                    i++;
                    k=0;
                    goto again;
                 }
                 else
                 {
                    strcpy(temp1,'\0');
                    strcpy(temp2,'\0');
                    strcpy(t,'\0');
                    goto again1;
                }
            }
          }
          i++;
          k++;
    }
    if(f1==0)
           cout << "\nENTERED STRING IS INVALID";
    else
          cout << "\n\n\tENTERED STRING IS VALID";
    getch();
}



OUTPUT
*********

    LL(1)  PARSER  TABLE

    NT      <id>         +         *         ;
    E        Te     Error     Error     Error
    e     Error       +Te     Error
    T        Vt     Error     Error     Error
    t     Error                 *Vt
    V      <id>     Error     Error     Error

    ENTER THE STRING :<id>+<id>*<id>;

CHECKING VALIDATION OF THE STRING
            E
            Te
            Vte
            <id>te
            <id>e
            <id>+Te
            <id>+Vte
            <id>+<id>te
            <id>+<id>*Vte
            <id>+<id>*<id>te
            <id>+<id>*<id>e
            <id>+<id>*<id>
            ENTERED STRING IS VALID






Experiment No. 4

 Develop an operator precedence parser (Construct parse table also)
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>

int getOperatorPosition(char );

#define node struct tree1

int matrix[5][5]={
        {1,0,0,1,1},
        {1,1,0,1,1},
        {0,0,0,2,3},
        {1,1,3,1,1},
        {0,0,0,3,2}};
int tos=-1;
void matrix_value(void);
//node create_node(char,*node);void show_tree( node *);
int isOperator(char );

struct tree1
{
   char data;
   node  *lptr;
   node  *rptr;
}*first;


struct opr
{
    char op_name;
    node *t;
}oprate[50];


char cur_op[5]={'+','*','(',')','['};
char stack_op[5]={'+','*','(',')',']'};

void  main()
{
    char exp[10];

    int ssm=0,row=0,col=0;
    node *temp;
//    clrscr();

    printf("Enter Exp : ");
    scanf("%s",exp);

    matrix_value();
    while(exp[ssm] != '\0')
    {
        if(ssm==0)
        {
            tos++;
            oprate[tos].op_name = exp[tos];
        }
        else
        {
            if(isOperator(exp[ssm]) == -1)
            {
                oprate[tos].t = (node*) malloc (sizeof(node));
                oprate[tos].t->data = exp[ssm];
                oprate[tos].t->lptr = '\0';
                oprate[tos].t->rptr = '\0';
            }
            else
            {
                row = getOperatorPosition(oprate[tos].op_name);
                col = getOperatorPosition(exp[ssm]);
                if(matrix[row][col] == 0)
                {
                    tos++;
                    oprate[tos].op_name = exp[ssm];
                }
                elseif(matrix[row][col] == 1)
                {
                    temp = (node*) malloc (sizeof(node));
                    temp->data = oprate[tos].op_name;

                    temp->lptr = (oprate[tos-1].t);
                    temp->rptr = (oprate[tos].t);
                    tos--;

                    oprate[tos].t = temp;

                    ssm--;
                }
                elseif(matrix[row][col] == 2)
                {
                    //temp = (node*) malloc (sizeof(node));
                    temp = oprate[tos].t;
                    tos--;
                    oprate[tos].t = temp;
                }
                elseif(matrix[row][col] == 3)
                {
                                  printf("\nExpression is Invalid...\n");
   printf("%c  %c can not occur simultaneously\n",oprate[tos].op_name,exp[ssm]);
                    break;
                }
            }

        }

        ssm++;
    }
    printf("show tree \n\n\n");
    show_tree(oprate[tos].t);
    printf("Over");
    getch();
    getch();
}

int isOperator(char c)
{
    int i=0;
     for(i=0;i<5;i++)
     {
        if (c==cur_op[i] || c==stack_op[i])
            break;
     }

     if(i==5)
        return (-1);
     elsereturn i;

}

int getOperatorPosition(char c)
{
    int i;
    for(i=0;i<5;i++)
    {
        if (c==cur_op[i] || c==stack_op[i])
            break;
    }
    return i;

}

void show_tree(node *start)
{
    if(start->lptr != NULL)
        show_tree(start->lptr);

    if(start->rptr != NULL)
        show_tree(start->rptr);

    printf("%c \n",start->data);
}

void matrix_value(void)
{
     int i,j;
     printf("OPERATOR PRECEDENCE MATRIX\n");
     printf("===========================\n   ");

 for(i=0; i<5; i++)
 {
    printf("%c ",stack_op[i]);
 }
 printf("\n");

 for(i=0;i<5;i++)
 {
    printf("%c  ",cur_op[i]);
   for(j=0;j<5;j++)
   {
        if(matrix[i][j] == 0)
            printf("< ");
        elseif(matrix[i][j] == 1)
            printf("> ");
        elseif(matrix[i][j] == 2)
            printf("= ");
        elseif(matrix[i][j] == 3)
            printf("  ");
    }
    printf("\n");
 }

}

              OUTPUT:


Enter Exp : [a+b*c]
OPERATOR PRECEDENCE MATRIX
===========================
   + * ( ) ]
+  > < < > >
*  > > < > >
(  < < < =
)  > >   > >
[  < < <   =
show tree

                                                                               
a                                                                              
b                                                                              
c                                                                               
*                                                                              
+                                                                              
Over                                                                            
Enter Exp : [a+(b*c)+d]
OPERATOR PRECEDENCE MATRIX                                                     
===========================                                                    
   + * ( ) ]                                                                   
+  > < < > >                                                                   
*  > > < > >                                                                   
(  < < < =                                                                      
)  > >   > >                                                                   
[  < < <   =                                                                   
show tree                                                                       
                                                                               
                                                                               
a                                                                               
b                                                                              
c                                                                              
*                                                                               
+                                                                              
d                                                                              
+                                                                               
Over                                                                           
Enter Exp : [)]
OPERATOR PRECEDENCE MATRIX                                                     
===========================                                                     
   + * ( ) ]                                                                   
+  > < < > >                                                                   
*  > > < > >                                                                   
(  < < < =                                                                     
)  > >   > >                                                                   
[  < < <   =                                                                   
                                                                                
Expression is Invalid...                                                       
[  ) can not occur simultaneously                                              
show tree                                                                       
.Over

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



Experiment No. 5

Develop a recursive descent parser

#include<stdio.h>
static char c[10];
int j=0;
int main()
{
    printf("Enter a string\n");
    scanf("%s",c);
    E();
    if(c[j]=='$')
        printf("Valid string\n");
    else
        printf("Invalid string\n");
    return 0;
}
E()
{
    Y();
    Eprime();
    return;
}
X()
{
    if(c[j]=='+')
    {
        j++;
        E();
    }
    else if(c[j]=='*')
    {
        j++;
        E();
    }
    return;
}
Y()
{
    if(c[j]=='(')
    {
        j++;
        E();
        if(c[j]==')')
            j++;
    }
    else if(c[j]=='i')
        j++;
    return;
}

Eprime()
{
    X();
    Eprime();
    return;
}


OUTPUT:
Enter an expression : a+b*c+d
its a valid expression
a   +   b   *   c   +   d

enter an expression :a+b*+
error



Experiment No. 6

 Write a program for generating for various intermediate code forms
i)                   Three address code

#include<stdio.h>

#include<string.h>

#include<ctype.h>

void input();

void output();

void change(int p,int q,char *res);

void constant();

void expression();

struct expr

{

char op[2],op1[5],op2[5],res[5];

int flag;

}arr[10];

int n;

int main()

{

int ch=0;

input();

constant();

expression();

output();

}

void input()

{

int i;

printf(“\n\nEnter the maximum number of  expressions : “);

scanf(“%d”,&n);

printf(“\nEnter the input : \n”);

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

{

scanf(“%s”,arr[i].op);

scanf(“%s”,arr[i].op1);

scanf(“%s”,arr[i].op2);

scanf(“%s”,arr[i].res);

arr[i].flag=0;

}

}

void constant()

{

int i;

int op1,op2,res;

char op,res1[5];

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

{

if(isdigit(arr[i].op1[0]) && isdigit(arr[i].op2[0])) //if both digits, store them in variables

{

op1=atoi(arr[i].op1);

op2=atoi(arr[i].op2);

op=arr[i].op[0];

switch(op)

{

case ‘+’:

res=op1+op2;

break;



case ‘-’:

res=op1-op2;

break;
case ‘*’:

res=op1*op2;

break;

case ‘/’:

res=op1/op2;

break;

}

sprintf(res1,”%d”,res);

arr[i].flag=1; //eliminate expr and replace any operand below that uses result of this expr



change(i,i,res1);

}

}

}

void expression()

{

int i,j;

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

{

for(j=i+1;j<n;j++)

{

if(strcmp(arr[i].op,arr[j].op)==0) //if operators are same

{

if(strcmp(arr[i].op,”+”)==0||strcmp(arr[i].op,”*”)==0) //order doesn’t matter if operators are + or *

{

if(strcmp(arr[i].op1,arr[j].op1)==0&&strcmp(arr[i].op2,arr[j].op2)==0 || strcmp(arr[i].op1,arr[j].op2)==0&&strcmp(arr[i].op2,arr[j].op1)==0)

{

arr[j].flag=1; //does’t print

change(i,j,NULL); //change any operand below that uses result of this expression

}

}

else

{

if(strcmp(arr[i].op1,arr[j].op1)==0&&strcmp(arr[i].op2,arr[j].op2)==0)

{

arr[j].flag=1;

change(i,j,NULL);

}

}

}

}

}

}

void output()

{

int i=0;

printf(“\nOptimized code is : “);

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

{

if(!arr[i].flag)

{

printf(“\n%s %s %s %s”,arr[i].op,arr[i].op1,arr[i].op2,arr[i].res);

}

}

}

void change(int p,int q,char *res)

{

int i;

for(i=q+1;i<n;i++)

{

if(strcmp(arr[q].res,arr[i].op1)==0)

if(res == NULL)                         //for csub

strcpy(arr[i].op1,arr[p].res);

else                                    //for ceval

strcpy(arr[i].op1,res);

else if(strcmp(arr[q].res,arr[i].op2)==0)

if(res == NULL)                         //for csub

strcpy(arr[i].op2,arr[p].res);

else                                    //for ceval

strcpy(arr[i].op2,res);

}

}

 INPUT / OUTPUT :

[Codearea@localhost ~]$ cc CodeOptimization.c

[Codearea@localhost ~]$ ./a.out

Enter the maximum number of  expressions : 5

Enter the input :

+ 4 2 t1

+ a t1 t2

- b a t3

+ a 6 t4

* t3 t4 t5

Optimized code is :

+ a 6 t2

- b a t3

* t3 t2 t5



(ii) Write a program to convert given input string into postfix notation.

      #include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#define N 64
#define LP 10
#define RP 20
#define OPERATOR 30
#define OPERAND 40

// Left parentheses precedence. Minimum of all
#define LPP 0

// Addition Subtraction precedence. Minimum among all operator precedence
#define AP 1
#define SP AP

// Multiplication divisor precedence.
#define MP 2
#define DP MP

// Remainder precedence.
#define REMP 2

#define NONE 9

static char infix[N+1],stack[N],postfix[N+1];
static int top;

void infixtopostfix(void);     /** POSTFIX CONVERSION FUNCTION **/
int gettype(char);             /** TYPE OF EXPRESSION GENERATOR **/
void push(char);               /** PUSH FUNCTION **/
char pop(void);                /** POP FUNCTION **/
int getprec(char);             /** PRECEDENCE CHECKER FUNCTION **/

void main()
{
    char ch;
    do
    {
      top=-1;
      printf("\nEnter an infix expression\n");
      fflush(stdin);
      gets(infix);
      infixtopostfix();
      printf("\ninfix = %s\npost fix =%s\n",infix,postfix);
      printf("\nDo you wish to continue\n");
      ch=getche();
    }while(ch=='Y' || ch=='y');
}

void infixtopostfix(void)
{
    int i,p,l,type,prec;
    char next;
    i=p=0;
    l=strlen(infix);
    while(i<l)
    {
      type=gettype(infix[i]);
      switch(type)
      {
      case LP:
          push(infix[i]);
          break;
      case RP:
          while((next=pop())!='(')
                  postfix[p++]=next;
          break;
      case OPERAND:
          postfix[p++]=infix[i];
          break;
      case OPERATOR:
          prec=getprec(infix[i]);
          while(top>-1 && prec <= getprec(stack[top]))
                  postfix[p++]=pop();
          push(infix[i]);
          break;
      }
      i++;
    }
    while(top>-1)
      postfix[p++]=pop();
    postfix[p]='\0';
}
int gettype(char sym)
{
    switch(sym)
    {
    case '(':
      return(LP);
    case ')':
      return(RP);
    case '+':
    case '-':
    case '*':
    case '/':
    case '%':
      return(OPERATOR);
    default :
      return(OPERAND);
    }
}

void push(char sym)
{
    if(top>N)
    {
      printf("\nStack is full\n");
      exit(0);
    }
    else
      stack[++top]=sym;
}

char pop(void)
{
    if(top<=-1)
    {
      printf("\nStack is empty\n");
      exit(0);
    }
    else
      return(stack[top--]);
}

int getprec(char sym)
{
    switch(sym)
    {
    case '(':
      return(LPP);
    case '+':
      return(AP);
    case '-':
      return(SP);
    case '*':
      return(MP);
    case '/':
      return(DP);
    case '%':
      return(REMP);
    default :
      return(NONE);
    }
}

OUTPUT:
ENTER THE EXPRESSION:   a+b*c
Postfix-----> abc*+




Experiment No. 7

Write a program to simulate Heap storage allocation strategy.

#include<stdio.h>
#include<conio.h>
void manage(int *, int);
void heapsort(int *, int, int);
int main()
{
 int arr[20];
 int i,j,size,tmp,k;
 printf("\n\t------- Heap allocation -------\n\n");
 printf("Enter the number of elements to sort : ");
 scanf("%d",&size);
 for(i=1; i<=size; i++)
 {
   printf("Enter %d element : ",i);
   scanf("%d",&arr[i]);
   manage(arr,i);
 }
 j=size;
 for(i=1; i<=j; i++)
 {
   tmp=arr[1];
   arr[1]=arr[size];
   arr[size]=tmp;
   size--;
   heapsort(arr,1,size);
 }
 printf("\n\t------- Heap sorted elements -------\n\n");
 size=j;
 for(i=1; i<=size; i++)
     printf("%d ",arr[i]);
 getch();
 return 0;
}


void manage(int *arr, int i)
{
 int tmp;
 tmp=arr[i];
 while((i>1)&&(arr[i/2]<tmp))
 {
   arr[i]=arr[i/2];
   i=i/2;
 }
 arr[i]=tmp;
}


void heapsort(int *arr, int i, int size)
{
 int tmp,j;
 tmp=arr[i];
 j=i*2;
 while(j<=size)
 {
   if((j<size)&&(arr[j]<arr[j+1]))
      j++;
   if(arr[j]<arr[j/2])
      break;
   arr[j/2]=arr[j];
   j=j*2;
 }
 arr[j/2]=tmp;
}


OUTPUT:
Enter the elements
35, 54,12,11,40
Sorted Elements:
11, 12, 35, 40, 54


Experiment No. 8
Generate Lexical analyzer using LEX

/* program name is lexp.l */
%{
/* program to recognize a c program */
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 |
do |
if |
break |
continue |
void |
switch |
case |
long |
struct |
const |
typedef |
return |
else |
goto {printf("\n\t%s is a KEYWORD",yytext);}
"/*" {COMMENT = 1;}
/*{printf("\n\n\t%s is a COMMENT\n",yytext);}*/
"*/" {COMMENT = 0;}
/* printf("\n\n\t%s is a COMMENT\n",yytext);}*/
{identifier}\( {if(!COMMENT)printf("\n\nFUNCTION\n\t%s",yytext);}
\{ {if(!COMMENT) printf("\n BLOCK BEGINS");}
\} {if(!COMMENT) printf("\n 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\t%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)
{
if (argc > 1)
{
FILE *file;
file = fopen(argv[1],"r");
if(!file)
{
printf("could not open %s \n",argv[1]);
exit(0);
}
yyin = file;
}
yylex();
printf("\n\n");
return 0;
} int yywrap()
{
return 0;
}
Input:
$vi var.c
#include<stdio.h>
main()
{
int a,b;
}
Output:
#include<stdio.h> is a PREPROCESSOR DIRECTIVE
FUNCTION
main (
)
BLOCK BEGINS
int is a KEYWORD
a IDENTIFIER
b IDENTIFIER
BLOCK ENDS




Experiment No. 8
Write a program For Recognizing Arithmetic Symbols from a Text File.
#include<fstream.h>
#include<stdio.h>
int main()
{
            ifstream fin;
            fin.open("I:\\digit.txt");
            char ch;
            int plus = 0;
            int minus = 0;
            int multiply = 0;
            int divide = 0;
            int modulus = 0;
            int other = 0;

            printf("\n");
            while(!fin.eof())
            {


                        if(ch=='+')
                                    plus++;
                        else if(ch=='-')
                                    minus++;
                        else if(ch=='*')
                                    multiply++;
                        else if(ch=='/')
                                    divide++;
                        else if(ch=='%')
                                    modulus++;
                        else
                                    other++;
                        fin>>ch;
            }

            printf("\n+ = %d",plus);
            printf("\n- = %d",minus);
            printf("\n* = %d",multiply);
            printf("\n/ = %d",divide);
            printf("\n% = %d",modulus);
            printf("\no = %d",other);
            return 0;

}
OUTPUT
plus
minus
multiply
divide
modulus
other
Experiment No. 9

a)    Program to recognize a valid arithmetic expression that uses operator +, - , * and /.

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;
}



%{
#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:

x=a+b;
Identifier is x
Operator is EQUAL
Identifier is a
Operator is PLUS
Identifier is b








Experiment No. 10
#include<stdio.h>
#include<conio.h>
#define BLOCKSIZE (8)
void main(void)
{
int i = 0;
int limit = 33;  /* could be anything */
int blocklimit;
/* The limit may not be divisible by BLOCKSIZE,
 * go as near as we can first, then tidy up.
 */
blocklimit = (limit / BLOCKSIZE) * BLOCKSIZE;
clrscr();
/* unroll the loop in blocks of 8 */
while( i < blocklimit )
{
    printf("process(%d)\n", i);
    printf("process(%d)\n", i+1);
    printf("process(%d)\n", i+2);
    printf("process(%d)\n", i+3);
    printf("process(%d)\n", i+4);
    printf("process(%d)\n", i+5);
    printf("process(%d)\n", i+6);
    printf("process(%d)\n", i+7);
    /* update the counter */
    i += 8;
}


OUTPUT:

process(0)
process(1)
process(2)
process(3)
process(4)
process(5)
process(6)
process(7)
process(8)
process(9)
process(10)
process(11)
process(12)
process(13)
process(14)
process(15)
process(16)
process(17)
process(18)
process(19)
process(20)
process(21)
process(22)
process(23)
process(24)



Experiment No. 11

                  
Study of an Object Oriented Compiler.


                  
A Compiler is a program that can read a program in one language – the source language and translate it into an equivalent program in another language – the Target language . An important role of the compiler is to report any errors in the source program that it detects during the translation process.
An object-oriented language is one that supports object-oriented programming, a programming style in which a program consists of a collection of objects (i.e. classes) that interact with one another.
                     The obvious candidate for object technology in a compiler is the symbol table, a mapping from user-defined names to their properties as expressed in the program. If the internal representation is a tree of objects, semantic checking and generation can be accomplished by sending a message to these objects or by visiting each object. If the result of generation is a set of persistent objects, program execution can consist of sending a message to a distinguished object in this set.
Object orientation was first introduced in Simula ( in 1967), and has been incorporated in languages such as Smalltalk, C++, C#, and Java.
We have gained them in several projects and used them to great advantage in two courses on compiler construction with Objective C and Java It turns out that OOP can be applied productively in every phase of a compiler implementation and it delivers the expected benefits as :
Objects enforce information hiding and state encapsulation,
Methods help to develop by divide and conquer technique.
All work is carried out by messages , which can be debugged by incrementing their methods.
Most importantly, classes encourage code reuse between projects .
Inheritance allows code reuse within a project and modifications from one project to another.
                  Modern class libraries contain many pre-fabricated algorithms and data structures.



No comments:

Post a Comment

Workout and Fitness

Latest Update

Recent Posts Widget