cra.c

COCO類似C的編譯器

/************************************************
**   Mar 24, 2000  Version 1.15
**      Complex DFA Fix
**      F. Arzu 
*************************************************/
#include "collect.h"
#include "set.h"
#include "cra.h"
#include "crt.h"
#include "crf.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

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;
static Set Stepped_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(void)
{
	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(void)
{
	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 GetTransChars(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(void)
{
	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) {
					GetTransChars(a, &seta);
					GetTransChars(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)
{
	int next;
	PGraphNode gn;
	if (gp == 0) return;
	Set_AddItem(&Stepped_Nodes, gp);
	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:
		next = abs(gn->next);
		if (!Set_IsItem(&Stepped_Nodes, next)) Step(from, 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) {
		Set_Clean(&Stepped_Nodes);
		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);