Cut (~) operator in grammar unclear

[99991]

Python's Full Grammar specification and PEP 617 states:

~ (“cut”): commit to the current alternative and fail the rule even [NB: typo?] if this [alternative] fails to parse

It is not clear to me whether the cut applies to all alternatives in the current parse tree or only the latest alternative. Apparently, there are both types of cuts, as has been discussed in this issue, and I think (?) the conclusion by Guido was

Your first quote convinces me that cut is meant to act locally (which is how I have implemented it).

But the current grammar contains rules where the cut appears (to me) to be useless, for example:

assignment_expression:
    | NAME ':=' ~ expression 

If cut only acts locally on this single rule, wouldn't the rule be the same without the cut, since there are no alternatives to skip over in case expression fails to parse?

Either way, it would be nice if the documentation could be clarified with regard to which kind of cut is used in Python's grammar.

Linked PRs

• gh-143054: Disallow non-top-level Cut for now #143622
• [3.14] gh-143054: Disallow non-top-level Cut for now (GH-143622) #143790

[StanFromIreland]

CC @encukou

[encukou]

Hmm... this isn't clear to me either.
Looking at the implementation: if an alternative matches up to a cut, then other alternatives in the current Rhs are skipped. But, we don't quite define what Rhs is; and there's a flatten operation that inlines parenthesized groups into a “parent” Rhs.

@lysnikolaou, do you know what exactly a cut should do? (I'm interested in the intent more than the current behaviour.)

This might be an academic question as this point -- it does looks like in the documented grammar, all cuts are “useless”.

---

If cut only acts locally on this single rule, wouldn't the rule be the same without the cut, since there are no alternatives to skip over in case expression fails to parse?

Cuts are taken from the actual grammar as used by CPython. Some other details are omitted in the docs, though.
So, while a cut might look “useless”, it might be there to support better error messages (invalid rules) or as an optimization.

I guess people expect formal grammars in docs to be simplified (in the mathematical sense), and we should note that this one isn't.
(Generating simplified (but equivalent) grammar is on my TODO list, but currently blocked by other tasks that will take a long time.)

[lysnikolaou]

do you know what exactly a cut should do? (I'm interested in the intent more than the current behaviour.)

I can only confirm that when cut was initially added to the grammar, the intention was to locally commit to the current alternative, i.e. fail the whole rule if the current alternative fails.

So, while a cut might look “useless”, it might be there to support better error messages (invalid rules) or as an optimization.

Yup, cuts most of the time are optimizations. If I'm not mistaken, the current status is that we mostly cut before invalid alternatives when we know that no customized error messages will be relevant. If I remember correctly, there was a time when there were some significant cuts in the grammar but that's not true anymore.

assignment_expression:
    | NAME ':=' ~ expression

Skimming quickly through the grammar, it seems like this is indeed unnecessary. It might be a remnant from refactoring the rule but not removing the cut.

[gvanrossum]

Sadly, even though I wrote the initial PEG parser, I don't recall the precise semantics of cut either. We're sure a bumbling set of experts here! :-)

I have a feeling though that it might mean "If we got this far, this is definitely the right alternative, and if we don't see what's expected after this point, that's an error". IIRC if we were to omit the cut, on failure to match the entire alternative would make the parser attempt other alternatives (also at a higher level than the current list of alternatives) causing less precise error reporting? Under this interpretation cut is not always just an optimization -- it may prevent a later non-error alternative from being taken in parts of the grammar where ordering matters (in general, the order of alternatives does matter with PEG, unless for classic context-free grammars).

CC'ing @apalala (creator of TatSu), maybe he recalls the exact rules for the cut operator.

[apalala]

Hi Guido, Your interpretation is correct. A parsed cut will prevent other alternatives from being tried. When we discussed this before you had concerns about a cut escaping the current rule. I think TatSu does let it escape, and I think either way is good, though a cut in a one-alternative rule is hard to grok. About the error reporting, most agree that the parser should keep a `furthest_pos`, and report any errors against it. You should consider what rules like this mean: letter = ('a' ~ ) *. # should be equivalent to 'a'+? FWIW, TatSu clears the memo cache by evicting any memos with a position lower than the one of a parsed cut. Today I'm changing that to a bounded cache of size 1024, and I see no performance differences with the parsers for Java and COBOL. Happy Holidays! -- Juancarlo Añez ***@***.***

[gvanrossum]

A parsed cut will prevent other alternatives from being tried.

I think we're all in agreement on that. What I'm not sure about (nor do I know what Python's PEG parser does nor whether it ever occurs in our grammar) is this:

start: xx | yy | zz

xx: ...
yy: NAME `=` ~ NUMBER | NAME '+=' NUMBER
zz: NAME = NAME

Here I wonder if on input foo = bar the zz alternative is considered or not -- IOW, is the cut global or local. Is there a standard answer in the world of PEG theory?

[apalala]

I didn't find much written about cut in PEG. There's a paper by Kota Mizushima that I think is about automatically introducing cut during grammar parsing. I knew cut would be useful in Grako/Tatsu because of my experience in grammar parsing with PROLOG. In your example the answer is _yes_, zz will be considered. What will never be considered is the `NAME += NUMBER` alternative, because the cut is in front of NUMBER, which means that the whole rule will fail if what's next doesn't match NUMBER. With: yy: NAME `=` NUMBER ~ | NAME '+=' NUMBER Every alternative will be considered. See: https://gemini.google.com/share/f241ecbade42

…

-- Juancarlo Añez ***@***.***

On Thu, Dec 25, 2025 at 1:56 PM Guido van Rossum ***@***.***> wrote: *gvanrossum* left a comment (python/cpython#143054) <#143054 (comment)> A parsed cut will prevent other alternatives from being tried. I think we're all in agreement on that. What I'm not sure about (nor do I know what Python's PEG parser does nor whether it ever occurs in our grammar) is this: start: xx | yy | zz xx: ... yy: NAME `=` ~ NUMBER | NAME '+=' NUMBER zz: NAME = NAME Here I wonder if on input foo = bar the zz alternative is considered or not -- IOW, is the cut global or local. Is there a standard answer in the world of PEG theory? — Reply to this email directly, view it on GitHub <#143054 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAEI5FMND4NLSFITU7IYL5L4DQQMHAVCNFSM6AAAAACPWKNUP6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTMOJRGYZTQNZQGY> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[apalala]

As to the error reporting, this is what TatSu does: try: rule = self._find_rule(start) return rule() except FailedCut as e: self._set_furthest_exception(e.nested) raise self._furthest_exception from e except FailedParse as e: self._set_furthest_exception(e) raise self._furthest_exception from e finally: self._clear_memoization_caches() def _set_furthest_exception(self, e): if ( not self._furthest_exception or e.pos > self._furthest_exception.pos ): self._furthest_exception = e In your parser, you'd have to save `furthest_pos` and `furthest_errror`, or something like that.

…

-- Juancarlo Añez ***@***.***

On Thu, Dec 25, 2025 at 2:23 PM Juancarlo Añez ***@***.***> wrote: I didn't find much written about cut in PEG. There's a paper by Kota Mizushima that I think is about automatically introducing cut during grammar parsing. I knew cut would be useful in Grako/Tatsu because of my experience in grammar parsing with PROLOG. In your example the answer is _yes_, zz will be considered. What will never be considered is the `NAME += NUMBER` alternative, because the cut is in front of NUMBER, which means that the whole rule will fail if what's next doesn't match NUMBER. With: yy: NAME `=` NUMBER ~ | NAME '+=' NUMBER Every alternative will be considered. See: https://gemini.google.com/share/f241ecbade42 -- Juancarlo Añez ***@***.*** On Thu, Dec 25, 2025 at 1:56 PM Guido van Rossum ***@***.***> wrote: > *gvanrossum* left a comment (python/cpython#143054) > <#143054 (comment)> > > A parsed cut will prevent other alternatives from being tried. > > I think we're all in agreement on that. What I'm not sure about (nor do I > know what Python's PEG parser does nor whether it ever occurs in our > grammar) is this: > > start: xx | yy | zz > > xx: ... > yy: NAME `=` ~ NUMBER | NAME '+=' NUMBER > zz: NAME = NAME > > Here I wonder if on input foo = bar the zz alternative is considered or > not -- IOW, is the cut global or local. Is there a standard answer in the > world of PEG theory? > > — > Reply to this email directly, view it on GitHub > <#143054 (comment)>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/AAEI5FMND4NLSFITU7IYL5L4DQQMHAVCNFSM6AAAAACPWKNUP6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTMOJRGYZTQNZQGY> > . > You are receiving this because you were mentioned.Message ID: > ***@***.***> >

[apalala]

I forgot to mention the interaction between cut and lookaheads. For example: statement = | &'if' ~ if_statement | &'while' ~ while_statement | ... There's no point in trying a rule when there's a cheap way to narrow the alternatives.

…

-- Juancarlo Añez ***@***.***

[gvanrossum]

Okay. So my main question is now cleared up: cut only affects the current list of alternatives, skipping the remaining alternatives in the list if a cut was reached but a failure occurred after that in the same alternative. Ergo, a cut in the last or only alternative for a given rule has no effect.

Thinking about using cut in a parenthesized list of alternatives, I think the most sensitive interpretation is to let its scope be just that parenthesized list. So from that, ('a' ~) makes little sense, and I don't understand why ('a' ~)* would have a different meaning than 'a'*. So I am stull confused about @apalala's example. But maybe I don't follow what *. and *? mean? Those don't exist in Python's PEG parser generator, AFAIK.

[apalala]

In TatSu * means repeat zero or more times, and + means repeat one or more times. There is an implicit choice in 'a'*, which is ('a'|()). I think you're correct in that ('a' ~)* does nothing new. But consider ('a' ~ 'b')*. Let me ask for permission to share the TatSu grammar for Java, which has plenty of uses of cut. Note that cut may interfere with alternatives for error reporting or parser recovery, because those are usually the last alternative in a choice. I changed TatSu so it doesn't let cut exceptions travel outside the nearest choice. Previously this grammar would always fail, and now it produces 'something', which a more sensible outcome. GRAMMAR = ''' start = | one | two ; one = | ~ !() # cut fail | 'abc'; two = `something` ; # result is the quoted text ''' -- Juancarlo Añez ***@***.***

…

On Fri, Dec 26, 2025 at 1:29 PM Guido van Rossum ***@***.***> wrote: *gvanrossum* left a comment (python/cpython#143054) <#143054 (comment)> Okay. So my main question is now cleared up: cut only affects the current list of alternatives, skipping the remaining alternatives in the list if a cut was reached but a failure occurred after that in the same alternative. Ergo, a cut in the last or only alternative for a given rule has no effect. Thinking about using cut in a parenthesized list of alternatives, I think the most sensitive interpretation is to let its scope be *just* that parenthesized list. So from that, ('a' ~) makes little sense, and I don't understand why ('a' ~)* would have a different meaning than 'a'*. So I am stull confused about @apalala <https://github.com/apalala>'s example. But maybe I don't follow what *. and *? mean? Those don't exist in Python's PEG parser generator, AFAIK. — Reply to this email directly, view it on GitHub <#143054 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAEI5FLCEMMJE2R2DQTBVND4DVV75AVCNFSM6AAAAACPWKNUP6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZTMOJTGE2DGOBWGA> . You are receiving this because you were mentioned.Message ID: ***@***.***>