From a859f78651b4da2d31890b9c7b01a431fa7a93f6 Mon Sep 17 00:00:00 2001 From: David Kerkeslager Date: Sun, 6 Aug 2017 14:45:45 -0400 Subject: [PATCH] Added support for comparison operators --- examples/12_integer_comparison.fur | 53 ++++++++++ examples/12_integer_comparison.fur.output.txt | 18 ++++ generation.py | 7 ++ parsing.py | 82 +++++++++++++- templates/program.c | 54 ++++++++++ tokenization.py | 71 ++++++++++++- transformation.py | 100 ++++++++++++++++++ 7 files changed, 380 insertions(+), 5 deletions(-) create mode 100644 examples/12_integer_comparison.fur create mode 100644 examples/12_integer_comparison.fur.output.txt diff --git a/examples/12_integer_comparison.fur b/examples/12_integer_comparison.fur new file mode 100644 index 0000000..0826b6b --- /dev/null +++ b/examples/12_integer_comparison.fur @@ -0,0 +1,53 @@ +print('13 < 17: ') +print(13 < 17) +print('\n') +print('17 < 17: ') +print(17 < 17) +print('\n') +print('19 < 17: ') +print(19 < 17) +print('\n') +print('13 > 17: ') +print(13 > 17) +print('\n') +print('17 > 17: ') +print(17 > 17) +print('\n') +print('19 > 17: ') +print(19 > 17) +print('\n') +print('13 == 17: ') +print(13 == 17) +print('\n') +print('17 == 17: ') +print(17 == 17) +print('\n') +print('19 == 17: ') +print(19 == 17) +print('\n') +print('13 <= 17: ') +print(13 <= 17) +print('\n') +print('17 <= 17: ') +print(17 <= 17) +print('\n') +print('19 <= 17: ') +print(19 <= 17) +print('\n') +print('13 >= 17: ') +print(13 >= 17) +print('\n') +print('17 >= 17: ') +print(17 >= 17) +print('\n') +print('19 >= 17: ') +print(19 >= 17) +print('\n') +print('13 != 17: ') +print(13 != 17) +print('\n') +print('17 != 17: ') +print(17 != 17) +print('\n') +print('19 != 17: ') +print(19 != 17) diff --git a/examples/12_integer_comparison.fur.output.txt b/examples/12_integer_comparison.fur.output.txt new file mode 100644 index 0000000..b9e30a3 --- /dev/null +++ b/examples/12_integer_comparison.fur.output.txt @@ -0,0 +1,18 @@ +13 < 17: true +17 < 17: false +19 < 17: false +13 > 17: false +17 > 17: false +19 > 17: true +13 == 17: false +17 == 17: true +19 == 17: false +13 <= 17: true +17 <= 17: true +19 <= 17: false +13 >= 17: false +17 >= 17: true +19 >= 17: true +13 != 17: true +17 != 17: false +19 != 17: true \ No newline at end of file diff --git a/generation.py b/generation.py index 28f08cd..8e93e02 100644 --- a/generation.py +++ b/generation.py @@ -61,6 +61,13 @@ def generate_expression(c_argument): transformation.CMultiplicationExpression: 'multiply', transformation.CIntegerDivisionExpression: 'integerDivide', transformation.CModularDivisionExpression: 'modularDivide', + transformation.CEqualityExpression: 'equals', + transformation.CInequalityExpression: 'notEquals', + transformation.CGreaterThanExpression: 'greaterThan', + transformation.CLessThanExpression: 'lessThan', + transformation.CGreaterThanOrEqualExpression: 'greaterThanOrEqual', + transformation.CLessThanOrEqualExpression: 'lessThanOrEqual', + transformation.CAndExpression: 'and', } return 'builtin${}({}, {})'.format( diff --git a/parsing.py b/parsing.py index 495b34a..b30556e 100644 --- a/parsing.py +++ b/parsing.py @@ -105,6 +105,54 @@ FurModularDivisionExpression = collections.namedtuple( ], ) +FurEqualityExpression = collections.namedtuple( + 'FurEqualityExpression', + [ + 'left', + 'right', + ], +) + +FurInequalityExpression = collections.namedtuple( + 'FurInequalityExpression', + [ + 'left', + 'right', + ], +) + +FurLessThanOrEqualExpression = collections.namedtuple( + 'FurLessThanOrEqualExpression', + [ + 'left', + 'right', + ], +) + +FurGreaterThanOrEqualExpression = collections.namedtuple( + 'FurGreaterThanOrEqualExpression', + [ + 'left', + 'right', + ], +) + +FurLessThanExpression = collections.namedtuple( + 'FurLessThanExpression', + [ + 'left', + 'right', + ], +) + +FurGreaterThanExpression = collections.namedtuple( + 'FurGreaterThanExpression', + [ + 'left', + 'right', + ], +) + def _integer_literal_expression_parser(index, tokens): failure = (False, index, None) @@ -219,12 +267,40 @@ def _addition_level_expression_parser(index, tokens): return True, index, result +def _equality_level_expression_parser(index, tokens): + failure = (False, index, None) + + success, index, result = _addition_level_expression_parser(index, tokens) + + if not success: + return failure + + while success and index < len(tokens) and tokens[index].type == 'equality_level_operator': + success = False + + if index + 1 < len(tokens): + success, try_index, value = _addition_level_expression_parser(index + 1, tokens) + + if success: + result = { + '==': FurEqualityExpression, + '!=': FurInequalityExpression, + '>=': FurGreaterThanOrEqualExpression, + '<=': FurLessThanOrEqualExpression, + '>': FurGreaterThanExpression, + '<': FurLessThanExpression, + }[tokens[index].match](left=result, right=value) + index = try_index + + return True, index, result + + def _comma_separated_list_parser(index, tokens): failure = (False, index, None) expressions = [] - success, index, expression = _addition_level_expression_parser(index, tokens) + success, index, expression = _expression_parser(index, tokens) if success: expressions.append(expression) @@ -235,7 +311,7 @@ def _comma_separated_list_parser(index, tokens): success = False if index + 1 < len(tokens): - success, try_index, expression = _addition_level_expression_parser(index + 1, tokens) + success, try_index, expression = _expression_parser(index + 1, tokens) if success: expressions.append(expression) @@ -294,7 +370,7 @@ def _function_call_expression_parser(index, tokens): return True, index, FurFunctionCallExpression(function=function, arguments=arguments) -_expression_parser = _addition_level_expression_parser +_expression_parser = _equality_level_expression_parser def _assignment_statement_parser(index, tokens): # TODO Use a FurSymbolExpression for the target? Maybe this is actually not a good idea diff --git a/templates/program.c b/templates/program.c index c9c7394..650c1e8 100644 --- a/templates/program.c +++ b/templates/program.c @@ -264,6 +264,60 @@ Object builtin$modularDivide(Object left, Object right) return result; } +Object builtin$equals(Object left, Object right) +{ + assert(left.type == INTEGER); + assert(right.type == INTEGER); + + Object result = { BOOLEAN, left.instance.integer == right.instance.integer }; + return result; +} + +Object builtin$notEquals(Object left, Object right) +{ + assert(left.type == INTEGER); + assert(right.type == INTEGER); + + Object result = { BOOLEAN, left.instance.integer != right.instance.integer }; + return result; +} + +Object builtin$greaterThan(Object left, Object right) +{ + assert(left.type == INTEGER); + assert(right.type == INTEGER); + + Object result = { BOOLEAN, left.instance.integer > right.instance.integer }; + return result; +} + +Object builtin$lessThan(Object left, Object right) +{ + assert(left.type == INTEGER); + assert(right.type == INTEGER); + + Object result = { BOOLEAN, left.instance.integer < right.instance.integer }; + return result; +} + +Object builtin$greaterThanOrEqual(Object left, Object right) +{ + assert(left.type == INTEGER); + assert(right.type == INTEGER); + + Object result = { BOOLEAN, left.instance.integer >= right.instance.integer }; + return result; +} + +Object builtin$lessThanOrEqual(Object left, Object right) +{ + assert(left.type == INTEGER); + assert(right.type == INTEGER); + + Object result = { BOOLEAN, left.instance.integer <= right.instance.integer }; + return result; +} + {% if 'pow' in builtins %} Object builtin$pow(Object base, Object exponent) { diff --git a/tokenization.py b/tokenization.py index e9f536b..e6cad0a 100644 --- a/tokenization.py +++ b/tokenization.py @@ -36,12 +36,13 @@ _TOKEN_MATCHERS = [ ('open_parenthese', r'\('), ('close_parenthese', r'\)'), ('comma', r','), - ('assignment_operator', r'='), ('integer_literal', r'\d+'), ('symbol', r'[a-z]+'), ('single_quoted_string_literal', r"'.*?'"), + ('equality_level_operator', r'(<=|>=|==|!=|<|>)'), ('addition_level_operator', r'(\+|-)'), - ('multiplication_level_operator', r'(\*|//|%)'), + ('multiplication_level_operator', r'(\*|//|%)'), + ('assignment_operator', r'='), ] _TOKEN_MATCHERS = list(map(_make_token_matcher, _TOKEN_MATCHERS)) @@ -197,6 +198,72 @@ if __name__ == '__main__': ),), ) + def test_tokenizes_equality_operator(self): + self.assertEqual( + tokenize('=='), + (Token( + type='equality_level_operator', + match='==', + index=0, + line=1, + ),), + ) + + def test_tokenizes_greater_than_or_equal_operator(self): + self.assertEqual( + tokenize('>='), + (Token( + type='equality_level_operator', + match='>=', + index=0, + line=1, + ),), + ) + + def test_tokenizes_less_than_or_equal_operator(self): + self.assertEqual( + tokenize('<='), + (Token( + type='equality_level_operator', + match='<=', + index=0, + line=1, + ),), + ) + + def test_tokenizes_greater_than_equal_operator(self): + self.assertEqual( + tokenize('>'), + (Token( + type='equality_level_operator', + match='>', + index=0, + line=1, + ),), + ) + + def test_tokenizes_less_than_equal_operator(self): + self.assertEqual( + tokenize('<'), + (Token( + type='equality_level_operator', + match='<', + index=0, + line=1, + ),), + ) + + def test_tokenizes_not_equal_operator(self): + self.assertEqual( + tokenize('!='), + (Token( + type='equality_level_operator', + match='!=', + index=0, + line=1, + ),), + ) + def test_handles_trailing_newline(self): self.assertEqual( tokenize('print\n'), diff --git a/transformation.py b/transformation.py index b038b5d..cd9d18d 100644 --- a/transformation.py +++ b/transformation.py @@ -70,6 +70,63 @@ CIntegerDivisionExpression = collections.namedtuple( ], ) +CEqualityExpression = collections.namedtuple( + 'CEqualityExpression', + [ + 'left', + 'right', + ], +) + +CInequalityExpression = collections.namedtuple( + 'CInequalityExpression', + [ + 'left', + 'right', + ], +) + +CGreaterThanOrEqualExpression = collections.namedtuple( + 'CGreaterThanOrEqualExpression', + [ + 'left', + 'right', + ], +) + +CLessThanOrEqualExpression = collections.namedtuple( + 'CLessThanOrEqualExpression', + [ + 'left', + 'right', + ], +) + +CGreaterThanExpression = collections.namedtuple( + 'CGreaterThanExpression', + [ + 'left', + 'right', + ], +) + +CLessThanExpression = collections.namedtuple( + 'CLessThanExpression', + [ + 'left', + 'right', + ], +) + +CAndExpression = collections.namedtuple( + 'CAndExpression', + [ + 'left', + 'right', + ], +) + + CModularDivisionExpression = collections.namedtuple( 'CModularDivisionExpression', [ @@ -105,6 +162,46 @@ CProgram = collections.namedtuple( ], ) +EQUALITY_LEVEL_TYPE_MAPPING = { + parsing.FurEqualityExpression: CEqualityExpression, + parsing.FurInequalityExpression: CInequalityExpression, + parsing.FurLessThanOrEqualExpression: CLessThanOrEqualExpression, + parsing.FurGreaterThanOrEqualExpression: CGreaterThanOrEqualExpression, + parsing.FurLessThanExpression: CLessThanExpression, + parsing.FurGreaterThanExpression: CGreaterThanExpression, +} + +def transform_equality_level_expression(builtin_dependencies, symbol_list, expression): + # Transform expressions like 1 < 2 < 3 into expressions like 1 < 2 && 2 < 3 + if type(expression.left) in EQUALITY_LEVEL_TYPE_MAPPING: + left = transform_equality_level_expression( + builtin_dependencies, + symbol_list, + expression.left + ) + + middle = left.right + + right = transform_expression( + builtin_dependencies, + symbol_list, + expression.right, + ) + + # TODO Don't evaluate the middle expression twice + return CAndExpression( + left=left, + right=EQUALITY_LEVEL_TYPE_MAPPING[type(expression)]( + left=middle, + right=right, + ), + ) + + return EQUALITY_LEVEL_TYPE_MAPPING[type(expression)]( + left=transform_expression(builtin_dependencies, symbol_list, expression.left), + right=transform_expression(builtin_dependencies, symbol_list, expression.right), + ) + BUILTINS = { 'false': [], 'pow': ['math.h'], @@ -143,6 +240,9 @@ def transform_expression(builtin_dependencies, symbol_list, expression): if type(expression) in LITERAL_TYPE_MAPPING: return LITERAL_TYPE_MAPPING[type(expression)](value=expression.value) + if type(expression) in EQUALITY_LEVEL_TYPE_MAPPING: + return transform_equality_level_expression(builtin_dependencies, symbol_list, expression) + INFIX_TYPE_MAPPING = { parsing.FurAdditionExpression: CAdditionExpression, parsing.FurSubtractionExpression: CSubtractionExpression, -- 2.20.1