Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #12608
| 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 <spibou@gmail.com> |
| Newsgroups | comp.unix.shell, comp.programming |
| Subject | Re: Extended pattern syntax extension |
| Message-ID | <CXKS8ZtfDBvmQxRCZ@bongo-ra.co> (permalink) |
| References | <s7io9t$mr3$1@news-1.m-online.net> <3Y9TmbsO0BhnLZt12@bongo-ra.co> <s7jerp$t9t$1@news-1.m-online.net> |
| In-Reply-To | <s7jerp$t9t$1@news-1.m-online.net> |
| 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 |
Cross-posted to 2 groups.
Show key headers only | 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
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