crt.c

COCO類似C的編譯器

{
	PSymSetNode sn;
	if (sp == NIL) return;
	sn = GetSymSetP(sp);
	Set_Union(set, &sn->set);
}

/* symset union by index */
void IncludeSymSet(int sp, PSet set)
{
	PSymSetNode sn;
	sn = GetSymSetP(sp);
	CR_ASSERT(sn != NULL);
	Set_Union(&sn->set, set);
}

/* symset diference by index */
void ExcludeSymSet(int sp, PSet set)
{
	PSymSetNode sn;
	sn = GetSymSetP(sp);
	CR_ASSERT(sn != NULL);
	Set_Diference(&sn->set, set);
}

/* show symset */
static void Func_ShowSymSet(PSymSetNode sn, int sp)
{
	CR_ASSERT(sn != NULL);
	fprintf(lstfile, "%3d|", sp);
	switch (sn->type) {
	case T_WT  :
		fprintf(lstfile, "WEAK T = \t");
		break;
	case T_ANY :
		fprintf(lstfile, "ANY    = \t");
		break;
	case T_SYNC:
		fprintf(lstfile, "SYNC   = \t");
		break;
	}
	Set_ForEach(&sn->set, (Set_Func) PrintTerm);
	fprintf(lstfile, "\n");
}

void ShowSymSetTab(void)
{
	fprintf(lstfile, "\nSYMBOL SETS\n");
	Collection_ForEachPos(&symset_tab, (Collection_FuncPos) Func_ShowSymSet);
}

/*****************************************************************
***         Nonterminals management Functions                  ***
*****************************************************************/

/* find a nonterminal by name */
static int CompNTerm(PNTermNode ntn, PName name)
{
	return !strcmp(ntn->name, name);
}

int FindNTerm(PName name)
{
	int ntp;
	ntp = Collection_FirstThat(&nterm_tab, (Collection_Comp) CompNTerm, name);
	return ntp;
}

/* install a nonterminal */
int NewNTerm(PName name)
{
	int ntp;
	PNTermNode ntn;

	if ((ntp = FindNTerm(name)) == UNDEF) {
		ntp = Collection_New(&nterm_tab);
		ntn = GetNTermP(ntp);
		CR_ASSERT(ntn != NULL);
		strcpy(ntn->name, name);
		ntn->graph     = NIL;
		ntn->sem       = NIL;
		ntn->nullable  = FALSE;
		ntn->ready     = FALSE;
		ntn->has_attr  = FALSE;
		ntn->reachable = FALSE;
		ntn->attr      = NIL;
		Set_Init(&ntn->first);
		Set_Init(&ntn->follow);
		Set_Init(&ntn->AuxNt);
	}
	return ntp;
}

/* get nonterminal First Set */
static void GetNTermFirst(int ntp, Set *first)
{
	PNTermNode ntn;
	ntn = GetNTermP(ntp);
	CR_ASSERT(ntn != NULL);
	Set_Union(first, &(ntn->first));
}

/* get nonterminal Follow Set */
static void GetNTermFollow(int ntp, Set *follow)
{
	PNTermNode ntn;
	ntn = GetNTermP(ntp);
	CR_ASSERT(ntn != NULL);
	Set_Union(follow, &(ntn->follow));
}

/* get nonterminal Nullable */
static int IsNTermNullable(int ntp)
{
	PNTermNode ntn;
	ntn = GetNTermP(ntp);
	CR_ASSERT(ntn != NULL);
	return ntn->nullable;
}

/* show nonterminal */
static void Func_ShowNTerm(PNTermNode ntn, int ntp)
{
	if (!ntp) return;
	fprintf(lstfile, "%3d|%s\t:", ntp, ntn->name);
	if (ntn->nullable) fprintf(lstfile, "    (Nullable)");
	if (G_option) {
		fprintf(lstfile, "\n\tGraph: ");
		ShowGraph(ntn->graph);
	}
	if (F_option) {
		fprintf(lstfile, "\n\tStart With :\t");
		Set_ForEach(&ntn->first, (Set_Func) PrintTerm);
		fprintf(lstfile, "\n\tFollow =\t");
		Set_ForEach(&ntn->follow, (Set_Func) PrintTerm);
	}
	fprintf(lstfile, "\n");
}

/* show nonterminal tab */
void ShowNTermTab(void)
{
	fprintf(lstfile, "\nNO TERMINALS\n");
	Collection_ForEachPos(&nterm_tab, (Collection_FuncPos) Func_ShowNTerm);
}

/* apply "fn" to each nonterminal graph */
static void ForEachNTermGraph(Graph_Func fn)
{
	PNTermNode ntn;
	int c, i;
	c = Collection_Count(&nterm_tab);
	for (i = 1; i < c; i++) { /* for each nonterminal */
		CurrentNt = i;
		ntn = GetNTermP(i);
		CR_ASSERT(ntn != NULL);
		(*fn) (ntn->graph);
	}
}

/* apply "fn" to each nonterminal graph pasing an "p" as parameter */
static void ForEachNTermGraph_Int(Graph_FuncInt fn, int p)
{
	PNTermNode ntn;
	int c, i;
	c = Collection_Count(&nterm_tab);
	for (i = 1; i < c; i++) {
		CurrentNt = i;
		ntn = GetNTermP(i);
		CR_ASSERT(ntn != NULL);
		(*fn) (ntn->graph, p);
	}
}

/*****************************************************************
***          First & Follow Functions                          ***
*****************************************************************/

/* compute follow links in a graph */
void CompFollowNode(int gp, int fgp)
{
	PGraphNode gn;
	int next;

	while (gp>NIL) {
		gn = GetGraphP(gp);
		CR_ASSERT(gn != NULL);
		next = (gn->next != NIL) ? gn->next : fgp;
		switch(gn->type) {
		case T_OPT:
			CompFollowNode(gn->INNER, next);
			break;
		case T_REP:
			CompFollowNode(gn->INNER, gp);
			break;
		case T_ALT:
			{
				PGraphNode gn1;
				int gp1 = gp;
				while (gp1 > NIL) {
					gn1 = GetGraphP(gp1);
					CR_ASSERT(gn1 != NULL);
					CompFollowNode(gn1->INNER, next);
					gp1 = gn1->ALT;
				}
				break;
			}
		}
		if (gn->next == NIL) gn->next = -fgp;
		gp = gn->next;
	}
}

/* compute Follow links for all graphs */
static void CompAllFollowNodes(void)
{
	ForEachNTermGraph_Int((Graph_FuncInt) CompFollowNode, 0);
}

/* TRUE => node is Nullable */
static int IsNullableNode(int gp)
{
	PGraphNode gn;
	if (gp <= NIL) return TRUE;
	gn = GetGraphP(gp);
	CR_ASSERT(gn != NULL);
	switch(gn->type) {
	case T_NT :
		return IsNTermNullable(gn->SYMLINK);
	case T_OPT:
	case T_REP:
	case T_SEM:
	case T_SYNC:
		return TRUE;
	case T_ALT:
		if (IsNullableGraph(gn->INNER)) return TRUE;
		if (gn->ALT) return IsNullableNode(gn->ALT);
	}
	return FALSE; /* Terminal, Weak Terminal => Not Nullable */
}

/* TRUE => graph is Nullable */
int IsNullableGraph(int gp)
{
	if (gp <= NIL) return TRUE;
	if (IsNullableNode(gp)) {
		PGraphNode gn = GetGraphP(gp);
		CR_ASSERT(gn != NULL);
		return IsNullableGraph(gn->next);
	}
	return FALSE;
}

/* TRUE => graph is Nullable (use follow links) */
static int IsNullableNextGraph(int gp)
{
	if (gp <= NIL) return TRUE;
	if (IsNullableNode(gp)) {
		PGraphNode gn = GetGraphP(gp);
		CR_ASSERT(gn != NULL);
		return IsNullableNextGraph(abs(gn->next));
	}
	return FALSE;
}

static void CompAllNullable(void)
{
	PNTermNode ntn;
	int i, c, change;

	do { /* Loop until nothing changes */
		change = FALSE;
		c = Collection_Count(&nterm_tab);
		for (i = 1; i < c; i++) { /* for each nonterminal */
			ntn = GetNTermP(i);
			CR_ASSERT(ntn != NULL);
			if (!ntn->nullable)
				if (IsNullableNextGraph(ntn->graph)) {
					ntn->nullable = TRUE;
					ntn->ready    = TRUE;
					change        = TRUE;
				}
		}
	} while (change);
}

/* get First Terminals of a graph
   STRICT = TRUE ==> don't use follow links
*/
static void CompFirst(int gp, Set *first, int STRICT)
{
	PGraphNode gn;

	while (gp > NIL && !Set_IsItem(&FirstVisited, gp)) {
		Set_AddItem(&FirstVisited, gp);
		gn = GetGraphP(gp);
		CR_ASSERT(gn != NULL);
		switch(gn->type) {
		case T_T :
		case T_WT:
			Set_AddItem(first, gn->SYMLINK);
			break;
		case T_NT :
			{
				PNTermNode ntn = GetNTermP(gn->SYMLINK);
				CR_ASSERT(ntn != NULL);
				if (ntn->ready) GetNTermFirst(gn->SYMLINK, first);
				else CompFirst(ntn->graph, first, STRICT);
				break;
			}
		case T_ANY:
			GetSymSet(gn->SETLINK1, first);
			break;
		case T_OPT:
		case T_REP:
		case T_ALT:
			CompFirst(gn->INNER, first, STRICT);
			if (gn->type == T_ALT) CompFirst(gn->ALT, first, STRICT);
			break;
		}
		if (!IsNullableNode(gp)) break; /* Nullable => Continue */
		gp = (STRICT)? gn->next: abs(gn->next);
	}
}

/* get First Set of a graph */
void CompFirstSet(int gp, PSet first)
{
	Set_Clean(&FirstVisited);
	CompFirst(gp, first, TRUE);
}

/* get First Set of a graph (use follow links) */
static void CompNextFirstSet(int gp, Set *first)
{
	Set_Clean(&FirstVisited);
	CompFirst(gp, first, FALSE);
}

static void CompNTermFirstSet(PNTermNode ntn)
{
	ntn->ready = FALSE;
	CompFirstSet(ntn->graph, &ntn->first);
	ntn->ready = TRUE;
}

/* compute all First Sets of a nonterminal */
static void CompAllFirstSets(void)
{
	Collection_ForEach(&nterm_tab, (Collection_Func) CompNTermFirstSet);
}

/* compute Follow Set of each nonterminal in graph */
static void CompFollowSet(int gp)
{
	PGraphNode gn;

	while (gp > NIL && !Set_IsItem(&FollowVisited, gp)) {
		Set_AddItem(&FollowVisited, gp);
		gn = GetGraphP(gp);
		CR_ASSERT(gn != NULL);
		switch(gn->type) {
		case T_NT:
			{
				PNTermNode ntn = GetNTermP(gn->SYMLINK);
				CR_ASSERT(ntn != NULL);
				CompNextFirstSet(abs(gn->next), &(ntn->follow));
				if (IsNullableNextGraph(abs(gn->next)))
					Set_AddItem(&ntn->AuxNt, CurrentNt);
				break;
			}
		case T_OPT:
		case T_REP:
		case T_ALT:
			CompFollowSet(gn->INNER);
			if (gn->type == T_ALT) CompFollowSet(gn->ALT);
			break;
		}
		gp = gn->next;
	}
}

/* complete follow set by indirect nonterminal links */
static void CompleteFollow(int curr_nt)
{
	int i, c;
	PNTermNode ntn, ntn1;

	if (Set_IsItem(&FollowVisited, curr_nt)) return;
	Set_AddItem(&FollowVisited, curr_nt);
	ntn = GetNTermP(curr_nt);
	CR_ASSERT(ntn != NULL);
	Set_GetRange(&ntn->AuxNt, &i, &c);
	for (; i <= c; i++)
		if (Set_IsItem(&ntn->AuxNt, i)) {
			ntn1 = GetNTermP(i);
			CR_ASSERT(ntn1 != NULL);
			CompleteFollow(i);
			Set_Union(&ntn->follow, &ntn1->follow);
			Set_DelItem(&ntn->AuxNt, i);
		}
}

static void Func_CompFollowSet(int gp)
{
	Set_Clean(&FollowVisited);
	CompFollowSet(gp);
}

static void Func_CompleteFollowSet(int gp)
{
	Set_Clean(&FollowVisited);
	CompleteFollow(CurrentNt);
}

/* compute Follow of all nonterminals */
static void CompAllFollowSets(void)
{
	ForEachNTermGraph((Graph_Func) Func_CompFollowSet);
	ForEachNTermGraph((Graph_Func) Func_CompleteFollowSet);
}

/* return graph node index of a leading ANY in graph */
static int LeadingANY(int gp)
{
	PGraphNode gn;
	int a;

	if (gp <= NIL) return NIL;
	gn = GetGraphP(gp);
	CR_ASSERT(gn != NULL);
	switch (gn->type) {
	case T_ANY:
		return gp;
	case T_OPT:
	case T_REP:
		return LeadingANY(gn->INNER);
	case T_ALT:
		if ((a = LeadingANY(gn->INNER)) != NIL) return a;
		return a = LeadingANY(gn->ALT);
	}
	if (IsNullableNode(gp)) return LeadingANY(gn->next);
	return NIL;
}

/* exclude terminals from ANY set */
static void ExcludeANY(int gp, PSet set)
{
	PGraphNode gn;
	gn = GetGraphP(gp);
	CR_ASSERT(gn != NULL);
	if (gn->SETLINK1 == NIL) gn->SETLINK1 = NewANY();
	ExcludeSymSet(gn->SETLINK1, set);
}

/* compute ANY sets in graph */
static void CompANYSet(int gp)
{
	PGraphNode gn;
	Set set;

	Set_Init(&set);
	while (gp > NIL) {
		gn = GetGraphP(gp);
		CR_ASSERT(gn != NULL);
		switch(gn->type) {
		case T_OPT:
		case T_REP:
			{
				int a;
				CompANYSet(gn->INNER);
				if ((a = LeadingANY(gn->INNER)) != NIL) {
					Set_Clean(&set);
					CompExpected(abs(gn->next), CurrentNt, &set);
					ExcludeANY(a, &set);
				}
				break;
			}
		case T_ALT:
			{
				int gp1 = gp;
				int a;
				PGraphNode gn1;

				Set_Clean(&set);
				while (gp1 != NIL) {
					gn1 = GetGraphP(gp1);
					CR_ASSERT(gn1 != NULL);
					CompANYSet(gn1->INNER);
					if ((a = LeadingANY(gn1->INNER)) != NIL) {
						CompExpected(gn1->ALT, CurrentNt, &set);
						ExcludeANY(a, &set);
					} else CompExpected(gn1->INNER, CurrentNt, &set);
					gp1 = gn1->ALT;
				}
				break;
			} /* case */
		} /* switch */
		gp = gn->next;
	}
	Set_Done(&set);
}

static void Func_CompAnySet(int gp)
{
	Set_Clean(&FollowVisited);
	CompANYSet(gp);
}

/* compute all ANY sets */
static void CompAllANYSets(void)
{
	ForEachNTermGraph((Graph_Func) Func_CompAnySet);
}

/* compute SYNC sets in a graph */
static void CompSYNCSet(int gp)
{
	PGraphNode gn;
	Set set;

	Set_Init(&set);
	while (gp > NIL) {
		gn = GetGraphP(gp);
		CR_ASSERT(gn != NULL);
		switch(gn->type) {
		case T_SYNC:
			Set_Clean(&set);
			CompExpected(abs(gn->next), CurrentNt, &set);
			Set_AddItem(&set, EOFSYM);
			IncludeSymSet(ALL_SYNCS, &set);
			gn->SETLINK1 = NewSymSet(&set, T_SYNC);
			break;
		case T_OPT:
		case T_REP:
		case T_ALT:
			CompSYNCSet(gn->INNER);
			if (gn->type == T_ALT) CompSYNCSet(gn->ALT);
			break;
		}
		gp = gn->next;
	}
	Set_Done(&set);
}

/* compute all SYNC sets */
static void CompAllSYNCSets(void)
{
	Set set;

	Set_Init(&set);
	Set_AddItem(&set, EOFSYM);
	IncludeSymSet(ALL_SYNCS, &set);
	ForEachNTermGraph((Graph_Func) CompSYNCSet);
}

/* compute WEAK Terminal sets in a graph */
static void CompWEAKSet(int gp)
{
	PGraphNode gn, gn1;
	Set set;

	Set_Init(&set);
	while (gp > NIL) {
		gn = GetGraphP(gp);
		CR_ASSERT(gn != NULL);
		switch(gn->type) {
		case T_WT:
			Set_Clean(&set);
			CompExpected(abs(gn->next), CurrentNt, &set);  /* Follow WEAK TERMINAL */
			gn->SETLINK1 = NewSymSet(&set, T_WT);
			break;
		case T_REP:
			gn1 = GetGraphP(gn->INNER);
			CR_ASSERT(gn1 != NULL);
			if (gn1->type == T_WT) {
				Set_Clean(&set);
				CompExpected(abs(gn->next), CurrentNt, &set); /* Follow LOOP */
				gn1->SETLINK2 = NewSymSet(&set, T_WT);
			}
			CompWEAKSet(gn->INNER);
			break;
		case T_OPT:
		case T_ALT: