Labmannual Cd2

MAHAKAL INSTITUTE OF TECHNOLOGY BEHIND AIR STRIP UJJAIN (MP)

Approved By All India Council of Technical Education (New Delhi)

DEPARTMENT OF INFORMATION TECHNOLOGY

COMPILER DESIGN (IT-701)

LAB - MANUAL

Affiliated to Rajiv Gandhi Prodyogiki Vishwavidyalaya Bhopal (MP)

INDEX S.NO.

Program Name

1

WAP to count number of words, characters and line of a text file WAP to replace every odd occurrence a particular word in file by the same word written in uppercase. WAP to implement DFA for Accepting Pascal identifier and relational Operator. WAP to recognize variable declaration for following types :- int, char, long, double. WAP to convert given infix expression to post fix expression. WAP to evaluate postfix expression

2 3 4 5 6

7

WAP to find FIRST set for Nonterminals of a given grammar.

8

WAP to find FOLLOW set for Nonterminals of a given grammar.

9

10

WAP to construct predictive parser for given grammar with following option. • Print parse table • Parser string WAP to find LEADING sets for a given grammar.

11

WAP to find TRAILING sets for a given grammar

12

WAP to construct Operator precedence parser for given grammar. WAP to construct recursive descent parser for given grammar

13

Date

Signature

Remarks

PROGRAM NO: - 1 Unit/Topic: 1/ Review of File handling in C

PROBLEM DEFINITION: WAP to count number of words and line in a file..

OBJECTIVE: To revise concept of reading, updating a file through C program.

ALGORITHM: 1 2 3

4 5

To open a text file in read mode Set w1 =0 , l1:=0; While (! EOF ) a. Increment w1 for every blank space b. Increment l1 for every new line. Close file. Print w1 and l1.

INPUT SET: network.txt

OUTPUT SET: No. of char 15 No. of blanks 2 No. of lines 1 No. of tabs 0

NOTES: Once the file has been opened for reading using fopen() , as we have seen , the file’s content are brought into buffer and a pointer is setup that points to the first character in buffer.

PROGRAM: #include<stdio.h> #include void main() { clrscr(); int nol=0,nob=0,noc=0,not=0; char ch; FILE *fp; fp=fopen("College.txt","r"); while(1) { ch=getc(fp); if(ch==EOF) break; else { noc++; nol++; if(ch==' ') nob++; if(ch=='\n') nol++; if(ch=='\t') not++; } } fclose(fp); printf("No. of char %d",noc); printf("\nNo. of blanks %d",nob); printf("\nNo. of lines %d",nol); printf("\nNo of tabs %d",not); getch(); }

OUTPUT: No. of char 15 No. of blanks 2 No. of lines 1 No. of tabs 0

NAME OF FACULTY: Prof. Kshitij Pathak SIGNATURE: DATE:

PROGRAM NO: - 2 Unit/Topic: 2/ Review of File handling in C

PROBLEM DEFINITION: WAP to replace every odd occurrence a particular word in file by the same word written in uppercase

OBJECTIVE: To revise concept of reading, updating and writing a file through C program.

ALGORITHM: 1. 2. 3. 4.

To open a text file in read, write mode read the word which is to be searched and replaced. initialize count :=0; While (! EOF ) a. Increment count for every occurrence of word. b. If count is odd replace the word . 5. if count ==0 print word not found 6. else print Success. 7. Close file.

INPUT SET: P1.txt

OUTPUT SET: Source file content is copied in the target with language replacing.

Compiler converts the source language that is high level language into target language that is low level language.

Compiler converts the source LANGUAGE that is high level language into target LANGUAGE that is low level language.

NOTES: Once the file has been opened for reading using fopen() , as we have seen , the file’s content are brought into buffer and a pointer is setup that points to the first character in buffer.

PROGRAM: #include<stdio.h> #include #include<string.h> void main() { char ch; char chs[20]; char chp[20]; char token[20]; char *match="language"; int i=0,flag=0,count=0,k; FILE *fs,*ft; clrscr(); fs=fopen("P1.txt","r"); if(fs==NULL) { printf("Cannot open source file"); } ft=fopen("P2.txt","w"); if(ft==NULL) { printf("Cannot open target file"); } ch=fgetc(fs); while(ch!=EOF) { i=0; while(ch!=''&& ch!='\n' && ch!=EOF) { token[i]=ch; ch=fgetc(fs); i++; } token[i]='\0'; i=0; k=strcmp(token, match); if(k==0) { flag++; while(1) { ch=token[i]; i++; if(ch=='\0') { break; }

else { count++; if(count%2==0) { fputc(ch,ft); } else { chs[0]=ch; strcpy(chp, strupr(chs)); fputc(chp[0],ft); } } } ch=fgetc(fs); fputc('',ft); } else { i=0; while(token[i]!='\0') { fputc(token[i],ft); i++; } ch=fgetc(fs); fputc('',ft); } } if(flag==0) { printf("\n String %s is not available in the source file", match); } else { printf("Source file content is copied in the target with %s replacing.", match); } fclose(ft); fclose(fs); getch(); }

OUTPUT : Source file content is copied in the target with language replacing.

Compiler converts the source language that is high level language into target language that is low level language.

Compiler converts the source LANGUAGE that is high level language into target LANGUAGE that is low level language.

NAME OF FACULTY:Proff. Kshitij Pathak SIGNATURE: DATE:

PROGRAM NO: - 3 Unit/Topic: 1/ Review of Finite automata, Lexical Analyzer

PROBLEM DEFINITION: WAP to implement DFA for Accepting Pascal identifier.

OBJECTIVE: To understand and implement DFA by implementing Pascal identifier

ALGORITHM: The expression representing Pascal Identifier identifier = letter (letter | digit)* Steps: 1. Read string. 2. if first character than move to state 1 a. if next character is letter or digit than move to state 2 i. if next character is letter or digit remain in state 2 ii. else if next character is \0 print “ String is Identifier” and exit iii. else print “not a Pascal identifier” b. else i. if next character is \0 print “ String is Identifier” and exit ii. else print “not a Pascal identifier”. 3. else print “Not an Pascal identifier”.

INPUT SET: Enter string for checking : id+id*id Enter string for checking : Anamika Enter string for checking : print6

OUTPUT SET: ( id+id*id ) is not an identifier Because it's 3 letter ( + ) is not a char and not a digit ( Anamika ) is an identifier ( print6 ) is an identifier

NOTES: DFA machine has atmost 1 transition from each state to any input,so it is easy to determine whether a dfa accepts or rejects a string

PROGRAM: #include #include<stdio.h> #include<string.h> int isnumber(char no) { if(no>=48 && no<=57) { return 1; } else { return 0; } } int ischar(char c) { if(((c>=65) && (c<=90)) || ((c>=97) && (c<=122))) { return 1; } else { return 0; } } void main() { char *s; clrscr(); printf("Enter string for checking :\n"); gets(s); int str_len=strlen(s); if((str_len<=8 && str_len>=1)) { if(ischar(s[0])) {

for(int i1=1;i1<str_len;i1++) { if(!isnumber(s[i1]) && !ischar(s[i1])) { printf("\n\n( %s ) is not an identifier\n\n\ Because it's %d letter ( %c ) is not a char and not a digit\n",s,i1+1,s[i1]); break; } } if(i1==str_len) { printf("\n\n( %s ) is an identifier", s); } } else { printf("\n\n( %s ) is not an identifier\n\nBecause it's 1st letter is not a char\n", s); } } else { printf("\n\n( %s ) is not an identifier\n\nBecause it has more than 8 char\n", s); } getch(); }

OUTPUT : Enter string for checking : id+id*id ( id+id*id ) is not an identifier Because it's 3 letter ( + ) is not a char and not a digit

Enter string for checking : Anamika ( Anamika ) is an identifier

Enter string for checking : print6 ( print6 ) is an identifier

NAME OF FACULTY: Proff. Kshitij Pathak SIGNATURE: DATE:

PROGRAM NO: - 4 Unit/Topic: 1, 2/ Lexical Analyzer , Recognition of tokens

PROBLEM DEFINITION: WAP to recognize variable declaration for following types :- int, char, long, double.

OBJECTIVE: To recognize keywords and check for correct declaration statement.

ALGORITHM: 1. Check for the line starting with given key words 2. For each line a. Move to next word. b. Check whether the word is identifier (can use module written in program 3) c. If word is identifier then repeat step a, b till get delaminater (;) d. Else print “not valid declaration”.

INPUT SET: Enter string : Anamika Enter string : char Anamika;

OUTPUT SET: Declaration Error : 1st word (Anamika ) is not a keyword ( char ) is a keyword

PROGRAM: #include #include<stdio.h> #include<string.h> int isnumber(char no) { if(no>=48 && no<=57) { return 1; } else { return 0; } } int ischar(char c) { if(((c>=65) && (c<=90)) || ((c>=97) && (c<=122)) || c=='_') { return 1; } else { return 0; } } int isidentifier(char *s) { int str_len=strlen(s); if((str_len<=8 && str_len>=1)) { if(ischar(s[0])) { for(int i1=1;i1<str_len;i1++) { if(!isnumber(s[i1]) && !ischar(s[i1])) { printf("\n\n( %s ) is not an identifier\n\n Because it's %d letter ( %c ) is not a char or not a digit\n",s,i1+1,s[i1]); break; } } if(i1==str_len) { printf("\n\n( %s ) is an identifier", s); return 1;

} } else { printf("\n\n( %s ) is not an identifier\n\nBecause it's 1st letter is not a char\n", s); } } else { printf("\n\n( %s ) is not an identifier\n\nBecause it has more than 8 char\n", s); return 0; } } int iskeyword(char *s) { char *keywords[] = { "int", "char", "long", "double" }; for(int i=0;i<4;i++) { if(strcmp(s, keywords[i])==0) break; } if(i==4) { return 0; } else { return 1; } } void main() { char x='y'; while((x=='y')||(x=='Y')) { clrscr(); char *s,p[20],p1; int i,i1=0,word=0; printf("Enter string :\n"); gets(s); int str_len=strlen(s); if(s[str_len-1]!=';')

{ printf("\nTermination Error"); } else { for(i=0;i<str_len;i++) { p1=s[i]; if((p1==',')||(p1==' ')||(i==str_len-1)) { p[i1]='\0'; word++; printf("%d", word); i1=0; } else { p[i1]=p1; i1++; } if(i1==0) { if(p1==' ' && word==1) { if(!iskeyword(p)) { printf("\nDeclaration Error : 1st word ( %s ) is not a keyword", p); break; } else { printf("\n ( %s ) is a keyword", p); } } else { if(word==1) { printf("\nDeclaration Error : Wrong string"); break; } else { if(p1==' ') { printf("\nDeclaration Syntex Error : There is a space between variables"); break; } else

{ isidentifier(p); break; printf(" %s is not an dentifier", p); } } } } } } printf("\nDo you want to insert new string : y/n \t"); x=getch(); } }

OUTPUT: Enter string : Anamika Declaration Error : 1st word (Anamika ) is not a keyword Do you want to insert new string : y/n y Enter string : char Anamika; ( char ) is a keyword Do you want to insert new string : y/n n

NAME OF FACULTY: Proff. Kshitij Pathak SIGNATURE: DATE:

PROGRAM NO: - 5 Unit/Topic: 3/ Intermediate code forms

PROBLEM DEFINITION: WAP to convert given infix expression to post fix expression.

OBJECTIVE: To understand post fix representation of an expression.

ALGORITHM: 1. Place parentheses around the expression 2. Moving left to right until the end of the infix expression a. if the item is a number put into the post fix expression b. if the item is an open brace push it onto the stack c. if the item is an operator pop all operators of lower and equal precedence off of the stack and place them in the postfix expression, then push the operator onto the stack d. If the operator is a close brace pop all operators off the stack until an open brace, then delete

INPUT SET: Enter the infix expression: a+b

OUTPUT SET: The postfix expression is: ab+

NOTES: When operator symbol is placed between 2 operands,it is an infix expression,whereas When operator symbol is placed after 2 operands,it is an postfix expression.

PROGRAM: #include<stdio.h> #include #include<string.h> char stack[50]; int top=-1; void in_to_post(char infix[]); void push(char); char pop(); void main() { char infix[25]; clrscr(); printf("Enter the infix expression:\n"); gets(infix); in_to_post(infix); getch(); } void push(char symb) { if(top>=49) { printf("Stack overflow"); getch(); return; } else { top=top+1; stack[top]=symb; } } char pop() { char item; if(top==-1) { printf("Stack empty"); getch(); return(0); } else { item=stack[top]; top--; }

return(item); } int preced(char ch) { if(ch==47) { return(5); } else if(ch==42) { return(4); } else if(ch==43) { return(3); } else { return(2); } } void in_to_post(char infix[]) { int length; static int index=0,pos=0; char symbol,temp; char postfix[40]; length=strlen(infix); push('#'); while(index=preced(symbol))

{ temp=pop(); postfix[pos]=temp; pos++; } push(symbol); break; default : postfix[pos++]=symbol; break; } index++; } while(top>0) { temp=pop(); postfix[pos++]=temp; } postfix[pos++]='\0'; printf("The postfix expression is:\n",postfix); puts(postfix); return; }

OUTPUT : Enter the infix expression: a+b The postfix expression is: ab+

NAME OF FACULTY: Proff. Kshitij Pathak SIGNATURE: DATE:

PROGRAM NO: - 6 Unit /Topic: 3 / Intermediate code forms.

PROBLEM DEFINITION: WAP to evaluate post fix expression.

OBJECTIVE: To understand use of post fix expression.

ALGORITHM: 1. Moving left to right along the post fix expression a. If the item is a number push it onto the stack b. If the item is an operator pop two numbers from the Stack, execute the operator and push the result back onto the stack c. When no more items in the postfix string pop the answer off the stack

INPUT SET: Enter a valid postfix expression: ab+ Enter the value of a: 8 Enter the value of b: 8

OUTPUT SET: The result of ab+ is = 16.000000

NOTES: When operator symbol is placed after 2 operands,it is an postfix expression.It is also known as Reverse Polish Notation

PROGRAM: #include<stdio.h> #include float stack[10]; int top=-1; void push(char); float pop(); float eval(char[],float[]); void main() { int i=0; char suffix[20]; float value[20],result; clrscr(); printf("Enter a valid postfix expression:\n"); gets(suffix); while(suffix[i]!='\0') { if(isalpha(suffix[i])) { fflush(stdin); printf("Enter the value of %c:\n",suffix[i]); scanf("%f",&value[i]); } i++; } result=eval(suffix,value); printf("The result of %s is = %f",suffix,result); getch(); } float eval(char suffix[],float data[]) { int i=0; float op1,op2,res; char ch; while((suffix[i])!='\0') { ch=suffix[i]; if(isalpha(suffix[i])) { push(data[i]); } else { op2=pop(); op1=pop(); switch(ch) {

case '+' : push(op1+op2); break; case '-' : push(op1-op2); break; case '*' : push(op1*op2); break; case '/' : push(op1/op2); break; case '^' : push(pow(op1,op2)); break; } } i++; } res=pop(); return(res); } void push(char num) { top=top+1; stack[top]=num; } float pop() { float num; num=stack[top]; top=top-1; return(num); }

OUTPUT : Enter a valid postfix expression: ab+ Enter the value of a: 8 Enter the value of b: 8 The result of ab+ is = 16.000000

NAME OF FACULTY: Proff. Kshitij Pathak SIGNATURE: DATE:

PROGRAM NO: - 7 Unit/Topic: 2/ Parsing Technique

PROBLEM DEFINITION: WAP to find FIRST set for Nonterminals of a given grammar. E -> TE’ E’ -> +TE | ε T -> FT’ T’ -> *FT’ | ε F -> (E) | id

OBJECTIVE: To understand concept of First set and implementation associated with it

ALGORITHM: 1. 2.

If X is a terminal, FIRST(X) = X. Otherwise (X is a nonterminal), • If X ->ε is a production, add ε to FIRST(X) • If X -> Y1 … Yk is a production, then place a in FIRST(X) if for some i, a is in FIRST(Yi) and Y1…Yi-1 =*> ε

Given FIRST(X) for all single symbols X, Let FIRST(X1…Xn) = FIRST(X1) If ε € FIRST(X1), then add FIRST(X2), and so on…

INPUT SET: Enter the grammar : E->TE’ E’->+TE’ | ε T->FT’ T’->*FT’ | ε F->(E) | id

OUTPUT SET: First of E = ( , id First of E’ = + , ε First of T = ( , id First of T’ = * , ε First of F = ( , id

PROGRAM: #include<stdio.h> #include void main() { clrscr(); char f1, f2, f3, f4, f5; char *p1,*p2,*p3,*p4,*p5; printf(“Enter the grammar :\n"); gets(p1); gets(p2); gets(p3); gets(p4); gets(p5); if(p1[3]==p2[0]) { if(p2[3]!=p3[0]) { f1=p2[3]; } else { f1=p3[3]; } } if(p1[3]==p3[0]) { if(p3[3]!=p2[0]) { f1=p3[3]; } else { f1=p2[3]; } } if(p1[3]==p4[0]) { if(p4[3]!=p3[0]) { f1=p4[3]; } else { f1=p3[3]; } } if(p1[3]==p5[0]) {

if(p5[3]!=p4[0]) { f1=p5[3]; } else { f1=p4[3]; } } if(p1[3]!=p2[0]&&p1[3]!=p3[0]&& p1[3]!=p4[0]&& p1[3]!=p5[0]) { f1=p1[3]; } if(p2[3]==p1[0]) { if(p1[3]!=p3[0]) { f2=p1[3]; } else { f2=p3[3]; } } if(p2[3]==p3[0]) { if(p3[3]!=p1[0]) { f2=p3[3]; } else { f2=p1[3]; } } if(p2[3]==p4[0]) { if(p4[3]!=p1[0]) { f2=p4[3]; } else { f2=p1[3]; } } if(p2[3]==p5[0]) { if(p5[3]!=p1[0]) {

f2=p5[3]; } else { f2=p1[3]; } } if(p2[3]!=p1[0]&&p2[3]!=p3[0]&& p2[3]!=p4[0]&&p2[3]!=p5[0]) { f2=p2[3]; } if(p3[3]==p1[0]) { if(p1[3]!=p2[0]) { f3=p1[3]; } else { f3=p2[3]; } } if(p3[3]==p2[0]) { if(p2[3]!=p1[0]) { f3=p2[3]; } else { f3=p1[3]; } } if(p3[3]==p4[0]) { if(p4[3]!=p1[0]) { f3=p4[3]; } else { f3=p1[3]; } } if(p3[3]==p5[0]) { if(p5[3]!=p1[0]) { f3=p5[3]; }

else { f3=p1[3]; } } if(p3[3]!=p1[0]&&p3[3]!=p2[0]&& p3[3]!=p4[0]&&p3[3]!=p5[0]) { f3=p3[3]; } if(p4[3]==p1[0]) { if(p1[3]!=p2[0]) { f4=p1[3]; } else { f4=p2[3]; } } if(p4[3]==p2[0]) { if(p2[3]!=p1[0]) { f4=p2[3]; } else { f4=p1[3]; } } if(p4[3]==p3[0]) { if(p3[3]!=p2[0]) { f4=p3[3]; } else { f4=p2[3]; } } if(p4[3]==p5[0]) { if(p5[3]!=p1[0]) { f4=p5[3]; } else {

f4=p1[3]; } } if(p4[3]!=p1[0]&&p4[3]!=p2[0]&& p4[3]!=p3[0]&&p4[3]!=p5[0]) { f4=p4[3]; } if(p5[3]==p1[0]) { if(p1[3]!=p2[0]) { f5=p1[3]; } else { f5=p2[3]; } } if(p5[3]==p2[0]) { if(p2[3]!=p1[0]) { f5=p2[3]; } else { f5=p1[3]; } } if(p5[3]==p3[0]) { if(p3[3]!=p2[0]) { f5=p3[3]; } else { f5=p2[3]; } } if(p5[3]==p4[0]) { if(p4[3]!=p1[0]) { f5=p4[3]; } else { f5=p1[3]; }

} if(p5[3]!=p1[0]&&p5[3]!=p2[0]&& p5[3]!=p3[0]&&p5[3]!=p4[0]) { f5=p5[3]; } printf(“\n”); printf("First of %c = %c \n",p1[0],f1); printf("First of %c = %c \n",p2[0],f2); printf("First of %c = %c \n",p3[0],f3); printf("First of %c = %c \n",p4[0],f4); printf("First of %c = %c \n",p5[0],f5); getch(); }

OUTPUT : Enter the grammar : E->TE’ E’->+TE’ | ε T->FT’ T’->*FT’ | ε F->(E) | id First of E = ( , id First of E’ = + , ε First of T = ( , id First of T’ = * , ε First of F = ( , id

NAME OF FACULTY: Proff. Kshitij Pathak SIGNATURE: DATE:

PROGRAM NO: - 8 Unit/Topic: 2/ Parsing Technique.

PROBLEM DEFINITION: WAP to find FOLLOW set for Nonterminals of a given grammar. E -> TE’ E’ -> +TE | ε T -> FT’ T’ -> *FT’ | ε F -> (E) | id

OBJECTIVE: To understand concept of Follow set and implementation associated with it.

ALGORITHM: 1. Place $ in FOLLOW(S) (where S the start symbol) 2. If A -> α B β, then in FOLLOW(B) = FIRST(β)- ε 3. If there is a production A -> α B or a production A -> α B β where β =*> ε, then everything in FOLLOW(A) is in FOLLOW(B). 4. Repeatedly apply these rules until no FOLLOW set changes.

INPUT SET: Enter the grammar : E->TE’ E’->+TE’ | ε T->FT’ T’->*FT’ | ε F->(E) | id

OUTPUT SET: Follow of E Follow of E’ Follow of T Follow of T’ Follow of F

=),$ =),$ =+,),$ =+,),$ =+,*,),$

PROGRAM: #include<stdio.h> #include void main() { clrscr(); char f1,f2,f3,f4,f5; char *p1,*p2,*p3,*p4,*p5; printf(“Enter the grammar :\n"); gets(p1); gets(p2); gets(p3); gets(p4); gets(p5); if(p1[3]==p2[0]) { if(p2[3]!=p3[0]) { f1=p2[3]; } else { f1=p3[3]; } } if(p1[3]==p3[0]) { if(p3[3]!=p2[0]) { f1=p3[3]; } else { f1=p2[3]; } } if(p1[3]==p4[0]) { if(p4[3]!=p3[0]) { f1=p4[3]; } else { f1=p3[3]; } } if(p1[3]==p5[0])

{ if(p5[3]!=p4[0]) { f1=p5[3]; } else { f1=p4[3]; } } if(p1[3]!=p2[0]&&p1[3]!=p3[0]&& p1[3]!=p4[0]&& p1[3]!=p5[0]) { f1=p1[3]; } if(p2[3]==p1[0]) { if(p1[3]!=p3[0]) { f2=p1[3]; } else { f2=p3[3]; } } if(p2[3]==p3[0]) { if(p3[3]!=p1[0]) { f2=p3[3]; } else { f2=p1[3]; } } if(p2[3]==p4[0]) { if(p4[3]!=p1[0]) { f2=p4[3]; } else { f2=p1[3]; } } if(p2[3]==p5[0]) { if(p5[3]!=p1[0])

{ f2=p5[3]; } else { f2=p1[3]; } } if(p2[3]!=p1[0]&&p2[3]!=p3[0]&& p2[3]!=p4[0]&&p2[3]!=p5[0]) { f2=p2[3]; } if(p3[3]==p1[0]) { if(p1[3]!=p2[0]) { f3=p1[3]; } else { f3=p2[3]; } } if(p3[3]==p2[0]) { if(p2[3]!=p1[0]) { f3=p2[3]; } else { f3=p1[3]; } } if(p3[3]==p4[0]) { if(p4[3]!=p1[0]) { f3=p4[3]; } else { f3=p1[3]; } } if(p3[3]==p5[0]) { if(p5[3]!=p1[0]) { f3=p5[3];

} else { f3=p1[3]; } } if(p3[3]!=p1[0]&&p3[3]!=p2[0]&& p3[3]!=p4[0]&&p3[3]!=p5[0]) { f3=p3[3]; } if(p4[3]==p1[0]) { if(p1[3]!=p2[0]) { f4=p1[3]; } else { f4=p2[3]; } } if(p4[3]==p2[0]) { if(p2[3]!=p1[0]) { f4=p2[3]; } else { f4=p1[3]; } } if(p4[3]==p3[0]) { if(p3[3]!=p2[0]) { f4=p3[3]; } else { f4=p2[3]; } } if(p4[3]==p5[0]) { if(p5[3]!=p1[0]) { f4=p5[3]; } else

{ f4=p1[3]; } } if(p4[3]!=p1[0]&&p4[3]!=p2[0]&& p4[3]!=p3[0]&&p4[3]!=p5[0]) { f4=p4[3]; } if(p5[3]==p1[0]) { if(p1[3]!=p2[0]) { f5=p1[3]; } else { f5=p2[3]; } } if(p5[3]==p2[0]) { if(p2[3]!=p1[0]) { f5=p2[3]; } else { f5=p1[3]; } } if(p5[3]==p3[0]) { if(p3[3]!=p2[0]) { f5=p3[3]; } else { f5=p2[3]; } } if(p5[3]==p4[0]) { if(p4[3]!=p1[0]) { f5=p4[3]; } else { f5=p1[3];

} } if(p5[3]!=p1[0]&&p5[3]!=p2[0]&& p5[3]!=p3[0]&&p5[3]!=p4[0]) { f5=p5[3]; } int n=5; while(p1[n]!='\0') { if(p1[n]==p1[0]) { n++; if(p1[n]!=p1[0]&&p1[n]!=p2[0]&&p1[n]!=p3[0]&& p1[n]!=p4[0]&& p1[n]!=p5[0]) { i++; f1[i]=p1[n]; } if(p1[n]==p2[0]) { i++; f1[i]=f2; } if(p1[n]==p3[0]) { i++; f1[i]=f3; } if(p1[n]==p1[0]) { i++; f1[i]=f1; } } n++; } n=5; while(p2[n]!='\0') { if(p2[n]==p1[0]) { n++; if(p2[n]!=p1[0]&&p2[n]!=p2[0]&&p2[n]!=p3[0]&& p2[n]!=p4[0]&&p2[n]!=p5[0]) { i++; f2[i]=p2[n]; } if(p2[n]==p2[0]) {

i++; f2[i]=f2; } if(p2[n]==p3[0]) { i++; f2[i]=f3; } if(p2[n]==p1[0]) { i++; f2[i]=f1; } } n++; } n=5; while(p3[n]!='\0') { if(p3[n]==p1[0]) { n++; if(p3[n]!=p1[0]&&p3[n]!=p2[0]&&p3[n]!=p3[0]&& p3[n]!=p4[0]&&p3[n]!=p5[0]) { i++; f3[i]=p3[n]; } if(p3[n]==p2[0]) { i++; f3[i]=f2; } if(p3[n]==p3[0]) { i++; f3[i]=f3; } if(p3[n]==p1[0]) { i++; f3[i]=f1; } } n++; } n=5; while(p4[n]!='\0') { if(p4[n]==p1[0])

{ n++; if(p4[n]!=p1[0]&&p4[n]!=p2[0]&&p4[n]!=p3[0]&& p4[n]!=p4[0]&&p4[n]!=p5[0]) { i++; f4[i]=p4[n]; } if(p4[n]==p2[0]) { i++; f4[i]=f2; } if(p4[n]==p3[0]) { i++; f4[i]=f3; } if(p4[n]==p1[0]) { i++; f4[i]=f1; } } n++; } n=5; while(p5[n]!='\0') { if(p5[n]==p1[0]) { n++; if(p5[n]!=p1[0]&&p5[n]!=p2[0]&&p5[n]!=p3[0]&& p5[n]!=p4[0]&&p5[n]!=p5[0]) { i++; f5[i]=p5[n]; } if(p5[n]==p2[0]) { i++; f5[i]=f2; } if(p5[n]==p5[0]) { i++; f5[i]=f3; } if(p5[n]==p1[0]) {

i++; f5[i]=f1; } } n++; } printf(“\n”); printf("Follow of printf("Follow of printf("Follow of printf("Follow of printf("Follow of getch();

%c %c %c %c %c

= %c \n",p1[0],f1); = %c \n",p2[0],f2); = %c \n",p3[0],f3); = %c \n",p4[0],f4); = %c \n",p5[0],f5);

}

OUTPUT : Enter the grammar : E->TE’ E’->+TE’ | ε T->FT’ T’->*FT’ | ε F->(E) | id Follow of E Follow of E’ Follow of T Follow of T’ Follow of F

=),$ =),$ =+,),$ =+,),$ =+,*,),$

\

NAME OF FACULTY: Proff. Kshitij Pathak SIGNATURE: DATE:

PROGRAM NO: - 9 Unit/Topic: 2/ Parsing Technique

PROBLEM DEFINITION: WAP to construct predictive parser for given grammar with following option. • Print parse table • Parser string E -> TE’ E’ -> +TE | ε T -> FT’ T’ -> *FT’ | ε F -> (E) | id.

OBJECTIVE: To understand concept predictive parser and implement it.

ALGORITHM: To construct parse table(represented by matrix M) 1. For each production A ->α in G, do: a. For each terminal a in FIRST(α ) add A -> α to M[A,a] b. If ε belongs to FIRST(α ), for each terminal b in FOLLOW(A), i. add A -> α to M[A,b] c. If ε belongs to FIRST(α) and $ is in FOLLOW(A), i. add A -> α to M[A,$] 2. Make each undefined entry in M[ ] an ERROR

Parsing a string Repeat At each step, the parser considers the top-of-stack symbol X and input symbol a: 1. If both are $, accept 2. If they are the same (nonterminals), pop X, advance input 3. If X is a nonterminal, consult M[X,a]. a. If M[X,a] is “ERROR” call an error recovery routine. b. Otherwise, if M[X,a] is a production of he grammar X -> UVW, replace X on the stack with WVU (U on top) Until not error or end of input string

INPUT SET: Enter any String(Append with $) : id + id * id$

OUTPUT SET: Stack $E $E’T $E’T’F $E’T’id $E’T’ $E’ $E’T+ $E’T $E’T’F $E’T’id $E’T’ $E’T’F* $E’T’F $E’T’id $E’T’ $E’ $

Input id + id * id$ id + id * id$ id + id * id$ id + id * id$ + id * id$ + id * id$ + id * id$ id * id$ id * id$ id * id$ * id$ * id$ id$ id$ $ $ $

Output E->TE’ T->FT’ F->id T’->ε E’->+TE’ T->FT’ F->id T’->*FT’ F->id T’->ε E’->ε

Given String is accepted.

NOTES: A syntax analyzer or a parser is a program that performs syntax analysis.

PROGRAM: #include<string.h> #include char a[10]; int top=-1,i; void error() { printf("Syntax Error"); } void push(char k[]) { for(i=0;k[i]!='\0';i++) { if(top<9)

a[++top]=k[i]; } } char TOS() { return a[top]; } void pop() { if(top>=0) a[top--]='\0'; } void display() { for(i=0;i<=top;i++) printf("%c",a[i]); } void display1(char p[],int m) { int l; printf("\t"); for(l=m;p[l]!='\0';l++) printf("%c",p[l]); } char* stack() { return a; } int main() { char ip[20],r[20],st,an; int ir,ic,j=0,k; char t[5][6][10]={"$","$","TE’","$","TE’","$","+TE","$","e","e","$","e", "$","$","FT’","$","FT’","$","e", "*FT","e","e","$","e", "$","$","(E)","$","id","$"}; clrscr(); printf("\nEnter any String(Append with $) :\n"); gets(ip); printf("Stack\t\t\tInput\t\t\tOutput\n"); push("$E"); display(); printf("\t%s\n",ip); for(j=0;ip[j]!='\0';) { if(TOS()==an) { pop(); display(); display1(ip,j+1); printf("\tPOP\n");

j++; } an=ip[j]; st=TOS(); if(st=='E')ir=0; else if(st=='H')ir=1; else if(st=='T')ir=2; else if(st=='U')ir=3; else if(st=='F')ir=4; else { error(); break; } if(an=='+')ic=0; else if(an=='*')ic=1; else if(an=='(')ic=2; else if(an==')')ic=3; else if((an>='a'&&an<='z')||(an>='A'&&an<='Z')){ic=4;an='i';} else if(an=='$')ic=5; strcpy(r,strrev(t[ir][ic])); strrev(t[ir][ic]); pop(); push(r); if(TOS()=='e') { pop(); display(); display1(ip,j); printf("\t%c->%c\n",st,238); } else { display(); display1(ip,j); printf("\t%c->%s\n",st,t[ir][ic]); } if(TOS()=='$'&&an=='$') break; if(TOS()=='$') { error(); break; } } k=strcmp(stack(),"$"); if(k==0 && i==strlen(ip)) { printf("\n\nGiven String is accepted."); }

else { printf("\n\nGiven String is not accepted."); return 0; } }

OUTPUT : Enter any String(Append with $) : id + id * id$ Stack $E $E’T $E’T’F $E’T’id $E’T’ $E’ $E’T+ $E’T $E’T’F $E’T’id $E’T’ $E’T’F* $E’T’F $E’T’id $E’T’ $E’ $

Input id + id * id$ id + id * id$ id + id * id$ id + id * id$ + id * id$ + id * id$ + id * id$ id * id$ id * id$ id * id$ * id$ * id$ id$ id$ $ $ $

Given String is accepted.

NAME OF FACULTY: Proff. Kshitij Pathak SIGNATURE: DATE:

Output E->TE’ T->FT’ F->id T’->ε E’->+TE’ T->FT’ F->id T’->*FT’ F->id T’->ε E’->ε

PROGRAM NO: - 10 Unit/Topic: 2/ Parsing Technique.

PROBLEM DEFINITION: WAP to find LEADING sets for a given grammar. E
E+T|T T
T*F|F F
(E) | Id

OBJECTIVE: To understand concept of LEADING sets and implementation associated with it.

ALGORITHM: Rules for computing Leading set: 1. a is in LEADING (A) a. if there is a production of the form A
γ a δ, i. where γ is ε or single nonterminal. 2. If a is in LEADING (B) and there is a production of the form A
Bα, then a. a is in LEADING (A)

INPUT SET: Enter the grammar : E->E + T | T T->T * F | F F->(E) | id

OUTPUT SET: Leading of E = + , * , ( , id Leading of T = * , ( , id Leading of F = ( , id

PROGRAM: #include<stdio.h> #include void main() { clrscr(); char l1, l2, l3; char *p1,*p2,*p3; printf(“Enter the grammar :\n"); gets(p1); gets(p2); gets(p3); if(p1[3]==p2[0]) { if(p2[3]!=p3[0]) { l1=p2[3]; } else { l1=p3[3]; } } if(p1[3]==p3[0]) { if(p3[3]!=p2[0]) { l1=p3[3]; } else { l1=p2[3]; } } if(p1[3]!=p2[0]&&p1[3]!=p3[0]) { l1=p1[3]; } if(p2[3]==p1[0]) { if(p1[3]!=p3[0]) { l2=p1[3]; } else { l2=p3[3]; } }

if(p2[3]==p3[0]) { if(p3[3]!=p1[0]) { l2=p3[3]; } else { l2=p1[3]; } } if(p2[3]!=p1[0]&&p2[3]!=p3[0]) { l2=p2[3]; } if(p3[3]==p1[0]) { if(p1[3]!=p2[0]) { l3=p1[3]; } else { l3=p2[3]; } } if(p3[3]==p2[0]) { if(p2[3]!=p1[0]) { l3=p2[3]; } else { l3=p1[3]; } } if(p3[3]!=p1[0]&&p3[3]!=p2[0]) { l3=p3[3]; } printf(“\n”); printf("Leading of %c = %c \n",p1[0],l1); printf("Leading of %c = %c \n",p2[0],l2); printf("Leading of %c = %c \n",p3[0],l3); getch(); }

OUTPUT: Enter the grammar : E->E + T | T T->T * F | F F->(E) | id Leading of E = + , * , ( , id Leading of T = * , ( , id Leading of F = ( , id

NAME OF FACULTY: Proff. Kshitij Pathak SIGNATURE: DATE:

PROGRAM NO: - 11 Unit/Topic: 2/ Parsing Technique

PROBLEM DEFINITION: WAP to find TRAILING sets for a given grammar E
E+T|T T
T*F|F F
(E) | Id

OBJECTIVE: To understand concept of TRAILING sets and implementation associated with it..

ALGORITHM: Rules for computing TRAILING set: 3. a is in TRAILING (A) a. if there is a production of the form A
γ a δ, i. where δ is ε or single nonterminal.

INPUT SET: Enter the grammar : E->E + T | T T->T * F | F F->(E) | id

OUTPUT SET: Trailing of E = + , * , ) , id Trailing of T = * , ) , id Trailing of F = ) , id

PROGRAM: #include<stdio.h> #include #include<string.h> void main() { clrscr(); char t1, t2, t3; char *p1,*p2,*p3; char *f1,*f2,*f3; printf(“Enter the grammar :"); gets(p1); gets(p2); gets(p3); int n=3; while(p1[n]!='\0') { if(p1[n]==p1[0]) { n++; if(p1[n]!=p1[0]&&p1[n]!=p2[0]&&p1[n]!=p3[0]) { i++; f1[i]=p1[n]; } if(p1[n]==p2[0]) { i++; f1[i]=t2; } if(p1[n]==p3[0]) { i++; f1[i]=t3; } if(p1[n]==p1[0]) { i++; f1[i]=t1; } } n++; } n=3; while(p2[n]!='\0') { if(p2[n]==p2[0]) { n++;

if(p2[n]!=p1[0]&&p2[n]!=p2[0]&&p2[n]!=p3[0]) { j++; f2[j]=p2[n]; } if(p2[n]==p2[0]) { j++; f2[j]=t2; } if(p2[n]==p3[0]) { j++; f2[j]=t3; } if(p2[n]==p1[0]) { j++; f2[j]=t1; } } n++; } n=3; while(p3[n]!='\0') { if(p3[n]==p3[0]) { n++; if(p3[n]!=p1[0]&&p3[n]!=p2[0]&&p3[n]!=p3[0]) { k++; f3[k]=p3[n]; } if(p3[n]==p2[0]) { k++; f3[k]=t2; } if(p3[n]==p3[0]) { k++; f3[k]=t3; } if(p3[n]==p1[0]) { k++; f3[k]=t1; } }

n++; } printf(“\n”); printf("Trailing of %c = %c \n",p1[0],f1); printf("Trailing of %c = %c \n",p2[0],f2); printf("Trailing of %c = %c \n",p3[0],f3); getch(); }

OUTPUT : Enter the grammar : E->E + T | T T->T * F | F F->(E) | id Trailing of E = + , * , ) , id Trailing of T = * , ) , id Trailing of F = ) , id

NAME OF FACULTY: Proff. Kshitij Pathak SIGNATURE: DATE:

PROGRAM NO: - 13 Unit/Topic: 2/ Parsing Technique

PROBLEM DEFINITION: WAP to construct recursive descent parser for given grammar E -> T E’ E’ -> + T E’ | ε T -> F T’ T’ -> * F T’ | ε F -> ( E ) | id

OBJECTIVE: To understand working of recursive descent parser.

ALGORITHM: Transition diagrams are used to describe recursive parsers, construction: 1. Eliminate left recursion from G 2. Left factor G 3. For each non-terminal A, do • Create an initial and final (return) state. • For each production A -> X1 X2 … Xn, create a path from the initial to the final state with edges X1 X2 … Xn. 4. Begin in the start state for the start symbol 5. When we are in state s with edge labeled by terminal a to state t, a. if the next input symbol is a, move to state and advance the input pointer. b. If the next input symbol is non-terminal A to state t, jump to the transition diagram for A, and when finished, return to state t 6. For an edge labeled ε , move immediately to t.

INPUT SET: Enter the string : id + id * id

OUTPUT SET: String is accepted. Sequence of Productions : E->TE’ T->FT’ F->id T’->ε E’->+TE’ T->FT’ F->id T’->*FT’ F->id T’->ε E’->ε

NOTES: Recursive Descent parsing is a top down method of syntax analysis in which we execute a set of recursive procedures to process the input.

PROGRAM: #include<stdio.h> #include #include<string.h> int j=1,top=-1; int E(); int E’(); int T(); int T’(); int F(); char *ip, a[10]; void main() { clrscr(); int k; printf(“Enter the string :\n”); gets(ip); k=strlen(ip); E(); if(j==k) { printf(“\nString is accepted.”); } else

{ printf(“\nString is rejected because it is not completed.”); } printf(“\nSequence of Productions :\n”); display(); getch(); } void display() { for(j=0;j<=top;j++) printf(“%c”,a[j]); } int E() { printf(“\n\n”); ptintf(“E-> TE' accepted \n”); if(T()==1) { if(E’()==1) { return 1; } else { printf(“Error in E() function \n”); return 0; } } else { printf(“Error in E() function \n”); return 0; } } int T() { printf(“T-> FT' accepted \n”); if(F()==1) { if(T’()==1) { return 1; } else { printf(“Error in T’() function \n”); return 0; } } else

{ printf(“Error in F() function \n”); return 0; } } int E’() { if(*ip=='+') { printf(“E'-> +TE' accepted \n”); j++; ip++; if(T()==1) { if(E’()==1) { return 1; } else { printf(“Error in E’() function \n”); return 0; } } else { printf(“Error in T() function \n”); return 0; } } else { printf(“E’-> ε accepted \n”); return 1; } } int T’() { if(*ip=='*') { printf(“T’-> *FT1 accepted \n”); j++; ip++; if(F()==1) { if(T’()==1) { return 1; } else

{ printf(“Error in T’() function \n”); return 0; } } else { printf(“Error in F() function \n”); return 0; } } else { printf(“T’-> ε return 1;

accepted \n”);

} } int F() { if(*ip=='(') { printf(“F-> (E) accepted \n”); j++; ip++; if(E()==1) { if(*ip==')') { j++; ip++; return 1; } else { printf(“) not present \n”); return 0; } } else { printf(“Error in E()function \n”); return 0; } } else { if(*ip=='id') { j++; ip++;

printf(“F->id return 1;

accepted \n”);

} } }

OUTPUT: Enter the string : id + id * id String is accepted. Sequence of Productions : E->TE’ T->FT’ F->id T’->ε E’->+TE’ T->FT’ F->id T’->*FT’ F->id T’->ε E’->ε

NAME OF FACULTY: Proff. Kshitij Pathak SIGNATURE: DATE: