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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
#include <stdio.h>
#include <stdlib.h>
#define ARR_LEN(a) (sizeof(a) / sizeof(*a))
enum symbol {
PLUS = 0,
MINUS,
LPAREN,
RPAREN,
N0, N1,
END_INPUT,
EP, E, T, N,
SYMBOL_COUNT,
};
static inline int is_terminal(enum symbol s) { return s < E; }
static inline int is_nonterminal(enum symbol s) { return s >= E; }
struct production {
enum symbol LHS;
enum symbol *RHS;
size_t nRHS;
};
#define PROD(LHS, _, ...) {LHS, (enum symbol[]){__VA_ARGS__}, sizeof((enum symbol[]){__VA_ARGS__})/sizeof(enum symbol)}
static struct production grammar[] = {
PROD(EP, ->, E, END_INPUT),
PROD(E, -->, E, PLUS, T),
PROD(E, -->, E, MINUS, T),
PROD(E, -->, T),
PROD(T, -->, T, LPAREN, E, RPAREN),
PROD(T, -->, N),
PROD(N, -->, N0),
PROD(N, -->, N1),
};
static int follow[SYMBOL_COUNT][SYMBOL_COUNT];
void fill_follow_table();
void print_grammar()
{
for(size_t i = 0; i < ARR_LEN(grammar); i++)
{
printf("%d --> ", grammar[i].LHS);
for(size_t j = 0; j < grammar[i].nRHS; j++)
printf("%d ", grammar[i].RHS[j]);
printf("\n");
}
}
struct action {
enum action_type {
ACTION_NOT_SET = 0, ACTION_SHIFT,
ACTION_GOTO, ACTION_REDUCE,
ACTION_ACCEPT
} type;
size_t arg;
};
static struct action *(table[SYMBOL_COUNT]);
static size_t states;
struct item {
size_t prod_idx;
size_t dot;
};
int items_eq(struct item *i1, struct item *i2)
{
if(i1->dot == i2->dot && i1->prod_idx == i2->prod_idx) return 1;
}
// TODO: check bounds
static struct {
struct item *items;
size_t nitems;
size_t state;
} seen_sets[100];
static size_t nseen_sets;
size_t handle_set(struct item *set, size_t nset);
int fill_table(size_t state, struct item *initial_set, size_t ninitial);
void closure(struct item *in_set, size_t nin, struct item *out_set, size_t *nout);
#define DIE(...) (printf("ERROR %s:%d\n", __FILE__, __LINE__), __VA_OPT__(exit(__VA_ARGS__),) exit(1), 1)
int main(void)
{
struct item i[] = {{1, 2}};
struct item o[16];
size_t no = ARR_LEN(o);
closure(i, ARR_LEN(i), o, &no);
(no > ARR_LEN(o)) && DIE();
for(int i = 0; i < no; i++) {
printf("%d %d\n", o[i].prod_idx, o[i].dot);
}
}
size_t handle_set(struct item *set, size_t nset)
{
// is set in seen_sets
for(size_t i = 0; i < nseen_sets; i++) {
if(seen_sets[i].nitems != nset) continue;
int _seen = 0;
for(size_t j = 0; j < nset; j++) {
_seen = 0;
for(size_t k = 0; k < nset; k++)
if(items_eq(&seen_sets[i].items[j], &set[k])) _seen = 1;
if(!_seen) break;
}
if(_seen) return seen_sets[i].state;
}
// add set to seen_sets
// TODO: check calloc
seen_sets[nseen_sets].items = calloc(nset, sizeof(*set));
seen_sets[nseen_sets].nitems = nset;
for(size_t i = 0; i < nset; i++)
seen_sets[nseen_sets].items[i] = set[i];
size_t new_state = seen_sets[nseen_sets++].state = states++;
fill_table(new_state, set, nset) && DIE();
return new_state;
}
int fill_table(size_t state, struct item *initial_set, size_t ninitial)
{
struct item closure_set[100];
size_t nclosure = 100;
closure(initial_set, ninitial, closure_set, &nclosure);
if(nclosure > 100) return 1;
for(size_t sym = 0; sym < SYMBOL_COUNT; sym++) {
// TOOD: check goto bounds
struct item goto_set[100];
size_t ngoto = 0;
for(size_t j = 0; j < nclosure; j++) {
struct production *p = &grammar[closure_set[j].prod_idx];
size_t dot = closure_set[j].dot;
if(dot == p->nRHS) {
// if(follow[p->LHS][sym]) {
// //add reduction
// }
continue;
}
if(p->RHS[dot] == sym) {
goto_set[ngoto] = closure_set[j];
goto_set[ngoto++].dot++;
}
}
size_t new_state = handle_set(goto_set, ngoto);
// TODO: check table bounds
// TODO: check if table state is already set
table[state][sym] = (struct action){
is_terminal(sym) ? ACTION_SHIFT : ACTION_GOTO,
new_state};
}
}
void closure(struct item *in_set, size_t nin, struct item *out_set, size_t *nout)
{
size_t nout_max = *nout;
*nout = nin;
if(*nout > nout_max) return;
for(size_t i = 0; i < nin; i++) out_set[i] = in_set[i];
int *is_in_closure = calloc(ARR_LEN(grammar), sizeof(int));
for(size_t i = 0; i < *nout; i++)
{
struct production *p = &grammar[out_set[i].prod_idx];
if(out_set[i].dot == p->nRHS) continue;
enum symbol sym = p->RHS[out_set[i].dot];
for(size_t j = 0; j < ARR_LEN(grammar); j++)
if(grammar[j].LHS == sym) {
if(is_in_closure[j]) continue;
is_in_closure[j] = 1;
if(*nout >= nout_max) goto cleanup;
out_set[(*nout)++] = (struct item){j, 0};
}
}
cleanup:
free(is_in_closure);
}
void fill_follow_table()
{
1 && DIE();
}
|
