From 381bf1c8481276c5ee6318e6694bb2ee151a54b7 Mon Sep 17 00:00:00 2001
From: onelin <oscar@nelin.dk>
Date: Tue, 22 Sep 2026 23:22:38 +0200
Subject: Update documentation on how parsing is done without recursion

---
 docs/recursion_free_parsing.md | 67 ++++++++++++++++++++++--------------------
 1 file changed, 35 insertions(+), 32 deletions(-)

diff --git a/docs/recursion_free_parsing.md b/docs/recursion_free_parsing.md
index 170efda..a34fe09 100644
--- a/docs/recursion_free_parsing.md
+++ b/docs/recursion_free_parsing.md
@@ -1,17 +1,6 @@
 # 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)))`
-
+There's missing a error check for two consequtive non-nullary expressions.
 
 ```
 let parse (ts : token list) =
@@ -30,25 +19,28 @@ let parse (ts : token list) =
       // ts = (l : ts)
       if t is leaf && root == nil:
           root = t
+          top = t
+
       // ts = (l : l : ts)
-      if t is leaf && root is leaf:
+      elif t is leaf && root is leaf:
           error
 
       // ts = (l : n : l : ts)
-      if t is leaf && root.r == nil:
+      elif t is leaf && root.r == nil:
           root.r = t
+          top = root
 
       // unless polish notation ofc,
       // ts = (n : ts)
-      if t is node && root == nil:
+      elif t is node && root == nil:
           error
 
-      if t is node && root != nil:
+      elif t is node && root != nil:
           // ts = (l : n : ts)
           if root is leaf:
               t.l = root
               root = t
-              e = root
+              top = root
 
           // We want left associativity by default;
           // ts = (l : n : l' : n' : ts) -> (n' (n (l, l')) ts) / ((l n l') n ts)
@@ -56,20 +48,30 @@ let parse (ts : token list) =
           //  (2 + 2 + 2 + 2)
           // turns into
           //  (((2 + 2) + 2) + 2)
+          //
+          // case(s) we will never get into with these rules:
+          //  root is node && root.l == nil and root.r == nil
+          //  root is node && root.l == nil and root.r != nil
 
           // 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
+          /// Examples, x, y, and z are variables, r=root, t=t, e=top. If `e` is
+          /// omitted in rhs of `=>`, then `r` is also `e`/top
+
+          // when precedence is (root < t), then t.l=root.r, root.r=t, top=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
+          // when precedence is (root > t), then t.l=root,             top=t,    root=t
           // Eg. ( x * y + . ) => ( + ( x * y ) . )
-          //         r   t          e     r
+          //         r   t          r
+
+          // when precedence is (root = t), then t.l=root,             top=t,    root=t
+          // Eg. ( x + y + . ) => ( + ( x + y ) . )
+          //         r   t          r
 
           //         r   t
           // so (  x + y + z ) => ( x + ( y + z ) )
@@ -86,16 +88,17 @@ let parse (ts : token list) =
           // okay, but what about commutativity?
 
           if root is node:
-              if root.precedence > t.precedence:
-                  t.l = root
-                  exp = root
-                  root = t
+              if root.precedence < t.precedence:
+                  t.l    = root.r
+                  top    = root
+                  root.r = t
+                  root   = t
 
               else:
-                  t.l = root.r
-                  root.r = t
-                  exp=t
-                  root=t
+                  t.l  = root
+                  root = t
+                  top  = root
+
           // counter examples, on eg. exp=root and root=t?
 
           //    r    t
@@ -118,15 +121,15 @@ let parse (ts : token list) =
           // (x + y) * (z + w[)] => ( * ( + x y) z )
                                     ( * ( + x y) ( + z w ) )
 
-          // something tells me `exp` assignment ain't right.
+          // something tells me `top` assignment ain't right.
 
 
 
 
     // now handle parenthesis, use a counter?
-    if par_start:
+    elif par_start:
         groups++
-    if par_end and groups > 0:
+    elif par_end and groups > 0:
         groups--
     else:
         error
-- 
cgit v1.3