1c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 2c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel/* Computation of FIRST stets */ 3c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 4c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel#include "pgenheaders.h" 5c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel#include "grammar.h" 6c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel#include "token.h" 7c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 8c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDanielextern int Py_DebugFlag; 9c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 10c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel/* Forward */ 11c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDanielstatic void calcfirstset(grammar *, dfa *); 12c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 13c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDanielvoid 14c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDanieladdfirstsets(grammar *g) 15c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel{ 16c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel int i; 17c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel dfa *d; 18c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 19c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (Py_DebugFlag) 20c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel printf("Adding FIRST sets ...\n"); 21c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel for (i = 0; i < g->g_ndfas; i++) { 22c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel d = &g->g_dfa[i]; 23c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (d->d_first == NULL) 24c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel calcfirstset(g, d); 25c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel } 26c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel} 27c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 28c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDanielstatic void 29c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDanielcalcfirstset(grammar *g, dfa *d) 30c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel{ 31c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel int i, j; 32c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel state *s; 33c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel arc *a; 34c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel int nsyms; 35c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel int *sym; 36c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel int nbits; 37c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel static bitset dummy; 38c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel bitset result; 39c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel int type; 40c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel dfa *d1; 41c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel label *l0; 42c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 43c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (Py_DebugFlag) 44c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel printf("Calculate FIRST set for '%s'\n", d->d_name); 45c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 46c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (dummy == NULL) 47c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel dummy = newbitset(1); 48c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (d->d_first == dummy) { 49c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel fprintf(stderr, "Left-recursion for '%s'\n", d->d_name); 50c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel return; 51c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel } 52c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (d->d_first != NULL) { 53c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel fprintf(stderr, "Re-calculating FIRST set for '%s' ???\n", 54c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel d->d_name); 55c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel } 56c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel d->d_first = dummy; 57c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 58c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel l0 = g->g_ll.ll_label; 59c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel nbits = g->g_ll.ll_nlabels; 60c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel result = newbitset(nbits); 61c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 62c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel sym = (int *)PyObject_MALLOC(sizeof(int)); 63c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (sym == NULL) 64c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel Py_FatalError("no mem for new sym in calcfirstset"); 65c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel nsyms = 1; 66c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel sym[0] = findlabel(&g->g_ll, d->d_type, (char *)NULL); 67c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 68c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel s = &d->d_state[d->d_initial]; 69c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel for (i = 0; i < s->s_narcs; i++) { 70c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel a = &s->s_arc[i]; 71c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel for (j = 0; j < nsyms; j++) { 72c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (sym[j] == a->a_lbl) 73c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel break; 74c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel } 75c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (j >= nsyms) { /* New label */ 76c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel sym = (int *)PyObject_REALLOC(sym, 77c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel sizeof(int) * (nsyms + 1)); 78c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (sym == NULL) 79c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel Py_FatalError( 80c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel "no mem to resize sym in calcfirstset"); 81c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel sym[nsyms++] = a->a_lbl; 82c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel type = l0[a->a_lbl].lb_type; 83c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (ISNONTERMINAL(type)) { 84c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel d1 = PyGrammar_FindDFA(g, type); 85c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (d1->d_first == dummy) { 86c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel fprintf(stderr, 87c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel "Left-recursion below '%s'\n", 88c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel d->d_name); 89c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel } 90c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel else { 91c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (d1->d_first == NULL) 92c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel calcfirstset(g, d1); 93c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel mergebitset(result, 94c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel d1->d_first, nbits); 95c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel } 96c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel } 97c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel else if (ISTERMINAL(type)) { 98c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel addbit(result, a->a_lbl); 99c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel } 100c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel } 101c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel } 102c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel d->d_first = result; 103c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (Py_DebugFlag) { 104c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel printf("FIRST set for '%s': {", d->d_name); 105c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel for (i = 0; i < nbits; i++) { 106c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel if (testbit(result, i)) 107c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel printf(" %s", PyGrammar_LabelRepr(&l0[i])); 108c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel } 109c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel printf(" }\n"); 110c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel } 111c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel 112c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel PyObject_FREE(sym); 113c8042e10763bca064df257547d04ae3dfcdfaf91Daryl McDaniel} 114