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