Initial commit

[jwcc.git] / lib / parser / parser.lua

function gettoken(tokenlist)
	local token = table.remove(tokenlist, 1)
	return token
end

function peektoken(tokenlist, n)
	if not n then
		n = 1
	end
	local token = tokenlist[n]
	return token
end

function expecttoken(token, expected)
	if not token then
		error("unexpected EOF", 1)
	end
	for k,v in pairs(expected) do
		if token.type == v then
			return token
		end
	end
	error("unexpected token "..token.type,1)
end

function parser_global(tokenlist, parsetree)
	-- GLOBAL = (VARIABLE | FUNCTION)
	local token = peektoken(tokenlist)
	while token do
		if token.type == "int" then
			local subtoken
			expecttoken(peektoken(tokenlist, 2), {"identifier"})
			subtoken = peektoken(tokenlist, 3)
			if not subtoken then
				error("unexpected EOF")
			end
			if subtoken.type == "(" then
				table.insert(parsetree, parser_function(tokenlist))
			elseif subtoken.type == ";" or subtoken.type == "=" then
				table.insert(parsetree, parser_variable(tokenlist))
			else
				error("unexpected token "..subtoken.type.." following 'int <identifier>'")
			end
		else
			error("unexpected token "..token.type)
		end
		token = peektoken(tokenlist)
	end
end

function parser_function(tokenlist)
	-- FUNCTION = TYPE IDENTIFIER ARGSLIST STMTLIST
	local myfunction = {}
	
	myfunction.type = "function"
	myfunction.returntype = parser_type(tokenlist)
	local token = expecttoken(gettoken(tokenlist), {"identifier"})
	myfunction.name = token.value
	myfunction.args = parser_argslist(tokenlist)
	myfunction.body = parser_stmtlist(tokenlist)
	return myfunction
end

function parser_type(tokenlist)
	-- TYPE = INT
	return expecttoken(gettoken(tokenlist), { "int" }).type
end

function parser_istype(tokenlist)
	if peektoken(tokenlist).type == "int" then
		return true
	end
	return false
end

function parser_argslist(tokenlist)
	-- ARGSLIST = ( [TYPE IDENTIFIER [, TYPE IDENTIFIER]*] )
	local token
	local argslist = {}
	local firstarg = true
	expecttoken(gettoken(tokenlist), { "(" })
	while true do
		local type, ident
		token = peektoken(tokenlist)
		if token.type == ")" then
			gettoken(tokenlist)
			return argslist
		end
		if not firstarg then
			expecttoken(gettoken(tokenlist), { "," })
			token = peektoken(tokenlist)
		end
		firstarg = false
		type = parser_type(tokenlist)
		token = expecttoken(gettoken(tokenlist), { "identifier" })
		ident = token.value
		table.insert(argslist, { type = type, name = ident })
	end
end

function parser_stmtlist(tokenlist)
	-- STMTLIST = { [( VARIABLE | STATEMENT | STMTLIST)]* }
	local token
	local stmtlist = {}
	
	stmtlist.type = "stmtlist"
	stmtlist.body = {}
	expecttoken(gettoken(tokenlist), {"{"})
	while true do
		token = peektoken(tokenlist)
		if token.type == "}" then
			gettoken(tokenlist)
			return stmtlist
		end
		if parser_istype(tokenlist) then
			table.insert(stmtlist.body, parser_variable(tokenlist))
		elseif token.type == "{" then
			table.insert(stmtlist.body, parser_stmtlist(tokenlist))
		else
			table.insert(stmtlist.body, parser_statement(tokenlist))
		end
	end
end

function parser_variable(tokenlist)
	-- VARIABLE = TYPE IDENTIFIER [ = TYPEINITIALIZER ] ;
	local variable = {}
	variable.type = "variable"
	variable.vtype = parser_type(tokenlist)
	variable.name = expecttoken(gettoken(tokenlist), { "identifier" }).value
	expecttoken(peektoken(tokenlist), { ";", "=" })
	local token = gettoken(tokenlist)
	if token.type == ";" then
		return variable
	end
	if token.type == '=' then
		if variable.vtype == "int" then
			variable.initializer = parser_getinitializer_int(tokenlist)
		else
			error("internal error")
		end
		expecttoken(gettoken(tokenlist), { ";" })
		return variable
	end
	error("internal error")
end

function parser_getinitializer_int(tokenlist)
	return expecttoken(gettoken(tokenlist), { "number" }).value
end

function parser_statement(tokenlist)
	-- STATEMENT = ; | EXPRESSION ; | (WHILE | IF)
	local token = peektoken(tokenlist)
	if token.type == ";" then
		return nil
	elseif token.type == "while" then
		return parser_while(tokenlist)
	elseif token.type == "if" then
		return parser_if(tokenlist)
	elseif token.type == "return" then
		return parser_return(tokenlist)
	else
		local result = parser_expression(tokenlist)
		expecttoken(gettoken(tokenlist), { ";" })
		return result
	end
end

function parser_while(tokenlist)
	-- WHILE = WHILE ( EXPRESSION ) CHUNK
	local result = {}
	result.type = "while"
	expecttoken(gettoken(tokenlist), { "while" })
	expecttoken(gettoken(tokenlist), { "(" })
	result.expression = parser_expression(tokenlist)
	expecttoken(gettoken(tokenlist), { ")" })
	result.chunk = parser_chunk(tokenlist)
	return result
end

function parser_if(tokenlist)
	-- IF = IF ( EXPRESSION ) CHUNK
	local result = {}
	result.type = "if"
	expecttoken(gettoken(tokenlist), { "if" })
	expecttoken(gettoken(tokenlist), { "(" })
	result.expression = parser_expression(tokenlist)
	expecttoken(gettoken(tokenlist), { ")" })
	result.chunk = parser_chunk(tokenlist)
	return result
end

function parser_return(tokenlist)
	-- RETURN [EXPRESSION] ;
	local result = {}
	result.type = "return"
	expecttoken(gettoken(tokenlist), { "return" })
	if peektoken(tokenlist).type == ";" then
		gettoken(tokenlist)
		return result
	end
	result.expression = parser_expression(tokenlist)
	expecttoken(gettoken(tokenlist), { ";" })
	return result
end

function parser_chunk(tokenlist)
	local token = peektoken(tokenlist)
	if token.type == "{" then
		return parser_stmtlist(tokenlist)
	else
		return parser_statement(tokenlist)
	end
end

function parser_expression(tokenlist)
	-- we support:
	-- ( ) + - < > == =
	-- of those, ( ) has precedence 0
	-- + - has precedence 3
	-- < > has precedence 5
	-- == has precedence 6
	-- = has precedence 13
	
	local operators = {
		["*"] = { precedence = 2, associative = "left" }, 
		["/"] = { precedence = 2, associative = "left" }, 
		["+"] = { precedence = 3, associative = "left" },
		["-"] = { precedence = 3, associative = "left" }, 
		["<"] = { precedence = 5, associative = "left" },
		[">"] = { precedence = 5, associative = "left" },
		["=="] ={ precedence = 6, associative = "left" },
		["="] = { precedence = 13, associative = "left" }
	}
	
	-- Shunting yard algorithm
	local outstack = {}
	local opstack = {}
	
	local addopertooutstack = function(oper)
		assert(table.getn(outstack) >= 2, "attempted to add operator "..oper.value.." to stack containing "..table.getn(outstack).." elements")
		oper.right = table.remove(outstack, table.getn(outstack))
		oper.left = table.remove(outstack, table.getn(outstack))
		table.insert(outstack, oper)
	end
	
	while true do
		local token = peektoken(tokenlist)
		if token.type == "identifier" or token.type == "number" then
			gettoken(tokenlist)
			
			if peektoken(tokenlist).type == "(" then	-- function call guyz!
				gettoken(tokenlist)
				local outp = { type = "funccall", name = token.value, args = {} }
				local token = peektoken(tokenlist)
				while token.type ~= ")" do
					table.insert(outp.args, parser_expression(tokenlist))
					token = expecttoken(peektoken(tokenlist), { ")", "," })
					if token.type == "," then
						gettoken(tokenlist)
					end
				end
				gettoken(tokenlist)
				
				table.insert(outstack, outp)
			else
				table.insert(outstack, { type = token.type, value = token.value })
			end
		elseif token.type == "(" then
			gettoken(tokenlist)
			
			local outp = parser_expression(tokenlist)
			expecttoken(gettoken(tokenlist), { ")" })
			table.insert(outstack, outp)
		elseif operators[token.type] then
			gettoken(tokenlist)
			
			while table.getn(opstack) > 0 and
					((operators[token.type].associative == "left" and
					  operators[token.type].precedence >= operators[opstack[table.getn(opstack)].value].precedence) or
					 (operators[token.type].associative == "right" and
					  operators[token.type].precedence > operators[opstack[table.getn(opstack)].value].precedence)) do
				addopertooutstack(table.remove(opstack, table.getn(opstack)))
			end
			table.insert(opstack, { type = "operator", value = token.type })
		elseif token.type == ")" or token.type == ";" or token.type == "," then
			break
		end
	end
	
	while table.getn(opstack) > 0 do
		addopertooutstack(table.remove(opstack, table.getn(opstack)))
	end
	assert(table.getn(outstack) == 1, "wrong number of objects ("..table.getn(outstack)..") on output stack after expression parse")
	return { type = "expression", value = outstack[1] }
end

function parse(tokenlist)
	local parsetree = {}
	parser_global(tokenlist, parsetree)
	return parsetree
end