Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.unix.shell > #21473

Re: Extended pattern syntax extension

Show all headers | View raw

On 2021-05-13, Janis Papanagnou <janis_papanagnou@hotmail.com> wrote:
> Kornshell introduced patterns (called extended patterns in bash) that
> allowed, for example, pattern expressions like @(A|B|C), matching any
> of the sub-patterns A, B, or C.  I was under the impression that I've
> somewhere - maybe in some intermediate or experimental ksh version -
> seen an extension of those patterns allowing expressions like @(A&B&C)
> with the semantics of matching all sub-patterns (in arbitrary order).
>
> One can think of various work-arounds for that like the equivalents
>
> [[ $1 == *@(A*B*C|A*C*B|B*A*C|B*C*A|C*A*B|C*B*A)* ]]
>
> [[ $1 == *A* && $1 == *B* && $1 == *C* ]]
>
> ((c=0))
> case $1 in
> (*A*) ((c++)) ;&
> (*B*) ((c++)) ;&
> (*C*) ((c++)) ;&
> (*) ((c==3))
> esac
>
> none of them really satisfying (if compared to @(A&B&C) ).
>
> Has someone seen such an extension in a shell (or other programming
> language's regexp library)?  I'm quite sure I've seen it somewhere
> but don't recall where it was.
>
> Thinking of an implementation, though, I'm not sure how to implement
> that efficiently based on an FSM. (OR-branches are simple, but ANDs?)

Regex derivatives can be used; the & operator has a simple
interpretation under derivatives.  Regex derivatives were discovered by
Janusz Brzozowski, who published about them in 1964.

Derivatives can be interpreted directly, and that's how they were
originally described.

The basic idea behind this is that given a regular expression R,
we can calculate a "derivative" of R with respect to an input symbol s,
or R' = d(R, s). Maybe dR/ds, haha.

The derivative R' is a regular expression which matches the rest of the
input after s has been consumed.

Matching a string is performed by repeatedly calculating a chain of
derivatives, for each symbol in the string. If the end of the string is
reached, and the remaining regular expression is nullable (capable of
matching the empty string), then the string has been matched.  If at any
time a derivative is produced which doesn't match any strings, then the
match has failed.

Some more recent work describes ways of using derivatives to compile
to DFA.  The gist is to chase the possible derivatives at compile time
and calculate the resulting transition graph statically.
The trick, while doing that, is to recognize the identical states to
condense the graph and recognize loops. Sometimes the derivative of
a regex will yield the same regex, or a regex that was seen before.
Repetition does this, for instance. The derivative of a* with respect
to a is a*.  A notion of "sameness" is required, in consideration of
the issue that sometimes regexes have the same meaning, but look
different.

About the and operator: given R1&R2, the derivative has an easy
interpretation.  d(R1&R2, s) is just d(R1, s)&d(R2, s).  The derivative
operation parallelizes into the branches of the and, and the results are
combined with & again. If either derivative is the empty regex [],
then there is no match since R&[] = [].

-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

Back to comp.unix.shell | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Extended pattern syntax extension Janis Papanagnou <janis_papanagnou@hotmail.com> - 2021-05-13 10:34 +0200
  Re: Extended pattern syntax extension Spiros Bousbouras <spibou@gmail.com> - 2021-05-13 13:22 +0000
    Re: Extended pattern syntax extension Janis Papanagnou <janis_papanagnou@hotmail.com> - 2021-05-13 16:59 +0200
      Re: Extended pattern syntax extension Spiros Bousbouras <spibou@gmail.com> - 2021-05-13 18:34 +0000
        Re: Extended pattern syntax extension Janis Papanagnou <janis_papanagnou@hotmail.com> - 2021-05-15 11:54 +0200
  Re: Extended pattern syntax extension Kaz Kylheku <563-365-8930@kylheku.com> - 2021-05-13 16:04 +0000
    Re: Extended pattern syntax extension Janis Papanagnou <janis_papanagnou@hotmail.com> - 2021-05-13 20:18 +0200
  Re: Extended pattern syntax extension Janis Papanagnou <janis_papanagnou@hotmail.com> - 2021-07-04 00:56 +0200
    Re: Extended pattern syntax extension Spiros Bousbouras <spibou@gmail.com> - 2021-07-04 14:32 +0000
      Re: Extended pattern syntax extension Janis Papanagnou <janis_papanagnou@hotmail.com> - 2021-07-04 16:52 +0200
        Re: Extended pattern syntax extension Spiros Bousbouras <spibou@gmail.com> - 2021-07-04 15:07 +0000
          Re: Extended pattern syntax extension Janis Papanagnou <janis_papanagnou@hotmail.com> - 2021-07-04 17:36 +0200
            Re: Extended pattern syntax extension William Unruh <unruh@invalid.ca> - 2021-07-04 17:03 +0000
              Re: Extended pattern syntax extension "David W. Hodgins" <dwhodgins@nomail.afraid.org> - 2021-07-04 15:32 -0400
                Re: Extended pattern syntax extension "David W. Hodgins" <dwhodgins@nomail.afraid.org> - 2021-07-04 15:40 -0400
              Re: Extended pattern syntax extension joerg@schily.net - 2021-07-05 10:43 +0000
            Re: Extended pattern syntax extension Spiros Bousbouras <spibou@gmail.com> - 2021-07-04 17:36 +0000
          Re: Extended pattern syntax extension William Unruh <unruh@invalid.ca> - 2021-07-04 15:57 +0000
            Re: Extended pattern syntax extension Spiros Bousbouras <spibou@gmail.com> - 2021-07-04 17:17 +0000
              Re: Extended pattern syntax extension William Unruh <unruh@invalid.ca> - 2021-07-04 19:43 +0000
        Re: Extended pattern syntax extension William Unruh <unruh@invalid.ca> - 2021-07-04 15:33 +0000

csiph-web