k-takata
commented
7 years ago First, I'd like to translate the important points of his paper very very roughly.
- Introduction
Complement sets are useful to express C-style comments, CR LF terminated lines, Python's """...""" strings, HTTP header terminated by CR LF CR LF, SMTP body terminated by CR LF . CR LF, etc. These can be expressed with the complement set of (any string)(terminator)(any string). However, it it not easy to construct a regex which matches such set. This proposes the absent operator which is easy to write and fits well to regular language theory.
- Regular expressions
Regular expressions consist of:
e: empty string
c: character
rr: concatenation
r|r: alternation
r*: Kleene closure
- Implementation of regular expressions engine
A regular expressions engine can be implemented with DFA or backtracking. Script languages nowadays like Perl, Python and Ruby uses backtracking, because it is not easy to implement capturing with DFA. He implemented a basic backtracking engine using Ruby.
3.1. Abstract Syntax Tree of regular expressions
3.2. A basic regular expressions engine
A basic implementation by Ruby.
# re: AST of a regex
# str: An array of characters
# pos: Start position
# block: A block executed when it is matched
# (Callback)
def try(re, str, pos, &block)- Proposal for the absent operator
If a regex engine uses DFA, complement sets can be handled easily. However it is not easy for backtracking engine. (See 7.3 for detail.)
- The absent operator !r
(Note: Onigmo actually uses (?~r) instead of !r, because !r is not compatible with current syntax.) The language generated by !r can be defined as the following:
L(!r) = \Sigma * - L(.*r.*)L(!r) is a complement set of L(.*r.*).
- Implementation of the absent operator
This is also described in pp.26-27 of his slide: http://www.a-k-r.org/pub/prosym49-akr-presen.pdf See also the next comment.
- Advantage of the absent operator
7.1. Easy to write
C-style comments can be expressed with the following:
ab[^b]*b+(([^ba][^b]*)b+)*a("a" and "b" are used here instead of "/" and "*" to reduce the complexity of escaping.)
If the absent operator is used, it can be:
ab!(ba)ba7.2. Fit with regular language theory
7.2.1. Repetition of lazy match
ab.*?baThis doesn't work well when concatenated with other regex. E.g.
ab.*?ba\nThis wrongly matches "/*2*/3/*4*/\n".
However,
ab!(ba)ba\nthis correctly matches "/*4*/\n".
7.2.2. No backtracking
ab(?>.*?ba)This works well when concatenated with "\n":
ab(?>.*?ba)\nHowever this hardly depends on the strategy of backtracking, and it doesn't have theoretical backgrounds. E.g. it cannot be converted to a DFA.
7.2.3. Negative lookahead
ab((?!ba).)*baThis works well.
However, it is not possible to define a language L((?!r)) which is generated
by (?!r).
Note: I'm not sure that the negative lookahead is regular or not. There is a paper (in Japanese) which says that it is regular.
7.3. Inefficiency of complement sets
It is possible to implement a negation operator which matches the complement set of r. This is, however, inefficient to implement on a backtracking engine. The absent operator is much efficient than the negation operator.
- Related researches
8.1. Ragel
Ragel has the following operators:
- negation operator
!rThis is the same as the complement set operator discussed in 7.3. - difference operator
r1-r2This is the same as the complement set operator when r1 generates all the possible strings. - strong difference operator
r1--r2This is the same as the absent operator when r1 generates all the possible strings.
8.2. Perl
8.3. Grail
- Conclusions
hachi8833
jaynetics
After the release of Ruby 2.4.1, some blog posts about the absent operator were written, and they caused some discussions.
Blog posts:
Discussions:
Unfortunately, some people might not understand the advantage of the absent operator. Maybe one of the reason is that the original paper by Tanaka Akira is written in Japanese. Another reason would be that the document of the operator in Onigmo is not enough.