Intermediate code generation for sample language using LEX and YACC.

CL1_A5.l :

%{
   #include "y.tab.h"
   extern char yyval;
%}

%%
[0-9]+         {yylval.symbol=(char)yytext[0]; return NUMBER;}
[a-zA-Z]+   {yylval.symbol=(char)yytext[0];return LETTER;}

\n {return 0;}
.  {return yytext[0];}

%%


CL1_A5.y :

%{
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    void ThreeAddressCode();
    void Triple();
    void Qudraple();
    char AddtoTable(char ,char, char);

    int index1=0;
    char temp='A';
    struct expr
    {
        char operand1;
        char operand2;
        char operator;
      };
%}

%union
{
    char symbol;
}

%token <symbol> LETTER NUMBER
%type <symbol> exp
%left '-''+'
%right '*''/'

%%

statement: LETTER '=' exp ';' {AddtoTable((char)$1,(char)$3,'=');}
           | exp ';'
       ;

exp: exp '+' exp {$$ = AddtoTable((char)$1,(char)$3,'+');}
      | exp '-' exp {$$ = AddtoTable((char)$1,(char)$3,'-');}
      | exp '*' exp {$$ = AddtoTable((char)$1,(char)$3,'*');}
      | exp '/' exp {$$ = AddtoTable((char)$1,(char)$3,'/');}
      | '(' exp ')' {$$ = (char)$2;}
      | NUMBER {$$ = (char)$1;}
      | LETTER {$$ = (char)$1;}
      ;

%%

yyerror(char *s)
{
  printf("%s",s);
  exit(0);
}

struct expr arr[20];
int id=0;

char AddtoTable(char operand1,char operand2,char operator)
{
    arr[index1].operand1=operand1;
    arr[index1].operand2=operand2;
    arr[index1].operator=operator;
    index1++;
    temp++;
    return temp;
}

void ThreeAddressCode()
{
    int cnt=0;
    temp++;
    printf("\n\n\t THREE ADDRESS CODE\n\n");
    while(cnt<index1)
    {
        printf("%c : = \t",temp);  
        if(isalpha(arr[cnt].operand1))
            printf("%c\t",arr[cnt].operand1);
        else
            {printf("%c\t",temp);}
        printf("%c\t",arr[cnt].operator);
        if(isalpha(arr[cnt].operand2))
            printf("%c\t",arr[cnt].operand2);
        else
            {printf("%c\t",temp);}
        printf("\n");
        cnt++;
        temp++;
    }
}

void Quadraple()
{
    int cnt=0;
    temp++;
    printf("\n\n\t QUADRAPLE CODE\n\n");
    while(cnt<index1)
    {
        printf("%d",id);
        printf("\t");      
        printf("%c",arr[cnt].operator);
        printf("\t");   
            if(isalpha(arr[cnt].operand1))
                printf("%c\t",arr[cnt].operand1);
            else
                {printf("%c\t",temp);}  
            if(isalpha(arr[cnt].operand2))
                printf("%c\t",arr[cnt].operand2);
            else
                {printf("%c\t",temp);}      
            printf("%c",temp);
        printf("\n");
        cnt++;
        temp++;
        id++;  
    }
}

void Triple()
{
    int cnt=0,cnt1,id1=0;
    temp++;
    printf("\n\n\t TRIPLE CODE\n\n");
    while(cnt<index1)
    {
        if(id1==0)
        {
            printf("%d",id1);
            printf("\t");      
            printf("%c",arr[cnt].operator);
            printf("\t");   
            if(isalpha(arr[cnt].operand1))
                 printf("%c\t",arr[cnt].operand1);
            else
                {printf("%c\t",temp);}
            cnt1=cnt-1;
            if(isalpha(arr[cnt].operand2))
                printf("%c",arr[cnt].operand2);
            else
                {printf("%c\t",temp);}
        }
        else
        {
            printf("%d",id1);
            printf("\t");      
            printf("%c",arr[cnt].operator);
            printf("\t");   
            if(isalpha(arr[cnt].operand1))
                printf("%c\t",arr[cnt].operand1);
            else
                 {printf("%c\t",temp);}
            cnt1=cnt-1;
            if(isalpha(arr[cnt].operand2))
                printf("%d",id1-1);
            else
                {printf("%c\t",temp);}
        }
        printf("\n");
        cnt++;
        temp++;
        id1++; 
    }
}

main()
{
    printf("\nEnter the Expression: ");
    yyparse();
    temp='A';
    ThreeAddressCode();
    Quadraple();
    Triple();
}

yywrap()
{
    return 1;
}


OUTPUT :

Parser for sample language using YACC.

***Note : While executing the program remove the comments in blue. Comments mentioned are for understanding purpose

calc.l:

%{
//declarations for c code
#include<stdio.h>
#include"y.tab.h"
//extern because it is declared in yacc file and used here   
extern int yylval;
%}

//regular expressions and corresponding actions for input streams read
%%
[0-9]+ {
    yylval=atoi(yytext);
    return NUMBER;
    }   
    //If any number is encountered yylval stores its value and we are returning token number which shows yylval's type ie int

[\t];    //we are ignoring white spaces
[\n] return 0; 
. return yytext[0];  //return all the other characters as it is
%%

int yywrap()   //returns 1 when end of file is reached otherwise its value is 0
{
return 1;
}


calc.y :

//for c declarations
%{
#include<stdio.h>
 #include<time.h>
int flag=0;
extern FILE* yyin;    //file pointer by default points to terminal
%}

//for declarations in yacc
%token NUMBER        //declaring token NUMBER
%left '+''-'        //to maintain associativity
%left '*''/''%'
%left '('')'

//context free grammar rules and corresponding action
%%
ArithematicExpression:E{
    printf("\n Result=%d\n",$$);
    return 0;
    }

E:E'+'E{$$=$1+$3;}    //$$ refers to non-terminal on left side, $1 to first E on right and so on
|E'-'E{$$=$1-$3;}    //Pseudo varibles in {} describe action to be performed for given grammar rule
|E'*'E{$$=$1*$3;}
|E'/'E{$$=$1/$3;}
|E'%'E{$$=$1%$3;}
|'('E')'{$$=$2;}
|NUMBER{$$=$1;}
;
%%

void main()
{
clock_t starttime;
clock_t endtime;
double timeinterval;
int i;
FILE* fp=fopen("expressions.txt","r");        //file contains expression to be evaluated
yyin=fp;

starttime=clock();
yyparse();     //yyparse() in turn calls yylex()

endtime=clock();
timeinterval=(double)(endtime-starttime)/CLOCKS_PER_SEC;
printf("Time required for execution=%lf Seconds.\n",timeinterval);

if(flag==0)
{
printf("\n ENTERED ARETHEMATIC EXPRESSION IS VALID \n\n");
}

}

void yyerror()
{
printf("\n ENTERED ARETHEMATIC EXPRESSION IS INVALID \n\n");
flag=1;
}


expressions.txt:
5+2*6
3*2+1

OUTPUT: 

Lexical analyzer for sample language using LEX.

CL1_A3.l:

letter[a-zA-Z]
digit[0-9]
whitespace[\n\t]
underscore[_]

%{
#include<stdio.h>
%}

%%
{whitespace}+ ;

int|float|double|if|else|for|do|while|switch|char|continue|default|enum|void|unsigned|signed|short|long|extrn|goto|case|break|auto|register|return|const|static|struct|typedef|sizeof|union|include|main|stdio|printf|scanf printf("\n%s-->is a Keyword ",yytext);

{digit}+ printf("\n%s--> is an Integer",yytext);

({digit}*\.{digit}+) printf("\n%s--> is a Float Value",yytext);

"+"|"-"|"*"|"/"|"%" printf("\n%s--> is an Arithmetic Operator",yytext);

"&"|"|"|"!"|"^" printf("\n%s--> is a Bitwise Operator",yytext);

"&&"|"||" printf("\n%s--> is a Logical Operator",yytext);
 
"<"|">"|"<="|">="|"==" printf("\n%s--> is a Relational Operator",yytext);

"="|"=+"|"=-"|"=*"|"=/"|"=%" printf("\n%s--> is a ASSIGNMENT OPERATOR",yytext);

"%d"|"%s"|"%c"|"%f"|"%e" printf("\n%s--> is a Format Specifier",yytext); 

"{"|"}"|"["|"]"|"("|")"|"#"|"'"|"."|"\""|"\\"|";"|"," printf("\n%s--> is a Special Character",yytext); 

{letter}({letter}|{digit}|{underscore})* printf("\n%s--> is an Identifier",yytext);

\#({letter}*\<{letter}*.{letter}*>) printf("\n%s--> is a Header File",yytext);
%%

main()
{
    yyin=fopen("CL1_A3.c","r");
    yylex();
    fclose(yyin);
    printf("\n");
}

int yywrap()
{
    return 1;
}


CL1_A3.c:

#include<stdio.h>

main()
{
    int i=0;
    int a[10],b[3][3];
    float f;
    printf("HELLO");
    if(i==0)
    {
        f=10.5;
    }
    return 0;
}

OUTPUT:

Using Divide and Conquer Strategies design a class for Concurrent Quick Sort using C++.

Using Divide and Conquer Strategies design a class for Concurrent Quick Sort using C++.

#include<iostream>
#include<omp.h>

using namespace std;
int thread_id,pass_count=0;

class sort
{
    public:
        int i,length,*array=NULL;       
        void input();
        void display();
        void quick_sort (int[],int,int);
        int partition(int[],int,int);
};

void sort::input()
{
    cout<<"Enter number of elements in the array"<<endl;
    cin>>length;
    array=new int [length];
    cout<<"Enter the elements"<<endl;
    for(i=0;i<length;i++)
    {
        cin>>array[i];
    }
}
   
void sort::display()
{
    for(i=0;i<length;++i)
    {
        cout<<array[i]<<"\t";
    }
    cout<<"\n";
}

void sort::quick_sort(int array[],int left_index,int right_index)
{   
    int j;
    if(left_index<right_index)
    {       
        j=partition(array,left_index,right_index);
        ++pass_count;
        cout<<"Pass:" <<pass_count<<"\t";   
        display();
       
        #pragma omp parallel sections
        {       
            #pragma omp section
            {
                thread_id=omp_get_thread_num();
                cout<<"\nLeft side array [";
                for(int t=left_index;t<=j-1;t++)
                    cout<<array[t]<<"\t";
                cout<<"] processed by Thread "<<thread_id<<endl;
                quick_sort(array,left_index ,j-1);
            }           
       
            #pragma omp section
            {
                thread_id=omp_get_thread_num();
                cout<<"\nRight side array [";
                for(int t=j+1;t<=right_index;t++)
                    cout<<array[t]<<"\t";
                cout<<"] processed by Thread "<<thread_id<<"\n\n\n";               
                quick_sort(array,j+1,right_index);
            }
           
        }
    }
}

int sort::partition(int array[],int left_index,int right_index)
{
    int pivot,i,j,temp;
    pivot=array[left_index];
    i=left_index;
    j=right_index+1;
    while(1)
    {
        do
            ++i;
        while(array[i]<pivot && i<=right_index);
        do
            --j;
        while(array[j]>pivot);
        if(i>=j)
            break;
        temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
    temp=array[left_index];
    array[left_index]=array[j];
    array[j]=temp;
    return j;
}

int main()
{
    sort obj;
    obj.input();
    cout<<"\nUnsorted array is:";   
    obj.display();
    cout<<"\n\n";
    obj.quick_sort(obj.array,0,(obj.length-1));
    cout<<"\nSorted array is:";
    obj.display();
}



OUTPUT:

Using Divide and Conquer Strategies design a function for Binary Search using C++/ Java/ Python/ Scala.

Using Divide and Conquer Strategies design a function for Binary Search using C++/ Java/ Python/ Scala.

#include<iostream>
#include<stdio.h>
#include <bits/stdc++.h>

using namespace std;

int binary_search(int array[],int low, int high, int key);    //function declaration

int main()
{
    int low,high,length,i,key;
    cout<<"Enter the length Of array"<<endl;
    cin>>length;
    int array[length+1];
    cout<<"Enter the elements of the array"<<endl;
    for(i=0;i<length;i++)
    {
        cin>>array[i];
    }
    cout<<"Sorting the array as follows:"<<endl;
    sort(array, array+length);          //sorting array using sort function in STL
    for(i=0;i<length;i++)
    {
        cout<<array[i]<<"\t";
    }  
    cout<<"\nEnter the key to be searched"<<endl;
    cin>>key;
    high=length-1;
    low=0;
    int position=binary_search(array,low,high,key);        //function call
    if (position==-1)
    {
        cout<<"Number not found";
    }
    else
        cout<<"Number found at location "<<position+1<<endl;
}

int binary_search(int array[],int low, int high, int key)             
{
    if(low>high)
        return -1;
    else
    {
        int mid=(low+high)/2;            //calculate centre postion in array
        if(array[mid]==key)
        {
            return  mid;
        }
        else if(array[mid]<key)
        {
            low=mid+1;
            return(binary_search(array,low,high,key));   //search in right half of array
        }
        else if(array[mid]>key)
        {
            high=mid-1;
            return(binary_search(array,low,high,key));   //search in left half of array
        }
    }
}



OUTPUT: