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
|
#include <stdio.h>
#include <stdlib.h>
// TODO: check erros and fail safely and
// see connection with the lexer
// Requirements
#include "parts/symbol.h"
#include "parts/grammar.h"
#include "parts/table.h"
#include "parts/toklist.h"
typedef int stack_item;
#define STACK_CAP 128
static stack_item stack_bottom[STACK_CAP];
static 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
// implement symbol.h
enum symbol {
PLUS = 0,
MINUS,
LPAREN,
RPAREN,
N0, N1,
END_INPUT,
EP, E, T, N,
SYMBOLS_END,
};
size_t total_symbols = SYMBOLS_END;
IMPLEMENT_FUNCPTR(int, symbol_is_valid, (symbol s), { return s < SYMBOLS_END; })
// implement grammar.h
#define PROD(LHS, _, ...) {LHS, (symbol[]){__VA_ARGS__}, sizeof((symbol[]){__VA_ARGS__})/sizeof(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, -->, LPAREN, E, RPAREN),
PROD(T, -->, N),
PROD(N, -->, N0),
PROD(N, -->, N1),
};
struct production *grammar = _grammar;
size_t total_productions = sizeof(_grammar)/sizeof(*_grammar);
// implement table.h
struct action **table = (struct action *([])){
(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;
// implement toklist
static symbol toklist[] = {N0, PLUS, N1, END_INPUT};
static symbol *tok = toklist;
symbol toklist_eat() { return *(tok++); } // unsafe
symbol toklist_peek() { return *tok; } // unsafe
int main(void)
{
return lr_parser();
}
#endif
|
