Lexical Analyzer using C Program - Simulation of Lexical Analyzer in C Program

Finite Automata for Lexical analyzer (Click to enlarge)

The input to lexical analyzer is character stream. The character stream input is grouped into meaningful units called lexemes, which are then mapped into tokens, the latter constituting the output of the lexical analyzer. The lexical analyzer uses a symbol table. Each identifier, keyword and symbol are given unique id (symbol table id). The lexical analyzer is designed using finite automata. The finite automata for this program is added at the end of the post. The program takes a file input.c (in same file) as input. The input to a lexical analyzer is source string (source code as a long string). A sample input to the lexical analyzer is shown after this program.

Lexical Analyzer Program in C

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>

//***********

struct token
{
char type[30];
char name[50];
int id;
}retToken;

//*******

struct symboltable
{
char type[30];
char name[50];
}st[60];

typedef struct token token;

char* sourcecode;
int lexbeg=0,fwdptr=0,state=0;
int symbolcount=0;
token newtoken;
int isexist=0,lineno=1;

//************

int indexof(char *subString,int fromIndex,char *MainString)
{
	int Mainlength,subLength,i,j,retIndex=-1;
	Mainlength=strlen(MainString);
	subLength=strlen(subString);
	if(Mainlength<1||subLength<1||Mainlength-fromIndex<subLength)
		return(-1);
	for(i=fromIndex;Mainlength-i>=subLength;i++)
		{
		if(*(MainString+i)==*(subString))
			{
			retIndex=i;
			for(j=0;j<subLength;j++)
				{
				if(*(MainString+i+j)!=*(subString+j))
					{
					retIndex=-1;
					break;
					}
				}
			if(retIndex!=-1)
				return retIndex;
			}
		}
	return (-1);
}

//************

char * subString(char *MainString,int fromIndex,int toIndex)
{
int Mainlength,j;
char *subStr;
Mainlength=strlen(MainString);
if(fromIndex<0||fromIndex>=Mainlength||toIndex<fromIndex||toIndex>=Mainlength)
	{
	printf("\nError in args: subString fn");
	return(NULL);
	}
subStr=(char *)malloc(1000*sizeof(char));
for(j=0;j<=toIndex-fromIndex;j++)
	*(subStr+j)=*(MainString+fromIndex+j);

*(subStr+j)='\0';
return(subStr);
}

//************

char nextchar()
{
fwdptr++;
return(sourcecode[fwdptr-1]);
}

//************

void retract(int n)
{
fwdptr-=n;
}

//************

int fail(char * msg)
	{
	printf("%s",msg);
	return(-1);
	}

//************

int installid(char *string)
{
int i;
for(i=0;i<symbolcount;i++)
{
if(strcmp(string,st[i].name)==0)
	return i;
}
strcpy(st[symbolcount].name,string);
strcpy(st[symbolcount].type,"identifier");
symbolcount++;
return(symbolcount-1);
}

//************

token getType(char *tok)
{
int i;
token tt;
for(i=0;i<symbolcount;i++)
	{
	if(strcmp(st[i].name,tok)==0)
		{
        strcpy(tt.type,st[i].type);
        strcpy(tt.name,st[i].name);
        tt.id=i;
		return(tt);
		}
	}

}

//************

int isSymbol(char c)
{
int i;
char syms[]={'.','<','>',',','{','}','(',')','#',';'};
for(i=0;i<10;i++)
{
if(c==syms[i])
	return(i+41);
}
return(0);
}

void nextToken()
{
char c;
char *temptok;
state=0;
while(*(sourcecode+fwdptr)!='\0'&&state!=-1)
{
switch(state)
	{
	case -1:return;
	case 0:c=nextchar();
		if(c==' '||c=='\t'||c=='\n')
			{
			state=0;
			lexbeg++;
			if(c=='\n')
				{
				lineno++;
				printf("\nline %d: ",lineno);
				}
			if(c=='\0')
				state=-1;
			}
		else if(c=='<')
			state=1;
		else if(c=='>')
			state=5;
		else if(c=='=')
			state=8;
		else if(isalpha(c))
			state=10;
		else if(isdigit(c))
			state=22;
		else if(isSymbol(c))
			state=24;
		else if(c=='+')
			state=12;
		else if(c=='-')
			state=15;
		else if(c=='*')
			state=18;
		else if(c=='/')
			state=19;
		else if(c=='%')
			state=20;
		else
			state=fail("unknown symbol encountered");
		break;
	case 1:c=nextchar();
		if(c=='=')
			state=2;
		else if(c=='>')
			state=3;
		else
			state=4;
		break;
	case 2:strcpy(retToken.type,"relop");
		strcpy(retToken.name,"LE");
		retToken.id=17;lexbeg=fwdptr;return;
	case 3:strcpy(retToken.type,"relop");retToken.id=18;
		strcpy(retToken.name,"NE");lexbeg=fwdptr;return;
	case 4:retract(1);
		strcpy(retToken.type,"relop");retToken.id=19;
		strcpy(retToken.name,"LT");lexbeg=fwdptr;return;
	case 5:c=nextchar();
		if(c=='=')
			state=6;
		else
			state=7;
		break;
	case 6:strcpy(retToken.type,"relop");retToken.id=20;
		strcpy(retToken.name,"GE");lexbeg=fwdptr;return;
	case 7:retract(1);
		strcpy(retToken.type,"relop");retToken.id=21;
		strcpy(retToken.name,"GT");lexbeg=fwdptr;return;
	case 8:c=nextchar();
		if(c=='=')
			state=9;
		else
			state=21;
		break;
	case 9:strcpy(retToken.type,"relop");retToken.id=22;
		strcpy(retToken.name,"EQ");lexbeg=fwdptr;return;
	case 10:c=nextchar();
		if(isalpha(c)||isdigit(c))
			state=10;
		else
			state=11;
		break;
	case 11:retract(1);
		temptok=subString(sourcecode,lexbeg,fwdptr-1);
		retToken.id=installid(temptok);
		retToken=getType(temptok);
		lexbeg=fwdptr;return;
	case 12:c=nextchar();
		if(c=='+')
			state=13;
		else
			state=14;
		break;
	case 13:strcpy(retToken.type,"arop");retToken.id=23;
		strcpy(retToken.name,"INC");lexbeg=fwdptr;return;
	case 14:retract(1);
		strcpy(retToken.type,"arop");retToken.id=24;
		strcpy(retToken.name,"PLU");lexbeg=fwdptr;return;
	case 15:c=nextchar();
		if(c=='-')
			state=16;
		else
			state=17;
		break;
	case 16:strcpy(retToken.type,"arop");retToken.id=25;
		strcpy(retToken.name,"DEC");lexbeg=fwdptr;return;
	case 17:retract(1);
		strcpy(retToken.type,"arop");retToken.id=26;
		strcpy(retToken.name,"MIN");lexbeg=fwdptr;return;
	case 18:strcpy(retToken.type,"arop");retToken.id=27;
		strcpy(retToken.name,"MUL");lexbeg=fwdptr;return;
	case 19:strcpy(retToken.type,"arop");retToken.id=28;
		strcpy(retToken.name,"DIV");lexbeg=fwdptr;return;
	case 20:strcpy(retToken.type,"arop");retToken.id=29;
		strcpy(retToken.name,"MOD");lexbeg=fwdptr;return;
	case 21:retract(1);retToken.id=30;
		strcpy(retToken.type,"arop");
		strcpy(retToken.name,"ASSIGN");lexbeg=fwdptr;return;
	case 22:c=nextchar();
		if(isdigit(c))
			state=22;
		else
			state=23;
		break;
	case 23:retract(1);retToken.id=41;
		strcpy(retToken.type,"Numeric constant");
		strcpy(retToken.name,subString(sourcecode,lexbeg,fwdptr-1));lexbeg=fwdptr;return;
	case 24:strcpy(retToken.type,"Reserved Symbol");retToken.id=isSymbol(c);
		strcpy(retToken.name,subString(sourcecode,lexbeg,fwdptr-1));lexbeg=fwdptr;return;

	}
}

}

//************

void regkeywords()
{
int i;
char keywords[][15]={"do","while","main","for","include","if","else","break","continue","int","char","float","double","void","return","switch","case"};
//17
char relop[][3]={"LE","NE","LT","GE","GT","EQ"};//17 to 22
char arop[][7]={"INC","PLU","DEC","MIN","MUL","DIV","MOD","ASSIGN"};//23 to 30
char syms[][2]={".","<",">",",","{","}","(",")","#",";"};//31 to 40

for(i=0;i<=16;i++)
{
strcpy(st[i].name,keywords[i]);
strcpy(st[i].type,"keyword");
}

for(i=17;i<=22;i++)
{
strcpy(st[i].name,relop[i-17]);
strcpy(st[i].type,"relop");
}

for(i=23;i<=30;i++)
{
strcpy(st[i].name,arop[i-23]);
strcpy(st[i].type,"arop");
}

for(i=31;i<41;i++)
{
strcpy(st[i].name,syms[i-31]);
strcpy(st[i].type,"Reserved Symbol");
}
strcpy(st[41].name,"NC");
strcpy(st[41].type,"Numeric Constant");
symbolcount=42;

}

//************

void main()
{
int i;
char c,*line;
FILE *input;
input=fopen("input.c","r");
i=0;
sourcecode=(char*)malloc(sizeof(char)*1200);
while((c=getc(input))!=EOF)
	{
	*(sourcecode+i)=c; i++;
	}
*(sourcecode+i)='\0';
regkeywords();
printf("\nline 1: ");
nextToken();
while(state!=-1)
{
printf("type: %s, name: %s, id= %d\n",retToken.type,retToken.name,retToken.id);
nextToken();
if(lexbeg>=strlen(sourcecode)||fwdptr>=strlen(sourcecode))
	state=-1;
}
printf("\nSymbol Table:\n");
for(i=0;i<=symbolcount;i++)
{
    printf("\nType: %s",st[i].type);
    printf("\tName: %s",st[i].name);
    printf("\tid=: %d",i);
}
}

Sample input (input.c) to the Lexical Analyzer

void main()
{
int a,b,c,d;
a=10;
b=30;
c=a+b;
d=a*b;
}

C Program to Simulate Round Robin CPU Sceduling Algorithm

The round robin CPU scheduling algorithm is simulated using C program. The time slice or time quantum is read from the user.

Program:

#include<stdio.h>
struct process{



int burst,wait,comp,f;
}p[20]={0,0};
int main(){
int
n,i,j,totalwait=0,totalturn=0,quantum,flag=1,
time=0;
printf("\nEnter The No Of Process
:");
scanf("%d",&n);
printf("\nEnter The Quantum time (in ms)
:");
scanf("%d",&quantum);
for(i=0;i<n;i++){
printf("Enter The Burst Time (in ms) For
Process #%2d :",i+1);
scanf("%d",&p[i].burst);
p[i].f=1;
}
printf("\nOrder Of Execution \n");
printf("\nProcess \tStarting\tEnding\tRemaining");
printf("\n\tTime \tTime\tTime");
while(flag==1){
flag=0;
for(i=0;i<n;i++){
if(p[i].f==1){
flag=1;
j=quantum;
if((p[i].burst-p[i].comp)>quantum){
p[i].comp+=quantum;
}
else{
p[i].wait=time-p[i].comp;
j=p[i].burst-p[i].comp;
p[i].comp=p[i].burst;
p[i].f=0;
}
printf("\nprocess # %-3d %-10d %-10d %-10d",i+1,time,time+j,p[i].burst-
p[i].comp);
time+=j;
}}}
printf("\n\n------------------");
printf("\nProcess \t Waiting Time  TurnAround Time ");
for(i=0;i<n;i++){
printf("\nProcess # %-12d%-15d%-15d",i+1,p[i].wait,p[i].wait+p[i].burst);
totalwait=totalwait+p[i].wait;
totalturn=totalturn+p[i].wait+p[i].burst;
}
printf("\n\nAverage\n------------------");
printf("\nWaiting Time : %f ms",totalwait/(float)n);
printf("\nTurnAround Time : %f ms\n\n",totalturn/(float)n);
return 0;
}

C Program to Simulate Priority Scheduling CPU scheduling Algorithm

The following C program implements Simulation of  priority scheduling (CPU Scheduling algorithm). Each process or job is given a priority. The priority is represented using a positive integer. The priority increases as the value of the integer decreases.

Program:

#include<stdio.h>
struct process{



int burst,wait,no,priority;
}p[20]={0,0};
int main(){
int n,i,j,totalwait=0,totalturn=0;
printf("\nEnter The No Of Process :");
scanf("%d",&n);
for(i=0;i<n;i++){
printf("Enter The Burst Time (in ms) For Process #%2d :",i+1);
scanf("%d",&p[i].burst);
printf("Enter The Priority For Process #%2d :",i+1);
scanf("%d",&p[i].priority);
p[i].no=i+1;
}
for(i=0;i<n;i++)
for(j=0;j<n-i-1;j++)
if(p[j].priority>p[j+1].priority)
{
p[j].burst^=p[j+1].burst^=p[j].burst^=p[j+1].burst;
p[j].no^=p[j+1].no^=p[j].no^=p[j+1].no;
//Simple way to swap 2 var’s
p[j].priority^=p[j+1].priority^=p[j].priority^=p[j+1].priority;
//printf("j");
}
printf("\nProcess \t Starting\tEnding\tWaiting\tTurnAround ");
printf("\n\t Time\tTime\tTime\tTime ");
for(i=0;i<n;i++)
{
printf("\nProcess # %-11d%-10d%-10d%-10d%10d",p[i].no,p[i].wait,p[i].wait+p[i].burst,p[i].wait,p[i].wait+p[i].burst);
p[i+1].wait=p[i].wait+p[i].burst;
totalwait=totalwait+p[i].wait;
totalturn=totalturn+p[i].wait+p[i].burst;
}
printf("\n\nAverage\n---------");
printf("\nWaiting Time : %f ms",totalwait/(float)n);
printf("\nTurnAround Time : %f ms\n\n",totalturn/(float)n);
return 0;
}

Output:
Enter The No Of Process :3
Enter The Burst Time (in ms) For Process #1 :30
Enter The Priority For Process # 1 :2
Enter The Burst Time (in ms) For Process #2 :20
Enter The Priority For Process # 2 :1
Enter The Burst Time (in ms) For Process #3 :40
Enter The Priority For Process # 3 :3

Process          Starting  Ending  Waiting  TurnAround
                          Time        Time      Time          Time
Process # 2        0             20           0                20
Process # 1       20            50          20              50
Process # 3       50            90          50              90

Average
---------
Waiting Time : 23.333333 ms
TurnAround Time : 53.333333 ms

Simulation of Shortest Job First (SJF) CPU scheduling algorithm in C Language

This is a C program to simulate Shortest Job First (SJF) CPU scheduling algorithm. In Shortest Job first CPU scheduling algorithm, the process with  shortest CPU burst time is executed first. The following program is to simulate non preemptive SJF scheduling. Preemptive SJF CPU scheduling algorithm will be discussed in another post.

#include<stdio.h>
struct process
{
int burst,wait,no;
}p[20]={0,0};

int main()
{
int n,i,j,totalwait=0,totalturn=0;
printf("\nEnter The No Of Process :");
scanf("%d",&n);
for(i=0;i<n;i++)
  {
  printf("Enter The Burst Time (in ms) For Process #%2d :",i+1);
  scanf("%d",&p[i].burst);
  p[i].no=i+1;
  }

for(i=0;i<n;i++)
  for(j=0;j<n-i-1;j++)
    if(p[j].burst>p[j+1].burst)
      {
      p[j].burst^=p[j+1].burst^=p[j].burst^=p[j+1].burst;
      p[j].no^=p[j+1].no^=p[j].no^=p[j+1].no;
      }

printf("\nProcess \t Waiting Time TurnAround Time ");
for(i=0;i<n;i++)
  {
  printf("\nProcess # %-12d%-15d%-15d",p[i].no,p[i].wait,p[i].wait+p[i].burst);
  p[i+1].wait=p[i].wait+p[i].burst;
  totalwait=totalwait+p[i].wait;
  totalturn=totalturn+p[i].wait+p[i].burst;
  }
printf("\n\nAverage\n---------");
printf("\nWaiting Time : %f ms",totalwait/(float)n);
printf("\nTurnAround Time : %f ms\n\n",totalturn/(float)n);
return 0;

}

Output:

Enter The No Of Process :3
Enter The Burst Time (in ms) For Process # 1 :20
Enter The Burst Time (in ms) For Process # 2 :30
Enter The Burst Time (in ms) For Process # 3 :10
Process          Waiting Time     TurnAround Time
Process # 3          0                           10
Process # 1        10                            30
Process # 2        30                            60

Average---------
Waiting Time : 13.333333 ms
TurnAround Time : 33.333333 ms

Related Posts:

C Program to Simulate ls Command in Linux
C Program to Simulate Round Robin CPU Scheduling Algorithm
C Program to Simulate Priority CPU Scheduling Algorithm
C Program to Simulate First Come First Serve (FCFS) CPU Scheduling Algorithm
C Program to Simulate rmdir Command or Delete Directory
C Program to Open, Read and Write Files
C Program to Create Process and Display Process ID - OS Lab Program
How to Use Fork and Exec System Calls
How to Use Exit System Call
C Program to make Parent Process Wait for Child to Terminate
C Program to Simulate GREP Command in Linux
C Program to make Child Process an Orphan Process
C Program to Show Process ID in Linux
C Program for Inter Process Communication using Pipes or Named Pipes (Chat Program)
C Program to Create a Process Using Fork System Call

Simulation of FCFS CPU Scheduling Algorithm in C

This is a C program to simulate First come first served (FCFS) CPU scheduling algorithm. First come first served algorithm serves each processes (or jobs) in the order of arrival. The process with lowest arrival time is executed first.

Program:
#include<stdio.h>
struct process
{
int burst,wait;
}p[20]={0,0};



int main()
{
int n,i,totalwait=0,totalturn=0;
printf("\nEnter The No Of Process :");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter The Burst Time (in ms) For Process #%2d :",i+1);
scanf("%d",&p[i].burst);
}
printf("\nProcess \t Waiting Time\tTurnAround Time ");
printf("\n\t (in ms)\t(in ms)");
for(i=0;i<n;i++)
{
printf("\nProcess # %-12d%-15d%-15d",i+1,p[i].wait,p[i].wait+p[i].burst);
p[i+1].wait=p[i].wait+p[i].burst;
totalwait=totalwait+p[i].wait;
totalturn=totalturn+p[i].wait+p[i].burst;
}
printf("\n\nAVERAGE\n--------- ");
printf("\nWaiting Time : %f ms",totalwait/(float)n);
printf("\nTurnAround Time : %f ms\n\n",totalturn/(float)n);
return 0;
}

Output:
Enter The No Of Process :3
Enter The Burst Time (in ms) For Process # 1 :10
Enter The Burst Time (in ms) For Process # 2 :30
Enter The Burst Time (in ms) For Process # 3 :20
Process    Waiting Time     Turn Around Time
                     (in ms)                      (in ms)
Process # 1     0                               10
Process # 2    10                              40
Process # 3    40                              60

AVERAGE
---------
Waiting Time : 16.666667 ms
TurnAround Time : 36.666667 ms

C Program to Simulate grep Command in Linux

This post contains C program to simulate grep command in Linux or Unix operating systems

Simulation of  grep command in Linux

#include<stdio.h>
#include<string.h>
void main()
{
char fn[10],pat[10],temp[200];
FILE *fp;
printf("Enter file name\n");
scanf("%s",fn);
printf("Enter pattern to be searched\n");
scanf("%s",pat);
fp=fopen(fn,"r");
while(!feof(fp))
{
fgets(temp,1000,fp);
if(strstr(temp,pat))
  printf("%s",temp);
}
fclose(fp);
}

Related Posts:

C Program to Simulate ls Command in Linux
C Program to Simulate Round Robin CPU Scheduling Algorithm
C Program to Simulate Priority CPU Scheduling Algorithm
C Program to Simulate Shortest Job First (SJF) CPU Scheduling Algorithm
C Program to Simulate First Come First Serve (FCFS) CPU Scheduling Algorithm
C Program to Simulate rmdir Command or Delete Directory
C Program to Open, Read and Write Files
C Program to Create Process and Display Process ID - OS Lab Program
How to Use Fork and Exec System Calls
How to Use Exit System Call
C Program to make Parent Process Wait for Child to Terminate
C Program to make Child Process an Orphan Process
C Program to Show Process ID in Linux
C Program for Inter Process Communication using Pipes or Named Pipes (Chat Program)
C Program to Create a Process Using Fork System Call