How does grep work?

Question

I am trying to understand how grep works.

When I say grep "hello" *.*, does grep get 2 arguments — (1) string to be searched i.e. "hello" and (2) path *.*? Or does the shell convert *.* into something that grep can understand?

Where can I get source code of grep? I came across this GNU grep link. One of the README files says its different from unix grep. How so?

I want to look at source of FreeBSD version of grep and also Linux version of it (if they are different).

Solution 1

The shell does the globbing (conversion from * form to filenames). You can see this by if you have a simple C program:

#include <stdio.h>

int main(int argc, char **argv) {
    for(int i=1; i<argc; i++) {
        printf("%s\n", argv[i]);
    }
    return 0;
}

And then run it like this:

./print_args *

You'll see it prints out what matched, not * literally. If you invoke it like this:

./print_args '*'

You'll see it gets a literal *.

Solution 2

The power of grep is the magic of automata theory. GREP is an abbreviation for Global Regular Expression Print. And it works by constructing an automaton (a very simple "virtual machine": not Turing Complete); it then "executes" the automaton against the input stream.

The automaton is a graph or network of nodes or states. The transition between states is determined by the input character under scrutiny. Special automatons like + and * work by having transitions that loop back to themselves. Character classes like [a-z] are represented by a fan: one start node with branches for each character out to the "spokes"; and usually the spokes have a special "epsilon transition" to a single final state so it can be linked up with the next automaton to be built from the regular expression (the search string). The epsilon transitions allow a change of state without moving forward in the string being searched.

Edit: It appears I didn't read the question very closely.

When you type a command-line, it is first pre-processed by the shell. The shell performs alias substitutions and filename globbing. After substituting aliases (they're like macros), the shell chops up the command-line into a list of arguments (space-delimited). This argument list is passed to the main() function of the executable command program as an integer count (often called argc) and a pointer to a NULL-terminated ((void *)0) array of nul-terminated ('\0') char arrays.

Individual commands make use of their arguments however they wish. But most Unix programs will print a friendly help message if given the -h argument (since it begins with a minus-sign, it's called an option). GNU software will also accept a "long-form" option --help.

Since there are a great many differences between different versions of Unix programs the most reliable way to discover the exact syntax that a program requires is to ask the program itself. If that doesn't tell you what you need (or it's too cryptic to understand), you should next check the local manpage (man grep). And for gnu software you can often get even more info from info grep.

Solution 3

The shell expands the '*.*' into a list of file names and passes the expanded list of file names to the program such as grep. The grep program itself does not do expansion of file names.

So, in answer to your question: grep does not get 2 arguments; the shell converts '*.*' into something grep can understand.

GNU grep is different from Unix grep in supporting extra options, such as -w and -B and -A.

It looks to me like FreeBSD uses the GNU version of grep:

• http://svnweb.freebsd.org/base/stable/8/gnu/usr.bin/grep/

Solution 4

How grep sees the wildcard argument depends on your shell. (Standard) Bourne shell has a switch (-f) to disable file name globbing (see man pages).

You may activate this switch in a script with

set -f

View more solutions

Comments

[Devin M]

As a reference here is the UNIX man page for grep: compute.cnr.berkeley.edu/cgi-bin/man-cgi?grep Here is the FreeBSD version: freebsd.org/cgi/man.cgi?query=grep and here is the Linux version: linux.die.net/man/1/grep

[luser droog]

A great place to browse old UNIX source code is tuhs.org

[luser droog]

@hari: If you're brave enough, take a look at the C compiler in version 3; it's truly frightening. Pointers are declared a[] rather than *a!

[Keith Thompson]

Yes, but that's rarely used. All (?) Unix/Linux shells do wildcard expansion by default. And if you disable globbing and type grep "hello" *.*, grep will see *.* and treat it as a file name (and probably fail unless you happen to have a file with that name).

[hari]

Thanks for the answer. In case of grep, what does it get as second argument? list of files? or one file at a time?

[icktoofay]

@hari: Think about grep as that simple C program. If you give grep a *, it will end up with a bunch of filenames as extra arguments. If you quote the * like '*', though, then the shell won't do globbing and grep will only get the single * argument (which will probably fail unless you have a file named exactly * in your current directory).

[hari]

Wow, so if that particular dir has 1000 files, * would give it 1000 arguments? (each as a single file)?

[icktoofay]

@hari: Yes; try it. If you have a bunch of files you need to operate on like that, you may be better off using find and xargs.

[GreyCat]

Technically, echo * is more that sufficient to demonstrate the globbing.

[Jens]

Just a nit-pick: GREP is not an abbreviation for General Regular Expression Parser. It's a contraction of the vi/ex-mode command :g/re/p which stands for global/regular expression/print.

[Jonathan Leffler]

@Jens: grep predates vi/ex by a bit; it was the ed command g/re/p that it simulates, which was translated into :g/re/p in vi mode (and is also g/re/p in ex). But the gist is correct.