aboutsummaryrefslogtreecommitdiff
path: root/recursive
diff options
context:
space:
mode:
Diffstat (limited to 'recursive')
-rw-r--r--recursive/recursive-ascent-descent.c197
-rw-r--r--recursive/recursive-ascent.c316
2 files changed, 513 insertions, 0 deletions
diff --git a/recursive/recursive-ascent-descent.c b/recursive/recursive-ascent-descent.c
new file mode 100644
index 0000000..628540d
--- /dev/null
+++ b/recursive/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;
+}
+
diff --git a/recursive/recursive-ascent.c b/recursive/recursive-ascent.c
new file mode 100644
index 0000000..7f69e57
--- /dev/null
+++ b/recursive/recursive-ascent.c
@@ -0,0 +1,316 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+/*
+ * For grammar: (https://en.wikipedia.org/wiki/Recursive_ascent_parser)
+ * expr : expr '+' term { $$ = $1 + $3; }
+ * | expr '-' term { $$ = $1 - $3; }
+ * | term { $$ = $1; }
+ * ;
+ *
+ * term : '(' expr ')' { $$ = $2; }
+ * | num { $$ = $1; }
+ * ;
+ *
+ * num : '0' { $$ = 0; }
+ * | '1' { $$ = 1; }
+ * ;
+ */
+
+#pragma GCC diagnostic ignored "-Wunused-value"
+
+#define DIE(...) (printf("ERROR %s:%d\n", __FILE__, __LINE__), __VA_OPT__(exit(__VA_ARGS__),) exit(1), 1)
+
+enum nonterminal { 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])
+
+struct result state0(char *s, struct args a);
+struct result state1(char *s, struct args a);
+struct result state2(char *s, struct args a);
+struct result state3(char *s, struct args a);
+struct result state4(char *s, struct args a);
+struct result state5(char *s, struct args a);
+struct result state6(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 state11(char *s, struct args a);
+struct result state12(char *s, struct args a);
+struct result state13(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 = state0(s, new_arg(0));
+ printf("%s = %d\n", s, r.value);
+ return 0;
+}
+
+/*
+ * 0 $accept: . expr $end
+ *
+ * '(' shift, and go to state 1
+ * '0' shift, and go to state 2
+ * '1' shift, and go to state 3
+ *
+ * expr go to state 4
+ * term go to state 5
+ * num go to state 6
+ */
+struct result state0(char *s, struct args a)
+{
+ struct result r = {0};
+ switch(*s) {
+ case '(': r = state1(s+1, a); break;
+ case '0': r = state2(s+1, a); break;
+ case '1': r = state3(s+1, a); break;
+ default: DIE();
+ }
+
+ while(r.depth == 0) {
+ switch(r.nonterm) {
+ case EXPR: r = state4(r.s, new_arg(r.value)); break;
+ case TERM: r = state5(r.s, new_arg(r.value)); break;
+ case NUM: r = state6(r.s, new_arg(r.value)); break;
+ default: DIE();
+ }
+ }
+
+ r.depth--;
+ return r;
+}
+
+/*
+ * 4 term: '(' . expr ')'
+ *
+ * '(' shift, and go to state 1
+ * '0' shift, and go to state 2
+ * '1' shift, and go to state 3
+ *
+ * expr go to state 7
+ * term go to state 5
+ * num go to state 6
+ */
+struct result state1(char *s, struct args a)
+{
+ struct result r = {0};
+ switch(*s) {
+ case '(': r = state1(s+1, a); break;
+ case '0': r = state2(s+1, a); break;
+ case '1': r = state3(s+1, a); break;
+ default: DIE();
+ }
+
+ while(r.depth == 0) {
+ switch(r.nonterm) {
+ case EXPR: r = state7(r.s, new_arg(r.value)); break;
+ case TERM: r = state5(r.s, new_arg(r.value)); break;
+ case NUM: r = state6(r.s, new_arg(r.value)); break;
+ default: DIE();
+ }
+ }
+
+ r.depth--;
+ return r;
+}
+
+/*
+ * 6 num: '0' .
+ *
+ * $default reduce using rule 6 (num)
+ */
+struct result state2(char *s, struct args a)
+{
+ (void)a;
+ return (struct result){NUM, 0, 0, s};
+}
+
+/*
+ * 7 num: '1' .
+ *
+ * $default reduce using rule 7 (num)
+ */
+struct result state3(char *s, struct args a)
+{
+ (void)a;
+ return (struct result){NUM, 1, 0, s};
+}
+
+/*
+ * 0 $accept: expr . $end
+ * 1 expr: expr . '+' term
+ * 2 | expr . '-' term
+ *
+ * $end shift, and go to state 8
+ * '+' shift, and go to state 9
+ * '-' shift, and go to state 10
+ */
+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();
+ }
+
+ (r.depth == 0) && DIE();
+
+ r.depth--;
+ return r;
+}
+
+/*
+ * 3 expr: term .
+ *
+ * $default reduce using rule 3 (expr)
+ */
+struct result state5(char *s, struct args a)
+{
+ return (struct result){EXPR, get_arg(a, 0), 0, s};
+}
+
+/*
+ * 5 term: num .
+ *
+ * $default reduce using rule 5 (term)
+ */
+struct result state6(char *s, struct args a)
+{
+ return (struct result){TERM, get_arg(a, 0), 0, s};
+}
+
+/*
+ * 1 expr: expr . '+' term
+ * 2 | expr . '-' term
+ * 4 term: '(' expr . ')'
+ *
+ * '+' shift, and go to state 9
+ * '-' shift, and go to state 10
+ * ')' shift, and go to state 11
+ */
+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 = state11(s+1, a); break;
+ default: DIE();
+ }
+
+ (r.depth == 0) && DIE();
+
+ r.depth--;
+ return r;
+}
+
+/*
+ * 0 $accept: expr $end .
+ *
+ * $default accept
+ */
+struct result state8(char *s, struct args a)
+{
+ return (struct result){EXPR, a.args[0], 2, s};
+}
+
+/*
+ * 1 expr: expr '+' . term
+ *
+ * '(' shift, and go to state 1
+ * '0' shift, and go to state 2
+ * '1' shift, and go to state 3
+ *
+ * term go to state 12
+ * num go to state 6
+ */
+struct result state9(char *s, struct args a)
+{
+ struct result r = {0};
+ switch(*s) {
+ case '(': r = state1(s+1, a); break;
+ case '0': r = state2(s+1, a); break;
+ case '1': r = state3(s+1, a); break;
+ default: DIE();
+ }
+
+ while(r.depth == 0) {
+ switch(r.nonterm) {
+ case TERM: r = state12(r.s, new_arg(r.value, get_arg(a, 0))); break;
+ case NUM: r = state6(r.s, new_arg(r.value)); break;
+ default: DIE();
+ }
+ }
+
+ r.depth--;
+ return r;
+}
+
+/*
+ * 2 expr: expr '-' . term
+ *
+ * '(' shift, and go to state 1
+ * '0' shift, and go to state 2
+ * '1' shift, and go to state 3
+ *
+ * term go to state 13
+ * num go to state 6
+ */
+struct result state10(char *s, struct args a)
+{
+ struct result r = {0};
+ switch(*s) {
+ case '(': r = state1(s+1, a); break;
+ case '0': r = state2(s+1, a); break;
+ case '1': r = state3(s+1, a); break;
+ default: DIE();
+ }
+
+ while(r.depth == 0) {
+ switch(r.nonterm) {
+ case TERM: r = state13(r.s, new_arg(get_arg(a, 0), r.value)); break;
+ case NUM: r = state6(r.s, new_arg(r.value)); break;
+ default: DIE();
+ }
+ }
+
+ r.depth--;
+ return r;
+}
+
+/*
+ * 4 term: '(' expr ')' .
+ *
+ * $default reduce using rule 4 (term)
+ */
+struct result state11(char *s, struct args a)
+{
+ return (struct result){TERM, get_arg(a, 0), 2, s};
+}
+
+/*
+ * 1 expr: expr '+' term .
+ *
+ * $default reduce using rule 1 (expr)
+ */
+struct result state12(char *s, struct args a)
+{
+ return (struct result){EXPR, get_arg(a, 0) + get_arg(a, 1), 2, s};
+}
+
+/*
+ * 2 expr: expr '-' term .
+ *
+ * $default reduce using rule 2 (expr)
+ */
+struct result state13(char *s, struct args a)
+{
+ return (struct result){EXPR, get_arg(a, 0) - get_arg(a, 1), 2, s};
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-18 13:02:41 +0000