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

Groups > comp.programming > #12606 > unrolled thread

Re: Extended pattern syntax extension

Back to article view | Back to comp.programming

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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

#12606 — Re: Extended pattern syntax extension

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

[toc] | [next] | [standalone]

#12607

On 13.05.2021 15:22, Spiros Bousbouras wrote:
> [ 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 ?

I would say so (but don't recall the implementation I thought to have
seen).

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

You are right.

> 
>> [[ $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 :
[...]
> 
> 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 ...  .

I needed it as well in a couple cases.

(It could as well have been the case that I haven't seen that feature
in some tool, but just thought it would be an useful and in Kornshell
a lexically coherent extension.)

> Obviously it can be done with AWK too.

Yes, and quite trivially (in Awk I'm using that pattern quite often)

/A/&&/B/&&/C/

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

Well, okay. I was more thinking (initially) about a method that will
stay within the Regular Expression (Chomsky 3) class. As I understand
it this method (like a counting automaton, etc.) would not qualify for
that. On the other hand, Kornshell's patterns are also already beyond
Chomsky 3 since they support backreferences in their patterns, so it's
okay, I guess, to think about non-regular implementations.

Would that be a candidate for ksh93u+m ?

Janis

[toc] | [prev] | [next] | [standalone]

#12608

On Thu, 13 May 2021 16:59:05 +0200
Janis Papanagnou <janis_papanagnou@hotmail.com> wrote:
> On 13.05.2021 15:22, Spiros Bousbouras wrote:
> > [ Crossposting to  comp.programming ]
> > 
> > On Thu, 13 May 2021 10:34:04 +0200
> > Janis Papanagnou <janis_papanagnou@hotmail.com> wrote:

[...]

> >> 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.
> 
> Well, okay. I was more thinking (initially) about a method that will
> stay within the Regular Expression (Chomsky 3) class. As I understand
> it this method (like a counting automaton, etc.) would not qualify for
> that.

It can be realised with a regular expression like the  \{n,m\}  operator can.

Anyway , I did some digging and I saw a better way to do conjunction (it's
the same idea really but all the details are presented) : you take the
product of 2 deterministic finite automata. Details are on pages 30-32 of
http://www.cse.chalmers.se/~coquand/AUTOMATA/o2.pdf .And right after , the
notes describe a modification of the product which works to get disjunction.

> On the other hand, Kornshell's patterns are also already beyond
> Chomsky 3 since they support backreferences in their patterns, so it's
> okay, I guess, to think about non-regular implementations.

-- 
I was once seriously berated for revealing the ending of
"The Passion of the Christ."
  Roger Ebert

[toc] | [prev] | [next] | [standalone]

#12609

On 13.05.2021 20:34, Spiros Bousbouras wrote:
> On Thu, 13 May 2021 16:59:05 +0200
> Janis Papanagnou <janis_papanagnou@hotmail.com> wrote:
>> On 13.05.2021 15:22, Spiros Bousbouras wrote:
>>> [ Crossposting to  comp.programming ]
>>>
>>> On Thu, 13 May 2021 10:34:04 +0200
>>> Janis Papanagnou <janis_papanagnou@hotmail.com> wrote:
> 
> [...]
> 
>>>> 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.
>>
>> Well, okay. I was more thinking (initially) about a method that will
>> stay within the Regular Expression (Chomsky 3) class. As I understand
>> it this method (like a counting automaton, etc.) would not qualify for
>> that.
> 
> It can be realised with a regular expression like the  \{n,m\}  operator can.

Hmm.. - I've considered the range terminology (and a few other syntaxes)
always like an abbreviation, still within FSA/Chomsky-3, if linearized.
(While for large values of 'm' this is practically not a sophisticated
implementation, of course; complexity would be depending on 'm', as the
expanded form of the FSM would be that huge.)

(With "counting automaton" I rather meant syntaxes like, for example,
bracket counting.)

> 
> Anyway , I did some digging and I saw a better way to do conjunction (it's
> the same idea really but all the details are presented) : you take the
> product of 2 deterministic finite automata. Details are on pages 30-32 of
> http://www.cse.chalmers.se/~coquand/AUTOMATA/o2.pdf .And right after , the
> notes describe a modification of the product which works to get disjunction.

I'll have a look into that. Thanks!

Janis

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web