Path: csiph.com!2.eu.feeder.erje.net!feeder.erje.net!feeder5.feed.usenet.farm!feeder1.feed.usenet.farm!feed.usenet.farm!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!news-out.netnews.com!news.alt.net!fdc3.netnews.com!peer01.ams1!peer.ams1.xlned.com!news.xlned.com!peer03.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx46.ams4.POSTED!not-for-mail From: Spiros Bousbouras Newsgroups: comp.unix.shell,comp.programming Subject: Re: Extended pattern syntax extension Message-ID: References: <3Y9TmbsO0BhnLZt12@bongo-ra.co> In-Reply-To: X-Organisation: Weyland-Yutani Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit Lines: 41 X-Complaints-To: http://netreport.virginmedia.com NNTP-Posting-Date: Thu, 13 May 2021 18:34:37 UTC Organization: virginmedia.com Date: Thu, 13 May 2021 18:34:37 GMT X-Received-Bytes: 2683 Xref: csiph.com comp.unix.shell:21476 comp.programming:12608 On Thu, 13 May 2021 16:59:05 +0200 Janis Papanagnou 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 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