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

   1 import collections
   2
   3 def consume_newlines(index, tokens):
   4     while index < len(tokens) and tokens[index].type == 'newline':
   5         index += 1
   6
   7     return True, index, None
   8
   9 def _or_parser(*parsers):
  10     def result_parser(index, tokens):
  11         failure = (False, index, None)
  12
  13         for parser in parsers:
  14             success, index, value = parser(index, tokens)
  15
  16             if success:
  17                 return (success, index, value)
  18
  19         return failure
  20
  21     return result_parser
  22
  23 def _zero_or_more_parser(formatter, parser):
  24     def result_parser(index, tokens):
  25         values = []
  26
  27         while index < len(tokens):
  28             success, index, value = parser(index, tokens)
  29
  30             if success:
  31                 values.append(value)
  32             else:
  33                 break
  34
  35         return (True, index, formatter(values))
  36
  37     return result_parser
  38
  39 FurIntegerLiteralExpression = collections.namedtuple(
  40     'FurIntegerLiteralExpression',
  41     [
  42         'value',
  43     ],
  44 )
  45
  46 FurStringLiteralExpression = collections.namedtuple(
  47     'FurStringLiteralExpression',
  48     [
  49         'value',
  50     ],
  51 )
  52
  53 FurSymbolExpression = collections.namedtuple(
  54     'FurSymbolExpression',
  55     [
  56         'value',
  57     ],
  58 )
  59
  60 FurNegationExpression = collections.namedtuple(
  61     'FurNegationExpression',
  62     [
  63         'value',
  64     ],
  65 )
  66
  67 FurInfixExpression = collections.namedtuple(
  68     'FurInfixExpression',
  69     [
  70         'order',
  71         'operator',
  72         'left',
  73         'right',
  74     ],
  75 )
  76
  77 def _integer_literal_expression_parser(index, tokens):
  78     failure = (False, index, None)
  79
  80     if tokens[index].type != 'integer_literal':
  81         return failure
  82     value = int(tokens[index].match)
  83     index += 1
  84
  85     return True, index, FurIntegerLiteralExpression(value=value)
  86
  87 def _string_literal_expression_parser(index, tokens):
  88     if tokens[index].type == 'single_quoted_string_literal':
  89         return (True, index + 1, FurStringLiteralExpression(value=tokens[index].match[1:-1]))
  90
  91     return (False, index, None)
  92
  93 def _symbol_expression_parser(index, tokens):
  94     if tokens[index].type == 'symbol':
  95         return (True, index + 1, FurSymbolExpression(value=tokens[index].match))
  96
  97     return (False, index, None)
  98
  99 def _parenthese_wrapped_parser(internal_parser):
 100     def result_parser(index, tokens):
 101         failure = (False, index, None)
 102
 103         if tokens[index].type == 'open_parenthese':
 104             index += 1
 105         else:
 106             return failure
 107
 108         success, index, internal = internal_parser(index, tokens)
 109         if not success:
 110             return failure
 111
 112         if tokens[index].type == 'close_parenthese':
 113             index += 1
 114         else:
 115             raise Exception('Expected ")" on line {}, found "{}"'.format(
 116                 tokens[index].line,
 117                 tokens[index].match,
 118             ))
 119
 120         return True, index, internal
 121
 122     return result_parser
 123
 124 def _parenthesized_expression_parser(index, tokens):
 125     return _parenthese_wrapped_parser(_expression_parser)(index, tokens)
 126
 127 def _negation_expression_parser(index, tokens):
 128     failure = (False, index, None)
 129
 130     if tokens[index].match != '-':
 131         return failure
 132
 133     success, index, value = _literal_level_expression_parser(index + 1, tokens)
 134
 135     if not success:
 136         return failure
 137
 138     return (True, index, FurNegationExpression(value=value))
 139
 140 def _literal_level_expression_parser(index, tokens):
 141     return _or_parser(
 142         _negation_expression_parser,
 143         _function_call_expression_parser,
 144         _parenthesized_expression_parser,
 145         _integer_literal_expression_parser,
 146         _string_literal_expression_parser,
 147         _symbol_expression_parser,
 148     )(index, tokens)
 149
 150 def _left_recursive_infix_operator_parser(operator_token_matcher, operand_parser, order):
 151     def result_parser(index, tokens):
 152         failure = (False, index, None)
 153
 154         success, index, result = operand_parser(index, tokens)
 155
 156         if not success:
 157             return failure
 158
 159         while success and index < len(tokens) and operator_token_matcher(tokens[index]):
 160             success = False
 161
 162             if index + 1 < len(tokens):
 163                 success, try_index, value = operand_parser(index + 1, tokens)
 164
 165             if success:
 166                 result = FurInfixExpression(
 167                     order=order,
 168                     operator=tokens[index].match,
 169                     left=result,
 170                     right=value,
 171                 )
 172                 index = try_index
 173
 174         return True, index, result
 175
 176     return result_parser
 177
 178 def _multiplication_level_expression_parser(index, tokens):
 179     return _left_recursive_infix_operator_parser(
 180         lambda token: token.type == 'multiplication_level_operator',
 181         _literal_level_expression_parser,
 182         'multiplication_level',
 183     )(index, tokens)
 184
 185 def _addition_level_expression_parser(index, tokens):
 186     return _left_recursive_infix_operator_parser(
 187         lambda token: token.type == 'addition_level_operator',
 188         _multiplication_level_expression_parser,
 189         'addition_level',
 190     )(index, tokens)
 191
 192 def _comparison_level_expression_parser(index, tokens):
 193     return _left_recursive_infix_operator_parser(
 194         lambda token: token.type == 'comparison_level_operator',
 195         _addition_level_expression_parser,
 196         'comparison_level',
 197     )(index, tokens)
 198
 199 def _and_level_expression_parser(index, tokens):
 200     return _left_recursive_infix_operator_parser(
 201         lambda token: token.type == 'symbol' and token.match == 'and',
 202         _comparison_level_expression_parser,
 203         'and_level',
 204     )(index, tokens)
 205
 206 def _or_level_expression_parser(index, tokens):
 207     return _left_recursive_infix_operator_parser(
 208         lambda token: token.type == 'symbol' and token.match == 'or',
 209         _and_level_expression_parser,
 210         'or_level',
 211     )(index, tokens)
 212
 213 def _comma_separated_list_parser(subparser):
 214     def result_parser(index, tokens):
 215         start_index = index
 216
 217         items = []
 218
 219         success, index, item = subparser(index, tokens)
 220
 221         if success:
 222             items.append(item)
 223         else:
 224             return (True, start_index, ())
 225
 226         while success and index < len(tokens) and tokens[index].type == 'comma':
 227             success = False
 228
 229             if index + 1 < len(tokens):
 230                 success, try_index, item = subparser(index + 1, tokens)
 231
 232             if success:
 233                 items.append(item)
 234                 index = try_index
 235
 236         return True, index, tuple(items)
 237
 238     return result_parser
 239
 240 def _comma_separated_expression_list_parser(index, tokens):
 241     return _comma_separated_list_parser(_expression_parser)(index, tokens)
 242
 243 FurFunctionCallExpression = collections.namedtuple(
 244     'FurFunctionCallExpression',
 245     [
 246         'function',
 247         'arguments',
 248     ],
 249 )
 250
 251 FurExpressionStatement = collections.namedtuple(
 252     'FurExpressionStatement',
 253     [
 254         'expression',
 255     ],
 256 )
 257
 258 FurAssignmentStatement = collections.namedtuple(
 259     'FurAssignmentStatement',
 260     [
 261         'target',
 262         'expression',
 263     ],
 264 )
 265
 266 FurFunctionDefinitionStatement = collections.namedtuple(
 267     'FurFunctionDefinitionStatement',
 268     [
 269         'name',
 270         'argument_name_list',
 271         'statement_list',
 272     ],
 273 )
 274
 275 FurProgram = collections.namedtuple(
 276     'FurProgram',
 277     [
 278         'statement_list',
 279     ],
 280 )
 281
 282 def _function_call_expression_parser(index, tokens):
 283     failure = (False, index, None)
 284
 285     # We have to be careful what expressions we add here. Otherwise expressions
 286     # like "a + b()" become ambiguous to the parser.
 287     success, index, function = _or_parser(
 288         _symbol_expression_parser,
 289         _parenthesized_expression_parser,
 290     )(index, tokens)
 291
 292     if not success:
 293         return failure
 294
 295     success, index, arguments = _parenthese_wrapped_parser(_comma_separated_expression_list_parser)(
 296         index,
 297         tokens,
 298     )
 299
 300     if not success:
 301         return failure
 302
 303     while success and index < len(tokens):
 304         # "function" is actually the full function call if the next parse attempt doesn't succeed
 305         # We can't give this a better name without a bunch of checks, however.
 306         function = FurFunctionCallExpression(
 307             function=function,
 308             arguments=arguments,
 309         )
 310
 311         success, index, arguments = _parenthese_wrapped_parser(_comma_separated_expression_list_parser)(
 312             index,
 313             tokens,
 314         )
 315
 316     return True, index, function
 317
 318 _expression_parser = _or_level_expression_parser
 319
 320 def _expression_statement_parser(index, tokens):
 321     failure = (False, index, None)
 322
 323     success, index, expression = _expression_parser(index, tokens)
 324
 325     if not success:
 326         return failure
 327
 328     return (True, index, FurExpressionStatement(expression=expression))
 329
 330 BUILTINS = {'print', 'pow'}
 331
 332 def _assignment_statement_parser(index, tokens):
 333     failure = (False, index, None)
 334
 335     if tokens[index].type == 'symbol':
 336         target = tokens[index].match
 337         target_assignment_line = tokens[index].line
 338
 339         index += 1
 340     else:
 341         return failure
 342
 343
 344     if tokens[index].type == 'assignment_operator':
 345         if target in BUILTINS:
 346             raise Exception(
 347                 'Trying to assign to builtin "{}" on line {}'.format(target, target_assignment_line),
 348             )
 349         assignment_operator_index = index
 350     else:
 351         return failure
 352
 353     success, index, expression = _expression_parser(index + 1, tokens)
 354
 355     if not success:
 356         raise Exception(
 357             'Expected expression after assignment operator on line {}'.format(
 358                 tokens[assignment_operator_index].line
 359             )
 360         )
 361
 362     return True, index, FurAssignmentStatement(target=target, expression=expression)
 363
 364 def _function_definition_statement_parser(index, tokens):
 365     failure = (False, index, None)
 366
 367     if tokens[index].type == 'keyword' and tokens[index].match == 'def':
 368         index += 1
 369     else:
 370         return failure
 371
 372     if tokens[index].type == 'symbol':
 373         name = tokens[index].match
 374         index += 1
 375     else:
 376         raise Exception('Expected function name, found "{}" on line {}'.format(
 377             tokens[index].match,
 378             tokens[index].line,
 379         ))
 380
 381     if tokens[index].type == 'open_parenthese':
 382         index += 1
 383     else:
 384         raise Exception('Expected "(", found "{}" on line {}'.format(
 385             tokens[index].match,
 386             tokens[index].line,
 387         ))
 388
 389     success, index, argument_name_list = _comma_separated_list_parser(_symbol_expression_parser)(
 390         index,
 391         tokens,
 392     )
 393
 394     if tokens[index].type == 'close_parenthese':
 395         index += 1
 396     else:
 397         raise Exception('Expected ")", found "{}" on line {}'.format(
 398             tokens[index].match,
 399             tokens[index].line,
 400         ))
 401
 402     if tokens[index].type == 'symbol' and tokens[index].match == 'do':
 403         index += 1
 404     else:
 405         return failure
 406
 407     success, index, statement_list = _zero_or_more_parser(tuple, _statement_parser)(index, tokens)
 408
 409     _, index, _ = consume_newlines(index, tokens)
 410
 411     if tokens[index].type == 'keyword' and tokens[index].match == 'end':
 412         index += 1
 413     else:
 414         return failure
 415
 416     return True, index, FurFunctionDefinitionStatement(
 417         name=name,
 418         argument_name_list=tuple(an.value for an in argument_name_list),
 419         statement_list=statement_list,
 420     )
 421
 422 def _statement_parser(index, tokens):
 423     _, index, _ = consume_newlines(index, tokens)
 424
 425     if index == len(tokens):
 426         return (False, index, None)
 427
 428     return _or_parser(
 429         _assignment_statement_parser,
 430         _expression_statement_parser,
 431         _function_definition_statement_parser,
 432     )(index, tokens)
 433
 434 def _program_formatter(statement_list):
 435     return FurProgram(statement_list=statement_list)
 436
 437 _program_parser = _zero_or_more_parser(_program_formatter, _statement_parser)
 438
 439 def _parse(parser, tokens):
 440     success, index, result = parser(0, tokens)
 441
 442     if index < len(tokens):
 443         raise Exception('Unable to parse token {}'.format(tokens[index]))
 444
 445     if success:
 446         return result
 447
 448     raise Exception('Unable to parse')
 449
 450 def parse(tokens):
 451     return _parse(_program_parser, tokens)
 452
 453 if __name__ == '__main__':
 454     import unittest
 455
 456     import tokenization
 457
 458     class FurStringLiteralExpressionParserTests(unittest.TestCase):
 459         def test_parses_single_quoted_string_literal(self):
 460             self.assertEqual(
 461                 _string_literal_expression_parser(0, tokenization.tokenize("'Hello, world'")),
 462                 (
 463                     True,
 464                     1,
 465                     FurStringLiteralExpression(value='Hello, world'),
 466                 ),
 467             )
 468
 469     class FurFunctionCallExpressionParserTests(unittest.TestCase):
 470         def test_parses_function_with_string_literal_argument(self):
 471             self.assertEqual(
 472                 _function_call_expression_parser(0, tokenization.tokenize("print('Hello, world')")),
 473                 (
 474                     True,
 475                     4,
 476                     FurFunctionCallExpression(
 477                         name='print',
 478                         arguments=(FurStringLiteralExpression(value='Hello, world'),),
 479                     ),
 480                 ),
 481             )
 482
 483     unittest.main()