haiku.git

# Rules providing basic arithmetic operations

HAIKU_ZERO = + 0 ;
HAIKU_ONE = + 1 ;

HAIKU_PAD_9 = 0 1 2 3 4 5 6 7 8 ;

# a > b <==> $(HAIKU_DIGIT_GREATER_$(a)[1$(b)])
HAIKU_DIGIT_GREATER_0 = $(HAIKU_PAD_9) ;
HAIKU_DIGIT_GREATER_1 = $(HAIKU_PAD_9) 1 ;
HAIKU_DIGIT_GREATER_2 = $(HAIKU_PAD_9) 1 1 ;
HAIKU_DIGIT_GREATER_3 = $(HAIKU_PAD_9) 1 1 1 ;
HAIKU_DIGIT_GREATER_4 = $(HAIKU_PAD_9) 1 1 1 1 ;
HAIKU_DIGIT_GREATER_5 = $(HAIKU_PAD_9) 1 1 1 1 1 ;
HAIKU_DIGIT_GREATER_6 = $(HAIKU_PAD_9) 1 1 1 1 1 1 ;
HAIKU_DIGIT_GREATER_7 = $(HAIKU_PAD_9) 1 1 1 1 1 1 1 ;
HAIKU_DIGIT_GREATER_8 = $(HAIKU_PAD_9) 1 1 1 1 1 1 1 1 ;
HAIKU_DIGIT_GREATER_9 = $(HAIKU_PAD_9) 1 1 1 1 1 1 1 1 1 ;

# a + b == $(HAIKU_DIGIT_ADD_$(a)[1$(b)]) (carry ignored)
HAIKU_DIGIT_ADD_0 = $(HAIKU_PAD_9) 0 1 2 3 4 5 6 7 8 9 ;
HAIKU_DIGIT_ADD_1 = $(HAIKU_PAD_9) 1 2 3 4 5 6 7 8 9 0 ;
HAIKU_DIGIT_ADD_2 = $(HAIKU_PAD_9) 2 3 4 5 6 7 8 9 0 1 ;
HAIKU_DIGIT_ADD_3 = $(HAIKU_PAD_9) 3 4 5 6 7 8 9 0 1 2 ;
HAIKU_DIGIT_ADD_4 = $(HAIKU_PAD_9) 4 5 6 7 8 9 0 1 2 3 ;
HAIKU_DIGIT_ADD_5 = $(HAIKU_PAD_9) 5 6 7 8 9 0 1 2 3 4 ;
HAIKU_DIGIT_ADD_6 = $(HAIKU_PAD_9) 6 7 8 9 0 1 2 3 4 5 ;
HAIKU_DIGIT_ADD_7 = $(HAIKU_PAD_9) 7 8 9 0 1 2 3 4 5 6 ;
HAIKU_DIGIT_ADD_8 = $(HAIKU_PAD_9) 8 9 0 1 2 3 4 5 6 7 ;
HAIKU_DIGIT_ADD_9 = $(HAIKU_PAD_9) 9 0 1 2 3 4 5 6 7 8 ;

# a - b == $(HAIKU_DIGIT_SUB_$(a)[1$(b)]) (carry ignored)
HAIKU_DIGIT_SUB_0 = $(HAIKU_PAD_9) 0 9 8 7 6 5 4 3 2 1 ;
HAIKU_DIGIT_SUB_1 = $(HAIKU_PAD_9) 1 0 9 8 7 6 5 4 3 2 ;
HAIKU_DIGIT_SUB_2 = $(HAIKU_PAD_9) 2 1 0 9 8 7 6 5 4 3 ;
HAIKU_DIGIT_SUB_3 = $(HAIKU_PAD_9) 3 2 1 0 9 8 7 6 5 4 ;
HAIKU_DIGIT_SUB_4 = $(HAIKU_PAD_9) 4 3 2 1 0 9 8 7 6 5 ;
HAIKU_DIGIT_SUB_5 = $(HAIKU_PAD_9) 5 4 3 2 1 0 9 8 7 6 ;
HAIKU_DIGIT_SUB_6 = $(HAIKU_PAD_9) 6 5 4 3 2 1 0 9 8 7 ;
HAIKU_DIGIT_SUB_7 = $(HAIKU_PAD_9) 7 6 5 4 3 2 1 0 9 8 ;
HAIKU_DIGIT_SUB_8 = $(HAIKU_PAD_9) 8 7 6 5 4 3 2 1 0 9 ;
HAIKU_DIGIT_SUB_9 = $(HAIKU_PAD_9) 9 8 7 6 5 4 3 2 1 0 ;

# a * b == $(HAIKU_DIGIT_MULT_CARRY_$(a)[1$(b)]) $(HAIKU_DIGIT_MULT_$(a)[1$(b)])
HAIKU_DIGIT_MULT_0 = $(HAIKU_PAD_9) 0 0 0 0 0 0 0 0 0 0 ;
HAIKU_DIGIT_MULT_1 = $(HAIKU_PAD_9) 0 1 2 3 4 5 6 7 8 9 ;
HAIKU_DIGIT_MULT_2 = $(HAIKU_PAD_9) 0 2 4 6 8 0 2 4 6 8 ;
HAIKU_DIGIT_MULT_3 = $(HAIKU_PAD_9) 0 3 6 9 2 5 8 1 4 7 ;
HAIKU_DIGIT_MULT_4 = $(HAIKU_PAD_9) 0 4 8 2 6 0 4 8 2 6 ;
HAIKU_DIGIT_MULT_5 = $(HAIKU_PAD_9) 0 5 0 5 0 5 0 5 0 5 ;
HAIKU_DIGIT_MULT_6 = $(HAIKU_PAD_9) 0 6 2 8 4 0 6 2 8 4 ;
HAIKU_DIGIT_MULT_7 = $(HAIKU_PAD_9) 0 7 4 1 8 5 2 9 6 3 ;
HAIKU_DIGIT_MULT_8 = $(HAIKU_PAD_9) 0 8 6 4 2 0 8 6 4 2 ;
HAIKU_DIGIT_MULT_9 = $(HAIKU_PAD_9) 0 9 8 7 6 5 4 3 2 1 ;

HAIKU_DIGIT_MULT_CARRY_0 = $(HAIKU_PAD_9) 0 0 0 0 0 0 0 0 0 0 ;
HAIKU_DIGIT_MULT_CARRY_1 = $(HAIKU_PAD_9) 0 0 0 0 0 0 0 0 0 0 ;
HAIKU_DIGIT_MULT_CARRY_2 = $(HAIKU_PAD_9) 0 0 0 0 0 1 1 1 1 1 ;
HAIKU_DIGIT_MULT_CARRY_3 = $(HAIKU_PAD_9) 0 0 0 0 1 1 1 2 2 2 ;
HAIKU_DIGIT_MULT_CARRY_4 = $(HAIKU_PAD_9) 0 0 0 1 1 2 2 2 3 3 ;
HAIKU_DIGIT_MULT_CARRY_5 = $(HAIKU_PAD_9) 0 0 1 1 2 2 3 3 4 4 ;
HAIKU_DIGIT_MULT_CARRY_6 = $(HAIKU_PAD_9) 0 0 1 1 2 3 3 4 4 5 ;
HAIKU_DIGIT_MULT_CARRY_7 = $(HAIKU_PAD_9) 0 0 1 2 2 3 4 4 5 6 ;
HAIKU_DIGIT_MULT_CARRY_8 = $(HAIKU_PAD_9) 0 0 1 2 3 4 4 5 6 7 ;
HAIKU_DIGIT_MULT_CARRY_9 = $(HAIKU_PAD_9) 0 0 1 2 3 4 5 6 7 8 ;


# pragma mark - Number Operations


rule NormalizeNum number
{
	# NormalizeNum <number> ;

	local sign ;
	if $(number[1]) = "-" || $(number[1] = "+" {
		sign = $(number[1]) ;
		number = $(number[2-]) ;
	} else {
		sign = "+" ;
	}

	# cut off leading zeros
	local number = [ FReverse $(number) ] ;
	while $(number[1]) = 0 {
		number = $(number[2-]) ;
	}
	number = [ FReverse $(number) ] ;

	# zero is respresented as + 0
	if ! $(number) {
		number = 0 ;
		sign = "+" ;
	}

	return $(sign) $(number) ;
}

rule Num string : dontExit
{
	# Num <number string> [ : <dontExit> ] ;

	# split the string into three parts: sign, digits, and remainder
	local temp = [ Match ([^0-9]*)([0-9]+)(.*) : $(string) ] ;

	# there must be digits, but there must not be a remainder
	if ! $(temp[2]) || $(temp[3]) {
		if $(dontExit) {
			return ;
		}
		Exit "Not a number" ;
	}

	# get the sign
	local number ;
	if ! $(temp[1]) {
		number = "+" ;
	} else if $(temp[1]) = "+" || $(temp[1]) = "-" {
		number = $(temp[1]) ;
	} else {
		if $(dontExit) {
			return ;
		}
		Exit "Not a number (sign)" ;
	}

	# split the digits
	temp = $(temp[2]) ;
	while $(temp[1]) {
		# split off the last digit
		temp = [ Match (.*)([0-9]) : $(temp[1]) ] ;
		number += $(temp[2]) ;
	}

	# normalize
	return [ NormalizeNum $(number) ] ;
}

rule Num2String number
{
	# Num2String <number> ;

	local sign = $(number[1]) ;
	if $(sign) = "+" {
		sign = "" ;
	}

	number = [ FReverse $(number[2-]) ] ;

	return $(sign)$(number:J=) ;
}

rule NumGreaterAbs a : b
{
	# NumGreaterAbs <a> : <b> ;

	# we compare from least to most significant digit
	local cmp = 0 ;
	while $(a) && $(b) {
		# chop off the first digit
		local da = $(a[1]:E=0) ;
		local db = $(b[1]:E=0) ;
		a = $(a[2-]) ;
		b = $(b[2-]) ;

		if $(da) != $(db) {
			if $(HAIKU_DIGIT_GREATER_$(da)[1$(db)]) {
				cmp = 1 ;
			} else {
				cmp = -1 ;
			}
		}
	}

	# a is greater, if b is not longer and a is either longer or equally long
	# and greater according to the digits comparison
	if ! $(b) && ( $(a) || $(cmp) = 1 ) {
		return 1 ;
	}
	return ;
}

rule AddNumAbs a : b
{
	# AddNum <a> : <b> ;

	local result ;
	local carry ;
	while $(a) || $(b) || $(carry) {
		# chop off the first digit
		local da = $(a[1]:E=0) ;
		local db = $(b[1]:E=0) ;
		a = $(a[2-]) ;
		b = $(b[2-]) ;

		# add carry to the first digit
		if $(carry) {
			local daa = $(HAIKU_DIGIT_ADD_1[1$(da)]) ;
			carry = $(HAIKU_DIGIT_GREATER_$(da)[1$(daa)]) ;
			da = $(daa) ;
		}

		# add digits
		local dr = $(HAIKU_DIGIT_ADD_$(da)[1$(db)]) ;
		if $(HAIKU_DIGIT_GREATER_$(da)[1$(dr)]) {
			carry = 1 ;
		}

		result += $(dr) ;
	}

	return $(result) ;
}

rule SubNumAbs a : b
{
	# SubNum <a> : <b> ;

	local result ;
	local carry ;
	while $(a) && ( $(b) || $(carry) ) {
		# chop off the first digit
		local da = $(a[1]:E=0) ;
		local db = $(b[1]:E=0) ;
		a = $(a[2-]) ;
		b = $(b[2-]) ;

		# sub carry from the first digit
		if $(carry) {
			local daa = $(HAIKU_DIGIT_SUB_$(da)[11]) ;
			carry = $(HAIKU_DIGIT_GREATER_$(daa)[1$(da)]) ;
			da = $(daa) ;
		}

		# sub digits
		local dr = $(HAIKU_DIGIT_SUB_$(da)[1$(db)]) ;
		if $(HAIKU_DIGIT_GREATER_$(dr)[1$(da)]) {
			carry = 1 ;
		}

		result += $(dr) ;
	}

	if $(b) || $(carry) {
		Exit "Error: SubNumAbs: Can't subtract greater from smaller number." ;
	}

	return $(result) ;
}

rule NegNum a
{
	# NegNum <a> ;

	if $(a[1]) = "+" {
		if $(a) = $(HAIKU_ZERO) {
			return $(a) ;
		}
		return "-" $(a[2-]) ;
	} else {
		return "+" $(a[2-]) ;
	}
}

rule AddNum a : b
{
	# AddNum <a> : <b> ;

	local signa = $(a[1]) ;
	local signb = $(b[1]) ;
	a = $(a[2-]) ;
	b = $(b[2-]) ;

	if $(signa) = $(signb) {
		return $(signa) [ AddNumAbs $(a) : $(b) ] ;
	} else {
		local result ;
		if [ NumGreaterAbs $(a) : $(b) ] {
			result = $(signa) [ SubNumAbs $(a) : $(b) ] ;
		} else {
			result = $(signb) [ SubNumAbs $(b) : $(a) ] ;
		}
		return [ NormalizeNum $(result) ] ;
	}
}

rule SubNum a : b
{
	# SubNum <a> : <b> ;
	return [ AddNum $(a) : [ NegNum $(b) ] ] ;
}

rule MultNumAbsDigit a : digit
{
	# MultNumAbsDigit <a> : <digit> ;

	local digitMultiples = $(HAIKU_DIGIT_MULT_$(digit)) ;
	local digitCarries = $(HAIKU_DIGIT_MULT_CARRY_$(digit)) ;

	local result ;
	local carry = 0 ;
	while $(a) || $(carry) != 0 {
		# chop off the first digit
		local da = $(a[1]:E=0) ;
		a = $(a[2-]) ;

		local dr = $(digitMultiples[1$(da)]) ;

		# add carry to the resulting digit
		if $(carry) {
			local dra = $(HAIKU_DIGIT_ADD_$(dr)[1$(carry)]) ;
			carry = $(HAIKU_DIGIT_GREATER_$(dr)[1$(dra)]:E=0) ;
			dr = $(dra) ;
		}

		# new carry
		carry = $(HAIKU_DIGIT_ADD_$(carry:E=0)[1$(digitCarries[1$(da)])]) ;

		result += $(dr) ;
	}

	return $(result) ;
}

rule MultNum a : b
{
	# MultNum <a> : <b> ;

	# If one of the factors is 0, we save us computation and normalization.
	if $(a) = $(HAIKU_ZERO) || $(b) = $(HAIKU_ZERO) {
		return $(HAIKU_ZERO) ;
	}

	# get the sign for the result
	local sign = "+" ;
	if $(a[1]) != $(b[1]) {
		sign = "-" ;
	}

	a = $(a[2-]) ;
	b = $(b[2-]) ;

	# multiply the individual digits of b with a and add up the result
	local result = 0 ;
	local prefix ;
	while $(b) {
		local db = $(b[1]) ;
		b = $(b[2-]) ;

		local adb = $(prefix) [ MultNumAbsDigit $(a) : $(db) ] ;
		result = [ AddNumAbs $(result) : $(adb) ] ;

		prefix += 0 ;
	}

	return $(sign) $(result) ;
}

rule NumGreater a : b
{
	local signa = $(a[1]) ;
	local signb = $(b[1]) ;
	a = $(a[2-]) ;
	b = $(b[2-]) ;

	if $(signa) = $(signb) {
		if $(signa) = "+" {
			return [ NumGreaterAbs $(a) : $(b) ] ;
		} else {
			return [ NumGreaterAbs $(b) : $(a) ] ;
		}
	} else {
		if $(signa) = "+" {
			return 1 ;
		} else {
			return ;
		}
	}
}


# pragma mark - Number String Operations


rule Inc a
{
	# Inc <number string a> ;
	return [ Num2String [ AddNum [ Num $(a) ] : + 1 ] ] ;
}

rule Dec a
{
	# Dec <number string a> ;
	return [ Num2String [ AddNum [ Num $(a) ] : - 1 ] ] ;
}

rule Neg a
{
	# Neg <number string a> ;
	return [ Num2String [ NegNum [ Num $(a) ] ] ] ;
}

rule Add a : b
{
	# Add <number string a> : <number string b> ;
	return [ Num2String [ AddNum [ Num $(a) ] : [ Num $(b) ] ] ] ;
}

rule Sub a : b
{
	# Sub <number string a> : <number string b> ;
	return [ Num2String [ SubNum [ Num $(a) ] : [ Num $(b) ] ] ] ;
}

rule Mult a : b
{
	# Mult <number string a> : <number string b> ;
	return [ Num2String [ MultNum [ Num $(a) ] : [ Num $(b) ] ] ] ;
}

rule Equal a : b
{
	# Equal <number string a> : <number string b> ;
	if [ Num $(a) ] = [ Num $(b) ] {
		return 1 ;
	}

	return ;
}

rule Less a : b
{
	# Less <number string a> : <number string b> ;
	return [ NumGreater [ Num $(b) ] : [ Num $(a) ] ] ;
}

rule Greater a : b
{
	# Greater <number string a> : <number string b> ;
	return [ NumGreater [ Num $(a) ] : [ Num $(b) ] ] ;
}

rule LessOrEqual a : b
{
	# LessOrEqual <number string a> : <number string b> ;
	if [ NumGreater [ Num $(a) ] : [ Num $(b) ] ] {
		return ;
	}
	return 1 ;
}

rule GreaterOrEqual a : b
{
	# GreaterOrEqual <number string a> : <number string b> ;
	if [ NumGreater [ Num $(b) ] : [ Num $(a) ] ] {
		return ;
	}
	return 1 ;
}


# pragma mark - Expression Parser


rule ParseAtom expression
{
	# ParseAtom <expression> ;

	# expression: '(' expression ')' | number

	if $(expression[1]) = "(" {
		local result = [ ParseExpression $(expression[2-]) ] ;
		if $(result[2]) != ")" {
			Exit "ParseAtom: Parse error: Expected \")\"." ;
		}
		return $(result[1]) $(result[3-]) ;
	} else {
		if ! $(expression) {
			Exit "ParseAtom: Parse error: Unexpected end of expression." ;
		}

		local num = [ Num $(expression[1]) : 1 ] ;
		if ! $(num) {
			Exit "ParseAtom: Parse error: Expected number instead of:"
				$(expression[1]) ;
		}

		return [ Num2String $(num) ] $(expression[2-]) ;
	}
}

rule ParseUnary expression
{
	# ParseUnary <expression> ;

	# expression: ('+'/'-')* atom

	if ! $(expression) {
		Exit "ParseUnary: Parse error: Unexpected end of expression." ;
	}

	# eat all unary "+" and "-" operations
	local neg ;
	while $(expression[1]) = "+" || $(expression[1]) = "-" {
		if $(expression[1]) = "-" {
			if $(neg) {
				neg = ;
			} else {
				neg = 1 ;
			}
		}

		expression = $(expression[2-]) ;
	}

	local result = [ ParseAtom $(expression) ] ;

	if $(neg) {
		return [ Neg $(result[1]) ] $(result[2-]) ;
	}
	return $(result) ;
}

rule ParseTerm expression
{
	# ParseTerm <expression> ;

	# expression: unary ('*' unary)*

	local result = [ ParseUnary $(expression) ] ;
	local product = $(result[1]) ;
	expression = $(result[2-]) ;

	while $(expression[1]) = "*" {
		# get the operation
		local operation ;
		operation = Mult ;

		# parse the next operand
		result = [ ParseUnary $(expression[2-]) ] ;
		expression = $(result[2-]) ;

		# compute the product
		product = [ $(operation) $(product) : $(result[1]) ] ;
	}

	return $(product) $(expression) ;
}

rule ParseExpression expression
{
	# ParseExpression <expression> ;

	# expression: term ('+'/'-' term)*

	local result = [ ParseTerm $(expression) ] ;
	local sum = $(result[1]) ;
	expression = $(result[2-]) ;

	while $(expression[1]) = "+" || $(expression[1]) = "-" {
		# get the operation
		local operation ;
		if $(expression[1]) = "+" {
			operation = Add ;
		} else {
			operation = Sub ;
		}

		# parse the next operand
		result = [ ParseTerm $(expression[2-]) ] ;
		expression = $(result[2-]) ;

		# compute the sum
		sum = [ $(operation) $(sum) : $(result[1]) ] ;
	}

	return $(sum) $(expression) ;
}


rule Expr expression
{
	# Expr <expression> ;

	# tokenize the expression
	local tokens ;
	local string ;
	for string in $(expression) {
		while $(string) {
			local split = [ Match "[ \t]*(-|[()+*]|[0-9]*)(.*)" : $(string) ] ;
			if ! $(split[1]) {
				Exit "Expr: Syntax error: Invalid token: \"$(string)\"." ;
			}

			tokens += $(split[1]) ;
			string = $(split[2]) ;
		}
	}

	local result = [ ParseExpression $(tokens) ] ;
	if $(result[2-]) {
		Exit "Expr: Garbage at end of expression:" $(result[2-]) ;
	}

	return $(result[1]) ;
}