+++ /dev/null
-/* Parser generator */\r
-\r
-/* For a description, see the comments at end of this file */\r
-\r
-#include "Python.h"\r
-#include "pgenheaders.h"\r
-#include "token.h"\r
-#include "node.h"\r
-#include "grammar.h"\r
-#include "metagrammar.h"\r
-#include "pgen.h"\r
-\r
-extern int Py_DebugFlag;\r
-extern int Py_IgnoreEnvironmentFlag; /* needed by Py_GETENV */\r
-\r
-\r
-/* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */\r
-\r
-typedef struct _nfaarc {\r
- int ar_label;\r
- int ar_arrow;\r
-} nfaarc;\r
-\r
-typedef struct _nfastate {\r
- int st_narcs;\r
- nfaarc *st_arc;\r
-} nfastate;\r
-\r
-typedef struct _nfa {\r
- int nf_type;\r
- char *nf_name;\r
- int nf_nstates;\r
- nfastate *nf_state;\r
- int nf_start, nf_finish;\r
-} nfa;\r
-\r
-/* Forward */\r
-static void compile_rhs(labellist *ll,\r
- nfa *nf, node *n, int *pa, int *pb);\r
-static void compile_alt(labellist *ll,\r
- nfa *nf, node *n, int *pa, int *pb);\r
-static void compile_item(labellist *ll,\r
- nfa *nf, node *n, int *pa, int *pb);\r
-static void compile_atom(labellist *ll,\r
- nfa *nf, node *n, int *pa, int *pb);\r
-\r
-static int\r
-addnfastate(nfa *nf)\r
-{\r
- nfastate *st;\r
-\r
- nf->nf_state = (nfastate *)PyObject_REALLOC(nf->nf_state,\r
- sizeof(nfastate) * (nf->nf_nstates + 1));\r
- if (nf->nf_state == NULL)\r
- Py_FatalError("out of mem");\r
- st = &nf->nf_state[nf->nf_nstates++];\r
- st->st_narcs = 0;\r
- st->st_arc = NULL;\r
- return st - nf->nf_state;\r
-}\r
-\r
-static void\r
-addnfaarc(nfa *nf, int from, int to, int lbl)\r
-{\r
- nfastate *st;\r
- nfaarc *ar;\r
-\r
- st = &nf->nf_state[from];\r
- st->st_arc = (nfaarc *)PyObject_REALLOC(st->st_arc,\r
- sizeof(nfaarc) * (st->st_narcs + 1));\r
- if (st->st_arc == NULL)\r
- Py_FatalError("out of mem");\r
- ar = &st->st_arc[st->st_narcs++];\r
- ar->ar_label = lbl;\r
- ar->ar_arrow = to;\r
-}\r
-\r
-static nfa *\r
-newnfa(char *name)\r
-{\r
- nfa *nf;\r
- static int type = NT_OFFSET; /* All types will be disjunct */\r
-\r
- nf = (nfa *)PyObject_MALLOC(sizeof(nfa));\r
- if (nf == NULL)\r
- Py_FatalError("no mem for new nfa");\r
- nf->nf_type = type++;\r
- nf->nf_name = name; /* XXX strdup(name) ??? */\r
- nf->nf_nstates = 0;\r
- nf->nf_state = NULL;\r
- nf->nf_start = nf->nf_finish = -1;\r
- return nf;\r
-}\r
-\r
-typedef struct _nfagrammar {\r
- int gr_nnfas;\r
- nfa **gr_nfa;\r
- labellist gr_ll;\r
-} nfagrammar;\r
-\r
-/* Forward */\r
-static void compile_rule(nfagrammar *gr, node *n);\r
-\r
-static nfagrammar *\r
-newnfagrammar(void)\r
-{\r
- nfagrammar *gr;\r
-\r
- gr = (nfagrammar *)PyObject_MALLOC(sizeof(nfagrammar));\r
- if (gr == NULL)\r
- Py_FatalError("no mem for new nfa grammar");\r
- gr->gr_nnfas = 0;\r
- gr->gr_nfa = NULL;\r
- gr->gr_ll.ll_nlabels = 0;\r
- gr->gr_ll.ll_label = NULL;\r
- addlabel(&gr->gr_ll, ENDMARKER, "EMPTY");\r
- return gr;\r
-}\r
-\r
-static nfa *\r
-addnfa(nfagrammar *gr, char *name)\r
-{\r
- nfa *nf;\r
-\r
- nf = newnfa(name);\r
- gr->gr_nfa = (nfa **)PyObject_REALLOC(gr->gr_nfa,\r
- sizeof(nfa*) * (gr->gr_nnfas + 1));\r
- if (gr->gr_nfa == NULL)\r
- Py_FatalError("out of mem");\r
- gr->gr_nfa[gr->gr_nnfas++] = nf;\r
- addlabel(&gr->gr_ll, NAME, nf->nf_name);\r
- return nf;\r
-}\r
-\r
-#ifdef Py_DEBUG\r
-\r
-static char REQNFMT[] = "metacompile: less than %d children\n";\r
-\r
-#define REQN(i, count) \\r
- if (i < count) { \\r
- fprintf(stderr, REQNFMT, count); \\r
- Py_FatalError("REQN"); \\r
- } else\r
-\r
-#else\r
-#define REQN(i, count) /* empty */\r
-#endif\r
-\r
-static nfagrammar *\r
-metacompile(node *n)\r
-{\r
- nfagrammar *gr;\r
- int i;\r
-\r
- if (Py_DebugFlag)\r
- printf("Compiling (meta-) parse tree into NFA grammar\n");\r
- gr = newnfagrammar();\r
- REQ(n, MSTART);\r
- i = n->n_nchildren - 1; /* Last child is ENDMARKER */\r
- n = n->n_child;\r
- for (; --i >= 0; n++) {\r
- if (n->n_type != NEWLINE)\r
- compile_rule(gr, n);\r
- }\r
- return gr;\r
-}\r
-\r
-static void\r
-compile_rule(nfagrammar *gr, node *n)\r
-{\r
- nfa *nf;\r
-\r
- REQ(n, RULE);\r
- REQN(n->n_nchildren, 4);\r
- n = n->n_child;\r
- REQ(n, NAME);\r
- nf = addnfa(gr, n->n_str);\r
- n++;\r
- REQ(n, COLON);\r
- n++;\r
- REQ(n, RHS);\r
- compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);\r
- n++;\r
- REQ(n, NEWLINE);\r
-}\r
-\r
-static void\r
-compile_rhs(labellist *ll, nfa *nf, node *n, int *pa, int *pb)\r
-{\r
- int i;\r
- int a, b;\r
-\r
- REQ(n, RHS);\r
- i = n->n_nchildren;\r
- REQN(i, 1);\r
- n = n->n_child;\r
- REQ(n, ALT);\r
- compile_alt(ll, nf, n, pa, pb);\r
- if (--i <= 0)\r
- return;\r
- n++;\r
- a = *pa;\r
- b = *pb;\r
- *pa = addnfastate(nf);\r
- *pb = addnfastate(nf);\r
- addnfaarc(nf, *pa, a, EMPTY);\r
- addnfaarc(nf, b, *pb, EMPTY);\r
- for (; --i >= 0; n++) {\r
- REQ(n, VBAR);\r
- REQN(i, 1);\r
- --i;\r
- n++;\r
- REQ(n, ALT);\r
- compile_alt(ll, nf, n, &a, &b);\r
- addnfaarc(nf, *pa, a, EMPTY);\r
- addnfaarc(nf, b, *pb, EMPTY);\r
- }\r
-}\r
-\r
-static void\r
-compile_alt(labellist *ll, nfa *nf, node *n, int *pa, int *pb)\r
-{\r
- int i;\r
- int a, b;\r
-\r
- REQ(n, ALT);\r
- i = n->n_nchildren;\r
- REQN(i, 1);\r
- n = n->n_child;\r
- REQ(n, ITEM);\r
- compile_item(ll, nf, n, pa, pb);\r
- --i;\r
- n++;\r
- for (; --i >= 0; n++) {\r
- REQ(n, ITEM);\r
- compile_item(ll, nf, n, &a, &b);\r
- addnfaarc(nf, *pb, a, EMPTY);\r
- *pb = b;\r
- }\r
-}\r
-\r
-static void\r
-compile_item(labellist *ll, nfa *nf, node *n, int *pa, int *pb)\r
-{\r
- int i;\r
- int a, b;\r
-\r
- REQ(n, ITEM);\r
- i = n->n_nchildren;\r
- REQN(i, 1);\r
- n = n->n_child;\r
- if (n->n_type == LSQB) {\r
- REQN(i, 3);\r
- n++;\r
- REQ(n, RHS);\r
- *pa = addnfastate(nf);\r
- *pb = addnfastate(nf);\r
- addnfaarc(nf, *pa, *pb, EMPTY);\r
- compile_rhs(ll, nf, n, &a, &b);\r
- addnfaarc(nf, *pa, a, EMPTY);\r
- addnfaarc(nf, b, *pb, EMPTY);\r
- REQN(i, 1);\r
- n++;\r
- REQ(n, RSQB);\r
- }\r
- else {\r
- compile_atom(ll, nf, n, pa, pb);\r
- if (--i <= 0)\r
- return;\r
- n++;\r
- addnfaarc(nf, *pb, *pa, EMPTY);\r
- if (n->n_type == STAR)\r
- *pb = *pa;\r
- else\r
- REQ(n, PLUS);\r
- }\r
-}\r
-\r
-static void\r
-compile_atom(labellist *ll, nfa *nf, node *n, int *pa, int *pb)\r
-{\r
- int i;\r
-\r
- REQ(n, ATOM);\r
- i = n->n_nchildren;\r
- REQN(i, 1);\r
- n = n->n_child;\r
- if (n->n_type == LPAR) {\r
- REQN(i, 3);\r
- n++;\r
- REQ(n, RHS);\r
- compile_rhs(ll, nf, n, pa, pb);\r
- n++;\r
- REQ(n, RPAR);\r
- }\r
- else if (n->n_type == NAME || n->n_type == STRING) {\r
- *pa = addnfastate(nf);\r
- *pb = addnfastate(nf);\r
- addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str));\r
- }\r
- else\r
- REQ(n, NAME);\r
-}\r
-\r
-static void\r
-dumpstate(labellist *ll, nfa *nf, int istate)\r
-{\r
- nfastate *st;\r
- int i;\r
- nfaarc *ar;\r
-\r
- printf("%c%2d%c",\r
- istate == nf->nf_start ? '*' : ' ',\r
- istate,\r
- istate == nf->nf_finish ? '.' : ' ');\r
- st = &nf->nf_state[istate];\r
- ar = st->st_arc;\r
- for (i = 0; i < st->st_narcs; i++) {\r
- if (i > 0)\r
- printf("\n ");\r
- printf("-> %2d %s", ar->ar_arrow,\r
- PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));\r
- ar++;\r
- }\r
- printf("\n");\r
-}\r
-\r
-static void\r
-dumpnfa(labellist *ll, nfa *nf)\r
-{\r
- int i;\r
-\r
- printf("NFA '%s' has %d states; start %d, finish %d\n",\r
- nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);\r
- for (i = 0; i < nf->nf_nstates; i++)\r
- dumpstate(ll, nf, i);\r
-}\r
-\r
-\r
-/* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */\r
-\r
-static void\r
-addclosure(bitset ss, nfa *nf, int istate)\r
-{\r
- if (addbit(ss, istate)) {\r
- nfastate *st = &nf->nf_state[istate];\r
- nfaarc *ar = st->st_arc;\r
- int i;\r
-\r
- for (i = st->st_narcs; --i >= 0; ) {\r
- if (ar->ar_label == EMPTY)\r
- addclosure(ss, nf, ar->ar_arrow);\r
- ar++;\r
- }\r
- }\r
-}\r
-\r
-typedef struct _ss_arc {\r
- bitset sa_bitset;\r
- int sa_arrow;\r
- int sa_label;\r
-} ss_arc;\r
-\r
-typedef struct _ss_state {\r
- bitset ss_ss;\r
- int ss_narcs;\r
- struct _ss_arc *ss_arc;\r
- int ss_deleted;\r
- int ss_finish;\r
- int ss_rename;\r
-} ss_state;\r
-\r
-typedef struct _ss_dfa {\r
- int sd_nstates;\r
- ss_state *sd_state;\r
-} ss_dfa;\r
-\r
-/* Forward */\r
-static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits,\r
- labellist *ll, char *msg);\r
-static void simplify(int xx_nstates, ss_state *xx_state);\r
-static void convert(dfa *d, int xx_nstates, ss_state *xx_state);\r
-\r
-static void\r
-makedfa(nfagrammar *gr, nfa *nf, dfa *d)\r
-{\r
- int nbits = nf->nf_nstates;\r
- bitset ss;\r
- int xx_nstates;\r
- ss_state *xx_state, *yy;\r
- ss_arc *zz;\r
- int istate, jstate, iarc, jarc, ibit;\r
- nfastate *st;\r
- nfaarc *ar;\r
-\r
- ss = newbitset(nbits);\r
- addclosure(ss, nf, nf->nf_start);\r
- xx_state = (ss_state *)PyObject_MALLOC(sizeof(ss_state));\r
- if (xx_state == NULL)\r
- Py_FatalError("no mem for xx_state in makedfa");\r
- xx_nstates = 1;\r
- yy = &xx_state[0];\r
- yy->ss_ss = ss;\r
- yy->ss_narcs = 0;\r
- yy->ss_arc = NULL;\r
- yy->ss_deleted = 0;\r
- yy->ss_finish = testbit(ss, nf->nf_finish);\r
- if (yy->ss_finish)\r
- printf("Error: nonterminal '%s' may produce empty.\n",\r
- nf->nf_name);\r
-\r
- /* This algorithm is from a book written before\r
- the invention of structured programming... */\r
-\r
- /* For each unmarked state... */\r
- for (istate = 0; istate < xx_nstates; ++istate) {\r
- size_t size;\r
- yy = &xx_state[istate];\r
- ss = yy->ss_ss;\r
- /* For all its states... */\r
- for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {\r
- if (!testbit(ss, ibit))\r
- continue;\r
- st = &nf->nf_state[ibit];\r
- /* For all non-empty arcs from this state... */\r
- for (iarc = 0; iarc < st->st_narcs; iarc++) {\r
- ar = &st->st_arc[iarc];\r
- if (ar->ar_label == EMPTY)\r
- continue;\r
- /* Look up in list of arcs from this state */\r
- for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {\r
- zz = &yy->ss_arc[jarc];\r
- if (ar->ar_label == zz->sa_label)\r
- goto found;\r
- }\r
- /* Add new arc for this state */\r
- size = sizeof(ss_arc) * (yy->ss_narcs + 1);\r
- yy->ss_arc = (ss_arc *)PyObject_REALLOC(\r
- yy->ss_arc, size);\r
- if (yy->ss_arc == NULL)\r
- Py_FatalError("out of mem");\r
- zz = &yy->ss_arc[yy->ss_narcs++];\r
- zz->sa_label = ar->ar_label;\r
- zz->sa_bitset = newbitset(nbits);\r
- zz->sa_arrow = -1;\r
- found: ;\r
- /* Add destination */\r
- addclosure(zz->sa_bitset, nf, ar->ar_arrow);\r
- }\r
- }\r
- /* Now look up all the arrow states */\r
- for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {\r
- zz = &xx_state[istate].ss_arc[jarc];\r
- for (jstate = 0; jstate < xx_nstates; jstate++) {\r
- if (samebitset(zz->sa_bitset,\r
- xx_state[jstate].ss_ss, nbits)) {\r
- zz->sa_arrow = jstate;\r
- goto done;\r
- }\r
- }\r
- size = sizeof(ss_state) * (xx_nstates + 1);\r
- xx_state = (ss_state *)PyObject_REALLOC(xx_state,\r
- size);\r
- if (xx_state == NULL)\r
- Py_FatalError("out of mem");\r
- zz->sa_arrow = xx_nstates;\r
- yy = &xx_state[xx_nstates++];\r
- yy->ss_ss = zz->sa_bitset;\r
- yy->ss_narcs = 0;\r
- yy->ss_arc = NULL;\r
- yy->ss_deleted = 0;\r
- yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish);\r
- done: ;\r
- }\r
- }\r
-\r
- if (Py_DebugFlag)\r
- printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,\r
- "before minimizing");\r
-\r
- simplify(xx_nstates, xx_state);\r
-\r
- if (Py_DebugFlag)\r
- printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,\r
- "after minimizing");\r
-\r
- convert(d, xx_nstates, xx_state);\r
-\r
- /* XXX cleanup */\r
- PyObject_FREE(xx_state);\r
-}\r
-\r
-static void\r
-printssdfa(int xx_nstates, ss_state *xx_state, int nbits,\r
- labellist *ll, char *msg)\r
-{\r
- int i, ibit, iarc;\r
- ss_state *yy;\r
- ss_arc *zz;\r
-\r
- printf("Subset DFA %s\n", msg);\r
- for (i = 0; i < xx_nstates; i++) {\r
- yy = &xx_state[i];\r
- if (yy->ss_deleted)\r
- continue;\r
- printf(" Subset %d", i);\r
- if (yy->ss_finish)\r
- printf(" (finish)");\r
- printf(" { ");\r
- for (ibit = 0; ibit < nbits; ibit++) {\r
- if (testbit(yy->ss_ss, ibit))\r
- printf("%d ", ibit);\r
- }\r
- printf("}\n");\r
- for (iarc = 0; iarc < yy->ss_narcs; iarc++) {\r
- zz = &yy->ss_arc[iarc];\r
- printf(" Arc to state %d, label %s\n",\r
- zz->sa_arrow,\r
- PyGrammar_LabelRepr(\r
- &ll->ll_label[zz->sa_label]));\r
- }\r
- }\r
-}\r
-\r
-\r
-/* PART THREE -- SIMPLIFY DFA */\r
-\r
-/* Simplify the DFA by repeatedly eliminating states that are\r
- equivalent to another oner. This is NOT Algorithm 3.3 from\r
- [Aho&Ullman 77]. It does not always finds the minimal DFA,\r
- but it does usually make a much smaller one... (For an example\r
- of sub-optimal behavior, try S: x a b+ | y a b+.)\r
-*/\r
-\r
-static int\r
-samestate(ss_state *s1, ss_state *s2)\r
-{\r
- int i;\r
-\r
- if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish)\r
- return 0;\r
- for (i = 0; i < s1->ss_narcs; i++) {\r
- if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow ||\r
- s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label)\r
- return 0;\r
- }\r
- return 1;\r
-}\r
-\r
-static void\r
-renamestates(int xx_nstates, ss_state *xx_state, int from, int to)\r
-{\r
- int i, j;\r
-\r
- if (Py_DebugFlag)\r
- printf("Rename state %d to %d.\n", from, to);\r
- for (i = 0; i < xx_nstates; i++) {\r
- if (xx_state[i].ss_deleted)\r
- continue;\r
- for (j = 0; j < xx_state[i].ss_narcs; j++) {\r
- if (xx_state[i].ss_arc[j].sa_arrow == from)\r
- xx_state[i].ss_arc[j].sa_arrow = to;\r
- }\r
- }\r
-}\r
-\r
-static void\r
-simplify(int xx_nstates, ss_state *xx_state)\r
-{\r
- int changes;\r
- int i, j;\r
-\r
- do {\r
- changes = 0;\r
- for (i = 1; i < xx_nstates; i++) {\r
- if (xx_state[i].ss_deleted)\r
- continue;\r
- for (j = 0; j < i; j++) {\r
- if (xx_state[j].ss_deleted)\r
- continue;\r
- if (samestate(&xx_state[i], &xx_state[j])) {\r
- xx_state[i].ss_deleted++;\r
- renamestates(xx_nstates, xx_state,\r
- i, j);\r
- changes++;\r
- break;\r
- }\r
- }\r
- }\r
- } while (changes);\r
-}\r
-\r
-\r
-/* PART FOUR -- GENERATE PARSING TABLES */\r
-\r
-/* Convert the DFA into a grammar that can be used by our parser */\r
-\r
-static void\r
-convert(dfa *d, int xx_nstates, ss_state *xx_state)\r
-{\r
- int i, j;\r
- ss_state *yy;\r
- ss_arc *zz;\r
-\r
- for (i = 0; i < xx_nstates; i++) {\r
- yy = &xx_state[i];\r
- if (yy->ss_deleted)\r
- continue;\r
- yy->ss_rename = addstate(d);\r
- }\r
-\r
- for (i = 0; i < xx_nstates; i++) {\r
- yy = &xx_state[i];\r
- if (yy->ss_deleted)\r
- continue;\r
- for (j = 0; j < yy->ss_narcs; j++) {\r
- zz = &yy->ss_arc[j];\r
- addarc(d, yy->ss_rename,\r
- xx_state[zz->sa_arrow].ss_rename,\r
- zz->sa_label);\r
- }\r
- if (yy->ss_finish)\r
- addarc(d, yy->ss_rename, yy->ss_rename, 0);\r
- }\r
-\r
- d->d_initial = 0;\r
-}\r
-\r
-\r
-/* PART FIVE -- GLUE IT ALL TOGETHER */\r
-\r
-static grammar *\r
-maketables(nfagrammar *gr)\r
-{\r
- int i;\r
- nfa *nf;\r
- dfa *d;\r
- grammar *g;\r
-\r
- if (gr->gr_nnfas == 0)\r
- return NULL;\r
- g = newgrammar(gr->gr_nfa[0]->nf_type);\r
- /* XXX first rule must be start rule */\r
- g->g_ll = gr->gr_ll;\r
-\r
- for (i = 0; i < gr->gr_nnfas; i++) {\r
- nf = gr->gr_nfa[i];\r
- if (Py_DebugFlag) {\r
- printf("Dump of NFA for '%s' ...\n", nf->nf_name);\r
- dumpnfa(&gr->gr_ll, nf);\r
- printf("Making DFA for '%s' ...\n", nf->nf_name);\r
- }\r
- d = adddfa(g, nf->nf_type, nf->nf_name);\r
- makedfa(gr, gr->gr_nfa[i], d);\r
- }\r
-\r
- return g;\r
-}\r
-\r
-grammar *\r
-pgen(node *n)\r
-{\r
- nfagrammar *gr;\r
- grammar *g;\r
-\r
- gr = metacompile(n);\r
- g = maketables(gr);\r
- translatelabels(g);\r
- addfirstsets(g);\r
- PyObject_FREE(gr);\r
- return g;\r
-}\r
-\r
-grammar *\r
-Py_pgen(node *n)\r
-{\r
- return pgen(n);\r
-}\r
-\r
-/*\r
-\r
-Description\r
------------\r
-\r
-Input is a grammar in extended BNF (using * for repetition, + for\r
-at-least-once repetition, [] for optional parts, | for alternatives and\r
-() for grouping). This has already been parsed and turned into a parse\r
-tree.\r
-\r
-Each rule is considered as a regular expression in its own right.\r
-It is turned into a Non-deterministic Finite Automaton (NFA), which\r
-is then turned into a Deterministic Finite Automaton (DFA), which is then\r
-optimized to reduce the number of states. See [Aho&Ullman 77] chapter 3,\r
-or similar compiler books (this technique is more often used for lexical\r
-analyzers).\r
-\r
-The DFA's are used by the parser as parsing tables in a special way\r
-that's probably unique. Before they are usable, the FIRST sets of all\r
-non-terminals are computed.\r
-\r
-Reference\r
----------\r
-\r
-[Aho&Ullman 77]\r
- Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977\r
- (first edition)\r
-\r
-*/\r
projects / mirror_edk2.git / blobdiff