%{
#include<stdio.h>
#include<string.h>
#define STEP 2
#define yyerror printf
#define YYSTYPE int

extern char* yytext;


/* Cvor pretrazivackog drveta koje sadrzi neterminale i njihove kodove */

typedef struct NC
{   char* Net;
    int Code;
    struct NC *left, *right;
} NCNODE;

/* Koren drveta kodova neterminala  */
NCNODE* nctree=NULL;

/* Pomocna promenjiva koja pamti kod neterminala koji se pojavio 
   sa leve strane pravila koje se upravo obradjuje */
int leftnet;

/* Relaciju izvodjenja pamtimo u dinamickoj matrici */ 
typedef struct RL
{   int **rel; /* Elementi matrice (0 ili 1) */
    int size;  /* Velicina alociranog prostora za matricu */
} RELATION;

/* Relacija izvodjenja */
RELATION relation;

/* Najveci kod neterminala koji smo do sada pronasli */
int max_net_code=0;

/* Funkcije za rad sa drvetom kodova neterminala */
NCNODE* newNC(char*);
void  deleteNC(NCNODE*);
int   findNCode(NCNODE*, char*);
char* findNName(NCNODE*, int);

/* Funkcije za rad sa dinamickom matricom */
void reallocateR(RELATION*,int);
void printR(RELATION*);
void deleteR(RELATION*);
void setR(RELATION*,int,int);
void warshallR(RELATION*);
%}

%token ARROW SEMI TERM NETERM BAR
%start rules
%%
rules	:   rule rules
        |
        ;

rule    : neterm {leftnet=$1; /* Upamtimo ovaj neterminal*/ } ARROW rightsides SEMI
        ;

rightsides   : rightside BAR rightsides
             | rightside
             ;

rightside    :  neterm {setR(&relation, leftnet,$1); /* Modifikujemo relaciju izvodjenja */} rightside 
             |  TERM rightside 
             |
             ;

neterm  : NETERM { /* Odredjujemo kod ovog neterminala. Ako ne postoji u drvetu, novi cvor se pravi */
                   /* Kod se zatim postavlja na interni stek */
                   if (nctree!=NULL)
                     $$=findNCode(nctree,yytext);
                   else 
                   { nctree=newNC(yytext);
                     $$=nctree->Code;
                   }
                 }

%%

main()
{   int i;
    /* Relacija izvodjenja je prazna u pocetku */
    relation.size=0;
    relation.rel=NULL;

    printf("Pocinje parsiranje ...\n");
    yyparse();
    printf("Gotovo parsiranje \n");


    printR(&relation);

    /* Nalazimo tranzitivno zatvorenje relacije izvodjenja */
    warshallR(&relation);

    printf("Tranzitivno zatvorenje je : \n");
    printR(&relation);    

    /* Neterminal je tranzitivan ako je u R+ sam sa sobom */
   for (i=0; i<max_net_code; i++)
      if (relation.rel[i][i])
	printf("%s je rekurzivan\n",findNName(nctree,i));

    /* Uklanjamo relaciju */
    deleteR(&relation);

    /* Uklanjamo kodove neterminala */
    deleteNC(nctree);
}


/* Funkcija koja kreira novi cvor drveta kodova na osnovu imena neterminala.
   Kod je prvi prirodan broj koji ne predstavlja vec kod nekog neterminala */
NCNODE* newNC(char* n)
{   NCNODE* t=(NCNODE*)malloc(sizeof(NCNODE));
    t->Net=strdup(n);
    t->Code=max_net_code++;
    t->left=t->right=NULL;
    return t;
}


/* Funkcija koja uklanja drvo na koje pokazuje pokazivac n */
void deleteNC(NCNODE* n)
{ if (n!=NULL)
  {  deleteNC(n->left);
     deleteNC(n->right);
     free(n);
  }
}

/* Koristeci sortiranost po abecedi, funkcija vraca kod neterminala cije joj je ime 
   prosledjeno */
int findNCode (NCNODE* t,char* n)
{   int cmp=strcmp(t->Net,n);
    if (cmp==0)
       return t->Code;
    else if (cmp<0)
         {  if (t->left!=NULL)
                return findNCode(t->left,n);
            else 
            {   t->left=newNC(n);
                return t->left->Code;
            }
         }
         else
         {  if (t->right!=NULL)
                return findNCode(t->right,n);
            else 
            {   t->right=newNC(n);
                return t->right->Code;
            }
         }
}


/* Funkcija nalazi ime neterminala na osnovu prosledjenog koda */
char* findNName (NCNODE* t, int c)
{  char* f;
   if (t==NULL) return NULL;
   if (t->Code==c)
      return t->Net;
   f=findNName(t->left,c);
   if (f) return f;
   f=findNName(t->right,c);
   if (f) return f;
   return NULL;
}


/* Funkcija vrsi realociranje dinamicke matrice na velicinu sxs */
void reallocateR(RELATION* R, int s)
{   int i,j;
    int **newR;

    if (R->size>=s) 
       return;
   
    /* Kreiramo novu, vecu matricu */
    newR=(int**)malloc(s*sizeof(int*));
    for(i=0; i<s; i++)
       newR[i]=(int*)malloc(s*sizeof(int));
    
    /* Kopiramo elemente stare matrice, a na ostala mesta upisujemo 0 */
    for(i=0; i<R->size; i++)
    {   for(j=0; j<R->size; j++)
           newR[i][j]=R->rel[i][j];
        for( ; j<s; j++)
           newR[i][j]=0;
    }
    for ( ; i<s; i++)
       for(j=0; j<s; j++)
	  newR[i][j]=0;

    /* Brisemo staru matricu */ 
    deleteR(R);
    
    /* Sadrzaj postavljamo na novu matricu i azuriramo velicinu */
    R->rel=newR;
    R->size=s;
}


/* Funkcija brise dinamicku matricu */
void deleteR(RELATION* R)
{  int i;
   if (R->rel==NULL) return;
   for(i=0; i<R->size; i++)
      free(R->rel[i]);
   free(R->rel);
}

/* Funkcija za ispis matrice na ekran. Ne ispisuje se sadrzaj cele 
   matrice, vec samo onog dela koji se odnosi na koriscene neterminale  */
void printR(RELATION* R)
{  int i,j;
   for(i=0; i<max_net_code; i++)
   {  for(j=0; j<max_net_code; j++)
         printf("%d ",R->rel[i][j]); 
      printf("\n");
   }    
}

/* Funkcija postavlja polje R->rel [i][j] na 1. Ako polje ne postoji, 
   vrsi se realokacija memorije */ 
void setR(RELATION *R, int i, int j)
{  /* m je veci od brojeva i i j */
   int m=i;
   if (j>m) m=j;

   if (m>=R->size)
     reallocateR(R,m+STEP);
   R->rel[i][j]=1;   
}


/* Varsalovim algoritmom se konstruise tranzitivno zatvorenje relacije */
void warshallR(RELATION *R)
{  int i,j,k;
   for (k=0; k<R->size; k++)   
     for (i=0; i<R->size; i++)   
       for (j=0; j<R->size; j++)
	 if (R->rel[i][k] && R->rel[k][j])
	    R->rel[i][j]=1;
}
