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(operator_token_matcher, 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 operator_token_matcher(tokens[index]):
 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         lambda token: token.type == '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         lambda token: token.type == '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         lambda token: token.type == 'equality_level_operator',
 190         _addition_level_expression_parser,
 191         'equality_level',
 192     )(index, tokens)
 193
 194 def _and_level_expression_parser(index, tokens):
 195     return _left_recursive_infix_operator_parser(
 196         lambda token: token.type == 'symbol' and token.match == 'and',
 197         _equality_level_expression_parser,
 198         'and_level',
 199     )(index, tokens)
 200
 201 def _or_level_expression_parser(index, tokens):
 202     return _left_recursive_infix_operator_parser(
 203         lambda token: token.type == 'symbol' and token.match == 'or',
 204         _and_level_expression_parser,
 205         'or_level',
 206     )(index, tokens)
 207
 208 def _comma_separated_list_parser(index, tokens):
 209     failure = (False, index, None)
 210
 211     expressions = []
 212
 213     success, index, expression = _expression_parser(index, tokens)
 214
 215     if success:
 216         expressions.append(expression)
 217     else:
 218         return failure
 219
 220     while success and index < len(tokens) and tokens[index].type == 'comma':
 221         success = False
 222
 223         if index + 1 < len(tokens):
 224             success, try_index, expression = _expression_parser(index + 1, tokens)
 225
 226         if success:
 227             expressions.append(expression)
 228             index = try_index
 229
 230     return True, index, tuple(expressions)
 231
 232
 233 FurFunctionCallExpression = collections.namedtuple(
 234     'FurFunctionCallExpression',
 235     [
 236         'function',
 237         'arguments',
 238     ],
 239 )
 240
 241 FurAssignmentStatement = collections.namedtuple(
 242     'FurAssignmentStatement',
 243     [
 244         'target',
 245         'expression',
 246     ],
 247 )
 248
 249 FurProgram = collections.namedtuple(
 250     'FurProgram',
 251     [
 252         'statement_list',
 253     ],
 254 )
 255
 256 def _function_call_expression_parser(index, tokens):
 257     # TODO Use a FurSymbolExpression for the name
 258     failure = (False, index, None)
 259
 260     success, index, function = _symbol_expression_parser(index, tokens)
 261
 262     if not success:
 263         return failure
 264
 265     if tokens[index].type != 'open_parenthese':
 266         return failure
 267     index += 1
 268
 269     success, index, arguments = _comma_separated_list_parser(index, tokens)
 270
 271     if not success:
 272         return failure
 273
 274     if tokens[index].type != 'close_parenthese':
 275         raise Exception('Expected ")", found "{}" on line {}'.format(
 276             tokens[index].match,
 277             tokens[index].line,
 278         ))
 279     index += 1
 280
 281     return True, index, FurFunctionCallExpression(function=function, arguments=arguments)
 282
 283 _expression_parser = _or_level_expression_parser
 284
 285 def _assignment_statement_parser(index, tokens):
 286     # TODO Use a FurSymbolExpression for the target? Maybe this is actually not a good idea
 287     failure = (False, index, None)
 288
 289     if tokens[index].type != 'symbol':
 290         return failure
 291     target = tokens[index].match
 292     index += 1
 293
 294     if tokens[index].type != 'assignment_operator':
 295         return failure
 296     assignment_operator_index = index
 297
 298     success, index, expression = _expression_parser(index + 1, tokens)
 299
 300     if not success:
 301         raise Exception(
 302             'Expected expression after assignment operator on line {}'.format(
 303                 tokens[assignment_operator_index].line
 304             )
 305         )
 306
 307     return True, index, FurAssignmentStatement(target=target, expression=expression)
 308
 309 def _statement_parser(index, tokens):
 310     # 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)
 311     return _or_parser(
 312         _assignment_statement_parser,
 313         _expression_parser,
 314     )(index, tokens)
 315
 316 def _program_formatter(statement_list):
 317     return FurProgram(statement_list=statement_list)
 318
 319 _program_parser = _zero_or_more_parser(_program_formatter, _statement_parser)
 320
 321 def _parse(parser, tokens):
 322     success, index, result = parser(0, tokens)
 323
 324     if index < len(tokens):
 325         raise Exception('Unable to parse token {}'.format(tokens[index]))
 326
 327     if success:
 328         return result
 329
 330     raise Exception('Unable to parse')
 331
 332 def parse(tokens):
 333     return _parse(_program_parser, tokens)
 334
 335 if __name__ == '__main__':
 336     import unittest
 337
 338     import tokenization
 339
 340     class FurStringLiteralExpressionParserTests(unittest.TestCase):
 341         def test_parses_single_quoted_string_literal(self):
 342             self.assertEqual(
 343                 _string_literal_expression_parser(0, tokenization.tokenize("'Hello, world'")),
 344                 (
 345                     True,
 346                     1,
 347                     FurStringLiteralExpression(value='Hello, world'),
 348                 ),
 349             )
 350
 351     class FurFunctionCallExpressionParserTests(unittest.TestCase):
 352         def test_parses_function_with_string_literal_argument(self):
 353             self.assertEqual(
 354                 _function_call_expression_parser(0, tokenization.tokenize("print('Hello, world')")),
 355                 (
 356                     True,
 357                     4,
 358                     FurFunctionCallExpression(
 359                         name='print',
 360                         arguments=(FurStringLiteralExpression(value='Hello, world'),),
 361                     ),
 362                 ),
 363             )
 364
 365     unittest.main()