From 245f4b65cc695bf3d0dd430e2c728f2a3a51e3e5 Mon Sep 17 00:00:00 2001
From: kartofen <mladenovnasko0@gmail.com>
Date: Tue, 17 Jun 2025 15:15:21 +0300
Subject: add recursive ascent-descent

---
 recursive-ascent-descent.c | 197 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 197 insertions(+)
 create mode 100644 recursive-ascent-descent.c

(limited to 'recursive-ascent-descent.c')

diff --git a/recursive-ascent-descent.c b/recursive-ascent-descent.c
new file mode 100644
index 0000000..628540d
--- /dev/null
+++ b/recursive-ascent-descent.c
@@ -0,0 +1,197 @@
+#include <stdio.h>  // printf(char *, ...)
+#include <stdlib.h> // exit(int)
+
+/*
+ * For grammar: (https://en.wikipedia.org/wiki/Recursive_ascent_parser)
+ * (R1)  expr : expr _ '+' term   { $$ = $1 + $3; }
+ * (R2)       | expr _ '-' term   { $$ = $1 - $3; }
+ * (R3)       | _ term            { $$ = $1; }
+ *            ;
+ *
+ * (R4)  term : _ '(' expr ')'    { $$ = $2; }
+ * (R5)       | _ num             { $$ = $1; }
+ *            ;
+ *
+ * (R6)  num : _ '0'              { $$ = 0; }
+ * (R7)      | _ '1'              { $$ = 1; }
+ *           ;
+ */
+
+#pragma GCC diagnostic ignored "-Wunused-value"
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+
+#define DIE(...) (printf("ERROR %s:%d\n", __FILE__, __LINE__), __VA_OPT__(exit(__VA_ARGS__),) exit(1), 1)
+
+enum nonterminal { INVAILID, EXPR, TERM, NUM };
+struct result { enum nonterminal nonterm; int value; int depth; char *s; };
+
+struct args   { int args[2]; };
+#define new_arg(...) (struct args){{__VA_ARGS__}}
+#define get_arg(a, n) ((a).args[n])
+
+// top-down
+struct result rule0(char *s, struct args a);
+struct result rule1(char *s, struct args a);
+struct result rule2(char *s, struct args a);
+struct result rule3(char *s, struct args a);
+struct result rule4(char *s, struct args a);
+struct result rule5(char *s, struct args a);
+struct result rule6(char *s, struct args a);
+struct result rule7(char *s, struct args a);
+
+// bottom-up
+struct result accept(char *s, struct args a);
+struct result expr(char *s, struct args a);
+struct result expr2(char *s, struct args a);
+struct result term(char *s, struct args a);
+struct result num(char *s, struct args a);
+
+int main(void)
+{
+    char *s = "1-((0-1)+1+1+1+1+1)-0+1-(((1)))+1+1+1-1+0+(1-0+1)-1-0";
+    struct result r = accept(s, new_arg(0));
+    printf("%s = %d\n", s, r.value);
+    return 0;
+}
+
+char *eat(char *s, char c)
+{
+    if(*s == c)
+        return s + 1;
+    else DIE();
+}
+
+struct result rule0(char *s, struct args a)
+{
+    struct result r = {0, 0, 0, s};
+    r = expr(r.s, a);
+    r.s = eat(r.s, '\0');
+    return r;
+}
+
+struct result rule1(char *s, struct args a)
+{
+    struct result r = {0, 0, 0, s};
+    r.s = eat(r.s, '+');
+    r = term(r.s, a);
+    return (struct result){EXPR, get_arg(a, 0) + r.value, 0, r.s};
+}
+
+struct result rule2(char *s, struct args a)
+{
+    struct result r = {0, 0, 0, s};
+    r.s = eat(r.s, '-');
+    r = term(r.s, a);
+    return (struct result){EXPR, get_arg(a, 0) - r.value, 0, r.s};
+}
+
+struct result rule3(char *s, struct args a)
+{
+    struct result r = {0, 0, 0, s};
+    r = term(r.s, a);
+    return (struct result){EXPR, r.value, 0, r.s};
+}
+
+struct result rule4(char *s, struct args a)
+{
+    struct result r = {0, 0, 0, s};
+    r.s = eat(r.s, '(');
+    r = expr(r.s, a);
+    r.s = eat(r.s, ')');
+    return (struct result){EXPR, r.value, 1, r.s};
+}
+
+struct result rule5(char *s, struct args a)
+{
+    struct result r = {0, 0, 0, s};
+    r = num(r.s, a);
+    return (struct result){TERM, r.value, 0, r.s};
+}
+
+struct result rule6(char *s, struct args a)
+{
+    struct result r = {0, 0, 0, s};
+    r.s = eat(r.s, '0');
+    return (struct result){NUM, 0, 0, r.s};
+}
+
+struct result rule7(char *s, struct args a)
+{
+    struct result r = {0, 0, 0, s};
+    r.s = eat(r.s, '1');
+    return (struct result){NUM, 1, 0, r.s};
+}
+
+struct result accept(char *s, struct args a)
+{
+    struct result r = {0};
+    switch(*s) {
+    case '(':
+    case '0':
+    case '1': r = rule0(s, a); break;
+    default: DIE();
+    }
+
+    return r;
+}
+
+struct result expr(char *s, struct args a)
+{
+    struct result r = {0};
+    switch(*s) {
+    case '(':
+    case '0':
+    case '1': r = rule3(s, a); break;
+    default: DIE();
+    }
+
+    struct result r2 = r;
+    while(r2.depth == 0) {
+        r = r2;
+        switch(r.nonterm) {
+        case EXPR: r2 = expr2(r.s, new_arg(r.value)); break;
+        default: DIE();
+        }
+    }
+
+    r.depth--;
+    return r;   
+}
+
+struct result expr2(char *s, struct args a)
+{
+    struct result r = {0};
+    switch(*s) {
+    case '+': r = rule1(s, a); break;
+    case '-': r = rule2(s, a); break;
+    default: r.depth = 1;
+    }
+
+    return r;
+}
+    
+struct result term(char *s, struct args a)
+{
+    struct result r = {0};
+    switch(*s) {
+    case '(': r = rule4(s, a); break;
+    case '0': r = rule5(s, a); break;
+    case '1': r = rule5(s, a); break;
+    default: DIE();
+    }
+
+    return r;
+}
+
+struct result num(char *s, struct args a)
+{
+    struct result r = {0};
+    switch(*s) {
+    case '0': r = rule6(s, a); break;
+    case '1': r = rule7(s, a); break;
+    default: DIE();
+    }
+
+    return r;
+}
+
-- 
cgit v1.2.3