import "io"

manifest { htsize = 100 }

let htable = nil;

let hash(s) be
{ let h = 93291, i = 0;
  while true do
  { let c = byte i of s;
    if c = 0 then break;
    h := h * 69 + c;
    i +:= 1 }
  resultis (h bitand 0x7FFFFFFF) rem htsize }

let streql(s, t) be
{ let i = 0;
  while true do
  { let a = byte i of s, b = byte i of t;
    if a /= b then resultis false;
    if a = 0 then resultis true;
    i +:= 1; } }

manifest
{ he_string = 0, he_decl = 1, he_next = 2, sizeof_he = 3 }

let id(s) be
{ let h = hash(s);
  let p = htable ! h;
  while p /= nil do
  { if streql(s, p!he_string) then
      resultis p;
    p := p!he_next }
  p := newvec(sizeof_he);
  p!he_string := s;
  p!he_decl := nil;
  p!he_next := htable!h;
  htable!h := p;
  resultis p }

manifest
{ nd_size = 0, nd_type = 1 }

let n(a) be
{ let len = numbargs();
  let p = newvec(len + 1);
  let arg = @a;
  p!nd_size := len;
  for i = 0 to len-1 do
    p!(i+1) := arg!i;
  resultis p }

manifest
{ NT_ADD = 1, NT_SUB = 2, NT_MUL = 3, NT_DIV = 4, NT_EQUAL = 5, NT_LESS = 6, NT_LESSEQ = 7,
  NT_NUMBER = 8, NT_VAR = 9 }

let run() be
{ let tree = n(NT_MUL, n(NT_ADD, n(NT_VAR, id("x")),
                                 n(NT_NUMBER, 101)),
                       n(NT_SUB, n(NT_DIV, n(NT_NUMBER, 3),
                                           n(NT_VAR, id("cat")))
                                 n(NT_NUMBER, 59)));
  print(tree, 0);
  outch('\n') }

let start() be
{ init(!0x101, !0x100 - !0x101);
  htable := newvec(htsize);
  for i = 0 to htsize - 1 do
    htable ! i := nil;
  run(); }