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

#define MAXNET 50

extern char* yytext;


char* neterms[MAXNET];
int relation[MAXNET][MAXNET];

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

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

int findNCode(char*);
void warshall(int[][]);
%}

%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 {relation[leftnet][$1]=1; /* Modifikujemo relaciju izvodjenja */} rightside 
             |  TERM rightside 
             |
             ;

neterm  : NETERM { /* Odredjujemo kod ovog neterminala. Ako neterminal ne postoji u nizu, dodaje se */
                   /* Kod se zatim postavlja na interni stek */
                   $$=findNCode(yytext);
                 }

%%

main()
{   int i,j;
    /* Relacija izvodjenja je prazna u pocetku */
    for (i=0; i<MAXNET; i++)
      for (j=0; j<MAXNET; j++)
	relation[i][j]=0;

    yyparse();

    /* Nalazimo tranzitivno zatvorenje relacije izvodjenja */
    warshall(relation);

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


int findNCode (char* n)
{   int i;
    for (i=0; i<max_net_code; i++)
      if (strcmp(neterms[i],n)==0)
	return i;
    neterms[max_net_code]=strdup(n);
    return max_net_code++;
}


/* Varsalovim algoritmom se konstruise tranzitivno zatvorenje relacije */
void warshall(int rel[MAXNET][MAXNET])
{  int i,j,k;
   for (k=0; k<max_net_code; k++)   
     for (i=0; i<max_net_code; i++)   
       for (j=0; j<max_net_code; j++)
	 if (rel[i][k] && rel[k][j])
	    rel[i][j]=1;
}
