minilang.mini

# minilang compiler in minilang


var src_file, dst_file

# scanner
var line_number, cursor_pos
var character, lexeme
var token
var number, is_negative
var brackets, block, indent, newline, asm_active
var keywords


error(msg, a1, a2, a3, a4):
	fprintf(stderr, "%d:%d: error: ", line_number, cursor_pos)
	fprintf(stderr, msg, a1, a2, a3, a4)
	fprintf(stderr, "\n")
	exit(1)


output(msg, a1, a2, a3, a4): fprintf(dst_file, msg, a1, a2, a3, a4)


read_char():
	var c
	c = character
	character = fgetc(src_file)
	cursor_pos = cursor_pos + 1
	if character == '\n':
		line_number = line_number + 1
		cursor_pos = 0
	return c


scan():
	var i

	while 1:
		# whitespace
		while isspace(character):
			if newline:
				if character == ' ': indent = indent + 1
				elif character == '\t': indent = (indent & -4) + 4
			if character == '\n':
				indent = 0
				i = newline
				newline = 1
				if i == 0 & brackets == 0: return ';'
			read_char()

		# comment
		if character == '#':
			while character != '\n': read_char()
		else: break

	# indent
	if !brackets:
		if indent > block: error("invalid indentation")
		if indent < block:
			asm_active = 0
			block = block - 4
			return 'E'

	# asm line
	if asm_active:
		i = 0
		while character != '\n':
			token{i} = read_char()
			i = i + 1
		token{i} = 0
		return 'A'

	newline = 0

	if character == ':':
		read_char()
		block = block + 4
		indent = indent + 4
		return ':'

	if strchr("-+*&|!=<>;()[]{},", character):
		i = read_char()
		if strchr("<>=!", i) != 0 & character == '=':
			read_char()
			if i == '<': return 'L'
			if i == '>': return 'M'
			if i == '=': return 'Q'
			if i == '!': return 'T'
		if i == '[' | i == '(': brackets = brackets + 1
		elif i == ']' | i == ')': brackets = brackets - 1
		if isdigit(character): is_negative = (i == '-')
		return i

	# char
	if character == '\'':
		token{0} = read_char()
		i = 1
		if character == '\\': token{1} = read_char(); i = 2
		token{i} = read_char()
		token{i + 1} = '\''
		token{i + 2} = 0
		if read_char() != '\'': error("bad character literal")
		return 'C'

	# string
	if character == '"':
		i = 0
		while 1:
			if character == '\\': token{i} = read_char(); i = i + 1
			token{i} = read_char(); i = i + 1
			if i > 1020: error("string too long")
			if character == '"': break
		token{i} = read_char()
		token{i + 1} = 0
		return 'S'

	# number
	if isdigit(character):
		i = 0
		while isdigit(character):
			token{i} = read_char()
			i = i + 1
			if i > 20: error("number too long")
		token{i} = 0
		number = atoll(token)
		return 'N'

	# identifier/keyword
	if isalpha(character) | character == '_':
		token{0} = read_char()
		i = 1
		while isalnum(character) | character == '_':
			token{i} = read_char()
			i = i + 1
			if i > 62: error("identifier too long")
		token{i} = 0

		# check for keyword
		i = 0
		while i < 9:
			if strcmp(token, keywords[i]) == 0: return "ailfwbcrv"{i}
			i = i + 1
		return 'I'

	if character < 0: error("unknown character")
	if block > 0: block = block - 4; return 'E'
	return '0'


read_lexeme(): lexeme = scan()


expect(l):
	if lexeme != l: error("read <%c>, but <%c> expected", lexeme, l)
	read_lexeme()


# parser
var local_count, local_names, local_offsets
var cache, stack_size, frame
var label, while_labels, while_level
var regs, callregs


regname(i): return regs[cache[i]]


init_cache():
	var i; i = 0
	while i < 4: cache[i] = i; i = i + 1
	stack_size = 0


lookup_local():
	var i; i = 0
	while i < local_count:
		if strcmp(token, local_names[i]) == 0: return i
		i = i + 1
	return -1


add_local():
	var i
	frame = frame + 8
	i = 0
	while i < 256:
		if i == local_count:
			strcpy(local_names[i], token)
			local_offsets[i] = frame
			local_count = local_count + 1
			return
		if strcmp(token, local_names[i]) == 0: error("multiple declarations")
		i = i + 1
	error("too many variables")


push():
	var i, tmp
	i = 3
	tmp = cache[i]
	if stack_size >= 4: output("\tpush %s\n", regs[tmp])
	while i > 0:
		cache[i] = cache[i - 1]
		i = i - 1
	cache[0] = tmp
	stack_size = stack_size + 1


pop():
	var i, tmp
	stack_size = stack_size - 1
	if stack_size == 0: init_cache()
	else:
		i = 0
		tmp = cache[0]
		while i < 3:
			cache[i] = cache[i + 1]
			i = i + 1
		cache[i] = tmp
		if stack_size >= 4: output("\tpop %s\n", regs[i])


is_expr_beginning(): return strchr("-!(NCSI", lexeme) != 0
is_stmt_beginning(): return is_expr_beginning() | strchr("aiwbcr;", lexeme) != 0


expr_0():
	var i, v, s, name
	if lexeme == '!':
		read_lexeme()
		expr_0()
		output("\ttest %s, %s\n", regname(0), regname(0))
		output("\tsetz cl\n")
		output("\tmovzx %s, cl\n", regname(0))
		return
	if lexeme == '-':
		if !is_negative:
			read_lexeme()
			expr_0()
			output("\tneg %s\n", regname(0))
			return
		read_lexeme()
		push()
		output("\tmov %s, %ld\n", regname(0), -number)
		read_lexeme()
	elif lexeme == 'N':
		push()
		output("\tmov %s, %ld\n", regname(0), number)
		read_lexeme()
	elif lexeme == 'C':
		push()
		output("\tmov %s, %s\n", regname(0), token)
		read_lexeme()
	elif lexeme == '(':
		read_lexeme()
		expression()
		expect(')')
	elif lexeme == 'I':
		name = malloc(64)
		strcpy(name, token)
		v = lookup_local()
		read_lexeme()

		if lexeme == '(': # function call

			# save regs
			i = stack_size
			if i > 4: i = 4
			while i > 0:
				i = i - 1
				output("\tpush %s\n", regname(i))

			s = stack_size
			stack_size = 0

			read_lexeme()
			i = 0
			if is_expr_beginning():
				i = i + 1
				expression()
				output("\tpush %s\n", regname(0))
				pop()
				while lexeme == ',':
					read_lexeme()
					i = i + 1
					if i > 6: error("too many arguments")
					expression()
					output("\tpush %s\n", regname(0))
					pop()
			expect(')')

			# set-up regs
			while i > 0:
				i = i - 1
				output("\tpop %s\n", callregs[i])
			output("\txor rax, rax\n")
			output("\tcall %s@PLT\n", name)

			# return value in rax
			init_cache()
			push()
			stack_size = s + 1

			if s > 3: s = 3
			i = 1
			while i <= s:
				output("\tpop %s\n", regname(i))
				i = i + 1

		elif lexeme == '=': # assignment
			read_lexeme()
			expression()
			if v < 0: output("\tmov %s[rip], %s\n", name, regname(0))
			else: output("\tmov QWORD PTR [rbp - %d], %s\n",
					local_offsets[v], regname(0))
		else:
			push()
			if v < 0: output("\tmov %s, %s[rip]\n", regname(0), name)
			else: output("\tmov %s, QWORD PTR [rbp - %d]\n",
					regname(0), local_offsets[v])
		free(name)

	elif lexeme == 'S': # string literal
		push()
		output("\t.section .rodata\n")
		output("LC%d:\n", label)
		output("\t.string %s\n", token)
		output("\t.text\n")
		output("\tlea %s, LC%d[rip]\n", regname(0), label)
		label = label + 1
		read_lexeme()
	else: error("bad expression")

	while lexeme == '[':
		read_lexeme()
		expression()
		expect(']')
		if lexeme == '=':
			read_lexeme()
			expression()
			output("\tmov QWORD PTR [%s + %s * 8], %s\n",
					regname(2), regname(1), regname(0))
			i = cache[2]
			cache[2] = cache[0]
			cache[0] = i
			pop()
			pop()
			return
		output("\tmov %s, QWORD PTR [%s + %s * 8]\n",
				regname(1), regname(1), regname(0))
		pop()

	if lexeme == '{':
		read_lexeme()
		expression()
		expect('}')
		if lexeme == '=':
			read_lexeme()
			expression()
			output("\tmov rcx, %s\n", regname(0))
			output("\tmov BYTE PTR [%s + %s], cl\n", regname(2), regname(1))
			i = cache[2]
			cache[2] = cache[0]
			cache[0] = i
			pop()
			pop()
			return

		output("\tmov cl, BYTE PTR [%s + %s]\n", regname(1), regname(0))
		output("\tmovzx %s, cl\n", regname(1))
		pop()


expr_1():
	expr_0()
	while lexeme == '*':
		read_lexeme()
		expr_0()
		output("\timul %s, %s\n", regname(1), regname(0))
		pop()


expr_2():
	expr_1()
	while strchr("+-", lexeme):
		if lexeme == '+':
			read_lexeme()
			expr_1()
			output("\tadd %s, %s\n", regname(1), regname(0))
			pop()
		elif lexeme == '-':
			read_lexeme()
			expr_1()
			output("\tsub %s, %s\n", regname(1), regname(0))
			pop()


expr_3():
	var c
	expr_2()
	if lexeme == '<': c = "l"
	elif lexeme == '>': c = "g"
	elif lexeme == 'L': c = "le"
	elif lexeme == 'M': c = "ge"
	elif lexeme == 'Q': c = "e"
	elif lexeme == 'T': c = "ne"
	else: return
	read_lexeme()
	expr_2()
	output("\tcmp %s, %s\n", regname(1), regname(0))
	output("\tset%s cl\n", c)
	output("\tmovzx %s, cl\n", regname(1))
	pop()


expr_4():
	expr_3()
	while lexeme == '&':
		read_lexeme()
		expr_3()
		output("\tand %s, %s\n", regname(1), regname(0))
		pop()


expression():
	expr_4()
	while lexeme == '|':
		read_lexeme()
		expr_4()
		output("\tor %s, %s\n", regname(1), regname(0))
		pop()


statement_list(): while is_stmt_beginning(): statement()


statement():
	var l_end, l_next, end
	if lexeme == 'a':
		read_lexeme()
		asm_active = 1
		newline = 1
		expect(':')
		while lexeme == 'A':
			output("\t%s\n", token)
			read_lexeme()
		expect('E')
	elif lexeme == 'i':
		read_lexeme()
		expression()
		expect(':')
		l_end = label
		l_next = label + 1
		label = label + 2
		end = 0
		output("\ttest %s, %s\n", regname(0), regname(0))
		output("\tjz .L%d\n", l_next)
		init_cache()
		statement_list()
		expect('E')
		if strchr("lf", lexeme):
			output("\tjmp .L%d\n", l_end)
			end = 1
		output(".L%d:\n", l_next)
		while lexeme == 'f':
			read_lexeme()
			expression()
			expect(':')
			l_next = label
			label = label + 1
			output("\ttest %s, %s\n", regname(0), regname(0))
			output("\tjz .L%d\n", l_next)
			init_cache()
			statement_list()
			expect('E')
			if strchr("lf", lexeme): output("\tjmp .L%d\n", l_end)
			output(".L%d:\n", l_next)
		if lexeme == 'l':
			read_lexeme()
			expect(':')
			init_cache()
			statement_list()
			expect('E')
		if end: output(".L%d:\n", l_end)
	elif lexeme == 'w':
		read_lexeme()
		while_level = while_level + 1
		if while_level == 256: error("while nesting limit exceeded")
		while_labels[while_level] = label
		label = label + 2
		output(".L%d:\n", while_labels[while_level])
		expression()
		expect(':')
		output("\ttest %s, %s\n", regname(0), regname(0))
		output("\tjz .L%d\n", while_labels[while_level] + 1)
		init_cache()
		statement_list()
		expect('E')
		output("\tjmp .L%d\n", while_labels[while_level])
		output(".L%d:\n", while_labels[while_level] + 1)
		while_level = while_level - 1
	elif lexeme == 'b':
		read_lexeme()
		if while_level < 0: error("break without while")
		output("\tjmp .L%d\n", while_labels[while_level] + 1)
	elif lexeme == 'c':
		read_lexeme()
		if while_level < 0: error("continue without while")
		output("\tjmp .L%d\n", while_labels[while_level])
	elif lexeme == 'r':
		read_lexeme()
		if is_expr_beginning():
			expression()
			if strcmp(regname(0), "rax") != 0:
				output("\tmov rax, %s\n", regname(0))
			pop()
		output("\tleave\n")
		output("\tret\n")
	elif is_expr_beginning():
		expression()
		pop()
	else: expect(';')


minilang():
	var i, params

	# init scanner
	token = malloc(1024)
	keywords = malloc(8 * 9)
	keywords[0] = "asm"
	keywords[1] = "if"
	keywords[2] = "else"
	keywords[3] = "elif"
	keywords[4] = "while"
	keywords[5] = "break"
	keywords[6] = "continue"
	keywords[7] = "return"
	keywords[8] = "var"
	line_number = 1
	newline = 1
	read_char()
	read_lexeme()

	# init parser
	while_labels = malloc(8 * 256)
	cache = malloc(8 * 4)
	local_names = malloc(8 * 256)
	local_offsets = malloc(8 * 256)
	i = 0
	while i < 256:
		local_names[i] = malloc(64)
		i = i + 1
	regs = malloc(8 * 4)
	regs[0] = "r8"
	regs[1] = "r9"
	regs[2] = "r11"
	regs[3] = "rax"
	callregs = malloc(8 * 6)
	callregs[0] = "rdi"
	callregs[1] = "rsi"
	callregs[2] = "rdx"
	callregs[3] = "rcx"
	callregs[4] = "r8"
	callregs[5] = "r9"
	while_level = -1

	output("\t.intel_syntax noprefix\n")
	output("\t.text\n")

	while lexeme != '0':
		# global variables
		while lexeme == 'v':
			read_lexeme()
			expect('I')
		    output("\t.comm %s, 8, 8\n", token)
			while lexeme == ',':
				read_lexeme()
				expect('I')
    			output("\t.comm %s, 8, 8\n", token)
			while lexeme == ';': read_lexeme()


		# function definition
		expect('I')
		output("\t.globl %s\n", token)
		output("%s:\n", token)
		output("\tpush rbp\n")
		output("\tmov rbp, rsp\n")

		frame = 0
		local_count = 0

		# parameter list
		params = 0
		expect('(')
		if lexeme == 'I':
			params = params + 1
			expect('I')
			add_local()
			while lexeme == ',':
				read_lexeme()
				params = params + 1
				if params > 6: error("too many arguments")
				expect('I')
				add_local()
		expect(')')
		expect(':')

		# local variables
		while lexeme == ';': read_lexeme()
		while lexeme == 'v':
			read_lexeme()
			expect('I')
			add_local()
			while lexeme == ',':
				read_lexeme()
				expect('I')
				add_local()
			while lexeme == ';': read_lexeme()

		if frame > 0: output("\tsub rsp, %d\n", frame)
		i = 0
		while i < params:
			output("\tmov QWORD PTR [rbp - %d], %s\n", i * 8 + 8, callregs[i])
			i = i + 1

		init_cache()
		statement_list()
		output("\tleave\n")
		output("\tret\n")
		expect('E')


main(argc, argv):
	var s
	if argc < 2 | argc > 3:
		printf("usuage: %s <source> [output]\n", argv[0])
		exit(0)
	src_file = s = fopen(argv[1], "r")
	if !src_file: error("opening source file failed")
	if argc == 3: dst_file = fopen(argv[2], "w")
	else: dst_file = stdout
	minilang()
	fclose(src_file)
	if dst_file != stdin: fclose(dst_file)
	return 0