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