cpython-lru_cache-weakref: Parser/pgen.c annotate

annotate Parser/pgen.c @ 79675:c0a2294de787 2.7

Issue #16199: Backport 2to3 typo fix from 3.2.

author	Chris Jerdonek <chris.jerdonek@gmail.com>
date	Thu, 11 Oct 2012 16:15:46 -0700
parents	fd25030223b0
children

rev	line source
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	1 /* Parser generator */
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	2
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	3 /* For a description, see the comments at end of this file */
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	4
21181 944d6e02f359 The parser doesn't need its own implementation of assert, and having its Tim Peters <tim.peters@gmail.com> parents: 19867 diff changeset	5 #include "Python.h"
86 a6934380c6e7 "Compiling" version Guido van Rossum <guido@python.org> parents: 6 diff changeset	6 #include "pgenheaders.h"
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	7 #include "token.h"
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	8 #include "node.h"
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	9 #include "grammar.h"
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	10 #include "metagrammar.h"
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	11 #include "pgen.h"
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	12
5379 1c9a84e0981d Another directory quickly renamed. Guido van Rossum <guido@python.org> parents: 4839 diff changeset	13 extern int Py_DebugFlag;
23588 ab94ec4af98a Py_IgnoreEnvironmentFlag should be extern, since it is declared in pythonrun.c Neal Norwitz <nnorwitz@gmail.com> parents: 23213 diff changeset	14 extern int Py_IgnoreEnvironmentFlag; /* needed by Py_GETENV */
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	15
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	16
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	17 /* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	18
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	19 typedef struct _nfaarc {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	20 int ar_label;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	21 int ar_arrow;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	22 } nfaarc;
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	23
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	24 typedef struct _nfastate {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	25 int st_narcs;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	26 nfaarc *st_arc;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	27 } nfastate;
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	28
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	29 typedef struct _nfa {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	30 int nf_type;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	31 char *nf_name;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	32 int nf_nstates;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	33 nfastate *nf_state;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	34 int nf_start, nf_finish;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	35 } nfa;
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	36
170 ee0a32fd4567 Added forward declarations. Guido van Rossum <guido@python.org> parents: 145 diff changeset	37 /* Forward */
13447 a89f7f268de4 Nuke all remaining occurrences of Py_PROTO and Py_FPROTO. Tim Peters <tim.peters@gmail.com> parents: 13256 diff changeset	38 static void compile_rhs(labellist *ll,
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	39 nfa nf, node n, int pa, int pb);
13447 a89f7f268de4 Nuke all remaining occurrences of Py_PROTO and Py_FPROTO. Tim Peters <tim.peters@gmail.com> parents: 13256 diff changeset	40 static void compile_alt(labellist *ll,
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	41 nfa nf, node n, int pa, int pb);
13447 a89f7f268de4 Nuke all remaining occurrences of Py_PROTO and Py_FPROTO. Tim Peters <tim.peters@gmail.com> parents: 13256 diff changeset	42 static void compile_item(labellist *ll,
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	43 nfa nf, node n, int pa, int pb);
13447 a89f7f268de4 Nuke all remaining occurrences of Py_PROTO and Py_FPROTO. Tim Peters <tim.peters@gmail.com> parents: 13256 diff changeset	44 static void compile_atom(labellist *ll,
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	45 nfa nf, node n, int pa, int pb);
170 ee0a32fd4567 Added forward declarations. Guido van Rossum <guido@python.org> parents: 145 diff changeset	46
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	47 static int
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	48 addnfastate(nfa *nf)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	49 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	50 nfastate *st;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	51
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	52 nf->nf_state = (nfastate *)PyObject_REALLOC(nf->nf_state,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	53 sizeof(nfastate) * (nf->nf_nstates + 1));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	54 if (nf->nf_state == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	55 Py_FatalError("out of mem");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	56 st = &nf->nf_state[nf->nf_nstates++];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	57 st->st_narcs = 0;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	58 st->st_arc = NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	59 return st - nf->nf_state;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	60 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	61
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	62 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	63 addnfaarc(nfa *nf, int from, int to, int lbl)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	64 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	65 nfastate *st;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	66 nfaarc *ar;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	67
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	68 st = &nf->nf_state[from];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	69 st->st_arc = (nfaarc *)PyObject_REALLOC(st->st_arc,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	70 sizeof(nfaarc) * (st->st_narcs + 1));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	71 if (st->st_arc == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	72 Py_FatalError("out of mem");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	73 ar = &st->st_arc[st->st_narcs++];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	74 ar->ar_label = lbl;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	75 ar->ar_arrow = to;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	76 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	77
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	78 static nfa *
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	79 newnfa(char *name)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	80 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	81 nfa *nf;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	82 static int type = NT_OFFSET; /* All types will be disjunct */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	83
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	84 nf = (nfa *)PyObject_MALLOC(sizeof(nfa));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	85 if (nf == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	86 Py_FatalError("no mem for new nfa");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	87 nf->nf_type = type++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	88 nf->nf_name = name; /* XXX strdup(name) ??? */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	89 nf->nf_nstates = 0;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	90 nf->nf_state = NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	91 nf->nf_start = nf->nf_finish = -1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	92 return nf;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	93 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	94
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	95 typedef struct _nfagrammar {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	96 int gr_nnfas;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	97 nfa **gr_nfa;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	98 labellist gr_ll;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	99 } nfagrammar;
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	100
170 ee0a32fd4567 Added forward declarations. Guido van Rossum <guido@python.org> parents: 145 diff changeset	101 /* Forward */
13447 a89f7f268de4 Nuke all remaining occurrences of Py_PROTO and Py_FPROTO. Tim Peters <tim.peters@gmail.com> parents: 13256 diff changeset	102 static void compile_rule(nfagrammar gr, node n);
170 ee0a32fd4567 Added forward declarations. Guido van Rossum <guido@python.org> parents: 145 diff changeset	103
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	104 static nfagrammar *
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	105 newnfagrammar(void)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	106 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	107 nfagrammar *gr;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	108
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	109 gr = (nfagrammar *)PyObject_MALLOC(sizeof(nfagrammar));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	110 if (gr == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	111 Py_FatalError("no mem for new nfa grammar");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	112 gr->gr_nnfas = 0;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	113 gr->gr_nfa = NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	114 gr->gr_ll.ll_nlabels = 0;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	115 gr->gr_ll.ll_label = NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	116 addlabel(&gr->gr_ll, ENDMARKER, "EMPTY");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	117 return gr;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	118 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	119
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	120 static nfa *
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	121 addnfa(nfagrammar gr, char name)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	122 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	123 nfa *nf;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	124
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	125 nf = newnfa(name);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	126 gr->gr_nfa = (nfa **)PyObject_REALLOC(gr->gr_nfa,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	127 sizeof(nfa) (gr->gr_nnfas + 1));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	128 if (gr->gr_nfa == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	129 Py_FatalError("out of mem");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	130 gr->gr_nfa[gr->gr_nnfas++] = nf;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	131 addlabel(&gr->gr_ll, NAME, nf->nf_name);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	132 return nf;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	133 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	134
4839 4567e158d20c Rename DEBUG macro to Py_DEBUG Guido van Rossum <guido@python.org> parents: 4577 diff changeset	135 #ifdef Py_DEBUG
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	136
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	137 static char REQNFMT[] = "metacompile: less than %d children\n";
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	138
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	139 #define REQN(i, count) \
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	140 if (i < count) { \
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	141 fprintf(stderr, REQNFMT, count); \
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	142 Py_FatalError("REQN"); \
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	143 } else
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	144
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	145 #else
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	146 #define REQN(i, count) /* empty */
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	147 #endif
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	148
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	149 static nfagrammar *
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	150 metacompile(node *n)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	151 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	152 nfagrammar *gr;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	153 int i;
19867 5780724470ee Silence parser generator output. Guido van Rossum <guido@python.org> parents: 14375 diff changeset	154
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	155 if (Py_DebugFlag)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	156 printf("Compiling (meta-) parse tree into NFA grammar\n");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	157 gr = newnfagrammar();
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	158 REQ(n, MSTART);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	159 i = n->n_nchildren - 1; /* Last child is ENDMARKER */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	160 n = n->n_child;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	161 for (; --i >= 0; n++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	162 if (n->n_type != NEWLINE)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	163 compile_rule(gr, n);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	164 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	165 return gr;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	166 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	167
4577 fae78cf8541d Make gcc -Wall happy Guido van Rossum <guido@python.org> parents: 4503 diff changeset	168 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	169 compile_rule(nfagrammar gr, node n)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	170 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	171 nfa *nf;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	172
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	173 REQ(n, RULE);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	174 REQN(n->n_nchildren, 4);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	175 n = n->n_child;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	176 REQ(n, NAME);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	177 nf = addnfa(gr, n->n_str);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	178 n++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	179 REQ(n, COLON);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	180 n++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	181 REQ(n, RHS);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	182 compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	183 n++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	184 REQ(n, NEWLINE);
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	185 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	186
4577 fae78cf8541d Make gcc -Wall happy Guido van Rossum <guido@python.org> parents: 4503 diff changeset	187 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	188 compile_rhs(labellist ll, nfa nf, node n, int pa, int *pb)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	189 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	190 int i;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	191 int a, b;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	192
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	193 REQ(n, RHS);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	194 i = n->n_nchildren;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	195 REQN(i, 1);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	196 n = n->n_child;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	197 REQ(n, ALT);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	198 compile_alt(ll, nf, n, pa, pb);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	199 if (--i <= 0)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	200 return;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	201 n++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	202 a = *pa;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	203 b = *pb;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	204 *pa = addnfastate(nf);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	205 *pb = addnfastate(nf);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	206 addnfaarc(nf, *pa, a, EMPTY);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	207 addnfaarc(nf, b, *pb, EMPTY);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	208 for (; --i >= 0; n++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	209 REQ(n, VBAR);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	210 REQN(i, 1);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	211 --i;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	212 n++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	213 REQ(n, ALT);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	214 compile_alt(ll, nf, n, &a, &b);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	215 addnfaarc(nf, *pa, a, EMPTY);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	216 addnfaarc(nf, b, *pb, EMPTY);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	217 }
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	218 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	219
4577 fae78cf8541d Make gcc -Wall happy Guido van Rossum <guido@python.org> parents: 4503 diff changeset	220 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	221 compile_alt(labellist ll, nfa nf, node n, int pa, int *pb)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	222 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	223 int i;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	224 int a, b;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	225
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	226 REQ(n, ALT);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	227 i = n->n_nchildren;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	228 REQN(i, 1);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	229 n = n->n_child;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	230 REQ(n, ITEM);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	231 compile_item(ll, nf, n, pa, pb);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	232 --i;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	233 n++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	234 for (; --i >= 0; n++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	235 REQ(n, ITEM);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	236 compile_item(ll, nf, n, &a, &b);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	237 addnfaarc(nf, *pb, a, EMPTY);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	238 *pb = b;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	239 }
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	240 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	241
4577 fae78cf8541d Make gcc -Wall happy Guido van Rossum <guido@python.org> parents: 4503 diff changeset	242 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	243 compile_item(labellist ll, nfa nf, node n, int pa, int *pb)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	244 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	245 int i;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	246 int a, b;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	247
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	248 REQ(n, ITEM);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	249 i = n->n_nchildren;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	250 REQN(i, 1);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	251 n = n->n_child;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	252 if (n->n_type == LSQB) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	253 REQN(i, 3);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	254 n++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	255 REQ(n, RHS);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	256 *pa = addnfastate(nf);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	257 *pb = addnfastate(nf);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	258 addnfaarc(nf, pa, pb, EMPTY);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	259 compile_rhs(ll, nf, n, &a, &b);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	260 addnfaarc(nf, *pa, a, EMPTY);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	261 addnfaarc(nf, b, *pb, EMPTY);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	262 REQN(i, 1);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	263 n++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	264 REQ(n, RSQB);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	265 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	266 else {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	267 compile_atom(ll, nf, n, pa, pb);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	268 if (--i <= 0)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	269 return;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	270 n++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	271 addnfaarc(nf, pb, pa, EMPTY);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	272 if (n->n_type == STAR)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	273 pb = pa;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	274 else
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	275 REQ(n, PLUS);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	276 }
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	277 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	278
4577 fae78cf8541d Make gcc -Wall happy Guido van Rossum <guido@python.org> parents: 4503 diff changeset	279 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	280 compile_atom(labellist ll, nfa nf, node n, int pa, int *pb)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	281 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	282 int i;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	283
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	284 REQ(n, ATOM);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	285 i = n->n_nchildren;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	286 REQN(i, 1);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	287 n = n->n_child;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	288 if (n->n_type == LPAR) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	289 REQN(i, 3);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	290 n++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	291 REQ(n, RHS);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	292 compile_rhs(ll, nf, n, pa, pb);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	293 n++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	294 REQ(n, RPAR);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	295 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	296 else if (n->n_type == NAME \|\| n->n_type == STRING) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	297 *pa = addnfastate(nf);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	298 *pb = addnfastate(nf);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	299 addnfaarc(nf, pa, pb, addlabel(ll, n->n_type, n->n_str));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	300 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	301 else
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	302 REQ(n, NAME);
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	303 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	304
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	305 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	306 dumpstate(labellist ll, nfa nf, int istate)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	307 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	308 nfastate *st;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	309 int i;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	310 nfaarc *ar;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	311
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	312 printf("%c%2d%c",
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	313 istate == nf->nf_start ? '*' : ' ',
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	314 istate,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	315 istate == nf->nf_finish ? '.' : ' ');
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	316 st = &nf->nf_state[istate];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	317 ar = st->st_arc;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	318 for (i = 0; i < st->st_narcs; i++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	319 if (i > 0)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	320 printf("\n ");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	321 printf("-> %2d %s", ar->ar_arrow,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	322 PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	323 ar++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	324 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	325 printf("\n");
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	326 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	327
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	328 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	329 dumpnfa(labellist ll, nfa nf)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	330 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	331 int i;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	332
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	333 printf("NFA '%s' has %d states; start %d, finish %d\n",
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	334 nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	335 for (i = 0; i < nf->nf_nstates; i++)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	336 dumpstate(ll, nf, i);
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	337 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	338
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	339
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	340 /* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	341
2044 281e40652e23 Parser/tokenizer.c (tok_nextc): zap tok->buf after freeing; Guido van Rossum <guido@python.org> parents: 1848 diff changeset	342 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	343 addclosure(bitset ss, nfa *nf, int istate)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	344 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	345 if (addbit(ss, istate)) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	346 nfastate *st = &nf->nf_state[istate];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	347 nfaarc *ar = st->st_arc;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	348 int i;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	349
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	350 for (i = st->st_narcs; --i >= 0; ) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	351 if (ar->ar_label == EMPTY)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	352 addclosure(ss, nf, ar->ar_arrow);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	353 ar++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	354 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	355 }
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	356 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	357
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	358 typedef struct _ss_arc {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	359 bitset sa_bitset;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	360 int sa_arrow;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	361 int sa_label;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	362 } ss_arc;
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	363
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	364 typedef struct _ss_state {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	365 bitset ss_ss;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	366 int ss_narcs;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	367 struct _ss_arc *ss_arc;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	368 int ss_deleted;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	369 int ss_finish;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	370 int ss_rename;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	371 } ss_state;
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	372
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	373 typedef struct _ss_dfa {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	374 int sd_nstates;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	375 ss_state *sd_state;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	376 } ss_dfa;
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	377
170 ee0a32fd4567 Added forward declarations. Guido van Rossum <guido@python.org> parents: 145 diff changeset	378 /* Forward */
13447 a89f7f268de4 Nuke all remaining occurrences of Py_PROTO and Py_FPROTO. Tim Peters <tim.peters@gmail.com> parents: 13256 diff changeset	379 static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	380 labellist ll, char msg);
13447 a89f7f268de4 Nuke all remaining occurrences of Py_PROTO and Py_FPROTO. Tim Peters <tim.peters@gmail.com> parents: 13256 diff changeset	381 static void simplify(int xx_nstates, ss_state *xx_state);
a89f7f268de4 Nuke all remaining occurrences of Py_PROTO and Py_FPROTO. Tim Peters <tim.peters@gmail.com> parents: 13256 diff changeset	382 static void convert(dfa d, int xx_nstates, ss_state xx_state);
170 ee0a32fd4567 Added forward declarations. Guido van Rossum <guido@python.org> parents: 145 diff changeset	383
4577 fae78cf8541d Make gcc -Wall happy Guido van Rossum <guido@python.org> parents: 4503 diff changeset	384 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	385 makedfa(nfagrammar gr, nfa nf, dfa *d)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	386 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	387 int nbits = nf->nf_nstates;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	388 bitset ss;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	389 int xx_nstates;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	390 ss_state xx_state, yy;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	391 ss_arc *zz;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	392 int istate, jstate, iarc, jarc, ibit;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	393 nfastate *st;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	394 nfaarc *ar;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	395
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	396 ss = newbitset(nbits);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	397 addclosure(ss, nf, nf->nf_start);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	398 xx_state = (ss_state *)PyObject_MALLOC(sizeof(ss_state));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	399 if (xx_state == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	400 Py_FatalError("no mem for xx_state in makedfa");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	401 xx_nstates = 1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	402 yy = &xx_state[0];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	403 yy->ss_ss = ss;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	404 yy->ss_narcs = 0;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	405 yy->ss_arc = NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	406 yy->ss_deleted = 0;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	407 yy->ss_finish = testbit(ss, nf->nf_finish);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	408 if (yy->ss_finish)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	409 printf("Error: nonterminal '%s' may produce empty.\n",
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	410 nf->nf_name);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	411
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	412 /* This algorithm is from a book written before
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	413 the invention of structured programming... */
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	414
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	415 /* For each unmarked state... */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	416 for (istate = 0; istate < xx_nstates; ++istate) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	417 size_t size;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	418 yy = &xx_state[istate];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	419 ss = yy->ss_ss;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	420 /* For all its states... */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	421 for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	422 if (!testbit(ss, ibit))
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	423 continue;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	424 st = &nf->nf_state[ibit];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	425 /* For all non-empty arcs from this state... */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	426 for (iarc = 0; iarc < st->st_narcs; iarc++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	427 ar = &st->st_arc[iarc];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	428 if (ar->ar_label == EMPTY)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	429 continue;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	430 /* Look up in list of arcs from this state */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	431 for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	432 zz = &yy->ss_arc[jarc];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	433 if (ar->ar_label == zz->sa_label)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	434 goto found;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	435 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	436 /* Add new arc for this state */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	437 size = sizeof(ss_arc) * (yy->ss_narcs + 1);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	438 yy->ss_arc = (ss_arc *)PyObject_REALLOC(
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	439 yy->ss_arc, size);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	440 if (yy->ss_arc == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	441 Py_FatalError("out of mem");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	442 zz = &yy->ss_arc[yy->ss_narcs++];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	443 zz->sa_label = ar->ar_label;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	444 zz->sa_bitset = newbitset(nbits);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	445 zz->sa_arrow = -1;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	446 found: ;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	447 /* Add destination */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	448 addclosure(zz->sa_bitset, nf, ar->ar_arrow);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	449 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	450 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	451 /* Now look up all the arrow states */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	452 for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	453 zz = &xx_state[istate].ss_arc[jarc];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	454 for (jstate = 0; jstate < xx_nstates; jstate++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	455 if (samebitset(zz->sa_bitset,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	456 xx_state[jstate].ss_ss, nbits)) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	457 zz->sa_arrow = jstate;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	458 goto done;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	459 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	460 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	461 size = sizeof(ss_state) * (xx_nstates + 1);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	462 xx_state = (ss_state *)PyObject_REALLOC(xx_state,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	463 size);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	464 if (xx_state == NULL)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	465 Py_FatalError("out of mem");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	466 zz->sa_arrow = xx_nstates;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	467 yy = &xx_state[xx_nstates++];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	468 yy->ss_ss = zz->sa_bitset;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	469 yy->ss_narcs = 0;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	470 yy->ss_arc = NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	471 yy->ss_deleted = 0;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	472 yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	473 done: ;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	474 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	475 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	476
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	477 if (Py_DebugFlag)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	478 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	479 "before minimizing");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	480
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	481 simplify(xx_nstates, xx_state);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	482
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	483 if (Py_DebugFlag)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	484 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	485 "after minimizing");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	486
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	487 convert(d, xx_nstates, xx_state);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	488
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	489 /* XXX cleanup */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	490 PyObject_FREE(xx_state);
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	491 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	492
4577 fae78cf8541d Make gcc -Wall happy Guido van Rossum <guido@python.org> parents: 4503 diff changeset	493 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	494 printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	495 labellist ll, char msg)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	496 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	497 int i, ibit, iarc;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	498 ss_state *yy;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	499 ss_arc *zz;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	500
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	501 printf("Subset DFA %s\n", msg);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	502 for (i = 0; i < xx_nstates; i++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	503 yy = &xx_state[i];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	504 if (yy->ss_deleted)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	505 continue;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	506 printf(" Subset %d", i);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	507 if (yy->ss_finish)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	508 printf(" (finish)");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	509 printf(" { ");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	510 for (ibit = 0; ibit < nbits; ibit++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	511 if (testbit(yy->ss_ss, ibit))
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	512 printf("%d ", ibit);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	513 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	514 printf("}\n");
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	515 for (iarc = 0; iarc < yy->ss_narcs; iarc++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	516 zz = &yy->ss_arc[iarc];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	517 printf(" Arc to state %d, label %s\n",
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	518 zz->sa_arrow,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	519 PyGrammar_LabelRepr(
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	520 &ll->ll_label[zz->sa_label]));
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	521 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	522 }
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	523 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	524
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	525
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	526 /* PART THREE -- SIMPLIFY DFA */
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	527
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	528 /* Simplify the DFA by repeatedly eliminating states that are
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	529 equivalent to another oner. This is NOT Algorithm 3.3 from
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	530 [Aho&Ullman 77]. It does not always finds the minimal DFA,
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	531 but it does usually make a much smaller one... (For an example
13620 5b727ab37092 Spelling fixes supplied by Rob W. W. Hooft. All these are fixes in either Thomas Wouters <thomas@python.org> parents: 13447 diff changeset	532 of sub-optimal behavior, try S: x a b+ \| y a b+.)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	533 */
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	534
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	535 static int
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	536 samestate(ss_state s1, ss_state s2)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	537 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	538 int i;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	539
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	540 if (s1->ss_narcs != s2->ss_narcs \|\| s1->ss_finish != s2->ss_finish)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	541 return 0;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	542 for (i = 0; i < s1->ss_narcs; i++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	543 if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow \|\|
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	544 s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	545 return 0;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	546 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	547 return 1;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	548 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	549
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	550 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	551 renamestates(int xx_nstates, ss_state *xx_state, int from, int to)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	552 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	553 int i, j;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	554
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	555 if (Py_DebugFlag)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	556 printf("Rename state %d to %d.\n", from, to);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	557 for (i = 0; i < xx_nstates; i++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	558 if (xx_state[i].ss_deleted)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	559 continue;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	560 for (j = 0; j < xx_state[i].ss_narcs; j++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	561 if (xx_state[i].ss_arc[j].sa_arrow == from)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	562 xx_state[i].ss_arc[j].sa_arrow = to;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	563 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	564 }
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	565 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	566
4577 fae78cf8541d Make gcc -Wall happy Guido van Rossum <guido@python.org> parents: 4503 diff changeset	567 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	568 simplify(int xx_nstates, ss_state *xx_state)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	569 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	570 int changes;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	571 int i, j;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	572
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	573 do {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	574 changes = 0;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	575 for (i = 1; i < xx_nstates; i++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	576 if (xx_state[i].ss_deleted)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	577 continue;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	578 for (j = 0; j < i; j++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	579 if (xx_state[j].ss_deleted)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	580 continue;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	581 if (samestate(&xx_state[i], &xx_state[j])) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	582 xx_state[i].ss_deleted++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	583 renamestates(xx_nstates, xx_state,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	584 i, j);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	585 changes++;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	586 break;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	587 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	588 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	589 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	590 } while (changes);
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	591 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	592
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	593
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	594 /* PART FOUR -- GENERATE PARSING TABLES */
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	595
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	596 /* Convert the DFA into a grammar that can be used by our parser */
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	597
4577 fae78cf8541d Make gcc -Wall happy Guido van Rossum <guido@python.org> parents: 4503 diff changeset	598 static void
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	599 convert(dfa d, int xx_nstates, ss_state xx_state)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	600 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	601 int i, j;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	602 ss_state *yy;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	603 ss_arc *zz;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	604
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	605 for (i = 0; i < xx_nstates; i++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	606 yy = &xx_state[i];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	607 if (yy->ss_deleted)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	608 continue;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	609 yy->ss_rename = addstate(d);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	610 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	611
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	612 for (i = 0; i < xx_nstates; i++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	613 yy = &xx_state[i];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	614 if (yy->ss_deleted)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	615 continue;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	616 for (j = 0; j < yy->ss_narcs; j++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	617 zz = &yy->ss_arc[j];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	618 addarc(d, yy->ss_rename,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	619 xx_state[zz->sa_arrow].ss_rename,
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	620 zz->sa_label);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	621 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	622 if (yy->ss_finish)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	623 addarc(d, yy->ss_rename, yy->ss_rename, 0);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	624 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	625
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	626 d->d_initial = 0;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	627 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	628
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	629
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	630 /* PART FIVE -- GLUE IT ALL TOGETHER */
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	631
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	632 static grammar *
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	633 maketables(nfagrammar *gr)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	634 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	635 int i;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	636 nfa *nf;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	637 dfa *d;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	638 grammar *g;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	639
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	640 if (gr->gr_nnfas == 0)
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	641 return NULL;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	642 g = newgrammar(gr->gr_nfa[0]->nf_type);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	643 /* XXX first rule must be start rule */
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	644 g->g_ll = gr->gr_ll;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	645
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	646 for (i = 0; i < gr->gr_nnfas; i++) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	647 nf = gr->gr_nfa[i];
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	648 if (Py_DebugFlag) {
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	649 printf("Dump of NFA for '%s' ...\n", nf->nf_name);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	650 dumpnfa(&gr->gr_ll, nf);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	651 printf("Making DFA for '%s' ...\n", nf->nf_name);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	652 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	653 d = adddfa(g, nf->nf_type, nf->nf_name);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	654 makedfa(gr, gr->gr_nfa[i], d);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	655 }
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	656
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	657 return g;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	658 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	659
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	660 grammar *
13659 e78153e179fb Mass ANSIfication. Thomas Wouters <thomas@python.org> parents: 13620 diff changeset	661 pgen(node *n)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	662 {
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	663 nfagrammar *gr;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	664 grammar *g;
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	665
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	666 gr = metacompile(n);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	667 g = maketables(gr);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	668 translatelabels(g);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	669 addfirstsets(g);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	670 PyObject_FREE(gr);
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	671 return g;
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	672 }
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	673
28646 193b8aec00ce Changes from Jonathan Riehl to allow his pgen extension (PEP 269) to Guido van Rossum <guido@python.org> parents: 28108 diff changeset	674 grammar *
193b8aec00ce Changes from Jonathan Riehl to allow his pgen extension (PEP 269) to Guido van Rossum <guido@python.org> parents: 28108 diff changeset	675 Py_pgen(node *n)
193b8aec00ce Changes from Jonathan Riehl to allow his pgen extension (PEP 269) to Guido van Rossum <guido@python.org> parents: 28108 diff changeset	676 {
193b8aec00ce Changes from Jonathan Riehl to allow his pgen extension (PEP 269) to Guido van Rossum <guido@python.org> parents: 28108 diff changeset	677 return pgen(n);
193b8aec00ce Changes from Jonathan Riehl to allow his pgen extension (PEP 269) to Guido van Rossum <guido@python.org> parents: 28108 diff changeset	678 }
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	679
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	680 /*
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	681
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	682 Description
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	683 -----------
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	684
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	685 Input is a grammar in extended BNF (using * for repetition, + for
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	686 at-least-once repetition, [] for optional parts, \| for alternatives and
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	687 () for grouping). This has already been parsed and turned into a parse
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	688 tree.
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	689
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	690 Each rule is considered as a regular expression in its own right.
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	691 It is turned into a Non-deterministic Finite Automaton (NFA), which
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	692 is then turned into a Deterministic Finite Automaton (DFA), which is then
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	693 optimized to reduce the number of states. See [Aho&Ullman 77] chapter 3,
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	694 or similar compiler books (this technique is more often used for lexical
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	695 analyzers).
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	696
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	697 The DFA's are used by the parser as parsing tables in a special way
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	698 that's probably unique. Before they are usable, the FIRST sets of all
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	699 non-terminals are computed.
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	700
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	701 Reference
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	702 ---------
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	703
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	704 [Aho&Ullman 77]
61463 fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	705 Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977
fd25030223b0 Untabify C files. Will watch buildbots. Antoine Pitrou <solipsis@pitrou.net> parents: 44737 diff changeset	706 (first edition)
6 fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	707
fc6fcd7df4f7 Initial revision Guido van Rossum <guido@python.org> parents: diff changeset	708 */

Mercurial > cpython-lru_cache-weakref

annotate Parser/pgen.c @ 79675:c0a2294de787 2.7