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