www.pudn.com > 12cocorc.zip > CRA.C

#include "collect.h" 
#include "set.h" 
#include "cra.h" 
#include "crt.h" 
#include "crf.h" 
#include  
#include  
#include  
#include  
 
static FILE *fscan, *fhead; 
 
static Collection state_tab;        /* states */ 
static Collection melted_tab;       /* melted_tab states */ 
static Collection comment_tab;      /* comment tab */ 
 
static int last_sim_state;          /* last simple (non melted_tab state) */ 
static int last_state;              /* last allocated state */ 
static int root_state;              /* start state of DFA */ 
static Set Visited_Nodes; 
 
#define GetStateP(p)      (PStateNode) Collection_At(&state_tab, p) 
#define GetMeltedP(p)     (PMeltedNode) Collection_At(&melted_tab, p) 
#define GetTransP(list,p) (PTransNode) Collection_At(list, p) 
#define GetCommentP(p)    (PCommentNode) Collection_At(&comment_tab, p) 
 
 
extern void SemError(int); 
 
/***************************************************************** 
***          Comment management Functions                      *** 
*****************************************************************/ 
 
/* Convert a Comment Graph to a String */ 
static int GraphToComment(int gp, char *s) 
{ 
	PGraphNode gn; 
 
	while (gp > 0) { 
		gn = GetGraphP(gp); 
		CR_ASSERT(gn != NULL); 
		if (gn->type == T_CHAR) *s++ = (char) gn->SYMLINK; 
		if (gn->type == T_CLASS) { 
			PClassNode sn = GetClassP(gn->SYMLINK); 
			int i, c; 
			CR_ASSERT(sn != NULL); 
			Set_GetRange(&sn->data, &i, &c); 
			for (; i <= c; i++) 
				if (Set_IsItem(&sn->data, i)) *s++ = (byte) i; 
		} 
		gp = gn->next; 
	} 
	*s = '\0'; 
	return TRUE; 
} 
 
/* install a new comment */ 
void NewComment(int start_token, int end_token, int nested) 
{ 
	int p; 
	PCommentNode n; 
	char temp[255]; 
 
	p = Collection_New(&comment_tab); 
	n = GetCommentP(p); 
	CR_ASSERT(n != NULL); 
	GraphToComment(start_token, temp); 
	if (strlen(temp) > 2) SemError(125); 
	temp[2] = '\0'; 
	strcpy(n->start_token, temp); 
	GraphToComment(end_token, temp); 
	if (strlen(temp) > 2) SemError(125); 
	temp[2] = '\0'; 
	strcpy(n->end_token, temp); 
	n->nested = nested; 
} 
 
static void Func_ShowComment(PCommentNode n, int p) 
{ 
	fprintf(lstfile, "%3d| FROM %s  TO  %s ", p, n->start_token, n->end_token); 
	if (n->nested) fprintf(lstfile, "NESTED\n"); 
	else fprintf(lstfile, "\n"); 
} 
 
/* show all comments */ 
void ShowCommentTab() 
{ 
	fprintf(lstfile, "\nCOMMENTS\n"); 
	Collection_ForEachPos(&comment_tab, (Collection_FuncPos) Func_ShowComment); 
} 
 
/* add a new transition to a state */ 
static void AddTrans(int sp, PTransNode t) 
{ 
	PStateNode sn; 
	int n; 
 
	sn = GetStateP(sp); 
	CR_ASSERT(sn != NULL); 
	n = Collection_New(&sn->trans_list); 
	Collection_Put(&sn->trans_list, n, t); 
} 
 
/* delete transition from a state */ 
static void DelTrans(int snr, PTransNode t) 
{ 
	PStateNode sn; 
	PTransNode t1; 
	int c, i; 
 
	sn = GetStateP(snr); 
	CR_ASSERT(sn != NULL); 
	c = Collection_Count(&sn->trans_list); 
	for (i = 0; i < c; i++) { 
		t1 = GetTransP(&sn->trans_list, i); 
		CR_ASSERT(t1 != NULL); 
		if (t1->type == t->type && t1->sym == t->sym && t1->tc == t->tc 
				&& &t1->to_states == &t->to_states) { 
			t1->type = T_NONE; 
			return; 
		} 
	} 
} 
 
/* find a valid transition with ch from state snr */ 
static int FindTrans(int snr, byte ch) 
{ 
	PStateNode sn; 
	PTransNode t; 
	int c, i; 
 
	sn = GetStateP(snr); 
	CR_ASSERT(sn != NULL); 
	c = Collection_Count(&sn->trans_list); 
	for (i = 0; i < c; i++) { 
		t = GetTransP(&sn->trans_list, i); 
		CR_ASSERT(t != NULL); 
		if (t->type == T_CHAR) { 
			if (t->sym == ch) return i; 
		} else 
			if (t->type == T_CLASS) { 
				PClassNode cn = GetClassP(t->sym); 
				CR_ASSERT(cn != NULL); 
				if (Set_IsItem(&cn->data, ch)) return i; 
			} 
	} 
	return UNDEF; 
} 
 
/* change an old transition with a new character set */ 
static void ChangeTrans(PTransNode t, Set *set) 
{ 
	if (Set_Elements(set) == 1) { 
		t->type = T_CHAR; 
		t->sym = Set_MinIndex(set); 
	} else { 
		int n = FindClassWithSet(set); 
		if (n == UNDEF) n = NewClass("##", set); 
		t->type = T_CLASS; 
		t->sym = n; 
	} 
} 
 
/* combine two transitions; combine target states and Context */ 
static void CombineTrans(PTransNode a, PTransNode b) 
{ 
	CR_ASSERT(a != NULL); 
	CR_ASSERT(b != NULL); 
	Set_Union(&a->to_states, &b->to_states); 
	if (b->tc == T_CONTEXT) a->tc = T_CONTEXT; 
} 
 
/* check if two transitions overlap; Transitions with common elements */ 
static int OverlapTrans(PTransNode a, PTransNode b) 
{ 
	PClassNode cna, cnb; 
	int result = 0; 
	CR_ASSERT(a != NULL); 
	CR_ASSERT(b != NULL); 
	if (a->type == T_CHAR) { 
		if (b->type == T_CHAR) result = a->sym == b->sym; 
		else 
			if (b->type == T_CLASS) { /* Char with Class */ 
				cnb = GetClassP(b->sym); 
				CR_ASSERT(cnb != NULL); 
				result = Set_IsItem(&cnb->data, a->sym); 
			} 
	} else 
		if (a->type == T_CLASS) { 
			if (b->type == T_CHAR) { /* Char with Class */ 
				cna = GetClassP(a->sym); 
				CR_ASSERT(cna != NULL); 
				result = Set_IsItem(&cna->data, b->sym); 
			} else 
				if (b->type == T_CLASS) { /* Class with Class */ 
					cna = GetClassP(a->sym); 
					cnb = GetClassP(b->sym); 
					CR_ASSERT(cna != NULL); 
					CR_ASSERT(cnb != NULL); 
					result = ! Set_Diferent(&cna->data, &cnb->data); 
				} 
		} 
	return result; 
} 
 
 
/* create a new melted state (Join 2 or more old state) */ 
static int NewMelt(Set *set, int s) 
{ 
	int n; 
	PMeltedNode mn; 
 
	n = Collection_New(&melted_tab); 
	mn = GetMeltedP(n); 
	CR_ASSERT(mn != NULL); 
	Set_Init(&mn->set); 
	Set_Union(&mn->set, set); 
	mn->state = s; 
	return n; 
} 
 
/* create a new state */ 
static int NewState() 
{ 
	PStateNode sn; 
	last_state = Collection_New(&state_tab); 
	sn = GetStateP(last_state); 
	CR_ASSERT(sn != NULL); 
	sn->end_of = 0; 
	sn->ctx = T_NONE; 
	sn->gen_state_no = -1; 
	Collection_Init(&sn->trans_list, sizeof(TransNode), 1, 1); 
	return last_state; 
} 
 
static void Func_DoneTrans(PTransNode tn) 
{ 
	Set_Done(&tn->to_states); 
} 
 
static void DoneState(PStateNode s) 
{ 
	s->end_of = 0; 
	s->ctx = 0; 
	Collection_ForEach(&s->trans_list, (Collection_Func) Func_DoneTrans); 
	Collection_Done(&s->trans_list); 
} 
 
/* generate transition (g.state, g.sym) --> tostate */ 
static void NewTransition(int from_state, PGraphNode gn, int to_state) 
{ 
	TransNode t; 
	if (to_state == root_state) SemError(121); 
	t.type = gn->type; 
	t.sym  = gn->SYMLINK; 
	t.tc   = gn->CONTEXT; 
	Set_Init(&t.to_states); 
	Set_AddItem(&t.to_states, to_state); 
	AddTrans(from_state, &t); 
} 
 
/* find a transition from state s with char ch */ 
static int GetTransition(int s, byte ch) 
{ 
	int tn; 
	PTransNode t; 
	PStateNode sn; 
 
	tn = FindTrans(s, ch); 
	if (tn == UNDEF) return UNDEF; 
	sn = GetStateP(s); 
	CR_ASSERT(sn != NULL); 
	t  = GetTransP(&sn->trans_list, tn); 
	CR_ASSERT(t != NULL); 
	tn = Set_MinIndex(&t->to_states); 
	return tn; 
} 
 
/* get transition characters */ 
static void MakeSet(PTransNode t, Set *set) 
{ 
	Set_Clean(set); 
	if (t->type == T_CHAR) Set_AddItem(set, t->sym); 
	else 
		if (t->type == T_CLASS) { 
			PClassNode cn = GetClassP(t->sym); 
			CR_ASSERT(cn != NULL); 
			Set_Union(set, &cn->data); 
		} 
} 
 
/* combine transitions to the same state */ 
static void CombineShifts() 
{ 
	int s, i, j, c; 
	PStateNode sn; 
	PTransNode a, b; 
	Collection *trans_tab; 
	Set seta, setb; 
 
	Set_Init(&seta); 
	Set_Init(&setb); 
 
	for(s = root_state; s <= last_state; s++) { 
		sn = GetStateP(s); 
		CR_ASSERT(sn != NULL); 
		trans_tab = &sn->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 */ 
			for(j = i + 1; j < c; j++) { 
				b = GetTransP(trans_tab, j); 
				CR_ASSERT(b != NULL); 
				if (b->type == T_NONE) continue;  /* Trans Deleted */ 
				if (Set_Equal(&a->to_states, &b->to_states) && a->tc == b->tc) { 
					MakeSet(a, &seta); 
					MakeSet(b, &setb); 
					Set_Union(&seta, &setb); 
					ChangeTrans(a, &seta); 
					DelTrans(s, b); 
				} 
			} 
		} 
	} 
	Set_Done(&seta); 
	Set_Done(&setb); 
} 
 
/* return the automata state associated with a syntax graph node */ 
static int TheState(int gp, int sp) 
{ 
	int s; 
	PGraphNode gn; 
	PStateNode sn; 
 
	if (gp == 0) { 
		s = NewState(); 
		sn = GetStateP(s); 
		CR_ASSERT(sn != NULL); 
		sn->end_of = sp; 
		return s; 
	} 
	gn = GetGraphP(gp); 
	CR_ASSERT(gn != NULL); 
	return gn->STATE; 
} 
 
/* walk through the syntax graph to create the automata */ 
static void Step(int from, int gp, int sp) 
{ 
	PGraphNode gn; 
	if (gp == 0) return; 
	gn = GetGraphP(gp); 
	CR_ASSERT(gn != NULL); 
	switch (gn->type) { 
	case T_CHAR: 
	case T_CLASS: 
		NewTransition(from, gn, TheState(abs(gn->next), sp)); 
		break; 
	case T_ALT: 
		Step(from, gn->INNER, sp); 
		Step(from, gn->ALT, sp); 
		break; 
	case T_OPT: 
	case T_REP: 
		Step(from, abs(gn->next), sp); 
		Step(from, gn->INNER, sp); 
		break; 
	} 
} 
 
/* walk through the syntax graph to create the automata accepting sp */ 
static void MakeTrans(int p, int start, int sp) 
{ 
	PGraphNode gn; 
 
	if (p == 0 || Set_IsItem(&Visited_Nodes,p)) return; /* end of Graph */ 
	Set_AddItem(&Visited_Nodes,p); 
 
	gn = GetGraphP(p); 
	CR_ASSERT(gn != NULL); 
	if (start) Step(gn->STATE, p, sp); 
	switch (gn->type) { 
	case T_CHAR: 
	case T_CLASS: 
		MakeTrans(abs(gn->next), TRUE, sp); 
		break; 
	case T_ALT: 
		MakeTrans(gn->INNER, FALSE, sp); 
		MakeTrans(gn->ALT, FALSE, sp); 
		break; 
	case T_OPT: 
		MakeTrans(abs(gn->next),TRUE, sp); 
		MakeTrans(gn->INNER, FALSE, sp); 
		break; 
	case T_REP: 
		MakeTrans(abs(gn->next), FALSE, sp); 
		MakeTrans(gn->INNER, FALSE, sp); 
		break; 
	} 
} 
 
static void NumberNodes(int p, int state, int sp) 
{ 
	PGraphNode gn; 
 
	if (p == 0) return;         /* end of Graph */ 
	gn = GetGraphP(p); 
	CR_ASSERT(gn != NULL); 
	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); 
	MakeTrans(gp, TRUE, sp); 
	CleanGraphTab(); 
	Set_Done(&Visited_Nodes); 
} 
 
/* check the DFA if can match a string */ 
int MatchDFA(byte *str, int sp) 
{ 
	int matched_sp, s, s1, to, i, len; 
	GraphNode gn; 
	PStateNode state; 
 
	s = root_state; 
	i = 1; 
	len = strlen((char *) str) - 1; 
	while (1) { 
		if (i == len) break; 
		s1 = GetTransition(s, str[i]); 
		if (s1 == -1) break; 
		s = s1; 
		i++; 
	} 
 
	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); 
		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; 
} 
 
/* generate unique transitions from two overlapping transitions */ 
static void SplitTrans(int s, PTransNode a, PTransNode b) 
{ 
	TransNode c; 
	Set seta, setb, setc; 
 
	Set_Init(&seta); 
	Set_Init(&setb); 
	Set_Init(&setc); 
 
	MakeSet(a, &seta); 
	MakeSet(b, &setb); 
	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); 
			} 
	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 meted 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() 
{ 
	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); 
		if (state->gen_state_no == -1) change = TRUE; 
		state->gen_state_no = 1; 
	} 
	return change; 
} 
 
 
/* mark all states not reachable from state 0 */ 
static void DeleteRedundantStates() 
{ 
	PStateNode state; 
	int s, change; 
 
	state = GetStateP(0); 
	CR_ASSERT(state != NULL); 
	state->gen_state_no = 0; 
	do { 
		change = FALSE; 
		for (s = root_state; s <= last_state; s++) { 
			state = GetStateP(s); 
			CR_ASSERT(state != NULL); 
			if (state->gen_state_no == -1) continue; 
			if (MarkToStates(&state->trans_list)) change = TRUE; 
		} 
	} while (change); 
} 
 
int MakeDeterministic() 
{ 
	int s, correct, changed; 
 
	last_sim_state = last_state; 
 
	if (last_state == 0) return TRUE; 
 
	FindCtxStates(); 
	for (s = root_state; s <= last_state; s++) { 
		do { 
			changed = MakeUnique(s); 
		} while (changed); 
	} 
 
	correct = TRUE; 
	for (s = root_state; s <= last_state; s++) { 
		if (!MeltStates(s)) correct = FALSE; 
	} 
 
	CombineShifts(); 
	CleanGraphTab(); 
	return correct; 
} 
 
int StrToGraph(byte *name) 
{ 
	int next = 0, i, len, gp, first = 0; 
	len = strlen((char *) name); 
	for (i = 1; i <= len - 2; i++) { 
		gp = MakeGraph(T_CHAR, name[i]); 
		if (next) next = LinkGraph(next, gp); 
		else first = next = gp; 
	} 
	return first; 
} 
 
/* generate Ignore Chars */ 
static void GenIgnore() 
{ 
	int p; 
	PClassNode cn; 
 
	p = FindClass("@ignore_chars"); 
	cn = GetClassP(p); 
	GenCode(fscan, "while (%C) Scan_NextCh();", &cn->data); 
} 
 
/* generate comment part in GET*/ 
static void GenCommentPart() 
{ 
	int p; 
	PCommentNode n; 
	Set set; 
 
	Set_Init(&set); 
	p = 0; 
	while (p < Collection_Count(&comment_tab)) { 
		n = (PCommentNode) Collection_At(&comment_tab, p); 
		Set_AddItem(&set, n->start_token[0]); 
		p++; 
	} 
	if (!Set_Empty(&set)) 
		GenCode(fscan, "if ((%C) && Comment()) goto start;", &set); 
	Set_Done(&set); 
} 
 
/* generate State0 vector */ 
static void GenState0() 
{ 
	int i, n; 
 
	for (i = 0; i <= 254; i++) { 
		if (i % 30 == 0 && i / 30 > 0) GenCode(fscan, "$$"); 
		n = GetTransition(0, (byte) i); 
		if (n < 0) n = 0; 
		GenCode(fscan, "%d,", n); 
	} 
	n = GetTransition(0, 255); 
	if (n < 0) n = 0; 
	GenCode(fscan, "%d", n); 
} 
 
/* generate literal class search */ 
 
static void fixname(char *s, char *d) 
{ 
	char temp[MAX_ID_LEN]; 
	strcpy(temp, s); s = temp; 
	s[strlen(s) - 1] = '\0'; s++; 
	*d++ = '"'; 
	while (*s) { 
		if (*s == '\\') *d++ = '\\'; 
		if (*s == '"') *d++ = '\\'; 
		*d++ = *s++; 
	} 
	*d++ = '"'; 
	*d = '\0'; 
} 
 
static void GenLiterals() 
{ 
	char token[MAX_ID_LEN], name[MAX_ID_LEN]; 
	int i, p, start; 
	PTermNode n; 
 
	for (i = 33; i < 127; i++) { 
		p = 0; 
		start = 0; 
		while (p < term_tab.el_free) { 
			n = GetTermP(p); 
			CR_ASSERT(n != NULL); 
			if (n->type == T_LITTOKEN && n->name[1] == i) { 
				GetTermName(p, token); 
				if (start == 0) { 
					if (i != '\\') GenCode(fscan, "$1case '%c':$$", i); 
					else GenCode(fscan, "$1case %d:$$", i); 
				} 
				fixname(n->name, name); 
				GenCode(fscan, "$2if (EqualStr(%s)) return %s;$$", name, token); 
				start = 1; 
			} 
			p++; 
		} 
		if (start) GenCode(fscan, "$2break;$$"); 
	} 
} 
 
/* generate comment function */ 
static void GenCommentBody(PCommentNode n) 
{ 
	CR_ASSERT(n != NULL); 
	GenCode(fscan, "$2while (1) {$$" 
			"$3if (Scan_Ch== %#) { /* 5 */$$", n->end_token[0]); 
	if (n->end_token[1] == 0) { 
		GenCode(fscan, "$4Level--; Scan_NextCh(); Scan_ComEols = Scan_CurrLine - StartLine;$$" 
				"$4if(Level == 0) return 1;$$"); 
	} else { 
		GenCode(fscan, "$4Scan_NextCh();$$" 
				"$4if (Scan_Ch == %#) { /* 6 */$$", n->end_token[1]); 
		GenCode(fscan, "$5Level--; Scan_NextCh(); Scan_ComEols = Scan_CurrLine - StartLine;$$" 
				"$5if(Level == 0) return 1;$$" 
				"$4} /* 6 */ $$"); 
	} 
	if (n->nested) { 
		GenCode(fscan, "$3} else  /* 5 */$$"); 
		GenCode(fscan, "$3if (Scan_Ch == %#) {$$", n->start_token[0]); 
		if (n->start_token[1] == 0) { 
			GenCode(fscan, "$4Level++; Scan_NextCh();$$"); 
		} else { 
			GenCode(fscan, "$4Scan_NextCh();$$"); 
			GenCode(fscan, "$4if (Scan_Ch == %#) { Level++; Scan_NextCh(); }$$", n->start_token[1]); 
		} 
	} 
	GenCode(fscan, "$3} else /* 5 */$$"); 
	GenCode(fscan, "$3if (Scan_Ch == EOF_CHAR) return 0;$$$3else Scan_NextCh();$$"); 
	GenCode(fscan, "$2} /* while */$$"); 
} 
 
/* generate comment */ 
static void GenComment(PCommentNode n) 
{ 
	CR_ASSERT(n != NULL); 
	GenCode(fscan, "if (Scan_Ch == %#) { /* 1 */$$", n->start_token[0]); 
	if (n->start_token[1] == 0) { 
		GenCode(fscan, "$1Scan_NextCh();$$"); 
		GenCommentBody(n); 
	} else { 
		GenCode(fscan, "$1Scan_NextCh();$$" 
				"$1if (Scan_Ch == %#) { /* 2 */$$" 
				"$2Scan_NextCh();$$", n->start_token[1]); 
		GenCommentBody(n); 
		GenCode(fscan, "$1} else { /* 2 */$$"); 
		GenCode(fscan, "$2if (Scan_Ch == LF_CHAR) { Scan_CurrLine--; Scan_LineStart = OldLineStart; }$$"); 
		GenCode(fscan, "$2Scan_BuffPos -= 2; Scan_CurrCol = OldCol - 1; Scan_NextCh();$$"); 
		GenCode(fscan, "$1} /* 2 */$$"); 
	} 
	GenCode(fscan, "} /* 1*/$$"); 
} 
 
/* make the scanner */ 
 
/* generate State Transition */ 
static void GenStateTrans(int sn, PTransNode t, int is_context) 
{ 
	int to; 
	Set set1; 
 
	CR_ASSERT(t != NULL); 
	Set_Init(&set1); 
	if (t->type == T_CHAR) Set_AddItem(&set1, t->sym); 
	if (t->type == T_CLASS) { 
		PClassNode cn = GetClassP(t->sym); 
		Set_Copy(&set1, &cn->data); 
	} 
	to = Set_MinIndex(&t->to_states); 
	if (t->tc == T_CONTEXT) { /* Transition With Context */ 
		if (to != sn)  GenCode(fscan, "$1if (%C) { ctx++; state = %d;} else$$", &set1, to); 
		else GenCode(fscan, "$1if (%C) ctx++; else$$", &set1, to); 
	} else { 
		if (is_context) { /* Normal Transition in Context State => Reset Context*/ 
			if (to != sn)  GenCode(fscan, "$1if (%C) {ctx = 0; state = %d;} else$$", &set1, to); 
			else GenCode(fscan, "$1if (%C) ctx = 0; else$$", &set1, to); 
		} else {  /* Normal Transition */ 
			if (to != sn)  GenCode(fscan, "$1if (%C) state = %d; else$$", &set1, to); 
			else GenCode(fscan, "$1if (%C) /*same state*/; else$$", &set1, to); 
		} 
	} 
	Set_Done(&set1); 
} 
 
/* generate accepting token for a state */ 
static void GenStateAccept(int token, int is_context) 
{ 
	PTermNode tn; 
 
	if (is_context) 
		GenCode(fscan, "$1{$$" 
				"$2Scan_NextLen -= ctx; Scan_BuffPos -= ctx+1; Scan_CurrCol -= ctx+1; Scan_NextCh(); $$"); 
 
	tn = GetTermP(token); 
	CR_ASSERT(tn != NULL); 
	if (tn->type == T_CLASSLITTOKEN) 
		GenCode(fscan, "%Ireturn CheckLiteral(%T);$$", 1 + is_context, token); 
	else { 
		if (token == 0) GenCode(fscan, "%Ireturn NoSym;$$", 1 + is_context); 
		else GenCode(fscan, "%Ireturn %T;$$", 1 + is_context, token); 
	} 
 
	if (is_context) GenCode(fscan, "$1}$$"); 
} 
 
/* generate state */ 
static void GenState(PStateNode state, int sn) 
{ 
	int i, c, is_context, t_count; 
	Collection *trans_tab; 
	PTransNode t; 
 
	CR_ASSERT(state != NULL); 
	if (state->gen_state_no == -1) return; /* unused stated */ 
	is_context = (state->ctx == T_CONTEXT); 
 
	if (sn == 0) GenCode(fscan, " /* State 0; valid STATE0 Table$$"); 
	GenCode(fscan, "case %d:$$", sn); 
	trans_tab = &state->trans_list; 
	c = Collection_Count(trans_tab); 
	t_count = 0; 
	for (i = 0; i < c; i++) { 
		t = GetTransP(trans_tab, i); 
		CR_ASSERT(t != NULL); 
		if (t->type == T_NONE) continue; 
		GenStateTrans(sn, t, is_context); 
		t_count++; 
	} 
	is_context = (state->ctx == T_CONTEXT && t_count == 0); 
	i = state->end_of; 
	if (i >= FIRST_PRAGMA) i = (i - FIRST_PRAGMA) + no_sym + 1; 
	GenStateAccept(i, is_context); 
	if (t_count) GenCode(fscan, "$1break;$$"); 
	if (sn == 0) GenCode(fscan, " --------- End State0 --------- */$$"); 
} 
 
void MakeScanner() 
{ 
	DeleteRedundantStates(); 
} 
 
/* generate scanner */ 
int GenScannerOptions(FILE *Out, char *option) 
{ 
	fscan = Out; 
	if (!stricmp(option, "IgnoreCase")) { 
		GenCode(fscan, "%d", ignore_case); 
	} else 
	if (!stricmp(option, "State0")) { 
		GenState0(); 
	} else 
	if (!stricmp(option, "Literals")) { 
		GenLiterals(); 
	} else 
	if (!stricmp(option, "Comment")) { 
		Collection_ForEach(&comment_tab, (Collection_Func) GenComment); 
	} else 
	if (!stricmp(option, "GetDFA")) { 
		Collection_ForEachPos(&state_tab, (Collection_FuncPos) GenState); 
	} else 
	if (!stricmp(option, "GetIgnore")) { 
		GenIgnore(); 
	} else 
	if (!stricmp(option, "GetComment")) { 
		GenCommentPart(); 
	} else return 0; 
 
	return 1; 
} 
 
/* generate header file */ 
static void Func_GenHeaderItem(PTermNode n, int p) 
{ 
	char s[MAX_ID_LEN]; 
	GetTermName(p, s); 
	fprintf(fhead, "#define %s\t%d\t/* %s */\n", s, p, n->name); 
} 
 
void GenScannerTokens(FILE *Out) 
{ 
	fhead = Out; 
	Collection_ForEachPos(&term_tab, (Collection_FuncPos) Func_GenHeaderItem); 
	fprintf(fhead, "#define %s\t\t\t%s\t/* %s */\n", "MAXT", "NoSym", "Max Terminals"); 
} 
 
/* initialize scanner generator tables */ 
void InitScannerTab() 
{ 
	Collection_Init(&state_tab, sizeof(StateNode), 50, 10); 
	Collection_Init(&melted_tab, sizeof(MeltedNode), 10, 5); 
	Collection_Init(&comment_tab, sizeof(CommentNode), 10, 5); 
	last_state = -1; 
	root_state = NewState(); 
} 
 
/* destroy scanner generator tables */ 
static void Func_DoneState(PStateNode sn) 
{ 
	DoneState(sn); 
} 
 
static void Func_DoneMelt(PMeltedNode sn) 
{ 
	Set_Done(&sn->set); 
} 
 
void DoneScannerTab() 
{ 
	Collection_ForEach(&state_tab, (Collection_Func) Func_DoneState); 
	Collection_ForEach(&melted_tab, (Collection_Func) Func_DoneMelt); 
	Collection_Done(&state_tab); 
	Collection_Done(&melted_tab); 
	Collection_Done(&comment_tab); 
} 
 
/* dump state information to list file */ 
static void ShowState(PStateNode state, int sn) 
{ 
	Name name; 
	int i, c, tok; 
	Collection *trans_tab; 
	PTransNode t; 
	Set set1; 
 
	if (state->gen_state_no == -1) return; 
	fprintf(lstfile, "\n\nState %d: ", sn); 
	if (state->ctx) fprintf(lstfile, " Context State"); 
	fprintf(lstfile, "\n"); 
	Set_Init(&set1); 
	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; 
		Set_Clean(&set1); 
		if (t->type == T_CHAR) Set_AddItem(&set1, t->sym); 
		if (t->type == T_CLASS) { 
			PClassNode cn = GetClassP(t->sym); 
			Set_Copy(&set1, &cn->data); 
		} 
 
		fprintf(lstfile, "\t"); 
		Set_ForEach(&set1, (Set_Func) PrintAscii); 
		fprintf(lstfile, " -> "); 
		Set_ForEach(&t->to_states, (Set_Func) PrintInt); 
 
		if (t->tc == T_CONTEXT) fprintf(lstfile, "  CONTEXT Trans"); 
		fprintf(lstfile, "\n"); 
	} 
 
	tok = state->end_of; 
	if (tok >= FIRST_PRAGMA) tok = (tok - FIRST_PRAGMA) + no_sym + 1; 
	if (tok) GetTermName(tok, name); 
	else strcpy(name, "NoSym"); 
	fprintf(lstfile, "\tAccept Token:  %s (%d)\n", name, tok); 
	Set_Done(&set1); 
} 
 
void ShowDFA() 
{ 
	fprintf(lstfile, "\n\n\nDFA:\n"); 
	Collection_ForEachPos(&state_tab, (Collection_FuncPos) ShowState); 
}