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