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_string_literal(accumulators, expression):
 196     value = expression.value
 197
 198     try:
 199         index = accumulators.string_literal_list.index(value)
 200     except ValueError:
 201         index = len(accumulators.string_literal_list)
 202         accumulators.string_literal_list.append(value)
 203
 204     return CStringLiteral(index=index, value=value)
 205
 206 def transform_symbol_expression(accumulators, expression):
 207     if expression.value in ['true', 'false']:
 208         return CConstantExpression(value=expression.value)
 209
 210     if expression.value not in accumulators.symbol_list:
 211         symbol_list.append(expression.value)
 212
 213     return CSymbolExpression(
 214         symbol=expression.value,
 215         symbol_list_index=accumulators.symbol_list.index(expression.value),
 216     )
 217
 218 def transform_infix_expression(accumulators, expression):
 219     if expression.order == 'comparison_level':
 220         return transform_comparison_level_expression(accumulators, expression)
 221
 222     INFIX_OPERATOR_TO_FUNCTION_NAME = {
 223         '+':    'add',
 224         '-':    'subtract',
 225         '*':    'multiply',
 226         '//':   'integerDivide',
 227         '%':    'modularDivide',
 228         'and':  'and',
 229         'or':   'or',
 230     }
 231
 232     return CFunctionCallForFurInfixOperator(
 233         name=INFIX_OPERATOR_TO_FUNCTION_NAME[expression.operator],
 234         left=transform_expression(accumulators, expression.left),
 235         right=transform_expression(accumulators, expression.right),
 236     )
 237
 238 def transform_integer_literal_expression(accumulators, expression):
 239     return CIntegerLiteral(value=expression.value)
 240
 241 def transform_parenthesized_expression(accumulators, expression):
 242     # Parentheses can be removed because everything in the C output is explicitly parenthesized
 243     return transform_expression(accumulators, expression.internal)
 244
 245 def transform_expression(accumulators, expression):
 246     # TODO Clean up handlers for parsing expressions
 247     return {
 248         parsing.FurFunctionCallExpression: transform_function_call_expression,
 249         parsing.FurInfixExpression: transform_infix_expression,
 250         parsing.FurIntegerLiteralExpression: transform_integer_literal_expression,
 251         parsing.FurNegationExpression: transform_negation_expression,
 252         parsing.FurParenthesizedExpression: transform_parenthesized_expression,
 253         parsing.FurStringLiteralExpression: transform_string_literal,
 254         parsing.FurSymbolExpression: transform_symbol_expression,
 255         normalization.NormalFunctionCallExpression: transform_function_call_expression,
 256         normalization.NormalInfixExpression: transform_infix_expression,
 257         normalization.NormalNegationExpression: transform_negation_expression,
 258         normalization.NormalVariableExpression: transform_variable_expression,
 259     }[type(expression)](accumulators, expression)
 260
 261 def transform_symbol_assignment_statement(accumulators, assignment_statement):
 262     # TODO Check that target is not a builtin
 263     if assignment_statement.target not in accumulators.symbol_list:
 264         accumulators.symbol_list.append(assignment_statement.target)
 265
 266     return CSymbolAssignmentStatement(
 267         target=assignment_statement.target,
 268         target_symbol_list_index=accumulators.symbol_list.index(assignment_statement.target),
 269         expression=transform_expression(
 270             accumulators,
 271             assignment_statement.expression,
 272         ),
 273     )
 274
 275 def transform_negation_expression(accumulators, expression):
 276     return CNegationExpression(
 277         value=transform_expression(accumulators, expression.internal_expression),
 278     )
 279
 280 def transform_function_call_expression(accumulators, function_call):
 281     if function_call.function.value in BUILTINS.keys():
 282         # TODO Check that the builtin is actually callable
 283         accumulators.builtin_set.add(function_call.function.value)
 284
 285     # TODO Use the symbol from SYMBOL LIST
 286     return CFunctionCallExpression(
 287         name=function_call.function.value,
 288         argument_count=function_call.argument_count,
 289         argument_items=transform_expression(accumulators, function_call.argument_items),
 290     )
 291
 292 def transform_expression_statement(accumulators, statement):
 293     # TODO At some point we can verify that all expression types are supported and just call transform_expression
 294     expression = {
 295         parsing.FurFunctionCallExpression: transform_function_call_expression,
 296         parsing.FurInfixExpression: transform_expression,
 297         parsing.FurIntegerLiteralExpression: transform_expression,
 298         parsing.FurSymbolExpression: transform_expression,
 299         normalization.NormalFunctionCallExpression: transform_function_call_expression,
 300         normalization.NormalVariableExpression: transform_expression,
 301     }[type(statement.expression)](accumulators, statement.expression)
 302
 303     return CExpressionStatement(
 304         expression=expression,
 305     )
 306
 307 def transform_if_else_statement(accumulators, statement):
 308     return CIfElseStatement(
 309         condition_expression=transform_expression(accumulators, statement.condition_expression),
 310         if_statements=tuple(transform_statement(accumulators, s) for s in statement.if_statements),
 311         else_statements=tuple(transform_statement(accumulators, s) for s in statement.else_statements),
 312     )
 313
 314 def transform_array_variable_initialization_statement(accumulators, statement):
 315     return CArrayVariableInitializationStatement(
 316         variable=statement.variable,
 317         items=tuple(transform_expression(accumulators, i) for i in statement.items),
 318     )
 319
 320 def transform_variable_initialization_statement(accumulators, statement):
 321     return CVariableInitializationStatement(
 322         variable=statement.variable,
 323         expression=transform_expression(accumulators, statement.expression),
 324     )
 325
 326 def transform_variable_reassignment_statement(accumulators, statement):
 327     return CVariableReassignmentStatement(
 328         variable=statement.variable,
 329         expression=transform_expression(accumulators, statement.expression),
 330     )
 331
 332 def transform_function_definition_statement(accumulators, statement):
 333     # TODO Allow defining the same function in different contexts
 334     if any(fd.name == statement.name for fd in accumulators.function_definition_list):
 335         raise Exception('A function with name "{}" already exists'.format(statement.name))
 336
 337     accumulators.function_definition_list.append(CFunctionDefinition(
 338         name=statement.name,
 339         statement_list=tuple(transform_statement(accumulators, s) for s in statement.statement_list)
 340     ))
 341
 342     return CFunctionDeclaration(name=statement.name)
 343
 344 def transform_statement(accumulators, statement):
 345     return {
 346         parsing.FurAssignmentStatement: transform_symbol_assignment_statement,
 347         parsing.FurExpressionStatement: transform_expression_statement,
 348         normalization.NormalArrayVariableInitializationStatement: transform_array_variable_initialization_statement,
 349         normalization.NormalExpressionStatement: transform_expression_statement,
 350         normalization.NormalFunctionDefinitionStatement: transform_function_definition_statement,
 351         normalization.NormalIfElseStatement: transform_if_else_statement,
 352         normalization.NormalVariableInitializationStatement: transform_variable_initialization_statement,
 353         normalization.NormalVariableReassignmentStatement: transform_variable_reassignment_statement,
 354     }[type(statement)](accumulators, statement)
 355
 356
 357 Accumulators = collections.namedtuple(
 358     'Accumulators',
 359     [
 360         'builtin_set',
 361         'function_definition_list',
 362         'operator_set',
 363         'symbol_list',
 364         'string_literal_list',
 365     ],
 366 )
 367
 368 def transform(program):
 369     accumulators = Accumulators(
 370         builtin_set=set(),
 371         function_definition_list=[],
 372         operator_set=set(),
 373         symbol_list=[],
 374         string_literal_list=[],
 375     )
 376
 377     statement_list = [
 378         transform_statement(accumulators, statement) for statement in program.statement_list
 379     ]
 380
 381     standard_library_set = set()
 382     for builtin in accumulators.builtin_set:
 383         for standard_library in BUILTINS[builtin]:
 384             standard_library_set.add(standard_library)
 385
 386     return CProgram(
 387         builtin_set=accumulators.builtin_set,
 388         function_definition_list=accumulators.function_definition_list,
 389         statements=statement_list,
 390         standard_libraries=standard_library_set,
 391         string_literal_list=accumulators.string_literal_list,
 392         symbol_list=accumulators.symbol_list,
 393     )
 394
 395
 396 if __name__ == '__main__':
 397     import unittest
 398
 399     unittest.main()