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