From fd918259dd949c8fababcf49ced426ab3c39da38 Mon Sep 17 00:00:00 2001 From: David Kerkeslager Date: Fri, 4 Aug 2017 19:01:08 -0400 Subject: [PATCH] Add basic math --- examples/04_math.fur | 9 +++ examples/04_math.fur.output.txt | 5 ++ generation.py | 21 +++++- parsing.py | 121 ++++++++++++++++++++++++++++---- templates/program.c | 56 +++++++++++++++ tokenization.py | 100 ++++++++++++++++++++++---- transformation.py | 70 ++++++++++++++++-- 7 files changed, 346 insertions(+), 36 deletions(-) create mode 100644 examples/04_math.fur create mode 100644 examples/04_math.fur.output.txt diff --git a/examples/04_math.fur b/examples/04_math.fur new file mode 100644 index 0000000..5a1c43e --- /dev/null +++ b/examples/04_math.fur @@ -0,0 +1,9 @@ +print(1 + 2) +print('\n') +print(6 - 2) +print('\n') +print(2 * 3) +print('\n') +print(17 // 2) +print('\n') +print(17 % 2) diff --git a/examples/04_math.fur.output.txt b/examples/04_math.fur.output.txt new file mode 100644 index 0000000..f79bf6b --- /dev/null +++ b/examples/04_math.fur.output.txt @@ -0,0 +1,5 @@ +3 +4 +6 +8 +1 \ No newline at end of file diff --git a/generation.py b/generation.py index 56bd0a5..b51650b 100644 --- a/generation.py +++ b/generation.py @@ -24,10 +24,27 @@ def generate_string_literal(c_string_literal): ) def generate_argument(c_argument): - return { + LITERAL_TYPE_MAPPING = { transformation.CIntegerLiteral: generate_integer_literal, transformation.CStringLiteral: generate_string_literal, - }[type(c_argument)](c_argument) + } + + if type(c_argument) in LITERAL_TYPE_MAPPING: + return LITERAL_TYPE_MAPPING[type(c_argument)](c_argument) + + INFIX_TYPE_MAPPING = { + transformation.CAdditionExpression: 'add', + transformation.CSubtractionExpression: 'subtract', + transformation.CMultiplicationExpression: 'multiply', + transformation.CIntegerDivisionExpression: 'integerDivide', + transformation.CModularDivisionExpression: 'modularDivide', + } + + return 'builtin${}({}, {})'.format( + INFIX_TYPE_MAPPING[type(c_argument)], + generate_argument(c_argument.left), + generate_argument(c_argument.right), + ) def generate_statement(c_function_call_statement): return '{}({});'.format( diff --git a/parsing.py b/parsing.py index 03a1744..e8f9068 100644 --- a/parsing.py +++ b/parsing.py @@ -30,21 +30,61 @@ def _zero_or_more_parser(formatter, parser): return result_parser -IntegerLiteral = collections.namedtuple( - 'IntegerLiteral', +FurIntegerLiteralExpression = collections.namedtuple( + 'FurIntegerLiteralExpression', [ 'value', ], ) -StringLiteral = collections.namedtuple( - 'StringLiteral', +FurStringLiteralExpression = collections.namedtuple( + 'FurStringLiteralExpression', [ 'value', ], ) -def _integer_literal_parser(index, tokens): +FurAdditionExpression = collections.namedtuple( + 'FurAdditionExpression', + [ + 'left', + 'right', + ], +) + +FurSubtractionExpression = collections.namedtuple( + 'FurSubtractionExpression', + [ + 'left', + 'right', + ], +) + +FurMultiplicationExpression = collections.namedtuple( + 'FurMultiplicationExpression', + [ + 'left', + 'right', + ], +) + +FurIntegerDivisionExpression = collections.namedtuple( + 'FurIntegerDivisionExpression', + [ + 'left', + 'right', + ], +) + +FurModularDivisionExpression = collections.namedtuple( + 'FurModularDivisionExpression', + [ + 'left', + 'right', + ], +) + +def _integer_literal_expression_parser(index, tokens): failure = (False, index, None) if tokens[index].type != 'integer_literal': @@ -52,9 +92,9 @@ def _integer_literal_parser(index, tokens): value = int(tokens[index].match) index += 1 - return True, index, IntegerLiteral(value=value) + return True, index, FurIntegerLiteralExpression(value=value) -def _string_literal_parser(index, tokens): +def _string_literal_expression_parser(index, tokens): failure = (False, index, None) if tokens[index].type != 'single_quoted_string_literal': @@ -62,9 +102,60 @@ def _string_literal_parser(index, tokens): value = tokens[index].match[1:-1] index += 1 - return True, index, StringLiteral(value=value) + return True, index, FurStringLiteralExpression(value=value) -_argument_parser = _or_parser(_integer_literal_parser, _string_literal_parser) +def _literal_level_expression_parser(index, tokens): + return _or_parser( + _integer_literal_expression_parser, + _string_literal_expression_parser, + )(index, tokens) + +def _multiplication_level_expression_parser(index, tokens): + failure = (False, index, None) + + success, index, result = _literal_level_expression_parser(index, tokens) + + if not success: + return failure + + while success and index < len(tokens) and tokens[index].type == 'multiplication_level_operator': + success = False + + if index + 1 < len(tokens): + success, try_index, value = _literal_level_expression_parser(index + 1, tokens) + + if success: + result = { + '*': FurMultiplicationExpression, + '//': FurIntegerDivisionExpression, + '%': FurModularDivisionExpression, + }[tokens[index].match](left=result, right=value) + index = try_index + + return True, index, result + +def _addition_level_expression_parser(index, tokens): + failure = (False, index, None) + + success, index, result = _multiplication_level_expression_parser(index, tokens) + + if not success: + return failure + + while success and index < len(tokens) and tokens[index].type == 'addition_level_operator': + success = False + + if index + 1 < len(tokens): + success, try_index, value = _multiplication_level_expression_parser(index + 1, tokens) + + if success: + result = { + '+': FurAdditionExpression, + '-': FurSubtractionExpression, + }[tokens[index].match](left=result, right=value) + index = try_index + + return True, index, result FunctionCall = collections.namedtuple( 'FunctionCall', @@ -93,7 +184,7 @@ def _function_call_parser(index, tokens): return failure index += 1 - success, index, argument = _argument_parser(index, tokens) + success, index, argument = _addition_level_expression_parser(index, tokens) if not success: return failure @@ -101,7 +192,7 @@ def _function_call_parser(index, tokens): if tokens[index].type != 'close_parenthese': return failure index += 1 - + return True, index, FunctionCall(name=name, arguments=(argument,)) def _program_formatter(statement_list): @@ -129,14 +220,14 @@ if __name__ == '__main__': import tokenization - class StringLiteralParserTests(unittest.TestCase): + class FurStringLiteralExpressionParserTests(unittest.TestCase): def test_parses_single_quoted_string_literal(self): self.assertEqual( - _string_literal_parser(0, tokenization.tokenize("'Hello, world'")), + _string_literal_expression_parser(0, tokenization.tokenize("'Hello, world'")), ( True, 1, - StringLiteral(value='Hello, world'), + FurStringLiteralExpression(value='Hello, world'), ), ) @@ -149,7 +240,7 @@ if __name__ == '__main__': 4, FunctionCall( name='print', - arguments=(StringLiteral(value='Hello, world'),), + arguments=(FurStringLiteralExpression(value='Hello, world'),), ), ), ) diff --git a/templates/program.c b/templates/program.c index ecabb17..274aa33 100644 --- a/templates/program.c +++ b/templates/program.c @@ -113,6 +113,62 @@ Object stringLiteral(Runtime* runtime, const char* literal) return result; } +// TODO Make this conditionally added +Object builtin$add(Object left, Object right) +{ + assert(left.type == INTEGER); + assert(right.type == INTEGER); + + Object result; + result.type = INTEGER; + result.instance.integer = left.instance.integer + right.instance.integer; + return result; +} + +Object builtin$subtract(Object left, Object right) +{ + assert(left.type == INTEGER); + assert(right.type == INTEGER); + + Object result; + result.type = INTEGER; + result.instance.integer = left.instance.integer - right.instance.integer; + return result; +} + +Object builtin$multiply(Object left, Object right) +{ + assert(left.type == INTEGER); + assert(right.type == INTEGER); + + Object result; + result.type = INTEGER; + result.instance.integer = left.instance.integer * right.instance.integer; + return result; +} + +Object builtin$integerDivide(Object left, Object right) +{ + assert(left.type == INTEGER); + assert(right.type == INTEGER); + + Object result; + result.type = INTEGER; + result.instance.integer = left.instance.integer / right.instance.integer; + return result; +} + +Object builtin$modularDivide(Object left, Object right) +{ + assert(left.type == INTEGER); + assert(right.type == INTEGER); + + Object result; + result.type = INTEGER; + result.instance.integer = left.instance.integer % right.instance.integer; + return result; +} + {% if 'print' in builtins %} void builtin$print(Object output) { diff --git a/tokenization.py b/tokenization.py index 7733ab7..0421b84 100644 --- a/tokenization.py +++ b/tokenization.py @@ -8,6 +8,7 @@ Token = collections.namedtuple( [ 'type', 'match', + 'index', ], ) @@ -21,7 +22,11 @@ def _make_token_matcher(definition): if match is None: return False, index, None - return True, index + len(match.group()), Token(type=name, match=match.group()) + return ( + True, + index + len(match.group()), + Token(type=name, match=match.group(), index=index), + ) return token_matcher @@ -29,9 +34,11 @@ def _make_token_matcher(definition): _TOKEN_MATCHERS = [ ('open_parenthese', r'\('), ('close_parenthese', r'\)'), - ('integer_literal', r'-?\s*\d+'), + ('integer_literal', r'\d+'), ('symbol', r'[a-z]+'), ('single_quoted_string_literal', r"'.*?'"), + ('addition_level_operator', r'(\+|-)'), + ('multiplication_level_operator', r'(\*|//|%)'), ] _TOKEN_MATCHERS = list(map(_make_token_matcher, _TOKEN_MATCHERS)) @@ -41,6 +48,10 @@ def tokenize(source): index = 0 while index < len(source): + if source[index] == ' ': + index += 1 + continue + success = False for matcher in _TOKEN_MATCHERS: @@ -63,46 +74,111 @@ if __name__ == '__main__': def test_tokenizes_open_parenthese(self): self.assertEqual( tokenize('('), - [Token( + (Token( type='open_parenthese', match='(', - )], + index=0, + ),), ) def test_tokenizes_close_parenthese(self): self.assertEqual( tokenize(')'), - [Token( + (Token( type='close_parenthese', match=')', - )], + index=0, + ),), ) def test_tokenizes_symbol(self): self.assertEqual( tokenize('print'), - [Token( + (Token( type='symbol', match='print', - )], + index=0, + ),), ) def test_tokenizes_single_quoted_string_literal(self): self.assertEqual( tokenize("'Hello, world'"), - [Token( + (Token( type='single_quoted_string_literal', match="'Hello, world'", - )], + index=0, + ),), + ) + + def test_tokenizes_plus(self): + self.assertEqual( + tokenize('+'), + (Token( + type='addition_level_operator', + match='+', + index=0, + ),), + ) + + def test_tokenizes_minus(self): + self.assertEqual( + tokenize('-'), + (Token( + type='addition_level_operator', + match='-', + index=0, + ),), + ) + + def test_tokenizes_times(self): + self.assertEqual( + tokenize('*'), + (Token( + type='multiplication_level_operator', + match='*', + index=0, + ),), + ) + + def test_tokenizes_integer_divide(self): + self.assertEqual( + tokenize('//'), + (Token( + type='multiplication_level_operator', + match='//', + index=0, + ),), + ) + + def test_tokenizes_modular_divide(self): + self.assertEqual( + tokenize('%'), + (Token( + type='multiplication_level_operator', + match='%', + index=0, + ),), ) def test_handles_trailing_newline(self): self.assertEqual( tokenize('print\n'), - [Token( + (Token( + type='symbol', + match='print', + index=0, + ),), + ) + + def test_handles_leading_space(self): + self.assertEqual( + tokenize(' print'), + (Token( type='symbol', match='print', - )], + index=1, + ),), ) unittest.main() diff --git a/transformation.py b/transformation.py index f2bd2a7..cdf8155 100644 --- a/transformation.py +++ b/transformation.py @@ -16,6 +16,46 @@ CStringLiteral = collections.namedtuple( ], ) +CAdditionExpression = collections.namedtuple( + 'CAdditionExpression', + [ + 'left', + 'right', + ], +) + +CSubtractionExpression = collections.namedtuple( + 'CSubtractionExpression', + [ + 'left', + 'right', + ], +) + +CMultiplicationExpression = collections.namedtuple( + 'CMultiplicationExpression', + [ + 'left', + 'right', + ], +) + +CIntegerDivisionExpression = collections.namedtuple( + 'CIntegerDivisionExpression', + [ + 'left', + 'right', + ], +) + +CModularDivisionExpression = collections.namedtuple( + 'CModularDivisionExpression', + [ + 'left', + 'right', + ], +) + CFunctionCallStatement = collections.namedtuple( 'CFunctionCallStatement', [ @@ -37,11 +77,28 @@ BUILTINS = { 'print': ['stdio.h.'], } -def transform_argument(builtin_dependencies, argument): - return { - parsing.IntegerLiteral: CIntegerLiteral, - parsing.StringLiteral: CStringLiteral, - }[type(argument)](value=argument.value) +def transform_expression(builtin_dependencies, expression): + + LITERAL_TYPE_MAPPING = { + parsing.FurIntegerLiteralExpression: CIntegerLiteral, + parsing.FurStringLiteralExpression: CStringLiteral, + } + + if type(expression) in LITERAL_TYPE_MAPPING: + return LITERAL_TYPE_MAPPING[type(expression)](value=expression.value) + + INFIX_TYPE_MAPPING = { + parsing.FurAdditionExpression: CAdditionExpression, + parsing.FurSubtractionExpression: CSubtractionExpression, + parsing.FurMultiplicationExpression: CMultiplicationExpression, + parsing.FurIntegerDivisionExpression: CIntegerDivisionExpression, + parsing.FurModularDivisionExpression: CModularDivisionExpression, + } + + return INFIX_TYPE_MAPPING[type(expression)]( + left=transform_expression(builtin_dependencies, expression.left), + right=transform_expression(builtin_dependencies, expression.right), + ) def transform_function_call_statement(builtin_dependencies, function_call): if function_call.name in BUILTINS.keys(): @@ -49,12 +106,11 @@ def transform_function_call_statement(builtin_dependencies, function_call): return CFunctionCallStatement( name='builtin$' + function_call.name, - arguments=tuple(transform_argument(builtin_dependencies, arg) for arg in function_call.arguments), + arguments=tuple(transform_expression(builtin_dependencies, arg) for arg in function_call.arguments), ) raise Exception() - def transform(program): builtins = set() -- 2.20.1