code.kerkeslager.com Git - fur/blob - transformation.py

   1 import collections
   2
   3 import normalization
   4 import parsing
   5
   6 CIntegerLiteral = collections.namedtuple(
   7     'CIntegerLiteral',
   8     [
   9         'value',
  10     ],
  11 )
  12
  13 CStringLiteral = collections.namedtuple(
  14     'CStringLiteral',
  15     [
  16         'index',
  17         'value',
  18     ],
  19 )
  20
  21 CConstantExpression = collections.namedtuple(
  22     'CConstantExpression',
  23     [
  24         'value'
  25     ],
  26 )
  27
  28 CVariableExpression = collections.namedtuple(
  29     'CVariableExpression',
  30     [
  31         'variable',
  32     ],
  33 )
  34
  35 CSymbolExpression = collections.namedtuple(
  36     'CSymbolExpression',
  37     [
  38         'symbol',
  39         'symbol_list_index',
  40     ],
  41 )
  42
  43 CNegationExpression = collections.namedtuple(
  44     'CNegationExpression',
  45     [
  46         'value',
  47     ],
  48 )
  49
  50 CFunctionCallForFurInfixOperator = collections.namedtuple(
  51     'CFunctionCallForFurInfixOperator',
  52     [
  53         'name',
  54         'left',
  55         'right',
  56     ],
  57 )
  58
  59 CFunctionCallExpression = collections.namedtuple(
  60     'CFunctionCallExpression',
  61     [
  62         'name',
  63         'argument_count',
  64         'argument_items',
  65     ],
  66 )
  67
  68 CSymbolAssignmentStatement = collections.namedtuple(
  69     'CSymbolAssignmentStatement',
  70     [
  71         'target',
  72         'target_symbol_list_index',
  73         'expression',
  74     ],
  75 )
  76
  77 CArrayVariableInitializationStatement = collections.namedtuple(
  78     'CArrayVariableInitializationStatement',
  79     [
  80         'variable',
  81         'items',
  82     ],
  83 )
  84
  85 CVariableInitializationStatement = collections.namedtuple(
  86     'CVariableInitializationStatement',
  87     [
  88         'variable',
  89         'expression',
  90     ],
  91 )
  92
  93 CVariableReassignmentStatement = collections.namedtuple(
  94     'CVariableReassignmentStatement',
  95     [
  96         'variable',
  97         'expression',
  98     ],
  99 )
 100
 101 CExpressionStatement = collections.namedtuple(
 102     'CExpressionStatement',
 103     [
 104         'expression',
 105     ],
 106 )
 107
 108 CIfElseStatement = collections.namedtuple(
 109     'CIfElseStatement',
 110     [
 111         'condition_expression',
 112         'if_statements',
 113         'else_statements',
 114     ],
 115 )
 116
 117 CFunctionDeclaration = collections.namedtuple(
 118     'CFunctionDeclaration',
 119     [
 120         'name',
 121     ],
 122 )
 123
 124 CFunctionDefinition = collections.namedtuple(
 125     'CFunctionDefinition',
 126     [
 127         'name',
 128         'statement_list',
 129     ],
 130 )
 131
 132 CProgram = collections.namedtuple(
 133     'CProgram',
 134     [
 135         'builtin_set',
 136         'function_definition_list',
 137         'statements',
 138         'standard_libraries',
 139         'string_literal_list',
 140         'symbol_list',
 141     ],
 142 )
 143
 144 EQUALITY_LEVEL_OPERATOR_TO_FUNCTION_NAME_MAPPING = {
 145     '==':   'equals',
 146     '!=':   'notEquals',
 147     '<=':   'lessThanOrEqual',
 148     '>=':   'greaterThanOrEqual',
 149     '<':    'lessThan',
 150     '>':    'greaterThan',
 151 }
 152
 153 def transform_comparison_level_expression(accumulators, expression):
 154     # Transform expressions like 1 < 2 < 3 into expressions like 1 < 2 && 2 < 3
 155     if isinstance(expression.left, parsing.FurInfixExpression) and expression.left.order == 'comparison_level':
 156         left = transform_comparison_level_expression(
 157             accumulators,
 158             expression.left
 159         )
 160
 161         middle = left.right
 162
 163         right = transform_expression(
 164             accumulators,
 165             expression.right,
 166         )
 167
 168         # TODO Don't evaluate the middle expression twice
 169         return CFunctionCallForFurInfixOperator(
 170             name='and',
 171             left=left,
 172             right=CFunctionCallForFurInfixOperator(
 173                 name=EQUALITY_LEVEL_OPERATOR_TO_FUNCTION_NAME_MAPPING[expression.operator],
 174                 left=middle,
 175                 right=right,
 176             ),
 177         )
 178
 179     return CFunctionCallForFurInfixOperator(
 180         name=EQUALITY_LEVEL_OPERATOR_TO_FUNCTION_NAME_MAPPING[expression.operator],
 181         left=transform_expression(accumulators, expression.left),
 182         right=transform_expression(accumulators, expression.right),
 183     )
 184
 185 BUILTINS = {
 186     'false':    [],
 187     'pow':      ['math.h'],
 188     'print':    ['stdio.h'],
 189     'true':     [],
 190 }
 191
 192 def transform_variable_expression(accumulators, expression):
 193     return CVariableExpression(variable=expression.variable)
 194
 195 def transform_infix_expression(accumulators, expression):
 196     if expression.order == 'comparison_level':
 197         return transform_comparison_level_expression(accumulators, expression)
 198
 199     INFIX_OPERATOR_TO_FUNCTION_NAME = {
 200         '+':    'add',
 201         '-':    'subtract',
 202         '*':    'multiply',
 203         '//':   'integerDivide',
 204         '%':    'modularDivide',
 205         'and':  'and',
 206         'or':   'or',
 207     }
 208
 209     return CFunctionCallForFurInfixOperator(
 210         name=INFIX_OPERATOR_TO_FUNCTION_NAME[expression.operator],
 211         left=transform_expression(accumulators, expression.left),
 212         right=transform_expression(accumulators, expression.right),
 213     )
 214
 215 def transform_expression(accumulators, expression):
 216     if isinstance(expression, parsing.FurParenthesizedExpression):
 217         # Parentheses can be removed because everything in the C output is explicitly parenthesized
 218         return transform_expression(accumulators, expression.internal)
 219
 220     if isinstance(expression, parsing.FurNegationExpression):
 221         return transform_negation_expression(accumulators, expression)
 222
 223     if isinstance(expression, parsing.FurFunctionCallExpression):
 224         return transform_function_call_expression(accumulators, expression)
 225
 226     if isinstance(expression, parsing.FurSymbolExpression):
 227         if expression.value in ['true', 'false']:
 228             return CConstantExpression(value=expression.value)
 229
 230         if expression.value not in accumulators.symbol_list:
 231             symbol_list.append(expression.value)
 232
 233         return CSymbolExpression(
 234             symbol=expression.value,
 235             symbol_list_index=accumulators.symbol_list.index(expression.value),
 236         )
 237
 238     if isinstance(expression, parsing.FurStringLiteralExpression):
 239         value = expression.value
 240
 241         try:
 242             index = accumulators.string_literal_list.index(value)
 243         except ValueError:
 244             index = len(accumulators.string_literal_list)
 245             accumulators.string_literal_list.append(value)
 246
 247         return CStringLiteral(index=index, value=value)
 248
 249     LITERAL_TYPE_MAPPING = {
 250         parsing.FurIntegerLiteralExpression: CIntegerLiteral,
 251     }
 252
 253     if type(expression) in LITERAL_TYPE_MAPPING:
 254         return LITERAL_TYPE_MAPPING[type(expression)](value=expression.value)
 255
 256     # TODO Handle all possible types in this form
 257     return {
 258         parsing.FurInfixExpression: transform_infix_expression, # TODO Shouldn't need this
 259         normalization.NormalFunctionCallExpression: transform_function_call_expression,
 260         normalization.NormalInfixExpression: transform_infix_expression,
 261         normalization.NormalNegationExpression: transform_negation_expression,
 262         normalization.NormalVariableExpression: transform_variable_expression,
 263     }[type(expression)](accumulators, expression)
 264
 265 def transform_symbol_assignment_statement(accumulators, assignment_statement):
 266     # TODO Check that target is not a builtin
 267     if assignment_statement.target not in accumulators.symbol_list:
 268         accumulators.symbol_list.append(assignment_statement.target)
 269
 270     return CSymbolAssignmentStatement(
 271         target=assignment_statement.target,
 272         target_symbol_list_index=accumulators.symbol_list.index(assignment_statement.target),
 273         expression=transform_expression(
 274             accumulators,
 275             assignment_statement.expression,
 276         ),
 277     )
 278
 279 def transform_negation_expression(accumulators, expression):
 280     return CNegationExpression(
 281         value=transform_expression(accumulators, expression.internal_expression),
 282     )
 283
 284 def transform_function_call_expression(accumulators, function_call):
 285     if function_call.function.value in BUILTINS.keys():
 286         # TODO Check that the builtin is actually callable
 287         accumulators.builtin_set.add(function_call.function.value)
 288
 289     # TODO Use the symbol from SYMBOL LIST
 290     return CFunctionCallExpression(
 291         name=function_call.function.value,
 292         argument_count=function_call.argument_count,
 293         argument_items=transform_expression(accumulators, function_call.argument_items),
 294     )
 295
 296 def transform_expression_statement(accumulators, statement):
 297     # TODO At some point we can verify that all expression types are supported and just call transform_expression
 298     expression = {
 299         parsing.FurFunctionCallExpression: transform_function_call_expression,
 300         parsing.FurInfixExpression: transform_expression,
 301         parsing.FurIntegerLiteralExpression: transform_expression,
 302         parsing.FurSymbolExpression: transform_expression,
 303         normalization.NormalFunctionCallExpression: transform_function_call_expression,
 304         normalization.NormalVariableExpression: transform_expression,
 305     }[type(statement.expression)](accumulators, statement.expression)
 306
 307     return CExpressionStatement(
 308         expression=expression,
 309     )
 310
 311 def transform_if_else_statement(accumulators, statement):
 312     return CIfElseStatement(
 313         condition_expression=transform_expression(accumulators, statement.condition_expression),
 314         if_statements=tuple(transform_statement(accumulators, s) for s in statement.if_statements),
 315         else_statements=tuple(transform_statement(accumulators, s) for s in statement.else_statements),
 316     )
 317
 318 def transform_array_variable_initialization_statement(accumulators, statement):
 319     return CArrayVariableInitializationStatement(
 320         variable=statement.variable,
 321         items=tuple(transform_expression(accumulators, i) for i in statement.items),
 322     )
 323
 324 def transform_variable_initialization_statement(accumulators, statement):
 325     return CVariableInitializationStatement(
 326         variable=statement.variable,
 327         expression=transform_expression(accumulators, statement.expression),
 328     )
 329
 330 def transform_variable_reassignment_statement(accumulators, statement):
 331     return CVariableReassignmentStatement(
 332         variable=statement.variable,
 333         expression=transform_expression(accumulators, statement.expression),
 334     )
 335
 336 def transform_function_definition_statement(accumulators, statement):
 337     # TODO Allow defining the same function in different contexts
 338     if any(fd.name == statement.name for fd in accumulators.function_definition_list):
 339         raise Exception('A function with name "{}" already exists'.format(statement.name))
 340
 341     accumulators.function_definition_list.append(CFunctionDefinition(
 342         name=statement.name,
 343         statement_list=tuple(transform_statement(accumulators, s) for s in statement.statement_list)
 344     ))
 345
 346     return CFunctionDeclaration(name=statement.name)
 347
 348 def transform_statement(accumulators, statement):
 349     return {
 350         parsing.FurAssignmentStatement: transform_symbol_assignment_statement,
 351         parsing.FurExpressionStatement: transform_expression_statement,
 352         normalization.NormalArrayVariableInitializationStatement: transform_array_variable_initialization_statement,
 353         normalization.NormalExpressionStatement: transform_expression_statement,
 354         normalization.NormalFunctionDefinitionStatement: transform_function_definition_statement,
 355         normalization.NormalIfElseStatement: transform_if_else_statement,
 356         normalization.NormalVariableInitializationStatement: transform_variable_initialization_statement,
 357         normalization.NormalVariableReassignmentStatement: transform_variable_reassignment_statement,
 358     }[type(statement)](accumulators, statement)
 359
 360
 361 Accumulators = collections.namedtuple(
 362     'Accumulators',
 363     [
 364         'builtin_set',
 365         'function_definition_list',
 366         'symbol_list',
 367         'string_literal_list',
 368     ],
 369 )
 370
 371 def transform(program):
 372     accumulators = Accumulators(
 373         builtin_set=set(),
 374         function_definition_list=[],
 375         symbol_list=[],
 376         string_literal_list=[],
 377     )
 378
 379     statement_list = [
 380         transform_statement(accumulators, statement) for statement in program.statement_list
 381     ]
 382
 383     standard_library_set = set()
 384     for builtin in accumulators.builtin_set:
 385         for standard_library in BUILTINS[builtin]:
 386             standard_library_set.add(standard_library)
 387
 388     return CProgram(
 389         builtin_set=accumulators.builtin_set,
 390         function_definition_list=accumulators.function_definition_list,
 391         statements=statement_list,
 392         standard_libraries=standard_library_set,
 393         string_literal_list=accumulators.string_literal_list,
 394         symbol_list=accumulators.symbol_list,
 395     )
 396
 397
 398 if __name__ == '__main__':
 399     import unittest
 400
 401     unittest.main()