From: Grant Taylor via COFF <coff@tuhs.org>
To: coff@tuhs.org
Subject: [COFF] Re: Requesting thoughts on extended regular expressions in grep.
Date: Fri, 3 Mar 2023 12:26:41 -0700 [thread overview]
Message-ID: <9bb089cd-1317-6bcf-3bd3-231ce96b333c@spamtrap.tnetconsulting.net> (raw)
In-Reply-To: <CAEoi9W5JBfNC8rEmcv=_fMvKRKcD1CocqnQzFv_oXjcKZ8M8zQ@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 3045 bytes --]
On 3/3/23 6:47 AM, Dan Cross wrote:
> Oh, for sure; to be clear, it was obvious that in the earlier
> discussion the original was just part of something larger.
Good. For a moment I thought that you might be thinking it was stand alone.
> FWIW, this RE seems ok to me; the additional context makes it unlikely
> to match something else accidentally.
:-)
> It needn't be special. The point is simply that there's some external
> knowledge that can be brought to bear to guide the shape of the REs.
ACK
I've heard "domain (specific) knowledge" used to refer to both extremely
specific training in a field and -- as you have -- data that is having
something done to it.
> In this case, you know that log lines won't begin with `___ 123
> 456:789` or other similar junk.
They darned well had better not.
> Kinda. The "machine" in this case is actually an abstraction, like a
> Turing machine. The salient point here is that REs map to finite state
> machines, and in particular, one need not keep (say) a stack of prior
> states when simulating them. Note that even in an NDFA simulation,
> where one keeps track of what states one may be in, one doesn't need
> to keep track of how one got into those states.
ACK
> Obviously in a real implementation you've got the program counter,
> register contents, local variables, etc, all of which consume
> "memory" in the conventional sense. But the point is that you don't
> need additional memory proportional to anything other than the size
> of the RE. DFA implementation could be implemented entirely with
> `switch` and `goto` if one wanted, as opposed to a bunch of mutually
> recursive function calls, NDFA simulation similarly except that
> you need some (bounded) additional memory to hold the active set
> of states. Contrast this with a pushdown automata, which can parse
> a context-free language, in which a stack is maintained that can
> store additional information relative to the input (for example,
> an already seen character). Pushdown automata can, for example,
> recognize matched parenthesis while regular languages cannot.
I think I understand the gist of what you're saying, but I need to
re-read it and think about it a little bit.
> Anyway, sorry, this is all rather more theoretical than is perhaps
> interesting or useful.
Apology returned to sender as unnecessary.
You are providing the requested thought provoking discussion, which is
exactly what I asked for. I feel like I'm going to walk away from this
thread wiser based on the thread's content plus all additional reading
material on top of the thread itself.
> Bottom line is, I think your REs are probably fine. `egrep` will
> complain at you if they are not, and I wouldn't worry too much about
> optimizing them: I'd "stop" whenever you're happy that you've got
> something understandable that matches what you want it to match.
Thank you (again) Dan. :-)
--
Grant. . . .
unix || die
[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 4017 bytes --]
next prev parent reply other threads:[~2023-03-03 19:26 UTC|newest]
Thread overview: 46+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-03-02 18:54 [COFF] " Grant Taylor via COFF
2023-03-02 19:23 ` [COFF] " Clem Cole
2023-03-02 19:38 ` Grant Taylor via COFF
2023-03-02 23:01 ` Stuff Received
2023-03-02 23:46 ` Steffen Nurpmeso
2023-03-03 1:08 ` Grant Taylor via COFF
2023-03-03 2:10 ` Dave Horsfall
2023-03-03 3:34 ` Grant Taylor via COFF
2023-03-02 21:53 ` Dan Cross
2023-03-03 1:05 ` Grant Taylor via COFF
2023-03-03 3:04 ` Dan Cross
2023-03-03 3:53 ` Grant Taylor via COFF
2023-03-03 13:47 ` Dan Cross
2023-03-03 19:26 ` Grant Taylor via COFF [this message]
2023-03-03 10:59 ` Ralph Corderoy
2023-03-03 13:11 ` Dan Cross
2023-03-03 13:42 ` Ralph Corderoy
2023-03-03 19:19 ` Grant Taylor via COFF
2023-03-04 10:15 ` [COFF] Reading PDFs on a mobile. (Was: Requesting thoughts on extended regular expressions in grep.) Ralph Corderoy
2023-03-07 21:49 ` [COFF] " Tomasz Rola
2023-03-07 22:46 ` Tomasz Rola
2023-06-20 16:02 ` Michael Parson
2023-06-20 21:26 ` Tomasz Rola
2023-06-22 15:45 ` Michael Parson
2023-07-10 9:08 ` [COFF] Re: Reader, paper, tablet, phone (was: Re: Reading PDFs on a mobile. (Was: Requesting thoughts on extended regular expressions in grep.)) Tomasz Rola
2023-03-03 16:12 ` [COFF] Re: Requesting thoughts on extended regular expressions in grep Dave Horsfall
2023-03-03 17:13 ` Dan Cross
2023-03-03 17:38 ` Ralph Corderoy
2023-03-03 19:09 ` Dan Cross
2023-03-03 19:36 ` Grant Taylor via COFF
2023-03-04 10:26 ` Ralph Corderoy
2023-03-03 19:06 ` Grant Taylor via COFF
2023-03-03 19:31 ` Dan Cross
2023-03-04 10:07 ` Ralph Corderoy
2023-03-06 10:01 ` Ed Bradford
2023-03-06 21:01 ` Dan Cross
2023-03-06 21:49 ` Steffen Nurpmeso
2023-03-07 1:43 ` Larry McVoy
2023-03-07 4:01 ` Ed Bradford
2023-03-07 11:39 ` [COFF] " Ralph Corderoy
2023-03-07 18:31 ` [COFF] " Grant Taylor via COFF
2023-03-08 11:22 ` Ed Bradford
2023-03-07 16:14 ` Dan Cross
2023-03-07 17:34 ` [COFF] " Ralph Corderoy
2023-03-07 18:33 ` [COFF] " Dan Cross
2023-03-07 4:19 ` Ed Bradford
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=9bb089cd-1317-6bcf-3bd3-231ce96b333c@spamtrap.tnetconsulting.net \
--to=coff@tuhs.org \
--cc=gtaylor@tnetconsulting.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).