Removed one more test using ternary comparison
[fur] / 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 NodeMetadata = collections.namedtuple(
40     'NodeMetadata',
41     [
42         'index',
43         'line',
44     ],
45 )
46
47 FurIntegerLiteralExpression = collections.namedtuple(
48     'FurIntegerLiteralExpression',
49     [
50         'integer',
51     ],
52 )
53
54 FurStringLiteralExpression = collections.namedtuple(
55     'FurStringLiteralExpression',
56     [
57         'string',
58     ],
59 )
60
61 FurSymbolExpression = collections.namedtuple(
62     'FurSymbolExpression',
63     [
64         'symbol',
65     ],
66 )
67
68 FurNegationExpression = collections.namedtuple(
69     'FurNegationExpression',
70     [
71         'value',
72     ],
73 )
74
75 FurInfixExpression = collections.namedtuple(
76     'FurInfixExpression',
77     [
78         'metadata',
79         'order',
80         'operator',
81         'left',
82         'right',
83     ],
84 )
85
86 FurListLiteralExpression = collections.namedtuple(
87     'FurListLiteralExpression',
88     [
89         'item_expression_list',
90     ],
91 )
92
93 FurIfExpression = collections.namedtuple(
94     'FurIfExpression',
95     [
96         'condition_expression',
97         'if_statement_list',
98         'else_statement_list',
99     ],
100 )
101
102 FurSymbolExpressionPair = collections.namedtuple(
103     'FurSymbolExpressionPair',
104     [
105         'symbol',
106         'expression',
107     ],
108 )
109
110 FurStructureLiteralExpression = collections.namedtuple(
111     'FurStructureLiteralExpression',
112     [
113         'fields',
114     ],
115 )
116
117 def _integer_literal_expression_parser(index, tokens):
118     failure = (False, index, None)
119
120     if tokens[index].type != 'integer_literal':
121         return failure
122     value = int(tokens[index].match)
123     index += 1
124
125     return True, index, FurIntegerLiteralExpression(integer=value)
126
127 def _string_literal_expression_parser(index, tokens):
128     if tokens[index].type == 'double_quoted_string_literal':
129         return (True, index + 1, FurStringLiteralExpression(string=tokens[index].match[1:-1]))
130
131     if tokens[index].type == 'single_quoted_string_literal':
132         return (True, index + 1, FurStringLiteralExpression(string=tokens[index].match[1:-1]))
133
134     return (False, index, None)
135
136 def _symbol_expression_parser(index, tokens):
137     if tokens[index].type == 'symbol':
138         return (True, index + 1, FurSymbolExpression(symbol=tokens[index].match))
139
140     return (False, index, None)
141
142 def _wrapped_parser(open_token, close_token, internal_parser):
143     def result_parser(index, tokens):
144         failure = (False, index, None)
145
146         if tokens[index].type == open_token:
147             index += 1
148         else:
149             return failure
150
151         success, index, internal = internal_parser(index, tokens)
152         if not success:
153             return failure
154
155         if tokens[index].type == close_token:
156             index += 1
157         else:
158             # TODO Put the actual expected character in the error message
159             raise Exception('Expected closing token on line {}, found "{}"'.format(
160                 tokens[index].line,
161                 tokens[index].match,
162             ))
163
164         return True, index, internal
165
166     return result_parser
167
168 def _bracket_wrapped_parser(internal_parser):
169     return _wrapped_parser('open_bracket', 'close_bracket', internal_parser)
170
171 def _parenthese_wrapped_parser(internal_parser):
172     return _wrapped_parser('open_parenthese', 'close_parenthese', internal_parser)
173
174 def _parenthesized_expression_parser(index, tokens):
175     return _parenthese_wrapped_parser(_expression_parser)(index, tokens)
176
177 def symbol_expression_pair_parser(index, tokens):
178     failure = (False, index, None)
179
180     if tokens[index].type == 'symbol':
181         symbol = tokens[index].match
182         index += 1
183     else:
184         return failure
185
186     if tokens[index].type == 'colon':
187         index += 1
188     else:
189         return failure
190
191     success, index, expression = _expression_parser(index, tokens)
192
193     if not success:
194         raise Exception()
195
196     return (
197         True,
198         index,
199         FurSymbolExpressionPair(
200             symbol=symbol,
201             expression=expression,
202         ),
203     )
204
205 def _structure_literal_parser(index, tokens):
206     success, index, result = _parenthese_wrapped_parser(_comma_separated_list_parser(symbol_expression_pair_parser))(index, tokens)
207     return (
208         success,
209         index,
210         FurStructureLiteralExpression(
211             fields=result,
212         ),
213     )
214
215 def _list_literal_expression_parser(index, tokens):
216     failure = (False, index, None)
217
218     success, index, item_expression_list = _bracket_wrapped_parser(_comma_separated_expression_list_parser)(index, tokens)
219
220     if success:
221         return success, index, FurListLiteralExpression(
222             item_expression_list=item_expression_list,
223         )
224     else:
225         return failure
226
227 def _literal_level_expression_parser(index, tokens):
228     return _or_parser(
229         _list_item_expression_parser,
230         _function_call_expression_parser,
231         _parenthesized_expression_parser,
232         _integer_literal_expression_parser,
233         _string_literal_expression_parser,
234         _list_literal_expression_parser,
235         _symbol_expression_parser,
236         _structure_literal_parser,
237     )(index, tokens)
238
239 def _dot_expression_parser(index, tokens):
240     return _left_recursive_infix_operator_parser(
241         lambda token: token.type == 'period',
242         _literal_level_expression_parser,
243         'dot_level',
244     )(index, tokens)
245
246 def _negation_expression_parser(index, tokens):
247     failure = (False, index, None)
248
249     if tokens[index].match != '-':
250         return failure
251
252     success, index, value = _dot_expression_parser(index + 1, tokens)
253
254     if not success:
255         return failure
256
257     return (True, index, FurNegationExpression(value=value))
258
259 def _negation_level_expression_parser(index, tokens):
260     return _or_parser(
261         _dot_expression_parser,
262         _negation_expression_parser,
263     )(index, tokens)
264
265 def _left_recursive_infix_operator_parser(operator_token_matcher, operand_parser, order):
266     def result_parser(index, tokens):
267         failure = (False, index, None)
268
269         success, index, result = operand_parser(index, tokens)
270
271         if not success:
272             return failure
273
274         while success and index < len(tokens) and operator_token_matcher(tokens[index]):
275             success = False
276
277             if index + 1 < len(tokens):
278                 success, try_index, value = operand_parser(index + 1, tokens)
279
280             if success:
281                 result = FurInfixExpression(
282                     metadata=NodeMetadata(
283                         index=tokens[index].index,
284                         line=tokens[index].line,
285                     ),
286                     order=order,
287                     operator=tokens[index].match,
288                     left=result,
289                     right=value,
290                 )
291                 index = try_index
292
293         return True, index, result
294
295     return result_parser
296
297 def _multiplication_level_expression_parser(index, tokens):
298     return _left_recursive_infix_operator_parser(
299         lambda token: token.type == 'multiplication_level_operator',
300         _negation_level_expression_parser,
301         'multiplication_level',
302     )(index, tokens)
303
304 def _addition_level_expression_parser(index, tokens):
305     return _left_recursive_infix_operator_parser(
306         lambda token: token.type == 'addition_level_operator',
307         _multiplication_level_expression_parser,
308         'addition_level',
309     )(index, tokens)
310
311 def _comparison_level_expression_parser(index, tokens):
312     return _left_recursive_infix_operator_parser(
313         lambda token: token.type == 'comparison_level_operator',
314         _addition_level_expression_parser,
315         'comparison_level',
316     )(index, tokens)
317
318 def _and_level_expression_parser(index, tokens):
319     return _left_recursive_infix_operator_parser(
320         lambda token: token.type == 'symbol' and token.match == 'and',
321         _comparison_level_expression_parser,
322         'and_level',
323     )(index, tokens)
324
325 def _or_level_expression_parser(index, tokens):
326     return _left_recursive_infix_operator_parser(
327         lambda token: token.type == 'symbol' and token.match == 'or',
328         _and_level_expression_parser,
329         'or_level',
330     )(index, tokens)
331
332 def _comma_separated_list_parser(subparser):
333     def result_parser(index, tokens):
334         start_index = index
335
336         items = []
337
338         _, index, _ = consume_newlines(index, tokens)
339
340         success, index, item = subparser(index, tokens)
341
342         if success:
343             items.append(item)
344         else:
345             return (True, start_index, ())
346
347         while success and index < len(tokens) and tokens[index].type == 'comma':
348             index += 1
349             success = False
350
351             _, index, _ = consume_newlines(index, tokens)
352
353             if index < len(tokens):
354                 success, try_index, item = subparser(index, tokens)
355
356             if success:
357                 items.append(item)
358                 index = try_index
359
360         return True, index, tuple(items)
361
362     return result_parser
363
364 def _comma_separated_expression_list_parser(index, tokens):
365     return _comma_separated_list_parser(_expression_parser)(index, tokens)
366
367 FurListItemExpression = collections.namedtuple(
368     'FurListItemExpression',
369     [
370         'list_expression',
371         'index_expression',
372     ],
373 )
374
375 FurFunctionCallExpression = collections.namedtuple(
376     'FurFunctionCallExpression',
377     [
378         'function',
379         'arguments',
380     ],
381 )
382
383 FurExpressionStatement = collections.namedtuple(
384     'FurExpressionStatement',
385     [
386         'expression',
387     ],
388 )
389
390 FurAssignmentStatement = collections.namedtuple(
391     'FurAssignmentStatement',
392     [
393         'target',
394         'expression',
395     ],
396 )
397
398 FurFunctionDefinitionStatement = collections.namedtuple(
399     'FurFunctionDefinitionStatement',
400     [
401         'name',
402         'argument_name_list',
403         'statement_list',
404     ],
405 )
406
407 FurProgram = collections.namedtuple(
408     'FurProgram',
409     [
410         'statement_list',
411     ],
412 )
413
414 def _list_item_expression_parser(index, tokens):
415     failure = (False, index, None)
416
417     # We have to be careful what expressions we add here. Otherwise expressions
418     # like "a + b[0]" become ambiguous to the parser.
419     success, index, list_expression = _or_parser(
420         _symbol_expression_parser,
421         _parenthesized_expression_parser,
422     )(index, tokens)
423
424     if not success:
425         return failure
426
427     success, index, index_expression = _bracket_wrapped_parser(_expression_parser)(
428         index,
429         tokens,
430     )
431
432     if not success:
433         return failure
434
435     while success and index < len(tokens):
436         # "list_expression" is actually the full list item expression if the next parse attempt doesn't succeed
437         # We can't give this a better name without a bunch of checks, however.
438         list_expression = FurListItemExpression(
439             list_expression=list_expression,
440             index_expression=index_expression,
441         )
442
443         success, index, index_expression = _bracket_wrapped_parser(_expression_parser)(
444             index,
445             tokens,
446         )
447
448     return True, index, list_expression
449
450 def _function_call_expression_parser(index, tokens):
451     failure = (False, index, None)
452
453     # We have to be careful what expressions we add here. Otherwise expressions
454     # like "a + b()" become ambiguous to the parser.
455     success, index, function = _or_parser(
456         _symbol_expression_parser,
457         _parenthesized_expression_parser,
458     )(index, tokens)
459
460     if not success:
461         return failure
462
463     success, index, arguments = _parenthese_wrapped_parser(_comma_separated_expression_list_parser)(
464         index,
465         tokens,
466     )
467
468     if not success:
469         return failure
470
471     while success and index < len(tokens):
472         # "function" is actually the full function call if the next parse attempt doesn't succeed
473         # We can't give this a better name without a bunch of checks, however.
474         function = FurFunctionCallExpression(
475             function=function,
476             arguments=arguments,
477         )
478
479         success, index, arguments = _parenthese_wrapped_parser(_comma_separated_expression_list_parser)(
480             index,
481             tokens,
482         )
483
484     return True, index, function
485
486 def _if_expression_parser(index, tokens):
487     failure = (False, index, None)
488
489     if tokens[index].match == 'if':
490         index += 1
491     else:
492         return failure
493
494     success, index, condition_expression = _or_level_expression_parser(index, tokens)
495
496     if not success:
497         raise Exception('Expected condition after "if" on line {}'.format(tokens[index].line))
498
499     if tokens[index].match == 'do':
500         index += 1
501     else:
502         raise Exception('Expected "do" after "if" on line {}'.format(tokens[index].line))
503
504
505     success, index, if_statement_list = _zero_or_more_parser(tuple, _statement_parser)(index, tokens)
506     _, index, _ = consume_newlines(index, tokens)
507
508     if tokens[index].match == 'else':
509         index += 1
510         success, index, else_statement_list = _zero_or_more_parser(tuple, _statement_parser)(index, tokens)
511         _, index, _ = consume_newlines(index, tokens)
512     else:
513         else_statement_list = ()
514
515     if tokens[index].match == 'end':
516         index += 1
517     else:
518         raise Exception('Expected "end" after "if" on line {}'.format(tokens[index].line))
519
520     return (
521         True,
522         index,
523         FurIfExpression(
524             condition_expression=condition_expression,
525             if_statement_list=if_statement_list,
526             else_statement_list=else_statement_list,
527         ),
528     )
529
530 _expression_parser = _or_parser(
531     _or_level_expression_parser,
532     _if_expression_parser, # This should always be at the top level
533 )
534
535 def _expression_statement_parser(index, tokens):
536     failure = (False, index, None)
537
538     success, index, expression = _expression_parser(index, tokens)
539
540     if not success:
541         return failure
542
543     return (True, index, FurExpressionStatement(expression=expression))
544
545 BUILTINS = {'print', 'pow'}
546
547 def _assignment_statement_parser(index, tokens):
548     failure = (False, index, None)
549
550     if tokens[index].type == 'symbol':
551         target = tokens[index].match
552         target_assignment_line = tokens[index].line
553
554         index += 1
555     else:
556         return failure
557
558
559     if tokens[index].type == 'assignment_operator':
560         if target in BUILTINS:
561             raise Exception(
562                 'Trying to assign to builtin "{}" on line {}'.format(target, target_assignment_line),
563             )
564         assignment_operator_index = index
565     else:
566         return failure
567
568     success, index, expression = _expression_parser(index + 1, tokens)
569
570     if not success:
571         raise Exception(
572             'Expected expression after assignment operator on line {}'.format(
573                 tokens[assignment_operator_index].line
574             )
575         )
576
577     return True, index, FurAssignmentStatement(target=target, expression=expression)
578
579 def _function_definition_statement_parser(index, tokens):
580     failure = (False, index, None)
581
582     if tokens[index].type == 'keyword' and tokens[index].match == 'def':
583         index += 1
584     else:
585         return failure
586
587     if tokens[index].type == 'symbol':
588         name = tokens[index].match
589         index += 1
590     else:
591         raise Exception('Expected function name, found "{}" on line {}'.format(
592             tokens[index].match,
593             tokens[index].line,
594         ))
595
596     if tokens[index].type == 'open_parenthese':
597         index += 1
598     else:
599         raise Exception('Expected "(", found "{}" on line {}'.format(
600             tokens[index].match,
601             tokens[index].line,
602         ))
603
604     success, index, argument_name_list = _comma_separated_list_parser(_symbol_expression_parser)(
605         index,
606         tokens,
607     )
608
609     if tokens[index].type == 'close_parenthese':
610         index += 1
611     else:
612         raise Exception('Expected ")", found "{}" on line {}'.format(
613             tokens[index].match,
614             tokens[index].line,
615         ))
616
617     if tokens[index].match == 'do':
618         index += 1
619     else:
620         return failure
621
622     success, index, statement_list = _zero_or_more_parser(tuple, _statement_parser)(index, tokens)
623
624     _, index, _ = consume_newlines(index, tokens)
625
626     if tokens[index].type == 'keyword' and tokens[index].match == 'end':
627         index += 1
628     else:
629         return failure
630
631     return True, index, FurFunctionDefinitionStatement(
632         name=name,
633     argument_name_list=tuple(an.symbol for an in argument_name_list),
634         statement_list=statement_list,
635     )
636
637 def _statement_parser(index, tokens):
638     _, index, _ = consume_newlines(index, tokens)
639
640     if index == len(tokens):
641         return (False, index, None)
642
643     return _or_parser(
644         _assignment_statement_parser,
645         _expression_statement_parser,
646         _function_definition_statement_parser,
647     )(index, tokens)
648
649 def _program_formatter(statement_list):
650     return FurProgram(statement_list=statement_list)
651
652 _program_parser = _zero_or_more_parser(_program_formatter, _statement_parser)
653
654 def _parse(parser, tokens):
655     success, index, result = parser(0, tokens)
656
657     if index < len(tokens):
658         raise Exception('Unable to parse token {}'.format(tokens[index]))
659
660     if success:
661         return result
662
663     raise Exception('Unable to parse')
664
665 def parse(tokens):
666     return _parse(_program_parser, tokens)
667
668 if __name__ == '__main__':
669     import unittest
670
671     import tokenization
672
673     class FurStringLiteralExpressionParserTests(unittest.TestCase):
674         def test_parses_single_quoted_string_literal(self):
675             self.assertEqual(
676                 _string_literal_expression_parser(0, tokenization.tokenize("'Hello, world'")),
677                 (
678                     True,
679                     1,
680                     FurStringLiteralExpression(string='Hello, world'),
681                 ),
682             )
683
684     class FurFunctionCallExpressionParserTests(unittest.TestCase):
685         def test_parses_function_with_string_literal_argument(self):
686             self.assertEqual(
687                 _function_call_expression_parser(0, tokenization.tokenize("print('Hello, world')")),
688                 (
689                     True,
690                     4,
691                     FurFunctionCallExpression(
692                         name='print',
693                         arguments=(FurStringLiteralExpression(string='Hello, world'),),
694                     ),
695                 ),
696             )
697
698     unittest.main()