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