b791d4634742dc6e6834c7533ede425cfc9e51be
[fur] / 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()