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