regexp and strings you don't want

regexp and strings you don't want

[Chaz]

Hi,

I know that ^ at the start of [ ] excludes individual characters (or
ranges of characters) from a regular expression search, but is there
an equivalent to eliminate strings?  That is, how can I search for a
regular expression that does not include a specified string?

For example, how can I search for a paragraph beginning with "The"
that does NOT include the word "top"?

Thanks

Chaz

Re: regexp and strings you don't want

[Barry Margolin]

In article <6c185cf3.0308251145.6af55ffc@posting.google.com>,
Chaz <chaz2@thedoghousemail.com> wrote:
>I know that ^ at the start of [ ] excludes individual characters (or
>ranges of characters) from a regular expression search, but is there
>an equivalent to eliminate strings?  That is, how can I search for a
>regular expression that does not include a specified string?
>
>For example, how can I search for a paragraph beginning with "The"
>that does NOT include the word "top"?

This is something that regexps by themselves are pretty bad at.  What you
should do is collect all the paragraphs that begin with "The", and then
search each of them for "top", and discard those from the list.

-- 
Barry Margolin, barry.margolin@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

Re: regexp and strings you don't want

[Chaz]

Barry Margolin <barry.margolin@level3.com> wrote in message news:<A9u2b.399$mD.8@news.level3.com>...

> >For example, how can I search for a paragraph beginning with "The"
> >that does NOT include the word "top"?
> 
> This is something that regexps by themselves are pretty bad at.  

That's too bad.  I wouldn't have thought it so complicated to have
some function like [^"string"], or to list strings as options, maybe
["dog""cat""turtle"].  These would be quite handy.

Re: regexp and strings you don't want

[Kevin Rodgers]

Chaz wrote:

> Barry Margolin <barry.margolin@level3.com> wrote in message news:<A9u2b.399$mD.8@news.level3.com>...
>>>For example, how can I search for a paragraph beginning with "The"
>>>that does NOT include the word "top"?
>>>
>>This is something that regexps by themselves are pretty bad at.  
>>
> 
> That's too bad.  I wouldn't have thought it so complicated to have
> some function like [^"string"], or to list strings as options, maybe
> ["dog""cat""turtle"].  These would be quite handy.


I don't think you understand the theory behind regular expressions, which are
based on regular languages and the finite state automata that recognize them.

But as Barry said, it's easy to write a function that does what you want.


-- 
Kevin Rodgers

Re: regexp and strings you don't want

[Stefan Monnier]

> That's too bad.  I wouldn't have thought it so complicated to have
> some function like [^"string"],

What would it match, exactly ?  There are many different possibilities with
very different behavior: match a string different from "string"; match a
string which does not include "string" as a submatch; match the empty string
if it is not followed by a string that matches "string"; ...

> or to list strings as options, maybe
> ["dog""cat""turtle"].  These would be quite handy.

I don't understand what you want here.  How is that different from
"dog\\|cat\\|turtle" ?


        Stefan

Re: regexp and strings you don't want

[Eric Pement]

chaz2@thedoghousemail.com (Chaz) wrote in message news:<6c185cf3.0308251145.6af55ffc@posting.google.com>...
> I know that ^ at the start of [ ] excludes individual characters (or
> ranges of characters) from a regular expression search, but is there
> an equivalent to eliminate strings?  That is, how can I search for a
> regular expression that does not include a specified string?
> 
> For example, how can I search for a paragraph beginning with "The"
> that does NOT include the word "top"?

A big problem is that paragraphs are multi-line objects and they
aren't amenable to simple grep operations or "M-x occur", which I'm
using much more frequently now.

But to answer your question more directly, here's how to locate the
matching paragraphs (separated by blank lines) in sed:

   sed '/./{H;$!d;};x;/^\nThe/!d;/\<top\>/d' file

And in Emacs, mark the region and then do

   M-| sed '/./{H;$!d;};x;/^\nThe/!d;/\<top\>/d' <RET>

   M-| runs shell-command-on-region, sending the results to a new
window. This will show you how many paragraphs match your
specification. It's not like "M-x occur", which will take you directly
to the matching lines there. However, this script will let you see how
many paragraphs match your specification, without leaving Emacs.

   I presume you have GNU sed; if not, omit the \< and \>  characters,
which are GNU options to match whole words. If you use WinNT Emacs,
wrap the sed script in "double quotes" instead of 'single quotes'. 
Hope this helps.

--
Eric Pement

Re: regexp and strings you don't want

[Kai Großjohann]

chaz2@thedoghousemail.com (Chaz) writes:

> For example, how can I search for a paragraph beginning with "The"
> that does NOT include the word "top"?

It is possible to build a regexp that does this (disregarding the
paragraph problem at the moment), but it is not pretty.

Some regexp implementations have the feature you're looking for to
make it convenient, but the Emacs implementation doesn't.

Let me rephrase this in terms of lines instead of paragraphs.

The idea is this: search for a line that begins with The and then
does not have top after it, as follows: after The, we allow any
characters that aren't t.  We also allow a t followed by something
that's not o, and also a to that's followed by something that's not
p.  And so on:

"^The\\([^t]*\\($\\|t$\\|t[^o]\\|to$\\|to[^p]\\)\\)*$"

The above regexp is in Lisp syntax, with doubled backslashes.  Note
that I treat the newline that might follow a t, or to, specially.

Do you see the idea?  I hope I haven't made a mistake, but if you
understand the idea, you'll see what to do.
-- 
Two cafe au lait please, but without milk.

Re: regexp and strings you don't want

[Oliver Scholz]

kai.grossjohann@gmx.net (Kai Großjohann) writes:

> chaz2@thedoghousemail.com (Chaz) writes:
>
>> For example, how can I search for a paragraph beginning with "The"
>> that does NOT include the word "top"?
>
> It is possible to build a regexp that does this (disregarding the
> paragraph problem at the moment), but it is not pretty.
>
> Some regexp implementations have the feature you're looking for to
> make it convenient, but the Emacs implementation doesn't.
>
> Let me rephrase this in terms of lines instead of paragraphs.
>
> The idea is this: search for a line that begins with The and then
> does not have top after it, as follows: after The, we allow any
> characters that aren't t.  We also allow a t followed by something
> that's not o, and also a to that's followed by something that's not
> p.  And so on:
>
> "^The\\([^t]*\\($\\|t$\\|t[^o]\\|to$\\|to[^p]\\)\\)*$"

Hmm. This is not really human readable. Would it be hard and/or bad
to extend `rx' so that it allows for (not STRING)? A là:

(looking-at (rx (and line-start
		     "The "
		     (not "top"))))

Whereas `(not "top")' would compile to a normal regexp in the way you
described it. WDYT?

    Oliver
-- 
12 Fructidor an 211 de la Révolution
Liberté, Egalité, Fraternité!

Re: regexp and strings you don't want

[Oliver Scholz]

[Yet another follow-up to myself ...]
[Superseded because of a flaky patch]

Oliver Scholz <alkibiades@gmx.de> writes:

> kai.grossjohann@gmx.net (Kai Großjohann) writes:
>
>> chaz2@thedoghousemail.com (Chaz) writes:
>>
>>> For example, how can I search for a paragraph beginning with "The"
>>> that does NOT include the word "top"?
>>
>> It is possible to build a regexp that does this (disregarding the
>> paragraph problem at the moment), but it is not pretty.
>>
>> Some regexp implementations have the feature you're looking for to
>> make it convenient, but the Emacs implementation doesn't.
>>
>> Let me rephrase this in terms of lines instead of paragraphs.
>>
>> The idea is this: search for a line that begins with The and then
>> does not have top after it, as follows: after The, we allow any
>> characters that aren't t.  We also allow a t followed by something
>> that's not o, and also a to that's followed by something that's not
>> p.  And so on:
>>
>> "^The\\([^t]*\\($\\|t$\\|t[^o]\\|to$\\|to[^p]\\)\\)*$"
>
> Hmm. This is not really human readable. Would it be hard and/or bad
> to extend `rx' so that it allows for (not STRING)? A là:
>
> (looking-at (rx (and line-start
> 		     "The "
> 		     (not "top"))))
>
> Whereas `(not "top")' would compile to a normal regexp in the way you
> described it. WDYT?
[...]

I've played a bit with this (patch below). But I thing I am a bit
puzzled. With my patch, `(rx (not top))' translates to:

"\\(?:[^t]*\\|t[^o]*\\|to[^p]*\\)"

Is this actually correct?

What does the concept of a regexp that matches a sequence of
characters that does _not_ contain a certain sequence of characters
actually mean?

Should it match any sequence of characters not identical to the
unwanted one (including the empty string) or should it match only
sequences of the same length? Or any non-empty sequence of characters
not identical with the unwanted one?

With my patch:

(string-match (rx (and line-start
		       "The "
		       (not "top")
 		       " lirum larum"))
	      "The top lirum larum")
 ==> nil

(string-match (rx (and line-start
		       "The "
		       (not "top")
 		       " lirum larum"))
	      "The to lirum larum")
 ==> 0

(string-match (rx (and line-start
		       "The "
		       (not "top")
 		       " lirum larum"))
	      "The lirum larum")

 ==> nil

Is this good or bad?

    Oliver (puzzled)


Index: lisp/emacs-lisp/rx.el
===================================================================
RCS file: /cvsroot/emacs/emacs/lisp/emacs-lisp/rx.el,v
retrieving revision 1.3
diff -u -r1.3 rx.el
--- lisp/emacs-lisp/rx.el	23 Dec 2002 17:43:24 -0000	1.3
+++ lisp/emacs-lisp/rx.el	29 Aug 2003 18:46:18 -0000
@@ -334,6 +334,7 @@
 		    '(digit control hex-digit blank graphic printing
 			    alphanumeric letter ascii nonascii lower
 			    punctuation space upper word))
+	      (stringp form)
 	      (and (consp form)
 		   (memq (car form) '(not any in syntax category:))))
     (error "Rx `not' syntax error: %s" form))
@@ -343,27 +344,41 @@
 (defun rx-not (form)
   "Parse and produce code from FORM.  FORM is `(not ...)'."
   (rx-check form)
-  (let ((result (rx-to-string (cadr form) 'no-group)))
-    (cond ((string-match "\\`\\[^" result)
-	   (if (= (length result) 4)
-	       (substring result 2 3)
-	     (concat "[" (substring result 2))))
-	  ((string-match "\\`\\[" result)
-	   (concat "[^" (substring result 1)))
-	  ((string-match "\\`\\\\s." result)
-	   (concat "\\S" (substring result 2)))
-	  ((string-match "\\`\\\\S." result)
-	   (concat "\\s" (substring result 2)))
-	  ((string-match "\\`\\\\c." result)
-	   (concat "\\C" (substring result 2)))
-	  ((string-match "\\`\\\\C." result)
-	   (concat "\\c" (substring result 2)))
-	  ((string-match "\\`\\\\B" result)
-	   (concat "\\b" (substring result 2)))
-	  ((string-match "\\`\\\\b" result)
-	   (concat "\\B" (substring result 2)))
-	  (t
-	   (concat "[^" result "]")))))
+  (if (stringp (cadr form))
+      (rx-reverse-string (cadr form))
+    (let ((result (rx-to-string (cadr form) 'no-group)))
+      (cond ((string-match "\\`\\[^" result)
+	     (if (= (length result) 4)
+		 (substring result 2 3)
+	       (concat "[" (substring result 2))))
+	    ((string-match "\\`\\[" result)
+	     (concat "[^" (substring result 1)))
+	    ((string-match "\\`\\\\s." result)
+	     (concat "\\S" (substring result 2)))
+	    ((string-match "\\`\\\\S." result)
+	     (concat "\\s" (substring result 2)))
+	    ((string-match "\\`\\\\c." result)
+	     (concat "\\C" (substring result 2)))
+	    ((string-match "\\`\\\\C." result)
+	     (concat "\\c" (substring result 2)))
+	    ((string-match "\\`\\\\B" result)
+	     (concat "\\b" (substring result 2)))
+	    ((string-match "\\`\\\\b" result)
+	     (concat "\\B" (substring result 2)))
+	    (t
+	     (concat "[^" result "]"))))))
+
+(defun rx-reverse-string (string)
+  (let ((list nil))
+    (dotimes (i (length string))
+      (push (rx-reverse-string-1 i string) list))
+    (concat "\\(?:"
+	    (mapconcat 'identity (nreverse list) "\\|")
+	    "\\)")))
+
+(defun rx-reverse-string-1 (n string)
+  (concat (substring string 0 n)
+	  "[^" (string (aref string n)) "]*"))
 
 
 (defun rx-repeat (form)

-- 
12 Fructidor an 211 de la Révolution
Liberté, Egalité, Fraternité!

Re: regexp and strings you don't want

[Kai Großjohann]

Oliver Scholz <alkibiades@gmx.de> writes:

> I've played a bit with this (patch below). But I thing I am a bit
> puzzled. With my patch, `(rx (not top))' translates to:
>
> "\\(?:[^t]*\\|t[^o]*\\|to[^p]*\\)"
>
> Is this actually correct?

Well, err, it depends.

I guess one meaningful meaning of the hypothetical x\\(!:top\\)y would
be to look whether the characters following x are t-o-p.  If so, then
fail.  If not, then do like xy would have done.

That's what Perl does, I believe.
-- 
Two cafe au lait please, but without milk.

Re: regexp and strings you don't want

[Oliver Scholz]

kai.grossjohann@gmx.net (Kai Großjohann) writes:

> Oliver Scholz <alkibiades@gmx.de> writes:
>
>> I've played a bit with this (patch below). But I thing I am a bit
>> puzzled. With my patch, `(rx (not top))' translates to:
>>
>> "\\(?:[^t]*\\|t[^o]*\\|to[^p]*\\)"
>>
>> Is this actually correct?
>
> Well, err, it depends.
>
> I guess one meaningful meaning of the hypothetical x\\(!:top\\)y would
> be to look whether the characters following x are t-o-p.  If so, then
> fail.  If not, then do like xy would have done.
[...]

Hmpf. I don't see a way to compile this to an ordinary Emacs regexp
programatically. Is it actually possible, even with you trick? But
maybe I am just a little bit slow this evening. Any thoughts?

    Oliver (time to go to bed now)
-- 
12 Fructidor an 211 de la Révolution
Liberté, Egalité, Fraternité!

Re: regexp and strings you don't want

[Ilya Zakharevich]

[A complimentary Cc of this posting was sent to
=?iso-8859-1?q?Kai_Gro=DFjohann?=
<kai.grossjohann@gmx.net>], who wrote in article <84isogutgt.fsf@slowfox.is.informatik.uni-duisburg.de>:
> I guess one meaningful meaning of the hypothetical x\\(!:top\\)y would
> be to look whether the characters following x are t-o-p.  If so, then
> fail.  If not, then do like xy would have done.
> 
> That's what Perl does, I believe.

Keep in mind that Perl has very primitive REx engine.  E.g., "onion
rings" (google for me and this) are not supported.

The semantic of "onion rings" is that

  A & B & C &! D & E

will match if A can match, and the *substring* which A matched matches
B, C, E, and does not match D.  The syntax is not defined (until it is
supported).

[But even with primitive state one can do negation without a problem:
(?!.*B) will match anything which does not contain B (if you put this
expression up front).]