SyntaxError = table{}

function syntax_error(s)
   return table SyntaxError{value=["Syntax error: ",s,"."].join()}
end

Symbol = table(Type,"Symbol"){}
Id = table(Type,"Id"){}

function scan(s)
   a = []
   n = len(s)
   i = 0
   line = 0
   col = 0
   while i<n
      if s[i] in "+-*/^(){}[];,="
         a.push([Symbol,s[i],line,col])
         i+=1; col+=1
      elif s[i].isalpha()
         j = i; hcol=col
         while i<n and s[i].isalnum()
            i+=1; col+=1
         end
         if len(a)!=0 and a[-1][0] is Int
            a.push([Symbol,"*",line,col])
         end
         a.push([Id,s[j..i-1],line,hcol])
      elif s[i].isdigit()
         j = i; hcol=col
         while i<n and s[i].isdigit()
            i+=1; col+=1
         end
         a.push([Int,int(s[j..i-1]),line,hcol])
      elif s[i].isspace()
         if s[i]=='\n'
            line+=1
            col=0
         else
            col+=1
         end
         i+=1
      else
         raise syntax_error(
            "unexpected character: '{}'"%[s[i]])
      end
   end
   a.push([null,null,line,col])
   return a
end

function expect(a,i)
   if a[i][0] is null
      raise syntax_error("unexpected end of input")
   else
      return a[i]
   end
end

function atom(a,i)
   t = expect(a,i)
   if t[0] is Int
      return i+1,t[1]
   elif t[0] is Id
      return i+1,t[1]
   elif t[0] is Symbol and t[1]=="("
      i,x = expression(a,i+1)
      te = expect(a,i)
      if not (te[0] is Symbol and te[1]==")")
         raise syntax_error(
            "expected ')', but got '{}'"%[te])
      end
      return i+1,x
   else
      raise syntax_error(
         "unexpected symbol: '{}'"%[a[i]])
   end
end

function argument_list(a,i)
   argv = []
   while true
      i,x = expression(a,i)
      argv.push(x)
      t = expect(a,i)
      if t[0] is Symbol and t[1]==","
         i+=1
      elif t[0] is Symbol and t[1]==")"
         return i+1,argv
      else
         raise syntax_error(
            "expected ',' or ')', but got '{}'"%[t])
      end
   end
end

function application(a,i)
   i,x = atom(a,i)
   t = a[i]
   if t[0] is Symbol and t[1]=="("
      i,argv = argument_list(a,i+1)
      return i,[x]+argv
   else
      return i,x
   end
end

function power(a,i)
   i,x = application(a,i)
   t = a[i]
   if t[0] is Symbol and t[1]=="^"
      i,y = negation(a,i+1)
      return i,["^",x,y]
   else
      return i,x
   end
end

function negation(a,i)
   t = a[i]
   if t[0] is Symbol and t[1]=="-"
      i,x = power(a,i+1)
      return i,["*",-1,x]
   else
      return power(a,i)
   end
end

function multiplication(a,i)
   i,x = negation(a,i)
   op = a[i]
   while op[0] is Symbol and op[1]=="*" or op[1]=="/"
      i,y = negation(a,i+1)
      x = [op[1],x,y]
      op = a[i]
   end
   return i,x
end

function addition(a,i)
   i,x = multiplication(a,i)
   op = a[i]
   while op[0] is Symbol and op[1]=="+" or op[1]=="-"
      i,y = multiplication(a,i+1)
      x = ["+",x,y] if op[1]=="+" else ["+",x,["*",-1,y]]
      op = a[i]
   end
   return i,x
end

function assignment(a,i)
   i,x = addition(a,i)
   op = a[i]
   if op[0] is Symbol and op[1]=="="
      i,y = addition(a,i+1)
      return i,["=",x,y]
   else
      return i,x
   end
end

function expression(a,i)
   return assignment(a,i)
end

function ast(a)
   i,x = expression(a,0)
   t = a[i]
   if t[0] is null
      return x
   else
      raise syntax_error(
         "unexpected symbol: '{}'"%[a[i]])
   end
end

binary_operators = {
   "=": 1,
   "+": 2, "-": 2,
   "*": 3, "/": 4,
   "^": 5
}

function ast_to_string(t,level=0)
   if t: List
      op = t[0]
      if op in binary_operators
         op_level = binary_operators[op]
         if op_level>=level
            return t[1..].map(|x| ast_to_string(x,op_level)).join(op)
         else
            return t[1..].map(ast_to_string).join(op,"(",")")
         end
      elif op=="~"
         return ["-",ast_to_string(t[1],3)].join()
      else
         return t[1..].map(ast_to_string).join(",",str(op)+"(",")")
      end
   else
      return str(t)
   end
end

function compile(s)
   return ast(scan(s))
end