/************************************************
** Mar 24, 2000 Version 1.15
** Complex DFA Fix
** F. Arzu
** Sep 8, 2002 Version 1.17
** Comment checking fix
** P. Terry
*************************************************/
#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;
else if (gn->type == T_CLASS) {
PClassNode sn = GetClassP(gn->SYMLINK);
int i, c;
CR_ASSERT(sn != NULL);
if (Set_Elements(&sn->data) != 1) SemError(126);
Set_GetRange(&sn->data, &i, &c);
for (; i <= c; i++)
if (Set_IsItem(&sn->data, i)) *s++ = (byte) i;
}
else SemError(122);
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);
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 || state->end_of == 0)) { // Fri 08-30-02
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;
/* Tue 08-27-02 removed following test
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);
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(void)
{
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(void)
{
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();
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(void)
{
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(void)
{
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(void)
{
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(void)
{
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);
GenCode(fscan, "$1if (%C)",&set1);
if (t->tc == T_CONTEXT) { /* Transition With Context */
if (to != sn) GenCode(fscan, " { ctx++; state = %d;} else$$", to);
else GenCode(fscan, " ctx++; else$$");
} else {
if (is_context) { /* Normal Transition in Context State => Reset Context*/
if (to != sn) GenCode(fscan, " {ctx = 0; state = %d;} else$$", to);
else GenCode(fscan, " ctx = 0; else$$");
} else { /* Normal Transition */
if (to != sn) GenCode(fscan, " state = %d; else$$", to);
else GenCode(fscan, " /*same state*/; else$$");
}
}
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 No_Sym;$$", 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(void)
{
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%s\t/* %s */\n", "MAXT", "No_Sym", "Max Terminals");
}
/* initialize scanner generator tables */
void InitScannerTab(void)
{
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(void)
{
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, "No_Sym");
fprintf(lstfile, "\tAccept Token: %s (%d)\n", name, tok);
Set_Done(&set1);
}
void ShowDFA(void)
{
fprintf(lstfile, "\n\n\nDFA:\n");
Collection_ForEachPos(&state_tab, (Collection_FuncPos) ShowState);
}
syntax highlighted by Code2HTML, v. 0.9.1