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

Groups > comp.programming > #12608

Re: Extended pattern syntax extension

Cross-posted to 2 groups.

Show all headers | View raw

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

Back to comp.programming | Previous | Next — Previous in thread | 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