1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
# 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
```
|
