COMPILER DESIGN LAB PROGRAMS

Program-1:
Aim: Implementation of symbol table.
Algorithm:
Step1: Start the program for performing insert, display, delete, search and modify option in
symbol table
Step2: Define the structure of the Symbol Table
Step3: Enter the choice for performing the operations in the symbol Table
Step4: If the entered choice is 1, search the symbol table for the symbol to be inserted. If the
symbol is
already present, it displays “Duplicate Symbol”. Else, insert the symbol and the
corresponding address in
the symbol table.
Step5: If the entered choice is 2, the symbols present in the symbol table are displayed.
Step6: If the entered choice is 3, the symbol to be deleted is searched in the symbol table.
Step7: If it is not found in the symbol table it displays “Label Not found”. Else, the symbol
is deleted.
Step8: If the entered choice is 5, the symbol to be modified is searched in the symbol table.
Program:
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
void main()
{
int i=0,j=0,x=0,n;
void *p,*add[5];
char ch,srch,b[15],d[15],c;
printf("Expression terminated by $:");
while((c=getchar())!='$')
{
b[i]=c;
i++;
}
n=i-1;
printf("Given Expression:");
i=0;
while(i<=n)
{
printf("%c",b[i]);
i++;
}
printf("\n Symbol Table\n");
printf("Symbol \t addr \t type");
while(j<=n)
{
c=b[j];
if(isalpha(toascii(c)))
{
p=malloc(c);
add[x]=p;
d[x]=c;
printf("\n%c \t %d \t identifier\n",c,p);
x++;
j++;
}
else
{
ch=c;
if(ch=='+'||ch=='-'||ch=='*'||ch=='=')
{
p=malloc(ch);
add[x]=p;
d[x]=ch;
printf("\n %c \t %d \t operator\n",ch,p);
x++;
j++;
}}}}
Output:

Program-2:
Aim:Develop a lexical analyzer to recognize a few patterns inc (ex. Identifiers, constants,
comments,operators etc.)
Algorithm:
Step1: Start the program.
Step2: Declare all the variables and file pointers.
Step3: Display the input program.
Step4: Separate the keyword in the program and display it.
Step5: Display the header files of the input program
Step6: Separate the operators of the input program and display it.
Step7: Print the punctuation marks.
Step8: Print the constant that are present in input program.
Step9: Print the identifiers of the input program.
Program:
#include<string.h>
#include<ctype.h>
#include<stdio.h>
#include<stdlib.h>
void keyword(char str[10])
{
if(strcmp("for",str)==0||strcmp("while",str)==0||strcmp("do",str)==0||strcmp("int",str)==0||str
cmp("float",str)==0||strcmp("char",str)==0||strcmp("double",str)==0||strcmp("printf",str)==0||
strcmp("switch",str)==0||strcmp("case",str)==0)
printf("\n%s is a keyword",str);
else
printf("\n%s is an identifier",str);
}
void main()
{
FILE *f1,*f2,*f3;
char c,str[10],st1[10];
int num[100],lineno=0,tokenvalue=0,i=0,j=0,k=0;
f1=fopen("input","r");
f2=fopen("identifier","w");
f3=fopen("specialchar","w");
while((c=getc(f1))!=EOF)
{
if(isdigit(c))
{
tokenvalue=c-'0';
c=getc(f1);
while(isdigit(c))
{
tokenvalue*=10+c-'0';
c=getc(f1);
}
num[i++]=tokenvalue;
 ungetc(c,f1);
}
else
if(isalpha(c))
{
putc(c,f2);
c=getc(f1);
while(isdigit(c)||isalpha(c)||c=='_'||c=='$')
{
putc(c,f2);
c=getc(f1);
}
putc(' ',f2);
ungetc(c,f1);
}
else
if(c==' '||c=='\t')
printf(" ");
else
if(c=='\n')
lineno++;
else
putc(c,f3);
}
fclose(f2);
fclose(f3);
fclose(f1);
printf("\n the no's in the program are:");
for(j=0;j<i;j++)
printf("\t%d",num[j]);
printf("\n");
f2=fopen("identifier","r");
k=0;
printf("the keywords and identifier are:");
while((c=getc(f2))!=EOF)
if(c!=' ')
str[k++]=c;
else
{
str[k]='\0';
keyword(str);
k=0;
}
fclose(f2);
f3=fopen("specialchar","r");
printf("\n Special Characters are");
 while((c=getc(f3))!=EOF)
printf("\t%c",c);
printf("\n");
fclose(f3);
printf("Total no of lines are:%d",lineno);
}
Output:

Program-3:
Aim: Implementation of lexical analyzer using lex tool.
Algorithm:
Step1: Lex program contains three sections: definitions, rules, and user subroutines. Each
section must be separated from the others by a line containing only the delimiter, %%. The
format is as follows: definitions %% rules %% user_subroutines.
Step2: In definition section, the variables make up the left column, and their definitions make
up the right column. Any C statements should be enclosed in %{..}%. Identifier is defined
such that the first letter of an identifier is alphabet and remaining letters are alphanumeric.
Step3: In rules section, the left column contains the pattern to be recognized in an input file to
yylex(). The right column contains the C program fragment executed when that pattern is
recognized. The various patterns are keywords, operators, new line character, number, string,
identifier, beginning and end of block, comment statements, preprocessor directive statements
etc.
Step4: Each pattern may have a corresponding action, that is, a fragment of C source code to
execute when the pattern is matched.
Step5: When yylex() matches a string in the input stream, it copies the matched text to an
external character array, yytext, before it executes any actions in the rules section.
Step6: In user subroutine section, main routine calls yylex(). yywrap() is used to get more
input.
Step7: The lex command uses the rules and actions contained in file to generate a program,
[Link].c, which can be compiled with the cc command. That program can then receive input,
break the input into the logical pieces defined by the rules in file, and run program fragments
contained in the actions in file.
Program:
%{
int COMMENT=0;
%}
identifier [a-zA-Z][a-zA-Z0-9]*
%%
#.* {printf("\n%s is a preprocessor directive",yytext);}
int |
float |
char |
double |
while |
for |
struct |
typedef |
do |
if |
break |
continue |
void |
switch |
return |
else |
goto {printf("\n\t%s is a keyword",yytext);}
"/*" {COMMENT=1;}{printf("\n\t %s is a COMMENT",yytext);}
{identifier}\( {if(!COMMENT)printf("\nFUNCTION \n\t%s",yytext);}
\{ {if(!COMMENT)printf("\n BLOCK BEGINS");}
\} {if(!COMMENT)printf("BLOCK ENDS ");}
{identifier}(\[[0-9]*\])? {if(!COMMENT) printf("\n %s IDENTIFIER",yytext);}
\".*\" {if(!COMMENT)printf("\n\t %s is a STRING",yytext);}
[0-9]+ {if(!COMMENT) printf("\n %s is a NUMBER
",yytext);}
\)(\:)? {if(!COMMENT)printf("\n\t");ECHO;printf("\n");}
\( ECHO;
= {if(!COMMENT)printf("\n\t %s is an ASSIGNMENT OPERATOR",yytext);}
\<= |
\>= |
\< |
== |
\> {if(!COMMENT) printf("\n\t%s is a RELATIONAL OPERATOR",yytext);}
%%
int main(int argc, char **argv)
{
FILE *file;
file=fopen("var.c","r"); if(!
file)
{
printf("could not open the file");
exit(0);
}
yyin=file;
yylex();
printf("\n");
return(0);
}
int yywrap()
{
return(1);
}
Input:
#include<stdio.h>
#include<conio.h>
void main()
{
int a,b,c;
a=1;
b=2;
c=a+b; printf("Sum:
%d",c);
}
Output:

Program-4:
Aim: Generate yacc specification for a few syntactic categories.
a) Program to recognize a valid arithmetic expression that uses operator +,-, * and /.
Algorithm:
Step1: Start the program.
Step2: Reading an expression .
Step3: Checking the validating of the given expression according to the rule using yacc.
Step4: Using expression rule print the result of the given values
Step5: Stop the program.
Program:
LEX PART:
%{
#include "[Link].h"
%}
%%
[a-zA-Z_][a-zA-Z_0-9]* return id;
[0-9]+(\.[0-9]*)? return
num; [+/*] return op;
. return yytext[0];
\n return 0;
%%
int yywrap()
{
return 1;
}
YACC PART:
%{
#include<stdio.h>
int valid=1;
%}
%token num id op
%%
start : id '=' s ';'
s: id x
| num x
| '-' num x
| '(' s ')' x
;
x: op s
| '-' s
|
;
%%
int yyerror()
{
 valid=0;
printf("\nInvalid expression!\n");
return 0;
}
int main()
{
printf("\nEnter the expression:\n");
yyparse();
if(valid)
{
printf("\nValid expression!\n");
}
}
Output:

b) Program to recognize a valid variable which starts with a letter followed by any
number of letter or digits.
Program:
LEX PART:
%{
#include "[Link].h"
%}
%%
[a-zA-Z_][a-zA-Z_0-9]* return letter;
[0-9] return digit;
. return yytext[0];
\n return 0;
%%
int yywrap()
{
return 1;
}
YACC PART:
%{
#include<stdio.h>
int valid=1;
%}
%token digit letter
%%
start : letter s
s: letter s
| digit s
|
;
%%
int yyerror()
{
printf("\nIts not a identifier!\n");
valid=0;
 return 0;
}
int main()
{
printf("\nEnter a name to tested for identifier ");
yyparse();
if(valid)
{
printf("\nIt is a identifier!\n");
}
}
Output:

c) Implementation of calculator using lex and yacc.

Program:
%{
int op = 0,i;
float a, b;
%}
dig [0-9]+|([0-9]*)"."([0-9]+)
add "+"
sub "-"
mul "*"
div "/"
pow "^"
ln \n
%%
{dig} {digi();}
{add} {op=1;}
{sub} {op=2;}
{mul} {op=3;}
{div} {op=4;}
{pow} {op=5;}
{ln} {printf("\n The Answer :%f\n\n",a);
}
%%
digi()
{
if(op==0)
a=atof(yytext);
else
{
b=atof(yytext);
switch(op)
{
case 1:a=a+b;
break;
case 2:a=a-b;
break;
case 3:a=a*b;
break;
case 4:a=a/b;
break;
case 5:for(i=a;b>1;b--)
a=a*i;
break;
}
op=0;
}
}
main(int argv,char *argc[])
{
yylex();
}
yywrap()
{
return 1;
}
Output:
5+5
The Answer :10.000000
3-3
The Answer :0.000000
8/8
The Answer :1.000000
6*22
The Answer :132.000000
Program 5:
Aim: Convert the bnf rules into yacc form and write code to generate abstract syntax tree.
Algorithm:
Step1: Reading an expression.
Step2: Calculate the value of given expression
Step3: Display the value of the nodes based on the precedence.
Step4: Using expression rule print the result of the given values
Program:
LEX PART:
%{
#include"[Link].h"
#include<stdio.h>
#include<string.h>
int LineNo=1;
%}
identifier [a-zA-Z][_a-zA-Z0-9]*
number [0-9]+|([0-9]*\.[0-9]+)
%%
main\(\) return MAIN;
if return IF;
else return ELSE;
while return WHILE;
int |
char |
float return TYPE;
{identifier} {strcpy([Link],yytext);
return VAR;}
{number} {strcpy([Link],yytext);
return NUM;}
\< |
\> |
\>= |
\<= |
== {strcpy([Link],yytext);
return RELOP;}
[ \t] ;
\n LineNo++;
. return yytext[0];
%%
YACC PART:
%{
#include<string.h>
#include<stdio.h>
struct quad
{
char op[5];
char arg1[10];
char arg2[10];
char result[10];
}QUAD[30];
struct stack
{
int items[100];
int top;
}stk;
int Index=0,tIndex=0,StNo,Ind,tInd;
extern int LineNo;
%}
%union
{
char var[10];
}
%token <var> NUM VAR RELOP
%token MAIN IF ELSE WHILE TYPE
%type <var> EXPR ASSIGNMENT CONDITION IFST ELSEST WHILELOOP
%left '-' '+'
%left '*' '/'
%%
PROGRAM : MAIN BLOCK
;
BLOCK: '{' CODE '}'
;
CODE: BLOCK
| STATEMENT CODE
| STATEMENT
;
STATEMENT: DESCT ';'
| ASSIGNMENT ';'
| CONDST
| WHILEST
;
DESCT: TYPE VARLIST
;
VARLIST: VAR ',' VARLIST
| VAR
;
ASSIGNMENT: VAR '=' EXPR{
strcpy(QUAD[Index].op,"=");
strcpy(QUAD[Index].arg1,$3);
strcpy(QUAD[Index].arg2,"");
strcpy(QUAD[Index].result,$1);
strcpy($$,QUAD[Index++].result);
}
;
EXPR: EXPR '+' EXPR {AddQuadruple("+",$1,$3,$$);}
| EXPR '-' EXPR {AddQuadruple("-",$1,$3,$$);}
| EXPR '*' EXPR {AddQuadruple("*",$1,$3,$$);}
| EXPR '/' EXPR {AddQuadruple("/",$1,$3,$$);}
| '-' EXPR {AddQuadruple("UMIN",$2,"",$$);}
| '(' EXPR ')' {strcpy($$,$2);}
| VAR
| NUM
;
CONDST: IFST{
Ind=pop();
sprintf(QUAD[Ind].result,"%d",Index);
Ind=pop();
sprintf(QUAD[Ind].result,"%d",Index);
}
| IFST ELSEST
;
IFST: IF '(' CONDITION ')' {
strcpy(QUAD[Index].op,"==");
strcpy(QUAD[Index].arg1,$3);
strcpy(QUAD[Index].arg2,"FALSE");
strcpy(QUAD[Index].result,"-1");
push(Index);
Index++;
}
BLOCK { strcpy(QUAD[Index].op,"GOTO"); strcpy(QUAD[Index].arg1,"");
strcpy(QUAD[Index].arg2,"");
strcpy(QUAD[Index].result,"-1");
push(Index);
Index++;
};
ELSEST: ELSE{
tInd=pop();
Ind=pop();
push(tInd);
sprintf(QUAD[Ind].result,"%d",Index);
}
BLOCK{
Ind=pop();
sprintf(QUAD[Ind].result,"%d",Index);
};
CONDITION: VAR RELOP VAR {AddQuadruple($2,$1,$3,$$);
StNo=Index-1;
}
| VAR
| NUM
;
WHILEST: WHILELOOP{
Ind=pop();
sprintf(QUAD[Ind].result,"%d",StNo);
Ind=pop();
sprintf(QUAD[Ind].result,"%d",Index);
}
;
WHILELOOP: WHILE'('CONDITION ')' {
strcpy(QUAD[Index].op,"==");
strcpy(QUAD[Index].arg1,$3);
strcpy(QUAD[Index].arg2,"FALSE");
strcpy(QUAD[Index].result,"-1");
push(Index);
Index++;
}
BLOCK {
strcpy(QUAD[Index].op,"GOTO");
strcpy(QUAD[Index].arg1,"");
strcpy(QUAD[Index].arg2,"");
strcpy(QUAD[Index].result,"-1");
push(Index);
Index++;
}
;
%%
extern FILE *yyin;
int main(int argc,char *argv[])
{
FILE *fp;
int i;
if(argc>1)
{
fp=fopen(argv[1],"r");
if(!fp)
{
printf("\n File not found");
exit(0);
}
yyin=fp;
}
yyparse();
printf("\n\n\t\t ----------------------------""\n\t\t Pos Operator \tArg1 \tArg2 \tResult" "\n\t\
t------");
for(i=0;i<Index;i++)
{
printf("\n\t\t %d\t
%s\t%s\t%s\t%s",i,QUAD[i].op,QUAD[i].arg1,QUAD[i].arg2,QUAD[i].result);
}
printf("\n\t\t ");
printf("\n\n"); return 0; }
void push(int data)
{ [Link]++;
if([Link]==100)
{
printf("\n Stack overflow\n");
exit(0);
}
[Link][[Link]]=data;
}
int pop()
{
int data;
if([Link]==-1)
{
printf("\n Stack underflow\n");
exit(0);
}
data=[Link][[Link]--];
return data;
}
void AddQuadruple(char op[5],char arg1[10],char arg2[10],char result[10])
{
strcpy(QUAD[Index].op,op);
strcpy(QUAD[Index].arg1,arg1);
strcpy(QUAD[Index].arg2,arg2);
sprintf(QUAD[Index].result,"t%d",tIndex++);
strcpy(result,QUAD[Index++].result);
}
yyerror()
{
printf("\n Error on line no:%d",LineNo);
}
INPUT:
main()
{
int a,b,c;
if(a<b)
{
a=a+b;
}
while(a<b)
{
a=a+b;
}
if(a<=b)
{
c=a-b;
}
else
{
c=a+b;
}}
Output:

Program-6:
Aim: Implement type
checking Algorithm:
Step1: Track the global scope type information (e.g. classes and their members)
Step2: Determine the type of expressions recursively, i.e. bottom-up, passing the resulting
types upwards.
Step3: If type found correct, do the operation
Step4: Type mismatches, semantic error will be notified
Program:
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n,i,k,flag=0;
char vari[15],typ[15],b[15],c;
printf("Enter the number of variables:");
scanf(" %d",&n);
for(i=0;i<n;i++)
{
printf("Enter the variable[%d]:",i);
scanf(" %c",&vari[i]);
printf("Enter the variable-type[%d](float-f,int-i):",i);
scanf(" %c",&typ[i]);
if(typ[i]=='f')
flag=1;
}
printf("Enter the Expression(end with $):");
i=0;
getchar();
while((c=getchar())!='$')
{
b[i]=c;
i++; }
k=i; for(i=0;i<k;i+
+)
{
if(b[i]=='/')
{
flag=1;
break; } }
for(i=0;i<n;i++)
{
if(b[0]==vari[i])
{
if(flag==1)
{
if(typ[i]=='f')
{ printf("\nthe datatype is correctly defined..!\n");
break; }
else
{ printf("Identifier %c must be a float type..!\n",vari[i]);
break; } }
else
{ printf("\nthe datatype is correctly defined..!\n");
break; } }
}
return 0;
}
Output:

Program-7:
Aim: Implement any one storage allocation strategies (heap, stack, static)
Algorithm:
Step1: Initially check whether the stack is empty
Step2: Insert an element into the stack using push operation
Step3: Insert more elements onto the stack until stack becomes full
Step4: Delete an element from the stack using pop operation
Step5: Display the elements in the stack
Step6: Top the stack element will be displayed
Program:
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
typedef struct Heap
{
int data;
struct Heap *next;
}
node;
node *create();
void main()
{
int
choice,val;
char ans;
node *head;
void display(node *);
node *search(node *,int);
node *insert(node *);
void dele(node **);
head=NULL;
do
{
printf("\nprogram to perform various operations on heap using dynamic memory
management");
printf("\[Link]"); printf("\
[Link]");
printf("\[Link] an element in a list");
printf("\[Link] an element from list");
printf("\[Link]");
printf("\nenter your chioce(1-5)");
scanf("%d",&choice);
switch(choice)
{
case 1:head=create();
break;
case 2:display(head);
break;
case 3:head=insert(head);
break;
case 4:dele(&head);
break;
case 5:exit(0);
default:
printf("invalid choice,try again");
}
}
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);
New=get_node();
if(New==NULL)
printf("\nmemory is not allocated");
New->data=val;
if(flag==TRUE)
{
head=New;
temp=head;
flag=FALSE;
}
else
{
temp->next=New;
temp=New;
}
printf("\ndo you want to enter more elements?(y/n)");
}
while(ans=='y');
printf("\nthe list is created\n");
return head;
}
node *get_node()
{
node *temp;
temp=(node*)malloc(sizeof(node));
temp->next=NULL;
return temp;
}
void display(node *head)
{
node *temp;
temp=head;
if(temp==NULL)
{
printf("\nthe list is empty\n");
return;
}
while(temp!=NULL)
{
printf("%d->",temp->data);
temp=temp->next;
}
printf("NULL");
}
node *search(node *head,int key)
{
node *temp;
int found;
temp=head;
if(temp==NULL)
{
printf("the linked list is empty\n");
return NULL;
}
found=FALSE;
while(temp!=NULL && found==FALSE)
{
if(temp->data!=key)
temp=temp->next;
else
found=TRUE;
}
if(found==TRUE)
{
printf("\nthe element is present in the list\n");
return temp;
}
else
{
printf("the element is not present in the list\n");
return NULL;
}
}
node *insert(node *head)
{
int choice;
node *insert_head(node *);
void insert_after(node *);
void insert_last(node *);
printf("[Link] a node as a head node");
printf("[Link] a node as a head node");
printf("[Link] a node at intermediate position in t6he list");
printf("\nenter your choice for insertion of node:");
scanf("%d",&choice);
switch(choice)
{
case 1:head=insert_head(head);
break;
case 2:insert_last(head);
break;
case 3:insert_after(head);
break;
}
return head;
}
node *insert_head(node *head)
{
node *New,*temp;
New=get_node();
printf("\nEnter 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;
}
void insert_last(node *head)
{
node *New,*temp;
New=get_node();
printf("\nenter 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;
}
}
void insert_after(node *head)
{
int key;
node *New,*temp;
New=get_node();
printf("\nenter the elements which you want to insert");
scanf("%d",&New->data);
if(head==NULL)
{
head=New;
}
else
{
printf("\enter the element which you want to insert the node");
scanf("%d",&key);
temp=head;
do
{
if(temp->data==key)
{
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;
while(temp!=NULL && ! flag)
{
if(temp->data!=val)
{
prev=temp;
temp=temp->next;
}
else
flag=TRUE;
}
if(flag)
return prev;
else
return NULL;
}
void dele(node **head)
{
node *temp,*prev;
int key;
temp=*head;
if(temp==NULL)
{
printf("\nthe list is empty\n");
return;
}
printf("\nenter the element you want to delete:");
scanf("%d",&key);
temp=search(*head,key);
if(temp!=NULL)
{
prev=get_prev(*head,key); if(prev!
=NULL)
{
prev->next=temp->next;
free(temp);
}
else
{
*head=temp->next;
free(temp);
}
printf("\nthe element is deleted\n");
}
}
Output:

Program-8:
Aim: Write a lex program to count the number of words and number of lines in a given file or
program
Algorithm:
Read each character from the text file :
Is it a capital letter in English? [A-Z] : increment capital letter count by 1.
Is it a small letter in English? [a-z] : increment small letter count by 1
Is it [0-9]? increment digit count by 1.
All other characters (like '!', '@','&') are counted as special characters
How to count the number of lines? we simply count the encounters of '\n' <newline>
[Link]'s all!!
To count the number of words we count white spaces and tab character(of course, newline
characters too..)
Program:
%{
#include<stdio.h>
int lines=0, words=0,s_letters=0,c_letters=0, num=0, spl_char=0,total=0;
%}
%%
\n { lines++; words++;}
[\t ' '] words++;
[A-Z] c_letters++;
[a-z] s_letters++;
[0-9] num++;
. spl_char++;
%%
main(void)
{
yyin= fopen("[Link]","r");
yylex();
total=s_letters+c_letters+num+spl_char;
printf(" This File contains ..."); printf("\n\
t%d lines", lines); printf("\n\t%d
words",words); printf("\n\t%d small
letters", s_letters); printf("\n\t%d capital
letters",c_letters); printf("\n\t%d digits",
num);
printf("\n\t%d special characters",spl_char); printf("\n\
tIn total %d characters.\n",total);
}
int yywrap()
{
return(1);
}
Output:
This file contains..
2 lines
9 words
30 small letters
3 capital letters
1 digits
9 special characters
In total 43 characters.
Program-9:
Aim: Write a ‘C’ program to implement lexical analyzer using c program.
Algorithm:
Program is an implementation of a lexical analyzer program in C language. In the
compilation process, the Lexical analysis phase is the first step. In this step, the lexical
analyzer breaks down the input code into small units called tokens (for example keywords,
identifiers, operators, literals, and punctuation).
Program:
#include<string.h>
#include<ctype.h>
#include<stdio.h>
void keyword(char str[10])
{
if(strcmp("for",str)==0||strcmp("while",str)==0||strcmp("do",str)==0|| strcmp("int",str)==0||
strcmp("float",str)==0||strcmp("char",str)==0|| strcmp("double",str)==0||
strcmp("static",str)==0||strcmp("switch",str)==0|| strcmp("case",str)==0)
printf("\n%s is a keyword",str);
else
printf("\n%s is an identifier",str);
}
main()
{
FILE *f1,*f2,*f3;
char c,str[10],st1[10];
int num[100],lineno=0,tokenvalue=0,i=0,j=0,k=0;
printf("\nEnter the c program");/*gets(st1);*/
f1=fopen("input","w"); while((c=getchar())!
=EOF)
putc(c,f1);
fclose(f1);
f1=fopen("input","r");
f2=fopen("identifier","w");
f3=fopen("specialchar","w");
while((c=getc(f1))!=EOF)
{
if(isdigit(c))
{
tokenvalue=c-'0';
c=getc(f1);
while(isdigit(c))
{
tokenvalue*=10+c-'0';
c=getc(f1);
}
num[i++]=tokenvalue;
ungetc(c,f1);
}
else if(isalpha(c))
{
putc(c,f2);
c=getc(f1);
while(isdigit(c)||isalpha(c)||c=='_'||c=='$')
{
putc(c,f2);
c=getc(f1);
}
putc(' ',f2);
ungetc(c,f1);
}
else if(c==' '||c=='\t')
printf(" ");
else if(c=='\n')
lineno++;
else
putc(c,f3);
}
fclose(f2);
fclose(f3);
fclose(f1);
printf("\nThe no's in the program are");
for(j=0;j<i;j++)
printf("%d",num[j]); printf("\
n");
f2=fopen("identifier","r");
k=0;
printf("The keywords and identifiersare:");
while((c=getc(f2))!=EOF)
{
if(c!=' ')
str[k++]=c;
else
{
str[k]='\0';
keyword(str);
k=0;
}
}
fclose(f2);
f3=fopen("specialchar","r");
printf("\nSpecial characters are");
while((c=getc(f3))!=EOF)
printf("%c",c);
printf("\n");
fclose(f3);
printf("Total no. of lines are:%d",lineno);}
Output:
Enter the C program
a+b*c
Ctrl-D
The no’s in the program are:
The keywords and identifiers are:
a is an identifier and terminal
b is an identifier and terminal
c is an identifier and terminal
Special characters are:
+*
Total no. of lines are: 1

Program-10:
Aim: Write recursive descent parser for the grammar E->E+T E->T T->T*F T->FF->(E)/id.
Algorithm:
It is a kind of Top-Down Parser. A top-down parser builds the parse tree from the top to
down, starting with the start non-terminal. A Predictive Parser is a special case of Recursive
Descent Parser, where no Back Tracking is required.
Program:
#include <stdio.h>
#include <string.h>
#define SUCCESS 1
#define FAILED 0
int E(), Edash(), T(), Tdash(), F();
const char *cursor;
char string[64];
int main()
{
puts("Enter the string");
// scanf("%s", string); sscanf("i+
(i+i)*i", "%s", string); cursor =
string;
puts("");
puts("Input Action");
puts(" ");
if (E() && *cursor == '\0') {
puts(" ");
puts("String is successfully parsed");
return 0;
} else {
puts(" ");
puts("Error in parsing String");
return 1;
}
}
int E()
{
printf("%-16s E -> T E'\n", cursor);
if (T()) {
if (Edash())
return SUCCESS;
else
return FAILED;
} else
return FAILED;
}
int Edash()
{
if (*cursor == '+') {
printf("%-16s E' -> + T E'\n", cursor);
cursor++;
if (T()) {
if (Edash())
return SUCCESS;
else
return FAILED;
} else
return FAILED;
} else {
printf("%-16s E' -> $\n", cursor);
return SUCCESS;
}
}
int T()
{
printf("%-16s T -> F T'\n",
cursor); if (F()) {
if (Tdash())
return SUCCESS;
else
return FAILED;
} else
return FAILED;
}
int Tdash()
{
 if (*cursor == '*') {
printf("%-16s T' -> * F T'\n", cursor);
cursor++;
if (F()) {
if (Tdash())
return SUCCESS;
else
return FAILED;
} else
return FAILED;
} else {
printf("%-16s T' -> $\n", cursor);
return SUCCESS;
}
}
int F()
{
if (*cursor == '(') {
printf("%-16s F -> ( E )\n", cursor);
cursor++;
if (E()) {
if (*cursor == ')') {
cursor++;
return SUCCESS;
} else
return FAILED;
} else
return FAILED;
} else if (*cursor == 'i') {
cursor++;
 printf("%-16s F ->i\n", cursor);
return SUCCESS;
} else
return FAILED;
}
Output:
Enter the string

Input Action

i+(i+i)*i E -> T E'

i+(i+i)*i T -> F T'
+(i+i)*i F ->i
+(i+i)*i T' -> $
+(i+i)*i E' -> + T E'
(i+i)*i T -> F T'
(i+i)*i F -> ( E )
i+i)*i E -> T E'
i+i)*i T -> F T'
+i)*i F ->i
+i)*i T' -> $
+i)*i E' -> + T E'
i)*i T -> F T'
)*i F ->i
)*i T' -> $
)*i E' -> $
*i T' -> * F T'
F ->i
T' -> $
E' -> $

String is successfully parsed

Program-11:
Aim: Write recursive descent parser for the grammar S->(L) S->a L->L,S L->S
Algorithm:
1.S() Function
2.L() Function
3. match(char expected) Function

4. next_token() Function

5. Error() Function
 6. Main Function

Program:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
void error();
void S();
void L();
char lookahead;
void error() {
printf("Syntax error\n");
exit(1);
}
void next_token()
{ lookahead = getchar();
while (lookahead == ' ' || lookahead == '\n') // Skip spaces and newlines
lookahead = getchar();
}
void S() {
if (lookahead == '(') {
printf("S -> (L)\n");
next_token();
L();
if (lookahead == ')') {
printf("S -> (L)\n");
next_token();
}
else
error();
}
 else if (lookahead == 'a') {
printf("S -> a\n");
next_token();
}
else {
error();
}
}
void L() {
S();
if (lookahead == ',') {
printf("L -> LS\n");
next_token();
L();
}
}
int main() {
printf("Enter a string: ");
next_token();
S();
if (lookahead == '\n' || lookahead == EOF)
{ printf("Parsing successful\n");
} else {
printf("Parsing failed\n");
}
return 0;
}
Output:
Enter a string: (a,a)
S -> (L)
S -> a
L ->
LS S ->
a
Parsing successful

Program-12:
Aim: Write a C program to calculate first function for the
grammar E->E+T E->T T->T*F T->F F->(E)/id.
Algorithm:
1. Main Function

2. calculateFirst Function

3. isTerminal Function

Program:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_RULES 5
#define MAX_SYMBOLS 10
void calculateFirst(char non_terminal, char first[]);
bool isTerminal(char symbol);
char rules[MAX_RULES][MAX_SYMBOLS] =
{ "E", "E+T",
"E", "T",
"T", "T*F",
"T", "F",
"F", "(E)",
"F", "id"
};
int main() {
char non_terminals[] = {'E', 'T', 'F'};
int num_non_terminals = sizeof(non_terminals) / sizeof(non_terminals[0]);
 for (int i = 0; i < num_non_terminals; i++)
{ char first[MAX_SYMBOLS];
calculateFirst(non_terminals[i], first);
printf("First(%c): {%s}\n", non_terminals[i], first);
}
return 0;
}
void calculateFirst(char non_terminal, char first[])
{ bool visited[MAX_RULES] = {false};
int index = 0;
for (int i = 0; i < MAX_RULES; i++) {
if (rules[i][0] == non_terminal && !visited[i])
{ visited[i] = true;
if (rules[i][3] == '\0' || rules[i][3] == '$')
{ first[index++] = '$';
}
else if (isTerminal(rules[i][3]) || rules[i][3] == non_terminal)
{ first[index++] = rules[i][3];
}
else {
int j = 3;
while (rules[i][j] != '\0') {
if (isTerminal(rules[i][j]))
{ first[index++] = rules[i]
[j]; break;
}
else {
calculateFirst(rules[i][j], first);
if (strchr(first, '$') == NULL)
break;
 } j+
+;
}
}
}
}

first[index] = '\0';
}
bool isTerminal(char symbol) {
return islower(symbol) || symbol == '(' || symbol == ')';
}
Output:
First(E): {(+), (*), (,), (id)}
First(T): {(+), (*), (,), (id)}
First(F): {($), (,), (id)}

Program-13:
Aim: Write a YACC program to implement a top down parser for the given grammar.
Algorithm:
1. Header Section

2. Token Section

3. Start Symbol

4. Rules Section

5. E Productions

6. T Productions

7. F Productions

8. Main Function

9. Error Handling

Program:
Yaac:
%{
#include <stdio.h>
#include <stdlib.h>
%}
%token PLUS STAR LPAREN RPAREN ID
%start E
%%
E : E PLUS T
|T
;
T : T STAR F
|F
;
F : LPAREN E RPAREN
| ID
;
%%
int main() {
yyparse();
return 0;
}
int yyerror(const char *s) {
printf("Syntax Error\n");
return 0;
}
Lex:
%{
#include "[Link].h"
%}
%%
"+" { return PLUS; }
"*" { return STAR; }
"(" { return LPAREN; }
")" { return RPAREN; }
[a-zA-Z]+ { return ID; }
[ \t\n] ; /* skip whitespace */
. { yyerror("Invalid character"); }
%%
int yywrap()
{ return 1;
}
Output:
lex parser.l
yacc -d
parser.y
gcc [Link].c [Link].c -o parser -ll
./parser

Program-14:
Aim: Write a YACC program to evaluate algebraic expression.
Algorithm:
1. Header Section

2. Token Declaration

3. Operator Precedence Declaration

4. Start Symbol Declaration

5. Production Rules

6. Main Function

7. Lexical Analyzer(Lexer) Function-‘yylex()’

8. yyerror() Functionss

Program:
%{
#include <stdio.h>
#include <stdlib.h>
%}
%token NUMBER
%left PLUS MINUS
%left TIMES DIVIDE
%start expr
%%
expr : expr PLUS expr { $$ = $1 + $3; }
| expr MINUS expr { $$ = $1 - $3; }
| expr TIMES expr { $$ = $1 * $3; }
| expr DIVIDE expr { if ($3 != 0) $$ = $1 / $3; else { printf("Error: Division by zero\n");
exit(1); } }
| NUMBER { $$ = $1; }
;
%%
int main() {
printf("Enter an algebraic expression: ");
yyparse();
return 0;
}
int yylex() {
int c = getchar();
if (c == '+' || c == '-' || c == '*' || c == '/')
{ return c;
} else if (isdigit(c))
{ ungetc(c, stdin);
scanf("%d", &yylval);
return NUMBER;
} else if (c == '\n' || c == EOF)
{ return 0;
} else {
printf("Invalid character '%c'\n", c);
 exit(1);
}
}
void yyerror(const char *s) {
printf("Error: %s\n", s);
exit(1);}
Output:
Enter an algebraic expression: 5 + 3 * 2
Result: 11