# Parsing ASTs without recursion

There's missing a error check for two consequtive non-nullary expressions.

```
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
          top = t

      // ts = (l : l : ts)
      elif t is leaf && root is leaf:
          error

      // ts = (l : n : l : ts)
      elif t is leaf && root.r == nil:
          root.r = t
          top = root

      // unless polish notation ofc,
      // ts = (n : ts)
      elif t is node && root == nil:
          error

      elif t is node && root != nil:
          // ts = (l : n : ts)
          if root is leaf:
              t.l = root
              root = t
              top = 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)
          //
          // 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=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

          // when precedence is (root > t), then t.l=root,             top=t,    root=t
          // Eg. ( x * y + . ) => ( + ( x * y ) . )
          //         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 ) )
                   - - - - -
          // 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.r
                  top    = root
                  root.r = t
                  root   = t

              else:
                  t.l  = root
                  root = t
                  top  = root

          // 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 `top` assignment ain't right.




    // now handle parenthesis, use a counter?
    elif par_start:
        groups++
    elif par_end and groups > 0:
        groups--
    else:
        error
```