C code implementing a simple DFA

 

Hello freinds, 

Here I am posting my C implementation of DFA shown below. This DFA will accept any string containing 'a's and 'b' and last symbol should be 'a'.

#include <stdio.h>

#define TOTAL_STATES 2

#define FINAL_STATES 1

#define ALPHABET_CHARCTERS 2

#define UNKNOWN_SYMBOL_ERR 0

#define NOT_REACHED_FINAL_STATE 1

#define REACHED_FINAL_STATE 2

enum DFA_STATES{q0,q1};

enum input{a,b};

int Accepted_states[FINAL_STATES]={q1};

char alphabet[ALPHABET_CHARCTERS]={'a','b'};

int Transition_Table[TOTAL_STATES][ALPHABET_CHARCTERS];

int Current_state=q0;

void DefineDFA()

{

    Transition_Table[q0][a] = q1;

    Transition_Table[q0][b] = q0;

    Transition_Table[q1][a] = q1;

    Transition_Table[q1][b] = q0;

}

int DFA(char current_symbol)

{

int i,pos;

    for(pos=0;pos<ALPHABET_CHARCTERS; pos++)

        if(current_symbol==alphabet[pos])   

            break;//stops if any character other than a or b

    if(pos==ALPHABET_CHARCTERS)

         return UNKNOWN_SYMBOL_ERR;

    for(i=0;i<FINAL_STATES;i++)

 if((Current_state=Transition_Table[Current_state][pos])

==Accepted_states[i])

            return REACHED_FINAL_STATE;

    return NOT_REACHED_FINAL_STATE;

}

int main(void)

{

    char current_symbol;

    int result;

    DefineDFA();    //Fill transition table

    printf("Enter a string with 'a' s and 'b's:\n

                Press Enter Key to stop\n");

    while((current_symbol=getchar())!= '\n')

        if((result= DFA(current_symbol))==UNKNOWN_SYMBOL_ERR)

            break;

    switch (result) {

    case UNKNOWN_SYMBOL_ERR:printf("Unknown Symbol %c",

  current_symbol); 

 break;

    case NOT_REACHED_FINAL_STATE:printf("Not accepted"); break;

    case REACHED_FINAL_STATE:printf("Accepted");break;

    default: printf("Unknown Error");

    }

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

    return 0;

}

Read more »

Quadruple ~ C code

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

main()
{

 char line[20];
int s[20];
int t=1;
     
int i=0;     
printf("Enter string..  :");
gets(line);
for(i=0;i<20;i++)s[i]=0;
printf("op\ta1\ta2\tres\n");
for(i=2;line[i]!='\0';i++)
{
if(line[i]=='/' || line[i]=='*')
{
                printf("\n");
if(s[i]==0)
{
if(s[i+1]==0)
{
printf(":=\t%c\t\t t%d\n",line[i+1],t);
s[i+1]=t++;
}
printf("%c\t",line[i]);
(s[i-1]==0)?printf("%c\t",line[i-1]):printf("t%d\t",s[i-1]);
printf("t%d \t t%d",s[i+1],t);
s[i-1]=s[i+1]=t++;
s[i]=1;
}
}
}

for(i=2;line[i]!='\0';i++)
{
if(line[i]=='+' || line[i]=='-')
{
                printf("\n");
if(s[i]==0)
{
if(s[i+1]==0)
{
printf(":=\t%c\t\t t%d\n",line[i+1],t);
s[i+1]=t++;
}
printf("%c\t",line[i]);
(s[i-1]==0)?printf("%c\t",line[i-1]):printf("t%d\t",s[i-1]);
printf("t%d \t t%d",s[i+1],t);
s[i-1]=s[i+1]=t++;
s[i]=1;
}
}
}
printf("\n:=\tt%d\t\t%c",t-1,line[0]);



getch();
}




Output




Enter string..  :a=b*c-b*c


op      a1      a2      res
:=      c                t1
*       b       t1       t2
:=      c                t3
*       b       t3       t4
-       t2      t4       t5
:=      t5              a

Read more »

LEX program to check a Date (dd/mm/yyyy)

Hello dude..   

            I would like to discuss a problem asked by my teacher in our internal lab exam- LEX program to check the validity of a Date. Ahem..In normal programming (i.e, that with C or Java) this is not a big deal!! But in Lex paradigm,it require some more effort..!!

                                                
                                                   

*Check the syntax of Date::

* If we have to check the syntax only ,i.e., dd/mm/yyyy apply the simple logic

[0-9][0-9] \ / [0-9][0-9] \ / [0-9] [0-9] [0-9] [0-9]

* But date should be within range [01-31] ,month be within [01-12] and assume year be within the range [1000-2999]. To apply these constraints, we redefine rules as:

"01-31"----> ([0-2][0-9] | 3 [0-1])
"01-12"----> (0[1-9] | 1[0-2])
"1000-2999"---->  ([1-2][0-9][0-9][0-9])

* Thus we can simply check the syntax of given Date as:

([0-2][0-9] | 3 [0-1])  \ /  (0[1-9] | 1[0-2]) \ / ([1-2][0-9][0-9][0-9])

*To Check the validity of date::

-->  In months 01,03,05,07,08,10 &12 , there will be at most 31 days.

([0-2][0-9]|[3][0-1])\/((0(1|3|5|7|8))|(10|12))\/([1-2][0-9][0-9][-0-9]) 

--> In months 04,06,09 & 11 may have at most 30 days

([0-2][0-9]|30)\/((0(4|6|9))|11)\/([1-2][0-9][0-9][0-9])

-->February has 28 days (in linear and non-linear years)

([0-1][0-9]|2[0-8])\/02\/([1-2][0-9][0-9][0-9])

-->If February has a day 29, check whether it is leap year or not..!!

29\/02\/([1-2][0-9][0-9][0-9])

 {

extract year value;

check whether it is a leap year;

}

-->Extract year value

   1.Iterate upto two "/" in date are over.(i.e.,in dd/mm/yyyy pass over two "/"s to reach at year value.

   2.read all susequent characters (they all are part of year value - yyyy)

while(yytext[i]!='/')i++;   //reach at first "/"
i++;                        // increment pointer
while(yytext[i]!='/')i++;   //reach at next "/"
i++;                        // increment pointer
while(i<yyleng)             // read all characters upto end of the string
yr=(10*yr)+(yytext[i++]-'0');// extract integer value of year

--> Check whether it is Leap year or not:

if(yr%4==0||(yr%100==0&&yr%400!=0))

Well... the complete lex program is as follows..!!

Date.l

%{
#include<stdio.h>
int i=0,yr=0,valid=0;
%}
%%
([0-2][0-9]|[3][0-1])\/((0(1|3|5|7|8))|(10|12))\/([1-2][0-9][0-9][-0-9]) {valid=1;}

([0-2][0-9]|30)\/((0(4|6|9))|11)\/([1-2][0-9][0-9][0-9]) {valid=1;}

([0-1][0-9]|2[0-8])\/02\/([1-2][0-9][0-9][0-9]) {valid=1;}

29\/02\/([1-2][0-9][0-9][0-9]) { while(yytext[i]!='/')i++; i++;while(yytext[i]!='/')i++;i++;while(i<yyleng)yr=(10*yr)+(yytext[i++]-'0'); if(yr%4==0||(yr%100==0&&yr%400!=0))valid=1;}

%%
main()
{
yyin=fopen("vpn.txt","r");
yylex();
if(valid==1) printf("It is a valid date\n");
else printf("It is not a valid date\n");
}
int yywrap()
{
return 1;
}

OUTPUT

Content in input file (here, vpn.txt)	Output
12/12/2011	It is a valid date
32/10/2009	It is not a valid date
29/02/2008	It is a valid date
31/04/1990	It is not a valid date
29/02/2007	It is not a valid date

Hope this post was useful for you. If you have any suggestions or doubts,please do comment here...!!
Thank you

Read more »

FOLLOW OF GIVEN GRAMMAR USING C PROGRAM

Hello reader,
In this post I am posting implementation of FOLLOW in C.
Note:
If your production statements contain multiple terms connected by '|'  then give these terms as separate productions
 


#include<stdio.h>

#include<string.h>

int n,m=0,p,i=0,j=0;

char a[10][10],followResult[10];

void follow(char c);

void first(char c);

void addToResult(char);

int main()

{

 int i;

 int choice;

 char c,ch;

 printf("Enter the no.of productions: ");

scanf("%d", &n);

 printf(" Enter %d productions\nProduction with multiple terms should be give as separate productions \n", n);

 for(i=0;i<n;i++)

  scanf("%s%c",a[i],&ch);

    // gets(a[i]);

 do

 {

  m=0;

  printf("Find FOLLOW of -->");

  scanf(" %c",&c);

  follow(c);

  printf("FOLLOW(%c) = { ",c);

  for(i=0;i<m;i++)

   printf("%c ",followResult[i]);

  printf(" }\n");

  printf("Do you want to continue(Press 1 to continue....)?");

 scanf("%d%c",&choice,&ch);

 }

 while(choice==1);

}

void follow(char c)

{

    if(a[0][0]==c)addToResult('$');

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

   }

  }

 }

}

void first(char c)

{

      int k;

                 if(!(isupper(c)))

                     //f[m++]=c;

                     addToResult(c);

                 for(k=0;k<n;k++)

                 {

                 if(a[k][0]==c)

                 {

                 if(a[k][2]=='$') follow(a[i][0]);

                 else if(islower(a[k][2]))

                     //f[m++]=a[k][2];

                     addToResult(a[k][2]);

                 else first(a[k][2]);

                 }

                 }

}

void  addToResult(char c)

{

    int i;

    for( i=0;i<=m;i++)

        if(followResult[i]==c)

            return;

   followResult[m++]=c;

}

Sample output:

Read more »

Recursive Descent Parser using C program

Updated on 09/02/15

Hello reader,

Here is the updated post considering your valuable suggestions. check it out.


The grammar on which we are going to do recursive descent parsing is:

E -> E+T | T
T -> T*F | F
F -> (E) | id
  RD parser will verify whether the syntax of the input stream is correct by checking each character  from left to right. A basic operation necessary is reading characters from the input stream and matching then with terminals from the grammar that describes the syntax of the input.

 The given grammar can accept all arithmetic equations involving +, * and ().
eg:
 a+(a*a)  a+a*a , (a), a , a+a+a*a+a.... etc are accepted
a++a, a***a, +a, a*, ((a . . . etc are rejected.

Solution:
First we have to avoid left recursion

E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' | ε
F -> (E) | id

After eliminating Left recursion, we have to simply move from one character to next by checking whether it follow the grammar. In this program, ε is indicated as $.


recursive.c

#include<stdio.h>
#include<string.h>
#include<ctype.h>
 
char input[10];
int i,error;
void E();
void T();
void Eprime();
void Tprime();
void F(); 
          main()
          {
i=0;
error=0;
                printf("Enter an arithmetic expression   :  "); // Eg: a+a*a
                gets(input);
                E();
                if(strlen(input)==i&&error==0)
                        printf("\nAccepted..!!!\n");
                else printf("\nRejected..!!!\n");
                          }
         
         
 
void E()
{
     T();
     Eprime();
}
void Eprime()
{
     if(input[i]=='+')
     {
     i++;
     T();
     Eprime();
     }
     }
void T()
{
     F();
     Tprime();
}
void Tprime()
{
     if(input[i]=='*')
     {
                      i++;
                      F();
                      Tprime();
                      }
                      }
     void F()
     {
          if(isalnum(input[i]))i++;
          else if(input[i]=='(')
          {
          i++;
          E();
          if(input[i]==')')
          i++;

          else error=1;
            }
        
          else error=1;
          }
           

Output:
 a+(a*a)  a+a*a , (a), a , a+a+a*a+a.... etc are  accepted
++a, a***a, +a, a*, ((a . . . etc are rejected.

Read more »

Calculator using YACC program

Here is the Yacc program implementing a simple calculator:

%{
#include<stdio.h>
#include<ctype.h>
%}
%token num
%left '+''-'
%left '*''/'
%right '^'
%%
s:e'\n'{printf("%d",$1);}
e:    e '+' e{$$=$1+$3;}
 |e '-' e{$$=$1-$3;}
 |e '*' e{$$=$1*$3;}
 |e '/' e{$$=$1/$3;}
 |e '^' e {
  int i,j=$1;
  for(i=1;i<$3;i++)
  {
  j=j*$1;
  $$=j;
  }
  }
 |'('e')'{$$=$2;}
 |num1;
num1:num1 num{$$ = $1*10 + $2;}
 |num
 ;
%%
yylex()
{
int c;
c=getchar();
if(isdigit(c))
{
yylval=c-'0';
return num;
}
return c;
}
int main()
{
yyparse();
return 1;
}
int yyerror()
{
return 1;
}
int yywrap()
{
return 1;
}



Illustration:

Let the Input be 2+5

Moving from first definition s:e'\n'
s  --> move to DEF(e)
e: e '+' e is selected. Evaluate first 'e' ie e-->num1
num1 extracts the token (i.e, number here 2 is extracted and stored in $1)
Then '+' is extracted and stored in $2.
Then move to e--> num1, thus 5 is  extracted and stored  in $3.
Now add them and store result in $$.

Go back to S: e'\n' and print result (which is 'e' here..!!)


If you have any doubt regarding this post feel free to comment here.
Thank U..!!

For more Yacc programs click here..!!

Read more »

YACC program to convert infix

%{#include<stdio.h>
#include<ctype.h>
%}
%token num
%left '+''-'
%left '*' '/'
%%
s:e'\n'{}
e:e'+'e{printf("+");}
|e'-'e{printf("-");}
|e'/'e{printf("/");}
|e'*'e{printf("*");}
|num1{printf("%d",$1);}
num1:num1 num {$$=$1*10+$2;}
|num
;
%%
yylex()
{
 int c;
 c=getchar();
if(isdigit(c))
{ yylval=c-'0';
 return num;
}return c;
}
int main()
{
 yyparse();
return 1;
}
int yyerror()
{
return 1;
}
int yywrap()
{
 return 1;
}

Read more »

Yacc program to evaluate POSTFIX expression

%{#include<stdio.h>
#include<ctype.h>
%}
%token num
%left '+''-'
%left '*' '/'
%right '^'
%%
s:e'\n'{printf("\n%d",$1);}
e:e e'+'{$$=$1+$2;}
|e e'-'{$$=$1-$2;}
|e e'*'{$$=$1*$2;}
|e e'/'{$$=$1/$2;}
|num
;
%%
yylex()
{
int c;
c=getchar();
if(isdigit(c))
{ yylval=c-'0';
 return num;
}return c;
}
int main()
{
 yyparse();
return 1;
}
int yyerror()
{
return 1;
}
int yywrap()
{
 return 1;
}

Illustraion:

Evaluation of postfix expression can be done very easily.

34+
3--> store value in $1
4--> store value in $2
+--> add $1 and $2 and store result in $$

For more Yacc programs click here..!!

Read more »

C Program to generate Intermediate code

#include<stdio.h>
#include<ctype.h>
#include<string.h>
main()
{
char a[20];
int i=2,n;
printf("Exp  :");
scanf("%s", a);
if(isdigit(a[0]))
printf("MVI A,%c\n",a[0]);
else printf("MOV A,%c\n",a[0]);
n=strlen(a);
while(i<n)
{
switch(a[i])
{
case '+':printf("ADD B\n");i+=3;break;
case '-':printf("SUB B\n");i+=3;break;


default:if(isdigit(a[i]))
printf("MVI B,%c\n",a[i]);
else
printf("MOV B,%c\n",a[i]);
i--;
}
}
}

Read more »