diff options
| -rw-r--r-- | docs/recursion_free_parsing.md | 67 |
1 files 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 |