// 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;
}