compiler lab


COMPILER DESIGN LAB

1. Implement Token Separation for a given expression.
2.a. Use LEX and YACC to implement parser on ambiguous grammar.
2.b. Use LEX and YACC to implement parser on unambiguous grammar using LEX.
3. Use LEX and YACC tool to implement Desktop Calculator. 
4. Implement Operator precedence parsing.
5. Implement Recursive Descent Parser algorithm.
6. Implement Shift Reduce Parser algorithm.
7. Implement the back end of the compiler to produce three address code. 
8. Implement Symbol Table management using LEX and YACC.
9. Construction of NFA from a regular expression. 
10. Construction of DFA from a regular expression.
11. Reserved function expansion/substitution using LEX and YACC.      
12. Loop expansion using  LEX and YACC.














1. Implement Token Separation for a given expression using LEX. 

File.l :
letter [A-Za-z]
digit [0-9]
operator [-+*]
%%
void |
main |
if |   
do |       
printf |    
int |
float |
char |
for                                          {printf("%s is a keyword\n",yytext);}
%s |
%c |
%d |
%f                                           {printf("%s is a Format Specifier\n",yytext);}
({letter}|_)({letter}|{digit})*   {printf("%s is a identifier\n",yytext);} 
{operator}({operator})*        {printf("%s is an operator\n",yytext);}
{digit}+            {printf("%s is a number\n",yytext);}
"("                               {printf("%s is an open parenthesis\n",yytext);}
\)                        {printf("%s is an close parenthesis\n",yytext);}
\;                                 {printf("%s is a semicolon\n",yytext);}
\{
\.
\=
\/
\,
\'
\"                {printf("%s is a double quote\n",yytext);}
.        {printf("\nSyntax Error!!\n");}
%%

int main(intargc, char *argv[])
{
FILE *fp=fopen(argv[1],"r");
printf("\n%s %s %s\n",argv[1],argv[2],argv[3]);
yyin=fp;
yylex();
return 0;
}


Input.c
int x;
charch;
void main()
{
getch();
}

Output :











2.a. Use LEX and YACC to implement parser on ambiguous grammar.

File.l :
%{
#include<stdlib.h>
#include"y.tab.h"
voidyyerror(char *s);
externintyylval;
%}
%%
[0-9]+ {yylval=atoi(yytext); return INT;}
[-+*/\n] {return *yytext;}
"("       {return *yytext;}
\)       {return *yytext;}
[\t];
.       {yyerror("Syntax Error");}
%%
intyywrap()
{
return 1;
}


File.y  :
%{
#include<stdio.h>
externintyylex(void);
voidyyerror(char *);
%}
%token INT
%%
program:
programexpr '\n     { printf("%d\n",$2);}
|
;
expr:
expr '+' expr                         {$$=$1+$3;}
|expr '-' expr           {$$=$1-$3;}
|expr '*' expr                                  {$$=$1*$3;}
|expr '/' expr           {$$=$1/$3;}
|INT               {$$=$1;}
| '(' expr ')'   {$$=$2;}
;
%%

voidyyerror(char *s)
{
printf("%s\n",s);
}

int main()
{
yyparse();
return 0;
}


INPUT:

OUTPUT:













2.b. Use LEX and YACC to implement parser on unambiguous grammar.

File.l :
%{
#include<stdlib.h>
#include"y.tab.h"
voidyyerror(char *s);
externintyylval;
%}
%%
[0-9]+ {yylval=atoi(yytext); return INT;}
[-+*/\n] {return *yytext;}
"("       {return *yytext;}
\)       {return *yytext;}
[\t];
.       {yyerror("Syntax Error");}
%%
intyywrap()
{
return 1;
}


File.y  :
%{
#include<stdio.h>
externintyylex(void);
voidyyerror(char *);
%}
%token INT
%%
program:
programexpr '\n'                { printf("%d\n",$2);}
|
;
expr:
T                                              {$$=$1;}
|expr '+' T                             {$$=$1+$3;}
|expr '-' T                  {$$=$1-$3;}
;
T:
F                                  {$$=$1;}
|T '*' F                                               {$$=$1*$3;}
|T '/' F                        {$$=$1/$3;}
;
F:
INT                              {$$=$1;}
| '(' expr ')'               {$$=$2;}
;
%%

voidyyerror(char *s)
{
printf("%s\n",s);
}

int main()
{
yyparse();
return 0;
}


INPUT:

OUTPUT:







3. Use LEX and YACC tool to implement Desktop Calculator. 

File.l
%{
#include<stdlib.h>
#include"y.tab.h"
voidyyerror(char *s);
externintyylval;
%}
%%
[0-9]+ {yylval=atoi(yytext); return INT;}
[a-z]  {yylval=toascii(*yytext)-97; return ID;}
[A-Z] {yylval=toascii(*yytext)-65; return ID;}
[-+*=/\n] {return *yytext;}
\(   {return *yytext;}
")"       {return *yytext;}
[\t]   ;
.       {yyerror("Invalid Token!!");}
%%
intyywrap()
{
return 1;
}              

File.y
%{
#include<stdio.h>
externintyylex(void);
voidyyerror(char *);
int x=0;
intval[26];
%}
%token INT ID
%%
nithish:
nithishexpr '\n'                    {x=$2; printf("%d\n",$2);}
|nithish ID '=' expr '\n'                  {val[$2]=$4;}
|       
;   

expr:         
expr '+' T                                                                   {$$=$1+$3;}
|expr '-' T                                          {$$=$1-$3;}
|T                                                        {$$=$1;}
|'+' T                                                  {$$=x+$2;}
|'-' T                                                   {$$=x-$2;}
;
T:
F                                              {$$=$1;}
|T '*' F                                                                       {$$=$1*$3;}
|T '/' F                                                {$$=$1/$3;}
|'*' F                                                              {$$=x*$2;}
|'/' F                                                               {$$=x/$2;}
;
F:
INT                                          {$$=$1;}
|ID                                          {$$=val[$1];}
| '(' expr ')'                                       {$$=$2;}
;
%%

voidyyerror(char* s)
{
printf("%s",s);
}

int main()
{
yyparse();
return 0;
}


Input

Output
































4. Implement Operator precedence parsing


#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
charbuf[50],stk[50]="$",choice;
intibuf,istk=0,i,j;
char q[9][9]={
//{'+','-','*','/','^','a','(',')','$'}
  {'>','>','<','<','<','<','<','>','>'},//+
  {'>','>','<','<','<','<','<','>','>'},//-
  {'>','>','>','>','<','<','<','>','>'},//*
  {'>','>','>','>','<','<','<','>','>'},// \
  {'>','>','>','>','<','>','<','>','>'},//^
  {'<','<','<','<','<','E','E','>','>'},// a
  {'<','<','<','<','<','<','<','=','E'},//(
  {'>','>','>','>','>','E','E','>','>'},//)
  {'<','<','<','<','<','<','<','E','A'}, //$
};
char c[9]={'+','-','*','/','^','a','(',')','$'};
intcheckindex(char ch)
{
if(isalpha(ch)) ch='a';
for(i=0;i<9;i++)
if(ch==c[i])                            //   q[*][/]
            returni;                             //     2  3
printf("\nInvalid Token");
getch();
exit(0);
}

main()
{
clrscr();
printf("Enter a string:");
scanf("%s",buf);
printf("\n   + - * / ^ a ( ) $\n");
for(i=0;i<9;i++)
 {
printf("\n%c  ",c[i]);
for(j=0;j<9;j++)
    {
printf(" %c",q[i][j]);
    }
 }
printf("\n\nPARSING TABLE:");
printf("\nSTACK\tBUFFER\tACTION");
strcat(buf,"$");
strrev(buf);
ibuf=strlen(buf)-1;
while(1)
 {
choice=q[checkindex(stk[istk])][checkindex(buf[ibuf])];
printf("\n%s\t %s\t %c\t ",stk,buf,choice);
getch();
switch(choice)
     {                                   
            case '<':                              
            printf(" PUSH");
            istk++; stk[istk]=buf[ibuf];
            stk[istk+1]='\0';            
            buf[ibuf]='\0'; ibuf--;  
            break;
            case '>':
            printf(" POP");
            stk[istk]='\0'; istk--;
            break;
            case '=':
            printf("POP BOTH");
            stk[istk]='\0'; istk--;
            buf[ibuf]='\0'; ibuf--;
            break;
            case 'A':
            printf("  Accepted");
            getch();
            exit(0);
            default:
            printf("  ERROR");
            getch();
            exit(0);
     }
 }
getch();
}


Input:
Output:
















5. Implement Recursive Descent Parser algorithm.

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

inti=0 ,f=0;
charstr[30];

void E();
voidEprime();
void T();
voidTprime();
void F();

void E()
{
printf("\nE->TE'");
T();
Eprime();
}

voidEprime()
{
if(str[i]=='+')
                        {
                        printf("\n\E'->+TE'");
                        i++;
                        T();
                        Eprime();
                        }
            else if(str[i]==')')
                        printf("\nE'->^");
}

void T()
{
printf("\nT->FT'");
F();
Tprime();
}

voidTprime()
{
            if(str[i]=='*')
                        {
                        printf("\nT'->*FT'");
                       

i++;
                        F();
                        Tprime();
                        }

            else if((str[i]==')')||(str[i]=='+'))
                        printf("\nT'->^");
}

void F()
{
            if(str[i]=='a')
                        {
                        printf("\nF->a");
                        i++;
                        }

            else if(str[i]=='(')
                        {
                        printf("\nF->(E)");
                        i++;
                        E();
                        if(str[i]==')')
                                    i++;
                        }
            else
                        f=1;
}

void main()
{
intlen;
clrscr();
printf("Enter the string: ");
scanf("%s",str);
len=strlen(str);
str[len]='$';
E();
if((str[i]=='$')&&(f==0))
printf("\nStringsucessfully parsed!");
else
printf("\nSyntax Error!");
getch();
}




Output 1
Enter the string: a+a*a$
E->TE'
T->FT'
F->a
T'->^
E'->+TE'
T->FT'
F->a
T'->*FT'
F->a
String sucessfully parsed!













6. Implement Shift Reduce Parser algorithm. 
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>

int main()
            {
            char str[10],stk[10],a[10],b[10];
            int i,j,k,len,s;
            for(s=0;s<10;s++)
                        {
                        stk[s]=NULL;
                        str[s]=NULL;
                        }
            printf("Enter an artihmetic exprssion: ");
            scanf("%s",&str);
            len=strlen(str);
            str[len]='$';
            stk[0]='$';
            j=1;

            printf("Stack\t\t|\tAction\t\t\t|\tInput\n");
            printf("\n%s\t\t|\t\t\t\t|\t%s\n",stk,str);
            for(i=0;i<=len;i++)
                        {
                        if(islower(str[i]))
                          {
                          stk[j]=str[i];
                          str[i]=NULL;
                          printf("%s\t\t|\tShift a\t\t\t|\t",stk);
                          /* Printing input sring */
                                      for(k=0;k<=len;k++)
                              {
                              printf("%c",str[k]);
                              }
                          printf("\n");
                          }

                        if(islower(stk[j]))
                          {
                          stk[j]='E';
                          printf("%s\t\t|\tReduce (E->a)\t\t|\t",stk);
                          /* Printing input sring */
                          for(k=0;k<=len;k++)
                              {
                              printf("%c",str[k]);
                              }
                          printf("\n");

                        if(str[i+1]!='$')
                                    j=j+1;
                          }

                        if(str[i]=='+')
                          {
                          str[i]=NULL;
                          stk[j]='+';
                          printf("%s\t\t|\tShift +\t\t\t|\t",stk);
                          /* Printing input sring */
                          for(k=0;k<=len;k++)
                              {
                              printf("%c",str[k]);
                              }
                          printf("\n");
                          j=j+1;
                          }

                        if(str[i]=='*')
                          {
                          str[i]=NULL;
                          stk[j]='*';
                          printf("%s\t\t|\tShift *\t\t\t|\t",stk);
                          /* Printing input sring */
                          for(k=0;k<=len;k++)
                              {

      printf("%c",str[k]);
                              }
                          printf("\n");
                          j=j+1;
                          }

                        if(stk[j]=='E'&& stk[j-1]=='+'&& stk[j-2]=='E' && stk[j+1]!='*')
                          {
                          stk[j-1]=NULL;
                          stk[j]=NULL;
                          printf("%s\t\t|\tReduce (E->E+E)\t\t|\t",stk);
                          /* Printing input sring */
                          for(k=0;k<=len;k++)
                              {
                              printf("%c",str[k]);
                              }
                          printf("\n");
                          j=j-2;
                          }

                        if(stk[j]=='E'&&stk[j-1]=='*'&&stk[j-2]=='E')
                          {
                          stk[j-1] =NULL;
                          stk[j]=NULL;
                          printf("%s\t\t|\tReduce (E->E*E)\t\t|\t",stk);
                          /* Printing input sring */
                          for(k=0;k<=len;k++)
                              {
                              printf("%c",str[k]);
                              }
                          printf("\n");
                          j=j-2;
                          }
            }

            printf("\n\n");

            if(stk[j]=='E' && stk[j-1]=='$' && str[i-1]=='$')
                        printf("Parsing successfull!!\n");
            else
                        printf("Syntax error!! \n");

            return 0;
            }

Input:
Output:
























7. Implement the back end of the compiler to produce three address code. 
#include<conio.h>
#include<stdio.h>
int ptr=3,t=1,mov;
char * process(char str[25])             
{
char temp[25];
if(strlen(str)>ptr)                      
 {
            strcpy(temp,str);
            temp[ptr]='\0';
            if(ptr==3)
                        printf("\nt%d:=%s",t++,temp);
            else
                        printf("\nt%d:=t%d%s",t++,t-1,temp);
            mov=ptr;
            ptr=2;
            str=process(&str[mov]);
 }
            returnstr;
}
main()
{
char *ret,sub[4][15],str[25],temp[25];
clrscr();
printf("Enter the statement: ");
gets(str);
strcpy(temp,str);
sscanf(str,"%s",sub[0]);
if(str[1]=='=')
 {
            if(strlen(str)<=5)
            printf("\n%s",str);
            else
            {
                        ret=process(&str[2]);
                        printf("\n%c:%ct%d%s",str[0],str[1],t-1,ret);
            }
 }
else
 {
            sscanf(str,"%s %s %s %s",sub[0],sub[1],sub[2],sub[3]);
            if(strcmp(sub[0],"if")==0)
             {
            ret=process(sub[1]);
            printf("\n%st%d%s %s %s",sub[0],t-1,ret,sub[2],sub[3]);
             }
            else if(strcmp(sub[0],"goto")==0)
             {
            printf("\n%s",str);
             }
            else
             {
                        ret=process(str);
                        printf("\nt%d=t%d%s",t,t-1,ret);
             }
 }
getch();
}


Input:

Output:










8. Implement Symbol Table management

%{
#include<stdio.h>
#include<string.h>
char prev[10];
struct symtab
{
                        char name[20];
                        unsigned int addr;
                        char type[10];
                        char att[20];
}sym[20];
int scount=0;
int flag=0;
unsigned int fmem=5050;
%}

letter [A-Za-z]
digit [0-9]
sym [#,<>.{}]

%%
void |
int |
float |
char |
double |
long {flag=1; strcpy(prev,yytext);}

{sym} |
if |
for |
main { flag=0; }

(_|{letter}).({letter}|{digit})* {
        if(flag==1)
        {
                yytext[strlen(yytext)-1]='\0';
                strcpy(sym[scount].name,yytext);
                strcpy(sym[scount].type,"var");
                strcpy(sym[scount].att,prev);
                fmem+=20;
                sym[scount++].addr=fmem;
        }
        flag=0;
        }

(_|{letter}).({letter}|{digit})*."(" {
        if(flag==1)
        {
                yytext[strlen(yytext)-1]='\0';
                strcpy(sym[scount].name,yytext);
                strcpy(sym[scount].type,"proc");
                strcpy(sym[scount].att,prev);
                fmem+=2;
                sym[scount++].addr=fmem;
        }
        flag=0;
        }

%%
int main()
{
        FILE *fp=fopen("input.c","r");
        int i=0;
        yyin=fp;
        yylex();
        printf("\n------------------------------------");
        printf("\n\tSYMBOL TABLE");
        printf("\n------------------------------------");
        printf("\nNAME\t|TYPE\t|ATTR\t|ADDR");
        printf("\n------------------------------------\n");
        for(i=0;i<scount;i++)
            printf("%s\t|%s\t|%s\t|%u\n",sym[i].name, sym[i].type,sym[i].att,sym[i].addr);
        printf("\n------------------------------------");
        return 0;
}

Input: (input.c)
#include<conio.h>
#include<stdio.h>
int fun1();
float fun2();
void main()
{
  int x;
  float a;
  if();
  main();
}

OUTPUT:

------------------------------------------
        SYMBOL TABLE
------------------------------------------
NAME    |TYPE   |ATTR   |ADDR
------------------------------------------
fun1               |proc             |int                |5052
fun2               |proc             |float             |5054
main               |proc             |void              |5056
x                      |var                |int                |5076
a                      |var                |float             |5096
------------------------------------------


Comments

Post a Comment

Popular posts from this blog

lab record

EX.NO.1      STUDY OF LEX TOOL AIM : To study about lexical analyser generator [LEX TOOL]. 1.Introduction: The unix utility lex parses a file of characters. It uses regular expression matching; typically it is used to ‘tokenize’ the contents of the file. In that context, it is often used together with the yacc utility. 2 Structure of a lex file A lex file looks like ...definitions... %% ...rules... %% ...code... Here is a simple example: %{ int charcount=0,linecount=0; %} %% . charcount++; \n {linecount++; charcount++;} %% int main() { yylex(); printf("There were %d characters in %d lines\n", charcount,linecount); return 0; } 2.1 Block Diagram : LEX COMPILER   LEX PGM----- à                                              ----- à LEX .YY.C                                                                         GCC   LEX.YY.C
Read more