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
|
#include <stdio.h>
#include <stdlib.h>
typedef unsigned int symbol;
// extern const size_t total_symbols;
// extern int symbol_is_terminal(symbol s);
// extern int symbol_is_input_end(symbol s);
extern int symbol_is_valid(symbol s);
extern struct production {
symbol LHS;
symbol *RHS;
size_t nRHS;
} grammar[];
extern const size_t total_productions;
// extern void grammar_print();
struct action {
enum action_type {
ACTION_NOT_SET = 0, ACTION_SHIFT,
ACTION_GOTO, ACTION_REDUCE,
ACTION_ACCEPT
} type;
size_t arg;
};
extern struct action *table[];
extern size_t table_states;
// extern void table_print();
extern symbol toklist_eat();
extern symbol toklist_peek();
typedef int stack_item;
#define STACK_CAP 128
stack_item stack_bottom[STACK_CAP];
stack_item *stack_head = stack_bottom;
int lr_parser()
{
#define push(item) ({ if(++stack_head - stack_bottom < STACK_CAP ) (*stack_head = item); else { fprintf(stderr, "ERROR: STACK_CAP exceeded"); return 1; }})
#define pop() (--stack_head)
#define eat() toklist_eat()
#define peek() ({ symbol s = toklist_peek(); if(!symbol_is_valid(s)) return 1; s; })
while(1) {
struct action a = table[(size_t)*stack_head][peek()];
switch(a.type) {
case ACTION_SHIFT:
push(eat());
push(a.arg);
break;
case ACTION_REDUCE:
for(size_t i = 0; i < 2*grammar[a.arg].nRHS; i++) pop();
symbol lhs = grammar[a.arg].LHS;
struct action a_goto = table[(size_t)*stack_head][lhs];
if(a_goto.type != ACTION_GOTO) {
fprintf(stderr,
"ERROR: Expected goto action for symbol %d at state %zu",
lhs, (size_t)*stack_head);
return 1;
}
push(lhs);
push(a_goto.arg);
break;
case ACTION_ACCEPT:
return 0;
case ACTION_NOT_SET:
default:
fprintf(stderr,
"ERROR: Unexpected error symbol %d at state %zu",
peek(), (size_t)*stack_head);
return 1;
}
}
return 1;
}
#ifdef _LR_PARSER_STANDALONE
enum symbol {
PLUS = 0,
MINUS,
LPAREN,
RPAREN,
N0, N1,
END_INPUT,
EP, E, T, N,
SYMBOLS_END,
};
const size_t total_symbols = SYMBOLS_END;
int symbol_is_valid(symbol s) { return s < SYMBOLS_END; }
#define PROD(LHS, _, ...) {LHS, (symbol[]){__VA_ARGS__}, sizeof((symbol[]){__VA_ARGS__})/sizeof(symbol)}
struct production grammar[] = {
PROD(EP, ->, E, END_INPUT),
PROD(E, -->, E, PLUS, T),
PROD(E, -->, E, MINUS, T),
PROD(E, -->, T),
PROD(T, -->, LPAREN, E, RPAREN),
PROD(T, -->, N),
PROD(N, -->, N0),
PROD(N, -->, N1),
};
const size_t total_productions = sizeof(grammar)/sizeof(*grammar);
struct action *table[] = {
(struct action[]){{0, 0},{0, 0},{1, 1},{0, 0},{1, 2},{1, 3},{0, 0},{0, 0},{2, 12},{2, 11},{2, 7},},
(struct action[]){{0, 0},{0, 0},{1, 1},{0, 0},{1, 2},{1, 3},{0, 0},{0, 0},{2, 4},{2, 11},{2, 7},},
(struct action[]){{3, 6},{3, 6},{0, 0},{3, 6},{0, 0},{0, 0},{3, 6},{0, 0},{0, 0},{0, 0},{0, 0},},
(struct action[]){{3, 7},{3, 7},{0, 0},{3, 7},{0, 0},{0, 0},{3, 7},{0, 0},{0, 0},{0, 0},{0, 0},},
(struct action[]){{1, 5},{1, 8},{0, 0},{1, 10},{0, 0},{0, 0},{0, 0},{0, 0},{0, 0},{0, 0},{0, 0},},
(struct action[]){{0, 0},{0, 0},{1, 1},{0, 0},{1, 2},{1, 3},{0, 0},{0, 0},{0, 0},{2, 6},{2, 7},},
(struct action[]){{3, 1},{3, 1},{0, 0},{3, 1},{0, 0},{0, 0},{3, 1},{0, 0},{0, 0},{0, 0},{0, 0},},
(struct action[]){{3, 5},{3, 5},{0, 0},{3, 5},{0, 0},{0, 0},{3, 5},{0, 0},{0, 0},{0, 0},{0, 0},},
(struct action[]){{0, 0},{0, 0},{1, 1},{0, 0},{1, 2},{1, 3},{0, 0},{0, 0},{0, 0},{2, 9},{2, 7},},
(struct action[]){{3, 2},{3, 2},{0, 0},{3, 2},{0, 0},{0, 0},{3, 2},{0, 0},{0, 0},{0, 0},{0, 0},},
(struct action[]){{3, 4},{3, 4},{0, 0},{3, 4},{0, 0},{0, 0},{3, 4},{0, 0},{0, 0},{0, 0},{0, 0},},
(struct action[]){{3, 3},{3, 3},{0, 0},{3, 3},{0, 0},{0, 0},{3, 3},{0, 0},{0, 0},{0, 0},{0, 0},},
(struct action[]){{1, 5},{1, 8},{0, 0},{0, 0},{0, 0},{0, 0},{4, 0},{0, 0},{0, 0},{0, 0},{0, 0},},
};
size_t table_states = 13;
symbol toklist[] = {N0, PLUS, N1, END_INPUT};
symbol *tok = toklist;
symbol toklist_eat() { return *(tok++); }
symbol toklist_peek() { return *tok; }
int main(void)
{
return lr_parser();
}
#endif
|
