/* Parser generator */ /* For a description, see the comments at end of this file */ #include "Python.h"#include "pgenheaders.h"#include "token.h"#include "node.h"#include "grammar.h"#include "metagrammar.h"#include "pgen.h" extern int Py_DebugFlag;extern int Py_IgnoreEnvironmentFlag; /* needed by Py_GETENV */  /* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */ typedef struct _nfaarc {	int	ar_label;	int	ar_arrow;} nfaarc; typedef struct _nfastate {	int	st_narcs;	nfaarc	*st_arc;} nfastate; typedef struct _nfa {	int		nf_type;	char		*nf_name;	int		nf_nstates;	nfastate	*nf_state;	int		nf_start, nf_finish;} nfa; /* Forward */static void compile_rhs(labellist *ll,			nfa *nf, node *n, int *pa, int *pb);static void compile_alt(labellist *ll,			nfa *nf, node *n, int *pa, int *pb);static void compile_item(labellist *ll,			 nfa *nf, node *n, int *pa, int *pb);static void compile_atom(labellist *ll,			 nfa *nf, node *n, int *pa, int *pb); static intaddnfastate(nfa *nf){	nfastate *st;		nf->nf_state = (nfastate *)PyObject_REALLOC(nf->nf_state,                                     sizeof(nfastate) * (nf->nf_nstates + 1));	if (nf->nf_state == NULL)		Py_FatalError("out of mem");	st = &nf->nf_state[nf->nf_nstates++];	st->st_narcs = 0;	st->st_arc = NULL;	return st - nf->nf_state;} static voidaddnfaarc(nfa *nf, int from, int to, int lbl){	nfastate *st;	nfaarc *ar;		st = &nf->nf_state[from];	st->st_arc = (nfaarc *)PyObject_REALLOC(st->st_arc,				      sizeof(nfaarc) * (st->st_narcs + 1));	if (st->st_arc == NULL)		Py_FatalError("out of mem");	ar = &st->st_arc[st->st_narcs++];	ar->ar_label = lbl;	ar->ar_arrow = to;} static nfa *newnfa(char *name){	nfa *nf;	static int type = NT_OFFSET; /* All types will be disjunct */		nf = (nfa *)PyObject_MALLOC(sizeof(nfa));	if (nf == NULL)		Py_FatalError("no mem for new nfa");	nf->nf_type = type++;	nf->nf_name = name; /* XXX strdup(name) ??? */	nf->nf_nstates = 0;	nf->nf_state = NULL;	nf->nf_start = nf->nf_finish = -1;	return nf;} typedef struct _nfagrammar {	int		gr_nnfas;	nfa		**gr_nfa;	labellist	gr_ll;} nfagrammar; /* Forward */static void compile_rule(nfagrammar *gr, node *n); static nfagrammar *newnfagrammar(void){	nfagrammar *gr;		gr = (nfagrammar *)PyObject_MALLOC(sizeof(nfagrammar));	if (gr == NULL)		Py_FatalError("no mem for new nfa grammar");	gr->gr_nnfas = 0;	gr->gr_nfa = NULL;	gr->gr_ll.ll_nlabels = 0;	gr->gr_ll.ll_label = NULL;	addlabel(&gr->gr_ll, ENDMARKER, "EMPTY");	return gr;} static nfa *addnfa(nfagrammar *gr, char *name){	nfa *nf;		nf = newnfa(name);	gr->gr_nfa = (nfa **)PyObject_REALLOC(gr->gr_nfa,				      sizeof(nfa) * (gr->gr_nnfas + 1));	if (gr->gr_nfa == NULL)		Py_FatalError("out of mem");	gr->gr_nfa[gr->gr_nnfas++] = nf;	addlabel(&gr->gr_ll, NAME, nf->nf_name);	return nf;} #ifdef Py_DEBUG static char REQNFMT[] = "metacompile: less than %d children\n"; #define REQN(i, count) \ 	if (i < count) { \		fprintf(stderr, REQNFMT, count); \		Py_FatalError("REQN"); \	} else #else#define REQN(i, count)	/* empty */#endif static nfagrammar *metacompile(node *n){	nfagrammar *gr;	int i; 	if (Py_DebugFlag)		printf("Compiling (meta-) parse tree into NFA grammar\n");	gr = newnfagrammar();	REQ(n, MSTART);	i = n->n_nchildren - 1; /* Last child is ENDMARKER */	n = n->n_child;	for (; --i >= 0; n++) {		if (n->n_type != NEWLINE)			compile_rule(gr, n);	}	return gr;} static voidcompile_rule(nfagrammar *gr, node *n){	nfa *nf;		REQ(n, RULE);	REQN(n->n_nchildren, 4);	n = n->n_child;	REQ(n, NAME);	nf = addnfa(gr, n->n_str);	n++;	REQ(n, COLON);	n++;	REQ(n, RHS);	compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);	n++;	REQ(n, NEWLINE);} static voidcompile_rhs(labellist *ll, nfa *nf, node *n, int *pa, int *pb){	int i;	int a, b;		REQ(n, RHS);	i = n->n_nchildren;	REQN(i, 1);	n = n->n_child;	REQ(n, ALT);	compile_alt(ll, nf, n, pa, pb);	if (--i <= 0)		return;	n++;	a = *pa;	b = *pb;	*pa = addnfastate(nf);	*pb = addnfastate(nf);	addnfaarc(nf, *pa, a, EMPTY);	addnfaarc(nf, b, *pb, EMPTY);	for (; --i >= 0; n++) {		REQ(n, VBAR);		REQN(i, 1);		--i;		n++;		REQ(n, ALT);		compile_alt(ll, nf, n, &a, &b);		addnfaarc(nf, *pa, a, EMPTY);		addnfaarc(nf, b, *pb, EMPTY);	}} static voidcompile_alt(labellist *ll, nfa *nf, node *n, int *pa, int *pb){	int i;	int a, b;		REQ(n, ALT);	i = n->n_nchildren;	REQN(i, 1);	n = n->n_child;	REQ(n, ITEM);	compile_item(ll, nf, n, pa, pb);	--i;	n++;	for (; --i >= 0; n++) {		REQ(n, ITEM);		compile_item(ll, nf, n, &a, &b);		addnfaarc(nf, *pb, a, EMPTY);		*pb = b;	}} static voidcompile_item(labellist *ll, nfa *nf, node *n, int *pa, int *pb){	int i;	int a, b;		REQ(n, ITEM);	i = n->n_nchildren;	REQN(i, 1);	n = n->n_child;	if (n->n_type == LSQB) {		REQN(i, 3);		n++;		REQ(n, RHS);		*pa = addnfastate(nf);		*pb = addnfastate(nf);		addnfaarc(nf, *pa, *pb, EMPTY);		compile_rhs(ll, nf, n, &a, &b);		addnfaarc(nf, *pa, a, EMPTY);		addnfaarc(nf, b, *pb, EMPTY);		REQN(i, 1);		n++;		REQ(n, RSQB);	}	else {		compile_atom(ll, nf, n, pa, pb);		if (--i <= 0)			return;		n++;		addnfaarc(nf, *pb, *pa, EMPTY);		if (n->n_type == STAR)			*pb = *pa;		else			REQ(n, PLUS);	}} static voidcompile_atom(labellist *ll, nfa *nf, node *n, int *pa, int *pb){	int i;		REQ(n, ATOM);	i = n->n_nchildren;	REQN(i, 1);	n = n->n_child;	if (n->n_type == LPAR) {		REQN(i, 3);		n++;		REQ(n, RHS);		compile_rhs(ll, nf, n, pa, pb);		n++;		REQ(n, RPAR);	}	else if (n->n_type == NAME || n->n_type == STRING) {		*pa = addnfastate(nf);		*pb = addnfastate(nf);		addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str));	}	else		REQ(n, NAME);} static voiddumpstate(labellist *ll, nfa *nf, int istate){	nfastate *st;	int i;	nfaarc *ar;		printf("%c%2d%c",		istate == nf->nf_start ? '*' : ' ',		istate,		istate == nf->nf_finish ? '.' : ' ');	st = &nf->nf_state[istate];	ar = st->st_arc;	for (i = 0; i < st->st_narcs; i++) {		if (i > 0)			printf("\n    ");		printf("-> %2d  %s", ar->ar_arrow,			PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));		ar++;	}	printf("\n");} static voiddumpnfa(labellist *ll, nfa *nf){	int i;		printf("NFA '%s' has %d states; start %d, finish %d\n",		nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);	for (i = 0; i < nf->nf_nstates; i++)		dumpstate(ll, nf, i);}  /* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */ static voidaddclosure(bitset ss, nfa *nf, int istate){	if (addbit(ss, istate)) {		nfastate *st = &nf->nf_state[istate];		nfaarc *ar = st->st_arc;		int i;				for (i = st->st_narcs; --i >= 0; ) {			if (ar->ar_label == EMPTY)				addclosure(ss, nf, ar->ar_arrow);			ar++;		}	}} typedef struct _ss_arc {	bitset	sa_bitset;	int	sa_arrow;	int	sa_label;} ss_arc; typedef struct _ss_state {	bitset	ss_ss;	int	ss_narcs;	struct _ss_arc	*ss_arc;	int	ss_deleted;	int	ss_finish;	int	ss_rename;} ss_state; typedef struct _ss_dfa {	int	sd_nstates;	ss_state *sd_state;} ss_dfa; /* Forward */static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits,		       labellist *ll, char *msg);static void simplify(int xx_nstates, ss_state *xx_state);static void convert(dfa *d, int xx_nstates, ss_state *xx_state); static voidmakedfa(nfagrammar *gr, nfa *nf, dfa *d){	int nbits = nf->nf_nstates;	bitset ss;	int xx_nstates;	ss_state *xx_state, *yy;	ss_arc *zz;	int istate, jstate, iarc, jarc, ibit;	nfastate *st;	nfaarc *ar;		ss = newbitset(nbits);	addclosure(ss, nf, nf->nf_start);	xx_state = (ss_state *)PyObject_MALLOC(sizeof(ss_state));	if (xx_state == NULL)		Py_FatalError("no mem for xx_state in makedfa");	xx_nstates = 1;	yy = &xx_state[0];	yy->ss_ss = ss;	yy->ss_narcs = 0;	yy->ss_arc = NULL;	yy->ss_deleted = 0;	yy->ss_finish = testbit(ss, nf->nf_finish);	if (yy->ss_finish)		printf("Error: nonterminal '%s' may produce empty.\n",			nf->nf_name);		/* This algorithm is from a book written before	   the invention of structured programming... */ 	/* For each unmarked state... */	for (istate = 0; istate < xx_nstates; ++istate) {		size_t size;		yy = &xx_state[istate];		ss = yy->ss_ss;		/* For all its states... */		for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {			if (!testbit(ss, ibit))				continue;			st = &nf->nf_state[ibit];			/* For all non-empty arcs from this state... */			for (iarc = 0; iarc < st->st_narcs; iarc++) {				ar = &st->st_arc[iarc];				if (ar->ar_label == EMPTY)					continue;				/* Look up in list of arcs from this state */				for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {					zz = &yy->ss_arc[jarc];					if (ar->ar_label == zz->sa_label)						goto found;				}				/* Add new arc for this state */				size = sizeof(ss_arc) * (yy->ss_narcs + 1);				yy->ss_arc = (ss_arc *)PyObject_REALLOC(                                                            yy->ss_arc, size);				if (yy->ss_arc == NULL)					Py_FatalError("out of mem");				zz = &yy->ss_arc[yy->ss_narcs++];				zz->sa_label = ar->ar_label;				zz->sa_bitset = newbitset(nbits);				zz->sa_arrow = -1;			 found:	;				/* Add destination */				addclosure(zz->sa_bitset, nf, ar->ar_arrow);			}		}		/* Now look up all the arrow states */		for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {			zz = &xx_state[istate].ss_arc[jarc];			for (jstate = 0; jstate < xx_nstates; jstate++) {				if (samebitset(zz->sa_bitset,					xx_state[jstate].ss_ss, nbits)) {					zz->sa_arrow = jstate;					goto done;				}			}			size = sizeof(ss_state) * (xx_nstates + 1);			xx_state = (ss_state *)PyObject_REALLOC(xx_state,                                                                     size);			if (xx_state == NULL)				Py_FatalError("out of mem");			zz->sa_arrow = xx_nstates;			yy = &xx_state[xx_nstates++];			yy->ss_ss = zz->sa_bitset;			yy->ss_narcs = 0;			yy->ss_arc = NULL;			yy->ss_deleted = 0;			yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish);		 done:	;		}	}		if (Py_DebugFlag)		printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,						"before minimizing");		simplify(xx_nstates, xx_state);		if (Py_DebugFlag)		printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,						"after minimizing");		convert(d, xx_nstates, xx_state);		/* XXX cleanup */} static voidprintssdfa(int xx_nstates, ss_state *xx_state, int nbits,	   labellist *ll, char *msg){	int i, ibit, iarc;	ss_state *yy;	ss_arc *zz;		printf("Subset DFA %s\n", msg);

Lines 1–500 of 706. Load more