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