News for hackers. Stuff that matters.
Re:The New ‘Absent Operator’ in Ruby’s Regular Expressions by pcmonk on Thursday March 23, 2017 @09:29AM (#13939508)
Fascinating. As I recall, things like negative look-ahead (or look-behind) aren't formally regular expressions (i.e. the languages they recognize aren't generally regular languages). Is this "absent" operator like that too?
Re:The New ‘Absent Operator’ in Ruby’s Regular Expressions by rntz on Thursday March 23, 2017 @10:35AM (#13940075)
The negation (complement) of a regular language is always regular. So in the CS theory sense, these are still regular expressions. However, while regular languages correspond to finite automata, the transformation which negates a NFA is not very easy to describe, which is one reason regular expression matching libraries have rarely included negation proper as an operation. Implementing negation proper using backtracking is somewhat easier, but quite expensive if done naively.
Re:The New ‘Absent Operator’ in Ruby’s Regular Expressions by perlgeek on Thursday March 23, 2017 @10:04AM (#13939801)
A look-ahead isn't part of regular expression (in the CS sense) syntax, but since regular expressions are closed under AND, OR and NOT, you can emulate it with AND.

For example (?=a)b is the same as (a.*)&b if we take & to mean AND.

(But note that look-aheads don't influence the scope of captures in modern regex implementations, and regular expressions don't even have the notion of captures; this makes the emulation not practical).

Since I believe you can emulate the absence operator using look-aheads (see https://news.ycombinator.com/item?id=13939764), it should be expressible by regular language too.

Re:The New ‘Absent Operator’ in Ruby’s Regular Expressions by rntz on Thursday March 23, 2017 @10:40AM (#13940103)
It isn't quite that easy to emulate lookahead using intersection (AND). For (?=a)b you're right, but that's because `a` and `b` both only ever match strings of length one. `(?=foo)f`, for example, will match the first character of the string "foobar". But `foo&f` is the empty language: no string is both "foo" and "f"; they have different lengths!

The trouble with lookahead and lookbehind is that they aren't even describable in terms of the "language" which the regular expression corresponds to; rather, they modify how the pattern matches in the context of an overall string. So they don't quite use the same formalism as intersection, union, and negation of regular languages.

Re:The New ‘Absent Operator’ in Ruby’s Regular Expressions by bonzini on Thursday March 23, 2017 @06:07PM (#13944794)
Apart from the length of the match, (?=foo)f is equivalent to foo.* & f.* (the extra .* ensures that both of them match foo).
Re:The New ‘Absent Operator’ in Ruby’s Regular Expressions by k_takata on Monday March 27, 2017 @10:14AM (#13967833)
Hi, I'm the author of Onigmo regex library.

I'm not sure that negative look-ahead/behind are formally regular expressions. (There is a (Japanese) paper which says that they are formally regular expressions, but I don't understand it.)

However, the absent operator is formally regular expression.

I translated the main points of Tanaka Akira's paper very roughly. https://github.com/k-takata/Onigmo/issues/87 I hope this helps you to understand the operator.

Re:The New ‘Absent Operator’ in Ruby’s Regular Expressions by praptak on Thursday March 23, 2017 @10:05AM (#13939805)
Negative lookahead/behind is regular in the mathematical sense. Anything that can be achieved by a finite combination of FSMs is, including OR, AND and NOT on their accepting states.

What isn't regular is stipulation that a group matches the same string as another group. E.g. "Same word twice" is not expressible by formal regular languages.

Re:The New ‘Absent Operator’ in Ruby’s Regular Expressions by petercooper on Thursday March 23, 2017 @09:52AM (#13939690)
This initial paper on the concept seems to dig into that: https://staff.aist.go.jp/tanaka-akira/pub/prosym49-akr-paper... .. but it's in Japanese and a bit above my pay grade.