From 62bbcc8f9242c7f404db4756460a927b1ce90aec Mon Sep 17 00:00:00 2001 From: David Kerkeslager Date: Sat, 26 Aug 2017 16:00:35 -0400 Subject: [PATCH] Added structs --- examples/29_structures.fur | 7 ++ examples/29_structures.fur.output.txt | 2 + generation.py | 26 +++++++ normalization.py | 104 ++++++++++++++++++++++++++ parsing.py | 89 ++++++++++++++++++---- templates/program.c | 96 ++++++++++++++++++++++-- tokenization.py | 2 + transformation.py | 70 +++++++++++++++++ 8 files changed, 375 insertions(+), 21 deletions(-) create mode 100644 examples/29_structures.fur create mode 100644 examples/29_structures.fur.output.txt diff --git a/examples/29_structures.fur b/examples/29_structures.fur new file mode 100644 index 0000000..e8c7103 --- /dev/null +++ b/examples/29_structures.fur @@ -0,0 +1,7 @@ +expressions = ( + greeting: 'Hello', + farewell: 'Goodbye', +) + +print(expressions.greeting, '\n') +print(expressions.farewell, '\n') diff --git a/examples/29_structures.fur.output.txt b/examples/29_structures.fur.output.txt new file mode 100644 index 0000000..c86756d --- /dev/null +++ b/examples/29_structures.fur.output.txt @@ -0,0 +1,2 @@ +Hello +Goodbye diff --git a/generation.py b/generation.py index 99fd681..9757949 100644 --- a/generation.py +++ b/generation.py @@ -33,6 +33,20 @@ def generate_function_call_for_fur_infix_operator(expression): generate_expression(expression.right), ) +def generate_structure_literal_expression(expression): + return 'Structure_construct({}, {}, {})'.format( + expression.field_count, + expression.symbol_list_variable, + expression.value_list_variable, + ) + +def generate_dot_expression(expression): + return 'Structure_get(&{}, SYMBOL_LIST[{}] /* symbol: "{}" */)'.format( + generate_variable_expression(expression.instance), + expression.symbol_list_index, + expression.symbol, + ) + def generate_list_construct_expression(expression): return 'List_construct({})'.format(expression.allocate) @@ -44,6 +58,7 @@ def generate_list_get_expression(expression): def generate_expression(expression): return { + transformation.CDotExpression: generate_dot_expression, transformation.CFunctionCallExpression: generate_function_call, transformation.CFunctionCallForFurInfixOperator: generate_function_call_for_fur_infix_operator, transformation.CIntegerLiteral: generate_integer_literal, @@ -51,6 +66,7 @@ def generate_expression(expression): transformation.CListGetExpression: generate_list_get_expression, transformation.CNegationExpression: generate_negation_expression, transformation.CStringLiteral: generate_string_literal, + transformation.CStructureLiteralExpression: generate_structure_literal_expression, transformation.CSymbolExpression: generate_symbol_expression, transformation.CVariableExpression: generate_variable_expression, }[type(expression)](expression) @@ -90,6 +106,15 @@ def generate_array_variable_initialization_statement(statement): ', '.join(generate_expression(i) for i in statement.items), ) +def generate_symbol_array_variable_initialization_statement(statement): + return 'const char* {}[] = {{ {} }};'.format( + statement.variable, + ', '.join('SYMBOL_LIST[{}] /* symbol: "{}" */'.format( + statement.symbol_list_indices[i], + statement.symbol_list[i], + ) for i in range(len(statement.symbol_list))), + ) + def generate_variable_initialization_statement(statement): return 'Object {} = {};'.format( statement.variable, @@ -155,6 +180,7 @@ def generate_statement(statement): transformation.CIfElseStatement: generate_if_else_statement, transformation.CListAppendStatement: generate_list_append_statement, transformation.CSymbolAssignmentStatement: generate_symbol_assignment_statement, + transformation.CSymbolArrayVariableInitializationStatement: generate_symbol_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 762a8f1..dcbe9dd 100644 --- a/normalization.py +++ b/normalization.py @@ -38,6 +38,14 @@ NormalNegationExpression = collections.namedtuple( ], ) +NormalDotExpression = collections.namedtuple( + 'NormalDotExpression', + [ + 'instance', + 'field', + ], +) + NormalInfixExpression = collections.namedtuple( 'NormalInfixExpression', [ @@ -65,6 +73,14 @@ NormalArrayVariableInitializationStatement = collections.namedtuple( ], ) +NormalSymbolArrayVariableInitializationStatement = collections.namedtuple( + 'NormalSymbolArrayVariableInitializationStatement', + [ + 'variable', + 'symbol_list', + ], +) + NormalVariableInitializationStatement = collections.namedtuple( 'NormalVariableInitializationStatement', [ @@ -227,6 +243,72 @@ def normalize_string_literal_expression(counter, expression): NormalVariableExpression(variable=variable), ) +NormalStructureLiteralExpression = collections.namedtuple( + 'NormalStructureLiteralExpression', + [ + 'field_count', + 'symbol_list_variable', + 'value_list_variable', + ], +) + +def normalize_structure_literal_expression(counter, expression): + prestatements = [] + field_symbol_array = [] + field_value_array = [] + + for symbol_expression_pair in expression.fields: + counter, field_prestatements, field_expression = normalize_expression( + counter, + symbol_expression_pair.expression, + ) + + for p in field_prestatements: + prestatements.append(p) + + field_symbol_array.append(symbol_expression_pair.symbol) + field_value_array.append(field_expression) + + symbol_array_variable = '${}'.format(counter) + counter += 1 + + prestatements.append( + NormalSymbolArrayVariableInitializationStatement( + variable=symbol_array_variable, + symbol_list=tuple(field_symbol_array), + ) + ) + + value_array_variable = '${}'.format(counter) + counter += 1 + + prestatements.append( + NormalArrayVariableInitializationStatement( + variable=value_array_variable, + items=tuple(field_value_array), + ) + ) + + variable = '${}'.format(counter) + + prestatements.append( + NormalVariableInitializationStatement( + variable=variable, + expression=NormalStructureLiteralExpression( + field_count=len(expression.fields), + symbol_list_variable=symbol_array_variable, + value_list_variable=value_array_variable, + ), + ) + ) + + return ( + counter + 1, + tuple(prestatements), + NormalVariableExpression(variable=variable), + ) + + def normalize_symbol_expression(counter, expression): variable = '${}'.format(counter) return ( @@ -448,12 +530,33 @@ def normalize_boolean_expression(counter, expression): NormalVariableExpression(variable=result_variable), ) +def normalize_dot_expression(counter, expression): + assert isinstance(expression.right, parsing.FurSymbolExpression) + + counter, prestatements, left_expression = normalize_expression(counter, expression.left) + + variable = '${}'.format(counter) + + dot_expression_prestatement = NormalVariableInitializationStatement( + variable=variable, + expression=NormalDotExpression( + instance=left_expression, + field=expression.right.symbol, + ), + ) + + return ( + counter + 1, + prestatements + (dot_expression_prestatement,), + NormalVariableExpression(variable=variable), + ) def normalize_infix_expression(counter, expression): return { 'multiplication_level': normalize_basic_infix_operation, 'addition_level': normalize_basic_infix_operation, 'comparison_level': normalize_comparison_expression, + 'dot_level': normalize_dot_expression, 'and_level': normalize_boolean_expression, 'or_level': normalize_boolean_expression, }[expression.order](counter, expression) @@ -523,6 +626,7 @@ def normalize_expression(counter, expression): parsing.FurListItemExpression: normalize_list_item_expression, parsing.FurNegationExpression: normalize_negation_expression, parsing.FurStringLiteralExpression: normalize_string_literal_expression, + parsing.FurStructureLiteralExpression: normalize_structure_literal_expression, parsing.FurSymbolExpression: normalize_symbol_expression, }[type(expression)](counter, expression) diff --git a/parsing.py b/parsing.py index f16af14..2076837 100644 --- a/parsing.py +++ b/parsing.py @@ -90,6 +90,21 @@ FurIfExpression = collections.namedtuple( ], ) +FurSymbolExpressionPair = collections.namedtuple( + 'FurSymbolExpressionPair', + [ + 'symbol', + 'expression', + ], +) + +FurStructureLiteralExpression = collections.namedtuple( + 'FurStructureLiteralExpression', + [ + 'fields', + ], +) + def _integer_literal_expression_parser(index, tokens): failure = (False, index, None) @@ -150,6 +165,44 @@ def _parenthese_wrapped_parser(internal_parser): def _parenthesized_expression_parser(index, tokens): return _parenthese_wrapped_parser(_expression_parser)(index, tokens) +def symbol_expression_pair_parser(index, tokens): + failure = (False, index, None) + + if tokens[index].type == 'symbol': + symbol = tokens[index].match + index += 1 + else: + return failure + + if tokens[index].type == 'colon': + index += 1 + else: + return failure + + success, index, expression = _expression_parser(index, tokens) + + if not success: + raise Exception() + + return ( + True, + index, + FurSymbolExpressionPair( + symbol=symbol, + expression=expression, + ), + ) + +def _structure_literal_parser(index, tokens): + success, index, result = _parenthese_wrapped_parser(_comma_separated_list_parser(symbol_expression_pair_parser))(index, tokens) + return ( + success, + index, + FurStructureLiteralExpression( + fields=result, + ), + ) + def _list_literal_expression_parser(index, tokens): failure = (False, index, None) @@ -162,29 +215,42 @@ def _list_literal_expression_parser(index, tokens): else: return failure +def _literal_level_expression_parser(index, tokens): + return _or_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, + _structure_literal_parser, + )(index, tokens) + +def _dot_expression_parser(index, tokens): + return _left_recursive_infix_operator_parser( + lambda token: token.type == 'period', + _literal_level_expression_parser, + 'dot_level', + )(index, tokens) + def _negation_expression_parser(index, tokens): failure = (False, index, None) if tokens[index].match != '-': return failure - success, index, value = _literal_level_expression_parser(index + 1, tokens) + success, index, value = _dot_expression_parser(index + 1, tokens) if not success: return failure return (True, index, FurNegationExpression(value=value)) -def _literal_level_expression_parser(index, tokens): +def _negation_level_expression_parser(index, tokens): return _or_parser( + _dot_expression_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) def _left_recursive_infix_operator_parser(operator_token_matcher, operand_parser, order): @@ -218,7 +284,7 @@ def _left_recursive_infix_operator_parser(operator_token_matcher, operand_parser def _multiplication_level_expression_parser(index, tokens): return _left_recursive_infix_operator_parser( lambda token: token.type == 'multiplication_level_operator', - _literal_level_expression_parser, + _negation_level_expression_parser, 'multiplication_level', )(index, tokens) @@ -448,9 +514,6 @@ def _if_expression_parser(index, tokens): ), ) - - - _expression_parser = _or_parser( _or_level_expression_parser, _if_expression_parser, # This should always be at the top level diff --git a/templates/program.c b/templates/program.c index 25bb413..d6df732 100644 --- a/templates/program.c +++ b/templates/program.c @@ -55,6 +55,7 @@ enum Type LIST, STRING_CONCATENATION, STRING_LITERAL, + STRUCTURE, VOID }; @@ -78,6 +79,16 @@ struct List struct StringConcatenation; typedef struct StringConcatenation StringConcatenation; +struct Structure; +typedef struct Structure Structure; +struct Structure +{ + size_t reference_count; + size_t length; + const char** symbol_list; + Object* value_list; +}; + union Instance { bool boolean; @@ -86,6 +97,7 @@ union Instance List list; StringConcatenation* string_concatenation; const char* string_literal; + Structure* structure; }; struct Object @@ -137,6 +149,65 @@ Object List_get(Object* list, Object index) return list->instance.list.items[index.instance.integer]; } +Object Object_rereference(Object self) +{ + switch(self.type) + { + case BOOLEAN: + case CLOSURE: + case INTEGER: + case STRING_LITERAL: + case VOID: + return self; + + case STRING_CONCATENATION: + self.instance.string_concatenation->referenceCount++; + return self; + + case STRUCTURE: + self.instance.structure->reference_count++; + return self; + + default: + assert(false); + } +} + +Object Structure_construct(size_t length, const char** symbol_list, Object* value_list) +{ + Structure* structure = malloc(sizeof(Structure)); + structure->reference_count = 1; + structure->length = length; + structure->symbol_list = malloc(sizeof(const char*) * length); + structure->value_list = malloc(sizeof(Object) * length); + + // TODO Don't allow assignment of mutable structures, as this screws up reference counting + for(size_t i = 0; i < length; i++) + { + structure->symbol_list[i] = symbol_list[i]; + structure->value_list[i] = Object_rereference(value_list[i]); + } + + Object result = { STRUCTURE, (Instance)structure }; + + return result; +} + +Object Structure_get(Object* self, const char* symbol) +{ + assert(self->type == STRUCTURE); + + for(size_t i = 0; i < self->instance.structure->length; i++) + { + if(self->instance.structure->symbol_list[i] == symbol) + { + return self->instance.structure->value_list[i]; + } + } + + assert(false); +} + struct EnvironmentNode { const char* key; @@ -197,6 +268,21 @@ void Object_deinitialize(Object* self) } break; + case STRUCTURE: + self->instance.structure->reference_count--; + + if(self->instance.structure->reference_count == 0) + { + for(size_t i = 0; i < self->instance.structure->length; i++) + { + Object_deinitialize(&(self->instance.structure->value_list[i])); + } + free(self->instance.structure->symbol_list); + free(self->instance.structure->value_list); + free(self->instance.structure); + } + break; + default: assert(false); } @@ -435,9 +521,6 @@ Object operator$concatenate(Object left, Object right) { switch(left.type) { case STRING_CONCATENATION: - left.instance.string_concatenation->referenceCount++; - break; - case STRING_LITERAL: break; @@ -447,9 +530,6 @@ Object operator$concatenate(Object left, Object right) switch(right.type) { case STRING_CONCATENATION: - right.instance.string_concatenation->referenceCount++; - break; - case STRING_LITERAL: break; @@ -459,8 +539,8 @@ Object operator$concatenate(Object left, Object right) StringConcatenation* concatenation = malloc(sizeof(StringConcatenation)); concatenation->referenceCount = 1; - concatenation->left = left; - concatenation->right = right; + concatenation->left = Object_rereference(left); + concatenation->right = Object_rereference(right); Object result = { STRING_CONCATENATION, (Instance)concatenation }; return result; diff --git a/tokenization.py b/tokenization.py index 02f9528..bc8cf85 100644 --- a/tokenization.py +++ b/tokenization.py @@ -38,6 +38,8 @@ _TOKEN_MATCHERS = [ ('open_parenthese', r'\('), ('close_parenthese', r'\)'), ('comma', r','), + ('colon', r':'), + ('period', r'\.'), ('integer_literal', r'\d+'), ('symbol', r'[a-z_]+'), ('single_quoted_string_literal', r"'.*?'"), diff --git a/transformation.py b/transformation.py index 1a9f2c6..c07f692 100644 --- a/transformation.py +++ b/transformation.py @@ -33,6 +33,24 @@ CSymbolExpression = collections.namedtuple( ], ) +CStructureLiteralExpression = collections.namedtuple( + 'CStructureLiteralExpression', + [ + 'field_count', + 'symbol_list_variable', + 'value_list_variable', + ], +) + +CDotExpression = collections.namedtuple( + 'CDotExpression', + [ + 'instance', + 'symbol', + 'symbol_list_index', + ], +) + CNegationExpression = collections.namedtuple( 'CNegationExpression', [ @@ -76,6 +94,15 @@ CArrayVariableInitializationStatement = collections.namedtuple( ], ) +CSymbolArrayVariableInitializationStatement = collections.namedtuple( + 'CSymbolArrayVariableInitializationStatement', + [ + 'variable', + 'symbol_list', + 'symbol_list_indices', + ], +) + CVariableInitializationStatement = collections.namedtuple( 'CVariableInitializationStatement', [ @@ -148,6 +175,7 @@ BUILTINS = { } def transform_variable_expression(accumulators, expression): + assert isinstance(expression, normalization.NormalVariableExpression) return CVariableExpression(variable=expression.variable) def transform_string_literal_expression(accumulators, expression): @@ -292,6 +320,27 @@ CListGetExpression = collections.namedtuple( ], ) +def transform_structure_literal_expression(accumulators, expression): + return CStructureLiteralExpression( + field_count=expression.field_count, + symbol_list_variable=expression.symbol_list_variable, + value_list_variable=expression.value_list_variable, + ) + +def transform_dot_expression(accumulators, expression): + try: + symbol_list_index = accumulators.symbol_list.index(expression.field) + + except ValueError: + symbol_list_index = len(accumulators.symbol_list) + accumulators.symbol_list.append(expression.field) + + return CDotExpression( + instance=transform_variable_expression(accumulators, expression.instance), + symbol=expression.field, + symbol_list_index=symbol_list_index, + ) + def transform_list_construct_expression(accumulators, expression): return CListConstructExpression(allocate=expression.allocate) @@ -314,12 +363,14 @@ def transform_expression(accumulators, expression): parsing.FurIntegerLiteralExpression: transform_integer_literal_expression, parsing.FurNegationExpression: transform_negation_expression, parsing.FurStringLiteralExpression: transform_string_literal_expression, + normalization.NormalDotExpression: transform_dot_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.NormalStructureLiteralExpression: transform_structure_literal_expression, normalization.NormalStringLiteralExpression: transform_string_literal_expression, normalization.NormalSymbolExpression: transform_symbol_expression, normalization.NormalVariableExpression: transform_variable_expression, @@ -368,6 +419,24 @@ def transform_array_variable_initialization_statement(accumulators, statement): items=tuple(transform_expression(accumulators, i) for i in statement.items), ) +def transform_symbol_array_variable_initialization_statement(accumulators, statement): + symbol_list_indices = [] + + for symbol in statement.symbol_list: + try: + symbol_list_index = accumulators.symbol_list.index(symbol) + except ValueError: + symbol_list_index = len(accumulators.symbol_list) + accumulators.symbol_list.append(symbol) + + symbol_list_indices.append(symbol_list_index) + + return CSymbolArrayVariableInitializationStatement( + variable=statement.variable, + symbol_list=statement.symbol_list, + symbol_list_indices=tuple(symbol_list_indices), + ) + def transform_variable_initialization_statement(accumulators, statement): return CVariableInitializationStatement( variable=statement.variable, @@ -403,6 +472,7 @@ def transform_statement(accumulators, statement): normalization.NormalFunctionDefinitionStatement: transform_function_definition_statement, normalization.NormalIfElseStatement: transform_if_else_statement, normalization.NormalListAppendStatement: transform_list_append_statement, + normalization.NormalSymbolArrayVariableInitializationStatement: transform_symbol_array_variable_initialization_statement, normalization.NormalVariableInitializationStatement: transform_variable_initialization_statement, normalization.NormalVariableReassignmentStatement: transform_variable_reassignment_statement, }[type(statement)](accumulators, statement) -- 2.20.1