8 ms·

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 genera

by pcmonk 10y ago

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?

rntz 10y ago
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.
petercooper 10y ago
This initial paper on the concept seems to dig into that: https://staff.aist.go.jp/tanaka-akira/pub/prosym49-akr-paper.pdf https://staff.aist.go.jp/tanaka-akira/pub/prosym49-akr-paper... .. but it's in Japanese and a bit above my pay grade.
perlgeek 10y ago
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 https://news.ycombinator.com/item?id=13939764), it should be expressible by regular language too.
- rntz 10y ago
  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.
  - bonzini 10y ago
    Apart from the length of the match, (?=foo)f is equivalent to foo.* & f.* (the extra .* ensures that both of them match foo).
praptak 10y ago
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.
k_takata 10y ago
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 https://github.com/k-takata/Onigmo/issues/87 I hope this helps you to understand the operator.

by pcmonk 10y ago

rntz 10y ago

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.

petercooper 10y ago

This initial paper on the concept seems to dig into that: https://staff.aist.go.jp/tanaka-akira/pub/prosym49-akr-paper.pdf https://staff.aist.go.jp/tanaka-akira/pub/prosym49-akr-paper... .. but it's in Japanese and a bit above my pay grade.

perlgeek 10y ago

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 https://news.ycombinator.com/item?id=13939764), it should be expressible by regular language too.

rntz 10y ago
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.
- bonzini 10y ago
  Apart from the length of the match, (?=foo)f is equivalent to foo.* & f.* (the extra .* ensures that both of them match foo).

praptak 10y ago

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.

k_takata 10y ago

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 https://github.com/k-takata/Onigmo/issues/87 I hope this helps you to understand the operator.