Goodbye C compiler, hello colm compiler

3 files changed, 763 insertions, 0 deletions

diff --git a/src/compiler/compiler.lm b/src/compiler/compiler.lm
new file mode 100644
index 0000000..59b0ee3
--- /dev/null
+++ b/src/compiler/compiler.lm
@@ -0,0 +1,298 @@
+include 'expr.lm'
+
+context fspec
+   token WS / space /
+
+   context primitive
+      token TYPE_SIGN / [us] /
+      token TYPE_BITS / [1-9][0-9]* /
+      int strtoull(a:str, b:int) = c_strtoull
+
+      def type
+         signed:bool
+         bits:int
+         [TYPE_SIGN TYPE_BITS] {
+            lhs.signed = ($r1 == 's')
+            lhs.bits = strtoull($r2, 10)
+         }
+   end
+
+   context container
+      context enum
+         lex
+            ignore / space+ /
+            literal `= `, `{ `}
+         end
+
+         literal `enum
+
+         int
+         const_int_expr(expr:collapser::collapsed) {
+            if (!expr || !expr.result.value || !expr.result.value.number) reject
+            return expr.result.value.number.value
+         }
+
+         def item
+            value:int
+            [name:name::type `= expr::enum::type `, item] { lhs.value = const_int_expr(r3.collapsed) }
+         |  [name:name::type `= expr::enum::type] { lhs.value = const_int_expr(r3.collapsed) }
+         |  [name:name::type `, item] { lhs.value = 0 } # TODO: count
+         |  [name:name::type] { lhs.value = 0 } # TODO: count
+
+         def type
+            name:str
+            items:item+
+            [type:`enum WS+ name::type? `{ item+ `}] { if (name::type in r3) lhs.name = $(name::type in r3) lhs.items = r5 }
+      end
+
+      context strukt # <- struct is taken :(
+         lex
+            ignore / space+ /
+            literal `{ `}
+         end
+
+         literal `struct
+
+         def item
+            [data:declaration::type]
+
+         def type
+            name:str
+            items:item+
+            [type:`struct WS+ name::type? `{ item+ `}] { if (name::type in r3) lhs.name = $(name::type in r3) lhs.items = r5 }
+      end
+
+      context select
+         lex
+            ignore / space+ /
+            literal `( `) `{ `} `*
+         end
+
+         literal `select
+
+         def item
+            [expr:expr::paren::type `) data:declaration::type]
+         |  [expr:`* `) data:declaration::type]
+
+         def type
+            name:str
+            items:item+ # BUG: marking item+ with items: in the match below causes weird behaviour
+            [type:`select `( expr::paren::type `) `{ item+ `}] { lhs.items = r6 }
+      end
+
+      def type
+         [data:enum::type] | [data:strukt::type] | [data:select::type]
+   end
+
+   context declaration
+      lex
+         ignore / space+ /
+         literal `; `| `[ `]
+      end
+
+      literal `enum `struct
+      token VISUAL / 'nul' | 'dec' | 'hex' | 'str' /
+
+      def visual
+         [WS+ name:VISUAL]
+
+      def filter
+         [`| function:reference::function::type]
+
+      def length
+         [`[ expr:expr::bracket::type `]]
+
+      def extra
+         length:collapser::collapsed
+         [length* filter:filter* visual:visual?] {
+            f:str = ''
+            for l:length in repeat(r1) {
+               if (f != '')
+                  f = f + '*'
+
+               if (l.expr.collapsed.result.value) {
+                  f = f + '(' + $l.expr.collapsed.result.value + ')'
+               } else {
+                  f = f + '(' + $l.expr.collapsed + ')'
+               }
+            }
+            lhs.length = collapser::collapsestr(f)
+         }
+
+      def type
+         # enum name <primitive> name <extra>;
+         [cref:`enum WS+ parent:name::type WS+ primitive:primitive::type WS+ name:name::type extra:extra `;] commit
+         # struct name name <extra>;
+      |  [cref:`struct WS+ parent:name::type WS+ name:name::type extra:extra `;] commit
+         # <primitive> name <extra>;
+      |  [primitive:primitive::type WS+ name:name::type extra:extra `;] commit
+         # select ((thing)) { ... } <extra>; INVALID
+      |  [container::select::type extra `;] commit { reject }
+         # select ((thing)) { ... } <primitive> name <extra>; INVALID
+      |  [container::select::type primitive::type WS+ name::type extra `;] commit { reject }
+         # struct (optional) { ... } <primitive> name <extra>; INVALID
+      |  [container::strukt::type primitive::type WS+ name::type extra `;] commit { reject }
+         # enum (optional) { ... } <primitive> name <extra>;
+      |  [container:container::type primitive:primitive::type WS+ name:name::type extra:extra `;] commit
+         # select ((expr)) { ... } name <extra>;
+         # struct (optional) { ... } name <extra>;
+      |  [container:container::type name:name::type extra:extra `;]
+         # (enum|struct) name { ... };
+      |  [container:container::type `;]
+   end
+
+   def source
+      [items:declaration::type*] commit
+end
+
+parse source:fspec::source[stdin]
+
+if (!source) {
+   print(error)
+   exit(1)
+}
+
+struct scope
+   names:map<str, map<str, any>>
+end
+
+global g_scopes:list<scope> = new list<scope>()
+
+void
+push_scope() {
+   s:scope = new scope()
+   s->names = new map<str, map<str, any>>()
+   g_scopes->push_head(s)
+}
+
+void
+pop_scope()
+{
+   g_scopes->pop_head()
+}
+
+any
+lookup_no_error(type:str, name:str) {
+   for s:scope in g_scopes {
+      cmap:map<str, any> = s->names->find(type)
+      if (cmap) {
+         var:any = cmap->find(name)
+         if (var)
+            return var
+      }
+   }
+   return nil
+}
+
+any
+insert(type:str, name:str, var:any)
+{
+   if (!name)
+      return var # <anon>
+
+   if (type != 'variable' && lookup_no_error(type, name)) {
+      print('`', type, ' ', name, '` is already declared as a `', type, '` in current scope!\n')
+      exit(1)
+   }
+
+   cmap:map<str, any> = g_scopes->top->names->find(type)
+
+   if (!cmap) {
+      cmap = new map<str, any>()
+   } else if (cmap->find(name)) {
+      print('`', type, ' ', name, '` is already declared as a `', type, '` in current scope!\n')
+      exit(1)
+   }
+
+   cmap->insert(name, var)
+   g_scopes->top->names->insert(type, cmap)
+   return var
+}
+
+any
+lookup(type:str, name:str)
+{
+   r:any = lookup_no_error(type, name)
+   if (!r) {
+      print('`', type, ' ', name, '` is not declared in this or outer scope!\n')
+      exit(1)
+   }
+   return r
+}
+
+str
+container_name_str(s:ref<str>) { if (!s) return '<anon>' return s }
+
+str
+signed_str(s:ref<bool>) { if (s) return 'signed' return 'unsigned' }
+
+void
+print_declaration(d:fspec::declaration::type)
+{
+   insert('variable', $d.name, d)
+   print('variable `', $d.name, '` is ')
+
+   c:fspec::container::type
+   if (d.cref) c = lookup($d.cref, $d.parent) else c = d.container
+
+   if (c)
+      print('`', c.data.type, ' ', container_name_str(c.data.name), '` ')
+
+   if (d.primitive)
+      print(d.primitive.bits, ' bits and ', signed_str(d.primitive.signed))
+
+   print('\n')
+
+   if (d.extra) {
+      if (d.extra.length) {
+         if (!d.extra.length.result.value || d.extra.length.result.value.reference) {
+            print('   it has a variable length that needs to be computed with formula `', $d.extra.length, '`\n')
+         } else {
+            if (d.extra.length.result.value.number) {
+               print('   it has a constant length of `', $d.extra.length.result.value, '`\n')
+            } else if (d.extra.length.result.value.string) {
+               print('   its length will increase until pattern `', $d.extra.length.result.value.string.raw, '` has been read from stream\n')
+            }
+         }
+      }
+
+      for f:fspec::declaration::filter in repeat(d.extra.filter)
+         print('   it needs to be filtered with `', $f.function, '`\n')
+
+      for v:fspec::declaration::visual in child(d.extra.visual)
+         print('   and it should be visualized as `', $v.name, '`\n')
+   }
+}
+
+void
+walk(s:fspec::container::type)
+{
+   insert($s.data.type, s.data.name, s)
+   if ($s.data.type == 'enum') {
+      for i:fspec::container::enum::item in repeat(s.data.items)
+         insert('variable', $i.name, i)
+   } else if ($s.data.type == 'struct') {
+      push_scope()
+      for d:fspec::container::strukt::item in repeat(s.data.items) {
+         if (d.data.container)
+            walk(d.data.container)
+         if (d.data.name)
+            print_declaration(d.data)
+      }
+      pop_scope()
+   } else if ($s.data.type == 'select') {
+      push_scope()
+      for d:fspec::container::select::item in repeat(s.data.items) {
+         if (d.data.container)
+            walk(d.data.container)
+         if (d.data.name)
+            print_declaration(d.data)
+      }
+      pop_scope()
+   }
+}
+
+push_scope()
+for s:fspec::declaration::type in repeat(source.items)
+   walk(s.container)
+pop_scope()
diff --git a/src/compiler/expr.lm b/src/compiler/expr.lm
new file mode 100644
index 0000000..d615358
--- /dev/null
+++ b/src/compiler/expr.lm
@@ -0,0 +1,410 @@
+include 'types.lm'
+
+global RTYPE_UNKNOWN:int = 0
+global RTYPE_NUMBER:int = 1
+global RTYPE_STRING:int = 2
+
+context expr
+   context enum
+      token EXPR / (any - [,}])+ /
+
+      def type
+         collapsed:collapser::collapsed
+         [EXPR] {
+            lhs.collapsed = collapser::collapsestr($r1)
+            if (!lhs.collapsed) reject
+         }
+   end
+
+   context paren
+      literal `( `)
+      token EXPR / (any - [()])+ /
+
+      def syntax
+         [EXPR] | [`( syntax `)]
+
+      def type
+         collapsed:collapser::collapsed
+         [syntax] {
+            lhs.collapsed = collapser::collapsestr($r1)
+            if (!lhs.collapsed) reject
+         }
+   end
+
+   context bracket
+      literal `[ `]
+      token EXPR / (any - '[' - ']')+ /
+
+      def syntax
+         [EXPR] | [`[ syntax `]]
+
+      def type
+         collapsed:collapser::collapsed
+         [syntax] {
+            lhs.collapsed = collapser::collapsestr($r1)
+            if (!lhs.collapsed) reject
+         }
+   end
+
+   context arg
+      literal `( `)
+      token EXPR / (any - [(),])+ /
+
+      def syntax
+         [EXPR] | [`( syntax `)]
+
+      def type
+         collapsed:collapser::collapsed
+         [syntax] {
+            lhs.collapsed = collapser::collapsestr($r1)
+            if (!lhs.collapsed) reject
+         }
+   end
+end
+
+context reference
+   context function
+      literal `( `) `,
+
+      def arg
+         [expr::arg::type `, arg] | [expr::arg::type]
+
+      def type
+         [name:name::type `( args:arg* `)]
+   end
+
+   context variable
+      def type
+         [name:name::type]
+   end
+
+   def type
+      [function::type]
+   |  [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:int, op:str) = c_op_stack_push
+   str op_stack_pop(stack:int) = c_op_stack_pop
+
+   stack:int
+   values:str
+   next_is_unary:bool
+
+   token WS / space /
+   literal `+ `-
+   literal `( `) `+# `-# `! `~ `* `/ `% `#+ `#- `<< `>> `< `> `<= `>= `== `!= `& `^ `| `&& `|| `? `:
+   literal `. `[ `]
+   literal `sizeof
+
+   def unary_unambi
+      [`!] | [`~]
+
+   def binary_unambi
+      [`.] | [`*] | [`/] | [`%] | [`<<] | [`>>] | [`<] | [`>] | [`<=] | [`>=] | [`==] | [`!=] | [`&] | [`^] | [`|] | [`&&] | [`||]
+
+   def ternary
+      [`:]
+
+   context reducer
+      int modulo(a:int, b:int) = c_modulo
+      int bitnot(a:int) = c_bitnot
+      int bitand(a:int, b:int) = c_bitand
+      int bitor(a:int, b:int) = c_bitor
+      int bitxor(a:int, b:int) = c_bitxor
+      int shiftl(a:int, b:int) = c_shiftl
+      int shiftr(a:int, b:int) = c_shiftr
+      int subscript(a:str, b: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[$(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 `&] { 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 `|] { lhs.value = parse value[$bitor(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 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 `]] {
+         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 WS value WS `]] { lhs.rtype = RTYPE_NUMBER }
+      |  [value WS unary] { lhs.rtype = RTYPE_NUMBER }
+      |  [value WS value WS binary] { lhs.rtype = RTYPE_NUMBER }
+      |  [value WS value WS value WS ternary] { if (r3.rtype != r5.rtype) reject lhs.rtype = r1.rtype }
+
+      def operation
+         rtype:int
+          [numop] { lhs = parse operation[$r1.value] }
+       |  [stringop] { lhs = parse operation[$r1.value] }
+       |  [valueop] { lhs.rtype = r1.rtype }
+       |  [value] { lhs.rtype = r1.rtype }
+       |  [value WS] { lhs.rtype = r1.rtype }
+       |  [operation WS] { lhs.rtype = r1.rtype }
+       |  [operation anynary] { 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 WS* rsquare] commit
+   |  [tok+ question tok+ colon tok+] commit
+   |  [otherops] { 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
+   collapse(s:stream)
+   {
+      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
+   }
+
+   collapsed
+   collapsestr(s:str)
+   {
+      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::collapse(stdin)
+# if (r) {
+#    print($r.result, '\n')
+# } else {
+#    print('invalid expression\n')
+# }
diff --git a/src/compiler/types.lm b/src/compiler/types.lm
new file mode 100644
index 0000000..34a9026
--- /dev/null
+++ b/src/compiler/types.lm
@@ -0,0 +1,55 @@
+context number
+   context unsigned
+      literal `true `false
+      token OCT / '0'[0-7]+ /
+      token DEC / [0-9]+ /
+      token HEX / '0x' xdigit+ /
+      int strtoull(a:str, b:int) = c_strtoull
+
+      def type
+         value:int
+         [`false] { lhs.value = 0 }
+      |  [`true] { lhs.value = 1 }
+      |  [OCT] { lhs.value = strtoull($r1, 8) }
+      |  [DEC] { lhs.value = strtoull($r1, 10) }
+      |  [HEX] { lhs.value = strtoull($r1, 16) }
+   end
+
+   lex
+      ignore / space+ /
+      literal `+ `-
+   end
+
+   def type
+      value:int
+      [unsigned::type] { lhs.value = r1.value }
+   |  [`- type] { lhs.value = r2.value - (r2.value * 2) }
+   |  [`+ type] { lhs.value = r2.value }
+end
+
+context string
+   rl ESC / '\\' /
+   token ESC_CHR / ESC [abfnrtv\\'"e] /
+   token ESC_HEX / ESC 'x' xdigit{2} /
+   token ESC_OCT / ESC [0-7]{1,3} /
+   token CHAR / ^cntrl - ['"] - ESC /
+   literal `' `"
+
+   def raw
+      [ESC_CHR] # TODO: how to output raw bytes?
+   |  [ESC_HEX] # TODO: how to output raw bytes?
+   |  [ESC_OCT] # TODO: how to output raw bytes?
+   |  [CHAR]
+
+   def type
+      length:int
+      [`' raw:raw* `'] { i:int = 0 for s:raw in r2 i = i + 1 lhs.length = i }
+   |  [`" raw:raw* `"] { i:int = 0 for s:raw in r2 i = i + 1 lhs.length = i }
+end
+
+context name
+   token NAME / [a-zA-Z_][a-zA-Z_0-9]* /
+
+   def type
+      [NAME]
+end