Debian Codegraph @

Lib/test/test_peg_generator/test_pegen.py

raw
1 import ast
2 import difflib
3 import io
4 import textwrap
5 import unittest
6
7 from test import test_tools
8 from typing import Dict, Any
9 from tokenize import TokenInfo, NAME, NEWLINE, NUMBER, OP
10
11 test_tools.skip_if_missing("peg_generator")
12 with test_tools.imports_under_tool("peg_generator"):
13 from pegen.grammar_parser import GeneratedParser as GrammarParser
14 from pegen.testutil import parse_string, generate_parser, make_parser
15 from pegen.grammar import GrammarVisitor, GrammarError, Grammar
16 from pegen.grammar_visualizer import ASTGrammarPrinter
17 from pegen.parser import Parser
18 from pegen.parser_generator import compute_nullables, compute_left_recursives
19 from pegen.python_generator import PythonParserGenerator
20
21
22 class TestPegen(unittest.TestCase):
23 def test_parse_grammar(self) -> None:
24 grammar_source = """
25 start: sum NEWLINE
26 sum: t1=term '+' t2=term { action } | term
27 term: NUMBER
28 """
29 expected = """
30 start: sum NEWLINE
31 sum: term '+' term | term
32 term: NUMBER
33 """
34 grammar: Grammar = parse_string(grammar_source, GrammarParser)
35 rules = grammar.rules
36 self.assertEqual(str(grammar), textwrap.dedent(expected).strip())
37 # Check the str() and repr() of a few rules; AST nodes don't support ==.
38 self.assertEqual(str(rules["start"]), "start: sum NEWLINE")
39 self.assertEqual(str(rules["sum"]), "sum: term '+' term | term")
40 expected_repr = (
41 "Rule('term', None, Rhs([Alt([NamedItem(None, NameLeaf('NUMBER'))])]))"
42 )
43 self.assertEqual(repr(rules["term"]), expected_repr)
44
45 def test_repeated_rules(self) -> None:
46 grammar_source = """
47 start: the_rule NEWLINE
48 the_rule: 'b' NEWLINE
49 the_rule: 'a' NEWLINE
50 """
51 with self.assertRaisesRegex(GrammarError, "Repeated rule 'the_rule'"):
52 parse_string(grammar_source, GrammarParser)
53
54 def test_long_rule_str(self) -> None:
55 grammar_source = """
56 start: zero | one | one zero | one one | one zero zero | one zero one | one one zero | one one one
57 """
58 expected = """
59 start:
60 | zero
61 | one
62 | one zero
63 | one one
64 | one zero zero
65 | one zero one
66 | one one zero
67 | one one one
68 """
69 grammar: Grammar = parse_string(grammar_source, GrammarParser)
70 self.assertEqual(str(grammar.rules["start"]), textwrap.dedent(expected).strip())
71
72 def test_typed_rules(self) -> None:
73 grammar = """
74 start[int]: sum NEWLINE
75 sum[int]: t1=term '+' t2=term { action } | term
76 term[int]: NUMBER
77 """
78 rules = parse_string(grammar, GrammarParser).rules
79 # Check the str() and repr() of a few rules; AST nodes don't support ==.
80 self.assertEqual(str(rules["start"]), "start: sum NEWLINE")
81 self.assertEqual(str(rules["sum"]), "sum: term '+' term | term")
82 self.assertEqual(
83 repr(rules["term"]),
84 "Rule('term', 'int', Rhs([Alt([NamedItem(None, NameLeaf('NUMBER'))])]))",
85 )
86
87 def test_gather(self) -> None:
88 grammar = """
89 start: ','.thing+ NEWLINE
90 thing: NUMBER
91 """
92 rules = parse_string(grammar, GrammarParser).rules
93 self.assertEqual(str(rules["start"]), "start: ','.thing+ NEWLINE")
94 self.assertStartsWith(repr(rules["start"]),
95 "Rule('start', None, Rhs([Alt([NamedItem(None, Gather(StringLeaf(\"','\"), NameLeaf('thing'"
96 )
97 self.assertEqual(str(rules["thing"]), "thing: NUMBER")
98 parser_class = make_parser(grammar)
99 node = parse_string("42\n", parser_class)
100 node = parse_string("1, 2\n", parser_class)
101 self.assertEqual(
102 node,
103 [
104 [
105 TokenInfo(
106 NUMBER, string="1", start=(1, 0), end=(1, 1), line="1, 2\n"
107 ),
108 TokenInfo(
109 NUMBER, string="2", start=(1, 3), end=(1, 4), line="1, 2\n"
110 ),
111 ],
112 TokenInfo(
113 NEWLINE, string="\n", start=(1, 4), end=(1, 5), line="1, 2\n"
114 ),
115 ],
116 )
117
118 def test_expr_grammar(self) -> None:
119 grammar = """
120 start: sum NEWLINE
121 sum: term '+' term | term
122 term: NUMBER
123 """
124 parser_class = make_parser(grammar)
125 node = parse_string("42\n", parser_class)
126 self.assertEqual(
127 node,
128 [
129 TokenInfo(NUMBER, string="42", start=(1, 0), end=(1, 2), line="42\n"),
130 TokenInfo(NEWLINE, string="\n", start=(1, 2), end=(1, 3), line="42\n"),
131 ],
132 )
133
134 def test_optional_operator(self) -> None:
135 grammar = """
136 start: sum NEWLINE
137 sum: term ('+' term)?
138 term: NUMBER
139 """
140 parser_class = make_parser(grammar)
141 node = parse_string("1 + 2\n", parser_class)
142 self.assertEqual(
143 node,
144 [
145 [
146 TokenInfo(
147 NUMBER, string="1", start=(1, 0), end=(1, 1), line="1 + 2\n"
148 ),
149 [
150 TokenInfo(
151 OP, string="+", start=(1, 2), end=(1, 3), line="1 + 2\n"
152 ),
153 TokenInfo(
154 NUMBER, string="2", start=(1, 4), end=(1, 5), line="1 + 2\n"
155 ),
156 ],
157 ],
158 TokenInfo(
159 NEWLINE, string="\n", start=(1, 5), end=(1, 6), line="1 + 2\n"
160 ),
161 ],
162 )
163 node = parse_string("1\n", parser_class)
164 self.assertEqual(
165 node,
166 [
167 [
168 TokenInfo(NUMBER, string="1", start=(1, 0), end=(1, 1), line="1\n"),
169 None,
170 ],
171 TokenInfo(NEWLINE, string="\n", start=(1, 1), end=(1, 2), line="1\n"),
172 ],
173 )
174
175 def test_optional_literal(self) -> None:
176 grammar = """
177 start: sum NEWLINE
178 sum: term '+' ?
179 term: NUMBER
180 """
181 parser_class = make_parser(grammar)
182 node = parse_string("1+\n", parser_class)
183 self.assertEqual(
184 node,
185 [
186 [
187 TokenInfo(
188 NUMBER, string="1", start=(1, 0), end=(1, 1), line="1+\n"
189 ),
190 TokenInfo(OP, string="+", start=(1, 1), end=(1, 2), line="1+\n"),
191 ],
192 TokenInfo(NEWLINE, string="\n", start=(1, 2), end=(1, 3), line="1+\n"),
193 ],
194 )
195 node = parse_string("1\n", parser_class)
196 self.assertEqual(
197 node,
198 [
199 [
200 TokenInfo(NUMBER, string="1", start=(1, 0), end=(1, 1), line="1\n"),
201 None,
202 ],
203 TokenInfo(NEWLINE, string="\n", start=(1, 1), end=(1, 2), line="1\n"),
204 ],
205 )
206
207 def test_alt_optional_operator(self) -> None:
208 grammar = """
209 start: sum NEWLINE
210 sum: term ['+' term]
211 term: NUMBER
212 """
213 parser_class = make_parser(grammar)
214 node = parse_string("1 + 2\n", parser_class)
215 self.assertEqual(
216 node,
217 [
218 [
219 TokenInfo(
220 NUMBER, string="1", start=(1, 0), end=(1, 1), line="1 + 2\n"
221 ),
222 [
223 TokenInfo(
224 OP, string="+", start=(1, 2), end=(1, 3), line="1 + 2\n"
225 ),
226 TokenInfo(
227 NUMBER, string="2", start=(1, 4), end=(1, 5), line="1 + 2\n"
228 ),
229 ],
230 ],
231 TokenInfo(
232 NEWLINE, string="\n", start=(1, 5), end=(1, 6), line="1 + 2\n"
233 ),
234 ],
235 )
236 node = parse_string("1\n", parser_class)
237 self.assertEqual(
238 node,
239 [
240 [
241 TokenInfo(NUMBER, string="1", start=(1, 0), end=(1, 1), line="1\n"),
242 None,
243 ],
244 TokenInfo(NEWLINE, string="\n", start=(1, 1), end=(1, 2), line="1\n"),
245 ],
246 )
247
248 def test_repeat_0_simple(self) -> None:
249 grammar = """
250 start: thing thing* NEWLINE
251 thing: NUMBER
252 """
253 parser_class = make_parser(grammar)
254 node = parse_string("1 2 3\n", parser_class)
255 self.assertEqual(
256 node,
257 [
258 TokenInfo(NUMBER, string="1", start=(1, 0), end=(1, 1), line="1 2 3\n"),
259 [
260 TokenInfo(
261 NUMBER, string="2", start=(1, 2), end=(1, 3), line="1 2 3\n"
262 ),
263 TokenInfo(
264 NUMBER, string="3", start=(1, 4), end=(1, 5), line="1 2 3\n"
265 ),
266 ],
267 TokenInfo(
268 NEWLINE, string="\n", start=(1, 5), end=(1, 6), line="1 2 3\n"
269 ),
270 ],
271 )
272 node = parse_string("1\n", parser_class)
273 self.assertEqual(
274 node,
275 [
276 TokenInfo(NUMBER, string="1", start=(1, 0), end=(1, 1), line="1\n"),
277 [],
278 TokenInfo(NEWLINE, string="\n", start=(1, 1), end=(1, 2), line="1\n"),
279 ],
280 )
281
282 def test_repeat_0_complex(self) -> None:
283 grammar = """
284 start: term ('+' term)* NEWLINE
285 term: NUMBER
286 """
287 parser_class = make_parser(grammar)
288 node = parse_string("1 + 2 + 3\n", parser_class)
289 self.assertEqual(
290 node,
291 [
292 TokenInfo(
293 NUMBER, string="1", start=(1, 0), end=(1, 1), line="1 + 2 + 3\n"
294 ),
295 [
296 [
297 TokenInfo(
298 OP, string="+", start=(1, 2), end=(1, 3), line="1 + 2 + 3\n"
299 ),
300 TokenInfo(
301 NUMBER,
302 string="2",
303 start=(1, 4),
304 end=(1, 5),
305 line="1 + 2 + 3\n",
306 ),
307 ],
308 [
309 TokenInfo(
310 OP, string="+", start=(1, 6), end=(1, 7), line="1 + 2 + 3\n"
311 ),
312 TokenInfo(
313 NUMBER,
314 string="3",
315 start=(1, 8),
316 end=(1, 9),
317 line="1 + 2 + 3\n",
318 ),
319 ],
320 ],
321 TokenInfo(
322 NEWLINE, string="\n", start=(1, 9), end=(1, 10), line="1 + 2 + 3\n"
323 ),
324 ],
325 )
326
327 def test_repeat_1_simple(self) -> None:
328 grammar = """
329 start: thing thing+ NEWLINE
330 thing: NUMBER
331 """
332 parser_class = make_parser(grammar)
333 node = parse_string("1 2 3\n", parser_class)
334 self.assertEqual(
335 node,
336 [
337 TokenInfo(NUMBER, string="1", start=(1, 0), end=(1, 1), line="1 2 3\n"),
338 [
339 TokenInfo(
340 NUMBER, string="2", start=(1, 2), end=(1, 3), line="1 2 3\n"
341 ),
342 TokenInfo(
343 NUMBER, string="3", start=(1, 4), end=(1, 5), line="1 2 3\n"
344 ),
345 ],
346 TokenInfo(
347 NEWLINE, string="\n", start=(1, 5), end=(1, 6), line="1 2 3\n"
348 ),
349 ],
350 )
351 with self.assertRaises(SyntaxError):
352 parse_string("1\n", parser_class)
353
354 def test_repeat_1_complex(self) -> None:
355 grammar = """
356 start: term ('+' term)+ NEWLINE
357 term: NUMBER
358 """
359 parser_class = make_parser(grammar)
360 node = parse_string("1 + 2 + 3\n", parser_class)
361 self.assertEqual(
362 node,
363 [
364 TokenInfo(
365 NUMBER, string="1", start=(1, 0), end=(1, 1), line="1 + 2 + 3\n"
366 ),
367 [
368 [
369 TokenInfo(
370 OP, string="+", start=(1, 2), end=(1, 3), line="1 + 2 + 3\n"
371 ),
372 TokenInfo(
373 NUMBER,
374 string="2",
375 start=(1, 4),
376 end=(1, 5),
377 line="1 + 2 + 3\n",
378 ),
379 ],
380 [
381 TokenInfo(
382 OP, string="+", start=(1, 6), end=(1, 7), line="1 + 2 + 3\n"
383 ),
384 TokenInfo(
385 NUMBER,
386 string="3",
387 start=(1, 8),
388 end=(1, 9),
389 line="1 + 2 + 3\n",
390 ),
391 ],
392 ],
393 TokenInfo(
394 NEWLINE, string="\n", start=(1, 9), end=(1, 10), line="1 + 2 + 3\n"
395 ),
396 ],
397 )
398 with self.assertRaises(SyntaxError):
399 parse_string("1\n", parser_class)
400
401 def test_repeat_with_sep_simple(self) -> None:
402 grammar = """
403 start: ','.thing+ NEWLINE
404 thing: NUMBER
405 """
406 parser_class = make_parser(grammar)
407 node = parse_string("1, 2, 3\n", parser_class)
408 self.assertEqual(
409 node,
410 [
411 [
412 TokenInfo(
413 NUMBER, string="1", start=(1, 0), end=(1, 1), line="1, 2, 3\n"
414 ),
415 TokenInfo(
416 NUMBER, string="2", start=(1, 3), end=(1, 4), line="1, 2, 3\n"
417 ),
418 TokenInfo(
419 NUMBER, string="3", start=(1, 6), end=(1, 7), line="1, 2, 3\n"
420 ),
421 ],
422 TokenInfo(
423 NEWLINE, string="\n", start=(1, 7), end=(1, 8), line="1, 2, 3\n"
424 ),
425 ],
426 )
427
428 def test_left_recursive(self) -> None:
429 grammar_source = """
430 start: expr NEWLINE
431 expr: ('-' term | expr '+' term | term)
432 term: NUMBER
433 foo: NAME+
434 bar: NAME*
435 baz: NAME?
436 """
437 grammar: Grammar = parse_string(grammar_source, GrammarParser)
438 parser_class = generate_parser(grammar)
439 rules = grammar.rules
440 self.assertFalse(rules["start"].left_recursive)
441 self.assertTrue(rules["expr"].left_recursive)
442 self.assertFalse(rules["term"].left_recursive)
443 self.assertFalse(rules["foo"].left_recursive)
444 self.assertFalse(rules["bar"].left_recursive)
445 self.assertFalse(rules["baz"].left_recursive)
446 node = parse_string("1 + 2 + 3\n", parser_class)
447 self.assertEqual(
448 node,
449 [
450 [
451 [
452 TokenInfo(
453 NUMBER,
454 string="1",
455 start=(1, 0),
456 end=(1, 1),
457 line="1 + 2 + 3\n",
458 ),
459 TokenInfo(
460 OP, string="+", start=(1, 2), end=(1, 3), line="1 + 2 + 3\n"
461 ),
462 TokenInfo(
463 NUMBER,
464 string="2",
465 start=(1, 4),
466 end=(1, 5),
467 line="1 + 2 + 3\n",
468 ),
469 ],
470 TokenInfo(
471 OP, string="+", start=(1, 6), end=(1, 7), line="1 + 2 + 3\n"
472 ),
473 TokenInfo(
474 NUMBER, string="3", start=(1, 8), end=(1, 9), line="1 + 2 + 3\n"
475 ),
476 ],
477 TokenInfo(
478 NEWLINE, string="\n", start=(1, 9), end=(1, 10), line="1 + 2 + 3\n"
479 ),
480 ],
481 )
482
483 def test_python_expr(self) -> None:
484 grammar = """
485 start: expr NEWLINE? $ { ast.Expression(expr) }
486 expr: ( expr '+' term { ast.BinOp(expr, ast.Add(), term, lineno=expr.lineno, col_offset=expr.col_offset, end_lineno=term.end_lineno, end_col_offset=term.end_col_offset) }
487 | expr '-' term { ast.BinOp(expr, ast.Sub(), term, lineno=expr.lineno, col_offset=expr.col_offset, end_lineno=term.end_lineno, end_col_offset=term.end_col_offset) }
488 | term { term }
489 )
490 term: ( l=term '*' r=factor { ast.BinOp(l, ast.Mult(), r, lineno=l.lineno, col_offset=l.col_offset, end_lineno=r.end_lineno, end_col_offset=r.end_col_offset) }
491 | l=term '/' r=factor { ast.BinOp(l, ast.Div(), r, lineno=l.lineno, col_offset=l.col_offset, end_lineno=r.end_lineno, end_col_offset=r.end_col_offset) }
492 | factor { factor }
493 )
494 factor: ( '(' expr ')' { expr }
495 | atom { atom }
496 )
497 atom: ( n=NAME { ast.Name(id=n.string, ctx=ast.Load(), lineno=n.start[0], col_offset=n.start[1], end_lineno=n.end[0], end_col_offset=n.end[1]) }
498 | n=NUMBER { ast.Constant(value=ast.literal_eval(n.string), lineno=n.start[0], col_offset=n.start[1], end_lineno=n.end[0], end_col_offset=n.end[1]) }
499 )
500 """
501 parser_class = make_parser(grammar)
502 node = parse_string("(1 + 2*3 + 5)/(6 - 2)\n", parser_class)
503 code = compile(node, "", "eval")
504 val = eval(code)
505 self.assertEqual(val, 3.0)
506
507 def test_f_string_in_action(self) -> None:
508 grammar = """
509 start: n=NAME NEWLINE? $ { f"name -> {n.string}" }
510 """
511 parser_class = make_parser(grammar)
512 node = parse_string("a", parser_class)
513 self.assertEqual(node.strip(), "name -> a")
514
515 def test_nullable(self) -> None:
516 grammar_source = """
517 start: sign NUMBER
518 sign: ['-' | '+']
519 """
520 grammar: Grammar = parse_string(grammar_source, GrammarParser)
521 rules = grammar.rules
522 nullables = compute_nullables(rules)
523 self.assertNotIn(rules["start"], nullables) # Not None!
524 self.assertIn(rules["sign"], nullables)
525
526 def test_advanced_left_recursive(self) -> None:
527 grammar_source = """
528 start: NUMBER | sign start
529 sign: ['-']
530 """
531 grammar: Grammar = parse_string(grammar_source, GrammarParser)
532 rules = grammar.rules
533 nullables = compute_nullables(rules)
534 compute_left_recursives(rules)
535 self.assertNotIn(rules["start"], nullables) # Not None!
536 self.assertIn(rules["sign"], nullables)
537 self.assertTrue(rules["start"].left_recursive)
538 self.assertFalse(rules["sign"].left_recursive)
539
540 def test_mutually_left_recursive(self) -> None:
541 grammar_source = """
542 start: foo 'E'
543 foo: bar 'A' | 'B'
544 bar: foo 'C' | 'D'
545 """
546 grammar: Grammar = parse_string(grammar_source, GrammarParser)
547 out = io.StringIO()
548 genr = PythonParserGenerator(grammar, out)
549 rules = grammar.rules
550 self.assertFalse(rules["start"].left_recursive)
551 self.assertTrue(rules["foo"].left_recursive)
552 self.assertTrue(rules["bar"].left_recursive)
553 genr.generate("<string>")
554 ns: Dict[str, Any] = {}
555 exec(out.getvalue(), ns)
556 parser_class: Type[Parser] = ns["GeneratedParser"]
557 node = parse_string("D A C A E", parser_class)
558
559 self.assertEqual(
560 node,
561 [
562 [
563 [
564 [
565 TokenInfo(
566 type=NAME,
567 string="D",
568 start=(1, 0),
569 end=(1, 1),
570 line="D A C A E",
571 ),
572 TokenInfo(
573 type=NAME,
574 string="A",
575 start=(1, 2),
576 end=(1, 3),
577 line="D A C A E",
578 ),
579 ],
580 TokenInfo(
581 type=NAME,
582 string="C",
583 start=(1, 4),
584 end=(1, 5),
585 line="D A C A E",
586 ),
587 ],
588 TokenInfo(
589 type=NAME,
590 string="A",
591 start=(1, 6),
592 end=(1, 7),
593 line="D A C A E",
594 ),
595 ],
596 TokenInfo(
597 type=NAME, string="E", start=(1, 8), end=(1, 9), line="D A C A E"
598 ),
599 ],
600 )
601 node = parse_string("B C A E", parser_class)
602 self.assertEqual(
603 node,
604 [
605 [
606 [
607 TokenInfo(
608 type=NAME,
609 string="B",
610 start=(1, 0),
611 end=(1, 1),
612 line="B C A E",
613 ),
614 TokenInfo(
615 type=NAME,
616 string="C",
617 start=(1, 2),
618 end=(1, 3),
619 line="B C A E",
620 ),
621 ],
622 TokenInfo(
623 type=NAME, string="A", start=(1, 4), end=(1, 5), line="B C A E"
624 ),
625 ],
626 TokenInfo(
627 type=NAME, string="E", start=(1, 6), end=(1, 7), line="B C A E"
628 ),
629 ],
630 )
631
632 def test_nasty_mutually_left_recursive(self) -> None:
633 # This grammar does not recognize 'x - + =', much to my chagrin.
634 # But that's the way PEG works.
635 # [Breathlessly]
636 # The problem is that the toplevel target call
637 # recurses into maybe, which recognizes 'x - +',
638 # and then the toplevel target looks for another '+',
639 # which fails, so it retreats to NAME,
640 # which succeeds, so we end up just recognizing 'x',
641 # and then start fails because there's no '=' after that.
642 grammar_source = """
643 start: target '='
644 target: maybe '+' | NAME
645 maybe: maybe '-' | target
646 """
647 grammar: Grammar = parse_string(grammar_source, GrammarParser)
648 out = io.StringIO()
649 genr = PythonParserGenerator(grammar, out)
650 genr.generate("<string>")
651 ns: Dict[str, Any] = {}
652 exec(out.getvalue(), ns)
653 parser_class = ns["GeneratedParser"]
654 with self.assertRaises(SyntaxError):
655 parse_string("x - + =", parser_class)
656
657 def test_lookahead(self) -> None:
658 grammar = """
659 start: (expr_stmt | assign_stmt) &'.'
660 expr_stmt: !(target '=') expr
661 assign_stmt: target '=' expr
662 expr: term ('+' term)*
663 target: NAME
664 term: NUMBER
665 """
666 parser_class = make_parser(grammar)
667 node = parse_string("foo = 12 + 12 .", parser_class)
668 self.maxDiff = None
669 self.assertEqual(
670 node,
671 [
672 TokenInfo(
673 NAME, string="foo", start=(1, 0), end=(1, 3), line="foo = 12 + 12 ."
674 ),
675 TokenInfo(
676 OP, string="=", start=(1, 4), end=(1, 5), line="foo = 12 + 12 ."
677 ),
678 [
679 TokenInfo(
680 NUMBER,
681 string="12",
682 start=(1, 6),
683 end=(1, 8),
684 line="foo = 12 + 12 .",
685 ),
686 [
687 [
688 TokenInfo(
689 OP,
690 string="+",
691 start=(1, 9),
692 end=(1, 10),
693 line="foo = 12 + 12 .",
694 ),
695 TokenInfo(
696 NUMBER,
697 string="12",
698 start=(1, 11),
699 end=(1, 13),
700 line="foo = 12 + 12 .",
701 ),
702 ]
703 ],
704 ],
705 ],
706 )
707
708 def test_named_lookahead_error(self) -> None:
709 grammar = """
710 start: foo=!'x' NAME
711 """
712 with self.assertRaises(SyntaxError):
713 make_parser(grammar)
714
715 def test_start_leader(self) -> None:
716 grammar = """
717 start: attr | NAME
718 attr: start '.' NAME
719 """
720 # Would assert False without a special case in compute_left_recursives().
721 make_parser(grammar)
722
723 def test_opt_sequence(self) -> None:
724 grammar = """
725 start: [NAME*]
726 """
727 # This case was failing because of a double trailing comma at the end
728 # of a line in the generated source. See bpo-41044
729 make_parser(grammar)
730
731 def test_left_recursion_too_complex(self) -> None:
732 grammar = """
733 start: foo
734 foo: bar '+' | baz '+' | '+'
735 bar: baz '-' | foo '-' | '-'
736 baz: foo '*' | bar '*' | '*'
737 """
738 with self.assertRaises(ValueError) as errinfo:
739 make_parser(grammar)
740 self.assertTrue("no leader" in str(errinfo.exception.value))
741
742 def test_cut(self) -> None:
743 grammar = """
744 start: '(' ~ expr ')'
745 expr: NUMBER
746 """
747 parser_class = make_parser(grammar)
748 node = parse_string("(1)", parser_class)
749 self.assertEqual(
750 node,
751 [
752 TokenInfo(OP, string="(", start=(1, 0), end=(1, 1), line="(1)"),
753 TokenInfo(NUMBER, string="1", start=(1, 1), end=(1, 2), line="(1)"),
754 TokenInfo(OP, string=")", start=(1, 2), end=(1, 3), line="(1)"),
755 ],
756 )
757
758 def test_cut_is_local_in_rule(self) -> None:
759 grammar = """
760 start:
761 | inner
762 | 'x' { "ok" }
763 inner:
764 | 'x' ~ 'y'
765 | 'x'
766 """
767 parser_class = make_parser(grammar)
768 node = parse_string("x", parser_class)
769 self.assertEqual(node, 'ok')
770
771 def test_cut_is_local_in_parens(self) -> None:
772 # we currently don't guarantee this behavior, see gh-143054
773 grammar = """
774 start:
775 | ('x' ~ 'y' | 'x')
776 | 'x' { "ok" }
777 """
778 parser_class = make_parser(grammar)
779 node = parse_string("x", parser_class)
780 self.assertEqual(node, 'ok')
781
782 def test_dangling_reference(self) -> None:
783 grammar = """
784 start: foo ENDMARKER
785 foo: bar NAME
786 """
787 with self.assertRaises(GrammarError):
788 parser_class = make_parser(grammar)
789
790 def test_bad_token_reference(self) -> None:
791 grammar = """
792 start: foo
793 foo: NAMEE
794 """
795 with self.assertRaises(GrammarError):
796 parser_class = make_parser(grammar)
797
798 def test_missing_start(self) -> None:
799 grammar = """
800 foo: NAME
801 """
802 with self.assertRaises(GrammarError):
803 parser_class = make_parser(grammar)
804
805 def test_invalid_rule_name(self) -> None:
806 grammar = """
807 start: _a b
808 _a: 'a'
809 b: 'b'
810 """
811 with self.assertRaisesRegex(GrammarError, "cannot start with underscore: '_a'"):
812 parser_class = make_parser(grammar)
813
814 def test_invalid_variable_name(self) -> None:
815 grammar = """
816 start: a b
817 a: _x='a'
818 b: 'b'
819 """
820 with self.assertRaisesRegex(GrammarError, "cannot start with underscore: '_x'"):
821 parser_class = make_parser(grammar)
822
823 def test_invalid_variable_name_in_temporal_rule(self) -> None:
824 grammar = """
825 start: a b
826 a: (_x='a' | 'b') | 'c'
827 b: 'b'
828 """
829 with self.assertRaisesRegex(GrammarError, "cannot start with underscore: '_x'"):
830 parser_class = make_parser(grammar)
831
832 def test_soft_keyword(self) -> None:
833 grammar = """
834 start:
835 | "number" n=NUMBER { eval(n.string) }
836 | "string" n=STRING { n.string }
837 | SOFT_KEYWORD l=NAME n=(NUMBER | NAME | STRING) { l.string + " = " + n.string }
838 """
839 parser_class = make_parser(grammar)
840 self.assertEqual(parse_string("number 1", parser_class), 1)
841 self.assertEqual(parse_string("string 'b'", parser_class), "'b'")
842 self.assertEqual(
843 parse_string("number test 1", parser_class), "test = 1"
844 )
845 assert (
846 parse_string("string test 'b'", parser_class) == "test = 'b'"
847 )
848 with self.assertRaises(SyntaxError):
849 parse_string("test 1", parser_class)
850
851 def test_forced(self) -> None:
852 grammar = """
853 start: NAME &&':' | NAME
854 """
855 parser_class = make_parser(grammar)
856 self.assertTrue(parse_string("number :", parser_class))
857 with self.assertRaises(SyntaxError) as e:
858 parse_string("a", parser_class)
859
860 self.assertIn("expected ':'", str(e.exception))
861
862 def test_forced_with_group(self) -> None:
863 grammar = """
864 start: NAME &&(':' | ';') | NAME
865 """
866 parser_class = make_parser(grammar)
867 self.assertTrue(parse_string("number :", parser_class))
868 self.assertTrue(parse_string("number ;", parser_class))
869 with self.assertRaises(SyntaxError) as e:
870 parse_string("a", parser_class)
871 self.assertIn("expected (':' | ';')", e.exception.args[0])
872
873 def test_unreachable_explicit(self) -> None:
874 source = """
875 start: NAME { UNREACHABLE }
876 """
877 grammar = parse_string(source, GrammarParser)
878 out = io.StringIO()
879 genr = PythonParserGenerator(
880 grammar, out, unreachable_formatting="This is a test"
881 )
882 genr.generate("<string>")
883 self.assertIn("This is a test", out.getvalue())
884
885 def test_unreachable_implicit1(self) -> None:
886 source = """
887 start: NAME | invalid_input
888 invalid_input: NUMBER { None }
889 """
890 grammar = parse_string(source, GrammarParser)
891 out = io.StringIO()
892 genr = PythonParserGenerator(
893 grammar, out, unreachable_formatting="This is a test"
894 )
895 genr.generate("<string>")
896 self.assertIn("This is a test", out.getvalue())
897
898 def test_unreachable_implicit2(self) -> None:
899 source = """
900 start: NAME | '(' invalid_input ')'
901 invalid_input: NUMBER { None }
902 """
903 grammar = parse_string(source, GrammarParser)
904 out = io.StringIO()
905 genr = PythonParserGenerator(
906 grammar, out, unreachable_formatting="This is a test"
907 )
908 genr.generate("<string>")
909 self.assertIn("This is a test", out.getvalue())
910
911 def test_unreachable_implicit3(self) -> None:
912 source = """
913 start: NAME | invalid_input { None }
914 invalid_input: NUMBER
915 """
916 grammar = parse_string(source, GrammarParser)
917 out = io.StringIO()
918 genr = PythonParserGenerator(
919 grammar, out, unreachable_formatting="This is a test"
920 )
921 genr.generate("<string>")
922 self.assertNotIn("This is a test", out.getvalue())
923
924 def test_locations_in_alt_action_and_group(self) -> None:
925 grammar = """
926 start: t=term NEWLINE? $ { ast.Expression(t) }
927 term:
928 | l=term '*' r=factor { ast.BinOp(l, ast.Mult(), r, LOCATIONS) }
929 | l=term '/' r=factor { ast.BinOp(l, ast.Div(), r, LOCATIONS) }
930 | factor
931 factor:
932 | (
933 n=NAME { ast.Name(id=n.string, ctx=ast.Load(), LOCATIONS) } |
934 n=NUMBER { ast.Constant(value=ast.literal_eval(n.string), LOCATIONS) }
935 )
936 """
937 parser_class = make_parser(grammar)
938 source = "2*3\n"
939 o = ast.dump(parse_string(source, parser_class).body, include_attributes=True)
940 p = ast.dump(ast.parse(source).body[0].value, include_attributes=True).replace(
941 " kind=None,", ""
942 )
943 diff = "\n".join(
944 difflib.unified_diff(
945 o.split("\n"), p.split("\n"), "cpython", "python-pegen"
946 )
947 )
948 self.assertFalse(diff)
949
950
951 class TestGrammarVisitor:
952 class Visitor(GrammarVisitor):
953 def __init__(self) -> None:
954 self.n_nodes = 0
955
956 def visit(self, node: Any, *args: Any, **kwargs: Any) -> None:
957 self.n_nodes += 1
958 super().visit(node, *args, **kwargs)
959
960 def test_parse_trivial_grammar(self) -> None:
961 grammar = """
962 start: 'a'
963 """
964 rules = parse_string(grammar, GrammarParser)
965 visitor = self.Visitor()
966
967 visitor.visit(rules)
968
969 self.assertEqual(visitor.n_nodes, 6)
970
971 def test_parse_or_grammar(self) -> None:
972 grammar = """
973 start: rule
974 rule: 'a' | 'b'
975 """
976 rules = parse_string(grammar, GrammarParser)
977 visitor = self.Visitor()
978
979 visitor.visit(rules)
980
981 # Grammar/Rule/Rhs/Alt/NamedItem/NameLeaf -> 6
982 # Rule/Rhs/ -> 2
983 # Alt/NamedItem/StringLeaf -> 3
984 # Alt/NamedItem/StringLeaf -> 3
985
986 self.assertEqual(visitor.n_nodes, 14)
987
988 def test_parse_repeat1_grammar(self) -> None:
989 grammar = """
990 start: 'a'+
991 """
992 rules = parse_string(grammar, GrammarParser)
993 visitor = self.Visitor()
994
995 visitor.visit(rules)
996
997 # Grammar/Rule/Rhs/Alt/NamedItem/Repeat1/StringLeaf -> 6
998 self.assertEqual(visitor.n_nodes, 7)
999
1000 def test_parse_repeat0_grammar(self) -> None:
1001 grammar = """
1002 start: 'a'*
1003 """
1004 rules = parse_string(grammar, GrammarParser)
1005 visitor = self.Visitor()
1006
1007 visitor.visit(rules)
1008
1009 # Grammar/Rule/Rhs/Alt/NamedItem/Repeat0/StringLeaf -> 6
1010
1011 self.assertEqual(visitor.n_nodes, 7)
1012
1013 def test_parse_optional_grammar(self) -> None:
1014 grammar = """
1015 start: 'a' ['b']
1016 """
1017 rules = parse_string(grammar, GrammarParser)
1018 visitor = self.Visitor()
1019
1020 visitor.visit(rules)
1021
1022 # Grammar/Rule/Rhs/Alt/NamedItem/StringLeaf -> 6
1023 # NamedItem/Opt/Rhs/Alt/NamedItem/Stringleaf -> 6
1024
1025 self.assertEqual(visitor.n_nodes, 12)
1026
1027
1028 class TestGrammarVisualizer(unittest.TestCase):
1029 def test_simple_rule(self) -> None:
1030 grammar = """
1031 start: 'a' 'b'
1032 """
1033 rules = parse_string(grammar, GrammarParser)
1034
1035 printer = ASTGrammarPrinter()
1036 lines: List[str] = []
1037 printer.print_grammar_ast(rules, printer=lines.append)
1038
1039 output = "\n".join(lines)
1040 expected_output = textwrap.dedent(
1041 """\
1042 └──Rule
1043 └──Rhs
1044 └──Alt
1045 ├──NamedItem
1046 │ └──StringLeaf("'a'")
1047 └──NamedItem
1048 └──StringLeaf("'b'")
1049 """
1050 )
1051
1052 self.assertEqual(output, expected_output)
1053
1054 def test_multiple_rules(self) -> None:
1055 grammar = """
1056 start: a b
1057 a: 'a'
1058 b: 'b'
1059 """
1060 rules = parse_string(grammar, GrammarParser)
1061
1062 printer = ASTGrammarPrinter()
1063 lines: List[str] = []
1064 printer.print_grammar_ast(rules, printer=lines.append)
1065
1066 output = "\n".join(lines)
1067 expected_output = textwrap.dedent(
1068 """\
1069 └──Rule
1070 └──Rhs
1071 └──Alt
1072 ├──NamedItem
1073 │ └──NameLeaf('a')
1074 └──NamedItem
1075 └──NameLeaf('b')
1076
1077 └──Rule
1078 └──Rhs
1079 └──Alt
1080 └──NamedItem
1081 └──StringLeaf("'a'")
1082
1083 └──Rule
1084 └──Rhs
1085 └──Alt
1086 └──NamedItem
1087 └──StringLeaf("'b'")
1088 """
1089 )
1090
1091 self.assertEqual(output, expected_output)
1092
1093 def test_deep_nested_rule(self) -> None:
1094 grammar = """
1095 start: 'a' ['b'['c'['d']]]
1096 """
1097 rules = parse_string(grammar, GrammarParser)
1098
1099 printer = ASTGrammarPrinter()
1100 lines: List[str] = []
1101 printer.print_grammar_ast(rules, printer=lines.append)
1102
1103 output = "\n".join(lines)
1104 expected_output = textwrap.dedent(
1105 """\
1106 └──Rule
1107 └──Rhs
1108 └──Alt
1109 ├──NamedItem
1110 │ └──StringLeaf("'a'")
1111 └──NamedItem
1112 └──Opt
1113 └──Rhs
1114 └──Alt
1115 ├──NamedItem
1116 │ └──StringLeaf("'b'")
1117 └──NamedItem
1118 └──Opt
1119 └──Rhs
1120 └──Alt
1121 ├──NamedItem
1122 │ └──StringLeaf("'c'")
1123 └──NamedItem
1124 └──Opt
1125 └──Rhs
1126 └──Alt
1127 └──NamedItem
1128 └──StringLeaf("'d'")
1129 """
1130 )
1131
1132 self.assertEqual(output, expected_output)