diff options
Diffstat (limited to 'recursive-ascent.c')
| -rw-r--r-- | recursive-ascent.c | 209 |
1 files changed, 209 insertions, 0 deletions
diff --git a/recursive-ascent.c b/recursive-ascent.c new file mode 100644 index 0000000..8020f7e --- /dev/null +++ b/recursive-ascent.c @@ -0,0 +1,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; +} |