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

Groups > comp.programming > #12606

Re: Extended pattern syntax extension

Cross-posted to 2 groups.

Show all headers | View raw

[ Crossposting to  comp.programming ]

On Thu, 13 May 2021 10:34:04 +0200
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).

Does  @(ab&bc)  match the string   abc ? In other words , are the
matches allowed to overlap ?

> 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)* ]]

For this the matches cannot overlap.

> [[ $1 == *A* && $1 == *B* && $1 == *C* ]]
> 
> ((c=0))
> case $1 in
> (*A*) ((c++)) ;&
> (*B*) ((c++)) ;&
> (*C*) ((c++)) ;&
> (*) ((c==3))
> esac

For both of these alternatives the matches can overlap.

> 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.

The closest I can think of is the  \&  operator in  vim  regular
expressions for which the  vim  documentation says :

                                                    */branch* */\&*
    2. A branch is one or more concats, separated by "\&".  It matches the last
       concat, but only if all the preceding concats also match at the same
       position.  Examples:
            "foobeep\&..." matches "foo" in "foobeep".
            ".*Peter\&.*Bob" matches in a line containing both "Peter" and "Bob"

I'm surprised it's not more common. Personally I often need such an idiom. On
the shell command line I usually do   grep A | grep B | grep ...  .Obviously
it can be done with AWK too.

> Thinking of an implementation, though, I'm not sure how to implement
> that efficiently based on an FSM. (OR-branches are simple, but ANDs?)

Create finite automata M1 , M2 , M3 corresponding to A , B , C .For each
symbol read , update each automaton. If any automaton reaches an accepting
state , stop updating it. If at some point all 3 automata have reached an
accepting state then the expression has matched ; if you reach the end of the
input and at least 1 automaton has not reached an accepting state , then the
expression has not matched.

-- 
I thought we were the better team. In the first half our keeper didn't
have a save to make apart from the two goals.
  Dean Saunders , football coach.

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

Thread

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

csiph-web