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
|
#ifndef TABLE_H
#define TABLE_H
#include <stddef.h> // size_t
#include "util/util.h"
#define ACTION_TYPE(X) \
X(ACTION_NOT_SET) \
X(ACTION_SHIFT) \
X(ACTION_GOTO) \
X(ACTION_REDUCE) \
X(ACTION_ACCEPT) \
X(ACTION_ERROR)
const char * const action_type_to_char[] = {
ACTION_TYPE(X_TO_STR)
};
extern struct action {
enum action_type { ACTION_TYPE(X_TO_ENUM) } type;
size_t arg;
} **table;
extern size_t table_states;
extern int (*table_fill)(); // non-zero on fail
extern void (*table_free)();
void table_print();
void table_print_cstyle();
int table_insert(size_t state, symbol sym, struct action a); // should it be here??
#include "symbol.h"
void table_print()
{
printf(" ");
for(size_t sym = 0; sym < total_symbols; sym++) printf("%2zu ", sym);
printf("\n");
char action_to_char[] = {[ACTION_SHIFT] = 's', [ACTION_REDUCE] = 'r', [ACTION_GOTO] = 'g', [ACTION_ERROR] = 'e'};
for(size_t i = 0; i < table_states; i++) {
printf("%2zu ", i);
for(size_t sym = 0; sym < total_symbols; sym++)
if(table[i][sym].type == ACTION_ACCEPT) printf(" a ");
else if(table[i][sym].type) printf("%c%-2zu ", action_to_char[table[i][sym].type], table[i][sym].arg);
else printf(" ");
printf("\n");
}
}
void table_print_cstyle()
{
for(size_t i = 0; i < table_states; i++) {
printf("(struct action[]){");
for(size_t sym = 0; sym < total_symbols; sym++)
printf("{%d, %zu},", table[i][sym].type, table[i][sym].arg);
printf("},\n");
}
}
#include "grammar.h"
#include "precedence.h"
int table_insert(size_t state, symbol sym, struct action a)
{
struct action *tbl_a = &table[state][sym];
struct action *new_a = &a;
if(tbl_a->type == new_a->type && tbl_a->arg == new_a->arg) return 0;
if(tbl_a->type == ACTION_NOT_SET) {
*tbl_a = *new_a;
return 0;
}
int r = 0, report = 0, set_tbl_a = 0,
reduce_reduce = 0, shift_reduce = 0,
tbl_is_reduce, shift_p, reduce_p;
if((tbl_a->type == ACTION_REDUCE && new_a->type == ACTION_REDUCE)) reduce_reduce = 1;
else if((tbl_a->type == ACTION_REDUCE && new_a->type == ACTION_SHIFT)) { shift_reduce = 1;
tbl_is_reduce = 1;
} else if((tbl_a->type == ACTION_SHIFT && new_a->type == ACTION_REDUCE)) { shift_reduce = 1;
tbl_is_reduce = 0;
}
if(shift_reduce) {
report = 1;
shift_p = precedence_symbol[sym];
reduce_p = (tbl_is_reduce)
? precedence_production[tbl_a->arg]
: precedence_production[new_a->arg];
}
#define prec_num(a) PRECEDENCE_NUM(precedence_production[(a)->arg])
#define prec_flag(a) PRECEDENCE_FLAG(precedence_production[(a)->arg])
if(reduce_reduce) {
if(prec_num(tbl_a) == 0 || prec_num(new_a) == 0) report = 1;
if(prec_num(tbl_a) > prec_num(new_a)) set_tbl_a = 0;
else if(prec_num(tbl_a) < prec_num(new_a)) set_tbl_a = 1;
else { report = 1;
if(new_a->arg > tbl_a->arg) set_tbl_a = 1;
}
} else if(shift_reduce) {
int favor_shift = 0;
if(shift_p == 0 || reduce_p == 0) { favor_shift = 1; report = 1; }
else if(PRECEDENCE_NUM(shift_p) > PRECEDENCE_NUM(reduce_p)) favor_shift = 1;
else if(PRECEDENCE_NUM(reduce_p) > PRECEDENCE_NUM(shift_p)) favor_shift = 0;
else if(PRECEDENCE_FLAG(shift_p) == PRECEDENCE_LEFT_ASSOC) favor_shift = 1;
else if(PRECEDENCE_FLAG(shift_p) == PRECEDENCE_RIGHT_ASSOC) favor_shift = 0;
else { favor_shift = 1, report = 1; }
if((favor_shift && tbl_is_reduce) || (!favor_shift && !tbl_is_reduce)) set_tbl_a = 1;
} else {
r = 1; report = 1;
}
if(report) {
struct action *a0 = (set_tbl_a) ? new_a: tbl_a;
struct action *a1 = (set_tbl_a) ? tbl_a: new_a;
fprintf(stderr, "REPORT: table collission on state '%zu' sym '%d'\n", state, sym);
fprintf(stderr, "\t%s resolve: {%s %zu} %s {%s %zu}\n",
(r == 0) ? "SUCCESSFULLY" : "COULD NOT",
action_type_to_char[a0->type], a0->arg,
(r == 0) ? "over" : "vs",
action_type_to_char[a1->type], a1->arg);
}
if(!r && set_tbl_a) *tbl_a = *new_a;
return r;
}
#endif
|
