COS 333: Assignment 2 (Spring 2018)

COS 333 Assignment 2 (Spring 2018): Feeping Creaturism

Due midnight, Friday, February 23

Tue Feb 13 07:40:23 EST 2018

One of the most common experiences for a programmer coming into a new job or working with some open-source code is to have to fix a bug or make a small change in a large unfamiliar program. This requires the ability to quickly find the relevant parts of the program and change them in a minimal way, while ignoring irrelevant parts and being sure not to break anything. In this assignment, you're going to work with the AWK programming language and with the current version of its original implementation.

In addition to working with existing code, the more general lessons include:

how a grammar for a language can be specified
how an interpreter can be implemented
how lexical analysis can be implemented
how patches are created and distributed
and again, testing, little languages, automation, shell programming

AWK is an elderly program by most standards; it was first implemented in 1977, about the time your parents were in elementary school. It shows all the signs of having been maintained over decades -- grimy code, unhelpful comments, violated abstractions, utterly mysterious constructs, and written in a language that's not exactly trendy. That said, after 40 years it's still a core Unix tool, and in terms of benefit divided by time to learn, it's hard to beat.

Warning: Most of the assignments in this course are best done on Linux or MacOSX, and that is especially true of this one. If you are a Windows user, it is strongly recommended that you use ssh, putty or MobaXterm to log into a CS cluster like cycles or an OIT cluster like nobel. The alternative is likely to be a great deal of beating your head against lots of walls, and it's just not worth it. (For general use, Cygwin is highly recommended; it makes Windows more convenient for programmers familiar with Unix.)

1. The assignment

This assignment is an exercise in adding some new features to an existing program that we have talked about in class, but whose innards are almost certainly unfamiliar. To get started, become familiar enough with AWK that you know in broad outline what it does; this awk help file might help. Then download the source from Github and skim the source code to see how it is implemented.

Your specific tasks are to

add a repeat-until statement that parallels the existing do-while statement but reverses the sense of the test. That is,
```
	repeat {
		statements
	} until (expression)
```
repeats the statements until the expression becomes true.
add a new built-in function htoi(s) that returns the result of converting the hexadecimal digits of the string s into a numeric value, analogous to the C function atoi. Your function should ignore leading whitespace, handle an optional + or - sign, ignore any 0x or 0X prefix, and stop scanning at the first character that can't be part of a hex number. This will happen for free if you use strtol; do not parse hex with your own code! (strtoul would be an alternative, but its results are somewhat surprising for negative hex strings. In this narrow context strtol is better.)
modify lexical analysis to permit // comments as in C++ and Java, in addition to the existing # comments.
create enough test cases to exercise your code thoroughly.

2. How to proceed

For this assignment, you can get a very long way merely by finding code that already does more or less what's needed and is already in the right place and right form; most of the job amounts to intelligent copy and paste, using grep to locate places that might be relevant.

For repeat-until, the AWK grammar needs a new rule that specifies the syntax of a repeat-until statement and creates the right kind of node in the parse tree. Lexical analysis has to recognize two new keywords and a new function has to be written and added to the program to provide the semantics. Figure out how do-while works, then copy, paste and edit.

For htoi, there are no grammar changes but there is a new function name to be recognized, and you have to add new semantics in the right place in run.c. Figure out how some analogous one-argument function works, then copy, paste and edit. Note that do-while is not the same as while.

For the new comment syntax, you have to fiddle the lexical analysis in lex.c. Figure out how # comments work, then copy, paste and edit.

For the last part, automate testing as much as possible. Create a bash shell file awk.test. There should be at least ten tests that ensure that your features are properly tested. The file awk.test should be self-contained, requiring no input from a user and generating its own test data somehow. It should produce no output if the tests work, and one line per failure, of the form

	Error: test N failed

if the N-th test fails. It should assume that the program being tested is named a.out and is in the current directory. For example, this file contains one minimal test of repeat-until and the // comment convention:

	#!/bin/bash
	# test 1: repeat-until counting down 3 2 1; no braces
	./a.out '
	BEGIN {
		n = 3	// a comment in the new syntax
		repeat
			print n
		until (--n <= 0)
	}' >temp1
	echo '3
	2
	1' >temp2
	cmp temp1 temp2 >/dev/null 2>&1 || echo 'Error: test 1 failed' 2>&1

Your awk.test should contain at least ten tests, with comments to explain what each test does. Don't forget to test for syntax errors. This is a good place to refresh your memory of the various I/O redirection mechanisms of the shell.

3. Advice

Talking over the precise meaning of the assignment with friends is encouraged. You must write your code yourself, however, so once you start coding, you may no longer discuss specific programming details with other students.

It is almost always best to attack such a task in stages, making sure each one works before the next one is started. First compile what you downloaded, before you make any changes. In spite of our best efforts, you might have to fiddle the makefile to get the right arguments for Yacc. The line

	YACC = yacc -d

works for me on CS and OIT computers; on my own Mac I had to use

	YACC = bison -d -y

Your mileage may vary; try one of the other options and report any serious problems.

Once you can compile without problems, make a tiny change, recompile, and test:

	repeat {tiny change; recompile; test} until (you're done)

I think it's easiest to do the new comment syntax first, since that requires only a simple change in one file. Then do htoi, which requires about 5 new lines in 3 files. Finally do repeat-until, which adds about 25-30 lines (most copied and pasted directly from existing ones) in 5 files. If you're doing a lot more than this, you are almost certainly off on the wrong track. If you get stuck, here are some hints that might help. No penalty for using them, no reward for not using them. You will probably find it most instructive to try hard before looking at the hints.

Prepare some good test cases ahead of time. Test early, test often, know what you are testing. Automate the testing as much as you can.

We will assess the quality of your test cases, so your tests should be good ones. We will also make sure you didn't break something else, so be careful of that. Don't make unnecessary or irrelevant changes in any file. In particular, do not replace newlines by carriage returns (Mac) or CRLF (Windows), and do not reformat the code. Whether you like it or not, use the existing formatting style. And try to make your tests correct; it would be nice if we could run your tests over everyone else's implementations.

It may help to learn gdb, though I think that in most cases you will do much better by thinking hard and using printf. If you prefer gdb, this short gdb help file might help you get started or remind you of basic commands.

No core dumps or seg faults, please.

4. Submission

Updates to significant pieces of software are often distributed as "patch" files, that is, the set of changes necessary to convert the old version into the new version. For Unix and Linux source, a patch file is usually made by running diff to create a file of editing commands on the system where the changes were made, and running patch with that file as input on the system where the changes are to be applied.

For this assignment, you have to submit a patch file awk.patch that contains your changes. The easiest way to do this is to place the original program in one directory, say old, and the new version in new. Clean out all the junk like Yacc-generated files (ytab*), proctab.c, and binary files like a.out and *.o. (The make clean rule in the makefile doesn't get rid of all of ytab*.) Then in the parent of these directories, say

	diff -ur old new >awk.patch

The recipient will say, on his/her system,

	cd old
	patch --verbose --backup <../awk.patch

to update the old version with your changes, in place.

Try the patch process yourself to be sure it works right before you submit. Back up your work before you start experimenting!! My patch file is around 170 lines long; if yours is a lot bigger, you are probably including something like a Yacc output file or you have somehow changed newlines or tabs in your source files. Fix those up and try again.

When you're all done, submit the two files awk.patch and awk.test, using the CS dropbox link dropbox.cs.princeton.edu/COS333_S2018/asgn2.

PLEASE follow the rules on what to submit. It will be a help if you get the filenames right and submit exactly what's asked for. Thanks.