Why this matters
grep is one of the oldest and most used Unix tools, and Ken Thompson's original version introduced regular expressions to most programmers. Writing a small one teaches more than it looks: a genuinely elegant recursive algorithm, command-line conventions (combined flags, file lists, the meaning of exit statuses), reading lines of any length, and handling errors per file without giving up on the rest. When you finish, you will have a tool you can actually use, and you will read the real grep manual with different eyes.
What we are building
$ ./mgrep -n night poem.txt notes.txt
poem.txt:2:In the forests of the night;
notes.txt:2:the night bus leaves at 11
$ ./mgrep -c the poem.txt notes.txt
poem.txt:1
notes.txt:1
$ ./mgrep night nope.txt poem.txt
mgrep: nope.txt: No such file or directory
poem.txt:In the forests of the night;
$ echo $?
2
The pattern language is a small but useful subset of regular expressions:
| pattern | matches |
|---|
c | the character c itself |
. | any single character |
c* | zero or more c's (.* is any sequence) |
^ | at the start of the pattern: the start of the line |
$ | at the end of the pattern: the end of the line |
Anywhere else, ^ and $ are ordinary characters: a$b matches the text a$b.
Step 1: the matcher
This matcher is adapted from one Rob Pike wrote for the book The Practice of Programming, and Brian Kernighan called it one of the most elegant pieces of code he knew. It is three short recursive functions.
match(re, text): anywhere in the text. A pattern can match starting at any position, so try each one in turn, including the empty string at the end (a pattern like a* or $ matches there). A leading ^ restricts the attempt to position 0.
int match(const char *re, const char *text)
{
if (re[0] == '^')
return match_here(re + 1, text);
do {
if (match_here(re, text))
return 1;
} while (*text++ != '\0');
return 0;
}
match_here(re, text): right here, at the start of the text. Look at the first element of the pattern and decide:
int match_here(const char *re, const char *text)
{
if (re[0] == '\0') /* 1. pattern used up: success */
return 1;
if (re[1] == '*') /* 2. x*: let match_star handle it */
return match_star(re[0], re + 2, text);
if (re[0] == '$' && re[1] == '\0') /* 3. final $: only at end of text */
return *text == '\0';
if (*text != '\0' && (re[0] == '.' || re[0] == *text))
return match_here(re + 1, text + 1); /* 4. one char matched: rest must too */
return 0;
}
Each recursive call consumes one pattern element and (usually) one text character, so the recursion ends. Notice the order: the * check comes before the single-character check because a* is one element, not "a" followed by something.
match_star(c, re, text): c* followed by the rest. Try the rest of the pattern after zero c's; if that fails, and the next text character is a c (or c is .), consume it and try again after one, two, three c's:
int match_star(int c, const char *re, const char *text)
{
do {
if (match_here(re, text)) /* rest matches after this many c's? */
return 1;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}
This is the shortest-first strategy: it tries zero repetitions first. For a yes/no answer that is fine. (Real grep reports the leftmost-longest match, which matters when highlighting.)
Trace ab*c against xabbc:
match: try at "xabbc" match_here("ab*c", "xabbc") 'a' != 'x' -> no
try at "abbc" match_here("ab*c", "abbc") 'a' == 'a', recurse
match_here("b*c", "bbc") b* -> match_star('b', "c", "bbc")
zero b's: match_here("c", "bbc") 'c' != 'b' -> no
one b: match_here("c", "bc") 'c' != 'b' -> no
two b's: match_here("c", "c") 'c' == 'c', then "" -> yes
Step 2: being a filter
A Unix filter reads standard input, writes standard output, and reports problems on standard error. grep's interface is a filter's: lines in, selected lines out.
Lines of any length. A char line[512] with fgets silently splits long lines in two, and each half would be matched separately. POSIX getline grows a heap buffer as needed:
char *line = NULL;
size_t cap = 0;
ssize_t len;
while ((len = getline(&line, &cap, stdin)) != -1) {
if (len > 0 && line[len - 1] == '\n')
line[len - 1] = '\0'; /* strip the newline */
/* ... */
}
free(line); /* one free, after the loop */
getline reallocates line when it needs more room and updates cap, so the same buffer is reused for every line and freed once. It needs #define _POSIX_C_SOURCE 200809L before the includes, because -std=c17 otherwise hides POSIX additions to <stdio.h>.
Option parsing. The convention is: options come first, each starts with -, several letters may share one dash (-nv), and the first argument that is not an option is the pattern. -- conventionally ends the options (so you can search for a pattern starting with a dash), and a lone - usually means stdin. The two nested loops in the solution, one over arguments and one over letters, are the hand-written version of what POSIX getopt does for you.
Selecting lines. One comparison handles -v neatly: match(re, line) == invert is true exactly for the lines to skip.
Exit status. grep defines three: 0 when at least one line was selected, 1 when none, 2 on trouble. Scripts rely on this: if grep -q root /etc/passwd; then ....
Step 3: files and errors
When files are named, each is opened, searched and closed in turn. The interesting decisions are about presentation and failure:
- Prefixes. With one file the output looks just like stdin's. With several, each line needs its file name, or the output is ambiguous. That is why the label is a parameter of
grep_stream, NULL meaning "no prefix". - Per-file errors. A missing file should not stop the search of the others. Report it in the standard format
program: name: reason, remember that an error happened, and exit 2 at the end. strerror(errno) produces the same text as perror, but lets you build the message yourself. - Case-insensitive matching. Rather than lowercasing copies of every line and the pattern, route every character comparison through one helper that consults the
-i flag. The cast to unsigned char before tolower matters for bytes above 127, as in the word counter.
Common mistakes
- Fixed-size line buffers, which split long lines and produce phantom matches or misses.
- Checking
. or single characters before * in match_here, so a* is treated as "a then *". - Forgetting the empty string at the end in
match: using while (*text != '\0') instead of do ... while (*text++ != '\0') makes $ and x* fail on empty lines. - Stopping at the first unreadable file, or reporting it on stdout where it pollutes the results.
- Returning 1 for errors, which scripts then read as "not found".
- Not resetting the line number for each file.
Recap
- A small regex matcher is three recursive functions: try every start position, match one element at a time, and handle
c* by trying zero, one, two... repetitions. getline reads lines of any length into a reusable heap buffer, freed once.- Options first, combined letters allowed, then operands; usage errors exit 2.
- Errors on individual files are reported in
prog: name: reason form, the search continues, and the exit status records the failure. - Exit statuses 0, 1 and 2 let scripts tell "yes", "no" and "could not tell" apart.
Going further: add + (one or more) and ? (zero or one) to the matcher, then character classes like [abc]. Add -r to search directories recursively with opendir/readdir. Compare your matcher's speed with real grep on a large file, and read Russ Cox's article "Regular Expression Matching Can Be Simple And Fast" to learn why backtracking matchers like this one can be exponentially slow on patterns such as a*a*a*a*a*b.
Exercise 1 · write code
Step 1: a tiny regular expression matcher
Implement the two helper functions of the regular expression matcher described in the lesson. match (provided) tries the pattern at each position of the text. You write:
match_here(re, text): does re match at the beginning of text?match_star(c, re, text): does c* followed by re match at the beginning of text?
Supported syntax: any ordinary character matches itself; . matches any single character; c* matches zero or more of the character c (or of any character, for .*); ^ at the start of the pattern anchors to the start of the line; $ at the end anchors to the end.
main reads lines of the form PATTERN TEXT (separated by one space; TEXT may be empty) and prints yes or no for each:
$ printf 'b.d abcde
^b.d abcde
a*$
' | ./prog
yes
no
yes
File: main.c
Starting point
#include <stdio.h>
#include <string.h>
int match_here(const char *re, const char *text);
/* Does c* followed by re match at the start of text? */
int match_star(int c, const char *re, const char *text)
{
return 0;
}
/* Does re match at the start of text? */
int match_here(const char *re, const char *text)
{
return 0;
}
/* Does re match anywhere in text? */
int match(const char *re, const char *text)
{
if (re[0] == '^')
return match_here(re + 1, text);
do {
if (match_here(re, text))
return 1;
} while (*text++ != '\0');
return 0;
}
int main(void)
{
char line[512];
while (fgets(line, sizeof line, stdin) != NULL) {
line[strcspn(line, "\n")] = '\0';
char *space = strchr(line, ' ');
if (space == NULL)
continue;
*space = '\0';
printf("%s\n", match(line, space + 1) ? "yes" : "no");
}
return 0;
}
Example
input
b.d abcde
^b.d abcde
a*$
expected output
yes
no
yes
Example
input
ab*c ac
ab*c abbbc
^x.*z$ xyz
^x.*z$ xyza
hello say hello
expected output
yes
yes
yes
no
yes
Hint 1
match_here has four cases, in this order: empty pattern (match), a character followed by '*' (hand over to match_star), '$' as the last pattern character (match only at end of text), and a single character or '.' that matches the current text character (recurse on the rest of both).
Hint 2
match_star: try to match the rest of the pattern here (zero repetitions); if that fails and the current text character is c (or c is '.'), consume it and try again.
Hint 3
The do/while form: do { if (match_here(re, text)) return 1; } while (*text != '\0' && (*text++ == c || c == '.'));
Reference solution
#include <stdio.h>
#include <string.h>
int match_here(const char *re, const char *text);
/* Does c* followed by re match at the start of text? */
int match_star(int c, const char *re, const char *text)
{
do {
if (match_here(re, text))
return 1;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}
/* Does re match at the start of text? */
int match_here(const char *re, const char *text)
{
if (re[0] == '\0')
return 1;
if (re[1] == '*')
return match_star(re[0], re + 2, text);
if (re[0] == '$' && re[1] == '\0')
return *text == '\0';
if (*text != '\0' && (re[0] == '.' || re[0] == *text))
return match_here(re + 1, text + 1);
return 0;
}
/* Does re match anywhere in text? */
int match(const char *re, const char *text)
{
if (re[0] == '^')
return match_here(re + 1, text);
do {
if (match_here(re, text))
return 1;
} while (*text++ != '\0');
return 0;
}
int main(void)
{
char line[512];
while (fgets(line, sizeof line, stdin) != NULL) {
line[strcspn(line, "\n")] = '\0';
char *space = strchr(line, ' ');
if (space == NULL)
continue;
*space = '\0';
printf("%s\n", match(line, space + 1) ? "yes" : "no");
}
return 0;
}
Exercise 2 · write code
Step 2: options and exit status
Turn the matcher into a filter. The program is run as
mgrep [-n] [-v] [-c] PATTERN
and reads lines from standard input (of any length: use getline), printing the lines that match.
-n: prefix each printed line with its line number and a colon (2:text).-v: select the lines that do not match.-c: print only the number of selected lines.- Options may be given separately or combined (
-nv), and come before PATTERN. - Exit status: 0 if any line was selected, 1 if none, 2 for a usage error. For a usage error (missing pattern or unknown option) print
usage: mgrep [-cnv] PATTERN to stderr.
The matcher from step 1 is provided.
$ printf 'one
two
three
' | ./prog -n t
2:two
3:three
File: main.c
Starting point
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int match_here(const char *re, const char *text);
static int match_star(int c, const char *re, const char *text)
{
do {
if (match_here(re, text))
return 1;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}
static int match_here(const char *re, const char *text)
{
if (re[0] == '\0')
return 1;
if (re[1] == '*')
return match_star(re[0], re + 2, text);
if (re[0] == '$' && re[1] == '\0')
return *text == '\0';
if (*text != '\0' && (re[0] == '.' || re[0] == *text))
return match_here(re + 1, text + 1);
return 0;
}
static int match(const char *re, const char *text)
{
if (re[0] == '^')
return match_here(re + 1, text);
do {
if (match_here(re, text))
return 1;
} while (*text++ != '\0');
return 0;
}
int main(int argc, char *argv[])
{
if (argc < 2) {
fprintf(stderr, "usage: mgrep [-cnv] PATTERN\n");
return 2;
}
const char *re = argv[1];
char *line = NULL;
size_t cap = 0;
ssize_t len;
while ((len = getline(&line, &cap, stdin)) != -1) {
if (len > 0 && line[len - 1] == '\n')
line[len - 1] = '\0';
if (match(re, line))
printf("%s\n", line);
}
free(line);
return 0;
}
Example with arguments -n t
input
one
two
three
expected output
2:two
3:three
Example with arguments -v ^t
input
one
two
three
four
expected output
one
four
Hint 1
Loop over arguments while they start with '-' (and are longer than just "-"); for each, loop over its letters and set a flag per letter.
Hint 2
After the options exactly one argument, the pattern, must remain: check i == argc - 1.
Hint 3
match(re, line) == invert is true exactly for the lines to skip: matching lines when -v is on, non-matching ones when it is off.
Hint 4
Count selected lines; the exit status is selected > 0 ? 0 : 1.
Reference solution
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int match_here(const char *re, const char *text);
static int match_star(int c, const char *re, const char *text)
{
do {
if (match_here(re, text))
return 1;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}
static int match_here(const char *re, const char *text)
{
if (re[0] == '\0')
return 1;
if (re[1] == '*')
return match_star(re[0], re + 2, text);
if (re[0] == '$' && re[1] == '\0')
return *text == '\0';
if (*text != '\0' && (re[0] == '.' || re[0] == *text))
return match_here(re + 1, text + 1);
return 0;
}
static int match(const char *re, const char *text)
{
if (re[0] == '^')
return match_here(re + 1, text);
do {
if (match_here(re, text))
return 1;
} while (*text++ != '\0');
return 0;
}
static int usage(void)
{
fprintf(stderr, "usage: mgrep [-cnv] PATTERN\n");
return 2;
}
int main(int argc, char *argv[])
{
int show_numbers = 0, invert = 0, count_only = 0;
int i = 1;
for (; i < argc && argv[i][0] == '-' && argv[i][1] != '\0'; i++) {
for (const char *f = argv[i] + 1; *f != '\0'; f++) {
switch (*f) {
case 'n': show_numbers = 1; break;
case 'v': invert = 1; break;
case 'c': count_only = 1; break;
default: return usage();
}
}
}
if (i != argc - 1)
return usage();
const char *re = argv[i];
char *line = NULL;
size_t cap = 0;
ssize_t len;
long lineno = 0, selected = 0;
while ((len = getline(&line, &cap, stdin)) != -1) {
lineno++;
if (len > 0 && line[len - 1] == '\n')
line[len - 1] = '\0';
if (match(re, line) == invert)
continue;
selected++;
if (count_only)
continue;
if (show_numbers)
printf("%ld:", lineno);
printf("%s\n", line);
}
free(line);
if (count_only)
printf("%ld\n", selected);
return selected > 0 ? 0 : 1;
}
Exercise 3 · write code
Step 3: files and -i
Finish mgrep:
mgrep [-i] [-c] [-n] [-v] PATTERN [FILE...]
- Files. With no FILE, read stdin. Otherwise search each file in turn. When there is more than one file, prefix every output line with the file name and a colon, before the line number if any (
notes.txt:2:text); with -c, print one name:count line per file. Line numbers restart at 1 in each file. - Errors. If a file cannot be opened, print
mgrep: NAME: REASON to stderr (REASON from strerror(errno), e.g. No such file or directory), continue with the other files, and exit with status 2 at the end. Otherwise exit 0 if any line was selected, 1 if none. -i: ignore case. Make the matcher compare characters through a helper that uses tolower when the flag is on.- Usage errors print
usage: mgrep [-icnv] PATTERN [FILE...] to stderr and exit 2.
The workspace has poem.txt and notes.txt:
$ ./prog -n night poem.txt notes.txt
poem.txt:2:In the forests of the night;
notes.txt:2:the night bus leaves at 11
File: main.c
Starting point
#define _POSIX_C_SOURCE 200809L
#include <ctype.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int ignore_case, show_numbers, invert, count_only;
static int match_here(const char *re, const char *text);
static int match_star(int c, const char *re, const char *text)
{
do {
if (match_here(re, text))
return 1;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}
static int match_here(const char *re, const char *text)
{
if (re[0] == '\0')
return 1;
if (re[1] == '*')
return match_star(re[0], re + 2, text);
if (re[0] == '$' && re[1] == '\0')
return *text == '\0';
if (*text != '\0' && (re[0] == '.' || re[0] == *text))
return match_here(re + 1, text + 1);
return 0;
}
static int match(const char *re, const char *text)
{
if (re[0] == '^')
return match_here(re + 1, text);
do {
if (match_here(re, text))
return 1;
} while (*text++ != '\0');
return 0;
}
static int usage(void)
{
fprintf(stderr, "usage: mgrep [-icnv] PATTERN [FILE...]\n");
return 2;
}
/* Search one stream; label is the file name to print, or NULL.
Returns the number of selected lines. */
static long grep_stream(const char *re, FILE *in, const char *label)
{
char *line = NULL;
size_t cap = 0;
ssize_t len;
long lineno = 0, selected = 0;
(void)label;
while ((len = getline(&line, &cap, in)) != -1) {
lineno++;
if (len > 0 && line[len - 1] == '\n')
line[len - 1] = '\0';
if (match(re, line) == invert)
continue;
selected++;
if (count_only)
continue;
if (show_numbers)
printf("%ld:", lineno);
printf("%s\n", line);
}
free(line);
if (count_only)
printf("%ld\n", selected);
return selected;
}
int main(int argc, char *argv[])
{
int i = 1;
for (; i < argc && argv[i][0] == '-' && argv[i][1] != '\0'; i++) {
for (const char *f = argv[i] + 1; *f != '\0'; f++) {
switch (*f) {
case 'n': show_numbers = 1; break;
case 'v': invert = 1; break;
case 'c': count_only = 1; break;
default: return usage();
}
}
}
if (i >= argc)
return usage();
const char *re = argv[i++];
long total = grep_stream(re, stdin, NULL);
return total > 0 ? 0 : 1;
}
Example with arguments -n night poem.txt notes.txt
expected output
poem.txt:2:In the forests of the night;
notes.txt:2:the night bus leaves at 11
Example with arguments burn poem.txt
expected output
Tyger Tyger, burning bright,
Hint 1
Count the files left after the pattern: nfiles = argc - i. Only when nfiles > 1 do you pass the file name as the label.
Hint 2
fopen returns NULL on failure and sets errno; strerror(errno) turns it into text. Remember the error, continue the loop, and return 2 at the end.
Hint 3
For -i, write static int same(int a, int b) that compares tolower((unsigned char)a) with tolower((unsigned char)b) when ignore_case is set, and use it in match_here and match_star instead of ==.
Hint 4
Close each file after searching it.
Reference solution
#define _POSIX_C_SOURCE 200809L
#include <ctype.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int ignore_case, show_numbers, invert, count_only;
static int same(int a, int b)
{
if (ignore_case)
return tolower((unsigned char)a) == tolower((unsigned char)b);
return a == b;
}
static int match_here(const char *re, const char *text);
static int match_star(int c, const char *re, const char *text)
{
do {
if (match_here(re, text))
return 1;
} while (*text != '\0' && (same(*text++, c) || c == '.'));
return 0;
}
static int match_here(const char *re, const char *text)
{
if (re[0] == '\0')
return 1;
if (re[1] == '*')
return match_star(re[0], re + 2, text);
if (re[0] == '$' && re[1] == '\0')
return *text == '\0';
if (*text != '\0' && (re[0] == '.' || same(re[0], *text)))
return match_here(re + 1, text + 1);
return 0;
}
static int match(const char *re, const char *text)
{
if (re[0] == '^')
return match_here(re + 1, text);
do {
if (match_here(re, text))
return 1;
} while (*text++ != '\0');
return 0;
}
static int usage(void)
{
fprintf(stderr, "usage: mgrep [-icnv] PATTERN [FILE...]\n");
return 2;
}
/* Search one stream; label is the file name to print, or NULL.
Returns the number of selected lines. */
static long grep_stream(const char *re, FILE *in, const char *label)
{
char *line = NULL;
size_t cap = 0;
ssize_t len;
long lineno = 0, selected = 0;
while ((len = getline(&line, &cap, in)) != -1) {
lineno++;
if (len > 0 && line[len - 1] == '\n')
line[len - 1] = '\0';
if (match(re, line) == invert)
continue;
selected++;
if (count_only)
continue;
if (label != NULL)
printf("%s:", label);
if (show_numbers)
printf("%ld:", lineno);
printf("%s\n", line);
}
free(line);
if (count_only) {
if (label != NULL)
printf("%s:", label);
printf("%ld\n", selected);
}
return selected;
}
int main(int argc, char *argv[])
{
int i = 1;
for (; i < argc && argv[i][0] == '-' && argv[i][1] != '\0'; i++) {
for (const char *f = argv[i] + 1; *f != '\0'; f++) {
switch (*f) {
case 'i': ignore_case = 1; break;
case 'n': show_numbers = 1; break;
case 'v': invert = 1; break;
case 'c': count_only = 1; break;
default: return usage();
}
}
}
if (i >= argc)
return usage();
const char *re = argv[i++];
int nfiles = argc - i;
long total = 0;
int error = 0;
if (nfiles == 0)
total = grep_stream(re, stdin, NULL);
for (; i < argc; i++) {
FILE *f = fopen(argv[i], "r");
if (f == NULL) {
fprintf(stderr, "mgrep: %s: %s\n", argv[i], strerror(errno));
error = 1;
continue;
}
total += grep_stream(re, f, nfiles > 1 ? argv[i] : NULL);
fclose(f);
}
if (error)
return 2;
return total > 0 ? 0 : 1;
}