1 files changed, 133 insertions, 0 deletions
diff --git a/docs/recursion_free_parsing.md b/docs/recursion_free_parsing.md
new file mode 100644
index 0000000..170efda
--- /dev/null
+++ b/docs/recursion_free_parsing.md
@@ -0,0 +1,133 @@
+# Parsing ASTs without recursion
+
+token = Leaf | Node token token
+ts = token list
+t = token
+
+l = leaf
+n = node
+
+
+Examples:
+* `[l n l] -> (n (l,l))`
+* `[l n l n l] -> (n (l, n (l, l)))`
+
+
+```
+let parse (ts : token list) =
+  // root of returned expression
+  exp = nil
+
+  // working root node, not necessarily the "top" node
+  root = nil
+
+  // "groups" are just parenthesized expressions,
+  // in this case we track them with a counter.
+  groups = 0
+
+  for t in ts:
+
+      // ts = (l : ts)
+      if t is leaf && root == nil:
+          root = t
+      // ts = (l : l : ts)
+      if t is leaf && root is leaf:
+          error
+
+      // ts = (l : n : l : ts)
+      if t is leaf && root.r == nil:
+          root.r = t
+
+      // unless polish notation ofc,
+      // ts = (n : ts)
+      if t is node && root == nil:
+          error
+
+      if t is node && root != nil:
+          // ts = (l : n : ts)
+          if root is leaf:
+              t.l = root
+              root = t
+              e = root
+
+          // We want left associativity by default;
+          // ts = (l : n : l' : n' : ts) -> (n' (n (l, l')) ts) / ((l n l') n ts)
+          // so
+          //  (2 + 2 + 2 + 2)
+          // turns into
+          //  (((2 + 2) + 2) + 2)
+
+          // in reality, we should check the precedence here,
+          // precedence is ordered by
+          // 1. groups (automagically assigned)
+          // 2. operator precedence
+
+          /// Examples, x, y, and z are variables, r=root, t=t, e=exp
+          // So, when precedence is (root <= t), then t.l=root.r, root.r=t, exp=root, root=t
+          // Eg. ( x + y * . ) => ( + x ( * y . ) )
+          //         r   t          e     r
+
+          // So, when precedence is (root >  t), then t.l=root,             exp=t,    root=t
+          // Eg. ( x * y + . ) => ( + ( x * y ) . )
+          //         r   t          e     r
+
+          //         r   t
+          // so (  x + y + z ) => ( x + ( y + z ) )
+                   - - - - -
+          // grp:  0 0 0 0 0
+
+          //         r    t
+          // so ( (x + y) + z ) ) => ( ( x + y ) + z )
+                  ------- - -
+          // grp:    1    0 0
+
+          //
+
+          // okay, but what about commutativity?
+
+          if root is node:
+              if root.precedence > t.precedence:
+                  t.l = root
+                  exp = root
+                  root = t
+
+              else:
+                  t.l = root.r
+                  root.r = t
+                  exp=t
+                  root=t
+          // counter examples, on eg. exp=root and root=t?
+
+          //    r    t
+          // (x + y) * (z + w)
+            -------- - -------
+                1    0    1
+
+          // (x + y) * [(z + w)] => ( * ( + x y ) . )
+
+          //         r  t
+          // (x + y) * (z + w)
+          // (x + y) * (z [+ w)] => ( * ( + x y ) z )
+
+          //         r    t
+          // (x + y) * (z + w)
+          // (x + y) * (z + [w)] => ( * ( + x y) ( + z . ) )
+
+          //         e    r t
+          // (x + y) * (z + w)
+          // (x + y) * (z + w[)] => ( * ( + x y) z )
+                                    ( * ( + x y) ( + z w ) )
+
+          // something tells me `exp` assignment ain't right.
+
+
+
+
+    // now handle parenthesis, use a counter?
+    if par_start:
+        groups++
+    if par_end and groups > 0:
+        groups--
+    else:
+        error
+```