local n=5 local function W(n)if n=="\043"or n=="-"then return 1,2 elseif n=="\042"or n=="\047"or n=="\037"then return 3,4 elseif n=="\094"then return 8,7 end end local function Y(n,W,Y)local v={}W:expect("\079\112\101\110 \080\097\114\101\110\116\104\101\115\105\115")while W:peek()~=nil and(W:peek()).kind~="\067\108\111\115\101 \080\097\114\101\110\116\104\101\115\105\115"do table.insert(v,Y(W,1))if W:peek()~=nil and(W:peek()).kind=="\065\114\103\117\109\101\110\116 \083\101\112\097\114\097\116\111\114"then W:next()end end W:expect("\067\108\111\115\101 \080\097\114\101\110\116\104\101\115\105\115")return{kind="\070\117\110\099\116\105\111\110 \067\097\108\108";identifier=n,arguments=v}end local function v(W,Y,v)local g=v(Y,n)if g==nil then error("\069\120\112\101\099\116\101\100 \118\097\108\117\101 \097\102\116\101\114 \117\110\097\114\121")end return{kind="\085\110\097\114\121 \079\112\101\114\097\116\105\111\110",operator=W,value=g}end local function g(n,W)local Y=W(n,0)if Y==nil then error("\069\120\112\101\099\116\101\100 \118\097\108\117\101 \119\105\116\104\105\110 \112\097\114\101\110\116\104\101\115\101\115")end n:expect("\067\108\111\115\101 \080\097\114\101\110\116\104\101\115\105\115")return Y end local function N(n,W)local N=n:next()if N==nil then return nil elseif N.kind=="\078\117\109\098\101\114"or N.kind=="\086\097\114\105\097\098\108\101"then return N elseif N.kind=="\070\117\110\099\116\105\111\110"then return Y(N.identifier,n,W)elseif N.kind=="\079\112\101\114\097\116\111\114"then return v(N.operator,n,W)elseif N.kind=="\079\112\101\110 \080\097\114\101\110\116\104\101\115\105\115"then return g(n,W)end end local function m(n,Y)local v=N(n,m)while n:peek()~=nil do local g=n:peek()local N,j=W(g.operator)if N==nil or N<Y then break end n:expect("\079\112\101\114\097\116\111\114")local d=m(n,j)if d==nil then error(string.format("\069\120\112\101\099\116\101\100 \118\097\108\117\101 \097\102\116\101\114 \037\115",g.operator))end v={kind="\066\105\110\097\114\121 \079\112\101\114\097\116\105\111\110",operator=g.operator;left=v,right=d}end return v end local function j(n)if n:peek()==nil then error("\073\110\112\117\116 \101\109\112\116\121")end return m(n,1)end return j
local UNARY_BINDING_POWER = 5

local function getInfixBindingPower(operator)
	if operator == "+" or operator == "-" then
		return 1, 2
	elseif operator == "*" or operator == "/" or operator == "%" then
		return 3, 4
	elseif operator == "^" then
		return 8, 7
	end
end

local function parseFunction(identifier, lexer, expression)
	local arguments = {}

	lexer:expect("Open Parenthesis")

	while lexer:peek() ~= nil and lexer:peek().kind ~= "Close Parenthesis" do
		table.insert(arguments, expression(lexer, 1))

		if lexer:peek() ~= nil and lexer:peek().kind == "Argument Separator" then
			lexer:next()
		end
	end

	lexer:expect("Close Parenthesis")

	return { kind = "Function Call", identifier = identifier, arguments = arguments }
end

local function parseUnaryOperation(operator, lexer, parseExpression)
	local value = parseExpression(lexer, UNARY_BINDING_POWER)

	if value == nil then
		error("Expected value after unary")
	end

	return {
		kind = "Unary Operation",
		operator = operator,
		value = value,
	}
end

local function parseOpenParenthesis(lexer, parseExpression)
	local expression = parseExpression(lexer, 0)

	if expression == nil then
		error("Expected value within parentheses")
	end

	lexer:expect("Close Parenthesis")

	return expression
end

local function parseLeft(lexer, parseExpression)
	local token = lexer:next()

	if token == nil then
		return nil
	elseif token.kind == "Number" or token.kind == "Variable" then
		return token
	elseif token.kind == "Function" then
		return parseFunction(token.identifier, lexer, parseExpression)
	elseif token.kind == "Operator" then
		return parseUnaryOperation(token.operator, lexer, parseExpression)
	elseif token.kind == "Open Parenthesis" then
		return parseOpenParenthesis(lexer, parseExpression)
	end
end

local function parseExpression(lexer, minimumBindingPower)
	local left = parseLeft(lexer, parseExpression)

	while lexer:peek() ~= nil do
		local nextToken = lexer:peek()
		local leftBindingPower, rightBindingPower = getInfixBindingPower(nextToken.operator)

		if leftBindingPower == nil or leftBindingPower < minimumBindingPower then
			break
		end

		lexer:expect("Operator")

		local right = parseExpression(lexer, rightBindingPower)

		if right == nil then
			error(string.format("Expected value after %s", nextToken.operator))
		end

		left = { kind = "Binary Operation", operator = nextToken.operator, left = left, right = right }
	end

	return left
end

local function parse(lexer)
	if lexer:peek() == nil then
		error("Input empty")
	end

	return parseExpression(lexer, 1)
end

return parse
