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