Recursive descent parsing

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char in[50];
int j=0,f=0;
void PE1();
void PT();
void PT1();
void PF();
void match(char c);
void PE()
{
printf("E->TE1\n");
//printf("Enter PE\n");
PT();
PE1();
}
void PE1()
{
//printf("Enter PE1\n");
char c=in[j];
if(c=='+')
{
printf("E1->+TE1\n");
match(c);
PT();
PE1();
}
else
printf("E1->NULL\n");
}
void PT()
{
//printf("Enter PT\n");
printf("T->FT1\n");
PF();
PT1();
}
void PT1()
{
//printf("Enter PT1\n");
char c=in[j];
if(c=='*')
{
printf("T1->*FT1\n");
match(c);
PF();
PT1();
}
else
printf("T1->NULL\n");
}
void PF()
{
//printf("Enter PF\n");
char c=in[j];
if(c=='(')
{
printf("F->(E)\n");
match('(');
PE();
match(')');
}
else if((c>='a' && c<='z')|| (c>='A' && c<='Z'))
{
printf("F->id\n");
match(c);
}
else
{
printf("Syntax Error\n");
exit(0);
}
}
void match(char c)
{
if(j<=strlen(in))
{
if(in[j]==c)
{
printf("matched %c\n",c);
j++;
}
else
printf("Error\n");
}
}
int main()
{
scanf("%s",in);
PE();
if(in[j]=='\0')
printf("correct\n");
else
printf("Syntax error\nUnidentified symbol %c\n",in[j]);
return 0;

Predictive Parsing Of the grammar

/*This Program implements the Predictive Parsing Of the grammar
E->E+T/T
F->F*T/F
F->id(Identifier)*/
#include<string.h>
#include<stdio.h>
char a[10];
int top=-1,i;
void error(){
printf("Syntax Error");
}
void push(char k[]) //Pushes The Set Of Characters on to the Stack
{
  for(i=0;k[i]!='\0';i++)
  {
    if(top<9)
    a[++top]=k[i];
  }
}
char TOS()        //Returns TOP of the Stack
{
  return a[top];
}
void pop()       //Pops 1 element from the Stack
{
  if(top>=0)
    a[top--]='\0';
}
void display()  //Displays Elements Of Stack
{
  for(i=0;i<=top;i++)
    printf("%c",a[i]);
}
void display1(char p[],int m) //Displays The Present Input String
{
  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]=  {"$","$","TH","$","TH","$",
      "+TH","$","e","e","$","e",
      "$","$","FU","$","FU","$",
      "e","*FU","e","e","$","e",
      "$","$","(E)","$","i","$"};
 printf("\nEnter any String(Append with $)");
 gets(ip);
 printf("Stack\tInput\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 && j==strlen(ip)-1)
  printf("\nGiven String is accepted");
 else
  printf("\nGiven String is not accepted");
 return 0;
}

making change using dynamic

#include<stdio.h>
int main()
{
    int n,C,d[10],i,j,V[15][15],b[15][15];
    printf("enter maximum change");
    scanf("%d",&C);
    printf("enter no. of elements");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&d[i]);
    }
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=C;j++)
        {
            if(i==0 || j==0)
            {
                //printf("A\n");
                if(i==0)
                    V[i][j]=65535;
                else
                    V[i][j]=0;
            }
            else if(j<d[i-1])
            {
                //printf("B\n");
                V[i][j]=V[i-1][j];
                b[i][j]=j;
            }
            else
            {
                //printf("C\n");
                if(V[i-1][j]<((V[i][j-d[i-1]])+1))
                {
                    V[i][j]=V[i-1][j];
                    b[i][j]=j;
                }
                else
                {
                    V[i][j]=V[i][j-d[i-1]]+1;
                    b[i][j]=j-d[i-1];
                }
            }
            //printf("%d %d %d\n",i,j,V[i][j]);
        }
    }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=C;j++)
            {
                printf("%d ",V[i][j]);
            }
            printf("\n");
        }
        printf("\nminimum coins used is %d\n",V[n][C]);
        i=n;
        j=C;
        while(j!=0)
        {
            if(V[i][j]==V[i-1][j])
                i--;
            else
            {
                printf("%d\t",d[i-1]);
                j=b[i][j];
              
            }
        }
    return 0;
}

matrix chain multiplication using dynamic

#include<stdio.h>
int p[10],m[10][10],s[10][10];
void matrix_chain_order(int n)
{
    int i,j,k,l,q;
//    n=p.length-1;
    for(i=1;i<n;i++)
    m[i][i]=0;
    for(l=2;l<=n;l++)
    {
        for(i=1;i<=n-l+1;i++)
        {
            j=i+l-1;
            m[i][j]=99999;
            //printf("%d\t%d\t%d\n",i,l,j);
            for(k=i;k<=j-1;k++)
            {
                q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(q<m[i][j])
                {
                    m[i][j]=q;
                    s[i][j]=k;
                    //printf("%d\t%d\t%d\t%d\n",i,j,k,m[i][j]);
                }
            }
        }
      
    }
    for(i=0;i<n;i++)
    {
        for(j=n;j>i;j--)
        {
            printf("%d %d\t",m[i][j],s[i][j]);
        }
        printf("\n");
    }
  
    printf("\n\n\n");
}

void PRINT_OPTIMAL_PARENS(i,j)
{
    if(i == j)
     printf("A%d",i);
    else
    {
        printf("(");
    PRINT_OPTIMAL_PARENS(i,s[i][j]);
    PRINT_OPTIMAL_PARENS(s[i][j]+1,j);
    printf(")");
    }

}
int main()
{
    int i,n;
    printf("enter no. of matrices");
    scanf("%d",&n);
    printf("enter sizes of matrix");
    for(i=0;i<=n;i++)
    scanf("%d",&p[i]);
    matrix_chain_order(n);
    PRINT_OPTIMAL_PARENS(1,6);
    return 0;
}

knapsack using dynamic

 //knapsack using dynamic
#include<stdio.h>
int main()
{
    int n,W,w[10],v[10],i,j,V[15][15];
    printf("enter capacity of knapsack");
    scanf("%d",&W);
    printf("enter no. of elements");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d %d",&w[i],&v[i]);
    }
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=W;j++)
        {
            if(i==0 || j==0)
            V[i][j]=0;
            else if((j-w[i-1])<0)
            V[i][j]=V[i-1][j] ;
            else
            {
                if(V[i-1][j]<V[i-1][j-w[i-1]]+v[i-1])
                V[i][j]=V[i-1][j-w[i-1]]+v[i-1];
                else
                V[i][j]=V[i-1][j];          
            }
        }
    }
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=W;j++)
            {
                printf("%d ",V[i][j]);
            }
            printf("\n");
        }
        printf("\nmax profit earned is %d\n",V[n][W]);
    return 0;
}

recursive_descent_parsing

#include<stdio.h>
#include<string.h>
char in[50];
int j=0,f=0;
void PE1();
void PT();
void PT1();
void PF();
void match(char c);
void PE()
{
//printf("Enter PE\n");
PT();
PE1();
printf("E->TE1\n");
}
void PE1()
{
//printf("Enter PE1\n");
char c=in[j];
if(c=='+')
{
match('+');
PT();
PE1();
}
else
printf("E1->NULL\n");
printf("E1->+TE1 | ^\n");
}
void PT()
{
//printf("Enter PT\n");
PF();
PT1();
printf("T->FT1\n");
}
void PT1()
{
//printf("Enter PT1\n");
int f=0;
char c=in[j];
if(c=='*')
{
match('*');
PF();
PT1();
}
else
printf("T1->NULL\n");
printf("T1->*FT1 | ^\n");
}
void PF()
{
//printf("Enter PF\n");
char c=in[j];
if(c=='(')
{
match('(');
PE();
match(')');
}
else if((c>='a' && c<='z')|| (c>='A' && c<='Z'))
match(c);
printf("F->(E)|i\n");
}
void match(char c)
{
if(j<=strlen(in))
{
if(in[j]==c)
{
printf("matched %c\n",c);
j++;
}
else
printf("Error\n");
}
}
int main()
{
scanf("%s",in);
PE();
if(in[j]=='\0')
printf("correct\n");
else
printf("Syntax error\nUnidentified symbol %c\n",in[j]);
return 0;
}

- Jinay Shah