code.kerkeslager.com Git - fur/blob - parsing.py

   1 import collections
   2
   3 def _or_parser(*parsers):
   4     def result_parser(index, tokens):
   5         failure = (False, index, None)
   6
   7         for parser in parsers:
   8             success, index, value = parser(index, tokens)
   9
  10             if success:
  11                 return (success, index, value)
  12
  13         return failure
  14
  15     return result_parser
  16
  17 def _zero_or_more_parser(formatter, parser):
  18     def result_parser(index, tokens):
  19         values = []
  20
  21         while index < len(tokens):
  22             success, index, value = parser(index, tokens)
  23
  24             if success:
  25                 values.append(value)
  26             else:
  27                 break
  28
  29         return (True, index, formatter(values))
  30
  31     return result_parser
  32
  33 FurIntegerLiteralExpression = collections.namedtuple(
  34     'FurIntegerLiteralExpression',
  35     [
  36         'value',
  37     ],
  38 )
  39
  40 FurStringLiteralExpression = collections.namedtuple(
  41     'FurStringLiteralExpression',
  42     [
  43         'value',
  44     ],
  45 )
  46
  47 FurSymbolExpression = collections.namedtuple(
  48     'FurSymbolExpression',
  49     [
  50         'value',
  51     ],
  52 )
  53
  54 FurNegationExpression = collections.namedtuple(
  55     'FurNegationExpression',
  56     [
  57         'value',
  58     ],
  59 )
  60
  61 FurParenthesizedExpression = collections.namedtuple(
  62     'FurParenthesizedExpression',
  63     [
  64         'internal',
  65     ],
  66 )
  67
  68 FurAdditionExpression = collections.namedtuple(
  69     'FurAdditionExpression',
  70     [
  71         'left',
  72         'right',
  73     ],
  74 )
  75
  76 FurSubtractionExpression = collections.namedtuple(
  77     'FurSubtractionExpression',
  78     [
  79         'left',
  80         'right',
  81     ],
  82 )
  83
  84 FurMultiplicationExpression = collections.namedtuple(
  85     'FurMultiplicationExpression',
  86     [
  87         'left',
  88         'right',
  89     ],
  90 )
  91
  92 FurIntegerDivisionExpression = collections.namedtuple(
  93     'FurIntegerDivisionExpression',
  94     [
  95         'left',
  96         'right',
  97     ],
  98 )
  99
 100 FurModularDivisionExpression = collections.namedtuple(
 101     'FurModularDivisionExpression',
 102     [
 103         'left',
 104         'right',
 105     ],
 106 )
 107
 108 FurEqualityExpression = collections.namedtuple(
 109     'FurEqualityExpression',
 110     [
 111         'left',
 112         'right',
 113     ],
 114 )
 115
 116 FurInequalityExpression = collections.namedtuple(
 117     'FurInequalityExpression',
 118     [
 119         'left',
 120         'right',
 121     ],
 122 )
 123
 124 FurLessThanOrEqualExpression = collections.namedtuple(
 125     'FurLessThanOrEqualExpression',
 126     [
 127         'left',
 128         'right',
 129     ],
 130 )
 131
 132 FurGreaterThanOrEqualExpression = collections.namedtuple(
 133     'FurGreaterThanOrEqualExpression',
 134     [
 135         'left',
 136         'right',
 137     ],
 138 )
 139
 140 FurLessThanExpression = collections.namedtuple(
 141     'FurLessThanExpression',
 142     [
 143         'left',
 144         'right',
 145     ],
 146 )
 147
 148 FurGreaterThanExpression = collections.namedtuple(
 149     'FurGreaterThanExpression',
 150     [
 151         'left',
 152         'right',
 153     ],
 154 )
 155
 156 def _integer_literal_expression_parser(index, tokens):
 157     failure = (False, index, None)
 158
 159     if tokens[index].type != 'integer_literal':
 160         return failure
 161     value = int(tokens[index].match)
 162     index += 1
 163
 164     return True, index, FurIntegerLiteralExpression(value=value)
 165
 166 def _string_literal_expression_parser(index, tokens):
 167     if tokens[index].type == 'single_quoted_string_literal':
 168         return (True, index + 1, FurStringLiteralExpression(value=tokens[index].match[1:-1]))
 169
 170     return (False, index, None)
 171
 172 def _symbol_expression_parser(index, tokens):
 173     if tokens[index].type == 'symbol':
 174         return (True, index + 1, FurSymbolExpression(value=tokens[index].match))
 175
 176     return (False, index, None)
 177
 178 def _parenthesized_expression_parser(index, tokens):
 179     failure = (False, index, None)
 180
 181     if tokens[index].type == 'open_parenthese':
 182         index += 1
 183     else:
 184         return failure
 185
 186     success, index, internal = _expression_parser(index, tokens)
 187     if not success:
 188         return failure
 189
 190     if tokens[index].type == 'close_parenthese':
 191         index += 1
 192     else:
 193         raise Exception('Expected ")" on line {}, found "{}"'.format(
 194             tokens[index].line,
 195             tokens[index].match,
 196         ))
 197
 198     return True, index, FurParenthesizedExpression(internal=internal)
 199
 200 def _negation_expression_parser(index, tokens):
 201     failure = (False, index, None)
 202
 203     if tokens[index].match != '-':
 204         return failure
 205
 206     success, index, value = _literal_level_expression_parser(index + 1, tokens)
 207
 208     if not success:
 209         return failure
 210
 211     return (True, index, FurNegationExpression(value=value))
 212
 213 def _literal_level_expression_parser(index, tokens):
 214     return _or_parser(
 215         _negation_expression_parser,
 216         _function_call_expression_parser,
 217         _parenthesized_expression_parser,
 218         _integer_literal_expression_parser,
 219         _string_literal_expression_parser,
 220         _symbol_expression_parser,
 221     )(index, tokens)
 222
 223 def _multiplication_level_expression_parser(index, tokens):
 224     failure = (False, index, None)
 225
 226     success, index, result = _literal_level_expression_parser(index, tokens)
 227
 228     if not success:
 229         return failure
 230
 231     while success and index < len(tokens) and tokens[index].type == 'multiplication_level_operator':
 232         success = False
 233
 234         if index + 1 < len(tokens):
 235             success, try_index, value = _literal_level_expression_parser(index + 1, tokens)
 236
 237         if success:
 238             result = {
 239                 '*': FurMultiplicationExpression,
 240                 '//': FurIntegerDivisionExpression,
 241                 '%': FurModularDivisionExpression,
 242             }[tokens[index].match](left=result, right=value)
 243             index = try_index
 244
 245     return True, index, result
 246
 247 def _addition_level_expression_parser(index, tokens):
 248     failure = (False, index, None)
 249
 250     success, index, result = _multiplication_level_expression_parser(index, tokens)
 251
 252     if not success:
 253         return failure
 254
 255     while success and index < len(tokens) and tokens[index].type == 'addition_level_operator':
 256         success = False
 257
 258         if index + 1 < len(tokens):
 259             success, try_index, value = _multiplication_level_expression_parser(index + 1, tokens)
 260
 261         if success:
 262             result = {
 263                 '+': FurAdditionExpression,
 264                 '-': FurSubtractionExpression,
 265             }[tokens[index].match](left=result, right=value)
 266             index = try_index
 267
 268     return True, index, result
 269
 270 def _equality_level_expression_parser(index, tokens):
 271     failure = (False, index, None)
 272
 273     success, index, result = _addition_level_expression_parser(index, tokens)
 274
 275     if not success:
 276         return failure
 277
 278     while success and index < len(tokens) and tokens[index].type == 'equality_level_operator':
 279         success = False
 280
 281         if index + 1 < len(tokens):
 282             success, try_index, value = _addition_level_expression_parser(index + 1, tokens)
 283
 284         if success:
 285             result = {
 286                 '==': FurEqualityExpression,
 287                 '!=': FurInequalityExpression,
 288                 '>=': FurGreaterThanOrEqualExpression,
 289                 '<=': FurLessThanOrEqualExpression,
 290                 '>': FurGreaterThanExpression,
 291                 '<': FurLessThanExpression,
 292             }[tokens[index].match](left=result, right=value)
 293             index = try_index
 294
 295     return True, index, result
 296
 297
 298 def _comma_separated_list_parser(index, tokens):
 299     failure = (False, index, None)
 300
 301     expressions = []
 302
 303     success, index, expression = _expression_parser(index, tokens)
 304
 305     if success:
 306         expressions.append(expression)
 307     else:
 308         return failure
 309
 310     while success and index < len(tokens) and tokens[index].type == 'comma':
 311         success = False
 312
 313         if index + 1 < len(tokens):
 314             success, try_index, expression = _expression_parser(index + 1, tokens)
 315
 316         if success:
 317             expressions.append(expression)
 318             index = try_index
 319
 320     return True, index, tuple(expressions)
 321
 322
 323 FurFunctionCallExpression = collections.namedtuple(
 324     'FurFunctionCallExpression',
 325     [
 326         'function',
 327         'arguments',
 328     ],
 329 )
 330
 331 FurAssignmentStatement = collections.namedtuple(
 332     'FurAssignmentStatement',
 333     [
 334         'target',
 335         'expression',
 336     ],
 337 )
 338
 339 FurProgram = collections.namedtuple(
 340     'FurProgram',
 341     [
 342         'statement_list',
 343     ],
 344 )
 345
 346 def _function_call_expression_parser(index, tokens):
 347     # TODO Use a FurSymbolExpression for the name
 348     failure = (False, index, None)
 349
 350     success, index, function = _symbol_expression_parser(index, tokens)
 351
 352     if not success:
 353         return failure
 354
 355     if tokens[index].type != 'open_parenthese':
 356         return failure
 357     index += 1
 358
 359     success, index, arguments = _comma_separated_list_parser(index, tokens)
 360
 361     if not success:
 362         return failure
 363
 364     if tokens[index].type != 'close_parenthese':
 365         raise Exception('Expected ")", found "{}" on line {}'.format(
 366             tokens[index].match,
 367             tokens[index].line,
 368         ))
 369     index += 1
 370
 371     return True, index, FurFunctionCallExpression(function=function, arguments=arguments)
 372
 373 _expression_parser = _equality_level_expression_parser
 374
 375 def _assignment_statement_parser(index, tokens):
 376     # TODO Use a FurSymbolExpression for the target? Maybe this is actually not a good idea
 377     failure = (False, index, None)
 378
 379     if tokens[index].type != 'symbol':
 380         return failure
 381     target = tokens[index].match
 382     index += 1
 383
 384     if tokens[index].type != 'assignment_operator':
 385         return failure
 386     assignment_operator_index = index
 387
 388     success, index, expression = _expression_parser(index + 1, tokens)
 389
 390     if not success:
 391         raise Exception(
 392             'Expected expression after assignment operator on line {}'.format(
 393                 tokens[assignment_operator_index].line
 394             )
 395         )
 396
 397     return True, index, FurAssignmentStatement(target=target, expression=expression)
 398
 399 def _statement_parser(index, tokens):
 400     # TODO It would be good to include newlines in the parsing of this because it removes the ambiguity between "function(argument)" (one statement) and "function\n(argument)" (two statements)
 401     return _or_parser(
 402         _assignment_statement_parser,
 403         _expression_parser,
 404     )(index, tokens)
 405
 406 def _program_formatter(statement_list):
 407     return FurProgram(statement_list=statement_list)
 408
 409 _program_parser = _zero_or_more_parser(_program_formatter, _statement_parser)
 410
 411 def _parse(parser, tokens):
 412     success, index, result = parser(0, tokens)
 413
 414     if index < len(tokens):
 415         raise Exception('Unable to parse token {}'.format(tokens[index]))
 416
 417     if success:
 418         return result
 419
 420     raise Exception('Unable to parse')
 421
 422 def parse(tokens):
 423     return _parse(_program_parser, tokens)
 424
 425 if __name__ == '__main__':
 426     import unittest
 427
 428     import tokenization
 429
 430     class FurStringLiteralExpressionParserTests(unittest.TestCase):
 431         def test_parses_single_quoted_string_literal(self):
 432             self.assertEqual(
 433                 _string_literal_expression_parser(0, tokenization.tokenize("'Hello, world'")),
 434                 (
 435                     True,
 436                     1,
 437                     FurStringLiteralExpression(value='Hello, world'),
 438                 ),
 439             )
 440
 441     class FurFunctionCallExpressionParserTests(unittest.TestCase):
 442         def test_parses_function_with_string_literal_argument(self):
 443             self.assertEqual(
 444                 _function_call_expression_parser(0, tokenization.tokenize("print('Hello, world')")),
 445                 (
 446                     True,
 447                     4,
 448                     FurFunctionCallExpression(
 449                         name='print',
 450                         arguments=(FurStringLiteralExpression(value='Hello, world'),),
 451                     ),
 452                 ),
 453             )
 454
 455     unittest.main()