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
208
209
|
// file: rad_mixed_parser.c
// Recursive Ascent–Descent parser for:
//
// expr : expr '+' term
// | expr '-' term
// | term
//
// term : '(' expr ')'
// | num
//
// num : '0' | '1'
//
// We implement:
// - A miniature LALR(1) ascent machine *just* for expr (+ and –).
// - A recursive‑descent helper for term/num.
// - No hand‑unrolling of left recursion!
#include <stdio.h>
#include <stdlib.h>
#define DIE() do { \
fprintf(stderr, "Parse error at %s:%d\n", __FILE__, __LINE__); \
exit(1); \
} while (0)
enum nonterminal { EXPR, TERM, NUM };
struct result {
enum nonterminal nonterm;
int value;
int depth;
char *s;
};
struct args { int args[2]; };
#define arg(...) (struct args){{__VA_ARGS__}}
// forward declarations of ascent states for expr
struct result state0(char *s, struct args a);
struct result state4(char *s, struct args a);
struct result state5(char *s, struct args a);
struct result state7(char *s, struct args a);
struct result state8(char *s, struct args a);
struct result state9(char *s, struct args a);
struct result state10(char *s, struct args a);
struct result state12(char *s, struct args a);
struct result state13(char *s, struct args a);
// --- Recursive‑descent helper for term/num ------------------------------
// Recognize exactly one `term` ( '(' expr ')' or '0' | '1' ).
// Return the updated pointer and write the semantic value into *out.
static char *
descend_term(char *s, int *out)
{
if (*s == '(') {
s++; // consume '('
// call back into the ascent machine for the full expr
struct result r = state0(s, arg(0));
// drive that machine to its final EXPR reduction
while (r.depth == 0) {
switch (r.nonterm) {
case EXPR: r = state4(r.s, arg(r.value)); break;
default: DIE();
}
}
// now r.nonterm==EXPR, r.depth==2, r.s points just past all of expr
r.depth--; // pop the final accept
if (*r.s != ')') DIE();
*out = r.value;
return r.s + 1;
}
else if (*s == '0' || *s == '1') {
*out = (*s - '0');
return s + 1;
}
else {
DIE();
}
return s; // unreachable
}
// --- Ascent state machine for expr (“+” and “–” only) ------------------
// state0: $accept: . expr $end
// dispatch to shift into the left‑recursive expr machine
struct result state0(char *s, struct args a)
{
struct result r = {0};
// Instead of shifting '(' or '0','1' directly,
// we “descend” for the initial term, then reduce to EXPR:
{
int t;
s = descend_term(s, &t);
r = (struct result){ TERM, t, 0, s };
}
// now fold up into EXPR until we reach a non‑term reduction
while (r.depth == 0) {
switch (r.nonterm) {
case EXPR: r = state4(r.s, arg(r.value)); break;
case TERM: r = state5(r.s, arg(r.value)); break;
default: DIE();
}
}
r.depth--;
return r;
}
// state4: 0 $accept: expr . $end
// 1 expr: expr . '+' term
// 2 expr: expr . '-' term
// on '+' → state9, on '-' → state10, on '\0' → state8
struct result state4(char *s, struct args a)
{
struct result r = {0};
switch(*s) {
case '\0': r = state8(s+1, a); break;
case '+': r = state9(s+1, a); break;
case '-': r = state10(s+1, a); break;
default: DIE();
}
if (r.depth == 0) DIE();
r.depth--;
return r;
}
// state5: 3 expr: term .
// reduce term→expr
struct result state5(char *s, struct args a)
{
return (struct result){ EXPR, a.args[0], 0, s };
}
// state7: after a nested expr in parentheses
// same as state4 but also handles ')'
struct result state7(char *s, struct args a)
{
struct result r = {0};
switch(*s) {
case '+': r = state9(s+1, a); break;
case '-': r = state10(s+1, a); break;
case ')': r = state8(s+1, a); break; // fold up to expr→term inside ()
default: DIE();
}
if (r.depth == 0) DIE();
r.depth--;
return r;
}
// state8: 0 $accept: expr $end .
// accept
struct result state8(char *s, struct args a)
{
return (struct result){ EXPR, a.args[0], 2, s };
}
// state9: 1 expr: expr '+' . term
// shift '+' then descend for *one* term, then reduce via state12
struct result state9(char *s, struct args a)
{
int t;
s = descend_term(s, &t);
return state12(s, arg(a.args[0], t));
}
// state10: 2 expr: expr '-' . term
// same as state9 but for '-'
struct result state10(char *s, struct args a)
{
int t;
s = descend_term(s, &t);
return state13(s, arg(a.args[0], t));
}
// state12: 1 expr: expr '+' term .
// reduce
struct result state12(char *s, struct args a)
{
return (struct result){ EXPR, a.args[0] + a.args[1], 2, s };
}
// state13: 2 expr: expr '-' term .
// reduce
struct result state13(char *s, struct args a)
{
return (struct result){ EXPR, a.args[0] - a.args[1], 2, s };
}
// --- main entry point ---------------------------------------------------
int main(void)
{
const char *input = "1+((0-1)+1)";
struct result r = state0((char*)input, arg(0));
// finish driving the ascent machine if needed
while (r.depth == 0) {
switch (r.nonterm) {
case EXPR: r = state4(r.s, arg(r.value)); break;
default: DIE();
}
}
if (r.nonterm != EXPR || r.depth != 2 || *r.s != '\0') {
DIE();
}
printf("result = %d\n", r.value);
return 0;
}
|
