# 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
```