Compiler Design Lab

E.V.Sasank
AP18110010661
CSE-J.
Program 1(a):
Implement a language recogniser which accepts set of all strings over the alphabet ∑={a,b}
containing an even number of a’s and an even number of b’s.
Description:
The acceptable strings of the language are ε(Null string), aa, bb, abba, babbab etc.

Deterministic Finite Automata for the given language is given below:

DFA M=(Q,∑,δ,Q0,F) Where

Q=Set of all states ={Q0,Q1,Q2,Q3}
∑=Input Alphabet={a,b},
Start state is Q0
F=Set of all final States={ Q0}

And the transitions are defined in the transition diagram

Algorithm: Language recognizer

Input:
input //input string
Output:
Algorithm prints a message
“String accepted”: If the input is acceptable by the language,
“String not accepted” otherwise,
“Invalid token”: If the input string contains symbols other than input alphabet.

Method:
state=0 //initial state
while((current=input[i++])!='\0'){
switch(state)
case 0: if(current=='a') state=1;
else if(current=='b') state=2;
else
Print "Invalid token" ; exit;
case 1: if(current=='a') state=0;
else if(current=='b') state=3;
else
Print "Invalid token" ; exit;
case 2: if(current=='a') state=3;
else if(current=='b') state=0;
else
Print "Invalid token" ; exit;
case 3: if(current=='a') state=2;
else if(current=='b') state=1;
else
Print "Invalid token" ; exit;
end switch
end while
//Print output
if(state==0)
Print ”String accepted”
else
Print ”String not accepted”

Test cases:

Input Expected Output

 aabb String accepted
abab String accepted
aaabb String not accepted
aaa String not accepted
abcd Invalid token

C CODE
#include<stdio.h>
void main(){
int state=0,i=0;
char current,input[20];
printf("Enter input string \t :");
scanf("%s",input);
while((current=input[i++])!='\0'){
switch(state){
case 0: if(current=='a')
state=1;
else if(current=='b')
state=2;
else{
printf("Invalid token");
exit(0);
}
break;
case 1: if(current=='a')
state=0;
else if(current=='b')
state=3;
else{
printf("Invalid token");
exit(0);
 }
break;
case 2: if(current=='a')
state=3;
else if(current=='b')
state=0;
else{
printf("Invalid token");
exit(0);
}
break;
case 3: if(current=='a')
state=2;
else if(current=='b')
state=1;
else{
printf("Invalid token");
exit(0);
}
break;
}
}
if(state==0)
printf("\n\nString accepted\n\n");
else
printf("\n\nString not accepted\n\n");
}
 Input Expected Output
Input 1: aabb Output 1: String accepted
Input 2: abab Output 2: String accepted
Input 3: aaabb Output 3: String not accepted
Input 4: aaa Output 4: String not accepted
Input 5: abcd Output 5: Invalid token

Program 1(b):
Implementation of Language recognizer for set of all strings ending with two symbols of
same type.
Description:
The acceptable strings of the language aa, bb, abbaa, babbabb etc.

Deterministic Finite Automata for the given language is given below:

DFA M=(Q,∑,δ,Q0,F) Where

Q=Set of all states ={Q0,Q1,Q2,Q3,Q4}
∑=Input Alphabet={a,b},
Start state is Q0
F=Set of all final States={ Q2,Q4}

And the transitions are defined in the transition diagram

Algorithm: Language recognizer

Input:
Input //input string
Output:
Algorithm prints a message
“String accepted”: If the input is acceptable by the language,
 “String not accepted” otherwise,
“Invalid token”: If the input string contains symbols other than input alphabet.

Method:
state=0 //initial state
while((current=input[i++])!='\0'){
switch(state)
case 0: if(current=='a') state=1;
else if(current=='b') state=3;
else
Print "Invalid token" ; exit;
case 1: if(current=='a') state=2;
else if(current=='b') state=3;
else
Print "Invalid token" ; exit;
case 2: if(current=='a') state=2;
else if(current=='b') state=3;
else
Print "Invalid token" ; exit;
case 3: if(current=='a') state=1;
else if(current=='b') state=4;
else
Print "Invalid token" ; exit;
case 4: if(current=='a') state=1;
else if(current=='b') state=4;
else
Print "Invalid token" ; exit;

end switch
end while
//Print output
if(state==2 || state==4)
Print ”String accepted”
else
Print ”String not accepted”

Test cases:

Input Expected Output

aabb String accepted
ababaa String accepted
aaabba String not accepted
aaa String not accepted
abcd Invalid token

C CODE
#include <stdio.h>
#include <stdlib.h>
void main(){
int s=0,i=0;
char c,input[20];
printf("Enter the input string:");
scanf("%s",input);
while((c=input[i++])!='\0'){
switch(s) {
case 0: if(c=='a')
s=1;
else if(c=='b')
s=3;
else{
printf("Invalid token");
exit(0);
 }
break;
case 1: if(c=='a')
s=2;
else if(c=='b')
s=3;
else{
printf("Invalid token");
exit(0);
}
break;
case 2: if(c=='a')
s=2;
else if(c=='b')
s=3;
else{
printf("Invalid token");
exit(0);
}
break;
case 3: if(c=='a')
s=1;
else if(c=='b')
s=4;
else{
printf("Invalid token");
exit(0);
}
break;
 case 4: if(c=='a')
s=1;
else if(c=='b')
s=4;
else{
printf("Invalid token");
exit(0);
}
break;
}

}
if(s==2 || s==4)
printf("String accepted");
else{
printf("String not accepted");
}
}

Input Expected Output

Input 1: aa Output 1: String accepted
Input 2: ababb Output 2: String accepted
Input 3: aaabba Output 3: String not accepted
Input 4: aaab Output 4: String not accepted
Input 5: abcd Output 5: Invalid token
Program-2:
Programs using Lex tool
a) Identification of Vowels and Consonants
CODE:
%option noyywrap
%%
[aeiouAEIOU] printf("%s is vowel\n",yytext);
[a-zA-Z] printf("%s is consonant\n",yytext);
. printf("%s is invalid lexeme\n",yytext);
%%
main()
{ yylex(); }

Output:

b) Count number of vowels and consonants

CODE:
%option noyywrap
%{
int v=0,c=0;
%}
%%
[aeiouAEIOU] ++v;
[a-zA-Z] ++c;
.
%%
main()
{
yylex();
printf(" no. of vowels=%d \n no.of consonants=%d",v,c);
}
OUTPUT:
 c) Count the number of Lines in given input
CODE:
%option noyywrap
%{
int num_lines=0;
%}
%%
\n ++num_lines;
.
%%
main()
{
yylex();
printf("no. of lines=%d",num_lines);
}
OUTPUT:
 d) Recognize strings ending with 00
CODE:
%option noyywrap
%%
[0-9]*00 printf("string accepted\n");
[0-9]* printf("string rejected\n");
.* printf("invalid string\n");
%%
main()
{ yylex(); }
OUTPUT:

e) Recognize a string with three consecutive 0’s

CODE:
%option noyywrap
%%
[0-9]*000[0-9]* printf("string accepted\n");
[0-9]* printf("string rejected\n");
.* printf("invalid string\n");
%%
main()
{ yylex(); }

OUTPUT:
Program 3:
Implement lexical analyzer using C
CODE:
#include<stdio.h>
#include<ctype.h>
#include<string.h>
char
keyword[24][30]={"int","while","break","for","do","if","float","char","switch","double","sho
rt","long","unsigned","sizeof",
"else","register","extern","static","auto","case","break","volatile","enum","typedef"};

int check_keyword(char s[]) {

for(int i=0;i<24;++i)
if(strcmp(s,keyword[i])==0)
return 1;
return 0;
}
void store_symb_tab(char id[], char symb_tab[][30]) {
int i;
for(i=0; strcmp(symb_tab[i],"")&&i<20;++i)
if(!strcmp(symb_tab[i],id))
return;
if(i==20)
{
printf("Overflow!");
return;
}
strcpy(symb_tab[i],id);
}
int main()
{
FILE *fp1,*fp2;
char c,id[30], num[10];
int state=0,i=0,j=0;
fp1=fopen("in.txt","r");
fp2=fopen("out.txt","w");
char symb_tab[20][30];
for(int i=0;i<20;++i) {
strcpy(symb_tab[i],"");
}
while((c=fgetc(fp1))!=EOF) {
switch(state) {
case 0:
if(isalpha(c)||c=='_') {
state=1;
 id[i++]=c;
}
else if(isdigit(c))
{
state=3;
num[j++]=c;
}
else if(c=='<' || c=='>') {
state=5;
}
else if(c=='=' || c=='!') {
state=8;
}
else if(c=='/') {
state=10;
}
else if(c==' ' || c=='\t' || c=='\n' || c=='\r') {
state=0;
}
else {
fprintf(fp2,"\n%c",c);
}
break;
case 1:
if(isalnum(c)||c=='_') {
state=1;
id[i++]=c;
}
else {
id[i]='\0';
if(check_keyword(id)) {
fprintf(fp2," \n%s : keyword ",id);
}
else {
fprintf(fp2,"\n%s : identifier",id);
store_symb_tab(id,symb_tab);
}
state=0;
i=0;
ungetc(c,fp1);
}
break;
case 3:
if(isdigit(c)) {
num[j++]=c;
state=3;
}
 else {
num[j]='\0';
fprintf(fp2," \n%s: number",num);
state=0;
j=0;
ungetc(c,fp1);
}
break;
case 5:
if(c=='=') {
fseek(fp1,-2,SEEK_CUR);
c=fgetc(fp1);
if(c=='<') {
fprintf(fp2,"\n<=: relational operator Less Than
or Equal To");
}
else {
fprintf(fp2,"\n<=: relational operator Greater
Than or Equal To");
}
c=fgetc(fp1);
state=0;
}
else {
fseek(fp1,-2,SEEK_CUR);
c=fgetc(fp1);
if(c=='<') {
fprintf(fp2,"\n<: relational operator Less Than");
}
else {
fprintf(fp2,"\n>: relational operator Greater
Than");
}
state=0;
}
break;
case 8:
if(c=='=') {
fseek(fp1,-2,SEEK_CUR);
c=fgetc(fp1);
if(c=='=') {
fprintf(fp2,"\n==: relational operator Equal
To");
}
else {
fprintf(fp2,"\n!=: relational operator Not Equal
To");
 }
c=fgetc(fp1);
state=0;
}
else {
fprintf(fp2,"\n!");
ungetc(c,fp1);
state=0;
}
break;
case 10:
if(c=='*') {
state=11;
}
else {
fprintf(fp2,"\n/%c: invalid lexeme",c);
state=0;
}
break;
case 11:
if(c=='*') {
state=12;
}
break;
case 12:
if(c=='*') {
state=12;
}
else if(c=='/') {
state=0;
}
else {
state=11;
}
break;
}
}
if(state==11) {
fprintf(fp2,"\nComment Not Closed");
}
fclose(fp1);
fclose(fp2);
return 0;
}

INPUT FILE:
OUTPUT FILE:

Program 4:
Implement lexical analyzer using LEX
CODE:
%option noyywrap
digit [+-]?[0-9]+
id [a-zA-Z_][a-zA-Z0-9_]*
num [+-]?[0-9]*\.[0-9]+
exp {digit}[e]{digit}
keywords
"int"|"char"|"float"|"void"|"double"|"if"|"else"|"for"|"while"|"do"|"switch"|"case"|"bre
ak"|"unsigned"|"main"
%{
#include<string.h>
char symb_tab[20][30];
void store_symb_tab(char* id);
%}
%%
"/*"([^*]|\*+[^*/])*\*+"/" fprintf(yyout,"multi-line comment\n"); //[^*] recognises
anything except *; "/*"(.|\n)*"*/" won't work until entire input is given.
"//".*\n fprintf(yyout,"single-line comment\n");
{keywords} fprintf(yyout,"%s: keyword\n",yytext);
"<=" fprintf(yyout,"%s: Relational operator LE\n",yytext);
"<" fprintf(yyout,"%s: Relational operator LT\n",yytext);
">=" fprintf(yyout,"%s: Relational operator GE\n",yytext);
">" fprintf(yyout,"%s: Relational operator GT\n",yytext);
"==" fprintf(yyout,"%s: Relational operator EQ\n",yytext);
"!=" fprintf(yyout,"%s: Relational operator NE\n",yytext);
"=" fprintf(yyout,"%s: Assignment operator\n",yytext);
{exp} fprintf(yyout,"%s: exponential float\n",yytext);
{num} fprintf(yyout,"%s: fractional float\n",yytext);
{digit} fprintf(yyout,"%s: digit\n",yytext);
{id} { fprintf(yyout,"%s: identifier\n",yytext); store_symb_tab(yytext); }
" "|\n
. fprintf(yyout,"%s: \n",yytext);
%%
main(int a,char **s) // command run line: a in.txt
{
yyin=fopen("in.txt","r");
yyout=fopen("out.txt","w");
yylex();
fprintf(yyout,"\nSymbol table:\n");
int i=0;
for(;strcmp(symb_tab[i],"")&&i<20;++i)
fprintf(yyout,"\n%d. %s",i+1,symb_tab[i]);
}
void store_symb_tab(char* id)
{
int i;
for(i=0; strcmp(symb_tab[i],"")&&i<20;++i)
if(!strcmp(symb_tab[i],id))
return;
if(i==20)
{ fprintf(yyout,"Overflow!\n"); return;} // create linked list to avoid this
strcpy(symb_tab[i],id); //adds id to symb_tab
}
INPUT FILE:

OUTPUT FILE:
Program 5:
Implementation of Recursive Descent Parser
E → TE’
E’→ +TE’ | ͼ
T → FT’
T’→ *FT’ | ͼ
F → (E) | i
CODE:
#include<stdio.h>
#include<string.h>
int E(),Edash(),T(),Tdash(),F();
char *ip;
char string[50];
int main()
{
printf("Enter the string:\n");
scanf("%s",string);
ip=string;
printf("\n\nInput\tAction\n--------------------------------\n");
if(E() && *ip=='\0'){
printf("\n--------------------------------\n");
printf("\n String is successfully parsed\n");
}
else{
printf("\n--------------------------------\n");
printf("Error in parsing String\n");
}
}
int E()
{
printf("%s\tE->TE' \n",ip);
if(T())
{
if(Edash())
{
return 1;
}
else
return 0;
}
else
return 0;
}
int Edash()
{
if(*ip=='+')
{
printf("%s\tE'->+TE' \n",ip);
ip++;
if(T())
{
if(Edash())
{
return 1;
}
else
return 0;
}
else
return 0;
}
else
{
printf("%s\tE'->^ \n",ip);
return 1;
}
}
int T()
{
printf("%s\tT->FT' \n",ip);
if(F())
{
if(Tdash())
{
return 1;
 }
else
return 0;
}
else
return 0;
}
int Tdash()
{
if(*ip=='*')
{
printf("%s\tT'->*FT' \n",ip);
ip++;
if(F())
{
if(Tdash())
{
return 1;
}
else
return 0;
}
else
return 0;
}
else
{
printf("%s\tT'->^ \n",ip);
return 1;
}
}
int F()
{
if(*ip=='(')
{
printf("%s\tF->(E) \n",ip);
ip++;
if(E())
{
if(*ip==')')
{
ip++;
return 1;
}
else
return 0;
}
 else
return 0;
}
else if(*ip=='i')
{
ip++;
printf("%s\tF->id \n",ip);
return 1;
}
else
return 0;
}

OUTPUT:

Program 6:
Computation of First and Follow
CODE:
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
int n,m=0,p,i=0,j=0;
char a[10][10],f[10];
void follow(char c);
void first(char c);
int main(){
int i,z;
char c,ch;

printf("Enter the no of prooductions:\n");

scanf("%d",&n);
printf("Enter the productions:\n");
for(i=0;i<n;i++)
scanf("%s%c",a[i],&ch);
do{
m=0;
printf("Enter the elements whose fisrt & follow is to be found:");
scanf("%c",&c);
first(c);
printf("First(%c)={",c);
for(i=0;i<m;i++)
printf("%c",f[i]);
printf("}\n");
strcpy(f," ");

m=0;
follow(c);
 printf("Follow(%c)={",c);
for(i=0;i<m;i++)
printf("%c",f[i]);
printf("}\n");
printf("Continue(0/1)?");
scanf("%d%c",&z,&ch);
}while(z==1);
return(0);
}
void first(char c)
{
int k;
if(!isupper(c))
f[m++]=c;
for(k=0;k<n;k++){
if(a[k][0]==c){
if(a[k][2]=='$')
follow(a[k][0]);
else if(islower(a[k][2]))
f[m++]=a[k][2];
else
first(a[k][2]);
}
}
}
void follow(char c)
{
if(a[0][0]==c)
f[m++]='$';
 for(i=0;i<n;i++){
for(j=2;j<strlen(a[i]);j++){
if(a[i][j]==c){
if(a[i][j+1]!='\0')
first(a[i][j+1]);
if(a[i][j+1]=='\0' && c!=a[i][0])
follow(a[i][0]);
}
}
}
}
OUTPUT:

Program 7:
Implementation of Predictive Parser
E → TE’
E’→ +TE’ | ε
T → FT’
T’→ *FT’ | ε
F → (E) | d

CODE:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
int i=0,top=0;
char stack[20],ip[20];
void push(char c)
{
if (top>=20)
printf("Stack Overflow");
else
stack[top++]=c;
}
void pop(void)
{
if(top<0)
printf("Stack underflow");
else
top--;
}
void error(void)
{
printf("\n\nSyntax Error!!!! String is invalid\n");
exit(0);
}
int main()
{
int n;
printf("The given grammar is\n\n");
printf("E -> TE'\n");
printf("E'-> +TE' | epsilon \n");
printf("T ->FT' \n");
printf("T'->*FT' | epsilon \n");
printf("F ->(E) | d \n\n");
printf("Enter the string to be parsed:\n");
scanf("%s",ip);
n=strlen(ip);
ip[n]='$';
ip[n+1]='\0';
push('$');
push('E');
while(ip[i]!='\0')
{
if(ip[i]=='$' && stack[top-1]=='$')
{
printf("\n\n Successful parsing of string \n");
return 1;
}
else if(ip[i]==stack[top-1])
{
printf("\nmatch of %c ",ip[i]);
i++;pop();
}
else
{
if(stack[top-1]=='E' && (ip[i]=='d' || ip[i]=='('))
{
printf(" \n E -> TE'");
pop();
push('A');//E'
push('T');
}
else if(stack[top-1]=='A' && ip[i]=='+') //E'
{
printf("\n E' ->+TE'");
pop();push('A');push('T');push('+');
}
else if(stack[top-1]=='A' && (ip[i]==')' || ip[i]=='$'))
{
printf("\n E' -> epsilon");
pop();
}
else if(stack[top-1]=='T' && (ip[i]=='d' || ip[i]=='('))
{
printf("\n T ->FT'");
pop();push('B');push('F'); //B is T'
}
else if(stack[top-1]=='B' && ip[i]=='*')
{
printf("\n T' ->*FT'");
pop();push('B');push('F');push('*');
}
 else if(stack[top-1]=='B' && (ip[i]=='+' || ip[i]==')'|| ip[i]=='$'))
{
printf("\n T' ->epsilon");
pop();
}
else if(stack[top-1]=='F' && ip[i]=='d')
{
printf("\n F ->d");
pop();push('d');
}
else if(stack[top-1]=='F' && ip[i]=='(')
{
printf("\n F ->(E)");
pop();push(')');push('E');push('(');
}
else
error();
}
}
}
OUTPUT:
Program 8:
Implementation of Shift reduce parser
E→E+E
E→E*E
E→(E)
E→d
CODE:

#include<stdio.h>

#include<stdlib.h>
char stack[100]="\0", input[100], *ip;

int top=-1;

void push(char c)

top++;

stack[top]=c;

void pop()

stack[top]='\0';

top--;

void display()

printf("\n%s\t%s\t",stack,ip);

void main()

printf("E->E+E\n");

printf("E->E*E\n");

printf("E->(E)\n");

printf("E->d\n");

printf("Enter the input string followed by $ \n");

scanf("%s",input);

ip=input;

push('$');

printf("STACK\t BUFFER \t ACTION\n");

printf("-----\t ------- \t ------\n");

display();

if(stack[top]=='$' && *ip=='$')

printf("Null Input");

exit(0);

do

if((stack[top]=='E' && stack[top-1]=='$') && (*(ip)=='$'))

display();

printf(" Valid\n\n\n");

break;

if(stack[top]=='$')

push(*ip);

ip++;

printf("Shift");
}

else if(stack[top]=='d')

display();

pop();

push('E');

printf("Reduce E->d");

else if(stack[top]=='E' && stack[top-1]=='+' && stack[top-2]=='E'&& *ip!='*')

display();

pop();

pop();

pop();

push('E');

printf("Reduce E->E+E");

else if(stack[top]=='E' && stack[top-1]=='*' && stack[top-2]=='E')

display();

pop();

pop();

pop();
 push('E');

printf("Reduce E->E*E");

else if(stack[top]==')' && stack[top-1]=='E' && stack[top-2]=='(')

display();

pop();

pop();

pop();

push('E');

printf("Reduce E->(E)");

else if(*ip=='$')

printf(" Invalid\n\n\n");

break;

else

display();

push(*ip);

ip++;

printf("shift");
 }

}while(1);

OUTPUT:

Program 9:
Implementation of LALR parser using YACC
E → E+T |T
E’→ T*F | F
F → (E) | d
LEX-CODE:
%option noyywrap
%{
#include "1.tab.h"
%}

%%
[0-9]+ {yylval=atoi(yytext);
return NUMBER;
}
[\t] ;
\n return 0;
. return yytext[0];
%%
YACC-CODE:
%{
#include<stdio.h>
%}
%token NUMBER
%%
S:E { printf("The result is %d\n",$1);}
;
E:E'+'T { $$ = $1 + $3; }
|T { $$ = $1;}
;
T:T'*'F { $$ = $1*$3; }
|F { $$ = $1;}
;
F:'('E')' { $$ = $2;}
|NUMBER { $$ = $1;}
;
%%
main()
{
yyparse();
}
void yyerror(char* s)
{
printf("Error %s",s);
}
OUTPUT:

Program 10:
YACC Specification for a simple desk calculator
LEX-CODE:
%{
#include<stdio.h>
#include "y.tab.h"
extern int yylval;
%}

%%
[0-9]+ {
yylval=atoi(yytext);
return NUMBER;

}
[\t] ;

[\n] return 0;
. return yytext[0];
%%
int yywrap()
{
return 1;
}
YACC CODE:
%{
#include<stdio.h>
int flag=0;
%}

%token NUMBER

%left '+' '-'

%left '*' '/' '%'

%left '(' ')'

%%
ArithmeticExpression: E{

printf("\nResult=%d\n", $$);

return 0;

};
E:E'+'E {$$=$1+$3;}

|E'-'E {$$=$1-$3;}

|E'*'E {$$=$1*$3;}

|E'/'E {$$=$1/$3;}

|E'%'E {$$=$1%$3;}

|'('E')' {$$=$2;}

| NUMBER {$$=$1;}

%%

void main()
{
printf("\nEnter Any Arithmetic Expression which can have operations
Addition,Subtraction, Multiplication, Division,Modulus and Round brackets:\n");
 yyparse();
if(flag==0)
printf("\nEntered arithmetic expression is Valid\n\n");
}

void yyerror()
{
printf("\nEntered arithmetic expression is Invalid\n\n");
flag=1;
}
OUTPUT: