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