CS 333 Assignment 1: s/ed/grep/

Due Thursday, February 10, 11:59 PM.

By now you've heard (or would have, if you had been at the first lecture) the story of how Ken Thompson, best known as the father of Unix, created the original grep command in a single evening, starting with the Unix editor ed.

Your assignment is to do the same thing, although with three advantages and one disadvantage. The advantages are that you have a week, you know what grep is and does, and ed is now written in C, not PDP-11 assembler as it originally was. The disadvantage? You're not Ken Thompson.

The file ed.c contains the source for the 10th Edition Unix version of ed, which is 1700 lines long. It dates from about 1989, but is typical of Unix code from the mid 1970's: terse, tight, efficient, and largely uncommented. Your version of grep must use that code for regular expression processing. You will have to throw away a fair amount, since your grep.c will not need more than about 400 lines; you should not need to add more than about 30 lines of your own code.

• Your version of grep should read its input either from stdin or from one or more named files, just like the real one does:

  	grep regexpr [files...]
  

• Each matched line should be prefixed by the filename and a colon (:) only if there are two or more files in the argument list; otherwise, print only the matched lines.
• You need not provide any of the grep options, but you must return proper status values, as described in the manual page grep(1):
  0: One or more matches were found.
  1: No matches were found.
  2: Syntax errors or inaccessible files (even if matches were found).

• Ed.c contains (horrors!) goto statements. Although they are carefully used there, your code is not to contain any goto's.

• You must remove unneeded variables, functions, etc.; points will be deducted for dregs.

• You must use ANSI C, with proper function prototypes, header files, etc.; your code must be a single file grep.c that compiles with lcc -A on Unix (arizona or a CS machine). You can't use system or similar functions.

It is almost always best to attack such a task in stages, making sure each one works before the next one is started. Recompile frequently as you remove code to make sure that what remains is syntactically correct. Be sure to keep a backup of the last known correct state, or learn how to use undo in your text editor. Make sure it handles stdin before handling filename arguments. Make sure the code works with its goto's before worrying about removing them. Try to modularize sensibly; in particular, it would be good if your regular expression code were easily separable so that it could be used in some other program later.

This is typical of what you might encounter in a new job -- you're asked to make a small change in a big program, and most of the challenge is finding the right thing to change, while making sure that nothing else breaks. Thus, most of this assignment is an exercise in figuring out what parts of the code are irrelevant and discarding them. If something has nothing to do with regular expressions, it can almost surely go. If you're unfamiliar with ed, see ed(1) or Appendix 1 of The Unix Programming Environment, which contains a brief tutorial.

Hints

Submission

	~cs333/bin/submit 1 grep.c

PLEASE follow the rules on what to submit -- get the filenames right and submit exactly what's asked for. This is a big class, and it will be hard to manage if we can't automate most of the processing. Remember that a happy TA gives better marks than an unhappy one. Keep your TA happy.

Historical note

From ken Sun Jan 17 13:53:50 EST 1993
looks like a very good assignment.
it stresses reuse and cleanliness rather than grunt.