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