Regexes: The Bad, the Better, and the Best • Hacker News Board

Re: Regexes: The Bad, the Better, and the Best

#31

Post by dpkendal » Wed, Jun 24, 2015, 1:54 AM UTC

thaumasiotes wrote: post #23

dpkendal wrote: post #21

Earlier quoted context omitted.

Not true. Finite automata (NFAs, DFAs) can match that pattern (and any pattern that doesn't involve backreferences or lookaround) in O(n) time where n is the size of the input string. DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression, but this is far better in most cases than the exponential worst-case time in terms of the input string offered by backtracking implementation…

> DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression What? Why is that? If the NFA has n states, then the DFA in principle might need one state for every possible set of states the NFA might be in, of which there are 2^n. Where does n^2 come from?

My mistake, I meant O(2 ^ n) indeed. Regardless, having exponential time complexity in terms of the regular expression (which is usually controlled by the programmer) where the processing is done at compile-time is much better than having exponential complexity in terms of the input string (which often comes from an untrusted source) where the processing is done at run-time.

Re: Regexes: The Bad, the Better, and the Best

#32

Post by hobs » Wed, Jun 24, 2015, 2:20 AM UTC

thaumasiotes wrote: post #22

edwintorok wrote: post #18

Earlier quoted context omitted.

that can be compiled to a state machine where a decision to switch states is taken based on current character only, and when all input is consumed you are either in an accepting or rejecting state. In your case I think it only needs 2 states: state 0 moves to state 1 when it sees an A, and state 1 moves to state 0 when it sees either A or B. For your string it'll be in state 0 when it sees a B and thus rejects it.

┌┐ ↓│ ┌────┴┐ ┌─→│ │←──┐ │ └─────┘ │ ╔════╧═╗ ┌──┴──┐ ├─→║ ╟───A──→│ │ ╚══════╝ └─┬───┘ ↑ │ └─────A,B────┘ Three states if you want to process the whole input. If your model is "reject when you fail to find an appropriate transition" rather than "reject if, after processing the string, you're in a reject state", then you don't need the failure trap and you can do it in two states. Backtracking is definitely not requi…

That diagram is quite pretty, did you just hand code it?

Re: Regexes: The Bad, the Better, and the Best

#33

Post by astangl » Wed, Jun 24, 2015, 2:40 AM UTC

thisrod wrote: post #29

carapace wrote: post #20

Okay but think: If you are searching a very large file for a very few occurrences of the expected match then this optimization is not so bad. If you are running line-by-line through a very large log file to extract just those two pieces of information per line, then throw away the first N characters in each line (where N is the hopefully-constant length of your timestamps plus that space char) and start the regex eng…

There's a higher order solution. Read the AWK book, do the exercises, then ignore blog posts about regexps. Make an exception when it's Russ Cox demonstrating how often this wheel has been reinvented in square form.

Which AWK book? The one by A, W, and K?

Re: Regexes: The Bad, the Better, and the Best

#34

Post by thaumasiotes » Wed, Jun 24, 2015, 5:05 AM UTC

hobs wrote: post #32

thaumasiotes wrote: post #22

Earlier quoted context omitted.

┌┐ ↓│ ┌────┴┐ ┌─→│ │←──┐ │ └─────┘ │ ╔════╧═╗ ┌──┴──┐ ├─→║ ╟───A──→│ │ ╚══════╝ └─┬───┘ ↑ │ └─────A,B────┘ Three states if you want to process the whole input. If your model is "reject when you fail to find an appropriate transition" rather than "reject if, after processing the string, you're in a reject state", then you don't need the failure trap and you can do it in two states. Backtracking is definitely not requi…

That diagram is quite pretty, did you just hand code it?

Yeah, all manual. :/

http://unicode-table.com/en/blocks/box-drawing/

http://unicode-table.com/en/sets/arrows-symbols/

Re: Regexes: The Bad, the Better, and the Best

#35

Post by Reefersleep » Wed, Jun 24, 2015, 8:58 AM UTC

Inspiring post - I'll be sure to put extra thought into how I write my regexes from here on out.

Does anyone know a good browser-based game that trains you to do regexes well?

Re: Regexes: The Bad, the Better, and the Best

#36

Post by dalore » Wed, Jun 24, 2015, 1:52 PM UTC

oftenwrong wrote: post #19

taco_emoji wrote: post #12

> In General, the Longer Regex Is the Better Regex I'd rather word this as "more specific is better". Like say for a U.S. phone number (minus area code for simplicity), \d{3}-?\d{4} is better than .*-?.* because it's more specific. "Longer is better" is only useful for helping identify which regex is better, not for helping write better regexes.

In many environments, [0-9]{3}-?[0-9]{4} is even more specific (and faster) because \d would match other digit characters outside of [0-9].

taking it to the next level:

[0-9][0-9][0-9]-?[0-9][0-9][0-9][0-9]

Re: Regexes: The Bad, the Better, and the Best

#37

Post by thisrod » Mon, Jun 29, 2015, 2:02 AM UTC

astangl wrote: post #33

thisrod wrote: post #29

Earlier quoted context omitted.

There's a higher order solution. Read the AWK book, do the exercises, then ignore blog posts about regexps. Make an exception when it's Russ Cox demonstrating how often this wheel has been reinvented in square form.

Which AWK book? The one by A, W, and K?

Yes.