From 3297817843cd6bd087505a70d8e108f1baa35cff Mon Sep 17 00:00:00 2001 From: David Kerkeslager Date: Fri, 18 Aug 2017 18:06:15 -0400 Subject: [PATCH] Added list literals --- examples/26_list_literals.fur | 7 ++ examples/26_list_literals.fur.output.txt | 2 + generation.py | 49 +++++++------ normalization.py | 82 +++++++++++++++++++++- parsing.py | 89 ++++++++++++++++++++++-- templates/program.c | 61 ++++++++++++++++ tokenization.py | 4 +- transformation.py | 49 +++++++++++-- 8 files changed, 309 insertions(+), 34 deletions(-) create mode 100644 examples/26_list_literals.fur create mode 100644 examples/26_list_literals.fur.output.txt diff --git a/examples/26_list_literals.fur b/examples/26_list_literals.fur new file mode 100644 index 0000000..4557356 --- /dev/null +++ b/examples/26_list_literals.fur @@ -0,0 +1,7 @@ +greetings = [ + 'Hello, world', + 'Goodnight, moon', +] + +print(greetings[0], '\n') +print(greetings[1], '\n') diff --git a/examples/26_list_literals.fur.output.txt b/examples/26_list_literals.fur.output.txt new file mode 100644 index 0000000..f48e806 --- /dev/null +++ b/examples/26_list_literals.fur.output.txt @@ -0,0 +1,2 @@ +Hello, world +Goodnight, moon diff --git a/generation.py b/generation.py index 4fe8de4..b060376 100644 --- a/generation.py +++ b/generation.py @@ -23,30 +23,32 @@ def generate_symbol_expression(symbol_expression): def generate_variable_expression(expression): return expression.variable -def generate_expression(expression): - if isinstance(expression, transformation.CNegationExpression): - return generate_negation_expression(expression) +def generate_function_call_for_fur_infix_operator(expression): + return 'operator${}({}, {})'.format( + expression.name, + generate_expression(expression.left), + generate_expression(expression.right), + ) - if isinstance(expression, transformation.CFunctionCallExpression): - return generate_function_call(expression) +def generate_list_construct_expression(expression): + return 'List_construct({})'.format(expression.allocate) + +def generate_list_get_expression(expression): + return 'List_get(&{}, {})'.format( + generate_expression(expression.list_expression), + generate_expression(expression.index_expression), + ) - LITERAL_TYPE_MAPPING = { +def generate_expression(expression): + return { + transformation.CFunctionCallExpression: generate_function_call, + transformation.CFunctionCallForFurInfixOperator: generate_function_call_for_fur_infix_operator, transformation.CIntegerLiteral: generate_integer_literal, + transformation.CListConstructExpression: generate_list_construct_expression, + transformation.CListGetExpression: generate_list_get_expression, + transformation.CNegationExpression: generate_negation_expression, transformation.CStringLiteral: generate_string_literal, transformation.CSymbolExpression: generate_symbol_expression, - } - - if type(expression) in LITERAL_TYPE_MAPPING: - return LITERAL_TYPE_MAPPING[type(expression)](expression) - - if isinstance(expression, transformation.CFunctionCallForFurInfixOperator): - return 'operator${}({}, {})'.format( - expression.name, - generate_expression(expression.left), - generate_expression(expression.right), - ) - - return { transformation.CVariableExpression: generate_variable_expression, }[type(expression)](expression) @@ -137,13 +139,20 @@ def generate_if_else_statement(statement): def generate_function_declaration(statement): return 'Environment_set(environment, "{}", (Object){{ CLOSURE, (Instance)(Closure){{ environment, user${}$implementation }} }});'.format(statement.name, statement.name) +def generate_list_append_statement(statement): + return 'List_append(&{}, {});'.format( + generate_expression(statement.list_expression), + generate_expression(statement.item_expression), + ) + def generate_statement(statement): return { + transformation.CArrayVariableInitializationStatement: generate_array_variable_initialization_statement, transformation.CExpressionStatement: generate_expression_statement, transformation.CFunctionDeclaration: generate_function_declaration, transformation.CIfElseStatement: generate_if_else_statement, + transformation.CListAppendStatement: generate_list_append_statement, transformation.CSymbolAssignmentStatement: generate_symbol_assignment_statement, - transformation.CArrayVariableInitializationStatement: generate_array_variable_initialization_statement, transformation.CVariableInitializationStatement: generate_variable_initialization_statement, transformation.CVariableReassignmentStatement: generate_variable_reassignment_statement, }[type(statement)](statement) diff --git a/normalization.py b/normalization.py index c96e455..ca6f57f 100644 --- a/normalization.py +++ b/normalization.py @@ -137,6 +137,83 @@ def normalize_integer_literal_expression(counter, expression): NormalVariableExpression(variable=variable), ) +NormalListConstructExpression = collections.namedtuple( + 'NormalListConstructExpression', + [ + 'allocate', + ], +) + +NormalListAppendStatement = collections.namedtuple( + 'NormalListAppendStatement', + [ + 'list_expression', + 'item_expression', + ], +) + +NormalListGetExpression = collections.namedtuple( + 'NormalListGetExpression', + [ + 'list_expression', + 'index_expression', + ], +) + +def normalize_list_literal_expression(counter, expression): + list_variable = '${}'.format(counter) + counter += 1 + + prestatements = [ + NormalVariableInitializationStatement( + variable=list_variable, + expression=NormalListConstructExpression(allocate=len(expression.item_expression_list)), + ), + ] + + list_expression = NormalVariableExpression(variable=list_variable) + + for item_expression in expression.item_expression_list: + counter, item_expression_prestatements, normalized = normalize_expression( + counter, + item_expression, + ) + + for p in item_expression_prestatements: + prestatements.append(p) + + prestatements.append( + NormalListAppendStatement( + list_expression=list_expression, + item_expression=normalized, + ) + ) + + return ( + counter, + tuple(prestatements), + list_expression, + ) + +def normalize_list_item_expression(counter, expression): + counter, list_prestatements, list_expression = normalize_expression(counter, expression.list_expression) + counter, index_prestatements, index_expression = normalize_expression(counter, expression.index_expression) + + result_variable = '${}'.format(counter) + result_prestatement = NormalVariableInitializationStatement( + variable=result_variable, + expression=NormalListGetExpression( + list_expression=list_expression, + index_expression=index_expression, + ), + ) + + return ( + counter + 1, + list_prestatements + index_prestatements + (result_prestatement,), + NormalVariableExpression(variable=result_variable), + ) + def normalize_string_literal_expression(counter, expression): variable = '${}'.format(counter) return ( @@ -408,9 +485,6 @@ def normalize_if_expression(counter, expression): NormalVariableExpression(variable=result_variable), ) - - - def normalize_negation_expression(counter, expression): counter, prestatements, internal_expression = normalize_expression(counter, expression.value) @@ -436,6 +510,8 @@ def normalize_expression(counter, expression): parsing.FurIfExpression: normalize_if_expression, parsing.FurInfixExpression: normalize_infix_expression, parsing.FurIntegerLiteralExpression: normalize_integer_literal_expression, + parsing.FurListLiteralExpression: normalize_list_literal_expression, + parsing.FurListItemExpression: normalize_list_item_expression, parsing.FurNegationExpression: normalize_negation_expression, parsing.FurStringLiteralExpression: normalize_string_literal_expression, parsing.FurSymbolExpression: normalize_symbol_expression, diff --git a/parsing.py b/parsing.py index f2198ad..45964d7 100644 --- a/parsing.py +++ b/parsing.py @@ -74,6 +74,13 @@ FurInfixExpression = collections.namedtuple( ], ) +FurListLiteralExpression = collections.namedtuple( + 'FurListLiteralExpression', + [ + 'item_expression_list', + ], +) + FurIfExpression = collections.namedtuple( 'FurIfExpression', [ @@ -105,11 +112,11 @@ def _symbol_expression_parser(index, tokens): return (False, index, None) -def _parenthese_wrapped_parser(internal_parser): +def _wrapped_parser(open_token, close_token, internal_parser): def result_parser(index, tokens): failure = (False, index, None) - if tokens[index].type == 'open_parenthese': + if tokens[index].type == open_token: index += 1 else: return failure @@ -118,10 +125,11 @@ def _parenthese_wrapped_parser(internal_parser): if not success: return failure - if tokens[index].type == 'close_parenthese': + if tokens[index].type == close_token: index += 1 else: - raise Exception('Expected ")" on line {}, found "{}"'.format( + # TODO Put the actual expected character in the error message + raise Exception('Expected closing token on line {}, found "{}"'.format( tokens[index].line, tokens[index].match, )) @@ -130,9 +138,27 @@ def _parenthese_wrapped_parser(internal_parser): return result_parser +def _bracket_wrapped_parser(internal_parser): + return _wrapped_parser('open_bracket', 'close_bracket', internal_parser) + +def _parenthese_wrapped_parser(internal_parser): + return _wrapped_parser('open_parenthese', 'close_parenthese', internal_parser) + def _parenthesized_expression_parser(index, tokens): return _parenthese_wrapped_parser(_expression_parser)(index, tokens) +def _list_literal_expression_parser(index, tokens): + failure = (False, index, None) + + success, index, item_expression_list = _bracket_wrapped_parser(_comma_separated_expression_list_parser)(index, tokens) + + if success: + return success, index, FurListLiteralExpression( + item_expression_list=item_expression_list, + ) + else: + return failure + def _negation_expression_parser(index, tokens): failure = (False, index, None) @@ -149,10 +175,12 @@ def _negation_expression_parser(index, tokens): def _literal_level_expression_parser(index, tokens): return _or_parser( _negation_expression_parser, + _list_item_expression_parser, _function_call_expression_parser, _parenthesized_expression_parser, _integer_literal_expression_parser, _string_literal_expression_parser, + _list_literal_expression_parser, _symbol_expression_parser, )(index, tokens) @@ -225,6 +253,8 @@ def _comma_separated_list_parser(subparser): items = [] + _, index, _ = consume_newlines(index, tokens) + success, index, item = subparser(index, tokens) if success: @@ -233,10 +263,13 @@ def _comma_separated_list_parser(subparser): return (True, start_index, ()) while success and index < len(tokens) and tokens[index].type == 'comma': + index += 1 success = False - if index + 1 < len(tokens): - success, try_index, item = subparser(index + 1, tokens) + _, index, _ = consume_newlines(index, tokens) + + if index < len(tokens): + success, try_index, item = subparser(index, tokens) if success: items.append(item) @@ -249,6 +282,14 @@ def _comma_separated_list_parser(subparser): def _comma_separated_expression_list_parser(index, tokens): return _comma_separated_list_parser(_expression_parser)(index, tokens) +FurListItemExpression = collections.namedtuple( + 'FurListItemExpression', + [ + 'list_expression', + 'index_expression', + ], +) + FurFunctionCallExpression = collections.namedtuple( 'FurFunctionCallExpression', [ @@ -288,6 +329,42 @@ FurProgram = collections.namedtuple( ], ) +def _list_item_expression_parser(index, tokens): + failure = (False, index, None) + + # We have to be careful what expressions we add here. Otherwise expressions + # like "a + b[0]" become ambiguous to the parser. + success, index, list_expression = _or_parser( + _symbol_expression_parser, + _parenthesized_expression_parser, + )(index, tokens) + + if not success: + return failure + + success, index, index_expression = _bracket_wrapped_parser(_expression_parser)( + index, + tokens, + ) + + if not success: + return failure + + while success and index < len(tokens): + # "list_expression" is actually the full list item expression if the next parse attempt doesn't succeed + # We can't give this a better name without a bunch of checks, however. + list_expression = FurListItemExpression( + list_expression=list_expression, + index_expression=index_expression, + ) + + success, index, index_expression = _bracket_wrapped_parser(_expression_parser)( + index, + tokens, + ) + + return True, index, list_expression + def _function_call_expression_parser(index, tokens): failure = (False, index, None) diff --git a/templates/program.c b/templates/program.c index 4ac6289..1766967 100644 --- a/templates/program.c +++ b/templates/program.c @@ -52,6 +52,7 @@ enum Type BOOLEAN, CLOSURE, INTEGER, + LIST, STRING, VOID }; @@ -64,11 +65,21 @@ struct Closure Object (*call)(EnvironmentPool*, Environment*, size_t, Object*); }; +struct List; +typedef struct List List; +struct List +{ + size_t allocated; + size_t length; + Object* items; +}; + union Instance { bool boolean; Closure closure; int32_t integer; + List list; const char* string; }; @@ -82,6 +93,38 @@ const Object builtin$true = { BOOLEAN, (Instance)(bool){ true } }; const Object builtin$false = { BOOLEAN, (Instance)(bool){ false } }; const Object builtin$nil = { VOID, { 0 } }; +Object List_construct(size_t allocate) +{ + Object* items = malloc(sizeof(Object) * allocate); + Object result = { LIST, (Instance)(List){ allocate, 0, items } }; + return result; +} + +void List_append(Object* list, Object item) +{ + assert(list->type == LIST); + + if(list->instance.list.allocated == list->instance.list.length) + { + list->instance.list.allocated *= 2; + list->instance.list.items = realloc( + list->instance.list.items, + sizeof(Object) * list->instance.list.allocated + ); + } + + list->instance.list.items[list->instance.list.length] = item; + list->instance.list.length++; +} + +Object List_get(Object* list, Object index) +{ + assert(list->type == LIST); + assert(index.type == INTEGER); + + return list->instance.list.items[index.instance.integer]; +} + struct EnvironmentNode { const char* key; @@ -114,6 +157,24 @@ void Environment_deinitialize(Environment* self) for(EnvironmentNode* node = self->root; node != NULL; node = next) { next = node->next; + + switch(node->value.type) + { + case BOOLEAN: + case CLOSURE: + case INTEGER: + case STRING: + case VOID: + break; + + case LIST: + free(node->value.instance.list.items); + break; + + default: + assert(false); + } + free(node); } } diff --git a/tokenization.py b/tokenization.py index f73ddf8..e12b8ec 100644 --- a/tokenization.py +++ b/tokenization.py @@ -33,13 +33,15 @@ def _make_token_matcher(definition): _TOKEN_MATCHERS = [ ('keyword', r'(def|do|else|end|if)(?![a-z_])'), + ('open_bracket', r'\['), + ('close_bracket', r'\]'), ('open_parenthese', r'\('), ('close_parenthese', r'\)'), ('comma', r','), ('integer_literal', r'\d+'), ('symbol', r'[a-z_]+'), ('single_quoted_string_literal', r"'.*?'"), - ('comparison_level_operator', r'(<=|>=|==|!=|<|>)'), + ('comparison_level_operator', r'(<=|>=|==|!=|<|>)'), ('assignment_operator', r'='), ('addition_level_operator', r'(\+|-)'), ('multiplication_level_operator', r'(\*|//|%)'), diff --git a/transformation.py b/transformation.py index 0b58907..51b0244 100644 --- a/transformation.py +++ b/transformation.py @@ -140,10 +140,10 @@ CProgram = collections.namedtuple( ) BUILTINS = { - 'false': [], - 'pow': ['math.h'], - 'print': ['stdio.h'], - 'true': [], + 'false': [], + 'pow': ['math.h'], + 'print': ['stdio.h'], + 'true': [], } def transform_variable_expression(accumulators, expression): @@ -255,6 +255,44 @@ def transform_negation_expression(accumulators, expression): value=transform_expression(accumulators, expression.internal_expression), ) +CListConstructExpression = collections.namedtuple( + 'CListConstructExpression', + [ + 'allocate', + ], +) + +CListAppendStatement = collections.namedtuple( + 'CListAppendStatement', + [ + 'list_expression', + 'item_expression', + ], +) + +CListGetExpression = collections.namedtuple( + 'CListGetExpression', + [ + 'list_expression', + 'index_expression', + ], +) + +def transform_list_construct_expression(accumulators, expression): + return CListConstructExpression(allocate=expression.allocate) + +def transform_list_get_expression(accumulators, expression): + return CListGetExpression( + list_expression=transform_expression(accumulators, expression.list_expression), + index_expression=transform_expression(accumulators, expression.index_expression), + ) + +def transform_list_append_statement(accumulators, expression): + return CListAppendStatement( + list_expression=transform_expression(accumulators, expression.list_expression), + item_expression=transform_expression(accumulators, expression.item_expression), + ) + def transform_expression(accumulators, expression): # TODO Clean up handlers for parsing expressions return { @@ -265,6 +303,8 @@ def transform_expression(accumulators, expression): normalization.NormalFunctionCallExpression: transform_function_call_expression, normalization.NormalInfixExpression: transform_infix_expression, normalization.NormalIntegerLiteralExpression: transform_integer_literal_expression, + normalization.NormalListConstructExpression: transform_list_construct_expression, + normalization.NormalListGetExpression: transform_list_get_expression, normalization.NormalNegationExpression: transform_negation_expression, normalization.NormalStringLiteralExpression: transform_string_literal_expression, normalization.NormalSymbolExpression: transform_symbol_expression, @@ -348,6 +388,7 @@ def transform_statement(accumulators, statement): normalization.NormalExpressionStatement: transform_expression_statement, normalization.NormalFunctionDefinitionStatement: transform_function_definition_statement, normalization.NormalIfElseStatement: transform_if_else_statement, + normalization.NormalListAppendStatement: transform_list_append_statement, normalization.NormalVariableInitializationStatement: transform_variable_initialization_statement, normalization.NormalVariableReassignmentStatement: transform_variable_reassignment_statement, }[type(statement)](accumulators, statement) -- 2.20.1