tcenal.parser_combinator.combinators source code

1 module tcenal.parser_combinator.combinators;
2 
3 import tcenal.parser_combinator.token : Token;
4 import tcenal.parser_combinator.parsing_result : ParsingResult;
5 import tcenal.parser_combinator.parse_tree_node : ParseTreeNode;
6 import tcenal.parser_combinator.memo : Memo, MemoEntry;
7 
8 import compile_time_unittest;
9 
10 import std.algorithm : startsWith, until;
11 import std.range : retro;
12 import std.array : array;
13 import std.conv : to;
14 
15 mixin enableCompileTimeUnittest;
16 
17 
18 ParsingResult parseToken(string tokenValue, string tokenType = "")(Token[] input, size_t position, ref Memo memo)
19 {
20     if (input.length > position && input[position].type == tokenType && input[position].value == tokenValue)
21     {
22         return ParsingResult(true, position + 1, ParseTreeNode(input[position]));
23     }
24     else
25     {
26         return ParsingResult(false);
27     }
28 }
29 unittest
30 {
31     Memo memo;
32 
33     with (parseToken!"foo"([Token("foo")], 0, memo))
34     {
35         assert (success);
36         assert (nextPosition == 1);
37         assert (node.token.value == "foo");
38     }
39 }
40 
41 
42 ParsingResult parseTokenWithType(string tokenType)(Token[] input, size_t position, ref Memo memo)
43 {
44     if (input.length > position && input[position].type == tokenType)
45     {
46         return ParsingResult(true, position + 1, ParseTreeNode(input[position]));
47     }
48     else
49     {
50         return ParsingResult(false);
51     }
52 }
53 unittest
54 {
55     Memo memo;
56 
57     with (parseTokenWithType!"identifier"([Token("foo", "identifier")], 0, memo))
58     {
59         assert (success);
60         assert (nextPosition == 1);
61         assert (node.token.value == "foo");
62         assert (node.token.type == "identifier");
63     }
64 }
65 
66 
67 ParsingResult parseTokenWithValue(string tokenValue)(Token[] input, size_t position, ref Memo memo)
68 {
69     if (input.length > position && input[position].value == tokenValue)
70     {
71         return ParsingResult(true, position + 1, ParseTreeNode(input[position]));
72     }
73     else
74     {
75         return ParsingResult(false);
76     }
77 }
78 unittest
79 {
80     Memo memo;
81 
82     with (parseTokenWithValue!"foo"([Token("foo", "identifier")], 0, memo))
83     {
84         assert (success);
85         assert (nextPosition == 1);
86         assert (node.token.value == "foo");
87         assert (node.token.type == "identifier");
88     }
89 }
90 
91 
92 ParsingResult parseWithMakingRuleNode(alias parser, string ruleName)(Token[] input, size_t position, ref Memo memo)
93 {
94     ParsingResult parsingResult = parser(input, position, memo);
95 
96     if (parsingResult.success)
97     {
98         parsingResult.node = ParseTreeNode(Token(), [parsingResult.node], ruleName);
99     }
100 
101     return parsingResult;
102 }
103 unittest
104 {
105     Memo memo;
106 
107     with (parseWithMakingRuleNode!(parseToken!"foo", "bar")([Token("foo")], 0, memo))
108     {
109         assert (success);
110         assert (nextPosition == 1);
111         assert (node.ruleName == "bar");
112         assert (node.children[0].token.value == "foo");
113     }
114 }
115 
116 
117 ParsingResult applyRule(alias parser, string ruleName = __FUNCTION__)(Token[] input, size_t position, ref Memo memo)
118 {
119     enum simplifiedRuleName = ruleName.retro().until('.').array().retro().to!string();
120 
121     if (position in memo)
122     {
123         if (ruleName in memo[position])
124         {
125             memo[position][ruleName].isCalled = true;
126             return memo[position][ruleName].parsingResult;
127         }
128     }
129 
130     memo[position][ruleName] = MemoEntry();
131     ParsingResult parsingResult = parseWithMakingRuleNode!(parser, simplifiedRuleName)(input, position, memo);
132 
133     if (!parsingResult.success)
134     {
135         return parsingResult;
136     }
137 
138     memo[position][ruleName].parsingResult = parsingResult;
139 
140     if (!memo[position][ruleName].isCalled)
141     {
142         return parsingResult;
143     }
144 
145     while (true)
146     {
147         size_t previousNextPosition = parsingResult.nextPosition;
148 
149         parsingResult = parseWithMakingRuleNode!(parser, simplifiedRuleName)(input, position, memo);
150 
151         if (!parsingResult.success)
152         {
153             assert(false);
154         }
155 
156         if (parsingResult.nextPosition <= previousNextPosition)
157         {
158             break;
159         }
160 
161         memo[position][ruleName].parsingResult = parsingResult;
162     }
163 
164     return memo[position][ruleName].parsingResult;
165 }
166 unittest
167 {
168     Memo memo;
169 
170     with (applyRule!(parseToken!"foo", "parseFoo")([Token("foo")], 0, memo))
171     {
172         assert (success);
173         assert (nextPosition == 1);
174         assert (node.ruleName == "parseFoo");
175         assert (node.children[0].token.value == "foo");
176     }
177 
178     with (memo[0]["parseFoo"])
179     {
180         assert (parsingResult.success);
181         assert (parsingResult.nextPosition == 1);
182         assert (parsingResult.node.ruleName == "parseFoo");
183         assert (parsingResult.node.children[0].token.value == "foo");
184         assert (!isCalled);
185     }
186 
187     static ParsingResult ruleForTest(Token[] input, size_t position, ref Memo memo)
188     {
189         return applyRule!(
190             choice!(
191                 sequence!(ruleForTest, parseToken!"+", parseToken!"1"),
192                 parseToken!"1"
193             ),
194             "ruleForTest"
195         )(input, position, memo);
196     }
197 
198     with (ruleForTest([Token("1")], 0, memo))
199     {
200         assert (success);
201         assert (nextPosition == 1);
202         assert (node.ruleName == "ruleForTest");
203         assert (node.children[0].token.value == "1");
204     }
205 
206     memo = memo.init;
207 
208     with (ruleForTest([Token("1"), Token("+"), Token("1")], 0, memo))
209     {
210         assert (success);
211         assert (nextPosition == 3);
212         assert (node.ruleName == "ruleForTest");
213         assert (node.children[0].children[0].ruleName == "ruleForTest");
214         assert (node.children[0].children[0].children[0].token.value == "1");
215         assert (node.children[0].children[1].token.value == "+");
216         assert (node.children[0].children[2].token.value == "1");
217     }
218 
219     memo = memo.init;
220 
221     with (ruleForTest([Token("1"), Token("+"), Token("1"), Token("+"), Token("1")], 0, memo))
222     {
223         assert (success);
224         assert (nextPosition == 5);
225         assert (node.ruleName == "ruleForTest");
226         assert (node.children[0].children[0].ruleName == "ruleForTest");
227         assert (node.children[0].children[0].children[0].children[0].ruleName == "ruleForTest");
228         assert (node.children[0].children[0].children[0].children[0].children[0].token.value == "1");
229         assert (node.children[0].children[0].children[0].children[1].token.value == "+");
230         assert (node.children[0].children[0].children[0].children[2].token.value == "1");
231         assert (node.children[0].children[1].token.value == "+");
232         assert (node.children[0].children[2].token.value == "1");
233     }
234 
235     with (memo[0]["ruleForTest"])
236     {
237         assert (parsingResult.success);
238         assert (parsingResult.nextPosition == 5);
239         assert (parsingResult.node.ruleName == "ruleForTest");
240         assert (parsingResult.node.children[0].children[0].ruleName == "ruleForTest");
241         assert (parsingResult.node.children[0].children[0].children[0].children[0].ruleName == "ruleForTest");
242         assert (parsingResult.node.children[0].children[0].children[0].children[0].children[0].token.value == "1");
243         assert (parsingResult.node.children[0].children[0].children[0].children[1].token.value == "+");
244         assert (parsingResult.node.children[0].children[0].children[0].children[2].token.value == "1");
245         assert (parsingResult.node.children[0].children[1].token.value == "+");
246         assert (parsingResult.node.children[0].children[2].token.value == "1");
247         assert (isCalled);
248     }
249 }
250 
251 
252 ParsingResult sequence(parsers...)(Token[] input, size_t position, ref Memo memo)
253 {
254     ParsingResult parsingWholeResult = ParsingResult(true, position);
255     parsingWholeResult.node.ruleName = "#sequence";
256 
257     foreach (parser; parsers)
258     {
259         ParsingResult parsingResult = parser(input, parsingWholeResult.nextPosition, memo);
260 
261         if (!parsingResult.success)
262         {
263             return ParsingResult(false);
264         }
265 
266         parsingWholeResult.node.children ~= parsingResult.node;
267         parsingWholeResult.nextPosition = parsingResult.nextPosition;
268     }
269 
270     return parsingWholeResult;
271 }
272 unittest
273 {
274     Memo memo;
275 
276     with (sequence!(parseToken!"foo", parseToken!"bar")([Token("foo"), Token("bar")], 0, memo))
277     {
278         assert (success);
279         assert (nextPosition == 2);
280         assert (node.ruleName == "#sequence");
281     }
282 }
283 
284 
285 ParsingResult select(size_t n, parsers...)(Token[] input, size_t position, ref Memo memo) if (n < parsers.length)
286 {
287     ParsingResult parsingResult = sequence!(parsers)(input, position, memo);
288 
289     if (parsingResult.success)
290     {
291         parsingResult.node = parsingResult.node.children[n];
292     }
293 
294     return parsingResult;
295 }
296 unittest
297 {
298     Memo memo;
299     with (select!(1, parseToken!"foo", parseToken!"bar")([Token("foo"), Token("bar")], 0, memo))
300     {
301         assert (success);
302         assert (nextPosition == 2);
303         assert (node.token.value == "bar");
304     }
305 }
306 
307 
308 ParsingResult choice(parsers...)(Token[] input, size_t position, ref Memo memo)
309 {
310     foreach (parser; parsers)
311     {
312         ParsingResult parsingResult = parser(input, position, memo);
313 
314         if (parsingResult.success)
315         {
316             return parsingResult;
317         }
318     }
319 
320     return ParsingResult();
321 }
322 unittest
323 {
324     Memo memo;
325 
326     with (choice!(parseToken!"foo", parseToken!"bar")([Token("foo")], 0, memo))
327     {
328         assert (success);
329         assert (nextPosition == 1);
330         assert (node.token.value == "foo");
331     }
332 
333     with (choice!(parseToken!"foo", parseToken!"bar")([Token("bar")], 0, memo))
334     {
335         assert (success);
336         assert (nextPosition == 1);
337         assert (node.token.value == "bar");
338     }
339 }
340 
341 
342 ParsingResult option(alias parser)(Token[] input, size_t position, ref Memo memo)
343 {
344     ParsingResult parsingWholeResult = ParsingResult(true, position);
345     parsingWholeResult.node.ruleName = "#option";
346 
347     ParsingResult parsingResult = parser(input, position, memo);
348 
349     if (parsingResult.success)
350     {
351         parsingWholeResult.nextPosition = parsingResult.nextPosition;
352         parsingWholeResult.node.children ~= parsingResult.node;
353     }
354 
355     return parsingWholeResult;
356 }
357 unittest
358 {
359     Memo memo;
360 
361     with (option!(parseToken!"foo")([Token("foo")], 0, memo))
362     {
363         assert (success);
364         assert (nextPosition == 1);
365         assert (node.ruleName == "#option");
366         assert (node.children[0].token.value == "foo");
367     }
368 
369     with (option!(parseToken!"foo")([Token("bar")], 0, memo))
370     {
371         assert (success);
372         assert (node.ruleName == "#option");
373         assert (node.children.length == 0);
374     }
375 }
376 
377 
378 ParsingResult repeat(alias parser, size_t n)(Token[] input, size_t position, ref Memo memo)
379 {
380     ParsingResult parsingWholeResult;
381     parsingWholeResult.node.ruleName = "#repeat";
382 
383     size_t currentPosition = position;
384 
385     while (true)
386     {
387         ParsingResult parsingResult = parser(input, currentPosition ,memo);
388 
389         if (!parsingResult.success)
390         {
391             break;
392         }
393 
394         currentPosition = parsingResult.nextPosition;
395         parsingWholeResult.node.children ~= parsingResult.node;
396     }
397 
398     parsingWholeResult.nextPosition = currentPosition;
399 
400     if (n <= parsingWholeResult.node.children.length)
401     {
402         parsingWholeResult.success = true;
403     }
404 
405     return parsingWholeResult;
406 }
407 unittest
408 {
409     Memo memo;
410 
411     with (repeat!(parseToken!"foo", 2)([Token("foo"), Token("foo")], 0, memo))
412     {
413         assert (success);
414         assert (nextPosition == 2);
415         assert (node.children[0].token.value == "foo");
416         assert (node.children[1].token.value == "foo");
417     }
418 
419     assert (!repeat!(parseToken!"foo", 2)([Token("foo")], 0, memo).success);
420 }
421 
422 
423 alias zeroOrMore(alias parser) = repeat!(parser, 0);
424 alias oneOrMore(alias parser) = repeat!(parser, 1);
425 
426 
427 ParsingResult repeatWithSeparator(alias parser, alias separator, size_t n)(Token[] input, size_t position, ref Memo memo)
428 {
429     ParsingResult parsingResult = sequence!(parser, zeroOrMore!(select!(1, separator, parser)))(input, position, memo);
430 
431     if (n == 0 && !parsingResult.success)
432     {
433         return ParsingResult(true, position, ParseTreeNode(Token(), [], "#repeat"));
434     }
435 
436     if (parsingResult.node.children[1].children.length + 1 < n)
437     {
438         return ParsingResult(false);
439     }
440 
441     if (parsingResult.success)
442     {
443         parsingResult.node.ruleName = "#repeat";
444         parsingResult.node.children = parsingResult.node.children[0] ~ parsingResult.node.children[1].children;
445     }
446 
447     return parsingResult;
448 }
449 unittest
450 {
451     Memo memo;
452 
453     with (repeatWithSeparator!(parseToken!"foo", parseToken!",", 2)([Token("foo"), Token(","), Token("foo"), Token(","), Token("foo")], 0, memo))
454     {
455         assert (success);
456         assert (nextPosition == 5);
457         assert (node.ruleName == "#repeat");
458         assert (node.children[0].token.value == "foo");
459         assert (node.children[1].token.value == "foo");
460         assert (node.children[2].token.value == "foo");
461     }
462 
463     assert (!repeatWithSeparator!(parseToken!"foo", parseToken!",", 4)([Token("foo"), Token(","), Token("foo"), Token(","), Token("foo")], 0, memo).success);
464 }
465 
466 
467 alias zeroOrMoreWithSeparator(alias parser, alias separator) = repeatWithSeparator!(parser, separator, 0);
468 alias oneOrMoreWithSeparator(alias parser, alias separator) = repeatWithSeparator!(parser, separator, 1);
469 
470 
471 ParsingResult not(alias parser)(Token[] input, size_t position, ref Memo memo)
472 {
473     return ParsingResult(!parser(input, position, memo).success, position);
474 }