| Ticket UUID: | 3574242 | ||
| Title: | exact match is greedy by reluctant exact match quantifier | ||
| Type: | Bug | Created on: | 2012-10-03 22:30:52 |
| Submitter: | sebres | Assigned to: | sebres |
| Subsystem: | 43. Regexp | Severity: | Minor |
| Priority: | 7 High | Last modified: | 2019-11-22 20:24:39 |
| Status: | Open | Closed by: | nobody |
| Resolution: | None | Closed on: | |
| Version: | None | ||
| Description: | ||||
Possible bug, cause IMO that should match the same:
Or a documentation bug - according to documentation "{m}?" is ungreedy quantifier.
% regexp -inline {((?:ab|abc){1}?)(cd|d){1}?} abcd
abcd abc d
% regexp -inline {((?:ab|abc){1,1}?)(cd|d){1,1}?} abcd
abcd ab cd
| ||||
| User Comments: | ||||
sebres added on 2019-11-22 14:52:40:
A fresh concern regarding the issue and new findings after discussion in tclchat with pooryorick. The issue could be explained with following sentence from the documentation: A quantified atom with quantifier {m} or {m}? has the same preference (possibly none) as the atom itself. A quantified atom with other normal quantifiers (including {m,n} with m equal to n) prefers longest match. A quantified atom with other non-greedy quantifiers (including {m,n}? with m equal to n) prefers shortest match. But the fact that Another interesting set of examples which can be related to the same issue:
% regexp -inline {(t*?)?} ttt
ttt ttt
% regexp -inline {(t*)?} ttt
ttt ttt
Although it behaves like described in the documentation:A branch has the same preference as the first quantified atom in it which has a preference. An RE consisting of two or more branches connected by the | operator prefers longest match. But it does not explain why the group is expanded to the whole match, as well as the difference to this counter-example:
% regexp -all -inline {(t)*} ttt
ttt t
So the change to greedy quantifier of RE seems to affect capturing behavior of (initially) non-greedy group, compared to (initially) greedy group. FWIW, maybe following would explain the reason (or rather the necessity) why or for which cases the sub-branch (group) could be non-greedy (why this can be expected or used):
% regexp -inline {(t*?(\w+))?} ttxx
ttxx ttxx ttxx
% regexp -inline {(t*(\w+))?} ttxx
ttxx ttxx xx
But that all still don't explain the growth of captured non-greedy group to the whole match.
sebres added on 2019-11-22 17:13:34:
If the issue is "caused" because RE-engine following main rule "greediness of topmost expression wins" or like a Kevin's statement: A general rule is that the greediness of the outermost quantifier determines the greediness of everything in the subexpression. it could explain why initially non-greedy subexpression grows, even to fulfill the whole match be greedy. So for example here the first capturing group grows to whole match, the second (inner) group capturing
% regexp -inline {((a*f)*?)?} aaafaaf
aaafaaf aaafaaf aaf
But there is just another example illustrating that this "concept" is not completely correct:
% regexp -inline {((a*f)*?)*} aaafaaf
aaafaaf aaf aaf
% regexp -inline {((a*f)*?)+} aaafaaf
aaafaaf {} {}
Both of topmost quantifiers (red/green) are greedy, the whole expression is greedy. So the (more aggressive) quantifier sebres added on 2019-11-22 20:24:39:
After pretty productive discussion in tclchat with Andrew Gierth (RhodiumToad) we have new other findings now. The new handling of quantifier "+" (in contrary to "*") as well as "{1,}" (in contrary to "{0,}") makes impossible to retrieve indices of last successful matched capturing groups, which results to impossibly to differentiate which sub-group (expression) causes the match exactly. I hope following example would illustrate that:
% regexp -indices -inline {((a?)*|(b?)*)*} aaa
{0 2} {0 2} {2 2} {-1 -1}
% regexp -indices -inline {((a?)*|(b?)*)+} aaa
{0 2} {3 2} {-1 -1} {-1 -1}
So it is basically impossible to differentiate which of last child sub-group (a?)* or (b?)* caused a match of the parent (which is also mistakenly an empty match outside of string - The same is valid for this (note the "*" instead of "?" in both last nesting groups):
% regexp -indices -inline {((a*)*|(b*)*)*} aaa
{0 2} {0 2} {0 2} {-1 -1}
% regexp -indices -inline {((a*)*|(b*)*)+} aaa
{0 2} {3 2} {-1 -1} {-1 -1}
Either one would expect the same result as using "*" instead of "+" here.
% regexp -indices -inline {((a?)*|(b?)*)+} aaa
% regexp -indices -inline {((a*)*|(b*)*)+} aaa
{0 2} {2 1} {2 1} {-1 -1}
Andrew is also going to file this as a Postgres bug... | ||||
