14710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 24710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Computation of FIRST stets */ 34710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 44710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#include "pgenheaders.h" 54710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#include "grammar.h" 64710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm#include "token.h" 74710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 84710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmextern int Py_DebugFlag; 94710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm/* Forward */ 114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic void calcfirstset(grammar *, dfa *); 124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmvoid 144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmaddfirstsets(grammar *g) 154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int i; 174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dfa *d; 184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (Py_DebugFlag) 204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm printf("Adding FIRST sets ...\n"); 214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (i = 0; i < g->g_ndfas; i++) { 224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm d = &g->g_dfa[i]; 234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (d->d_first == NULL) 244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm calcfirstset(g, d); 254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmstatic void 294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmcalcfirstset(grammar *g, dfa *d) 304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm{ 314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int i, j; 324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm state *s; 334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm arc *a; 344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int nsyms; 354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int *sym; 364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int nbits; 374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm static bitset dummy; 384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm bitset result; 394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm int type; 404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dfa *d1; 414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm label *l0; 424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (Py_DebugFlag) 444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm printf("Calculate FIRST set for '%s'\n", d->d_name); 454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (dummy == NULL) 474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dummy = newbitset(1); 484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (d->d_first == dummy) { 494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm fprintf(stderr, "Left-recursion for '%s'\n", d->d_name); 504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return; 514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (d->d_first != NULL) { 534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm fprintf(stderr, "Re-calculating FIRST set for '%s' ???\n", 544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm d->d_name); 554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm d->d_first = dummy; 574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm l0 = g->g_ll.ll_label; 594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm nbits = g->g_ll.ll_nlabels; 604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = newbitset(nbits); 614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sym = (int *)PyObject_MALLOC(sizeof(int)); 634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (sym == NULL) 644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_FatalError("no mem for new sym in calcfirstset"); 654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm nsyms = 1; 664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sym[0] = findlabel(&g->g_ll, d->d_type, (char *)NULL); 674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm s = &d->d_state[d->d_initial]; 694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (i = 0; i < s->s_narcs; i++) { 704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm a = &s->s_arc[i]; 714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (j = 0; j < nsyms; j++) { 724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (sym[j] == a->a_lbl) 734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm break; 744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (j >= nsyms) { /* New label */ 764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sym = (int *)PyObject_REALLOC(sym, 774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sizeof(int) * (nsyms + 1)); 784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (sym == NULL) 794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Py_FatalError( 804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "no mem to resize sym in calcfirstset"); 814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm sym[nsyms++] = a->a_lbl; 824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm type = l0[a->a_lbl].lb_type; 834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (ISNONTERMINAL(type)) { 844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm d1 = PyGrammar_FindDFA(g, type); 854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (d1->d_first == dummy) { 864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm fprintf(stderr, 874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "Left-recursion below '%s'\n", 884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm d->d_name); 894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else { 914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (d1->d_first == NULL) 924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm calcfirstset(g, d1); 934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm mergebitset(result, 944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm d1->d_first, nbits); 954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else if (ISTERMINAL(type)) { 984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm addbit(result, a->a_lbl); 994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm d->d_first = result; 1034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (Py_DebugFlag) { 1044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm printf("FIRST set for '%s': {", d->d_name); 1054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for (i = 0; i < nbits; i++) { 1064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (testbit(result, i)) 1074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm printf(" %s", PyGrammar_LabelRepr(&l0[i])); 1084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm printf(" }\n"); 1104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm } 1114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PyObject_FREE(sym); 1134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm} 114