-
Notifications
You must be signed in to change notification settings - Fork 0
/
states.c
107 lines (92 loc) · 2.68 KB
/
states.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include "states.h"
Edge edge(symbol X, State from, State to) {
Edge e = (Edge)malloc(sizeof(struct _Edge));
e->X = X;
e->from = from;
e->to = to;
return e;
}
void edgehash(Edge e, key hash) {
statehash(e->from, hash);
char *buff = malloc(sizeof(char)*50);
statehash(e->to, buff);
strcat(hash, buff);
sprintf(buff, "%d", e->X);
strcat(hash, buff);
free(buff);
}
void printedge(Edge e) {
key hash = malloc(sizeof(char)*50);
statehash(e->from, hash);
printf("%s -> ", hash);
statehash(e->to, hash);
printf("%s, ", hash);
char **symbols = getsymbols();
printf("%s\n", symbols[e->X-S_NT_PROGRAM]);
}
void stateinit(StateSet T) {
LR0_Item *allitems = LR0_getallitems();
State init = stb_symtable();
stb_put(init, stb_node(allitems[0], LR0_itemhash));
LR0_closure(init);
stb_put(T, stb_node(init, &statehash));
}
bool stateeq(State I1, State I2) {
if (stb_len(I1) != stb_len(I2)) return false;
StateNode n = I1->head;
while (n != NULL)
{
if (!stb_haskey(I2, n->k)) return false;
n = n->next;
}
return true;
}
void states(StateSet T, EdgeSet E) {
stateinit(T);
StateNode SN = T->head;
symbol X;
StateSet tmp = stb_symtable(); // set used to host state J, { J }
while (SN != NULL) // loop on states
{
ItemNode in = ((State)(SN->i))->head;
while (in != NULL) // loop on state items
{
if (((LR0_Item)in->i)->before == -1) {in = in->next; continue;}
State J = stb_symtable();
X = ((LR0_Item)in->i)->p->rhs[((LR0_Item)in->i)->before];
LR0_goto((State)(SN->i), X, J);
if (stb_len(J) == 0) {in = in->next; continue;}
stb_put(tmp, stb_node(J, &statehash));
if (SN == T->head) stb_unsert(T, tmp, &statehash, &stateeq); // only for first iteration
else stb_union(T, tmp, &statehash, SN, &stateeq); // union to insert states after SN
stb_clear(tmp);
Edge e = edge(X, (State)(SN->i), J);
stb_put(E, stb_node(e, &edgehash));
in = in->next;
}
SN = SN->next;
}
free(tmp);
}
void statehash(State I, key hash) {
int i[stb_len(I)];
int c = 0;
Node n = I->head;
while (n != NULL)
{
i[c++] = LR0_getindex((LR0_Item)n->i);
n = n->next;
}
sorti(i, stb_len(I));
char *buff = (char*)malloc(sizeof(char)*3);
sprintf(hash, "%d", i[0]);
for (int j = 1; j < stb_len(I); j++)
{
sprintf(buff, "%d", i[j]);
strcat(hash, buff);
}
free(buff);
}
void printstate(State I) {
stb_print(I, &printit);
}