blob: 8bb90e45d22c3bf639de8b67321fa700209cc3f2 (
plain)
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
|
Data struct:
- expression
- matrix
- complex
- polynomial
State Data struct:
- function
- variable
Instruction/line:
if is '?' evaluate label else declare label.
instruction ::= <label> '=' (<expr> | '?')
Declaration:
label is a declaration of function or variable name
label ::= <funcDecl> | <var>
funcDecl ::= <var> '(' <var> ')'
var ::= [a-zA-Z]+
Expression:
5. real imag matrix
4. + -
3. * / % **
2. ^
1. ( ) -- not an operator
expr ::= <sum> | <imag> | <matrix> | <real> | <var> | <funcExpr>
Arithmetic:
sum ::= <term> (+ | -) <sum> | <term>
term ::= <factor> (* | / | % | **)? <term> | <factor> -- default to '*'
factor ::= <base> '^' <factor> | <base>
base ::= '(' <expr> ')' | <expr>
Leaf:
real ::= [0-9]+(\.[0-9]+)?
imag ::= <real> '*'? 'i'
matrix ::= '[' (<matrixRow> ';')* ']'
matrixRow ::= '[' (<expr> ',')* ']'
fundExpr ::= <var> '(' <expr> ')'
REPL:
1. read user input
2. parse it into an ast
3. reduce the ast to the minimum possible form
4.
every expression is a binary tree, except () which can be interpreted by changing the
structure of the tree.
operators and operand are both expression (tree nodes).
operators always need 2 operand (not leaf node)
operand need 0 (leaf node)
evaluation of operand return the operand
evaluation of operator, evaluate his childs, perform the operation on them, return the result
fold?
!monoid
+
/ \
* \
/ \ \ 3 * 4 + (5 - 3i)
3 4 -
/ \
5 3i
Node +
|_ Node *
| |_ Leaf 3
| |_ Leaf 4
|
|_ Node -
|_ Leaf 5
|_ Leaf 3i
i^0 = 1
i^1 = sqrt(-1) = i
i^2 = -1
i^3 = -sqrt(-1) = -i
i^4 = 1
atoms: evaluate to itself
- rational
- imaginary
- complex
containers: evaluate contained
- matrix
- variable?
- f() ?
operations:
- +
- -
- *
- /
- %
- ^
- **
|
