1.

Develop a lexical analyzer to recognize a few patterns.

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

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

Page 2

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;

Page 3

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)

Page 4

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();

Page 5

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)

Page 6

printf(\n Relataional Operator); lookahead=lexer(); } }

Page 7

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

Page 8

Assigment Operator Identifier: a Operator Identifier: b

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;

Page 9

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

3. Develop LL(1) Parser( construct parse table also).

#include <iostream.h> #include <conio.h> #include <string.h> #include <stdio.h> void main() { clrscr(); char #include <stdlib.h>

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; 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>","+","*",";",

Page 10

"E", "Te","Error","Error","Error", "e", "Error","+Te","Error","\0", "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<<endl; cout<<array[i][j]; "T", "Vt","Error","Error","Error",

cout << endl; gets(str);

cout << "\n\tENTER THE STRING :"; 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();
Page 11

exit(1); } temp[k]=str[i]; temp[k+1]='\0'; again1: { f1=0; 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++; } { if((m+1)<strlen(str1)) { m++; temp1[o]=str1[m]; o++; } else
Page 12

o1++; 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); 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); cout << "\n\t" <<str1;

strcpy(temp1,'\0'); strcpy(temp2,'\0'); strcpy(t,'\0'); goto again1; } { cout << "\n\tERROR IN YOUR SOURCE STRING";
Page 13

if(strcmp(array[n][l],"Error")==0)

getch(); } exit(1);

strcpy(tt,'\0'); strcpy(tt,array[n][l]); strcpy(t3,'\0'); f=0; { t3[c]=tt[c]; t3[c+1]='\0'; if(strcmp(t3,temp)==0) { f=0; break; } else } f=1;

for(c=0;c<strlen(tt);c++)

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'); goto again1; } }

Page 14

strcpy(t,'\0');

} i++; } if(f1==0) else cout << "\nENTERED STRING IS INVALID"; k++;

cout << "\n\n\tENTERED STRING IS VALID";

getch(); }

OUTPUT
LL(1) PARSER TABLE

Page 15

NT E e t T V

<id> Error Vt Error <id> Te Error Error +Te

* Error Error *Vt Error Error

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

Page 16

4. Develop Operator Precedence Parser( construct parse table also).

#include<iostream.h> #include<ctype.h> char ptab[6][6] = { 'x', '+', '*', '(', ')', ']', '+', '>', '<', '<', '>', '>', '*', '>', '>', '<', '>', '>', '(', '<', '<', '<', '=', '#', '[', '<', '<', '<', '#', '=' ')', '>', '>', '#', '>', '>', }; struct node { char symbol; node *lptr; }; struct stack { char sign; struct node *optr; }; char comp(char,char); void postorder(struct node *); void preorder(struct node *); void inorder(struct node *); node *rptr;

Page 17

void main() { int i=0,tos=0,csf=1; char str[15]="[a*b+c]"; char ans; node *x; stack s[20]; s[tos].sign ='['; while(str[i]!='\0') { if(isalpha(str[csf])) { x=new node; x->symbol=str[csf]; x->lptr=NULL; s[tos].optr=x; } else { ans=comp(s[tos].sign,str[csf]); while(ans=='>') { x=new node; x->symbol=s[tos].sign; x->lptr=s[tos-1].optr; x->rptr=s[tos].optr; tos--; s[tos].optr= x; } { ans=comp(s[tos].sign,str[csf]); if(ans=='<') tos++; s[tos].sign=str[csf]; }
Page 18

x->rptr=NULL;

if(ans=='=' && s[tos].sign=='[') { } if(s[tos].sign=='(') { x=s[tos].optr; tos--; s[tos].optr=x; } } csf++; } i++; node *rt=s[0].optr; cout<<endl<<"The Postorder of the tree is::"; postorder(rt); cout<<endl<<"The Preorder of the tree is::"; cout<<endl<<"The Inorder of the tree is::"; cout<<endl; } char comp(char x,char y) { int i=0,j=0; while(ptab[i][0]!=x && i<=6) i++; while(ptab[0][j]!=y && j<=6) j++; return ptab[i][j]; } { struct node *ptr=rt; if(ptr!=NULL) { postorder(ptr->lptr);
Page 19

break;

preorder(rt); inorder(rt);

void postorder(struct node *rt)

postorder(ptr->rptr); } } void preorder(struct node *rt) { struct node *ptr=rt; cout<<ptr->symbol;

if (ptr!=NULL) {

cout<<ptr->symbol; preorder(ptr->lptr); } preorder(ptr->rptr); } { .

void inorder(struct node *rt) struct node *ptr=rt; if(ptr!=NULL) { inorder(ptr->lptr); cout<<ptr->symbol; inorder(ptr->rptr); } }

Page 20

OUTPUT
The Postorder of the tree is:: ab*c+ The Preorder of the tree is :: +*abc The Inorder of the tree is :: a*b+c

Page 21

5. Develop a Recursive Decent Parser.

#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;
Page 22

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,"return",KEYWORD, 0,0}; void errormsg(char *m) { fprintf(stderr,"line %d:%s\n",lineno,m); exit(1); } int lookup(char s[]) { int k; for(k=lastentry;k>0;k=k-1) if(strcmp(symtable[k].lexptr,s)==0) return k; return 0;
Page 23

} int insert(char s[],int tok) { int len; len=strlen(s); if(lastentry+1>=MAX) errormsg("symtable is full"); if(lastentry+len+1>=MAX) errormsg("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 initialise() { struct entry *ptr; for(ptr=keywords;ptr->token;ptr++) insert(ptr->lexptr,ptr->token); }
Page 24

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;
Page 25

if(i>=SIZE) errormsg("compile error"); } buffer[i]=EOS; if(t!=EOF) ungetc(t,stdin); val=lookup(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) {
Page 26

if(lookahead==t) lookahead=lexer(); else errormsg("syntax error"); } void display(int t,int tval) { if(t=='+'||t=='-'||t=='*'||t=='/') printf("\n arithmetic 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('(');
Page 27

E(); match(')'); break; case NUM: display(NUM,tokenval); match(NUM); break; case ID: display(ID,tokenval); match(ID); break; default: errormsg("syntax error"); } } void T() { int t; F(); while(1) { switch(lookahead) { case '*':
Page 28

t=lookahead; match(lookahead); F(); display(t,NONE); continue; case '/': t=lookahead; match(lookahead); F(); display(t,NONE); continue; default: return; } } } void E() { int t; T(); while(1) { switch(lookahead) { case '+':
Page 29

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();
Page 30

match(';'); } } int main() { char ans; clrscr(); printf("\n \t \t Program for recursive decent parsing"); initialise(); printf("enter the expression & place;at the end \n Press CTRL + Z to terminate"); parser(); return 0; }

Page 31

OUTPUT
Program for recursive decent parsing Enter the expression & place ; at the end Press CTRL + Z to terminate 2+3*4; number 2 number 3 number 4 arithmetic operator * arithmetic operator +

a-b; identifier a

Page 32

identifier b arithmetic operator

6. Write a program for generating for various intermediate code forms: Three address code Polish Notation
Three address code
%{

Page 33

#includey.tab.h extern char yyval; %} NUMBER [0-9]+ LETTER [a-zA-Z]+ %% {NUMBER} {yylval.sym=(char)yytext[0];return NUMBER;} {LETTER} {yylval.sym=(char)yytext[0];return LETTER;} \n {return 0;} {return yytext[0];} %% /* %{ #include #include int nIndex=0; struct InterCode { char operand1; char operand2; char opera; };
Page 34

Program name: intcode.y

*/

%} %union { char sym; } %token LETTER NUMBER %type expr %left - + %right * / %% statement: LETTER = expr ; {AddToTable((char)$1.(char)$3,=);} | expr ; ;

expr :expr + expr {$$ = AddToTable((char)$1.(char)$3,+);} |expr - expr {$$ = AddToTable((char)$1.(char)$3,-);} |expr * expr {$$ = AddToTable((char)$1.(char)$3,*);} |expr / expr {$$ = AddToTable((char)$1.(char)$3,/);} |(expr) {$$=(char)$2;) | NUMBER {$$=(char)$1;} | LETTER {$$=(char)$1;} ; %%
Page 35

yyerror(char *s) { printf(%s,s); exit(0); } struct InterCode Code[20]; char AddToTable(char operand1,char operand2,char opera) { char temp = A; Code[nIndex].operand1=operand1; Code[nIndex].operand2=operand2; Code[nIndex].opera=opera; nIndex++; temp++; return temp; } ThreeAddressCode() { int nCnt=0; char temp =A; printf(\n\n\t THREE ADDRESS CODE\n\n); temp++;
Page 36

while(nCnt<nindex)</nindex) { printf(%c : =\t,temp); if(isAlpha(Code[nCnt]].operand1)) printf(%c\t,Code[nCnt].operand1); else printf(%c\t,temp); printf(%c\t,Code[nCnt].opera); if(isAlpha(Code[nCnt]].operand2)) printf(%c\t,Code[nCnt].operand2); else printf(%c\t,temp); printf(\n); nCnt++; temp++; } } main() {

printf(\nEnter The Expression); yyparse();

Page 37

ThreeAddressCode(); } yywrap() { return 1; }

OUTPUT
Enter The Expression: a=b+c*d/e; THREE ADDRESS CODE B:= d C:= c / * e B B B

D:= b + E:= a =

Enter The Expression: a=(b)+(c*d)/e THREE ADDRESS CODE B:= c * d e B B

C:= B / D:= b + E:= a =

Page 38

Polish Notation

struct stack {char s[30]; int top; }st; void main() { char input[30]; void input_to_code(char infix[30]); clrscr(); printf("\n Enter an input in the form of expression "); scanf("%s",input); input_to_code(input); getch();

Page 39

} void input_to_code(char input[30]) { st.top=-1; st.s[st.top]='$'; char polish[30]; int i,j; char ch; int instack(char ch); int incoming(char ch); void push(char item); char pop(); j=0; strrev(input); for(i=0;input[i]!='\0';i++) { ch =input[i]; while(instack(st.s[st.top])>incoming(sh)) { polish[j]=pop(); j++; } if(instack(st.s[st.top])!=incoming(ch)) push(ch); else pop(); } while((ch=pop()!='$') { polish[j]=ch; j++; }

Page 40

polish[j]='\0;; strrev(polish); printf("\n The Polish Notation is %s",polish); } int instack(char ch) { int priority; switch(ch) { case ')':priority=0; break; case '+': case '-':priority=1; break; case '*'; case '/':priority=3; break case '^':priority=6; break; case '$':priority=-1; break; default:priority=8;//when it is operand break; } return priority; } int incoming(char ch) { int priority; switch(ch) { case '+': case '-':priority=2;
Page 41

break; case '*'; case '/':priority=4; break case '^':priority=5; break; case '(':priority=0; break; case ')':priority=9; break; default:priority=7;//when it is operand } return priority; } void push(char item) { st.top++; st.s[st.top]=item; } char pop() { char e; e=st.s[st.top]; st.top--; return e; }

Page 42

OUTPUT
Enter an input in the form of expression (a+b)*(c-d) The polish notation is *+ab-cd

Page 43

7.Write a program to Simulate Heap storage allocation strategy.

#include"stdio.h" #include"conio.h" #include"stdlib.h" #define TRUE 1 #include FALSE 0 typedef struct Heap { int data;

Page 44

struct Heap *next; }node; node *create(); void main() { /*local declarations*/ int choice,val; char ans; node *head; void display(node *); node *search(node *,int); node *insert(node *); void dele(node **); head=NULL; do { clrscr(); printf(\n Program 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 (\n Enter Your Choice(1-5)); scanf(%d,&choice); switch(choice) { case 1:head=create(); break; case 2:display(head); break;

Page 45

case 3:head=insert(head); break; case 4:dele(&head); break; case 5:exit(0); default:clrscr(); printf(Invalid Choice,Try again); getch(); } }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); /*allocate new node*/ new =get_node(); if(new==NULL) printf(\n Memory is not allocated); new-> data=val; if (flag==TRUE)/* Executed only for the first time*/ { head=new; temp=head; /*head is the first node in the heap*/ flag=FALSE;
Page 46

} else { temp->next=new; temp=new; } printf(\nDo you want to enter more elements?(y/n)); ans=getch(); }while(ans= = y); printf(\nThe list is created); getch(); clrscr(); return head; } node *get_node() { node *temp; temp=(node*)malloc(sizeof(node)); //using the mem. Allocation function temp->next=NULL; return temp; } void display(node*head) { node *temp; temp=head; if(temp= =NULL) { printf(\n The list is empty\n); getch(); clrscr(); return; }
Page 47

while(temp!= NULL) { printf(%d->,temp-> data); temp=temp->next; } print(NULL); getch(); clrscr(); } node *search(node *head,int key) { node*temp; int found; temp=head; if (temp= =Null) { printf(The linked list is empty\n); getch(); clrscr(); return NULL; } found=FALSE; While(temp!= NULL && found= =FALSE) { if(temp->data != key) temp = temp->next; else found = True; } if(found == TRUE) { printf(\n The Elements is present in the list\n); getch();
Page 48

return temp; } else printf(\n The Element is not present in the list\n); getch(); 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(\n1.Insert a node as a last node); printf(\n1.Insert a node as at the intermediate position in the list ); printf(\n1.Enter your choice for insertion of node ); scanf(%d,&choice); switch(choice) { case 1:head = insert_head(head); break; case2:insert_last(head); break; case2:insert_after (head); break; } return head; } /*Insertion of node at first position*/ node *insert_head(node*head) { node *New,*temp;
Page 49

New = get_node(); printf (\n Enter 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; } /*Insertion of node at last position*/ void insert_last(node *head) { node *New,*temp; New = get_node(); printf (\n Enter 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; }

Page 50

} /*Insertion of node at intermediate position*/ void insert_after(node *head) { int key; node *New,*temp; New = get_node(); printf(Enter the element after which you want to insert ); scanf(%d,&key); temp=head; do { if(temp->data==key) { printf (Enter element which you want to insert ); scanf(%d,&New->data); 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;
Page 51

while(temp!=NULL && !flag) { if(temp->data!=val) { prev = temp; temp = temp->next; } else flag = TRUE; } if(flag) /*if Flag is true*/ return prev; else return NULL; } void dele(node **head) { int key; node *New,*temp; temp=*head; if (temp== NULL) { printf (\n The list is empty\n ); getch(); clrscr(); return; } clrscr(); printf("\nENTER the Element you want to delete:"); scanf("%d".&key); temp= search(*head,key); if(temp !=NULL) {
Page 52

prev = get_prev(*head,key); if(prev != NULL) { prev ->next = temp-> next; free(temp); } else { *head = temp->next; free(temp); // using the mem. Dellocation function } printf(\nThe Element is deleted\n); getch(); clrscr(); } }

OUTPUT
Program to perform various operations on heap using Dynamic memory management.

Page 53

1. Create 2. Display 3. Insert an element in a list 4. Delete an element from list 5. Quit Enter your choice(1-5) 1 Enter the element: 10 Do you want to enter more elements? (y/n) y Enter the element:20 Do you want to enter more elements?(y/n)y Enter the element:30 Do you want to enter more elements?(y/n)n The List is created Program to perform various operations on Heap using Dynamic memory management. 1. Create 2. Display 3. Insert an element in a list 4. Delete an element from list 5. Quit Enter your choice(1-5) 4 Enter the element you want to delete: 20 The element is present in the list The element is deleted Program to perform various operations on Heap using Dynamic memory management. 1. Create 2. Display 3. Insert an element in a list 4. Delete an element from list 5. Quit Enter your choice(1-5) 2 10-> 30-> NULL

Page 54

8. Generate Lexical analyzer using LEX.

letter [a-zA-Z] digit[0-9] %% {digit}+("E"("+"|"-")?{digit}+)? printf("\n%s\tis real number",yytext); {digit}+"."{digit}+("E"("+"|"-")?{digit}+)? printf("\n%s\t is floating pt no ",yytext); float" printf("\n%s\t is keywords",yytext); "\a"|"\\n"|"\\b"|"\t"|"\\t"|"\b"|"\\a" printf("\n%s\tis Escape sequences",yytext); {letter}({letter}|{digit})* printf("\n%s\tis identifier",yytext); "&&"|"<"|">"|"<="|">="|"="|"+"|"-"|"?"|"*"|"/"|"%"|"&"|"||" printf("\n%s\toperator ",yytext); "{"|"}"|"["|"]"|"("|")"|"#"|"'"|"."|"\""|"\\"|";"|"," printf("\n%s\t is a special character",yytext); "%d"|"%s"|"%c"|"%f"|"%e" printf("\n%s\tis a format specifier",yytext); %% { return 1; } { int main(int argc,char *argv[]) yyin=fopen(argv[1],"r"); yylex(); fclose(yyin); return 0; } /*INPUT PROGRAM int yywrap() "if"|"else"|"int"|"char"|"scanf"|"printf"|"switch"|"return"|"struct"|"do"|"while"|"void"|"for"|"

Page 55

#include<stdio.h> void main() { } /* printf("\nhai\n");

OUTPUT

# is a special character include is identifier < operator stdio is identifier . is a special character h is identifier > operator void is keywords main is identifier ( is a special character ) is a special character printf is keywords { is a special character ( is a special character " is a special character
Page 56

\n is Escape sequences hai is identifier \n is Escape sequences " is a special character ) is a special character ; is a special character

} is a special character

Page 57

9. Generate YACC specification for a few syntactic categories.

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; } Program Name : arith_id.y %{ #include /* This YYAC program is for recognizing the Expression */ %} %%

Page 58

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) { }

Page 59

Page 60

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

Page 61

10. Given any intermediate code form implement code optimization techniques.
#include"stdio.h" #include"string.h" #include"conio.h" #include"stdlib.h" #include"ctype.h" struct ConstFold { char new_Str[10]; char str[10]; }Opt_Data[20]; void ReadInput(char Buffer[],FILE *Out_file); int Gen_token(char str[],char Tokens[][10]); int New_Index=0; int main() { file *In_file,*Out_file; char Buffer[100],ch; int i=0; In_file = fopen(d:\\code.txt,r); Out_file = fopen(d:\\output.txt,w); clrscr(); while(1) {

Page 62

Ch = fgetc(In_file); i=0; while(1) { If(ch == \n) break; Buffer[i++]=ch; ch = fgetc(_file); if(ch == EOF) break; }//End while if(ch ==EOF) break; Buffer[i]=\0; ReadInput(Bufer, Out_file);//writing to the output file }//End while return 0; }//End main void ReadInput(char Buffer[],FILE *Out_file) { char temp[100],Token[10][10]; int n,I,j,flag=0; strcpy(temp,Buffer); n= Gen_token(temp,Token); for(i=0;i { if(!strcmp(Token[i],=)) { if(isdigit(Token[i+1][0])||Token[i+1][0] == .) { /*If yes then saving that number and its variable In the Opt_Data array*/ flag=1;
Page 63

strcpy(Opt_Data[New_Index].New_Str,Token[i-1]); strcpy(Opt_Data[New_Index++].str,Token[i+1]); }//End if }//End if }//End for if(!flag) { for(i=0;i { for(j=0;j { if(!strcmp(Opt_Data[i].new_Str,Token[j])) strcpy(Token[j],Opt_Data[i].str); }//End for }//End for }//End if fflush(Out_file); strcpy(temp,); for(i=0;i { strcat(tem,Token[i]); if(Token[i+1][0]!=,||Token[i+1][0] != ,) strcat(temp, ); }//End for strcat(temp,\n\0); fwrite(&temp,strlen(temp),1,Out_file); } /*The Gen_Token function breaks the input line into tokens*/ int Gen_Token(char str[], char Token[][10]) { int i=0;j=0,k=0; while(str[k]!=\0) {
Page 64

j=0; while(str[k] == || str[k] ==\t) k++; while(str[k])!= && str[k]!=\0 && str[k]!= = && str[k] != / && str[k]!= + && str[k] != - && str[k]!= * && str[k] != , && str[k]!= ;) Token[i][j++] = str[k++]; Token[i++][j] = \0; if(str[k] == =|| str[k] == /|| str[k] == +|| str[k] == -|| str[k] == *|| str[k] == *|| str[k] == ,|| str[k] == ;) { Token[i][0] = str[k++]; Token[i++][1] = \0; }//End if if (str[k] == \0) break; }//End while return i; } Input File: code.txt #include main() { float pi=3.14,r,a; a = pi*r*r; printf(a = %f,a); return 0; }

Page 65

OUTPUT
#include main() { float pi = 3.14, r, a; a = 3.14 * r * r; printf(a = %f,a); return 0; }

Page 66

11.

Study of an Object Oriented Compiler.

Object-Oriented Compiler

A compiler takes a program in a source language, creates some internal representation while checking the syntax of the program, performs semantic checks, and finally generates something that can be executed to produce the intended effect of the program. 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. It turns out areas. A Compiler is a program that can read a program in one language the source 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 language and translate it into an equivalent program in another language the however, that compiler implementation can benefit from object technology in many more

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.

Page 67

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. methods. All work is carried out by messages , which can be debugged by instrumenting their 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.

Compilers are usually made with tools such as parser and lexical analysis generators. A

parser-generator takes a grammar, specified in a language such as BNF or EBNF, checks it, and constructs a representation (the parser) which will execute semantic actions as phrases over the grammar are recognized. If the parser consists of a set of persistent objects, checking the grammar is accomplished by sending a message to the objects. Similarly, recognizing a program amounts to a message to the start symbol of the grammar. Goal objects are then created to represent the phrases to be recognized and the user actions are defined as methods for the goals which are called from the parsing objects. The presentation will discuss existing Java implementations of these ideas: oops, a parser generator based on EBNF and objects; the compiler kit, a class library for implementing object-based tool for tree traversal, helpful in debugging and classical code generation. Introduction This paper summarizes our experiences how compiler construction benefits from objectoriented programming techniques. 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: objects enforce information hiding and state encapsulation, methods help to develop by divide and conquer, all work is carried out by messages which can be debugged by instrumenting their methods. Most importantly, classes encourage code reuse between projects and inheritance allows code reuse within a libraries contain many pre-fabricated algorithms and data structures.
Page 68

parse trees and interpreters for typical programming language constructs; and jag, an

project and modifications from one project to another. As an added benefit, modern class

Symbol Table

symtab manages a container for descriptions of mostly user-defined symbols: lex assembles a word form the source and hands it as a key to symtab to locate a description or create a new one. The lookup happens once per word of the source: from this point on the description is passed along by reference. Other parts of the compiler query the description or contribute more information. Symbol table and descriptions are obvious candidates for OOP within a compiler: the table is a container object where each description object is held. The descriptions share at least the ability to be located by key. If a base class is used to hold the key, inheritance helps to encapsulate and share the lookup mechanism while keeping it separate from the information constituting the actual description. Depending on the implementation

language, it is highly likely that an existing class library provides a suitable container, an efficient lookup mechanism, and perhaps even value representations for some of the description information.

Execution

Using OOP a compiler can transform a program source into a tree of persistent objects as an image. Execution is accomplished by sending a message to the root node of that tree which results in partial traversal as the message is passed along the tree. Specifically in Java it is very simple to make objects persistent. This results in a cheap, platform-independent image format and images can be executed wherever a Java machine is available. Moreover, the execution message can be reused in the compiler, e.g., when constant expressions need to be evaluated or expressions should be partially folded. This is a compilation and execution. significant advantage as it ensures that identical mechanisms are used for evaluation during

Semantic Analysis

Semantic analysis decides if a syntactically acceptable program is meaningful. For a large part it is concerned with the interaction of various data types in expressions: during a postorder traversal of the parse tree, result types are computed for each part of an expression and stored in the nodes for the benefit of code generation. Parse tree nodes are objects, their classes must implement a method to perform semantic nodes. Types are modeled as unique objects. They have methods informing the semantic analysis about available operations for the type and about permissible interaction with used as an interpreter or traversed for code generation. other types. Other type methods generate a simplified, persistent runtime tree which can be

checking of the node. If necessary, the method can augment the parse tree with conversion

Syntax Analysis

A compiler converts a sentence written in some language, i.e., a program, into an executable

Page 69

image. A compiler-compiler converts a sentence written in a language like EBNF, i.e., a grammar, into an image which is itself a compiler. Semantic analysis for a grammar means to check if the grammar is suitable for parsing, e.g., because it fulfills a condition such as LL(1). Using the image resulting from a grammar means at least to perform recognition, i.e., the execution message must implement at least a parsing algorithm. When the parser recognizes a phrase, it must either build an abstract syntax tree or it

should execute some user action. A popular generator, YACC, augments phrases with C statements.The phrases are specified in BNF, i.e., without an iteration syntax, to simplify how the C statements get access to the symbols accepted by the phrase.We have employed OOP to implement a parser generator oops which accepts a grammar written in EBNF, checks that it is LL(1), and creates a recursive descent parser for it. OOPS compiles itself; it was bootstrapped with jay, a version of YACC which we retargeted to Java. Both versions of oops share the class library for the execution trees. Unlike YACC, OOPS can deal with EBNF and has no syntax for user actions. When the generated parser starts on a phrase it creates a goal object from a phrase-specific class. The goal object receives shift and reduce messages as the phrase is recognized and completed. trivial goal classes for checking a grammar and tracing recognition. User actions can be implemented in the required methods for the goal classes. We provide

Conclusion

The popularity of Java has made it the language of choice for many university courses if not industrial projects. While in our opinion Java is not yet quite robust, efficient, and above all make sense to investigate old programming techniques using new paradigms. Java supports and (much more than C++) encourages OOP which makes significant promises to improve critical aspects of the software development process. We tried to show in this paper that these promises do apply to compiler construction: for projects, OOP in compilers permits significant code reuse, for instruction, OOP in compilers simplifies the design effort and makes some important algorithms accessible and transparent. portable enough for mission-critical applications, it is likely to get there soon and it does

Page 70