How to use a regex to match a pattern which does not have a specific string at the end

Question

How can I use a "POSIX BRE" or a "POSIX ERE" regex to match a string (line or word) that does not have bak at the end?

I want to do a ls | egrep '<regex>' to find all files which DO NOT have bak at the end of the filename.

For example, if there are three files file1, file2_bak, and bak_file3, the regex should match only file1 and bak_file3 (but not file2_bak).

I know that this can be done with ls | grep -v 'bak$', but I want to do this without using -v option for grep or egrep. I don’t want to use -v because this is just a theoretical/academic question on POSIX regexes.

This is how I match the filenames which DO HAVE bak at the end:

$ ls | egrep 'bak$'
file2_bak
$ 

The above regex, bak$, matches all strings that DO HAVE bak at the end. But how can I write a regex which matches all strings that do not have bak at the end?

Answer 1

If you use ksh (or bash with extended globbing activated, or zsh with ksh globs enabled) you can achieve the desired function using only file globbing patterns:

ls -d -- !(*bak)

With grep, to get a simple solution, just use the negation -v:

ls | grep -v 'bak$'

Answer 2

Regular languages (i.e. "this can be matched with a RE") are closed under complement, so it's possible, but it's not very useful for practical purposes: what you start out with is the condition

last letter is k AND letter before that is a AND letter before that is b

(let me write s[-1]=='k' and s[-2]=='a' and s[-3]=='b' in a pythonesque fashion) so a string that fails that has

not(s[-1]=='k' and s[-2]=='a' and s[-3]=='b')

i.e.

not(s[-1]=='k') or not (s[-2]=='a' and s[-3]=='b'))

i.e.

not(s[-1]=='k') or not(s[-2]=='a') or not(s[-3]=='b')

applying deMorgan's rule twice, and of course, this would in particular be the case if your string has length 2 or less, so you would roughly end up with

grep '^$\|^.$\|^..$\|..[^k]$\|.[^a].$\|[^b]..$'

which I'd consider typeable but unmaintainable.

(Theoretical sidenote: in general, you'd convert your regular expression into a deterministic finite automaton (DFA), invert the terminal states there, and then convert the new DFA back into a regular expression, which is all well-defined, but a somewhat tedious and error-prone process.)

Answer 3

Using find:

find . -maxdepth 1 -type f ! -name "*bak"

• .: asserts to search in the current working directory
• -maxdepth 1: asserts to search only one level below the specified directory (i.e. only the current working directory)
• -type f: asserts to search only for files
• ! -name "*bak": asserts to search only for filenames not ending in bak

However, if you want to grep ls's output:

ls | grep -v 'bak$'

• -v: prints only the lines not matching the given regex

Regex breakdown:

• bak: matches a bak string
• $: matches the end of the line

The same using negative look-behind (for PCREs-compatible grep versions):

ls | grep -P '(?<!bak)$'

• -P: matches lines using PCREs

Regex breakdown:

• (?<!bak): only matches the following pattern if not preceded by a bak string
• $: matches the end of the line

Answer 4

With POSIX BREs that have no alternation operator, you can use that \{0,1\} instead:

LC_ALL=C grep '^\.\{0,2\}\(.*[^k]\)\{0,1\}\(.*[^a].\)\{0,1\}\(.*[^b]..\)\{0,1\}$'

Answer 5

If you have perl extensions, you can use negative look ahead.

grep -P '^.{0,2}$|^.*(?!bak)...$'

For matching a line not ending with bak