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