You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oro-user@jakarta.apache.org by Kayiti Devanandam <ka...@webmethods.com> on 2005/05/03 12:53:23 UTC
RE: Pattern Regular Expressions: Consecutive ORs not handled corr
ectl y
Hi Daniel,
Please do find attached the test case for it. (testRegEx.java which can be
compiled with putting "jakarta-oro-2.0.8.jar" in the classpath.)
With both the 2.0.5 and 2.0.8 versions I am finding the following results:
For the stringPattern -->> \d{3}|\d{3}(.)\d{2}
123 -> Passed
123.46 Failed (which shouldn't fail)
For the stringPattern -->> \d{3}(.)\d{2}|\d{3}
123 -> Passed
123.46 -> Passed
You can out the stringPattern in the main method (line no 65) and compile
and see the results by
java testRegEx 123
Give the values to be validated as arguments in the command line. I think
now u can appreciate the problem very well. Sorry I couldn't attach the
testCase earlier.
Here in this case for the first case (\d{3}|\d{3}(.)\d{2}), 123.46 shouldn't
have been failed. Can u find out why this is happenning?
Thanks and Regards
Dev
-----Original Message-----
From: Daniel F. Savarese [mailto:dfs@savarese.org]
Sent: Tuesday, May 03, 2005 3:51 AM
To: ORO Users List
Subject: Re: Pattern Regular Expressions: Consecutive ORs not handled corr
ectl y
In message <A3...@mailwest-e6>, Kayiti
Devan andam writes:
>For the regular Expression \d{3}[.]\d{2}[.]\d{2}|\d{3}[.]\d{2}|\d{3}
>"123" string fails. But for 123.45 passes. (123 fails but it actually
>should have successfully validated since it correctly validated by the
>last OR Expression \d{3}...so it should have been validated.
Still need a test case that reproduces the problem. For example, I still
don't know if you're talking about contains or matches. In any case, I can
find no problem:
java examples.matchResultExample '\d{3}[.]\d{2}[.]\d{2}|\d{3}[.]\d{2}|\d{3}'
123
Match: 123
Length: 3
Groups: 1
Begin offset: 0
End offset: 3
Groups:
java examples.matchResultExample '\d{3}[.]\d{2}[.]\d{2}|\d{3}[.]\d{2}|\d{3}'
123.45
Match: 123.45
Length: 6
Groups: 1
Begin offset: 0
End offset: 6
Groups:
java examples.matchResultExample
'\d{3}[.]\d{2}[.]\d{2}|(\d{3}[.]\d{2}|\d{3})' 123
Match: 123
Length: 3
Groups: 2
Begin offset: 0
End offset: 3
Groups:
1: 123
Begin: 0
End: 3
java examples.matchResultExample
'\d{3}[.]\d{2}[.]\d{2}|(\d{3}[.]\d{2}|\d{3})' 123.45
Match: 123.45
Length: 6
Groups: 2
Begin offset: 0
End offset: 6
Groups:
1: 123.45
Begin: 0
End: 6
Those runs are using the matchResultExample program from src/java/examples.
I tested matches() using the demo applet with:
Perl5 Expression: \d{3}[.]\d{2}[.]\d{2}|\d{3}[.]\d{2}|\d{3}
Search Input: 123
Search Results:
Compiling regular expression.
Searching
The input IS an EXACT match.
Usually, the issue with matches() is the "foo|foot" issue, requiring one to
change the expression to start with ^ and end with $ to force the extra
backtracking. But that doesn't seem to be the case here.
At any rate, I can't reproduce the behavior. Assuming version 2.0.5 was not
a typo, then maybe there was a bug in 2.0.5 that was fixed by version 2.0.8.
However, just to be completely thorough, I downloaded version 2.0.5 and:
java -classpath ./jakarta-oro-2.0.5.jar:. examples.matchResultExample
'\d{3}[.]\d{2}[.]\d{2}|\d{3}[.]\d{2}|\d{3}' 123
Match: 123
Length: 3
Groups: 1
Begin offset: 0
End offset: 3
Groups:
I can't reproduce the reported behavior in any way. Assuming the problem
exists in an even earlier version of the library, then perhaps you've got an
earlier version sitting in your classpath. That happens sometimes when
using application servers since the software was included in most of the
major J2EE servers for a period of time. But without a test program, all I
can do is speculate and guess. The quickest way to resolve these issues is
to post self-contained code that reproduces the problem. That way we can
figure out if the problem is in the library, in the code, or something else.
daniel
---------------------------------------------------------------------
To unsubscribe, e-mail: oro-user-unsubscribe@jakarta.apache.org
For additional commands, e-mail: oro-user-help@jakarta.apache.org
Re: Re[6]: Pattern Regular Expressions: Consecutive ORs not handled corr ectl y
Posted by "robert.emmery" <ro...@bizilogic.com>.
Sergey,
The way ORO's "matches" function works in this case coincides with the way
perl regex engine works. While foo|foot example may seem odd to someone new
to regular expressions, it is a well understood fact about perl's matching
mechanics to many people. The simple rule about perl's regex that may help
is: Perl's alternations are not greedy. Knowing this, and understanding the
basic workings of traditional NFA engines should help explain why foo|foot
will match "foo" in "football" and not "foot" as one may expect. Other types
of engines (DFA or Posix NFA) will always match the longest of the leftmost,
in this case "foot".
Traditional NFA such as perl starts with the regular expression's first
character and tries to match the first character in the text. If you have
expression \d{3}|d{3}\.\d{2} and text "123.45", perl will look at \d{3}
first and see if it can match it to "1" in "123". To have a successful
match, at least one permutation of the regular expression must be matched
against the text. What's different about traditional NFA is that the first
permutation that matches is good enough. Knowing this can be pretty valuable
since you can craft your expressions so that the permutations which would
match fastest are tried first. In many cases, fine tuned perl regex can
outperform a DFA regex which keeps track of all matches so far until it
finds the longest. Another important thing to note is that all quantifiers
(like * and ? ) are greedy. With this in mind, one can achieve a greedy
alternation in traditional NFA by using ? quantifier. If you had an
expression like he(ll|llo) and text "hello" you could match "hello" if you
rewrite the expression as he(ll(llo)?)? However, I would still re-write the
expression as he(llo|ll), as long as I understand that it translates
to "Match hello if you can, if not, try to match hell". This is not the same
as "Match the longest of either hell or hello". If you think about it, the
last sentence is really semantically equivalent to "Match the longest of
either hello or hell" which is also the syntax that perl expects for such
semantic interpretation.
DFA and Posix will try to match text to the regular expression. So in your
case, they'll take "1" in "123.45" and try to match it to \{d3}|d{3}\.d{2}.
The result will always be the same, no matter how you order your
alternations, as the longst match wins.
Clearly two different approaches to matching. This said, asking for ORO's
matcher to have greedy alternations would be asking for a completely
different flavor of the regex engine inside ORO. Finally, making this type
of change would break many applications which currently rely on perl's regex
semantics.
Regards,
-Rob
On Fri, 13 May 2005 23:11:27 +0400, Sergey Samokhodkin wrote
> Hello Daniel!
>
> Friday, May 6, 2005, 11:16:54 PM, you wrote:
>
> DFS> .....
> DFS> The heart of the matter seems to be a difference in
> expectations. I
>
> Of course, but isn't my expectation *natural*?
>
> DFS> understand why you could expect matches() to behave that way.
> However, DFS> its documentation explains that it's not the same as
> ^pattern$. I'll
>
> In fact, it only states the difference without any real explanation.
> Let me cite:
> > matches() literally looks for an exact match according to the rules
> > of Perl5 expression matching. Therefore, if you have a pattern
> > foo|foot and are matching the input foot it will not produce an exact
match
>
> How "therefore"???
> Anyone who finds it clear (esp. Kevin Markey), please guess which of
> the following is true:
>
> /foot?/ matches "foot"
> /foot?/ matches "foo"
> /foot??/ matches "foot"
> /foot??/ matches "foo"
>
> DFS> matches() tests whether or not a pattern matches the input it
> is given. DFS> This means that the matching process must start at
> the beginning of DFS> the input and stop at the end of the input.
> If the matching process stops DFS> before the end of the input, then
> there's no match. The method answers DFS> the question "Is this
> input character sequence a member of the set of all DFS> the
> character sequences matched by this pattern?"
>
> Ooops!
> The matching set for "foo|foot" is {"foo","foot"}.
> The matching set for "foot|foo" is ***the same***. Order doesn't
> matter in sets.
>
> DFS> It may make more sense thinking about it this way. matches()
> returns true DFS> if and only if S =~ m/(P)/ is true and $1 equals
> S. For example:
>
> DFS> sub matches(@) {
> DFS> my ($pat, $str) = @_;
> DFS> $str =~ m/($pat)/;
> DFS> return ($str eq $1);
> DFS> }
>
> DFS> printf "%d\n%d\n", matches("foo|foot", "foo"),
> matches("foo|foot", "foot");
>
> Yes, that's it. Something like that had to be in the docs.
>
> DFS> In my opinion, the important thing is for the behavior to be
documented.
> DFS> If it's not sufficiently clear, then we ought to make it more clear.
> DFS> Documentation patches are welcome.
>
> DFS> Now, one can argue that we should add a validate() method specifically
> DFS> for input validation with the behavior you expected. My opinion
>
> I'd say that the best method would be the "matches()" itself (see my
> first remark).
> Otherwise the question is closed.
> Thanks a lot for your patience.
>
> DFS> daniel
>
> --
> Best regards,
> Sergey
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: oro-user-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: oro-user-help@jakarta.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: oro-user-unsubscribe@jakarta.apache.org
For additional commands, e-mail: oro-user-help@jakarta.apache.org
Re[6]: Pattern Regular Expressions: Consecutive ORs not handled corr ectl y
Posted by Sergey Samokhodkin <se...@zolshar.ru>.
Hello Daniel!
Friday, May 6, 2005, 11:16:54 PM, you wrote:
DFS> .....
DFS> The heart of the matter seems to be a difference in expectations. I
Of course, but isn't my expectation *natural*?
DFS> understand why you could expect matches() to behave that way. However,
DFS> its documentation explains that it's not the same as ^pattern$. I'll
In fact, it only states the difference without any real explanation.
Let me cite:
> matches() literally looks for an exact match according to the rules
> of Perl5 expression matching. Therefore, if you have a pattern
> foo|foot and are matching the input foot it will not produce an exact match
How "therefore"???
Anyone who finds it clear (esp. Kevin Markey), please guess which of
the following is true:
/foot?/ matches "foot"
/foot?/ matches "foo"
/foot??/ matches "foot"
/foot??/ matches "foo"
DFS> matches() tests whether or not a pattern matches the input it is given.
DFS> This means that the matching process must start at the beginning of
DFS> the input and stop at the end of the input. If the matching process stops
DFS> before the end of the input, then there's no match. The method answers
DFS> the question "Is this input character sequence a member of the set of all
DFS> the character sequences matched by this pattern?"
Ooops!
The matching set for "foo|foot" is {"foo","foot"}.
The matching set for "foot|foo" is ***the same***. Order doesn't
matter in sets.
DFS> It may make more sense thinking about it this way. matches() returns true
DFS> if and only if S =~ m/(P)/ is true and $1 equals S. For example:
DFS> sub matches(@) {
DFS> my ($pat, $str) = @_;
DFS> $str =~ m/($pat)/;
DFS> return ($str eq $1);
DFS> }
DFS> printf "%d\n%d\n", matches("foo|foot", "foo"), matches("foo|foot", "foot");
Yes, that's it. Something like that had to be in the docs.
DFS> In my opinion, the important thing is for the behavior to be documented.
DFS> If it's not sufficiently clear, then we ought to make it more clear.
DFS> Documentation patches are welcome.
DFS> Now, one can argue that we should add a validate() method specifically
DFS> for input validation with the behavior you expected. My opinion
I'd say that the best method would be the "matches()" itself (see my
first remark).
Otherwise the question is closed.
Thanks a lot for your patience.
DFS> daniel
--
Best regards,
Sergey
---------------------------------------------------------------------
To unsubscribe, e-mail: oro-user-unsubscribe@jakarta.apache.org
For additional commands, e-mail: oro-user-help@jakarta.apache.org
Re[4]: Pattern Regular Expressions: Consecutive ORs not handled corr ectl y
Posted by Sergey Samokhodkin <se...@zolshar.ru>.
Hello Daniel,
Wednesday, May 4, 2005, 8:50:28 PM, you wrote:
DFS> In message <12...@zolshar.ru>, Sergey Samokhodkin writes:
>>Not convinced yet. I still think there is a bug.
>>Let's look at the javadoc:
DFS> ...
>>I cannot see where the perlre allows the "foo|foot" not to produce the
>>exact match against "foot", which takes place in the case in question.
DFS> I don't see how the javadoc can be any clearer about explaining the
DFS> behavior. Run this test yourself and see:
DFS> echo foot | perl -pi -e 's/foo|foot/bar/g'
.......
.......
>>It obviously says about the partial rather than exact match, so
>>it simply doesn't apply.
DFS> I don't understand what you mean.
Same for me.
DFS> Perl expressions either match
DFS> something or they don't matching something. They don't either
DFS> exactly match the thing or partially match the thing.
That's what I mean:
$str =~ /^foo$/ - check for exact match, analog to matches()
$str =~ /foo/ - check for partial match, analog to contains()
DFS> foo|foot will never match foot in Perl, plain and simple. It
DFS> will only ever match foo, as my substitution example showed.
DFS> Awk is a different matter, because the longest possible match
DFS> will always be found.
You are referring, in essence, to the difference between the DFA- and
NFA-based matchers. I don't see how it applies to our case.
What I don't understand is, why the 'regexp("foo").matches(str)' is
diffrent in behaviour from the 'regexp("^(?:foo)$").contains(str)'.
IMHO these are the same and should behave the same.
DFS> daniel
DFS> ---------------------------------------------------------------------
DFS> To unsubscribe, e-mail: oro-user-unsubscribe@jakarta.apache.org
DFS> For additional commands, e-mail: oro-user-help@jakarta.apache.org
--
Best regards,
Sergey mailto:serge@zolshar.ru
---------------------------------------------------------------------
To unsubscribe, e-mail: oro-user-unsubscribe@jakarta.apache.org
For additional commands, e-mail: oro-user-help@jakarta.apache.org
Re[2]: Pattern Regular Expressions: Consecutive ORs not handled corr ectl y
Posted by Sergey Samokhodkin <se...@zolshar.ru>.
Hello Daniel,
Tuesday, May 3, 2005, 10:08:05 PM, you wrote:
Just of pure academic interest, let me to object on the issue.
DFS> That's a different pattern than the one you originally posted. Since
DFS> I now can see from your test case that you are using matches(), I can
DFS> tell you the problem is exactly the foo|foot scenario I mentioned. It
DFS> is explained in the documentation for Perl5Matcher.matches. There is
DFS> no bug. You should use either
DFS> \d{3}(.)\d{2}|\d{3} (although I suspect you mean \d{3}\.\d{2}|\d{3})
DFS> or
DFS> ^(?:\d{3}|\d{3}(.)\d{2})$
DFS> or
DFS> \d{3}(?:(.)\d{2})?
Not convinced yet. I still think there is a bug.
Let's look at the javadoc:
DFS> possible match. From the perlre manpage:
DFS> * <blockquote>
DFS> * Alternatives are tried from left to right, so the first
DFS> * alternative found for which the entire expression matches,
DFS> * is the one that is chosen. This means that alternatives
DFS> * are not necessarily greedy. For example: when matching
DFS> * foo|foot against "barefoot", only the "foo" part will
DFS> * match, as that is the first alternative tried, and it
DFS> * successfully matches the target string.
DFS> * </blockquote>
I cannot see where the perlre allows the "foo|foot" not to produce the
exact match against "foot", which takes place in the case in question.
It obviously says about the partial rather than exact match, so
it simply doesn't apply.
I'm not sure if i'm not missing something here.
--
Best regards,
Sergey mailto:serge@zolshar.ru
---------------------------------------------------------------------
To unsubscribe, e-mail: oro-user-unsubscribe@jakarta.apache.org
For additional commands, e-mail: oro-user-help@jakarta.apache.org