News for hackers. Stuff that matters.
Re:Regexes vs. Combinatorial Parsing (2019) by beeforpork on Thursday May 28, 2020 @01:56PM (#23340289)
> ... and can be compiled into finite state machines. ...

I am not a big fan of this argument without a 'but'. It is usually overlooked that the finite state machine can become exponentially large (=totally unusable), because sets of non-deterministic states are used for deterministic states. This caused me major trouble in a project where this effect was not noticed during the design phase.

I find this important to stress because the finite state machine can usually be constructed without problems (e.g. by the flex tool), so this property of regexps is undoubtedly useful.

But sometimes, it may explode on you.

Re:Regexes vs. Combinatorial Parsing (2019) by a1369209993 on Thursday May 28, 2020 @04:43PM (#23342302)
That's deterministic finite state machines (DFA); the nondeterministic (NFA) representation is linear in regex length (unless you use "a{99}", but that's nonstandard for a reason). You can also do concat/intersect/etc directly on the (actually-regular) regex representaion directly, although it is a bit ugly.