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