CD LAB PROGRAMS

Implementation of Predictive Parser.

#include<stdio.h> #include<ctype.h> #include<string.h> #include<stdlib.h> #define SIZE 128 #define NONE -1 #define EOS '\0' #define NUM 257 #define KEYWORD 258 #define ID 259 #define DONE 260 #define MAX 999 char lexemes[MAX]; char buffer[SIZE]; int lastchar=-1; int lastentry=0; int tokenval=DONE; int lineno=1; int lookahead; 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,"ret urn",KEYWORD,0,0}; void Error_Message(char *m) { fprintf(stderr,"line %d, %s \n",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(char s[ ],int tok) { int len;

len=strlen(s); if(lastentry+1>=MAX) Error_Message("Symbpl table is full"); if(lastchar+len+1>=MAX) Error_Message("Lexemes array is full"); lastentry=lastentry+1; symtable[lastentry].token=tok; symtable[lastentry].lexptr=&lexemes[lastchar+1]; lastchar=lastchar+len+1; strcpy(symtable[lastentry].lexptr,s); return lastentry; }/*void Initialize() { struct entry *ptr; for(ptr=keywords;ptr->token;ptr+1) 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=lineno+1; 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=i+1; 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 Match(int t) { if(lookahead==t) lookahead=lexer(); else Error_Message("Syntax error"); } void display(int t,int tval) { if(t=='+'||t=='-'||t=='*'||t=='/') printf("\nArithmetic Operator: %c",t); else if(t==NUM) printf("\n Number: %d",tval); else if(t==ID) printf("\n Identifier: %s",symtable[tval].lexptr); else printf("\n Token %d tokenval %d",t,tokenval); } void F() { //void E(); switch(lookahead) { case '(' : Match('('); E(); Match(')'); break; case NUM : display(NUM,tokenval); Match(NUM); break; case ID : display(ID,tokenval);

Match(ID); break; default : Error_Message("Syntax error"); } } void T() { int t; F(); while(1) { switch(lookahead) { case '*' : t=lookahead; Match(lookahead); F(); display(t,NONE); continue; case '/' : t=lookahead; Match(lookahead); display(t,NONE); continue; default : return; } } } void E() { int t; T(); while(1) { switch(lookahead) { case '+' : t=lookahead; Match(lookahead); T(); display(t,NONE); continue; case '-' : t=lookahead; Match(lookahead); T(); display(t,NONE); continue; default : return; }

} } void parser() { lookahead=lexer(); while(lookahead!=DONE) { E(); Match(';'); } } main() { char ans[10]; printf("\n Program for recursive decent parsing "); printf("\n Enter the expression "); printf("And place ; at the end\n"); printf("Press Ctrl-Z to terminate\n"); parser(); }

A Program to Generate Machine Code.

#include<stdio.h> #include<stdlib.h> #include<string.h> int label[20]; int no=0; int main() { FILE *fp1,*fp2; char fname[10],op[10],ch; char operand1[8],operand2[8],result[8]; int i=0,j=0; printf("\n Enter filename of the intermediate code"); scanf("%s",&fname); fp1=fopen(fname,"r"); fp2=fopen("target.txt","w"); if(fp1==NULL || fp2==NULL) { printf("\n Error opening the file"); exit(0); } while(!feof(fp1)) { fprintf(fp2,"\n"); fscanf(fp1,"%s",op); i++; if(check_label(i)) fprintf(fp2,"\nlabel#%d",i); if(strcmp(op,"print")==0) { fscanf(fp1,"%s",result); fprintf(fp2,"\n\t OUT %s",result); } if(strcmp(op,"goto")==0) { fscanf(fp1,"%s %s",operand1,operand2); fprintf(fp2,"\n\t JMP %s,label#%s",operand1,operand2); label[no++]=atoi(operand2); } if(strcmp(op,"[]=")==0) { fscanf(fp1,"%s %s %s",operand1,operand2,result);

fprintf(fp2,"\n\t STORE %s[%s],%s",operand1,operand2,result); } if(strcmp(op,"uminus")==0) { fscanf(fp1,"%s %s",operand1,result); fprintf(fp2,"\n\t LOAD -%s,R1",operand1); fprintf(fp2,"\n\t STORE R1,%s",result); } switch(op[0]) { case '*': fscanf(fp1,"%s %s %s",operand1,operand2,result); fprintf(fp2,"\n \t LOAD",operand1); fprintf(fp2,"\n \t LOAD %s,R1",operand2); fprintf(fp2,"\n \t MUL R1,R0"); fprintf(fp2,"\n \t STORE R0,%s",result); break; case '+': fscanf(fp1,"%s %s %s",operand1,operand2,result); fprintf(fp2,"\n \t LOAD %s,R0",operand1); fprintf(fp2,"\n \t LOAD %s,R1",operand2); fprintf(fp2,"\n \t ADD R1,R0"); fprintf(fp2,"\n \t STORE R0,%s",result); break; case '-': fscanf(fp1,"%s %s %s",operand1,operand2,result); fprintf(fp2,"\n \t LOAD %s,R0",operand1); fprintf(fp2,"\n \t LOAD %s,R1",operand2); fprintf(fp2,"\n \t SUB R1,R0"); fprintf(fp2,"\n \t STORE R0,%s",result); break; case '/': fscanf(fp1,"%s %s %s",operand1,operand2,result); fprintf(fp2,"\n \t LOAD %s,R0",operand1); fprintf(fp2,"\n \t LOAD %s,R1",operand2); fprintf(fp2,"\n \t DIV R1,R0"); fprintf(fp2,"\n \t STORE R0,%s",result); break; case '%': fscanf(fp1,"%s %s %s",operand1,operand2,result); fprintf(fp2,"\n \t LOAD %s,R0",operand1); fprintf(fp2,"\n \t LOAD %s,R1",operand2); fprintf(fp2,"\n \t DIV R1,R0"); fprintf(fp2,"\n \t STORE R0,%s",result); break; case '=': fscanf(fp1,"%s %s",operand1,result); fprintf(fp2,"\n\t STORE %s %s",operand1,result); break; case '>': j++; fscanf(fp1,"%s %s %s",operand1,operand2,result); fprintf(fp2,"\n \t LOAD %s,R0",operand1);

fprintf(fp2,"\n\t JGT %s,label#%s",operand2,result); label[no++]=atoi(result); break; case '<': fscanf(fp1,"%s %s %s",operand1,operand2,result); fprintf(fp2,"\n \t LOAD %s,R0",operand1); fprintf(fp2,"\n\t JLT %s,label#%d",operand2,result); label[no++]=atoi(result); break; } } fclose(fp2); fclose(fp1); fp2=fopen("target.txt","r"); if(fp2==NULL) { printf("Error opening the file\n"); exit(0); } do { ch=fgetc(fp2); printf("%c",ch); }while(ch!=EOF); fclose(fp1); return 0; }int check_label(int k) { int i; for(i=0;i<no;i++) { if(k==label[i]) return 1; } return 0; }

Input:
$vi int.txt =t1 2

[]=a 0 1 []=a 1 2 []=a 2 3 *t1 6 t2

+a[2] t2 t3 /t3 t2 t2 uminus t2 t2 print t2

goto t2 t3 =t3 99 uminus 25 t2 *t2 t3 t3 uminus t1 t1 +t1 t3 t4 print t4

Output:
Enter filename of the intermediate code: int.txt STORE t1,2 STORE a[0],1 STORE a[1],2 STORE a[2],3 LOAD t1,R0 LOAD 6,R1 ADD R1,R0 STORE R0,t3 LOAD a[2],R0 LOAD t2,R1 ADD R1,R0 STORE R0,t3 LOAD a[t2],R0 LOAD t1,R1 SUB R1,R0 STORE R0,t2 LOAD t3,R0 LOAD t2,R1 DIV R1,R0 STORE R0,t2 LOAD t2,R1 STORE R1,t2 LOAD t2,R0 JGT 5,label#11 Label#11: OUT t2 JMP t2,label#13 Label#13: STORE t3,99 LOAD 25,R1 STORE R1,t2 LOAD t2,R0 LOAD t3,R1 MUL R1,R0 STORE R0,t3 LOAD t1,R1 STORE R1,t1 LOAD t1,R0 LOAD t3,R1

ADD R1,R0 STORE R0,t4 OUT t4

Design LALR Bottom up Parser . <parser.l>

%{ #include<stdio.h> #include "y.tab.h" %} %% [0-9]+ {yylval.dval=atof(yytext); return DIGIT; } \n|. return yytext[0]; %%

<parser.y>
%{ /*This YACC specification file generates the LALR parser for the program considered in experiment 4.*/ #include<stdio.h> %} %union { double dval; } %token <dval> DIGIT %type <dval> expr %type <dval> term %type <dval> factor %% line: expr '\n' { printf("%g\n",$1); } ; expr: expr '+' term {$$=$1 + $3 ;} | term ; term: term '*' factor {$$=$1 * $3 ;} | factor ; factor: '(' expr ')' {$$=$2 ;} | DIGIT

; %% int main() { yyparse(); } yyerror(char *s) { printf("%s",s); }

Output:
$lex parser.l $yacc d parser.y $cc lex.yy.c y.tab.c ll lm $./a.out 2+3 5.0000

Shift reduce parser:

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