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         'integer',
  43     ],
  44 )
  45
  46 FurStringLiteralExpression = collections.namedtuple(
  47     'FurStringLiteralExpression',
  48     [
  49         'string',
  50     ],
  51 )
  52
  53 FurSymbolExpression = collections.namedtuple(
  54     'FurSymbolExpression',
  55     [
  56         'metadata',
  57         'symbol',
  58     ],
  59 )
  60
  61 FurNegationExpression = collections.namedtuple(
  62     'FurNegationExpression',
  63     [
  64         'metadata',
  65         'value',
  66     ],
  67 )
  68
  69 FurInfixExpression = collections.namedtuple(
  70     'FurInfixExpression',
  71     [
  72         'metadata',
  73         'order',
  74         'operator',
  75         'left',
  76         'right',
  77     ],
  78 )
  79
  80 FurListLiteralExpression = collections.namedtuple(
  81     'FurListLiteralExpression',
  82     [
  83         'item_expression_list',
  84     ],
  85 )
  86
  87 FurIfExpression = collections.namedtuple(
  88     'FurIfExpression',
  89     [
  90         'condition_expression',
  91         'if_statement_list',
  92         'else_statement_list',
  93     ],
  94 )
  95
  96 FurSymbolExpressionPair = collections.namedtuple(
  97     'FurSymbolExpressionPair',
  98     [
  99         'symbol',
 100         'expression',
 101     ],
 102 )
 103
 104 FurStructureLiteralExpression = collections.namedtuple(
 105     'FurStructureLiteralExpression',
 106     [
 107         'fields',
 108     ],
 109 )
 110
 111 def _integer_literal_expression_parser(index, tokens):
 112     failure = (False, index, None)
 113
 114     if tokens[index].type != 'integer_literal':
 115         return failure
 116     value = int(tokens[index].match)
 117     index += 1
 118
 119     return True, index, FurIntegerLiteralExpression(integer=value)
 120
 121 def _string_literal_expression_parser(index, tokens):
 122     if tokens[index].type == 'double_quoted_string_literal':
 123         return (True, index + 1, FurStringLiteralExpression(string=tokens[index].match[1:-1]))
 124
 125     if tokens[index].type == 'single_quoted_string_literal':
 126         return (True, index + 1, FurStringLiteralExpression(string=tokens[index].match[1:-1]))
 127
 128     return (False, index, None)
 129
 130 def _symbol_expression_parser(index, tokens):
 131     if tokens[index].type == 'symbol':
 132         return (
 133             True,
 134             index + 1,
 135             FurSymbolExpression(
 136                 metadata=tokens[index].metadata,
 137                 symbol=tokens[index].match,
 138             ),
 139         )
 140
 141     return (False, index, None)
 142
 143 def _wrapped_parser(open_token, close_token, internal_parser):
 144     def result_parser(index, tokens):
 145         failure = (False, index, None)
 146
 147         if tokens[index].type == open_token:
 148             index += 1
 149         else:
 150             return failure
 151
 152         success, index, internal = internal_parser(index, tokens)
 153         if not success:
 154             return failure
 155
 156         if tokens[index].type == close_token:
 157             index += 1
 158         else:
 159             # TODO Put the actual expected character in the error message
 160             raise Exception('Expected closing token on line {}, found "{}"'.format(
 161                 tokens[index].line,
 162                 tokens[index].match,
 163             ))
 164
 165         return True, index, internal
 166
 167     return result_parser
 168
 169 def _bracket_wrapped_parser(internal_parser):
 170     return _wrapped_parser('open_bracket', 'close_bracket', internal_parser)
 171
 172 def _parenthese_wrapped_parser(internal_parser):
 173     return _wrapped_parser('open_parenthese', 'close_parenthese', internal_parser)
 174
 175 def _parenthesized_expression_parser(index, tokens):
 176     return _parenthese_wrapped_parser(_expression_parser)(index, tokens)
 177
 178 def symbol_expression_pair_parser(index, tokens):
 179     failure = (False, index, None)
 180
 181     if tokens[index].type == 'symbol':
 182         symbol = tokens[index].match
 183         index += 1
 184     else:
 185         return failure
 186
 187     if tokens[index].type == 'colon':
 188         index += 1
 189     else:
 190         return failure
 191
 192     success, index, expression = _expression_parser(index, tokens)
 193
 194     if not success:
 195         raise Exception()
 196
 197     return (
 198         True,
 199         index,
 200         FurSymbolExpressionPair(
 201             symbol=symbol,
 202             expression=expression,
 203         ),
 204     )
 205
 206 def _structure_literal_parser(index, tokens):
 207     success, index, result = _parenthese_wrapped_parser(_comma_separated_list_parser(symbol_expression_pair_parser))(index, tokens)
 208     return (
 209         success,
 210         index,
 211         FurStructureLiteralExpression(
 212             fields=result,
 213         ),
 214     )
 215
 216 def _list_literal_expression_parser(index, tokens):
 217     failure = (False, index, None)
 218
 219     success, index, item_expression_list = _bracket_wrapped_parser(_comma_separated_expression_list_parser)(index, tokens)
 220
 221     if success:
 222         return success, index, FurListLiteralExpression(
 223             item_expression_list=item_expression_list,
 224         )
 225     else:
 226         return failure
 227
 228 def _literal_level_expression_parser(index, tokens):
 229     return _or_parser(
 230         _list_item_expression_parser,
 231         _function_call_expression_parser,
 232         _parenthesized_expression_parser,
 233         _integer_literal_expression_parser,
 234         _string_literal_expression_parser,
 235         _list_literal_expression_parser,
 236         _symbol_expression_parser,
 237         _structure_literal_parser,
 238     )(index, tokens)
 239
 240 def _dot_expression_parser(index, tokens):
 241     return _left_recursive_infix_operator_parser(
 242         lambda token: token.type == 'period',
 243         _literal_level_expression_parser,
 244         'dot_level',
 245     )(index, tokens)
 246
 247 def _negation_expression_parser(index, tokens):
 248     failure = (False, index, None)
 249
 250     if tokens[index].match != '-':
 251         return failure
 252
 253     metadata = tokens[index].metadata
 254
 255     success, index, value = _dot_expression_parser(index + 1, tokens)
 256
 257     if not success:
 258         return failure
 259
 260     return (True, index, FurNegationExpression(metadata=metadata, value=value))
 261
 262 def _negation_level_expression_parser(index, tokens):
 263     return _or_parser(
 264         _dot_expression_parser,
 265         _negation_expression_parser,
 266     )(index, tokens)
 267
 268 def _left_recursive_infix_operator_parser(operator_token_matcher, operand_parser, order):
 269     def result_parser(index, tokens):
 270         failure = (False, index, None)
 271
 272         success, index, result = operand_parser(index, tokens)
 273
 274         if not success:
 275             return failure
 276
 277         while success and index < len(tokens) and operator_token_matcher(tokens[index]):
 278             success = False
 279
 280             if index + 1 < len(tokens):
 281                 success, try_index, value = operand_parser(index + 1, tokens)
 282
 283             if success:
 284                 result = FurInfixExpression(
 285                     metadata=tokens[index].metadata,
 286                     order=order,
 287                     operator=tokens[index].match,
 288                     left=result,
 289                     right=value,
 290                 )
 291                 index = try_index
 292
 293         return True, index, result
 294
 295     return result_parser
 296
 297 def _multiplication_level_expression_parser(index, tokens):
 298     return _left_recursive_infix_operator_parser(
 299         lambda token: token.type == 'multiplication_level_operator',
 300         _negation_level_expression_parser,
 301         'multiplication_level',
 302     )(index, tokens)
 303
 304 def _addition_level_expression_parser(index, tokens):
 305     return _left_recursive_infix_operator_parser(
 306         lambda token: token.type == 'addition_level_operator',
 307         _multiplication_level_expression_parser,
 308         'addition_level',
 309     )(index, tokens)
 310
 311 def _comparison_level_expression_parser(index, tokens):
 312     return _left_recursive_infix_operator_parser(
 313         lambda token: token.type == 'comparison_level_operator',
 314         _addition_level_expression_parser,
 315         'comparison_level',
 316     )(index, tokens)
 317
 318 def _and_level_expression_parser(index, tokens):
 319     return _left_recursive_infix_operator_parser(
 320         lambda token: token.type == 'symbol' and token.match == 'and',
 321         _comparison_level_expression_parser,
 322         'and_level',
 323     )(index, tokens)
 324
 325 def _or_level_expression_parser(index, tokens):
 326     return _left_recursive_infix_operator_parser(
 327         lambda token: token.type == 'symbol' and token.match == 'or',
 328         _and_level_expression_parser,
 329         'or_level',
 330     )(index, tokens)
 331
 332 def _comma_separated_list_parser(subparser):
 333     def result_parser(index, tokens):
 334         start_index = index
 335
 336         items = []
 337
 338         _, index, _ = consume_newlines(index, tokens)
 339
 340         success, index, item = subparser(index, tokens)
 341
 342         if success:
 343             items.append(item)
 344         else:
 345             return (True, start_index, ())
 346
 347         while success and index < len(tokens) and tokens[index].type == 'comma':
 348             index += 1
 349             success = False
 350
 351             _, index, _ = consume_newlines(index, tokens)
 352
 353             if index < len(tokens):
 354                 success, try_index, item = subparser(index, tokens)
 355
 356             if success:
 357                 items.append(item)
 358                 index = try_index
 359
 360         return True, index, tuple(items)
 361
 362     return result_parser
 363
 364 def _comma_separated_expression_list_parser(index, tokens):
 365     return _comma_separated_list_parser(_expression_parser)(index, tokens)
 366
 367 FurListItemExpression = collections.namedtuple(
 368     'FurListItemExpression',
 369     [
 370         'list_expression',
 371         'metadata',
 372         'index_expression',
 373     ],
 374 )
 375
 376 FurFunctionCallExpression = collections.namedtuple(
 377     'FurFunctionCallExpression',
 378     [
 379         'metadata',
 380         'function',
 381         'arguments',
 382     ],
 383 )
 384
 385 FurExpressionStatement = collections.namedtuple(
 386     'FurExpressionStatement',
 387     [
 388         'expression',
 389     ],
 390 )
 391
 392 FurAssignmentStatement = collections.namedtuple(
 393     'FurAssignmentStatement',
 394     [
 395         'target',
 396         'expression',
 397     ],
 398 )
 399
 400 FurFunctionDefinitionStatement = collections.namedtuple(
 401     'FurFunctionDefinitionStatement',
 402     [
 403         'name',
 404         'argument_name_list',
 405         'statement_list',
 406     ],
 407 )
 408
 409 FurProgram = collections.namedtuple(
 410     'FurProgram',
 411     [
 412         'statement_list',
 413     ],
 414 )
 415
 416 def _list_item_expression_parser(index, tokens):
 417     failure = (False, index, None)
 418
 419     # We have to be careful what expressions we add here. Otherwise expressions
 420     # like "a + b[0]" become ambiguous to the parser.
 421     success, index, list_expression = _or_parser(
 422         _symbol_expression_parser,
 423         _parenthesized_expression_parser,
 424     )(index, tokens)
 425
 426     if not success:
 427         return failure
 428
 429     metadata = tokens[index].metadata
 430
 431     success, index, index_expression = _bracket_wrapped_parser(_expression_parser)(
 432         index,
 433         tokens,
 434     )
 435
 436     if not success:
 437         return failure
 438
 439     while success and index < len(tokens):
 440         # "list_expression" is actually the full list item expression if the next parse attempt doesn't succeed
 441         # We can't give this a better name without a bunch of checks, however.
 442         list_expression = FurListItemExpression(
 443             list_expression=list_expression,
 444             metadata=metadata,
 445             index_expression=index_expression,
 446         )
 447
 448         metadata = tokens[index].metadata
 449
 450         success, index, index_expression = _bracket_wrapped_parser(_expression_parser)(
 451             index,
 452             tokens,
 453         )
 454
 455     return True, index, list_expression
 456
 457 def _function_call_expression_parser(index, tokens):
 458     failure = (False, index, None)
 459
 460     # We have to be careful what expressions we add here. Otherwise expressions
 461     # like "a + b()" become ambiguous to the parser.
 462     success, index, function = _or_parser(
 463         _symbol_expression_parser,
 464         _parenthesized_expression_parser,
 465     )(index, tokens)
 466
 467     if not success:
 468         return failure
 469
 470     metadata = tokens[index].metadata
 471
 472     success, index, arguments = _parenthese_wrapped_parser(_comma_separated_expression_list_parser)(
 473         index,
 474         tokens,
 475     )
 476
 477     if not success:
 478         return failure
 479
 480     while success and index < len(tokens):
 481         # "function" is actually the full function call if the next parse attempt doesn't succeed
 482         # We can't give this a better name without a bunch of checks, however.
 483         function = FurFunctionCallExpression(
 484             metadata=metadata,
 485             function=function,
 486             arguments=arguments,
 487         )
 488
 489         metadata = tokens[index].metadata
 490
 491         success, index, arguments = _parenthese_wrapped_parser(_comma_separated_expression_list_parser)(
 492             index,
 493             tokens,
 494         )
 495
 496     return True, index, function
 497
 498 def _if_expression_parser(index, tokens):
 499     failure = (False, index, None)
 500
 501     if tokens[index].match == 'if':
 502         index += 1
 503     else:
 504         return failure
 505
 506     success, index, condition_expression = _or_level_expression_parser(index, tokens)
 507
 508     if not success:
 509         raise Exception('Expected condition after "if" on line {}'.format(tokens[index].line))
 510
 511     if tokens[index].match == 'do':
 512         index += 1
 513     else:
 514         raise Exception('Expected "do" after "if" on line {}'.format(tokens[index].line))
 515
 516
 517     success, index, if_statement_list = _zero_or_more_parser(tuple, _statement_parser)(index, tokens)
 518     _, index, _ = consume_newlines(index, tokens)
 519
 520     if tokens[index].match == 'else':
 521         index += 1
 522         success, index, else_statement_list = _zero_or_more_parser(tuple, _statement_parser)(index, tokens)
 523         _, index, _ = consume_newlines(index, tokens)
 524     else:
 525         else_statement_list = ()
 526
 527     if tokens[index].match == 'end':
 528         index += 1
 529     else:
 530         raise Exception('Expected "end" after "if" on line {}'.format(tokens[index].line))
 531
 532     return (
 533         True,
 534         index,
 535         FurIfExpression(
 536             condition_expression=condition_expression,
 537             if_statement_list=if_statement_list,
 538             else_statement_list=else_statement_list,
 539         ),
 540     )
 541
 542 _expression_parser = _or_parser(
 543     _or_level_expression_parser,
 544     _if_expression_parser, # This should always be at the top level
 545 )
 546
 547 def _expression_statement_parser(index, tokens):
 548     failure = (False, index, None)
 549
 550     success, index, expression = _expression_parser(index, tokens)
 551
 552     if not success:
 553         return failure
 554
 555     return (True, index, FurExpressionStatement(expression=expression))
 556
 557 BUILTINS = {'print', 'pow'}
 558
 559 def _assignment_statement_parser(index, tokens):
 560     failure = (False, index, None)
 561
 562     if tokens[index].type == 'symbol':
 563         target = tokens[index].match
 564         target_assignment_line = tokens[index].metadata.line
 565
 566         index += 1
 567     else:
 568         return failure
 569
 570
 571     if tokens[index].type == 'assignment_operator':
 572         if target in BUILTINS:
 573             raise Exception(
 574                 'Trying to assign to builtin "{}" on line {}'.format(target, target_assignment_line),
 575             )
 576         assignment_operator_index = index
 577     else:
 578         return failure
 579
 580     success, index, expression = _expression_parser(index + 1, tokens)
 581
 582     if not success:
 583         raise Exception(
 584             'Expected expression after assignment operator on line {}'.format(
 585                 tokens[assignment_operator_index].line
 586             )
 587         )
 588
 589     return True, index, FurAssignmentStatement(target=target, expression=expression)
 590
 591 def _function_definition_statement_parser(index, tokens):
 592     failure = (False, index, None)
 593
 594     if tokens[index].type == 'keyword' and tokens[index].match == 'def':
 595         index += 1
 596     else:
 597         return failure
 598
 599     if tokens[index].type == 'symbol':
 600         name = tokens[index].match
 601         index += 1
 602     else:
 603         raise Exception('Expected function name, found "{}" on line {}'.format(
 604             tokens[index].match,
 605             tokens[index].line,
 606         ))
 607
 608     if tokens[index].type == 'open_parenthese':
 609         index += 1
 610     else:
 611         raise Exception('Expected "(", found "{}" on line {}'.format(
 612             tokens[index].match,
 613             tokens[index].line,
 614         ))
 615
 616     success, index, argument_name_list = _comma_separated_list_parser(_symbol_expression_parser)(
 617         index,
 618         tokens,
 619     )
 620
 621     if tokens[index].type == 'close_parenthese':
 622         index += 1
 623     else:
 624         raise Exception('Expected ")", found "{}" on line {}'.format(
 625             tokens[index].match,
 626             tokens[index].line,
 627         ))
 628
 629     if tokens[index].match == 'do':
 630         index += 1
 631     else:
 632         return failure
 633
 634     success, index, statement_list = _zero_or_more_parser(tuple, _statement_parser)(index, tokens)
 635
 636     _, index, _ = consume_newlines(index, tokens)
 637
 638     if tokens[index].type == 'keyword' and tokens[index].match == 'end':
 639         index += 1
 640     else:
 641         return failure
 642
 643     return True, index, FurFunctionDefinitionStatement(
 644         name=name,
 645     argument_name_list=tuple(an.symbol for an in argument_name_list),
 646         statement_list=statement_list,
 647     )
 648
 649 def _statement_parser(index, tokens):
 650     _, index, _ = consume_newlines(index, tokens)
 651
 652     if index == len(tokens):
 653         return (False, index, None)
 654
 655     return _or_parser(
 656         _assignment_statement_parser,
 657         _expression_statement_parser,
 658         _function_definition_statement_parser,
 659     )(index, tokens)
 660
 661 def _program_formatter(statement_list):
 662     return FurProgram(statement_list=statement_list)
 663
 664 _program_parser = _zero_or_more_parser(_program_formatter, _statement_parser)
 665
 666 def _parse(parser, tokens):
 667     success, index, result = parser(0, tokens)
 668
 669     if index < len(tokens):
 670         raise Exception('Unable to parse token {}'.format(tokens[index]))
 671
 672     if success:
 673         return result
 674
 675     raise Exception('Unable to parse')
 676
 677 def parse(tokens):
 678     return _parse(_program_parser, tokens)
 679
 680 if __name__ == '__main__':
 681     import unittest
 682
 683     import tokenization
 684
 685     class FurStringLiteralExpressionParserTests(unittest.TestCase):
 686         def test_parses_single_quoted_string_literal(self):
 687             self.assertEqual(
 688                 _string_literal_expression_parser(0, tokenization.tokenize("'Hello, world'")),
 689                 (
 690                     True,
 691                     1,
 692                     FurStringLiteralExpression(string='Hello, world'),
 693                 ),
 694             )
 695
 696     class FurFunctionCallExpressionParserTests(unittest.TestCase):
 697         def test_parses_function_with_string_literal_argument(self):
 698             self.assertEqual(
 699                 _function_call_expression_parser(0, tokenization.tokenize("print('Hello, world')")),
 700                 (
 701                     True,
 702                     4,
 703                     FurFunctionCallExpression(
 704                         name='print',
 705                         arguments=(FurStringLiteralExpression(string='Hello, world'),),
 706                     ),
 707                 ),
 708             )
 709
 710     unittest.main()