cra.c

来自「COCO類似C的編譯器」· C语言 代码 · 共 1,269 行 · 第 1/3 页

	if (gn->STATE >= 0) return; /* already visited */
	if (state==-1) state = NewState();
	gn->STATE = state;
	if (IsNullableGraph(p)) {
		PStateNode sn = GetStateP(state);
		CR_ASSERT(sn != NULL);
		sn->end_of = sp;
	}
	switch (gn->type) {
	case T_CHAR:
	case T_CLASS:
		NumberNodes(abs(gn->next), -1, sp);
		break;
	case T_ALT:
		NumberNodes(gn->INNER, state, sp);
		NumberNodes(gn->ALT, state, sp);
		break;
	case T_OPT:
		NumberNodes(abs(gn->next), -1, sp);
		NumberNodes(gn->INNER, state, sp);
		break;
	case T_REP:
		NumberNodes(abs(gn->next), state, sp);
		NumberNodes(gn->INNER, state, sp);
		break;
	}
}

static void InitGraphState(PGraphNode gn)
{
	gn->STATE = -1;
}

/* convert syntax graph to automata */
void ConvertToStates(int gp, int sp)
{
	Collection_ForEach(&nodes_tab, (Collection_Func) InitGraphState);
	CompFollowNode(gp, 0);
	NumberNodes(gp, root_state, sp);
	Set_Init(&Visited_Nodes);
	Set_Init(&Stepped_Nodes);
	MakeTrans(gp, TRUE, sp);
	CleanGraphTab();
	Set_Done(&Visited_Nodes);
	Set_Done(&Stepped_Nodes);
}

/* check the DFA if can match a string */
int MatchDFA(byte *str, int sp)
{
	int matched_sp, s, s1, to, i, len, t;
	int weak_match;
	GraphNode gn;
	PStateNode state;
	PTransNode tp;

	s = root_state;
	i = 1;
	weak_match = 0;
	len = strlen((char *) str) - 1;
	while (1) {
		if (i == len) break;
		s1 = GetTransition(s, str[i]);
		if (s1 == -1) break;
		t  = FindTrans(s,str[i]);
		state = GetStateP(s);
		tp = GetTransP(&state->trans_list, t);
		if (tp->type == T_CLASS) weak_match = 1;
		s = s1;
		i++;
	}

	if (weak_match && i < len) {
		s = root_state; i=1; dirty_DFA=1;
	}

	while (i < len) {  /* make new DFA from str[i..len-1] */
		to = NewState();
		gn.type = T_CHAR;
		gn.SYMLINK = str[i];
		gn.CONTEXT = T_NORMAL;
		NewTransition(s, &gn, to);
		if (weak_match) {
			weak_match = 0;
			t = FindTrans(s,str[i]);
			state = GetStateP(s);
			tp = GetTransP(&state->trans_list, t);
		}
		s = to;
		i++;
	}

	state = GetStateP(s);
	CR_ASSERT(state != NULL);
	matched_sp = state->end_of;
	if (matched_sp == 0) state->end_of = sp;
	return matched_sp;
}

static void PrintTrans(PTransNode a)
{
	Set set;
	Set_Init(&set);
	if (a->type == T_CHAR) Set_AddItem(&set, a->sym);
	else
		if (a->type == T_CLASS) {
			PClassNode cn = GetClassP(a->sym);
			CR_ASSERT(cn != NULL);
			Set_Union(&set, &cn->data);
		}
	printf("Trans=(Ch=");
	Set_PrintChar(&set);
	printf(",States=");
	Set_PrintInt(&a->to_states);
	printf(")");
	Set_Done(&set);
}

/* generate unique transitions from two overlapping transitions */
static void SplitTrans(int s, PTransNode a, PTransNode b)
{
	TransNode c;
	Set seta, setb, setc;
	c.tc = T_NONE;

	Set_Init(&seta);
	Set_Init(&setb);
	Set_Init(&setc);

	GetTransChars(a, &seta);
	GetTransChars(b, &setb);

#if DEBUG
	printf("SplitTrans(%d,",s);
	PrintTrans(a);
	printf(",");
	PrintTrans(b);
	printf("):\n");
#endif
	
	if (Set_Equal(&seta, &setb)) {
		CombineTrans(a, b);
		DelTrans(s, b);
	} else
		if (Set_Includes(&seta, &setb)) {
			Set_Copy(&setc, &seta);
			Set_Diference(&setc, &setb);
			CombineTrans(b, a);
			ChangeTrans(a, &setc);
		}
		else
			if (Set_Includes(&setb, &seta)) {
				Set_Copy(&setc, &setb);
				Set_Diference(&setc, &seta);
				CombineTrans(a, b);
				ChangeTrans(b, &setc);
			}
			else {
				Set_Copy(&setc, &seta);
				Set_Intersect(&setc, &setb);
				Set_Diference(&seta, &setc);
				Set_Diference(&setb, &setc);
				ChangeTrans(a, &seta);
				ChangeTrans(b, &setb);

				Set_Init(&c.to_states);
				c.tc = T_NONE;
				CombineTrans(&c, a);
				CombineTrans(&c, b);
				ChangeTrans(&c, &setc);
				AddTrans(s, &c);
			}

#if DEBUG
	printf("Result = (");
	PrintTrans(a);

	if (b->tc != T_NONE) {
		printf(",");
		PrintTrans(b);
	}

	if (c.tc != T_NONE) {
		printf(",");
		PrintTrans(&c);
	}
	printf(")\n");
#endif

	Set_Done(&seta);
	Set_Done(&setb);
	Set_Done(&setc);
}

/* make all transitions in the state unique */
static int MakeUnique(int s)
{
	PStateNode state;
	Collection *trans_tab;
	PTransNode a, b;
	int i, j, c, changed = 0;

	state = GetStateP(s);
	CR_ASSERT(state != NULL);
	trans_tab = &(state->trans_list);
	c = Collection_Count(trans_tab);
	for (i = 0; i < c; i++) {
		trans_tab = &(state->trans_list);
		c = Collection_Count(trans_tab);

		a = GetTransP(trans_tab, i);
		CR_ASSERT(a != NULL);
		if (a->type == T_NONE) continue;  /* Trans Deleted??? */
		for(j = i + 1; j < c; j++) {
			trans_tab = &(state->trans_list);
			c = Collection_Count(trans_tab);

			b = GetTransP(trans_tab, j);
			CR_ASSERT(b != NULL);
			if (b->type == T_NONE) continue;  /* Trans Deleted??? */
			if (OverlapTrans(a, b)) {
				SplitTrans(s, a, b);
				changed = 1;
			}
		}
	}
	return changed;
}

/* return a melted state if known */
static int KnownMelt(Set *set)
{
	PMeltedNode melt;
	int i, c = Collection_Count(&melted_tab);

	for (i = 0; i < c; i++) {
		melt = GetMeltedP(i);
		CR_ASSERT(melt != NULL);
		if (Set_Equal(set, &melt->set)) return i;
	}
	return -1;
}

/* add the melted states numbers to 'set' */
static void AddMeltSet(int s, Set *set)
{
	PMeltedNode melt;
	int i, c = Collection_Count(&melted_tab);

	for (i = 0; i < c; i++) {
		melt = GetMeltedP(i);
		CR_ASSERT(melt != NULL);
		if (melt->state==s) {
			 Set_Union(set, &melt->set);
			 break;
		}
	}
}

/* get information about states_set */
static int GetStateSet(Set *state_set, Set *set, int *end_of, int *ctx)
{
	int f, s;
	int correct = TRUE;
	PStateNode state;
	char err[100];

	Set_Clean(set);
	*end_of = 0;
	*ctx = T_NONE;
	Set_GetRange(state_set, &s, &f);
	for ( ;s <= f; s++)
		if (Set_IsItem(state_set, s)) {
			if (s <= last_sim_state) Set_AddItem(set, s);
			else AddMeltSet(s, set);
			state = GetStateP(s);
			CR_ASSERT(state != NULL);
			if (state->end_of != 0) {
				if (*end_of == 0 || *end_of == state->end_of) {
					*end_of = state->end_of;
				} else {
					PTermNode tn1 = GetTermP(*end_of),
					tn2 = GetTermP(state->end_of);
					CR_ASSERT(tn1 != NULL);
					CR_ASSERT(tn2 != NULL);
					sprintf(err, "Tokens %s (%d) and %s (%d) cannot be distinguished.",
					tn1->name, *end_of, tn2->name, state->end_of);
					fprintf(lstfile, "%s\n", err);
					correct = FALSE;
				}
			}
			if (state->ctx != T_NONE) {
				*ctx = T_CONTEXT;
				if (state->end_of != 0) {
					PTermNode tn1 = GetTermP(*end_of),
					tn2 = GetTermP(state->end_of);
					CR_ASSERT(tn1 != NULL);
					CR_ASSERT(tn2 != NULL);
					sprintf(err, "Ambiguous CONTEXT clause. Tokens %s (%d) and %s (%d)",
					tn1->name, *end_of, tn2->name, state->end_of);
					fprintf(lstfile, "%s\n", err);
					correct = FALSE;
				}
			}
		}
	return correct;
}

/* copy all the transitions from state_set states to the state 'sn' */
static void FillWithTrans(int sn, Set *state_set)
{
	PTransNode t;
	TransNode t1;
	PStateNode state;
	Collection *trans_tab;
	int i, c, s, f;

	Set_GetRange(state_set, &s, &f);
	for (; s <= f ; s++)
		if (Set_IsItem(state_set, s)) {
			state = GetStateP(s);
			CR_ASSERT(state != NULL);
			trans_tab = &(state->trans_list);
			c = Collection_Count(trans_tab);
			for(i = 0; i < c; i++) {
				t = GetTransP(trans_tab, i);
				CR_ASSERT(t != NULL);
				Collection_Get(trans_tab, i, &t1);
				if (t->type != T_NONE) {
					Set_Init(&t1.to_states);
					Set_Copy(&t1.to_states, &t->to_states);
					AddTrans(sn, &t1);
				}
			}
		}
}

/* melt state_tab appearing with a shift of the same symbol */
static int MeltStates(int s)
{
	int s1, i, c, m, end_of, ctx, change, correct = TRUE;
	PStateNode state, state1;
	PMeltedNode melt;
	Collection *trans_tab;
	Set set;
	PTransNode a;

	Set_Init(&set);
	state = GetStateP(s);
	CR_ASSERT(state != NULL);
	trans_tab = &(state->trans_list);
	c = Collection_Count(trans_tab);
	for (i = 0; i < c; i++) {
		a = GetTransP(trans_tab, i);
		CR_ASSERT(a != NULL);
		if (a->type == T_NONE) continue;  /* Trans Deleted??? */
		if (Set_Elements(&a->to_states) <= 1) continue;  /* Trans to 1 state */
		/* Trans to more than 1 state => melt */
		if (!GetStateSet(&a->to_states, &set, &end_of, &ctx)) correct = FALSE;
		m = KnownMelt(&set);
		if (m == -1) {
			s1 = NewState();
			state1 = GetStateP(s1);
			CR_ASSERT(state1 != NULL);
			state1->end_of = end_of;
			state1->ctx = ctx;
			FillWithTrans(s1, &a->to_states);
			do {
				change = MakeUnique(s1);
			} while (change);
			m = NewMelt(&set, s1);
		}
		melt = GetMeltedP(m);
		CR_ASSERT(melt != NULL);
		Set_Clean(&a->to_states);
		Set_AddItem(&a->to_states, melt->state);
	}
	Set_Done(&set);
	return correct;
}

static void FindCtxStates(void)
{
	PStateNode state, state1;
	PTransNode t;
	Collection *trans_tab;
	int i, c, s, s1;

	for (s = root_state; s <= last_state; s++) {
		state = GetStateP(s);
		CR_ASSERT(state != NULL);
		trans_tab = &(state->trans_list);
		c = Collection_Count(trans_tab);
		for(i = 0; i < c; i++) {
			t = GetTransP(trans_tab, i);
			CR_ASSERT(t != NULL);
			if (t->type == T_NONE) continue;
			if (t->tc == T_CONTEXT) {
				s1 = Set_MinIndex(&t->to_states);
				state1 = GetStateP(s1);
				CR_ASSERT(state1 != NULL);
				state1->ctx = TRUE;
			}
		}
	}
}

/* mark the state reachable from valid transitions */
static int MarkToStates(PCollection trans_tab)
{
	int s, i, c, change;
	PTransNode t;
	PStateNode state;

	change = FALSE;
	c = Collection_Count(trans_tab);
	for(i = 0; i < c ; i++) {
		t = GetTransP(trans_tab, i);
		CR_ASSERT(t != NULL);
		if (t->type == T_NONE) continue;
		s = Set_MinIndex(&t->to_states);
		state = GetStateP(s);
		CR_ASSERT(state != NULL);