summaryrefslogtreecommitdiff
path: root/src/compiler/expr.lm
blob: 7c650b4a30285f30cb23fb0e5d90ba60dddf6a72 (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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
# Expression parser && collapser
# This lets us know what kind of operations we need to compile in.
# But it also collapses the expressions offline, so we don't have to compile in constant expressions
# This makes the compiler "useful"

include 'types.lm'

global RTYPE_UNKNOWN:int = 0
global RTYPE_NUMBER:int = 1
global RTYPE_STRING:int = 2

context expr
   context enum
      lex
         ignore / space+ /
         literal `, `{ `}
         token EXPR / any /
      end

      def type
         collapsed:collapser::collapsed
         [EXPR+] commit {
            lhs.collapsed = collapser::stream($r1)
            if (!lhs.collapsed) reject
         }
   end

   context select
      lex
         ignore / space+ /
         literal `( `) `{ `}
         token EXPR / any /
      end

      def syntax
         [EXPR] | [`( syntax+ `)]

      def type
         collapsed:collapser::collapsed
         [syntax+] commit {
            lhs.collapsed = collapser::stream($r1)
            if (!lhs.collapsed && $r1 != '*'reject
         }
   end

   context paren
      lex
         ignore / space+ /
         literal `( `) `{ `}
         token EXPR / any /
      end

      def syntax
         [EXPR] | [`( syntax+ `)]

      def type
         collapsed:collapser::collapsed
         [syntax+] commit {
            lhs.collapsed = collapser::stream($r1)
            if (!lhs.collapsed) reject
         }
   end

   context bracket
      lex
         ignore / space+ /
         literal `[ `] `? `: `{ `}
         token EXPR / any /
      end

      def syntax
         [EXPR] | [`[ syntax+ `]] | [syntax+ `? syntax+ `: syntax+]

      def type
         collapsed:collapser::collapsed
         [syntax+] commit {
            lhs.collapsed = collapser::stream($r1)
            if (!lhs.collapsed) reject
         }
   end

   context arg
      lex
         ignore / space+ /
         literal `( `) `, `{ `}
         token EXPR / any /
      end

      def syntax
         [EXPR] | [`( syntax+ `)]

      def type
         collapsed:collapser::collapsed
         [syntax+] commit {
            lhs.collapsed = collapser::stream($r1)
            if (!lhs.collapsed) reject
         }
   end
end

context reference
   lex
      # reserved
      literal `struct `enum `select
      literal `nul `dec `hex `str
      literal `until `sizeof
      token PRIMITIVE / [us][1-9][0-9]/
      literal `( `) `,
      token NAME / [a-zA-Z_][a-zA-Z_0-9]/
   end

   context function
      def arg
         [expr::arg::type WS* `, WS* arg] | [expr::arg::type]

      def name
         [`until] | [`sizeof] | [NAME]

      def type
         [name:name WS* `( WS* args:arg* WS* `)]
   end

   context variable
      def type
         [name:NAME]
   end

   def type
      [function:function::type] | [variable:variable::type]
end

context collapser
   # BUG: lists seem to not really work well here
   #      implement simple native stack
   int op_stack_new() = c_op_stack_new
   int op_stack_free(stack:int) = c_op_stack_free
   str op_stack_top(stack:int) = c_op_stack_top
   bool op_stack_push(stack:intop:str) = c_op_stack_push
   str op_stack_pop(stack:int) = c_op_stack_pop

   stack:int
   values:str
   next_is_unary:bool

   literal `+ `-
   literal `( `) `+# `-# `! `~ `* `/ `% `#+ `#- `<< `>> `< `> `<= `>= `== `!= `&& `& `^ `|| `| `? `:
   literal `. `[ `]
   literal `sizeof

   def unary_unambi
      [`!] | [`~]

   def binary_unambi
      [`.] | [`*] | [`/] | [`%] | [`<<] | [`>>] | [`<] | [`>] | [`<=] | [`>=] | [`==] | [`!=] | [`^] | [`&&] | [`&] | [`||] | [`|]

   def ternary
      [`:]

   context reducer
      int modulo(a:intb:int) = c_modulo
      int bitnot(a:int) = c_bitnot
      int bitand(a:intb:int) = c_bitand
      int bitor(a:intb:int) = c_bitor
      int bitxor(a:intb:int) = c_bitxor
      int shiftl(a:intb:int) = c_shiftl
      int shiftr(a:intb:int) = c_shiftr
      int subscript(a:strb:int) = c_subscript

      def builtin
         value:value
         [`sizeof `( string::type `)] { lhs.value = parse value[$r3.length] }

      def value
         rtype:int
         [builtin:builtin] { lhs = r1.value }
      |  [number:number::type] { lhs.rtype = RTYPE_NUMBER }
      |  [string:string::type] { lhs.rtype = RTYPE_STRING }
      |  [reference:reference::type]

      def unary
         [`+#] | [`-#] | [unary_unambi]

      def binary
         [`#+] | [`#-] | [binary_unambi]

      def anynary
         [unary] | [binary] | [ternary]

      def numop
         value:value
         [number::type WS `-#] { lhs.value = parse value[$(r1.value - (r1.value * 2))] }
      |  [number::type WS `+#] { lhs.value = parse value[$r1.value] }
      |  [number::type WS `!] { r:int = 0 if (r1.value == 0) r = 1 lhs.value = parse value[$r] }
      |  [number::type WS `~] { lhs.value = parse value[$bitnot(r1.value)] }
      |  [number::type WS number::type WS `*] { lhs.value = parse value[$(r1.value * r3.value)] }
      |  [number::type WS number::type WS `/] { lhs.value = parse value[$(r1.value / r3.value)] }
      |  [number::type WS number::type WS `%] { lhs.value = parse value[$modulo(r1.value, r3.value)] }
      |  [number::type WS number::type WS `#+] { lhs.value = parse value[$(r1.value + r3.value)] }
      |  [number::type WS number::type WS `#-] { lhs.value = parse value[$(r1.value - r3.value)] }
      |  [number::type WS number::type WS `<<] { lhs.value = parse value[$shiftl(r1.value, r3.value)] }
      |  [number::type WS number::type WS `>>] { lhs.value = parse value[$shiftr(r1.value, r3.value)] }
      |  [number::type WS number::type WS `<] { r:int = 0 if (r1.value < r3.value) r = 1 lhs.value = parse value[$r] }
      |  [number::type WS number::type WS `>] { r:int = 0 if (r1.value > r3.value) r = 1 lhs.value = parse value[$r] }
      |  [number::type WS number::type WS `<=] { r:int = 0 if (r1.value <= r3.value) r = 1 lhs.value = parse value[$r] }
      |  [number::type WS number::type WS `>=] { r:int = 0 if (r1.value >= r3.value) r = 1 lhs.value = parse value[$r] }
      |  [number::type WS number::type WS `==] { r:int = 0 if (r1.value == r3.value) r = 1 lhs.value = parse value[$r] }
      |  [number::type WS number::type WS `!=] { r:int = 0 if (r1.value != r3.value) r = 1 lhs.value = parse value[$r] }
      |  [number::type WS number::type WS `&&] { r:int = 0 if (r1.value && r3.value) r = 1 lhs.value = parse value[$r] }
      |  [number::type WS number::type WS `&] { lhs.value = parse value[$bitand(r1.value, r3.value)] }
      |  [number::type WS number::type WS `^] { lhs.value = parse value[$bitxor(r1.value, r3.value)] }
      |  [number::type WS number::type WS `||] { r:int = 0 if (r1.value || r3.value) r = 1 lhs.value = parse value[$r] }
      |  [number::type WS number::type WS `|] { lhs.value = parse value[$bitor(r1.value, r3.value)] }
      |  [number::type WS number::type WS number::type WS `:] { if (r1.value) lhs.value = parse value[$r3] else lhs.value = parse value[$r5] }
      |  [number::type WS value WS `]] commit { reject }

      # strings can only be operated with `!= and `== against other strings
      def stringop
         value:value
         [string::type WS string::type WS `==] commit { r:int = 0 if (r1.raw == r3.raw) r = 1 lhs.value = parse value[$r] }
      |  [string::type WS string::type WS `!=] commit { r:int = 0 if (r1.raw != r3.raw) r = 1 lhs.value = parse value[$r] }
      |  [number::type WS string::type WS string::type WS `:] { if (r1.value) lhs.value = parse value[$r3] else lhs.value = parse value[$r5] }
      |  [string::type WS unary] commit { reject } # <unary> str
      |  [string::type WS number::type WS binary] commit { reject } # str <binary> num
      |  [number::type WS string::type WS binary] commit { reject } # num <binary> str
      |  [string::type WS string::type WS binary] { reject } # str <math> str
      |  [value WS number::type WS string::type WS ternary] commit { reject } # (v ? num : str)
      |  [value WS string::type WS number::type WS ternary] commit { reject } # (v ? str : num)
      |  [string::type WS value WS value WS ternary] commit { reject } # (str ? v : v)
      |  [string::type WS number::type WS `]] commit {
         if (r1.length <= r3.value) {
            print('subscript out of bounds\n')
            reject
         } else {
            lhs.value = parse value[$subscript($r1.raw, r3.value)]
         }
      }

      def valueop
         rtype:int
         value:value
         [value WS `+#] { lhs.value = parse value[$r1] }
      |  [value WS value WS `>] { lhs = parse valueop[$r2 ' ' $r1 ' <'] }
      |  [value WS value WS `>=] { lhs = parse valueop[$r2 ' ' $r1 ' <='] }
      |  [value WS value WS op:`]] { lhs.rtype = RTYPE_NUMBER }
      |  [value WS op:unary] { lhs.rtype = RTYPE_NUMBER }
      |  [value WS value WS op:binary] { lhs.rtype = RTYPE_NUMBER }
      |  [value WS value WS value WS op:ternary] commit { if (r3.rtype != r5.rtype) reject lhs.rtype = r1.rtype }
      |  [valueop WS op:anynary] { lhs.rtype = r1.rtype }
      |  [valueop WS value] { lhs.rtype = r1.rtype }

      def operation
         rtype:int
          [numop] { lhs = parse operation[$r1.value] }
       |  [stringop] { lhs = parse operation[$r1.value] }
       |  [value WS] { lhs = parse operation[$r1] }
       |  [operation WS] { lhs = parse operation[$r1] }
       |  [valueop] { if (r1.value) lhs = parse operation[$r1.value] else lhs.rtype = r1.rtype }
       |  [value] { lhs.rtype = r1.rtype }

      def collapsed
         value:value
         [operation+] commit {
            # we check return type of every operation to make sure we don't operate on different types
            rtype:int = RTYPE_UNKNOWN
            for i:operation in repeat(r1) {
               if (i.rtype != RTYPE_UNKNOWN && rtype != RTYPE_UNKNOWN && i.rtype != rtype)
                  reject
               rtype = i.rtype
            }
            lhs.value = parse value[$lhs]
         }
   end

   def operator
      precedence:int
      rassoc:bool
      open:str
      close:str
      args:int
      [`[]  { lhs.precedence = 0  lhs.rassoc = false lhs.args = 0 lhs.open = ']' }
   |  [`]]  { lhs.precedence = 0  lhs.rassoc = false lhs.args = 2 lhs.close = '[' }
   |  [`(]  { lhs.precedence = 0  lhs.rassoc = false lhs.args = 0 lhs.open = ')' }
   |  [`)]  { lhs.precedence = 0  lhs.rassoc = false lhs.args = 0 lhs.close = '(' }
   |  [`.]  { lhs.precedence = 0  lhs.rassoc = false lhs.args = 2 }
   |  [`+#] { lhs.precedence = 1  lhs.rassoc = true  lhs.args = 1 }
   |  [`-#] { lhs.precedence = 1  lhs.rassoc = true  lhs.args = 1 }
   |  [`!]  { lhs.precedence = 1  lhs.rassoc = true  lhs.args = 1 }
   |  [`~]  { lhs.precedence = 1  lhs.rassoc = true  lhs.args = 1 }
   |  [`*]  { lhs.precedence = 2  lhs.rassoc = false lhs.args = 2 }
   |  [`/]  { lhs.precedence = 2  lhs.rassoc = false lhs.args = 2 }
   |  [`%]  { lhs.precedence = 2  lhs.rassoc = false lhs.args = 2 }
   |  [`#+] { lhs.precedence = 3  lhs.rassoc = false lhs.args = 2 }
   |  [`#-] { lhs.precedence = 3  lhs.rassoc = false lhs.args = 2 }
   |  [`<<] { lhs.precedence = 4  lhs.rassoc = false lhs.args = 2 }
   |  [`>>] { lhs.precedence = 4  lhs.rassoc = false lhs.args = 2 }
   |  [`<]  { lhs.precedence = 5  lhs.rassoc = false lhs.args = 2 }
   |  [`>]  { lhs.precedence = 5  lhs.rassoc = false lhs.args = 2 }
   |  [`<=] { lhs.precedence = 5  lhs.rassoc = false lhs.args = 2 }
   |  [`>=] { lhs.precedence = 5  lhs.rassoc = false lhs.args = 2 }
   |  [`==] { lhs.precedence = 6  lhs.rassoc = false lhs.args = 2 }
   |  [`!=] { lhs.precedence = 6  lhs.rassoc = false lhs.args = 2 }
   |  [`&]  { lhs.precedence = 7  lhs.rassoc = false lhs.args = 2 }
   |  [`^]  { lhs.precedence = 8  lhs.rassoc = false lhs.args = 2 }
   |  [`|]  { lhs.precedence = 9  lhs.rassoc = false lhs.args = 2 }
   |  [`&&] { lhs.precedence = 10 lhs.rassoc = false lhs.args = 2 }
   |  [`||] { lhs.precedence = 11 lhs.rassoc = false lhs.args = 2 }
   |  [`?]  { lhs.precedence = 12 lhs.rassoc = true  lhs.args = 0 lhs.open = ':' }
   |  [`:]  { lhs.precedence = 12 lhs.rassoc = true  lhs.args = 3 }

   void
   operate(op:operator)
   {
      if (!op.args)
         return 0

      s:str = values + $op
      # print('collapse: ', s, ' -> ')
      r:reducer::collapsed = parse reducer::collapsed[s]

      if (!r) {
         reject
      } else {
         # print(^r, '\n')
         values = $r + ' '
      }
   }

   void
   flush_all()
   {
      while (op_stack_top(stack))
         operate(parse operator[op_stack_pop(stack)])
   }

   void
   flush_until(name:str)
   {
      while (op_stack_top(stack) && op_stack_top(stack) != name)
         operate(parse operator[op_stack_pop(stack)])
   }

   void
   flush_ordered(name:str)
   {
      op:operator = parse operator[name]

      top:operator
      if (op_stack_top(stack)) top = parse operator[op_stack_top(stack)]
      while (top && (top.precedence < op.precedence || (top.precedence == op.precedence && !top.rassoc)) && !top.open) {
         operate(parse operator[op_stack_pop(stack)])
         if (op_stack_top(stack)) top = parse operator[op_stack_top(stack)] else top = nil
      }

      if (op.close)
         flush_until(op.close)

      next_is_unary = !op.close
   }

   void
   stack_op(name:str)
   {
      flush_ordered(name)
      # print('push op: ', name, '\n')
      op_stack_push(stack, name)
   }

   void
   stack_value(value:str)
   {
      # print('push value: ', value, '\n')
      values = values + value + ' '
      next_is_unary = false
   }

   def value
      [reducer::builtin] | [number::unsigned::type] | [string::type] | [reference::type]

   def ambiguous
      [`+] | [`-]

   def unambiguous
      [unary_unambi] | [binary_unambi]

   def binary
      [ambiguous] | [binary_unambi]

   def otherops
      op:str
      [ambiguous] { if (next_is_unary) lhs.op = $r1 + '#' else lhs.op = '#' + $r1 }
   |  [unambiguous] { lhs.op = $r1 }

   def lsquare
      [`[] { stack_op($lhs) }

   def rsquare
      [`]] { stack_op($lhs) }

   def lparen
      [`(] { stack_op($lhs) }

   def rparen
      [`)] { stack_op($lhs) }

   def question
      [`?] { stack_op($lhs) }

   def colon
      [`:] { stack_op($lhs) }

   def constant
      [number::unsigned::type] | [string::type]

   def tok#en
      [value WS* value] commit { reject }
   |  [binary WS* binary] commit { reject }
   |  [constant WS* `(] commit { reject }
   |  [`) WS* value] commit { reject }
   |  [`] WS* value] commit { reject }
   |  [lparen tok+ rparen] commit
   |  [lsquare tok+ rsquare] commit
   |  [tok+ question tok+ colon tok+] commit
   |  [otherops] commit { stack_op(r1.op) }
   |  [value] { stack_value($r1) }
   |  [WS] { lhs = nil }

   def collapsed
      result:reducer::collapsed
      [tok+] commit { flush_all() lhs.result = parse reducer::collapsed[values] if (!lhs.result) reject }

   collapsed
   stream(s:any)
   {
      c:collapser = new collapser()
      c->stack = op_stack_new()
      c->values = ''
      c->next_is_unary = true
      parse r:collapsed(c)[s]
      op_stack_free(c->stack)
      return r
   }
end

# r:collapser::collapsed = collapser::stream(stdin)
# if (r) {
#    print($r.result, '\n')
# } else {
#    print('invalid expression\n')
# }