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         'operator_declarations',
 138         'statements',
 139         'standard_libraries',
 140         'string_literal_list',
 141         'symbol_list',
 142     ],
 143 )
 144
 145 EQUALITY_LEVEL_OPERATOR_TO_FUNCTION_NAME_MAPPING = {
 146     '==':   'equals',
 147     '!=':   'notEquals',
 148     '<=':   'lessThanOrEqual',
 149     '>=':   'greaterThanOrEqual',
 150     '<':    'lessThan',
 151     '>':    'greaterThan',
 152 }
 153
 154 def transform_comparison_level_expression(accumulators, expression):
 155     # Transform expressions like 1 < 2 < 3 into expressions like 1 < 2 && 2 < 3
 156     if isinstance(expression.left, parsing.FurInfixExpression) and expression.left.order == 'comparison_level':
 157         left = transform_comparison_level_expression(
 158             accumulators,
 159             expression.left
 160         )
 161
 162         middle = left.right
 163
 164         right = transform_expression(
 165             accumulators,
 166             expression.right,
 167         )
 168
 169         # TODO Don't evaluate the middle expression twice
 170         return CFunctionCallForFurInfixOperator(
 171             name='and',
 172             left=left,
 173             right=CFunctionCallForFurInfixOperator(
 174                 name=EQUALITY_LEVEL_OPERATOR_TO_FUNCTION_NAME_MAPPING[expression.operator],
 175                 left=middle,
 176                 right=right,
 177             ),
 178         )
 179
 180     return CFunctionCallForFurInfixOperator(
 181         name=EQUALITY_LEVEL_OPERATOR_TO_FUNCTION_NAME_MAPPING[expression.operator],
 182         left=transform_expression(accumulators, expression.left),
 183         right=transform_expression(accumulators, expression.right),
 184     )
 185
 186 BUILTINS = {
 187     'false':    [],
 188     'pow':      ['math.h'],
 189     'print':    ['stdio.h'],
 190     'true':     [],
 191 }
 192
 193 def transform_variable_expression(accumulators, expression):
 194     return CVariableExpression(variable=expression.variable)
 195
 196 def transform_string_literal(accumulators, expression):
 197     value = expression.value
 198
 199     try:
 200         index = accumulators.string_literal_list.index(value)
 201     except ValueError:
 202         index = len(accumulators.string_literal_list)
 203         accumulators.string_literal_list.append(value)
 204
 205     return CStringLiteral(index=index, value=value)
 206
 207 def transform_symbol_expression(accumulators, expression):
 208     if expression.value in ['true', 'false']:
 209         return CConstantExpression(value=expression.value)
 210
 211     if expression.value not in accumulators.symbol_list:
 212         symbol_list.append(expression.value)
 213
 214     return CSymbolExpression(
 215         symbol=expression.value,
 216         symbol_list_index=accumulators.symbol_list.index(expression.value),
 217     )
 218
 219 CInfixOperatorDeclaration = collections.namedtuple(
 220     'CInfixOperatorDeclaration',
 221     [
 222         'name',
 223         'input_type',
 224         'result_type',
 225         'c_operator',
 226     ],
 227 )
 228
 229 INFIX_OPERATOR_TO_DECLARATION = {
 230     '+':    CInfixOperatorDeclaration(name='add', input_type='INTEGER', result_type='INTEGER', c_operator='+'),
 231     '-':    CInfixOperatorDeclaration(name='subtract', input_type='INTEGER', result_type='INTEGER', c_operator='-'),
 232     '*':    CInfixOperatorDeclaration(name='multiply', input_type='INTEGER', result_type='INTEGER', c_operator='*'),
 233     '//':   CInfixOperatorDeclaration(name='integerDivide', input_type='INTEGER', result_type='INTEGER', c_operator='/'),
 234     '%':    CInfixOperatorDeclaration(name='modularDivide', input_type='INTEGER', result_type='INTEGER', c_operator='%'),
 235     'and':  CInfixOperatorDeclaration(name='and', input_type='BOOLEAN', result_type='BOOLEAN', c_operator='&&'),
 236     'or':   CInfixOperatorDeclaration(name='or', input_type='BOOLEAN', result_type='BOOLEAN', c_operator='||'),
 237 }
 238
 239 def transform_infix_expression(accumulators, expression):
 240     if expression.order == 'comparison_level':
 241         return transform_comparison_level_expression(accumulators, expression)
 242
 243     accumulators.operator_set.add(INFIX_OPERATOR_TO_DECLARATION[expression.operator])
 244
 245     return CFunctionCallForFurInfixOperator(
 246         name=INFIX_OPERATOR_TO_DECLARATION[expression.operator].name,
 247         left=transform_expression(accumulators, expression.left),
 248         right=transform_expression(accumulators, expression.right),
 249     )
 250
 251 def transform_integer_literal_expression(accumulators, expression):
 252     return CIntegerLiteral(value=expression.value)
 253
 254 def transform_parenthesized_expression(accumulators, expression):
 255     # Parentheses can be removed because everything in the C output is explicitly parenthesized
 256     return transform_expression(accumulators, expression.internal)
 257
 258 def transform_negation_expression(accumulators, expression):
 259     return CNegationExpression(
 260         value=transform_expression(accumulators, expression.internal_expression),
 261     )
 262
 263 def transform_expression(accumulators, expression):
 264     # TODO Clean up handlers for parsing expressions
 265     return {
 266         parsing.FurFunctionCallExpression: transform_function_call_expression,
 267         parsing.FurInfixExpression: transform_infix_expression,
 268         parsing.FurIntegerLiteralExpression: transform_integer_literal_expression,
 269         parsing.FurNegationExpression: transform_negation_expression,
 270         parsing.FurParenthesizedExpression: transform_parenthesized_expression,
 271         parsing.FurStringLiteralExpression: transform_string_literal,
 272         parsing.FurSymbolExpression: transform_symbol_expression,
 273         normalization.NormalFunctionCallExpression: transform_function_call_expression,
 274         normalization.NormalInfixExpression: transform_infix_expression,
 275         normalization.NormalNegationExpression: transform_negation_expression,
 276         normalization.NormalVariableExpression: transform_variable_expression,
 277     }[type(expression)](accumulators, expression)
 278
 279 def transform_symbol_assignment_statement(accumulators, assignment_statement):
 280     # TODO Check that target is not a builtin
 281     if assignment_statement.target not in accumulators.symbol_list:
 282         accumulators.symbol_list.append(assignment_statement.target)
 283
 284     return CSymbolAssignmentStatement(
 285         target=assignment_statement.target,
 286         target_symbol_list_index=accumulators.symbol_list.index(assignment_statement.target),
 287         expression=transform_expression(
 288             accumulators,
 289             assignment_statement.expression,
 290         ),
 291     )
 292
 293 def transform_function_call_expression(accumulators, function_call):
 294     if function_call.function.value in BUILTINS.keys():
 295         # TODO Check that the builtin is actually callable
 296         accumulators.builtin_set.add(function_call.function.value)
 297
 298     # TODO Use the symbol from SYMBOL LIST
 299     return CFunctionCallExpression(
 300         name=function_call.function.value,
 301         argument_count=function_call.argument_count,
 302         argument_items=transform_expression(accumulators, function_call.argument_items),
 303     )
 304
 305 def transform_expression_statement(accumulators, statement):
 306     # TODO At some point we can verify that all expression types are supported and just call transform_expression
 307     expression = {
 308         parsing.FurFunctionCallExpression: transform_function_call_expression,
 309         parsing.FurInfixExpression: transform_expression,
 310         parsing.FurIntegerLiteralExpression: transform_expression,
 311         parsing.FurSymbolExpression: transform_expression,
 312         normalization.NormalFunctionCallExpression: transform_function_call_expression,
 313         normalization.NormalVariableExpression: transform_expression,
 314     }[type(statement.expression)](accumulators, statement.expression)
 315
 316     return CExpressionStatement(
 317         expression=expression,
 318     )
 319
 320 def transform_if_else_statement(accumulators, statement):
 321     return CIfElseStatement(
 322         condition_expression=transform_expression(accumulators, statement.condition_expression),
 323         if_statements=tuple(transform_statement(accumulators, s) for s in statement.if_statements),
 324         else_statements=tuple(transform_statement(accumulators, s) for s in statement.else_statements),
 325     )
 326
 327 def transform_array_variable_initialization_statement(accumulators, statement):
 328     return CArrayVariableInitializationStatement(
 329         variable=statement.variable,
 330         items=tuple(transform_expression(accumulators, i) for i in statement.items),
 331     )
 332
 333 def transform_variable_initialization_statement(accumulators, statement):
 334     return CVariableInitializationStatement(
 335         variable=statement.variable,
 336         expression=transform_expression(accumulators, statement.expression),
 337     )
 338
 339 def transform_variable_reassignment_statement(accumulators, statement):
 340     return CVariableReassignmentStatement(
 341         variable=statement.variable,
 342         expression=transform_expression(accumulators, statement.expression),
 343     )
 344
 345 def transform_function_definition_statement(accumulators, statement):
 346     # TODO Allow defining the same function in different contexts
 347     if any(fd.name == statement.name for fd in accumulators.function_definition_list):
 348         raise Exception('A function with name "{}" already exists'.format(statement.name))
 349
 350     accumulators.function_definition_list.append(CFunctionDefinition(
 351         name=statement.name,
 352         statement_list=tuple(transform_statement(accumulators, s) for s in statement.statement_list)
 353     ))
 354
 355     return CFunctionDeclaration(name=statement.name)
 356
 357 def transform_statement(accumulators, statement):
 358     return {
 359         parsing.FurAssignmentStatement: transform_symbol_assignment_statement,
 360         parsing.FurExpressionStatement: transform_expression_statement,
 361         normalization.NormalArrayVariableInitializationStatement: transform_array_variable_initialization_statement,
 362         normalization.NormalExpressionStatement: transform_expression_statement,
 363         normalization.NormalFunctionDefinitionStatement: transform_function_definition_statement,
 364         normalization.NormalIfElseStatement: transform_if_else_statement,
 365         normalization.NormalVariableInitializationStatement: transform_variable_initialization_statement,
 366         normalization.NormalVariableReassignmentStatement: transform_variable_reassignment_statement,
 367     }[type(statement)](accumulators, statement)
 368
 369
 370 Accumulators = collections.namedtuple(
 371     'Accumulators',
 372     [
 373         'builtin_set',
 374         'function_definition_list',
 375         'operator_set',
 376         'symbol_list',
 377         'string_literal_list',
 378     ],
 379 )
 380
 381 def transform(program):
 382     accumulators = Accumulators(
 383         builtin_set=set(),
 384         function_definition_list=[],
 385         operator_set=set(),
 386         symbol_list=[],
 387         string_literal_list=[],
 388     )
 389
 390     statement_list = [
 391         transform_statement(accumulators, statement) for statement in program.statement_list
 392     ]
 393
 394     standard_library_set = set()
 395     for builtin in accumulators.builtin_set:
 396         for standard_library in BUILTINS[builtin]:
 397             standard_library_set.add(standard_library)
 398
 399     return CProgram(
 400         builtin_set=accumulators.builtin_set,
 401         function_definition_list=accumulators.function_definition_list,
 402         operator_declarations=tuple(sorted(accumulators.operator_set)),
 403         statements=statement_list,
 404         standard_libraries=standard_library_set,
 405         string_literal_list=accumulators.string_literal_list,
 406         symbol_list=accumulators.symbol_list,
 407     )
 408
 409
 410 if __name__ == '__main__':
 411     import unittest
 412
 413     unittest.main()