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(index, tokens):
 216     start_index = index
 217
 218     expressions = []
 219
 220     success, index, expression = _expression_parser(index, tokens)
 221
 222     if success:
 223         expressions.append(expression)
 224     else:
 225         return (True, start_index, ())
 226
 227     while success and index < len(tokens) and tokens[index].type == 'comma':
 228         success = False
 229
 230         if index + 1 < len(tokens):
 231             success, try_index, expression = _expression_parser(index + 1, tokens)
 232
 233         if success:
 234             expressions.append(expression)
 235             index = try_index
 236
 237     return True, index, tuple(expressions)
 238
 239
 240 FurFunctionCallExpression = collections.namedtuple(
 241     'FurFunctionCallExpression',
 242     [
 243         'function',
 244         'arguments',
 245     ],
 246 )
 247
 248 FurExpressionStatement = collections.namedtuple(
 249     'FurExpressionStatement',
 250     [
 251         'expression',
 252     ],
 253 )
 254
 255 FurAssignmentStatement = collections.namedtuple(
 256     'FurAssignmentStatement',
 257     [
 258         'target',
 259         'expression',
 260     ],
 261 )
 262
 263 FurFunctionDefinitionStatement = collections.namedtuple(
 264     'FurFunctionDefinitionStatement',
 265     [
 266         'name',
 267         'statement_list',
 268     ],
 269 )
 270
 271 FurProgram = collections.namedtuple(
 272     'FurProgram',
 273     [
 274         'statement_list',
 275     ],
 276 )
 277
 278 def _function_call_expression_parser(index, tokens):
 279     # TODO Use a FurSymbolExpression for the name
 280     failure = (False, index, None)
 281
 282     success, index, function = _symbol_expression_parser(index, tokens)
 283
 284     if not success:
 285         return failure
 286
 287     if tokens[index].type != 'open_parenthese':
 288         return failure
 289     index += 1
 290
 291     success, index, arguments = _comma_separated_list_parser(index, tokens)
 292
 293     if not success:
 294         return failure
 295
 296     if tokens[index].type != 'close_parenthese':
 297         raise Exception('Expected ")", found "{}" on line {}'.format(
 298             tokens[index].match,
 299             tokens[index].line,
 300         ))
 301     index += 1
 302
 303     return True, index, FurFunctionCallExpression(function=function, arguments=arguments)
 304
 305 _expression_parser = _or_level_expression_parser
 306
 307 def _expression_statement_parser(index, tokens):
 308     failure = (False, index, None)
 309
 310     success, index, expression = _expression_parser(index, tokens)
 311
 312     if not success:
 313         return failure
 314
 315     return (True, index, FurExpressionStatement(expression=expression))
 316
 317 def _assignment_statement_parser(index, tokens):
 318     # TODO Use a FurSymbolExpression for the target? Maybe this is actually not a good idea
 319     failure = (False, index, None)
 320
 321     if tokens[index].type != 'symbol':
 322         return failure
 323     target = tokens[index].match
 324     index += 1
 325
 326     if tokens[index].type != 'assignment_operator':
 327         return failure
 328     assignment_operator_index = index
 329
 330     success, index, expression = _expression_parser(index + 1, tokens)
 331
 332     if not success:
 333         raise Exception(
 334             'Expected expression after assignment operator on line {}'.format(
 335                 tokens[assignment_operator_index].line
 336             )
 337         )
 338
 339     return True, index, FurAssignmentStatement(target=target, expression=expression)
 340
 341 def _function_definition_statement_parser(index, tokens):
 342     failure = (False, index, None)
 343
 344     if tokens[index].type == 'keyword' and tokens[index].match == 'def':
 345         index += 1
 346     else:
 347         return failure
 348
 349     if tokens[index].type == 'symbol':
 350         name = tokens[index].match
 351         index += 1
 352     else:
 353         raise Exception('Expected function name, found "{}" on line {}'.format(
 354             tokens[index].match,
 355             tokens[index].line,
 356         ))
 357
 358     if tokens[index].type == 'open_parenthese':
 359         index += 1
 360     else:
 361         raise Exception('Expected "(", found "{}" on line {}'.format(
 362             tokens[index].match,
 363             tokens[index].line,
 364         ))
 365
 366     if tokens[index].type == 'close_parenthese':
 367         index += 1
 368     else:
 369         raise Exception('Expected ")", found "{}" on line {}'.format(
 370             tokens[index].match,
 371             tokens[index].line,
 372         ))
 373
 374     if tokens[index].type == 'symbol' and tokens[index].match == 'do':
 375         index += 1
 376     else:
 377         return failure
 378
 379     success, index, statement_list = _zero_or_more_parser(tuple, _statement_parser)(index, tokens)
 380
 381     _, index, _ = consume_newlines(index, tokens)
 382
 383     if tokens[index].type == 'keyword' and tokens[index].match == 'end':
 384         index += 1
 385     else:
 386         return failure
 387
 388     return True, index, FurFunctionDefinitionStatement(name=name, statement_list=statement_list)
 389
 390 def _statement_parser(index, tokens):
 391     _, index, _ = consume_newlines(index, tokens)
 392
 393     if index == len(tokens):
 394         return (False, index, None)
 395
 396     return _or_parser(
 397         _assignment_statement_parser,
 398         _expression_statement_parser,
 399         _function_definition_statement_parser,
 400     )(index, tokens)
 401
 402 def _program_formatter(statement_list):
 403     return FurProgram(statement_list=statement_list)
 404
 405 _program_parser = _zero_or_more_parser(_program_formatter, _statement_parser)
 406
 407 def _parse(parser, tokens):
 408     success, index, result = parser(0, tokens)
 409
 410     if index < len(tokens):
 411         raise Exception('Unable to parse token {}'.format(tokens[index]))
 412
 413     if success:
 414         return result
 415
 416     raise Exception('Unable to parse')
 417
 418 def parse(tokens):
 419     return _parse(_program_parser, tokens)
 420
 421 if __name__ == '__main__':
 422     import unittest
 423
 424     import tokenization
 425
 426     class FurStringLiteralExpressionParserTests(unittest.TestCase):
 427         def test_parses_single_quoted_string_literal(self):
 428             self.assertEqual(
 429                 _string_literal_expression_parser(0, tokenization.tokenize("'Hello, world'")),
 430                 (
 431                     True,
 432                     1,
 433                     FurStringLiteralExpression(value='Hello, world'),
 434                 ),
 435             )
 436
 437     class FurFunctionCallExpressionParserTests(unittest.TestCase):
 438         def test_parses_function_with_string_literal_argument(self):
 439             self.assertEqual(
 440                 _function_call_expression_parser(0, tokenization.tokenize("print('Hello, world')")),
 441                 (
 442                     True,
 443                     4,
 444                     FurFunctionCallExpression(
 445                         name='print',
 446                         arguments=(FurStringLiteralExpression(value='Hello, world'),),
 447                     ),
 448                 ),
 449             )
 450
 451     unittest.main()