Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #28550 > unrolled thread

regex tidy

Back to article view | Back to comp.lang.java.programmer

Contents

  regex tidy Roedy Green <see_website@mindprod.com.invalid> - 2014-05-23 11:39 -0700
    Re: regex tidy leif.roar@invalid.com (Leif Roar Moldskred) - 2014-05-23 14:33 -0500
      Re: regex tidy Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2014-05-23 15:05 -0500
    Re: regex tidy Robert Klemme <shortcutter@googlemail.com> - 2014-05-24 14:55 +0200
      Re: regex tidy Roedy Green <see_website@mindprod.com.invalid> - 2014-05-25 09:09 -0700
        Re: regex tidy Robert Klemme <shortcutter@googlemail.com> - 2014-05-25 18:49 +0200
          Re: regex tidy leif.roar@invalid.com (Leif Roar Moldskred) - 2014-05-25 12:28 -0500
            Re: regex tidy Robert Klemme <shortcutter@googlemail.com> - 2014-05-25 19:55 +0200
            Re: regex tidy "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2014-05-26 12:12 +0100
      Re: regex tidy Roedy Green <see_website@mindprod.com.invalid> - 2014-05-25 09:10 -0700
      Re: regex tidy Roedy Green <see_website@mindprod.com.invalid> - 2014-05-25 09:13 -0700
      Re: regex tidy Roedy Green <see_website@mindprod.com.invalid> - 2014-05-25 09:21 -0700
        Re: regex tidy Joshua Cranmer 🐧 <Pidgeot18@verizon.invalid> - 2014-05-25 13:31 -0500
          Re: regex tidy "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2014-05-26 12:31 +0100

#28550 — regex tidy

What would a Java regex tidier do?

Here are some ideas:

1. remove nugatory \ quoting

2. convert \s*\s* --> \s*

3. alphabetise | lists.

4. remove (?:... ) that is not doing anything.

5. put [..] lists in canonical order.  

6. Convert runs of 4+ to a-d notation.

7. use negative char lists when it would shorten the list.
-- 
Roedy Green Canadian Mind Products http://mindprod.com
Young man, in mathematics you don’t understand things.
You just get used to them. 
~ John von Neumann (born: 1903-12-28 died: 1957-02-08 at age: 53)

[toc] | [next] | [standalone]

#28551

Roedy Green <see_website@mindprod.com.invalid> wrote:
>
> What would a Java regex tidier do?
>

Evil. 

Regular expressions should be written to as closely as
possible mirror a mental or conceptual model of the 
inputs it will match, and not to be as short or compact
as possible.

For instance, to match dates on the pattern "YY-MM-dd"
your regular expression should be "\\d{2}-\\d{2}-\\d{2}"
and not "((^|-)\\d{2}){3}"

-- 
Leif Roar Moldskred

[toc] | [prev] | [next] | [standalone]

#28552

On 5/23/2014 2:33 PM, Leif Roar Moldskred wrote:
> Roedy Green <see_website@mindprod.com.invalid> wrote:
>>
>> What would a Java regex tidier do?
>>
>
> Evil.
>
> Regular expressions should be written to as closely as
> possible mirror a mental or conceptual model of the
> inputs it will match, and not to be as short or compact
> as possible.
>
> For instance, to match dates on the pattern "YY-MM-dd"
> your regular expression should be "\\d{2}-\\d{2}-\\d{2}"
> and not "((^|-)\\d{2}){3}"

Those two regexes aren't actually equivalent. The latter matches 
-00-00-00, for example. I assume you meant "\\d{2}(?:-\\d{2}){2}"?


-- 
Beware of bugs in the above code; I have only proved it correct, not 
tried it. -- Donald E. Knuth

[toc] | [prev] | [next] | [standalone]

#28553

On 23.05.2014 20:39, Roedy Green wrote:
> What would a Java regex tidier do?
>
> Here are some ideas:
>
> 1. remove nugatory \ quoting
>
> 2. convert \s*\s* --> \s*

More generally convert

R*R* into R*

But who writes regexes like this?

> 3. alphabetise | lists.

What does that mean?  Are you talking about merging common prefixes to 
get a more efficient matching experience?  That might actually be done 
by a regex engine if it detects this situation.

> 4. remove (?:... ) that is not doing anything.

Hmm...  It may still serve the purpose of documentation for the human.

> 5. put [..] lists in canonical order.

I don't believe this will improve anything.

> 6. Convert runs of 4+ to a-d notation.

Not sure what you mean here.

> 7. use negative char lists when it would shorten the list.

I don't believe this has any impact as this is something the regex 
engine will do internally.  Also, if the list is longer the way it is 
written then someone probably had a reason to do so.  Who would 
voluntarily write longer char classes than necessary?

Generally I tend to agree with what Leif wrote: it may actually be 
harder to read a regex that you did not author.  I am sceptical of the 
effort.  And then, you must consider that some changes may actually hurt 
performance if the regex was specifically crafted for a particular engine.

Kind regards

	robert

[toc] | [prev] | [next] | [standalone]

#28554

On Sat, 24 May 2014 14:55:03 +0200, Robert Klemme
<shortcutter@googlemail.com> wrote, quoted or indirectly quoted
someone who said :

>What does that mean?  Are you talking about merging common prefixes to 
>get a more efficient matching experience?  That might actually be done 
>by a regex engine if it detects this situation.


(cat|rabbit|dog|cow)
could be transformed to
(cat|cow|dog|rabbit)

for two reasons:
make the list easier to proofread
might help engine optimise handling the c in cat and cow in common.
-- 
Roedy Green Canadian Mind Products http://mindprod.com
Young man, in mathematics you don’t understand things.
You just get used to them. 
~ John von Neumann (born: 1903-12-28 died: 1957-02-08 at age: 53)

[toc] | [prev] | [next] | [standalone]

#28558

On 25.05.2014 18:09, Roedy Green wrote:
> On Sat, 24 May 2014 14:55:03 +0200, Robert Klemme
> <shortcutter@googlemail.com> wrote, quoted or indirectly quoted
> someone who said :

>>> 3. alphabetise | lists.
>> What does that mean?  Are you talking about merging common prefixes to
>> get a more efficient matching experience?  That might actually be done
>> by a regex engine if it detects this situation.
>
>
> (cat|rabbit|dog|cow)
> could be transformed to
> (cat|cow|dog|rabbit)
>
> for two reasons:
> make the list easier to proofread
> might help engine optimise handling the c in cat and cow in common.

The engine does not need the reordering to do this optimization.  If you 
want to help lesser engines which do not optimize here you would have to 
transform it into

(c(?:at|ow)|dog|rabbit)

to get more efficient matching.

Cheers

	robert

[toc] | [prev] | [next] | [standalone]

#28559

Robert Klemme <shortcutter@googlemail.com> wrote:
> 
> The engine does not need the reordering to do this optimization.  If you 
> want to help lesser engines which do not optimize here you would have to 
> transform it into
> 
> (c(?:at|ow)|dog|rabbit)
> 
> to get more efficient matching.
> 


Besides, when we're talking about performance on this scale, the order
in which the terms are evaluated by the regex engine might matter:
we'd want it to check against the more common case first to minimize
the time spent backtracking.

Now, regex engines don't _have_ to use the ordering of the term as a
suggestion for the order of evaluation, but as far as I'm aware,
that's how it's usually done.

So if "rabbit" is much more prevalent in your expected input than either 
"cat", "cow" or "dog", alphabetizing the terms would yield suboptimal
performance.

(That said, if you find that such low-level details about the regex'
efficency is important enough that it is significant for your program,
you should probably rethink your whole approach.)

-- 
Leif Roar Moldskred

[toc] | [prev] | [next] | [standalone]

#28560

On 25.05.2014 19:28, Leif Roar Moldskred wrote:
> Robert Klemme <shortcutter@googlemail.com> wrote:
>>
>> The engine does not need the reordering to do this optimization.  If you
>> want to help lesser engines which do not optimize here you would have to
>> transform it into
>>
>> (c(?:at|ow)|dog|rabbit)
>>
>> to get more efficient matching.
>
> Besides, when we're talking about performance on this scale, the order
> in which the terms are evaluated by the regex engine might matter:
> we'd want it to check against the more common case first to minimize
> the time spent backtracking.

Only problem is that this cannot be done by looking at the expression - 
the optimizer would need additional data about inputs.  That would make 
the reordering more complicated and the result would probably be no 
longer "tidy".

I came to think that Roedy's main concern was human readability and not 
performance of the expression.  However, changing a human crafted 
expression is probably not wise - for performance reasons (see below) 
but also for readability: it may actually be crucial for readability 
that the expression stays as written.

> Now, regex engines don't _have_ to use the ordering of the term as a
> suggestion for the order of evaluation, but as far as I'm aware,
> that's how it's usually done.

That does make sense: since NFSs are known to execute in order (as 
opposed to DFAs) it is wise to use the human given order because then we 
have a chance to do that optimization.

> So if "rabbit" is much more prevalent in your expected input than either
> "cat", "cow" or "dog", alphabetizing the terms would yield suboptimal
> performance.

Right, but see above.

> (That said, if you find that such low-level details about the regex'
> efficency is important enough that it is significant for your program,
> you should probably rethink your whole approach.)

Yes, for word search there are probably better approaches.  I personally 
haven't come across a case where this order would have mattered.  In 
many cases cost of IO will be dominant anyway.

Cheers

	robert

[toc] | [prev] | [next] | [standalone]

#28565

Leif Roar Moldskred wrote:

> Now, regex engines don't _have_ to use the ordering of the term as a
> suggestion for the order of evaluation, but as far as I'm aware,
> that's how it's usually done.

If the regexp engine is any good at all (some of them -- unforgivably -- are 
not) then it'll match in O(n) on the length of the input with no dependency at 
all[*] on the complexity of the pattern.  In the process it will convert the 
regexp into a (possibly lazy, possibly optimal) FSA and the "ordering" of the 
input patterns will no longer even be meaningful.

    -- chris

[*] to a first approximation, cache effects can presumably be significant 
sometimes. 

[toc] | [prev] | [next] | [standalone]

#28555

On Sat, 24 May 2014 14:55:03 +0200, Robert Klemme
<shortcutter@googlemail.com> wrote, quoted or indirectly quoted
someone who said :

>> 5. put [..] lists in canonical order.
>
>I don't believe this will improve anything.

If lists are in canonical order, they are easier to proofread,
especially if they are complicated.
-- 
Roedy Green Canadian Mind Products http://mindprod.com
Young man, in mathematics you don’t understand things.
You just get used to them. 
~ John von Neumann (born: 1903-12-28 died: 1957-02-08 at age: 53)

[toc] | [prev] | [next] | [standalone]

#28556

On Sat, 24 May 2014 14:55:03 +0200, Robert Klemme
<shortcutter@googlemail.com> wrote, quoted or indirectly quoted
someone who said :

>> 6. Convert runs of 4+ to a-d notation.
>
>Not sure what you mean here.

see http://mindprod.com/project/regextidier.html

I would convert 

[acdbde] to [a-e]
-- 
Roedy Green Canadian Mind Products http://mindprod.com
Young man, in mathematics you don’t understand things.
You just get used to them. 
~ John von Neumann (born: 1903-12-28 died: 1957-02-08 at age: 53)

[toc] | [prev] | [next] | [standalone]

#28557

On Sat, 24 May 2014 14:55:03 +0200, Robert Klemme
<shortcutter@googlemail.com> wrote, quoted or indirectly quoted
someone who said :

>> 7. use negative char lists when it would shorten the list.
>
>I don't believe this has any impact as this is something the regex 
>engine will do internally.  

I was thinking of a transform something like one that searched for
every character but " by specifying every ascii char but one. It could
be simplified to use a negative.  Perhaps the author had never heard
of negative searches.

It is pretty clear any tidier will need to be configurable.
-- 
Roedy Green Canadian Mind Products http://mindprod.com
Young man, in mathematics you don’t understand things.
You just get used to them. 
~ John von Neumann (born: 1903-12-28 died: 1957-02-08 at age: 53)

[toc] | [prev] | [next] | [standalone]

#28561

On 5/25/2014 11:21 AM, Roedy Green wrote:
> On Sat, 24 May 2014 14:55:03 +0200, Robert Klemme
> <shortcutter@googlemail.com> wrote, quoted or indirectly quoted
> someone who said :
>
>>> 7. use negative char lists when it would shorten the list.
>>
>> I don't believe this has any impact as this is something the regex
>> engine will do internally.
>
> I was thinking of a transform something like one that searched for
> every character but " by specifying every ascii char but one. It could
> be simplified to use a negative.  Perhaps the author had never heard
> of negative searches.

That wouldn't be correct. The original regex would not match, e.g., Õ, 
while your converted one would.

[Although this does raise the question of how regular expressions handle 
or fail to handle characters like 💩 or the penguin in my display name. 
Stupid UTF-16 and the "it's fixed-width characters if you look at it 
funny" results.]

-- 
Beware of bugs in the above code; I have only proved it correct, not 
tried it. -- Donald E. Knuth

[toc] | [prev] | [next] | [standalone]

#28566

Joshua Cranmer ?? wrote:

> [Although this does raise the question of how regular expressions handle
> or fail to handle characters like ?? or the penguin in my display name.
> Stupid UTF-16 and the "it's fixed-width characters if you look at it
> funny" results.]

I don't know how the Java regexp implementation works (very badly, last time I 
looked, but that was /years/ ago) but you can easily handle variable-width 
characters by building the regexp over the underlying "words".

E.g. I (in another language) match UTF-8 patterns by transforming them into a 
FSA over the underlying byte sequences.  That increases the number of 
transitions needed to find a match to  be linear in the number of bytes of 
input rather than the number of characters, but means that my jump tables only 
have to handle 256 possible values instead of several million.

The test would be, does the trivial range "^["\uD8eD\uDC27"]$" (= 
^[<penguin>]$) match the input string "\uD8eD\uDC27" ("<penguin>"), or does it 
match either of the two input strings, "\uD8eD" or "\uDC27"?  (My UTF-16 
encodings may be wrong here, but you get the idea).

    -- chris 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web