https://github.com/python/cpython/commit/89fe9857dd0832de9b597d63ecb11fa7a09984f1
commit: 89fe9857dd0832de9b597d63ecb11fa7a09984f1
branch: main
author: Pablo Galindo Salgado <[email protected]>
committer: pablogsal <[email protected]>
date: 2026-09-14T20:26:18-04:00
summary:
gh-153568: Reuse shared prefixes in generated parser rules (#157465)
files:
A Lib/test/test_peg_generator/test_prefix.py
A
Misc/NEWS.d/next/Core_and_Builtins/2026-09-13-21-00-00.gh-issue-153568.prefix-cache.rst
M InternalDocs/parser.md
M Lib/test/test_peg_generator/test_c_parser.py
M Parser/parser.c
M Tools/peg_generator/pegen/c_generator.py
diff --git a/InternalDocs/parser.md b/InternalDocs/parser.md
index ff6426c4879f660..bdb130f7a5ccfb0 100644
--- a/InternalDocs/parser.md
+++ b/InternalDocs/parser.md
@@ -563,6 +563,23 @@ in the generated C parse code that allows to measure how
much each rule uses
memoization (check the [`Parser/pegen.c`](../Parser/pegen.c)
file for more information) but it needs to be manually activated.
+The C generator also reuses memoized prefixes within consecutive alternatives.
+For example, in `prefix ':' NAME | prefix ':' NUMBER`, failure after the first
+`':'` normally requires another call to `prefix` and another memo lookup. The
+generated code can keep the result and ending position in local variables and
+reuse them when trying the next alternative.
+
+This applies only when the shared first item is a memoized rule, including a
+left-recursion leader, that the generator can prove consumes input on success.
+The locals are reset on each rule-body invocation, including each seed-growing
+iteration. Alternative order, cuts, and suffix backtracking are preserved. When
+`call_invalid_rules` is enabled, the generated code uses the original rule
calls.
+
+The consumption analysis follows grammar items; it cannot inspect arbitrary C
+actions. As with memoization, actions must not invalidate cached results. In
+particular, suffix actions must not move the parser before their starting mark,
+rewrite buffered input, or replace memo entries for earlier positions.
+
Automatic variables
-------------------
diff --git a/Lib/test/test_peg_generator/test_c_parser.py
b/Lib/test/test_peg_generator/test_c_parser.py
index dc887693840a007..cd0b907667e4a27 100644
--- a/Lib/test/test_peg_generator/test_c_parser.py
+++ b/Lib/test/test_peg_generator/test_c_parser.py
@@ -145,6 +145,35 @@ def run_test(self, grammar_source, test_source):
TEST_TEMPLATE.format(extension_path=self.tmp_path,
test_source=test_source),
)
+ def test_prefix_reuses_position(self) -> None:
+ grammar_source = """
+ start:
+ | prefix ':' NAME NEWLINE? ENDMARKER
+ | prefix ':' NUMBER NEWLINE? ENDMARKER
+ | prefix '=' NUMBER NEWLINE? ENDMARKER
+ prefix (memo): NAME NAME
+ """
+ self.run_test(grammar_source, """
+ self.check_input_strings_for_grammar(
+ valid_cases=['one two : name', 'one two : 3', 'one two = 3'],
+ invalid_cases=['one = 3', 'one two = name', 'one two :'],
+ )
+ """)
+
+ def test_prefix_respects_cut(self) -> None:
+ grammar_source = """
+ start:
+ | prefix ':' ~ NAME NEWLINE? ENDMARKER
+ | prefix ':' NUMBER NEWLINE? ENDMARKER
+ prefix (memo): NAME NAME
+ """
+ self.run_test(grammar_source, """
+ self.check_input_strings_for_grammar(
+ valid_cases=['one two : name'],
+ invalid_cases=['one two : 3'],
+ )
+ """)
+
def test_c_parser(self) -> None:
grammar_source = """
start[mod_ty]: a[asdl_stmt_seq*]=stmt* $ { _PyAST_Module(a, NULL,
p->arena) }
diff --git a/Lib/test/test_peg_generator/test_prefix.py
b/Lib/test/test_peg_generator/test_prefix.py
new file mode 100644
index 000000000000000..b4d5128df0121c0
--- /dev/null
+++ b/Lib/test/test_peg_generator/test_prefix.py
@@ -0,0 +1,32 @@
+import unittest
+
+from test import test_tools
+
+with test_tools.imports_under_tool("peg_generator"):
+ from pegen.c_generator import consuming_rules
+ from pegen.testutil import GrammarParser, parse_string
+
+
+class ConsumingRuleTests(unittest.TestCase):
+ def test_predicates_cuts_and_nullable_repeats(self):
+ grammar = parse_string("""
+ start: NAME ENDMARKER
+ positive: &NAME
+ negative: !NAME
+ cut: ~ { _PyPegen_dummy_name(p) }
+ optional: [NAME]
+ empty_repeat: NAME*
+ nullable_repeat: optional+
+ consuming_repeat: NAME+
+ """, GrammarParser)
+ self.assertEqual(consuming_rules(grammar.rules), {'start',
'consuming_repeat'})
+
+ def test_fixed_point_and_mixed_alternatives(self):
+ grammar = parse_string("""
+ start: expression ENDMARKER
+ expression: expression '+' term | term
+ term: atom
+ atom: NAME | '(' expression ')'
+ nullable: NAME | &NAME
+ """, GrammarParser)
+ self.assertEqual(consuming_rules(grammar.rules), {'start',
'expression', 'term', 'atom'})
diff --git
a/Misc/NEWS.d/next/Core_and_Builtins/2026-09-13-21-00-00.gh-issue-153568.prefix-cache.rst
b/Misc/NEWS.d/next/Core_and_Builtins/2026-09-13-21-00-00.gh-issue-153568.prefix-cache.rst
new file mode 100644
index 000000000000000..0400f4431d996dc
--- /dev/null
+++
b/Misc/NEWS.d/next/Core_and_Builtins/2026-09-13-21-00-00.gh-issue-153568.prefix-cache.rst
@@ -0,0 +1,2 @@
+Speed up parsing by reusing memoized rule prefixes across consecutive grammar
+alternatives, avoiding repeated rule calls and cache lookups.
diff --git a/Parser/parser.c b/Parser/parser.c
index 750e41a4f7d4337..6b7e7e35bf422cf 100644
--- a/Parser/parser.c
+++ b/Parser/parser.c
@@ -11409,6 +11409,8 @@ expressions_rule(Parser *p)
}
expr_ty _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_0_result = NULL;
+ int _prefix_0_end = 0, _prefix_0_valid = 0;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
p->level--;
@@ -11429,7 +11431,7 @@ expressions_rule(Parser *p)
expr_ty a;
asdl_seq * b;
if (
- (a = expression_rule(p)) // expression
+ (a = ((!p->call_invalid_rules && _prefix_0_valid) ? (p->mark =
_prefix_0_end, _prefix_0_result) : (_prefix_0_result = expression_rule(p),
_prefix_0_end = p->mark, _prefix_0_valid = 1, _prefix_0_result))) // expression
&&
(b = _loop1_55_rule(p)) // ((',' expression))+
&&
@@ -11467,7 +11469,7 @@ expressions_rule(Parser *p)
Token * _literal;
expr_ty a;
if (
- (a = expression_rule(p)) // expression
+ (a = ((!p->call_invalid_rules && _prefix_0_valid) ? (p->mark =
_prefix_0_end, _prefix_0_result) : (_prefix_0_result = expression_rule(p),
_prefix_0_end = p->mark, _prefix_0_valid = 1, _prefix_0_result))) // expression
&&
(_literal = _PyPegen_expect_token(p, 12)) // token=','
)
@@ -11502,7 +11504,7 @@ expressions_rule(Parser *p)
D(fprintf(stderr, "%*c> expressions[%d-%d]: %s\n", p->level, ' ',
_mark, p->mark, "expression"));
expr_ty expression_var;
if (
- (expression_var = expression_rule(p)) // expression
+ (expression_var = ((!p->call_invalid_rules && _prefix_0_valid) ?
(p->mark = _prefix_0_end, _prefix_0_result) : (_prefix_0_result =
expression_rule(p), _prefix_0_end = p->mark, _prefix_0_valid = 1,
_prefix_0_result))) // expression
)
{
D(fprintf(stderr, "%*c+ expressions[%d-%d]: %s succeeded!\n",
p->level, ' ', _mark, p->mark, "expression"));
@@ -11855,6 +11857,8 @@ star_expressions_rule(Parser *p)
}
expr_ty _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_1_result = NULL;
+ int _prefix_1_end = 0, _prefix_1_valid = 0;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
p->level--;
@@ -11875,7 +11879,7 @@ star_expressions_rule(Parser *p)
expr_ty a;
asdl_seq * b;
if (
- (a = star_expression_rule(p)) // star_expression
+ (a = ((!p->call_invalid_rules && _prefix_1_valid) ? (p->mark =
_prefix_1_end, _prefix_1_result) : (_prefix_1_result = star_expression_rule(p),
_prefix_1_end = p->mark, _prefix_1_valid = 1, _prefix_1_result))) //
star_expression
&&
(b = _loop1_56_rule(p)) // ((',' star_expression))+
&&
@@ -11913,7 +11917,7 @@ star_expressions_rule(Parser *p)
Token * _literal;
expr_ty a;
if (
- (a = star_expression_rule(p)) // star_expression
+ (a = ((!p->call_invalid_rules && _prefix_1_valid) ? (p->mark =
_prefix_1_end, _prefix_1_result) : (_prefix_1_result = star_expression_rule(p),
_prefix_1_end = p->mark, _prefix_1_valid = 1, _prefix_1_result))) //
star_expression
&&
(_literal = _PyPegen_expect_token(p, 12)) // token=','
)
@@ -11948,7 +11952,7 @@ star_expressions_rule(Parser *p)
D(fprintf(stderr, "%*c> star_expressions[%d-%d]: %s\n", p->level, ' ',
_mark, p->mark, "star_expression"));
expr_ty star_expression_var;
if (
- (star_expression_var = star_expression_rule(p)) // star_expression
+ (star_expression_var = ((!p->call_invalid_rules &&
_prefix_1_valid) ? (p->mark = _prefix_1_end, _prefix_1_result) :
(_prefix_1_result = star_expression_rule(p), _prefix_1_end = p->mark,
_prefix_1_valid = 1, _prefix_1_result))) // star_expression
)
{
D(fprintf(stderr, "%*c+ star_expressions[%d-%d]: %s succeeded!\n",
p->level, ' ', _mark, p->mark, "star_expression"));
@@ -12352,6 +12356,8 @@ disjunction_rule(Parser *p)
return _res;
}
int _mark = p->mark;
+ expr_ty _prefix_2_result = NULL;
+ int _prefix_2_end = 0, _prefix_2_valid = 0;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
p->level--;
@@ -12370,7 +12376,7 @@ disjunction_rule(Parser *p)
expr_ty a;
asdl_seq * b;
if (
- (a = conjunction_rule(p)) // conjunction
+ (a = ((!p->call_invalid_rules && _prefix_2_valid) ? (p->mark =
_prefix_2_end, _prefix_2_result) : (_prefix_2_result = conjunction_rule(p),
_prefix_2_end = p->mark, _prefix_2_valid = 1, _prefix_2_result))) //
conjunction
&&
(b = _loop1_59_rule(p)) // (('or' conjunction))+
)
@@ -12405,7 +12411,7 @@ disjunction_rule(Parser *p)
D(fprintf(stderr, "%*c> disjunction[%d-%d]: %s\n", p->level, ' ',
_mark, p->mark, "conjunction"));
expr_ty conjunction_var;
if (
- (conjunction_var = conjunction_rule(p)) // conjunction
+ (conjunction_var = ((!p->call_invalid_rules && _prefix_2_valid) ?
(p->mark = _prefix_2_end, _prefix_2_result) : (_prefix_2_result =
conjunction_rule(p), _prefix_2_end = p->mark, _prefix_2_valid = 1,
_prefix_2_result))) // conjunction
)
{
D(fprintf(stderr, "%*c+ disjunction[%d-%d]: %s succeeded!\n",
p->level, ' ', _mark, p->mark, "conjunction"));
@@ -12440,6 +12446,8 @@ conjunction_rule(Parser *p)
return _res;
}
int _mark = p->mark;
+ expr_ty _prefix_3_result = NULL;
+ int _prefix_3_end = 0, _prefix_3_valid = 0;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
p->level--;
@@ -12458,7 +12466,7 @@ conjunction_rule(Parser *p)
expr_ty a;
asdl_seq * b;
if (
- (a = inversion_rule(p)) // inversion
+ (a = ((!p->call_invalid_rules && _prefix_3_valid) ? (p->mark =
_prefix_3_end, _prefix_3_result) : (_prefix_3_result = inversion_rule(p),
_prefix_3_end = p->mark, _prefix_3_valid = 1, _prefix_3_result))) // inversion
&&
(b = _loop1_60_rule(p)) // (('and' inversion))+
)
@@ -12493,7 +12501,7 @@ conjunction_rule(Parser *p)
D(fprintf(stderr, "%*c> conjunction[%d-%d]: %s\n", p->level, ' ',
_mark, p->mark, "inversion"));
expr_ty inversion_var;
if (
- (inversion_var = inversion_rule(p)) // inversion
+ (inversion_var = ((!p->call_invalid_rules && _prefix_3_valid) ?
(p->mark = _prefix_3_end, _prefix_3_result) : (_prefix_3_result =
inversion_rule(p), _prefix_3_end = p->mark, _prefix_3_valid = 1,
_prefix_3_result))) // inversion
)
{
D(fprintf(stderr, "%*c+ conjunction[%d-%d]: %s succeeded!\n",
p->level, ' ', _mark, p->mark, "inversion"));
@@ -12612,6 +12620,8 @@ comparison_rule(Parser *p)
}
expr_ty _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_4_result = NULL;
+ int _prefix_4_end = 0, _prefix_4_valid = 0;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
p->level--;
@@ -12630,7 +12640,7 @@ comparison_rule(Parser *p)
expr_ty a;
asdl_seq * b;
if (
- (a = bitwise_or_rule(p)) // bitwise_or
+ (a = ((!p->call_invalid_rules && _prefix_4_valid) ? (p->mark =
_prefix_4_end, _prefix_4_result) : (_prefix_4_result = bitwise_or_rule(p),
_prefix_4_end = p->mark, _prefix_4_valid = 1, _prefix_4_result))) // bitwise_or
&&
(b = _loop1_61_rule(p)) // compare_op_bitwise_or_pair+
)
@@ -12665,7 +12675,7 @@ comparison_rule(Parser *p)
D(fprintf(stderr, "%*c> comparison[%d-%d]: %s\n", p->level, ' ',
_mark, p->mark, "bitwise_or"));
expr_ty bitwise_or_var;
if (
- (bitwise_or_var = bitwise_or_rule(p)) // bitwise_or
+ (bitwise_or_var = ((!p->call_invalid_rules && _prefix_4_valid) ?
(p->mark = _prefix_4_end, _prefix_4_result) : (_prefix_4_result =
bitwise_or_rule(p), _prefix_4_end = p->mark, _prefix_4_valid = 1,
_prefix_4_result))) // bitwise_or
)
{
D(fprintf(stderr, "%*c+ comparison[%d-%d]: %s succeeded!\n",
p->level, ' ', _mark, p->mark, "bitwise_or"));
@@ -13448,6 +13458,8 @@ shift_expr_raw(Parser *p)
}
expr_ty _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_5_result = NULL;
+ int _prefix_5_end = 0, _prefix_5_valid = 0;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
p->level--;
@@ -13467,7 +13479,7 @@ shift_expr_raw(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = shift_expr_rule(p)) // shift_expr
+ (a = ((!p->call_invalid_rules && _prefix_5_valid) ? (p->mark =
_prefix_5_end, _prefix_5_result) : (_prefix_5_result = shift_expr_rule(p),
_prefix_5_end = p->mark, _prefix_5_valid = 1, _prefix_5_result))) // shift_expr
&&
(_literal = _PyPegen_expect_token(p, 33)) // token='<<'
&&
@@ -13506,7 +13518,7 @@ shift_expr_raw(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = shift_expr_rule(p)) // shift_expr
+ (a = ((!p->call_invalid_rules && _prefix_5_valid) ? (p->mark =
_prefix_5_end, _prefix_5_result) : (_prefix_5_result = shift_expr_rule(p),
_prefix_5_end = p->mark, _prefix_5_valid = 1, _prefix_5_result))) // shift_expr
&&
(_literal = _PyPegen_expect_token(p, 34)) // token='>>'
&&
@@ -13611,6 +13623,8 @@ sum_raw(Parser *p)
}
expr_ty _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_6_result = NULL;
+ int _prefix_6_end = 0, _prefix_6_valid = 0;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
p->level--;
@@ -13630,7 +13644,7 @@ sum_raw(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = sum_rule(p)) // sum
+ (a = ((!p->call_invalid_rules && _prefix_6_valid) ? (p->mark =
_prefix_6_end, _prefix_6_result) : (_prefix_6_result = sum_rule(p),
_prefix_6_end = p->mark, _prefix_6_valid = 1, _prefix_6_result))) // sum
&&
(_literal = _PyPegen_expect_token(p, 14)) // token='+'
&&
@@ -13669,7 +13683,7 @@ sum_raw(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = sum_rule(p)) // sum
+ (a = ((!p->call_invalid_rules && _prefix_6_valid) ? (p->mark =
_prefix_6_end, _prefix_6_result) : (_prefix_6_result = sum_rule(p),
_prefix_6_end = p->mark, _prefix_6_valid = 1, _prefix_6_result))) // sum
&&
(_literal = _PyPegen_expect_token(p, 15)) // token='-'
&&
@@ -13799,6 +13813,8 @@ term_raw(Parser *p)
}
expr_ty _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_7_result = NULL;
+ int _prefix_7_end = 0, _prefix_7_valid = 0;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
p->level--;
@@ -13818,7 +13834,7 @@ term_raw(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = term_rule(p)) // term
+ (a = ((!p->call_invalid_rules && _prefix_7_valid) ? (p->mark =
_prefix_7_end, _prefix_7_result) : (_prefix_7_result = term_rule(p),
_prefix_7_end = p->mark, _prefix_7_valid = 1, _prefix_7_result))) // term
&&
(_literal = _PyPegen_expect_token(p, 16)) // token='*'
&&
@@ -13857,7 +13873,7 @@ term_raw(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = term_rule(p)) // term
+ (a = ((!p->call_invalid_rules && _prefix_7_valid) ? (p->mark =
_prefix_7_end, _prefix_7_result) : (_prefix_7_result = term_rule(p),
_prefix_7_end = p->mark, _prefix_7_valid = 1, _prefix_7_result))) // term
&&
(_literal = _PyPegen_expect_token(p, 17)) // token='/'
&&
@@ -13896,7 +13912,7 @@ term_raw(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = term_rule(p)) // term
+ (a = ((!p->call_invalid_rules && _prefix_7_valid) ? (p->mark =
_prefix_7_end, _prefix_7_result) : (_prefix_7_result = term_rule(p),
_prefix_7_end = p->mark, _prefix_7_valid = 1, _prefix_7_result))) // term
&&
(_literal = _PyPegen_expect_token(p, 47)) // token='//'
&&
@@ -13935,7 +13951,7 @@ term_raw(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = term_rule(p)) // term
+ (a = ((!p->call_invalid_rules && _prefix_7_valid) ? (p->mark =
_prefix_7_end, _prefix_7_result) : (_prefix_7_result = term_rule(p),
_prefix_7_end = p->mark, _prefix_7_valid = 1, _prefix_7_result))) // term
&&
(_literal = _PyPegen_expect_token(p, 24)) // token='%'
&&
@@ -13974,7 +13990,7 @@ term_raw(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = term_rule(p)) // term
+ (a = ((!p->call_invalid_rules && _prefix_7_valid) ? (p->mark =
_prefix_7_end, _prefix_7_result) : (_prefix_7_result = term_rule(p),
_prefix_7_end = p->mark, _prefix_7_valid = 1, _prefix_7_result))) // term
&&
(_literal = _PyPegen_expect_token(p, 49)) // token='@'
&&
@@ -14220,6 +14236,8 @@ power_rule(Parser *p)
}
expr_ty _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_8_result = NULL;
+ int _prefix_8_end = 0, _prefix_8_valid = 0;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
p->level--;
@@ -14239,7 +14257,7 @@ power_rule(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = await_primary_rule(p)) // await_primary
+ (a = ((!p->call_invalid_rules && _prefix_8_valid) ? (p->mark =
_prefix_8_end, _prefix_8_result) : (_prefix_8_result = await_primary_rule(p),
_prefix_8_end = p->mark, _prefix_8_valid = 1, _prefix_8_result))) //
await_primary
&&
(_literal = _PyPegen_expect_token(p, 35)) // token='**'
&&
@@ -14276,7 +14294,7 @@ power_rule(Parser *p)
D(fprintf(stderr, "%*c> power[%d-%d]: %s\n", p->level, ' ', _mark,
p->mark, "await_primary"));
expr_ty await_primary_var;
if (
- (await_primary_var = await_primary_rule(p)) // await_primary
+ (await_primary_var = ((!p->call_invalid_rules && _prefix_8_valid)
? (p->mark = _prefix_8_end, _prefix_8_result) : (_prefix_8_result =
await_primary_rule(p), _prefix_8_end = p->mark, _prefix_8_valid = 1,
_prefix_8_result))) // await_primary
)
{
D(fprintf(stderr, "%*c+ power[%d-%d]: %s succeeded!\n", p->level,
' ', _mark, p->mark, "await_primary"));
@@ -14437,6 +14455,8 @@ primary_raw(Parser *p)
}
expr_ty _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_9_result = NULL;
+ int _prefix_9_end = 0, _prefix_9_valid = 0;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
p->level--;
@@ -14456,7 +14476,7 @@ primary_raw(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = primary_rule(p)) // primary
+ (a = ((!p->call_invalid_rules && _prefix_9_valid) ? (p->mark =
_prefix_9_end, _prefix_9_result) : (_prefix_9_result = primary_rule(p),
_prefix_9_end = p->mark, _prefix_9_valid = 1, _prefix_9_result))) // primary
&&
(_literal = _PyPegen_expect_token(p, 23)) // token='.'
&&
@@ -14494,7 +14514,7 @@ primary_raw(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = primary_rule(p)) // primary
+ (a = ((!p->call_invalid_rules && _prefix_9_valid) ? (p->mark =
_prefix_9_end, _prefix_9_result) : (_prefix_9_result = primary_rule(p),
_prefix_9_end = p->mark, _prefix_9_valid = 1, _prefix_9_result))) // primary
&&
(b = genexp_rule(p)) // genexp
)
@@ -14532,7 +14552,7 @@ primary_raw(Parser *p)
expr_ty a;
void *b;
if (
- (a = primary_rule(p)) // primary
+ (a = ((!p->call_invalid_rules && _prefix_9_valid) ? (p->mark =
_prefix_9_end, _prefix_9_result) : (_prefix_9_result = primary_rule(p),
_prefix_9_end = p->mark, _prefix_9_valid = 1, _prefix_9_result))) // primary
&&
(_literal = _PyPegen_expect_token(p, 7)) // token='('
&&
@@ -14574,7 +14594,7 @@ primary_raw(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = primary_rule(p)) // primary
+ (a = ((!p->call_invalid_rules && _prefix_9_valid) ? (p->mark =
_prefix_9_end, _prefix_9_result) : (_prefix_9_result = primary_rule(p),
_prefix_9_end = p->mark, _prefix_9_valid = 1, _prefix_9_result))) // primary
&&
(_literal = _PyPegen_expect_token(p, 9)) // token='['
&&
@@ -18823,6 +18843,8 @@ star_targets_rule(Parser *p)
}
expr_ty _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_10_result = NULL;
+ int _prefix_10_end = 0, _prefix_10_valid = 0;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
p->level--;
@@ -18840,7 +18862,7 @@ star_targets_rule(Parser *p)
D(fprintf(stderr, "%*c> star_targets[%d-%d]: %s\n", p->level, ' ',
_mark, p->mark, "star_target !','"));
expr_ty a;
if (
- (a = star_target_rule(p)) // star_target
+ (a = ((!p->call_invalid_rules && _prefix_10_valid) ? (p->mark =
_prefix_10_end, _prefix_10_result) : (_prefix_10_result = star_target_rule(p),
_prefix_10_end = p->mark, _prefix_10_valid = 1, _prefix_10_result))) //
star_target
&&
_PyPegen_lookahead_with_int(0, _PyPegen_expect_token, p, 12) //
token=','
)
@@ -18869,7 +18891,7 @@ star_targets_rule(Parser *p)
expr_ty a;
asdl_seq * b;
if (
- (a = star_target_rule(p)) // star_target
+ (a = ((!p->call_invalid_rules && _prefix_10_valid) ? (p->mark =
_prefix_10_end, _prefix_10_result) : (_prefix_10_result = star_target_rule(p),
_prefix_10_end = p->mark, _prefix_10_valid = 1, _prefix_10_result))) //
star_target
&&
(b = _loop0_98_rule(p)) // ((',' star_target))*
&&
@@ -20013,6 +20035,8 @@ expression_without_invalid_rule(Parser *p)
}
expr_ty _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_11_result = NULL;
+ int _prefix_11_end = 0, _prefix_11_valid = 0;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
p->call_invalid_rules = _prev_call_invalid;
@@ -20036,7 +20060,7 @@ expression_without_invalid_rule(Parser *p)
expr_ty b;
expr_ty c;
if (
- (a = disjunction_rule(p)) // disjunction
+ (a = ((!p->call_invalid_rules && _prefix_11_valid) ? (p->mark =
_prefix_11_end, _prefix_11_result) : (_prefix_11_result = disjunction_rule(p),
_prefix_11_end = p->mark, _prefix_11_valid = 1, _prefix_11_result))) //
disjunction
&&
(_keyword = _PyPegen_expect_token(p, 700)) // token='if'
&&
@@ -20080,7 +20104,7 @@ expression_without_invalid_rule(Parser *p)
D(fprintf(stderr, "%*c> expression_without_invalid[%d-%d]: %s\n",
p->level, ' ', _mark, p->mark, "disjunction"));
expr_ty disjunction_var;
if (
- (disjunction_var = disjunction_rule(p)) // disjunction
+ (disjunction_var = ((!p->call_invalid_rules && _prefix_11_valid) ?
(p->mark = _prefix_11_end, _prefix_11_result) : (_prefix_11_result =
disjunction_rule(p), _prefix_11_end = p->mark, _prefix_11_valid = 1,
_prefix_11_result))) // disjunction
)
{
D(fprintf(stderr, "%*c+ expression_without_invalid[%d-%d]: %s
succeeded!\n", p->level, ' ', _mark, p->mark, "disjunction"));
@@ -20271,6 +20295,8 @@ invalid_expression_rule(Parser *p)
}
void * _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_12_result = NULL;
+ int _prefix_12_end = 0, _prefix_12_valid = 0;
{ // STRING ((!STRING expression_without_invalid))+ STRING
if (p->error_indicator) {
p->level--;
@@ -20340,7 +20366,7 @@ invalid_expression_rule(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = disjunction_rule(p)) // disjunction
+ (a = ((!p->call_invalid_rules && _prefix_12_valid) ? (p->mark =
_prefix_12_end, _prefix_12_result) : (_prefix_12_result = disjunction_rule(p),
_prefix_12_end = p->mark, _prefix_12_valid = 1, _prefix_12_result))) //
disjunction
&&
(_keyword = _PyPegen_expect_token(p, 700)) // token='if'
&&
@@ -20373,7 +20399,7 @@ invalid_expression_rule(Parser *p)
expr_ty a;
expr_ty b;
if (
- (a = disjunction_rule(p)) // disjunction
+ (a = ((!p->call_invalid_rules && _prefix_12_valid) ? (p->mark =
_prefix_12_end, _prefix_12_result) : (_prefix_12_result = disjunction_rule(p),
_prefix_12_end = p->mark, _prefix_12_valid = 1, _prefix_12_result))) //
disjunction
&&
(_keyword = _PyPegen_expect_token(p, 700)) // token='if'
&&
@@ -20520,6 +20546,8 @@ invalid_if_expression_rule(Parser *p)
}
void * _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_13_result = NULL;
+ int _prefix_13_end = 0, _prefix_13_valid = 0;
{ // disjunction 'if' disjunction 'else' '*'
if (p->error_indicator) {
p->level--;
@@ -20532,7 +20560,7 @@ invalid_if_expression_rule(Parser *p)
expr_ty b;
expr_ty disjunction_var;
if (
- (disjunction_var = disjunction_rule(p)) // disjunction
+ (disjunction_var = ((!p->call_invalid_rules && _prefix_13_valid) ?
(p->mark = _prefix_13_end, _prefix_13_result) : (_prefix_13_result =
disjunction_rule(p), _prefix_13_end = p->mark, _prefix_13_valid = 1,
_prefix_13_result))) // disjunction
&&
(_keyword = _PyPegen_expect_token(p, 700)) // token='if'
&&
@@ -20568,7 +20596,7 @@ invalid_if_expression_rule(Parser *p)
expr_ty b;
expr_ty disjunction_var;
if (
- (disjunction_var = disjunction_rule(p)) // disjunction
+ (disjunction_var = ((!p->call_invalid_rules && _prefix_13_valid) ?
(p->mark = _prefix_13_end, _prefix_13_result) : (_prefix_13_result =
disjunction_rule(p), _prefix_13_end = p->mark, _prefix_13_valid = 1,
_prefix_13_result))) // disjunction
&&
(_keyword = _PyPegen_expect_token(p, 700)) // token='if'
&&
@@ -25460,6 +25488,8 @@ invalid_kvpair_unpacking_rule(Parser *p)
}
void * _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_14_result = NULL;
+ int _prefix_14_end = 0, _prefix_14_valid = 0;
{ // '**' if_expression
if (p->error_indicator) {
p->level--;
@@ -25564,7 +25594,7 @@ invalid_kvpair_unpacking_rule(Parser *p)
expr_ty b;
expr_ty expression_var;
if (
- (expression_var = expression_rule(p)) // expression
+ (expression_var = ((!p->call_invalid_rules && _prefix_14_valid) ?
(p->mark = _prefix_14_end, _prefix_14_result) : (_prefix_14_result =
expression_rule(p), _prefix_14_end = p->mark, _prefix_14_valid = 1,
_prefix_14_result))) // expression
&&
(_literal = _PyPegen_expect_token(p, 11)) // token=':'
&&
@@ -25597,7 +25627,7 @@ invalid_kvpair_unpacking_rule(Parser *p)
expr_ty b;
expr_ty expression_var;
if (
- (expression_var = expression_rule(p)) // expression
+ (expression_var = ((!p->call_invalid_rules && _prefix_14_valid) ?
(p->mark = _prefix_14_end, _prefix_14_result) : (_prefix_14_result =
expression_rule(p), _prefix_14_end = p->mark, _prefix_14_valid = 1,
_prefix_14_result))) // expression
&&
(_literal = _PyPegen_expect_token(p, 11)) // token=':'
&&
@@ -25642,6 +25672,8 @@ invalid_kvpair_rule(Parser *p)
}
void * _res = NULL;
int _mark = p->mark;
+ expr_ty _prefix_15_result = NULL;
+ int _prefix_15_end = 0, _prefix_15_valid = 0;
{ // expression !(':')
if (p->error_indicator) {
p->level--;
@@ -25650,7 +25682,7 @@ invalid_kvpair_rule(Parser *p)
D(fprintf(stderr, "%*c> invalid_kvpair[%d-%d]: %s\n", p->level, ' ',
_mark, p->mark, "expression !(':')"));
expr_ty a;
if (
- (a = expression_rule(p)) // expression
+ (a = ((!p->call_invalid_rules && _prefix_15_valid) ? (p->mark =
_prefix_15_end, _prefix_15_result) : (_prefix_15_result = expression_rule(p),
_prefix_15_end = p->mark, _prefix_15_valid = 1, _prefix_15_result))) //
expression
&&
_PyPegen_lookahead_with_int(0, _PyPegen_expect_token, p, 11) //
token=(':')
)
@@ -25679,7 +25711,7 @@ invalid_kvpair_rule(Parser *p)
expr_ty bitwise_or_var;
expr_ty expression_var;
if (
- (expression_var = expression_rule(p)) // expression
+ (expression_var = ((!p->call_invalid_rules && _prefix_15_valid) ?
(p->mark = _prefix_15_end, _prefix_15_result) : (_prefix_15_result =
expression_rule(p), _prefix_15_end = p->mark, _prefix_15_valid = 1,
_prefix_15_result))) // expression
&&
(_literal = _PyPegen_expect_token(p, 11)) // token=':'
&&
@@ -25712,7 +25744,7 @@ invalid_kvpair_rule(Parser *p)
expr_ty bitwise_or_var;
expr_ty expression_var;
if (
- (expression_var = expression_rule(p)) // expression
+ (expression_var = ((!p->call_invalid_rules && _prefix_15_valid) ?
(p->mark = _prefix_15_end, _prefix_15_result) : (_prefix_15_result =
expression_rule(p), _prefix_15_end = p->mark, _prefix_15_valid = 1,
_prefix_15_result))) // expression
&&
(_literal = _PyPegen_expect_token(p, 11)) // token=':'
&&
@@ -25743,7 +25775,7 @@ invalid_kvpair_rule(Parser *p)
Token * a;
expr_ty expression_var;
if (
- (expression_var = expression_rule(p)) // expression
+ (expression_var = ((!p->call_invalid_rules && _prefix_15_valid) ?
(p->mark = _prefix_15_end, _prefix_15_result) : (_prefix_15_result =
expression_rule(p), _prefix_15_end = p->mark, _prefix_15_valid = 1,
_prefix_15_result))) // expression
&&
(a = _PyPegen_expect_token(p, 11)) // token=':'
&&
diff --git a/Tools/peg_generator/pegen/c_generator.py
b/Tools/peg_generator/pegen/c_generator.py
index b233ea746330ee6..044366c3aac1405 100644
--- a/Tools/peg_generator/pegen/c_generator.py
+++ b/Tools/peg_generator/pegen/c_generator.py
@@ -375,6 +375,35 @@ def generate_call(self, node: Any) -> FunctionCall:
return super().visit(node)
+def consuming_rules(rules: dict[str, Rule]) -> set[str]:
+ """Conservatively prove which rules consume a token whenever they
succeed."""
+ consuming: set[str] = set()
+
+ def consumes(node: Any) -> bool:
+ if isinstance(node, NamedItem):
+ return consumes(node.item)
+ if isinstance(node, NameLeaf):
+ return node.value not in rules or node.value in consuming
+ if isinstance(node, StringLeaf):
+ return True
+ if isinstance(node, Group):
+ return consumes(node.rhs)
+ if isinstance(node, Rhs):
+ return bool(node.alts) and all(any(consumes(i) for i in alt.items)
for alt in node.alts)
+ if isinstance(node, (Forced, Repeat1, Gather)):
+ return consumes(node.node)
+ # Predicates, cuts, optional items, and zero-or-more items can succeed
+ # without consuming. Actions are assumed not to rewrite parser marks.
+ return False
+
+ while True:
+ added = {name for name, rule in rules.items()
+ if name not in consuming and consumes(rule.rhs)}
+ if not added:
+ return consuming
+ consuming.update(added)
+
+
class CParserGenerator(ParserGenerator, GrammarVisitor):
def __init__(
self,
@@ -394,6 +423,8 @@ def __init__(
self.debug = debug
self.skip_actions = skip_actions
self.cleanup_statements: list[str] = []
+ self.consuming = consuming_rules(self.rules)
+ self.prefix_calls: dict[int, tuple[str, str, str]] = {}
def add_level(self) -> None:
self.print("if (p->level++ == MAXSTACK || _PyPegen_stack_exhausted(p))
{")
@@ -615,6 +646,7 @@ def _handle_default_rule_body(self, node: Rule, rhs: Rhs,
result_type: str) -> N
self.add_return("_res")
self.print("}")
self.print("int _mark = p->mark;")
+ self.prepare_prefix_calls(rhs)
if any(alt.action and "EXTRA" in alt.action for alt in rhs.alts):
self._set_up_token_start_metadata_extraction()
self.visit(
@@ -674,7 +706,37 @@ def _handle_loop_rule_body(self, node: Rule, rhs: Rhs) ->
None:
self.print(f"_PyPegen_insert_memo(p, _start_mark,
{node.name}_type, _seq);")
self.add_return("_seq")
+ def prepare_prefix_calls(self, rhs: Rhs) -> None:
+ # Reuse a memoized, consuming prefix only within a consecutive group.
+ # Suffix parsing starts after the prefix and cannot revisit its start
+ # through ordinary grammar backtracking. Diagnostic calls are
unchanged.
+ def candidate(alt: Alt) -> Rule | None:
+ if not alt.items or not isinstance(alt.items[0].item, NameLeaf):
+ return None
+ rule = self.rules.get(alt.items[0].item.value)
+ if rule is None or rule.name not in self.consuming:
+ return None
+ if self._should_memoize(rule) or (rule.left_recursive and
rule.leader):
+ return rule
+ return None
+
+ i = 0
+ while i < len(rhs.alts):
+ rule = candidate(rhs.alts[i])
+ j = i + 1
+ while rule is not None and j < len(rhs.alts) and
candidate(rhs.alts[j]) is rule:
+ j += 1
+ if rule is not None and j - i > 1:
+ name = self.unique_varname("_prefix")
+ result, end, valid = name + "_result", name + "_end", name +
"_valid"
+ self.print(f"{rule.type or 'void *'} {result} = NULL;")
+ self.print(f"int {end} = 0, {valid} = 0;")
+ for alt in rhs.alts[i:j]:
+ self.prefix_calls[id(alt.items[0])] = result, end, valid
+ i = j
+
def visit_Rule(self, node: Rule) -> None:
+ self.prefix_calls = {}
is_loop = node.is_loop()
is_gather = node.is_gather()
rhs = node.flatten()
@@ -716,6 +778,15 @@ def visit_Rule(self, node: Rule) -> None:
def visit_NamedItem(self, node: NamedItem) -> None:
call = self.callmakervisitor.generate_call(node)
+ if id(node) in self.prefix_calls:
+ result, end, valid = self.prefix_calls[id(node)]
+ original = f"{call.function}({', '.join(map(str,
call.arguments))})"
+ call.function = (
+ f"((!p->call_invalid_rules && {valid}) ? "
+ f"(p->mark = {end}, {result}) : "
+ f"({result} = {original}, {end} = p->mark, {valid} = 1,
{result}))"
+ )
+ call.arguments = []
if call.assigned_variable:
call.assigned_variable = self.dedupe(call.assigned_variable)
self.print(call)
_______________________________________________
Python-checkins mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3//lists/python-checkins.python.org
Member address: [email protected]
