char *progname;
main(arge, argv)
int arge;
char #argvt);
int fa;
struct stat stbuf:
time_t old time = 0;
prognane = argv[0};
if large « 2)
error("Usage: %s filenane (end]", prognane);
Af (£4 = open(argvf1}, 0)) == -1)
error("ean’t open Xs", argv 1]);
Estat(£4, &stbuf);
while (stbuf.st_mtime I= old_time) {
old_time « stbuf-st_mtine;
sieep(60
fetat(fd, &stbut);
}
if (arge == 2) { /* copy file +/
execip("cat", "cat", argvi tl, (char +) 0);
error("can’t execute cat e", argvl 11)
} else ( /+ run process +/
execyp(argv[2], Sargv[2));
error("can’t execute Xs", argv[2]);
>
exit(0);222 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER 7
This illustrates both exec1p and exeevp.
‘We picked this design because it's useful, but other variations are plausible,
For example, waitfile could simply return after the file has stopped chang-
ing.
Exercise 7-17. Modify vatchEile (Exercise 7-12) so it has the same property as
waiteile: if there is no command, it copies the file; otherwise it does the command,
Could watontite and waittite share source code? Hint: argvl0].
Control of processes — fork and wait
‘The next step is to regain control after running a program with execip or
execyp. Since these routines simply overlay the new program on the old one,
to save the old one requires that it first be split into two copies; one of these
can be overlaid, while the other waits for the new, overlaying program to fin-
ish. ‘The splitting is done by a system call named fork:
proc_id = fork(};
splits the program into two copies, both of which continue to run. The only
difference between the two is the value returned by fork, the process-id. In
one of these processes (the child), proc_id is zero. In the other (the parent),
proc_id is non-zero; it is the process-id of the child. Thus the basic way (0
call, and return from, another program is
Af (£ork()
execip(
+ se", commandline, (char +) 0
And in fact, except for handling errors, this is sufficient. The fork makes
‘two copies of the program. In the child, the value returned by fork is zero,
so it calls execlp, which does the commandline and then dies. In the
parent, fork returns non-zero so it skips the execlp. (If there is any error,
fork returns ~1.)
More often, the parent waits for the child to terminate before continuing
itself. This is done with the system call wait:
int status;
Af (fork() == 0)
execip(... 7a chile +/
wait(Gstatue); 7+ parent +/
‘This still docsn’t handle any abnormal conditions, such as a failure of the
execlp or fork, of the possibility that there might be more than one child
running simultaneously. (wait returns the process-id of the terminated child,
if you want to check it against the value returned by fork.) Finally, this frag-
ment doesn’t deal with any funny behavior on the part of the child. Still, these
three lines are the heart of the standard aystem function
The status returned by wait encodes in its low-order eight bits the
system's idea of the child’s exit status; it is 0 for normal termination and non‘CHAPTER 7 UNIX SYSTEM CALLS 223
zero to indicate various kinds of problems. The next higher eight bits are
taken from the argument of the call to exit or return from main that caused
termination of the child process.
‘When a program is called by the shell, the three file descriptors 0, 1, and 2
are set up pointing at the right files, and all other file descriptors are available
for use. When this program calls another one, correct etiquette suggests mak-
ing sure the same conditions hold. Neither fork nor exec calls affect open
files in any way; both parent and child have the same open files. If the parent
is buffering output that must come out before output from the child, the parent
must flush its buffers before the exee1p. Conversely, if the parent buffers an
input stream, the child will lose any information that has been read by the
parent. Output can be flushed, but input cannot be put back. Both of these
considerations arise if the input or output is being done with the standard 1/0
libeary discussed in Chapter 6, since it normally buffers both input and output
It is the inheritance of file descriptors across an execip that breaks
system: if the calling program does not have its standard input and output
connected to the terminal, neither will the command called by system. This
may be what is wanted; in an ed script, for example, the input for a command
started with an exclamation mark 1 should probably come from the script.
Even then ed must read its input one character at a time to avoid input buffer-
ing problems.
For interactive programs like p, however, system should reconnect stan-
dard input and output to the terminal. One way is to connect them to
saev/tey
The system call dup(4) duplicates the file descriptor #4 on the lowest-
numbered unallocated file descriptor, returning a new descriptor that refers to
the same open file. This code connects the standard input of a program to a
file:
int £45
£4 = open( file", 0);
close(o);
dup( ea;
close(fa);
The close(0) deallocates file descriptor 0, the standard input, but as usual
doesn’t affect the pareat
Here is our version of system for interactive programs; it uses progname
for error messages. You should ignore the parts of the function that deal with
signals; we will return to them in the next section224 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER 7
o
+ Safer version of system for interactive programs
#include
#include
system(s) /+ run command line = +/
char +
‘
int status, pid, w, tty:
int (#istat)(), (eqseat) 00;
extern char «prognane;
f£lush( stdout);
tty = open(*/dev/ety", 2);
Af (tty == 0) (
fprintf(stderr, "Xs: can’t open /dev/tty\n", prognane);
return ~1;
>
AE (pid = fork())
elose(0); dup(tty)
elose(1); dup(tty:
elose(2); dup(tty)
close(tty)
execip("sh", "sh", "-c", s, (char *) 0);
exit(127);
oe
,
close(tty);
istat = signal (SrGrwr, s1G_roN);
gstat = signal(SicourT, sr¢_rGN);
while ((w = wait(kstatus)) I= pid && w I= 1)
se
status = -15
signal (SIGINT, istat);
signal(siGavrt, qetat);
return status;
-
)
Note that /dev/tty is opened with mode 2 — read and write — and then
dup'ed to form the standard input and output. This is actually how the system
assembles the standard input, output and error when you log in, Therefore,
your standard input is writable:
$ echo hello 1260
hello
‘
This means we could have dup'ed file descriptor 2 to reconnect the standard
input and output, but opening /dew/tty is cleaner and safer. Even thisCHAPTER 7 UNIK SYSTEM CALLS 225
system has potential problems: open files in the caller, such as tty in the
routine ttyin in p, will be passed to the child process.
‘The lesson here is not that you should use our version of system for all
your programs — it would break a non-interactive ed, for example — but that
you should understand how processes are managed and use the primitives
correctly; the meaning of “correctly” varies with the application, and may not
agree with the standard implementation of system.
7.5 Signals and interrupts
This section is concerned with how to deal gracefully with signals (like
interrupts) from the outside world, and with program faults. Program faults
arise mainly from illegal memory references, execution of peculiar instructions,
fr floating point errors. ‘The most common outside-world signals are interrupt,
which is sent when the DEL character is typed; quit, generated by the FS char-
acter (ctl-\); hangup, caused by hanging up the phone; and terminate, gen=
erated by the ki11 command. When one of these events occurs, the signal is
sent to all processes that were started from the same terminal; unless other
arrangements have been made, the signal terminates the process. For most sig-
nals, a core image file is written for potential debugging. (See adb(1) and
s€b(1).)
‘The system call signal alters the default action. It has two arguments.
‘The first is a number that specifies the signal. The second is either the address
of a function, or a code which requests that the signal be ignored or be given
the default action. The file contains definitions for the various
arguments. Thus
Wnelude
signal(SIGINP, SI¢_IGN);
‘causes interrupts to be ignored, while
signal(SIGINT, SIG_DPL);
restores the default action of process termination. In all cases, signal returns
the previous value of the signal. If the second argument to signal is the
name of a function (which must have been declared already in the same source
file), the function will be called when the signal occurs. Most commonly this,
facility is used to allow the program to clean up unfinished business before ter-
18, for example to delete a temporary file:226 THE UNIX PROGRAMMING ENVIRONMENT cuarren 7
#include
char *tempfile = "temp-Xxx00t"s
mainQ)
{
extern onintr();
Af (signal (SIGINT, $1G_1GN) I= st¢_rGw)
signal (SIGINT, onintr);
nktemp(tempfile) ;
7s Process... 4/
exit(0);
>
onintr() /+ clean up if interrupted */
{
unlink (tempfile);
exit(4);
,
Why the test and the double call to signa in main? Recall that signals
are sent to all processes started from a particular terminal. Accordingly, when
4 program is to be run non-interactively (started by &), the shell arranges that
the program will ignore interrupts, so it won't be stopped by interrupts
intended for foreground processes. If this program began by announcing that
all interrupts were to be sent to the onintr routine regardless, that would
undo the shell’s effort to protect it when-run in the background.
The solution, shown above, is to test the state of interrupt handling, and to
continue to ignore interrupts if they are already being ignored. The code as
written depends on the fact that signal returns the previous state of a partic-
ular signal. If signals were already being ignored, the process should continue
to ignore them; otherwise, they should be caught.
‘A more sophisticated program may wish to intercept an interrupt and inter-
pret it as a request to stop what it is doing and return to its own command-
processing loop. Think of a text editor: interrupting a long printout should not
cause it t0 exit and lose the work already done. The code for this case can be
written like this:‘CHAPTER 7 UNIK SYSTEM CALLS 227
#include
#inclade
Smp_buf sibuf;
main()
int oninte();
Af (signal(SIGINT, SIG_IGN) I= SIG_16N)
signal (SIGINT, onintr);
setjmp(ajbut); /4 save current stack position +/
for (33) (
74 pain processing loop +/
}
,
onintr() /# x
t
jet if interrupted +/
eignal(SIGINT, onintr); /+ reset for next interrupt #/
printé(*\ntnterrupt\n" );
Longjmp(s buf, 0); /+ return to saved state +/
,
The file declares the type jmp buf as an object in which the
stack position can be saved; s buf is declared to be such an object. ‘The func-
tion set:jmp(3) saves a record of where the program was executing. The
values of variables are nor saved. When an interrupt occurs, a call is forced 10
the onintr routine, which can print a message, set flags, or whatever
Long jmp takes as argument an object stored into by set imp, and restores
control to the location after the call 10 setjmp. So control (and the stack
level) will pop back to the place in the main routine where the main loop is
entered,
Notice that the signal is set again in onintr after an interrupt occurs.
This is necessary: signals are automatically reset to their default action when
they occur.
‘Some programs that want to detect signals simply can’t be stopped at an
arbitrary point, for example in the middle of updating a complicated data struc-
ture. The solution is to have the interrupt routine set a flag and return instead
of calling exit or Long jmp. Execution will continue at the exact point it was
interrupted, and the interrupt flag can be tested later.
There is one difficulty associated with this approach. Suppose the program
is reading the terminal when the interrupt is sent. The specified routine is duly
called; it sets its flag and returns. If it were really true, as we said above, that
execution resumes “at the exact point it was interrupted,” the program would
continue reading the terminal until the user typed another line. This behavior228 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER 7
might well be confusing, since the user might not know that the program is,
reading, and presumably would prefer to have the signal take effect instantly
To resolve this difficulty, the system terminates the read, but with an error
status that indicates what happened: eeno is set to EINTR, defined in
, to indicate an interrupted system call.
‘Thus programs that catch and resume execution after signals should be
prepared for “errors” caused by interrupted system calls. (The system calls to
‘watch out for are reads from a terminal, wait, and pause.) Such a program
could use code like the following when it reads the standard input
#include
extern int errno;
if (read(0, Sc, 1) <= 0) /+ EOF or interrupted +/
Af (errno “= EINTR) {| /+ EOF caused by interrupt +/
errno = 0; /+ reset for next time */
7s true end of file #/
‘There is a final subtlety to keep in mind when signal-catching is combined
with execution of other programs. Suppose a program catches interrupts, and
also includes a method (like "*!” in ed) whereby other programs can be exe
cuted. Then the code would look something like this:
Af (fork() == 0)
execip(...);
signal(SIGINT, SIG_IGN); /+ parent ignores interrupts */
wait(Gstatue); 7+ until child is done */
signal (SIGINT, onintr
/+ restore interrupts */
Why is this? Signals are sent to all your processes. Suppose the program you
call catches its own interrupts, as an editor does. If you interrupt the subpro-
gram, it will get the signal and return to its main loop, and probably read your
terminal. But the calling program will also pop out of its wait for the subpro-
gram and read your terminal. Having two processes reading your terminal is
very confusing, since in effect the system flips a coin to decide who should get
each line of input. ‘The solution is to have the parent program ignore inter-
rupts until the child is done. This reasoning is reflected in the signal handling
in system:‘CHAPTER 7 UNIX SYSTEM CALLS 229
#inelude
system(s) /* xun command line = +/
char «3
0
int status, pid, w, tty:
Ant (4istat)(), (aqstat)()s
if (pia = forkc)
execip(“sh’
exit (127);
d
istat = signal(siGINr, stG_rGN)
gstat = signal(stcqurT, s1¢_rGn)
while ((w = wait(Kstatus)) I= pid && w
ie (wae 1)
signal (SIGINT, istat);
signal (Srcaurr, qstat);
return statue;
)
As an aside on declarations, the function signal obviously has a rather
strange second argument. It is in fact a pointer to a function delivering an
integer, and this is also the type of the signal routine itself, The two values
SIG_IGN and SIG_DFL have the right type, but are chosen so they coincide
‘with no possible actual functions. For the enthusiast, here is how they are
defined for the PDP-11 and VAX; the definitions should be sufficiently ugly 10
‘encourage use of .
fdefine SIG_DFL (int (+)())0
f#define SIGLIGN (int (#)())1
Alarms
‘The system call alarm(n) causes a signal STGALRM to be sent to your pro-
cess m seconds later. The alarm signal can be used for making sure that some-
thing happens within the proper amount of time; if the something happens, the
alarm signal can be turned off, but if it does not, the process can regain control
by catching the alarm signal
To illustrate, here is a program called timeout that runs another com-
mand; if that command has not finished by the specified time, it will be
aborted when the alarm goes off. For example, recall the watchfor com-
mand from Chapter 5. Rather than having it run indefinitely, you might set a230 THE UNIX PROGRAMMING ENVIRONMENT ‘CHAPTER?
limit of an hour:
$ timeout -3600 watenfor dag &
The code in timeout illustrates almost everything we have talked about in
the past two sections. The child is created; the parent sets an alarm and then
waits for the child to finish. If the alarm arrives first, the child is killed. An
attempt is made to return the child’s exit status.
/4 timeout: set time Limit on a process +/
#include
#include
int pigs 7+ child process id +/
char +prognames
main(arge, argv)
int arge;
char targvt]s
«
Ant see = 10, status, onalarm();
prognane = argvi0);
3€ (arge > 1 66 argy(1](0} ‘
sec = atoi(argvi1][11)5
arge
argy+
)
Af (arge < 2)
error("Usage: %s [~10] command", progname);
Af ((pidefork()) == 0) (
execvp(argvi1], Sargvi1])
error("couldn’t start Xs", argv 1};
)
signal (SIGALRM, onalarn);
alarm(sec)
Af (wait(Sstatus) e= -1 11 (status & 0177) f= 0)
error("%s killed", argv{1)}i
exit((status >> 8) 6 0377);
)
onalarm() /+ kill child when alarm arrives +/
‘
kill (pid, STGKILL);
)
Exercise 7-18. Can you infer how steep is implemented? Hint: pause(2). Under
‘what circumstances, if any, could sleep and alarm interfere with each other? 0CHAPTER 7 UNIX SYSTEM CALLS 231
History and bibliographic notes
There is no detailed description of the UNIX system implementation, in part
because the code is proprietary. Ken Thompson’s paper “UNIX implementa
tion” (BSTJ, July, 1978) describes the basic ideas. Other papers that discuss
related topics are “The UNIX system—a retrospective” in the same issue of
BSTJ, and “The evolution of the UNIX time-sharing system” (Symposium on
Language Design and Programming Methodology, Springer-Verlag Lecture
Notes in Computer Science #79, 1979.) Both are by Dennis Ritchie.
The program readsiow was invented by Peter Weinberger, as a low-
‘overhead way for spectators to watch the progress of Belle, Ken Thompson and
Joe Condon’s chess machine, during chess tournaments. Belle recorded the
status of its game in a file; onlookers polled the file with readslow so as not
to steal too many precious cycles from Belle, (The newest version of the Belle
hardware does little computing on its host machine, so the problem has gone
away.)
Our inspiration for spname comes from Tom Duff. A paper by Ivor Dur-
ham, David Lamb and James Saxe entitled “Spelling correction in user inter
faces,” CACM, October, 1983, presents a somewhat different design for spel-
ling correction, in the context of a mail program,cuapter s: PROGRAM DEVELOPMENT
‘The UNIX system was originally meant as a program development environ-
ment. In this chapter we'll talk about some of the tools that are particularly
suited for developing programs. Our vehicle is a substantial program, an inter-
preter for a programming language comparable in power to BASIC, We chose
to implement a language because it's representative of problems encountered in
large programs. Furthermore, many programs can profitably be viewed as
languages that convert a systematic input into a sequence of actions and out-
puts, so we want to illustrate the language development tools.
In this chapter, we will cover specific lessons about
» yace, a parser generator, a program that generates a parser from a gram.
‘matical description of a language;
© make, a program for specifying and controlling the processes by which a
complicated program is compiled;
© Lex, a program analogous to yace, for making lexical analyzers.
We also want to convey some notions of how to go about such a project — the
importance of starting with something small and letting it grow; language evo-
lution; and the use of tools.
‘We will describe the implementation of the language in six stages, each of
which would be useful even if the development went no further. These stages
closely parallel the way that we actually wrote the program.
(1)A four-funetion calculator, providing +, -, *, / and parentheses, that
‘operates on floating point numbers. One expression is typed on each line;
its value is printed immediately.
(2) Variables with names a through 2. This version also has unary minus and
some defenses against errors.
(3) Arbitrarily-long variable names, builtin functions for sin, exp, etc., use-
ful constants like 1 (spelled PI because of typographic limitations), and an
exponentiation operator.
(4) A change in internals: code is generated for each statement and subse-
quently interpreted, rather than being evaluated on the fly. No new
features are added, but it leads to (5)
(5) Control flow: if-e1se and while, statement grouping with { and }, and
233234 THE UNIX PROGRAMMING ENVIRONMENT ‘CHAPTER
relational operators like >, <2, ete.
(© Recursive functions and procedures, with arguments. We also added state-
‘ments for input and for output of strings as well as numbers.
The resulting language is described in Chapter 9, where it serves as the main
example in our presentation of the UNIX document preparation software.
Appendix 2 is the reference manual.
‘This is a very long chapter, because there's a lot of detail involved in get-
ting a non-trivial program written correctly, let alone presented. We are
assuming that you understand C, and that you have a copy of the UNIX
Programmer's Manual, Volume 2, close at hand, since we simply don’t have
space to explain every nuance. Hang in, and be prepared to read the chapter a
couple of times. We have also included all of the code for the final version in
Appendix 3, so you can see more easily how the pieces fit together.
By the way, we wasted a lot of time debating names for this language but
never came up with anything satisfactory. We settled on hoc, which stands
for “high-order calculator.” ‘The versions are thus hoc, hoc2, etc.
8.1 Stage 1: A four-function calculator
This section describes the implementation of hoc, a program that provides
about the same capabilities as a minimal pocket calculator, and is substantially
less portable. It has only four functions: +, ~, *, and /, but it does have
parentheses that can be nested arbitrarily deeply, which few pocket calculators
provide. If you type an expression followed by RETURN, the answer will be
printed on the next line:
§ hoot
40302
24
(142) © (Gea)
24
wa
a5
355/113,
3.1415929
-3-4
hoct: syntax error near line 4 It doesn't have unary minus yet
s
Grammars
Ever since Backus-Naur Form was developed for Algol, languages have
been described by formal grammars. The grammar for hoc is small and sim-
ple in its abstract representation:corAPTER § PROGRAM DEVELOPMENT 235
List: expr \n
List expe \n
expr: NUMBER
expr + expe
expr - expr
expe + expr
expe / expr
(expr)
In other words, a List is a sequence of expressions, each followed by a new-
line. An expression is a number, or a pair of expressions joined by an opera-
tor, or a parenthesized expression.
This is not complete. Among other things, it does nat specify the normal
precedence and associativity of the operators, nor does it attach a meaning to
any construct, And although List is defined in terms of expr, and expr is,
defined in terms of NUMBER, NUMBER itself is nowhere defined. ‘These details
have to be filled in to go from a sketch of the language to a working program.
Overview of yace
yace is a parser generator.t that is, a program for converting a grammati-
cal specification of a language like the one above into a parser that will parse
statements in the language. yacc provides a way fo associate meanings with
the components of the grammar in such a way that as the parsing takes place,
the meaning can be “evaluated” as well. The stages in using yace are the fol.
lowing
First, a grammar is written, like the one above, but more precise. This
specifies the syntax of the language. yacc can be used at this stage to warn of
errors and ambiguities in the grammar.
Second, each rule or production of the grammar can be augmented with an
‘action — a statement of what to do when an instance of that grammatical form
is found in a program being parsed. The “what to do” part is written in C,
with conventions for connecting the grammar to the C code. This defines the
semantics of the language
Third, a lexical analyzer is needed, which will read the input being parsed
and break it up into meaningful chunks for the parser. A NUMBER is an exam-
ple of a lexical chunk that is several characters long; single-character operators
like + and + are also chunks. A lexical chunk is traditionally called a roken
Finally, a controlling routine is needed, to call the parser that yace built.
yace processes the grammar and the semantic actions into a parsing func-
tion, named yyparse, and writes it out as a file of C code. If yace finds no
errors, the parser, the lexical analyzer, and the control routine can be
¥ yace stands for “yet another compiler-compiler." a comment by its ereator, Steve Johnson, on
the number of such programs extant atthe Lime it was boing developed (around 1972). yee is
‘one of hand that have flourished.236 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
compiled, perhaps linked with other C routines, and executed. ‘The operation
of this program is to call repeatedly upon the lexical analyzer for tokens,
recognize the grammatical (syntactic) structure in the input, and perform the
semantic actions as each grammatical rule is recognized. ‘The entry to the lexi-
cal analyzer must be named yylex, since that is the function that yyparse
calls each time it wants another token. (All names used by yace start with y.)
To be somewhat more precise, the input to yace takes this form:
x4
C statements like #inciude, declarations, ete. This section is optional
*
‘ace declarations: lexical tokens, grammar variables,
precedence and associativity information
we
‘grammar rules and actions
cy
‘more C statements (optional
main() ( ...3 yyparse()s ... }
yylex) se. }
This is processed by yace and the result written into a file called [Link].c,
whose layout is like this:
C statements from berween %( and %), ifany
€ statements from after second %, if any
main() ( ...5 yyparse(); -..
yrtext) Cie D
yyparse() { parser, which calls yylex() }
It is typical of the UNIX approach that yace produces C instead of a com-
piled object (0) file. ‘This is the most flexible arrangement — the generated
code is portable and amenable to other processing whenever someone has a
good idea
yace itself is a powerful tool. It takes some effort to learn, but the effort
is repaid many times over. yace-generated parsers are small, efficient, and
correct (though the semantic actions are your own responsibility); many nasty
parsing problems are taken care of automatically. Language-recognizing pro
grams are easy to build, and (probably more important) can be modified
repeatedly as the language definition evolves.
‘Stage I program
‘The source code for hoc’ consists of @ grammar with actions, a lexical rou-
tine yylex, and a main, all in one file hoc.y. (yace filenames traditionally
end in .y, but this convention is not enforced by yace itself, unlike cc and
+¢.) The grammar partis the first half of hoc.y:CHAPTER § PROGRAM DEVELOPMENT 237
$ cat hoc.
me
faefine YYSTYPE double /x data type of yace stack +/
x)
Xtoken NUMBER
Kleft ‘s' ‘-' /s left associative, same precedence +/
Kleft "*' ’/' 7s left assoc., higher precedence +/
x
List: nothing +/
blast “\n"
Plist expr ‘\n’ —( printe(*\[Link]\n", $2); }
expr: | NUMBER (sess
expr ‘6 expr ( 3114 $3; }
expr ‘~ expr { 81-83: }
expe 'e? expr { $16 $35)
expe ‘/* expr { 817.83; )
1° expe 1)" 325)
1%
Ys ond of grammar +/
There's a lot of new information packed into these few lines, We are not
going to explain all of it, and certainly not how the parser works — for that,
you will have to read the yace manual
Alternate rules are separated by ‘!", Any grammar rule can have an associ
ated action, which will be performed when an instance of that rule is recog-
nized in the input. An action is a sequence of C statements enclosed in braces
{and }. Within an action, $n (that is, $1, $2, etc.) refers to the value
returned by the n-th component of the rule, and $$ is the value to be returned
a the value of the whole rule. So, for example, in the rule
expr: NUMBER ( $$ = $1; )
$1 is the value returned by recognizing NUMBER; that value is to be returned as
the value of the expr. ‘The particular assignment $$=8 1 can be omitted — $3
is always set to $1 unless you explicitly set it to something els.
‘At the next level, when the rule is
expe: expr ‘+’ expr ( $8 = $1 + $35)
the value of the result expr is the sum of the values from the two component
expr's. Notice that ’+” is $2; every component is numbered.
‘AL the level above this, an expression followed by a newline (’\n‘) is
recognized as a list and its value printed. If the end of the input follows such a
construction, the parsing process terminates cleanly. A List can be an empty
string; this is how blank input lines are handled.
yace input is free form; our format is the recommended standard.238 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
In this implementation, the act of recognizing or parsing the input also
causes immediate evaluation of the expression. In more complicated situations
(including hoc4 and its successors), the parsing process generates code for
later execution.
‘You may find it helpful to visualize parsing as drawing a parse tree like the
one in Figure 8.1, and to imagine values being computed and propagated up
the tree from the leaves towards the root
fist
Aa
tsi” woman nuusée | noMBER
\
toby 2 4
\n
Figure 8.1: Parse Tree for 2 + 3 + 4
‘The values of incompletely-recognized rules are actually kept on a stack; this is
how the values are passed from one rule to the next. The data type of this
stack is normally an int, but since we are processing floating point numbers,
‘we have to override the default. The definition
faefine YvsTYPE double
sets the stack type to double.
Syntactic classes that will be recognized by the lexical analyzer have to be
declared unless they are single character literals like ‘+’ and *~". The
declaration %token declares one or more such objects. Left oF right associa-
tivity can be specified if appropriate by using %left or right instead of
Xtoken. (Left associativity means that a~b-e will be parsed as (s-b)-¢
instead of a-(b-c).) Precedence is determined by order of appearance:
tokens in the same declaration are at the same level of precedence; tokens
declared Ister are of higher precedence. In this way the grammar proper is
ambiguous (that is, there are multiple ways to parse some inputs), but the
extra information in the declarations resolves the ambiguity
The rest of the code is the routines in the second half ofthe file hoc.y:‘CHAPTER & PROGRAM DEVELOPMENT 239
Continuing noc-y
#include
#inelude
char sprognane; /+ for error messages */
int Lineno = 1;
main(arge, argv) Zs moet «/
char sargvi li
«
progname = argv( 0};
yyparse():
>
main calls yyparse to parse the input. Looping from one expression to the
next is done entirely within the grammar, by the sequence of productions for
List. It would have been equally acceptable to put a loop around the call to
yyparse in main and have the action for List print the value and return
immediately.
yyparse in turn calls yylex repeatedly for input tokens. Our yylex is
easy: it skips blanks and tabs, converts strings of digits into a numeric value,
counts input lines for error reporting, and returns any other character as itself.
Since the grammar expects to see only +, -, #, /, (, ), and \n, any other
character will cause yyparse to report an error. Returning a 0 signals “end
of file” to yyparse.
Continuing noe. y
yylext) y+ moet +/
{
if (c == Bor)
return 0;
‘et Tt dedigit(c)) { /+ number +/
ungetc(c, stdin);
seanf("%i£", Syylval
return NUMBER;
if tc
)
if (owe Mn!)
Linenosss
,
The variable yyival is used for communication between the parser and the
lexical analyzer; it is defined by yyparse, and has the same type as the yace
stack. yylex returns the ype of a token as its function value, and sets
yylval to the value of the token (if there is one). For instance, a floating240 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
point number has the type NUMBER and a value like 12.34. For some tokens,
especially single characters like ’+” and ’\n’, the grammar does not use the
value, only the type. In that case, yyivai need not be set
The yacc declaration %token NUMBER is converted into a #define state-
ment in the yace output file [Link].c, so NUMBER can be used as a constant
anywhere in the C program. yacc chooses values that won't collide with
ASCII characters.
If there is a syntax error, yyparse calls yyerror with a string containing
the cryptic message “syntax error.” The yace user is expected to provide
a yyerror; ours just passes the string on to another function, warning,
Which prints somewhat more information, Later versions of hoc will make
direct use of warning.
yyerzor(s) /+ called for yace syntax error #/
char +8
‘
warning(s, (char #) 0);
>
varning(s, t) /* print warning message */
char «8, «t}
f
fprintf(stderr, "Ws: Xs", progname, 8);
se (te)
fprintf(stderr, * 4s", €)5
fprintf(stderr, "near line %a\n", lineno);
)
‘This marks the end of the routines in hoc. y.
Compilation of a yace program is a two-step process:
$ yace hoc. Leaves ouput in [Link].c
$cc [Link].c -0 hoct Leaves executable program in hoot
$ hoot
23
0..66666667
3-4
hoct: syntax error near line 1
s
Exercise 8-1. Examine the structure of the [Link].¢ file. (It's about 300 lines long for
heel.) o
‘Making changes — unary minus
We claimed earlier that using yacc makes it easy to change a language.
As an illustration, let’s add unary minus to hoc, so that expressions like
o34CHAPTER 8 PROGRAM DEVELOPMENT 241
are evaluated, not rejected as syntax errors.
Exactly two lines have to be added to hoc.y. A new token UNARYMINUS
is added to the end of the precedence section, to make unary minus have
highest precedence:
wiete far =
mete "e177
voleft — UNARYMTNUS + new */
‘The grammar is augmented with one more production for expr:
expe: NUMBER ($82 $15)
1 =" expr Xprec UNARYMINUS ( $$ = -$2; ) /» new #/
‘The %prec says that a unary minus sign (that is, a minus sign before an
expression) has the precedence of UNARYMINUS (high); the action is 10 change
the sign. A minus sign between two expressions takes the default precedence.
Bxercise 8-2. Add the operators % (modulus or remainder) and unary + to hoc.
Suggestion: look at frexp(3). ©
A digression on make
It’s a nuisance to have to type two commands to compile a new version of
hoct. Although it’s certainly easy to make a shell file that does the job,
there’s a better way, one that will generalize nicely later on when there is more
than one source file in the program. The program make reads a specification
‘of how the components of a program depend on each other, and how to pro-
cess them to create an up-to-date version of the program. It checks the times
at which the various components were last modified, figures out the minimum
amount of recompilation that has to be done to make a consistent new version,
then runs the processes. make also understands the intricacies of multi-step
processes like yacc, so these tasks can be put into a make specification
‘without spelling out the individual steps.
make is most useful when the program being created is large enough to be
spread over several source files, but it’s handy even for something as small as
hoct. Here is the make specification for hoc, which make expects in a file
called makefile.
$ cat makefile
hoc: hoe.0
ec hoe.0 -0 hoct
This says that hoc1 depends on hoc.o, and that hoc.o is converted into
hoc! by running the C compiler ce and putting the output in hoct. make
already knows how to convert the yace source file in hoc.y to an object file
hoc.o:282 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
$ make Make the frst thing in makefite, hoot
yace hoc.y
co -c [Link].c
zn [Link].c
nv [Link].o hoc.o
co hoc.o -o hoot
8 make Do it again
“noet” is up to date. make realizes i's unnecessary
s
8.2 Stage 2: Variables and error recovery
‘The next step (a small one) is to add “memory” to hoct, to make hoc?.
‘The memory is 26 variables, named a through z. This isn't very elegant, but
it’s an easy and useful intermediate step. We'll also add some error handling.
If you try hoc, you'll recognize that its approach to syntax errors is to print &
message and die, and its treatment of arithmetic errors like division by zero is
reprehensible:
$ hoct
vo
Floating exception ~ core dumped
s
The changes needed for these new features are modest, about 35 lines of
code. The lexical analyzer yylex has to recognize letters as variables; the
grammar has to include productions of the form
expe VAR
1 VAR “= expe
‘An expression can contain an assignment, which permits multiple assignments
like
‘The easiest way to store the values of the variables is in a 26-element array;
the single-letter variable name can be used to index the array. But if the gram-
‘mar is to process both variable names and values in the same stack, yace has
to be told that its stack contains a union of a double and an int, not just a
double. This is done with a %union declaration near the top. A #define
or a typedef is fine for setting the stack to a basic type like double, but the
%union mechanism is required for union types because yace checks for con-
sistency in expressions like $822.
Here is the grammar part of hoc.y for hoc2(CHAPTER PROGRAM DEVELOPMENT 243
$ cat hoc.y
%E
double mem(261; “4 memory for variables ‘a..'z" #/
»
Manion ( /s stack type */
double 7 actual value +/
int index; /# index into men[] +/
i
token NUMBER
Ktoken VAR
ktype expr
Sright
mest 147 7-7
wef te 77
left UNARYMINUS
wm
List J+ nothing +/
| ldee “An
| list expr ‘\n’ { printe("\[Link]\n", $2)5 }
| lise error “\n’ { yyerrok;
NUMBER
1 var (88 = ments); )
Hvar ‘2° expr ( nea($1)
expr ‘+? expr { sie s
| expr ‘-" expr (88 = $1 - §:
Pexpr ‘#/ expr ( 88 = $1 + $3;
expr "7" expr {
if (83 == 0.0)
execerror(
$3517 $3; )
"expr ‘)? {88 = 825)
1 '-* expr Xprec UNARYMINUS ( $$ = 82; )
7s end of grammar +/
‘The Kunion declaration says that stack elements hold either a double (a
number, the usual case), or an int, which is an index into the array mem.
The %token declarations have been augmented with a type indicator. The
xtype declaration specifies that expr is the member of the union, i.e.,
a double. The type information makes it possible for yace to generate refer-
fences to the correct members of the union. Notice also that = is right-
associative, while the other operators are left-associative.
Error handling comes in several pieces. The obvious one is a test for a zero
divisor; if one occurs, an error routine execerror is called,
A second test is to catch the “floating point exception” signal that occurs244 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER §
when a floating point number overflows. The signal is set in main.
The final part of error recovery is the addition of a production for exror.
“error” is @ reserved word in a yacc grammar; it provides a way to antici-
pate and recover from a syntax error. If an error occurs, yace will eventually
try to use this production, recognize the error as grammatically “correct,” and,
thus recover, The action yyerrok sets a flag in the parser that permits it to
get back into a sensible parsing state. Error recovery is difficult in any parser;
you should be aware that we have taken only the most elementary steps here,
‘and have skipped rapidly over yace’s capabilities as well.
The actions in the hoc2 grammar are not much changed. Here is main, to
which we have added set jmp to save a clean state suitable for resuming after
fan error. execerror does the matching longjmp. (See Section 7.5 for a
description of set-jmp and Long imp.)
Hnclude
#include
jmp_buf begin;
main(arge, argv) 7s nocd #/
char sargvlli
t
int fpecaton()5
prognane = argv[0];
set jmp( begin):
signal(SIGFPE, fpecatch);
yyparse();
)
execerror(s, t) /+ recover from run-time error +/
char +8, +t;
‘
warning(s, €)5
Longjmp(begin, 0);
)
Epecateh() + catch Floating point exceptions +/
{
execerror("floating point exception", (char +) 0)5
>
For debugging, we found it convenient to have execerror call abort (see
abort(3)), which causes a core dump that can be perused with adb or sdb.
Once the program is fairly robust, abort is replaced by long jmp.
The lexical analyzer is a litle different in hoc2. There is an extra test for
& lower-case letter, and since yylval is new a union, the proper member has
to be set before yylex returns. Here are the parts that have changed:‘CHAPTER PROGRAM DEVELOPMENT 245
yylex() 7+ noe +/
Hi dgaigitic)) (| /* number «/
ungete(c, stdin);
seanf("Xie", [Link]);
return NUMBER;
;
if (isiower(e)) ¢
[Link] = ¢ = ’a’; /+ ASCII only +/
‘Again, notice how the token type (e.g., NUMBER) is di
(eg. 3.1416).
Le us illustrate variables and error recovery, the new things in hoc?
inct from its value
$ hoc2
x = 355
ass.
yet
493
psx 2 is undefined and thus zero
@ivision by zero near line 4 Error recovery
3.418929
4230 # 1630 Overflow
ocd: floating point exception near line 5
Actually, the PDP-11 requires special arrangements to detect floating point
overflow, but on most other machines hoc2 behaves as shown.
Exercise 8.3. Add a facility for remembering the most recent value computed, so that it
does not have to be retyped in a sequence of related computations. One solution is to
make it one of the variables, for instance “p' for “previous.” 0
Exercise 8-4. Modify hoc so that a semicolon can be used as an expression terminator
‘equivalent to a newline, ©
8.3 Stage 3: Arbitrary variable names; buil
functions
This version, hoc3, adds several major new capabilities, and a correspond-
ing amount of extra code. The main new feature is access to built-in functions:
sin cos atan exp, log. og 10
sqrt int = abs
We have also added an exponentiation operator
cedence, and is right-associative,
Since the lexical analyzer has to cope with built:
it has the highest pre-
names longer than a286 THE UNIX PROGRAMMING ENVIRONMENT HAPTER &
single character, it isn’t much extra effort to permit variable names to be arbi
trarily long as well. We will need a more sophisticated symbol table to keep
track of these variables, but once we have it, we can pre-load it with names
and values for some useful constants:
Pr 3.14159265358979323846 a
E 2.71828182845904523536 Base of natural logarithms
GAMMA _0.57721566490153286060 Euler-Mascheroni constant
DEG —_57.29577951308232087680 Degrees per radian
Pur 1,61803398874989484820 Golden ratio
‘The result is @ useful calculator:
$ hoo3
4.5723
2,5410306
exp(2.34109(1.5))
2,5470206
sin(PI/2)
4
atan(1)*DBG
45
We have also cleaned up the behavior a little. In hoc2, the assignment
expr not only causes the assignment but also prints the value, because all
expressions are printed:
$ hoc2
x= 26 3.14159
6.20318 Value printed for assignment to variable
In hoc3, 2 distinction is made between assignments and expressions; values are
printed only for expressions:
$ hoes
xr 2+ 3.14159 Assignment: no value is printed
x Expression:
6.28318 value is printed
‘The program that results from all these changes is big enough (about 250
lines) that it is best split into separate files for easier editing and faster compi-
lation. There are now five files instead of one:CHAPTER & PROGRAM DEVELOPMENT. 247
hoe-y Grammar, main, yylex (as before)
hoo.h Global data structures for inclusion
symbole ‘Symbol table routines: Lookup, snetaLl
initic Built-ins and constants; init
math-c Interfaces to math routines: Sart, Log, ete
This requires that we learn more about how to organize a multi-file C pro-
gram, and more about make so it can do some of the work for us.
We'll get back to make shortly. First, let us look at the symbol table code.
A symbol has name, a type (it’s either a VAR or a BLTIN), and a value. If
the symbol is a VAR, the value is a double; if the symbol is a built-in, the
value is @ pointer to a function that returns a double. This information is
needed in hoc-y, symbol.c, and init.c. We could just make three copies,
but it’s too easy to make a mistake or forget to update one copy when a change
ig made. Instead we put the common information into a header file hoc.
that will be included by any file that needs it. (The suffix -h is conventional
but not enforced by any program.) We will also add to the makefite the fact
that these files depend on hoc-h, so that when it changes, the necessary
recompilations are done too.
$ cat hoc.h
typedef etruct symbol { /+ symbol table entry */
char mame;
short types /+ VAR, BLTIN, UNDEF +/
union (
double va 7s $6 VAR +/
gouble (*ptr)(); 7s SE BURIN «/
dus
struct Symbol next; /+ to link to another +/
} symbols
Symbol tinstall(), #lookup();
s
‘The type UNDEF is a VAR that has not yet been assigned a value.
The symbols are linked together in a list using the next field in Symbol.
‘The list itself is local to symbo1.c; the only access to it is through the func
tions Lookup and install. This makes it easy to change to symbol table
organization if it becomes necessary. (We did that once.) Lookup searches
the list for a particular name and returns a pointer to the Symbol with that
name if found, and zero otherwise. The symbol table uses linear search, which
is entirely adequate for our interactive calculator, since variables are looked up
only during parsing, not execution. instai1 puts a variable with its associ
ated type and value at the head of the list. emalloc calls malloc, the stan
dard storage allocator (ma11oc(3)), and checks the result. These three rou-
tines are the contents of symbol.c. The file [Link]-h is generated by run-
ning yace ~d; it contains #4efine statements that yace has generated for
tokens like NUMBER, VAR, BLTIN, etc.248 THE UNIX PROGRAMMING ENVIRONMENT ‘CHAPTER
$ cat symbol.c
#inelude "hoc .h"
#include “[Link].n*
static Symbol *symlist = 0; /* symbol table: linked list +/
Symbol *lockup(2) /* find 8 in symbol table +/
char
symbol +sp;
for (sp = symlist; sp I= (Symbol +) 0; sp = sp-snext)
Af (stremp(sp->nane, 5) == 0)
return sp;
return 0; 7+ 0 ==> not found */
?
symbol tinstali(s, t, 4) /+ install 6 in symbol table +/
char #83
int ti
double 4;
‘
symbol +s:
char semalloc();
sp = (Symbol +) emalloc( sizeof (symbol) );
sp->name = enalloc(strien(s)+1); /* +1 for ‘\0" «/
stropy(sp->name, 5:
sp->type = th
sp->[Link] = a;
sp->next = symlist; /+ put at front of list «/
symlist = spi
return 8p
)
char temalloc(n) /+ check return from malloc +/
unsigned nj
char +p, *malloc()s
p= malloc(n);
if (ps 0)
execerror("out of memory", (char *) 0);
return pi
)
s
The file init.c contains definitions for the constants (PI, etc.) and func
tion pointers for built-ins; they are installed in the symbol table by the function
init, which is called by main.CHAPTER §
8 cat init.c
#incluge "hoc.h”
#include "[Link]-n"
#include
PROGRAM DEVELOPMENT 249,
extern double Log(), Logt0(), Expl), sart(), integer();
static struct {
7s constants «/
char ename;
double eval;
) constst} = (
spr", 3, 14159265358979323846,
spt,” 2177828182843904523536,
"Gamma", 0.57721566490 153286060,
spec", '57.2957795 1308232087680,
"PHI", — 1.61803398874989404820,
°, o
h
static struct ( 7s Bailt-ins «/
char «name;
double (+fune)();
} puittins(] = ¢
checks.
checks
checks
checks
argument
argument
argunent,
argument,
"tog",” bog, /+
“Logi0", Logt0, /+
sexe", “Exp. | /*
“sqrt", Sart, /+
“ant",’ integer,
"abs", fabs,
°, °
a
init() /* install constants and built-ins
t
int 4;
syabol +
for (i = 0; conatali).name; i++)
install (consts[i].name, VAR, consts[i]
for (i = 0; builtine[i).names i++) {
/+ Baler +/
7s deg/radian +/
7s golden ratio */
”
”
”
in table «/
install (builtins[i).name, BLTIN, 0.
[Link] = builtins[i].func}
seval)
af
‘The data is kept in tables rather than being wired into the code because tables
ate easier to read and to change. The tables are declared static so that they
are visible only within this file rather than throughout the program. We'll
‘come back to the math routines like Log and Sqxt shortly.250 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER
With the foundation in place, we can move on to the changes in the gram-
mar that make use of it.
cat hoc.y
x
#include "hoc.h”
extern double Pow();
*
union {
double val: / actual value +/
Symbol ‘sym; /+ symbol table pointer +/
i
token NUMBER
Meoken VAR BLTIN UNDEF
wtype expr asgn
wrignt ‘=
west 14 ="
weft fet 177
‘left UWARYMINUS
Wright ‘*/ — /* exponentiation «/
1%
List: /+ nothing «/
blise ‘\n"
List asgn ’\n’
List expr ‘\n’ ( peinte(*\t%.eg\n", $2); }
List error ’\n’ 4 yyerrok; >
asgn: | VAR ’e expr ( $$2$%->[Link]$3; $1->type = VAR: }
expr: NUMBER
1 VAR ( Sf (81->type == UNDEF)
execerror( "undefined variable", $1->name);
$8 = [Link]; }
expr ‘*’ expr { $8 = $1 + 83)
expr ‘/' expr (
Ae ($3 == 0.0)
execerror("division by zero",
e267 $3; )
Eexpr ‘*/ expr { $8 = Pow(s1, $3); }
EC expe 17 1 $80 925}
=! expr prec UNARYMINUS { $$ = -82; }
>
1 asgn
Poautee “(7 expr 7)? (88 = (e($1->[Link]))(83)5 }
F expr ‘¢’ expr ($8 = $1 + $35)
E expr ‘-" expr ( $8 = $1 - 83; )
%
/+ end of granmar +/CHAPTER & PROGRAM DEVELOPMENT 251
‘The grammar now has asgn, for assignment, as well as expr; an input line
that contains just
VAR = expr
is an assignment, and so no value is printed. Notice, by the way, how easy it
was to add exponentiation to the grammar, including its right associativity
The yace stack has a different Kunion: instead of referring to a variable
by its index in @ 26-element table, there is a pointer to an object of type
Symbol. The header file hoc. h contains the definition of this type.
The lexical analyzer recognizes variable names, looks them up in the sym-
bol table, and decides whether they are variables (VAR) or built-ins (BLTIN)
The type returned by yylex is one of these; both user-defined variables and
pre-defined variables like PI are VAR's.
One of the properties of a variable is whether or not it has been assigned a
value, so the use of an undefined variable can be reported as an error by
yyparse. The test for whether a variable is defined has to be in the gram-
mar, not in the lexical analyzer. When a VAR is recognized lexically, its con-
text isn’t yet known; we don’t want a complaint that x is undefined when the
context is perfectly legal one such as the left side of an assignment like 221
Here is the revised part of yylex:
yytext) 7s nocd «/
Af (isalphate)) (
Symbol +8;
char sbuf[100], #p = sbaf;
ao {
spre = cy
} while ((c=getchar())
ungetc(c, stdin);
ap = ‘0
AE
sAnum(c))
jookup( sbuf))
8 = install(sbuf, UNDEF, 0.0);
[Link]
return e->type
UNDEF ? VAR : s->type;
main has one extra line, which calls the initialization routine init to
install built-ins and pre-defined names like PI in the symbol table.282 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER §
main(arge, argv) 7+ nocd +/
char eargv( i
«
int fpecaten();
progname = argv(0);
init(
set mp(begin) ;
signal (SIGFPE, fpecaten);
yyparse();
>
The only remaining file is math.c. Some of the standard mathematical
functions need an error-checking interface for messages and recovery — for
example the standard function sqrt silently returns zero if its argument is
negative. The code in math.c uses the error tests found in Section 2 of the
unix Programmer's Manual; see Chapter 7. This is more reliable and portable
than writing our own tests, since presumably the specific limitations of the rou-
tines are best reflected in the “official” code. The header file con-
tains type declarations for the standard mathematical functions.
contains names for the errors that can be incurred.
$ cat math.c
‘include
#inelude
extern int errno}
double errcheck();
double Log(x)
double x;
return errcheck(iog(x), “log"):
double Log 10(x)
double x;
return errcheck(1og10(x), "log10");
double Exp(x)
double x;
return errcheck(exp(x), “exp");
double sqrt (x)
double x;
return errcheck(sqrt(x), “sqrt");CHAPTER PROGRAM DEVELOPMENT 253
double Pow(x, y)
double x, yi
‘
return errcheck(pow(x,y), "exponentiation" );
)
double integer (x)
double x;
‘
return (double) (long) x;
}
double errcheck(4, 8) /* check result of library call «/
double 4;
char #8;
4€ (errno == EDOM) ¢
execerror(s, "argument out of domain");
} eise if (errno == ERANGE) {
errno = 0;
execerror(s, "result out of range
)
return
d
s
An interesting (and ungrammatical) diagnostic appears when we run yace
‘on the new grammar:
$ yace hoo.y
conflicts: 1 shift/reduce
s
The “shifvreduce” message means that the hoc3 grammar is ambiguous: the
single line of input
xa
ccan be parsed in two ways:254 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
lise
I
expr lise
| |
lish asgn list” asgn
| | | |
(emp) x= Xn (omy) x= Na
‘The parser can decide that the asgn should be reduced to an expr and then to a
list, as in the parse tree on the left, or it can decide to use the following \n
immediately ("shift") and convert the whole thing to a list without the inter-
mediate rule, as in the tree on the right. Given the ambiguity, yacc chooses
to shift, since this is almost always the right thing to do with real grammars,
You should try to understand such messages, to be sure that yace has made
the right decision.+ Running yace with the option -v produces a voluminous
file called [Link] that hints at the origin of conflicts.
Bxercise 8-5. As hoc3 stands, i's legal to say
prea
good idea? How would you change hoc3 to prohibit assignment to “con-
Exercise 8-6. Add the builtin function atan2(y,x), which returns the angle whose
tangent is y/x. Add the builtin xana(}, which returns a floating point random var
able uniformly distributed on the interval (0,1). How do you have to change the gram.
‘mar (0 allow for built-ins with different numbers of arguments?
Exercise 8-7. How would you add a facility to execute commands from within hoe,
similar to the 1 feature of other UNIX programs?
Bxercise 8-8. Revise the code in math.c to use a table instead of the set of essentially
identical functions that we presented,
Another digression on make
Since the program for hoc3 now lives on five files, not one, the makefile
is more complicated:
7 The yace message “reducelreduce confi” indicates x serious problem, more aften the symptom
of an outright error inthe grammar than an intentional umbigity.CHAPTER & PROGRAM DEVELOPMENT 255
5 cat makefile
YFLAGS = -4 # force creation of [Link]-h
OBJS = hoc.o init.o math.o symbol.o # abbreviation
hoe3: $(0BIS)
ce $(0B9S) -Im -0 hoc3
hoc.o: hoe.h
init.o eymbol.o: hoc.h y-tab.h
pr:
@pr hoc.y hoc.h init.c math.c eymbol.c makefile
clean:
rm -£ $(0BJS) [Link]. {ch}
’
‘The YELAGS = -d line adds the option -d to the yace command line gen-
erated by make; this tells yace to produce the [Link]-h file of #define
statements. The OBJS=... line defines a shorthand for a construct to be used
several times subsequently. ‘The syntax is not the same as for shell variables,
— the parentheses are mandatory. ‘The flag ~1m causes the math library to be
searched for the mathematical functions.
hhoc3 now depends on four .0 files; some of the .0 files depend on -b
files. Given these dependencies, make can deduce what recompilation is
needed after changes are made to any of the files involved. If you want to see
what make will do without actually running the processes, try
$ make -n
On the other hand, if you want to force the file times into a consistent state,
the -€ (“touch”) option will update them without doing any compilation steps.
Notice that we have added not only a set of dependencies for the source
files but miscellaneous utility routines as wel, all neatly encapsulated in one
place. By default, make makes the first thing listed in the makefile, but if
you name an item that labels a dependency rule, like symbol.o or pr, thet
will be made instead, An empty dependency is taken to mean that the item is
never “up to date,” so that action will always be done when requested. Thus
$ make pr Ipr
produces the listing you asked for on a line printer. (The leading @ in “@pr
suppresses the echo of the command being executed by make.) And
$ make clean
removes the yacc output files and the .0 files.
This mechanism of empty dependencies in the makefile is often256 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER §
preferable to a shell file as a way to keep all the related computations in a sin-
gle file. And make is not restricted to program development — it is valuable
for packaging any set of operations that have time dependencie:
A digression on Lex
‘The program Lex creates lexical analyzers in a manner analogous to the
way that yace creates parsers: you write a specification of the lexical rules of
your language, using regular expressions and fragments of C to be executed
when a matching string is found. Lex translates that into a recognizer. Lex
and yace cooperate by the same mechanism as the lexical analyzers we have
already written. We are not going into any great detail on Lex here; the fol-
lowing discussion is mainly to interest you in learning more, See the reference
manual for Lex in Volume 2B of the UNIX Programmer's Manual.
First, here is the Lex program, from the file Lex.2; it replaces the func
tion yylex that we have used so far.
$ cat lex.2
x
#include *hoc.n"
include "[Link]-h*
extern int lineno;
”
we
C\t) (3) /# skip blanks and tabs «/
[0-9] +\.7!(0-9]4\.(0-9}+
‘sscanf(yytext, "%1f", Syylval-val); return NUMBER;
[a-za-2}la-2A-20-9} {
‘symbol +8;
Af ((s=lookup(yytext)) == 0)
‘5 = install(yytext, UNDEF, 0.0);
[Link] =
return s->type == UNDEF ? VAR : s->types )
Ne { Lineno++; return “\n’; ) /+ everything else +/
{ return yytext(o}; }
s
Each “rule” is a regular expression like those in egrep or awk, except tha
Lex recognizes C-style escapes like \t and \n. The action is enclosed it
braces. The rules are attempted in order, and constructs like * and + match a
long a string as possible. If the rule matches the next part of the input, thi
action is performed. The input string that matched is accessible in a Le:
string called yytext.
‘The makefile has to be changed to use Lex:CHAPTER PROGRAM DEVELOPMENT 257
$ cat makefile
YELAGS = -4
ORS = hov.o Je:
.9 init.o math.o aymbol.o
hoe3: $085)
ce $(0BJS) -Im ~11 -0 hoc3
hoc.o: hoc.h
lex.0 init. symbol.o: hoe.h y-tab.h
s
Again, make knows how to get from a .1 file to the proper .o; all it needs
from us is the dependency information. (We also have to add the Lex library
=11 to the list searched by ce since the Lex-generated recognizer is not self-
contained.) ‘The output is spectacular and completely automatic:
$ make
yace -d hoc.y
conflicts: 1 shift/reduce
ec -c [Link].e
zm y-tab.c
mv [Link].o hoe.o
lex lex.2
ce -c [Link].c
rm [Link].c
ay [Link].0 lex.o
ec -c init.e
ce -o math.c
ce -¢ symbol.c
ce hoc-0 lex.0 init.o math.o symbol.o -Im -11 -0 hoe3
‘
If a single file is changed, the single command make is enough to make an
up-to-date version:
$ touch Jex.1 Change modified-time of Lex.
$ make
lex lex.1
ec -c [Link].c
zm [Link].e
mv [Link].0 lex.o
ce hoc-0 ex.o init.o math.o symbol.o -11 -Im -o hoc}
s
We debated for quite a while whether to treat Lex as a digression, to be
illustrated briefly and then dropped, or as the primary tool for lexical analysis
fonce the language got complicated. There are arguments on both sides. The258 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER §
main problem with lex (aside from requiring that the user learn yet another
Janguage) is that it tends to be slow to run and to produce bigger and slower
recognizers than the equivalent C versions. It is also somewhat harder to
adapt its input mechanism if one is doing anything unusual, such as error
recovery or even input from files. None of these issues is serious in the con-
text of hoc. The main limitation is space: it takes more pages to describe the
Lex version, so (regretfully) we will revert to C for subsequent lexical
analysis. It is a good exercise to do the Lex versions, however.
Exercise 8-9. Compare the sizes of the two versions of hoc3, Hint: see s4ze(1). 0
8.4 Stage 4: Compilation into a machine
We are heading towards hocS, an interpreter for a language with control
flow. hoed is an intermediate step, providing the same functions as hoc3, but
implemented within the interpreter framework of hoc5. We actually wrote
hhocé this way, since it gives us two programs that should behave identically,
which is valuable for debugging. As the input is parsed, hocd generates code
for a simple computer instead of immediately computing answers. Once the
end of a statement is reached, the generated code is executed (“interpreted”)
to compute the desired result
The simple computer is a stack machine: when an operand is encountered, it
is pushed onto a stack (more precisely, code is generated to push it onto a
stack); most operators operate on items on the top of the stack, For example,
to handle the assignment
xeaey
the following code is generated:
constpush Push a constant onto stack
2 the constant 2
varpush Push symbol table pointer onto stack
y Jor the variable y
eval Evaluate: replace pointer by value
mul Multiply top two items; product replaces them
varpush Push symbol table pointer onto stack
* {Jor the variable x
assign Store value in variable, pop pointer
pop Clear top value from stack
STOP End of instruction sequence
‘When this code is executed, the expression is evaluated and the result is stored
in x, as indicated by the comments. The final pop clears the value off the
stack because it is not needed any longer.
Stack machines usually result in simple interpreters, and ours is no excep-
tion — it’s just an array containing operators and operands, The operators are
the machine instructions; each is a function call with its arguments, if any, fol:
lowing the instruction, Other operands may already be on the stack, as they‘CHAPTER § PROGRAM DEVELOPMENT 259)
were in the example above.
The symbol table code for hoc4 is identical to that for hoc3; the initializa-
tion in init.c and the mathematical functions in math. are the same as
well. The grammar is the same as for hoe3, but the actions are quite dif
ferent. Basically, each action generates machine instructions and any argu-
‘ments that go with them. For example, three items are generated for a VAR in
fan expression: a varpush instruction, the symbol table pointer for the vari-
able, and an eval instruction that will replace the symbol table pointer by its
value when executed. The code for *s’ is just mul, since the operands for that
will already be on the stack.
$ cat hoo.
er
#inelude “hoc.h"
#4efine code2(ct,e2) _code(ct); code(e2)
#4efine code3(ct,02,c3) code(ct); code(e2); code(e3)
”
Kunion (
symbol ‘sym; /s symbol table pointer +/
Inst tinst; /+ machine instruction */
Xtoken NUMBER VAR BLTIN UNDEF
weight “=
wlefe “47 7-7
Kleft "4" 77"
Kieft UNARYMINUS
%rignt ‘7’ /* exponentiation «/
*%
List: /+ nothing +/
List ‘\n’
List asgn ‘\n’ { code2(pop, STOP); return 1; }
List expr ‘\n’ { code2(print, STP); return 1; )
List error ’\n’ ( yyerrok; }
asgn: VAR “=” expr { code3(varpush, (Inst)$1,assign);260 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
expr: NUMBER { code2(constpush, (Inst)$1);
var { code3(varpush, (Inst)s1, eval); }
asgn
BLTIN ‘(expr ‘)’ { codez(bitin, (Inst)$1->[Link]); }
°C expe 1)"
expr ‘+’ expr ( code(adai
‘ )
expr ’-/ expr ( code(sub); }
expr ‘+’ expr ( code(mul); }
expr ‘/' expr ( code(div); }
‘
expr ‘*/ expr { code(power); }
‘2 expr %prec UNARYMINUS ( code(negate); )
wh
7s end of grammar +/
Inst is the data type of a machine instruction (a pointer to a function return-
ing an int), which we will return to shortly. Notice that the arguments to
code are function names, that is, pointers to functions, or other values that
are coerced to function pointers.
We have changed main somewhat. The parser now returns after each
statement or expression; the code that it generated is executed. yyparse
returns zero at end of file
main(arge, argv) 7+ hock +/
char sargvl li
‘
int fpecateh();
progname = argvi0};
init);
set jmp(begin) ;
signal(SIGFPE, fpecatch);
for (initcode(); yyparse(); initcode())
execute (prog);
return 0;
>
The lexical analyzer is only a little different. The main change is that
‘numbers have to be preserved, not used immediately. The easiest way t0 do
this is to install them in the symbol table along with the variables. Here is the
changed part of yylex:‘CHAPTER PROGRAM DEVELOPMENT 261
yylext) /+ noc +/
Af (cme '.7 tf isaigiticy) (| /* number «/
‘double aj
ungete(c, stdin);
scant("%1E", 8d);
[Link] = install(", NUMBER, 4);
return NUMBER;
Each element on the interpreter stack is either a floating point value or a
pointer to a symbol table entry; the stack data type is a union of these. The
machine itself is an array of pointers that point either to routines like mul that
perform an operation, or to data in the symbol table. ‘The header file hoc.
has to be augmented to include these data structures and function declarations
for the interpreter, so they will be known where necessary throughout the pro-
gram. (By the way, we chose to put all this information in one file instead of
two. In a larger program, it might be better to divide the header information
into several files so that each is included only where really needed.)
$ cat hoc.h
typedef struct Symbol { /+ symbol table entry */
char «name;
short type; / VAR, BLTIN, UNDEF +/
union (
double val 7s 36 VAR +/
double («ptr)(); 7s is BLTIN +/
dus
struct Symbol ‘next; /+ to link to another +/
) symbol:
Symbol tinstall(), +lookup();
typedef union Datun { /+ interpreter stack type */
double vali
Symbol +sym;
) Datum
extern Datum pop);
typedef int (+Inst)();/* machine instruction */
faefine stoP (Inst) 0
extern Inst progi};
extern eval{), add(), sub(), mul(), div(), negate), power()
extern assign(), bltin(), varpush(), constpusn(), print();
‘
‘The routines that execute the machine instructions and manipulate the stack
are kept in a new file called code.c. Since it is about 150 lines long, we will262 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
show it in pieces,
$ cat code.c
#include "hoch"
#include "[Link].n"
faefine NSTACK 256
static Datum stack{NSTACK]; /+ the stack +/
static Datum stackp; 7+ next free spot on stack +/
#aefine NPROG 2000
Inst prog(NPROG]; /* the machine */
Inst sprogpi 7+ next free spot for code generation +/
Inst +pes, /+ program counter during execution +/
initcode() /* initialize for code generation +/
t
stackp = stack;
progp = prog:
>
The stack is manipulated by calls to push and pop:
push(4) /+ push d onto stack */
Datum 4;
‘
Af (stackp >= katack(NSTACK])
execerror("stack overflow", (char +) 0);
sstackpte = dy
)
Datum pop() /* pop and return top elem from stack +/
t
Af (stackp <= stack)
execerror("stack underflow", (char «) 0);
return +
stackp;
,
The machine is generated during parsing by calls to the function code,
which simply puts an instruction into the next free spot in the array prog. It
returns the location of the instruction (which is not used in hoc4).CHAPTER PROGRAM DEVELOPMENT 263
Inst +code(f) _/+ install one instruction or operand +/
Inst £5
a
Inst soprogp = progp;
if (progp >= EprogiNPROG]}
execerror("program too big", (char +) 0);
sprogptt = ft
return oprogp;
)
Execution of the machine is simple; in fact, it’s rather neat how small the
routine is that “runs” the machine once it’s set up:
execute(p) /+ von the machine «/
Inst *pi
‘
for (pe = pi spe I= STOP; }
CeGpere)) O05
,
Each cycle executes the function pointed to by the instruction pointed to by the
program counter pe, and increments pe so it’s ready for the next instruction.
An instruction with opcode STOP terminates the loop. Some instructions, such
as constpush and varpush, also increment pe to step over any arguments
that follow the instruction,
constpush() /# push constant onto stack +/
‘
Datum 4;
[Link] = ((Symbol *)epo++)->[Link]
push(a);
>
varpush() /+ push variable onto stack */
{
Datum 4;
sym = (Symbol +) («pe++);
push(a);
y
‘The rest of the machine is easy. For instance, the arithmetic operations are
all basically the same, and were created by editing a single prototype. Here is
ada:264 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER §
aaa)
>
7 add top two elems on stack */
Datum 41, 425
42 = popt)
at = pop()
[Link] += [Link]
push(at
‘The remaining routines are equally simple.
evan)
‘
)
assign()
(
,
print()
‘
}
bitin’)
¢
»
‘The hardest part
/+ evaluate variable on stack */
patum 4;
@ = popt):
Lf ([Link]->type == UNDEF)
execerror("undefined variable", é.syn->name);
é.val = [Link]->[Link];
push(a);
7+ assign top value to next value +/
Datum 41, 425
a1 = ppt)
42 = pop);
42 ([Link]->type I= VAR 68 [Link]->type = UNDEF)
execerror("assignnent to non-variable",
1. sym->name) ;
[Link] = [Link]}
[Link]->type = VAR;
push(d2);
7+ pop top value from stack, print it +/
patum 4;
= popl
prints("\t%.8g\n", diva):
/+ evaluate built-in on top of stack +/
Datum 4;
a = popt
[Link] = (4(double (+)()) (spots) )(.val) s
push(a);
is the cast in bltin, which says that #pc should be cast to
“pointer to function returning a double,” and that function executed with
val as argument.
‘The diagnostics in eval and assign should never occur if everything is‘CHAPTER § PROGRAM DEVELOPMENT 265
working properly; we left them in in case some program error causes the stack
to be curdied, The overhead in time and space is small compared to the bene-
fit of detecting the error if we make a careless change in the program. (We
did, several times.)
C's ability to manipulate pointers to functions leads to compact and efficient
code. An alternative, to make the operators constants and combine the seman-
tic functions into a big switch statement in execute, is straightforward and
is left as an exercise.
A third digression on make
As the source code for hoc grows, it becomes more and more valuable to
keep track mechanically of what has changed and what depends on that. The
beauty of make is that it automates jobs that we would otherwise do by hand
(and get wrong sometimes) or by creating a specialized shell file
We have made two improvements to the makefile. The first is based on
the observation that although several files depend on the yace-defined con-
stants in [Link].b, there's no need to recompile them unless the constants,
change — changes to the C code in hoc.y don’t affect anything else. In the
new makefile the .o files depend on a new file [Link]-h that is updated
only when the contents of [Link]-h change. The second improvement is to
make the rule for pr (printing the source files) depend on the source files, so
that only changed files are printed.
‘The first of these changes is a great time-saver for larger programs when
the grammar is static but the semantics are not (the usual situation). The
second change is a great paper-saver
Here is the new makefile for hoca:
YFLAGS = -€
OBIS = hoc.o code.o init.o math.o aynbol.o
nocd: #(0BIS)
cc $(OBJS) -Im -0 hood
hoc.0 code.o init.o symbol.o: hec.h
code.o init.o symbol.o: [Link]-h
[Link]: [Link]-n
-emp ~S [Link].h [Link].h I! ep [Link].h [Link]-h
PE: hov.y hoe-h code.c init.c math.c eymbol.c
pr 8?
@touch pr
clean:
em -£ $(0BJS) [xy]. tab. [oh]266 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
‘The ‘~' before cmp tells make to carry on even if the cmp fails; this permits
the process to work even if [Link].h doesn’t exist. (The ~s option causes
mp to produce no output but set the exit status.) The symbol $? expands into
the list of items from the rule that are not up to date. Regrettably, make’s
notational conventions are at best loosely related to those of the shell
To illustrate how these operate, suppose that everything is up to date.
Then’
$ touch hoe.y Change date of noc-y
‘$ make
yace ~4 hoc.y
conflicts: 1 shift/reduce
ce -c [Link].c
xm [Link].e
nv [Link]-o hoc.o
comp -s x-tab.h [Link].h 1! ep [Link].n [Link].h
cc hoc.0 code.o init.o math.o symbol.o -1m -o hocd
8 make -n pr Print changed files
PE hoc.y
touch pr
s
Notice that nothing was recompiled except hoc.y, because the [Link].h file
was the same as the previous one.
Exercise 8-10. Make the sizes of stack and prog dynamic, so that hoc never runs
‘out of space if memory can be obtained by calling malloc.
Exercise 8-11. Modify hocd to use a switch on the type of operation in execute
instead of calling functions. How do the versions compare in lines of source code and
‘execution speed? How are they likely to compare in ease of maintenance and growth?
8.5 Stage 5: Control flow and relational operators
This version, hocS, derives the benefit of the effort we put into making an
interpreter. It provides if-else and while statements like those in C, state-
ment grouping with { and }, and a print statement. A full set of relational
operators is included (>, >=, etc.), as are the AND and OR operators && and
1. (These last two do not guarantee the left-to-right evaluation that is such
an asset in C; they evaluate both conditions even if itis not necessary.)
‘The grammar has been augmented with tokens, non-terminals, and produc-
tions for i£, while, braces, and the relational operators. This makes it quite
a bit longer, but (except possibly for the if and white) not much more com-
plicatedCHAPTER &
$ cat hoc.y
x
#include
faefine
define
»
union {
)
xtoken
xtype
wright
mere
mere
mete
mest
meet
meee
Height
*%
List
asgn:
stmt:
cond:
waite:
PROGRAM DEVELOPMENT 267
snoc-n"
codez(ct,e2) code(c1); code(e2)
code3(c1,02,c3) code(c1); code(e2); code(e3)
symbol ‘sym; /+ symbol table pointer +/
Inet tint; /+ machine instruction */
NUMBER PRINT VAR BLTIN UNDEF WHILE IP ELSE
stmt asgn expr stmtlist cond while if end
oR
Gr GE LP LE ONE
fae
UNARYMINUS NOT
7+ nothing +/
blise “\n"
{list asgn ‘\n’ { codea(pop, STOP); return 1; )
1 list stmt ‘\n’ { code(stop); return 1; }
[list expr ’\n’ { code2(print, STOP); retuen 1; }
f lise error ‘\n’ ( yyerrok;
VAR ‘=’ expr ( $8583; code3(varpush, (znst)$1,assign);
exer { code(pop); }
} PRINT expr { code(prexpr); $$ = $2;
f while cond stmt end {
($1)01] = (Inst)$3; 7 body of loop */
($1)[2] = (Inst)$4; } 7+ end, Lf cond fails +/
{Af cond stmt end ( /+ else-lese if +/
(SDC) = (Inst)$3; 7+ thenpart +/
($1)(3) = (Inst)$4; } 7+ end, if cond faits +/
(S01) = (Inst)$3; 7+ thenpart +/
(s1)(2) © Gases 7+ elsepart +/
($1131 = Gnst)$7; ) 7+ end, if cond faite +/
FU eemelise 7)” ($s = 825)
“U expr “)’ ( code(stop); $$ = $2; }
WHILE { $$ = code3(whilecode, STOP, STOP); }
1 if cond stmt ené ELSE stmt end ( /+ if with else +/
>268 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
if: IF ( S8=code(itcode); code3(stoP, STOP, STOP); }
end: /+ nothing +/ { code( stor); $$ = progpi }
atmtlist! /+ nothing «/ {88 = progp; }
semtlist ‘\n’
semtlist seme
expr: | NUMBER { $$ = codea(constpush, (rnst)$1); }
1 vaR { $8 = code3(varpush, (Inst)$1, eval); }
1 asgn
BUTIN “(/ expr ‘)’
($8 = $3; code2(bitin, (inst) $1->u. ptr!
°C expe)’ (88 = $25)
expr ‘+’ expr ( code(add); )
expr ’-’ expr { code(sub); }
expr ‘+’ expr { code(mul); }
expr ‘/* expr { code(aiv); }
{ code (power); }
=" expr prec UNARYMINUS { $$ = $2; code(negate); }
expr GT expr ( code(gt);
expr GE expr { code(ge);
{
t
‘
‘
‘
expr ‘*/ expr
expr LE expr ( code(1e);
expr EQ expr
expr NE expr
expr AND expr
expr OR expr
NOT expr
code(eq)
code(ne)
code(an); }
code(or); }
$$ = $2; code(not); }
d
)
expr LT expr { code(1t); }
)
)
)
xx
The grammar has five shiftireduce conflicts, all like the one mentioned in
hoe3.
Notice that STOP instructions are now generated in several places to ter-
minate a sequence; as before, progp is the location of the next instruction that
will be generated. When executed these STOP instructions will terminate the
loop in execute. The production for end is in effect a subroutine, called
from several places, that generates a STOP and returns the location of the
instruction that follows it
‘The code generated for while and if needs particular study. When the
keyword while is encountered, the operation whilecode is generated, and
its position in the machine is returned as the value of the production
while: WHILE
At the same time, however, the two following positions in the machine are also
reserved, to be filled in later. ‘The next code generated is the expression that
makes up the condition part of the while. The value returned by cond is theCHAPTER & PROGRAM DEVELOPMENT 269
beginning of the code for the condition. After the whole while statement has
been recognized, the two extra positions reserved after the whilecode
instruction are filled with the locations of the loop body and the statement that
follows the loop. (Code for that statement will be generated next.)
| while cond stmt end (
(80011 = Ginst)s: /+ body of loop +/
($1)(2] = (Inst)s4; ) 7+ end, if cond fails +/
$1 is the location in the machine at which whilecode is stored; therefore,
($1)(4} and ($1)(2) are the next two positions.
A picture might make this clearer:
“srr —]
Body
‘SOP
The situation for an if is similar, except that three spots are reserved, for
the then and else parts and the statement that follows the ig. We will
return shortly to how this operates
Lexical analysis is somewhat longer this time, mainly to pick up the addi-
tional operators:20
THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
yylex() 7 noes +/
awiten Ce) [
case ">": return follow(’*’, GE, G7);
case return follow(’*’, LE, LT
case return follow(’2’, BQ, ‘=’)
case return follow(’=", NE, NOT);
case return follow('!’, oR, 117);
case return follow(’6") AND, ‘67;
case Linenose; return ‘\n’5
default: return ¢;
>
foliow looks ahead one character, and puts it back on the input with ungete
if it was not what was expected.
follow(expect, ifyes, ifno) /+ look ahead for >=, ete. +/
(
int ¢ = getchar();
Lf (c == expect)
return ifyea:
ungetc(c, stdin!
return ifno;
,
There are more function declarations in hoc. — all of the relationals, for
instance — but it’s otherwise the same idea as in hoc4, Here are the last few
$ cat hoc.b
typedef int (#Inst)(); /* machine instruction +/
fdefine sToP (Inst) 0
extern Inst progl], sprogp, #code();
extern eval(), add(), sub(), mul(), div(), negate(), power);
extern assign()
bitin(), varpush(}, constpush(), print()s
extern prexpr();
extern gt), 1t(), eg(), ge(), 1eC}, me(), and(), OFC), nob()s
extern ifcode(), whilecode();
Most of codec is the same too, although there are a lot of obvious new rou-
tines to handle the relational operators. The function 1e (“less than or equal
to") is a typical example:CHAPTER & PROGRAM DEVELOPMENT 271
re)
Datum 41, 42:
82 = popt)
at = pop);
[Link] » (double) (é[Link] <= [Link]);
push(at);
>
The two routines that are not obvious are whilecode and ifcode. The
critical point for understanding them is to realize that execute marches along
‘a sequence of instructions until it finds a STOP, whereupon it returns. Code
generation during parsing has carefully arranged that a STOP terminates each
Sequence of instructions that should be handled by a single call of execute
‘The body of a while, and the condition, then and else parts of an if are
all handled by recursive calls to execute that return to the parent level when
they have finished their task. The control of these recursive tasks is done by
code in whilecode and ifcode that corresponds directly to while and if
statements.
whilecode()
(
patun aj
Inst *savepe = poi 7+ loop body «/
execute(saveper2); 7+ condition +/
= port
while (d-val) (
execute(s((Inst ##)(savepe))); /* body +/
execute (savepe+2);
@ = popt);
,
pe = #((Inst e*)(savepc+t)); /+ next statement #/
y
Recall from our discussion earlier that the wailecode operation is followed
by a pointer to the body of the loop, a pointer to the next statement, and then
the beginning of the condition part. When whilecode is called, pe has
already been incremented, so it points to the loop body pointer. Thus pe+1
points to the following statement, and pe+2 points to the condition.
code is very similar; in this case, upon entry pe points to the then part,
pert to the else, pe+2 to the next statement, and pe+3 is the condition.272 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
Afeode()
‘
Datum a;
Inst *savepe = pe; 7+ then part +/
execute(saveper3) /* condition +/
@ = pops
s€ ([Link])
fexecute(+((Inst #+)(savepe) 1)
else if (#((Inat #4)(savepcr1))) /* else part? +/
execute(+((Inst ++) (savepe+1)})5
pe = #((Inst ++)(savepe+2));/# next stmt «/
»
‘The initialization code in init.c is augmented a little as well, with a table
of keywords that are stored in the symbol table along with everything else:
$ cat init.c
static struct { /* Keywords +/
char sname;
int val;
mr,
ELSE,
WHILE,
"print", PRINT,
°, °,
We also need one more loop in init, to install keywords.
for (4 = 0} keywords[i].name; iss)
install (keywords[i].name, keyworas[i}-kval, 0.0);
No changes are needed in any of the symbol table management; code.c
contains the routine prexpr, which is called when an statement of the form
print expr is executed.
prexpr() /* print numeric value */
c
Datum 4;
@ = popl);
peintf("%.8g\a", [Link])s
>
This is not the print function that is called automatically to print the final
result of an evaluation; that one pops the stack and adds a tab to the output.
hoe5 is by now quite a serviceable calculator, although for serious pro-
gramming, more facilities are needed. The following exercises suggest someCHAPTER # PROGRAM DEVELOPMENT 273
possibilities
Exercise 8-12. Modify hocS to print the machine it generates in a readable form for
debugging. ©
Exercise 8-13. Add the assignment operators of C, such as
‘ment and decrement operators ++ and --. Modify && and 1! so they guarantee left~
to-right evaluation and early termination, as in C. ©
Exercise 8-14. Add a for statement like that of C to hoc5. Add break and
Exercise 8-15. How would you modify the grammar or the lexical analyzer (or both) of
hnoeS 10 make it more forgiving about the placement of newlines? How would you add
semicolon as a synonym for newline? How would you add a comment convention?
What syntax would you use? 0
Exercise 8-16. Add interrupt handling to hoc, so that a runaway computation can be
stopped without losing the state of variables already computed.
#2, ete., and the inere-
Exercise 8-17. It is a nuisance to have to ereate a program in a file, run it, then edt
the file 1 make a trivial change. How would you modify hoc to provide an edit com-
‘mand that would cause you to be placed in an editor with a copy of your hoc program
already read in? Hint: consider a text opcode.
8.6 Stage 6: Functions and procedures; input/output
The final stage in the evolution of hoc, at least for this book, is a major
increase in functionality: the addition of functions and procedures. We have
also added the ability to print character strings as well as numbers, and to read
values from the standard input. noc6 also accepts filename arguments, includ-
ing the name “~” for the standard input. Together, these changes add 235
lines of code, bringing the total to about 810, but in effect convert hoc from a
calculator into a programming language. We won't show every line here;
Appendix 3 is a listing of the entire program so you can sce how the pieces fit
together.
In the grammar, function calls are expressions; procedure calls are state-
ments, Both are explained in detail in Appendix 2, which also has some more
examples. For instance, the definition and use of a procedure for printing all
the Fibonacci numbers less than its argument looks like this:274 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
s cat fib
proc #10) (
aso
bat
while (b < $1) {
print b
cob
b= arb
)
print "\nt
)
§ hocé Fi -
£40( 1000)
112358 19 21.34 55 89 144 233 377 610 987
This also illustrates the use of files: the filename
Here is a factorial function:
* is the standard input.
$ cat fac
fune fact) ¢
4€ ($1 <= 0) return 1 else return $1 * fac($1-1)
-
§ hoc fac -
fac(0)
1
fact?)
5040
fac(10)
3628800
Arguments are referenced within a function or procedure as $1, etc., as in the
shell, but it is legal to assign to them as well. Functions and procedures are
recursive, but only the arguments are local variables; all other variables are
global, that is, accessible throughout the program.
hoe distinguishes functions from procedures because doing so gives a level
of checking that is valuable in a stack implementation. It is too easy to forget
a return or add an extra expression and foul up the stack.
‘There are a fair number of changes to the grammar to convert hocS into
hhoc6, but they are localized. New tokens and non-terminals are needed, and
the Xunion declaration has a new member to hold argument counts:(CHAPTER & PROGRAM DEVELOPMENT 275
$ cat hoc.y
wanion (
symbol 7+ symbol table pointer +/
Inet 7+ wachine instruction */
ant
/* number of arguments */
)
token NUMBER STRING PRINT VAR BLTIN UNDEF WHILE IF ELSE
Xtoken FUNCTION PROCEDURE RETURN FUNC PROC READ
Yeoken ARG
Mtype expr stmt asgn prlist stmtlist
wtype cond while if begin end
xtype —procnane
xtype arglist,
lise! 7+ nothing +/
List ‘\n'
List defn ’\n’
List asgn ‘\n’ ( code2(pop, STOP); return 1; }
List stmt ‘\n’ { code(stoP}; return 1; }
List expr ‘\n’ ( code2(print, STOP); return 1; )
List error ‘\n’ ( yyerrok: }
asgn: VAR ‘=/ expr ( code3(varpush,(Inst)$1,assign); $8283; }
fARG ‘=! expr
{ defnoniy(*s"
code2(argassign, (Inst)$1); $$9§3;)
stmt: expr code(pop)i }
RETURN ( defnonly("zeturn"); code(procret:
RETURN expr
{ defnoniy(*return"); $$=$2; code(funcret); )
1 PROCEDURE begin “(’ arglist ‘)’
{ 88 = $2; code3(cail, (Inst), (inst)s4);
I PRINT priist {$$ = $2; )
?
expr! NUMBER { $$ = code2(constpush, (Inst}$1); }
VAR { $$ = code3(varpush, (Inst)$1, eval); }
ARG { defnonly("$"); $$ = code2(arg, (Inst) $1);
asgn
FUNCTION begin “(’ arglist ’)’
($$ = $2; code3(call,(Inst)$1,(xnst)$4); )
1 READ “(VAR ’)’ { $$ = code2(varread, (Inst)$3); }
begin: /+ nothing +/ ($8
progps }276 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
prlist: expr { code(prexpr); }
STRING ($8 = codeaiprstr, (Iast)$1)s }
prlist ’,/ expr ( code(prexpr); }
prlist ‘,’ STRING — { code2(prstr, (Inst)$3); }
defn: FUNC procname ( $2->type=PUNCTION; indef=1; }
“(CO 1)" stmt { code(procret); define ($2); indef0; }
1 PROC procname { $2->typesPROCEDURE; indefe1; )
“(UO ')" stmt { code(procret); define($2); inde
a
proename: VAR
| eunerzoN
| PROCEDURE
arglict:| /+ nothing «/
| expr
| arglist ",’ expr ‘
1%
The productions for arglist count the arguments. At first sight it might
seem necessary to collect arguments in some way, but it’s not, because each
expr in an argument list leaves its value on the stack exactly where it’s
wanted. Knowing how many are on the stack is all that’s needed
‘The rules for defn introduce a new yace feature, an embedded action. It
is possible to put an action in the middle of a rule so that it will be executed
during the recognition of the rule, We use that feature here to record the fact
that we are in a function or procedure definition. (The alternative is to create
‘4 new symbol analogous to begin, to be recognized at the proper time.) The
function defnonly prints a warning message if a construct occurs outside of
the definition of a function or procedure when it shouldn't, There is often a
choice of whether to detect errors syntactically or semantically; we faced one
earlier in handling undefined variables. The defnonly function is a good
example of a place where the semantic check is easier than the syntactic one.
defnonly(s) _/+ warn if illegal definition «/
char +8;
c
Af (Linde)
execerror(s, "used outside definition");
)
The variable indeg is declared in hoc.y, and set by the actions for defn.
The lexical analyzer is augmented by tests for arguments — a $ followed by
number — and for quoted strings. Backslash sequences like \n are inter
preted in strings by a function backs1ash.CHAPTER 6 PROGRAM DEVELOPMENT — 277
yylex() 7+ hoes */
if (ec
+87) ( 7» azgument? +/
int n= 0;
while (isdigit(cegete(fin)))
n= Went e- 0%
ungetc(e, fin);
Af (n == 0)
execerror("strange §...", (char +)0)5
yylval-narg = 15
4€ (eo “) ( /» quoted string +/
char sbuf[ 100], *p, semalloc(};
for (p = sbuf; (csgete(fin)) |
‘
4B (eee "\n? Ht EOF)
execerror ("missing quote”, "");
4€ (p >= sbuf + sizeot(sbaf) - 1) (
sp = ‘\0"
execerror("string too long", sbuf)
D
sp = backslash(e);
)
sp = 0
[Link] = (Symbol +)emalloc(strlen(sbuf)+1);
stropy([Link], sbuf);
return STRING;
backslash(e) /+ get next char with \'s interpreted +/
inte:
‘
char sindex(); /» ‘strebr()/ in some systems +/
static char transtabl] = "b\bf\fn\nr\rt\t";
de (o Im)
c = gete(fin);
Af (Aslower(e) && index(tzanstab, ¢))
return index(transtab, €)(1];
return ¢;
,
A Texical analyzer is an example of a finite state machine, whether written in C
or with a program generator like Lex. Our ad hoc C version has grown fairly
complicated; for anything beyond this, 1ex is probably better, both in size of
source code and ease of change.
Most of the other changes are in codec, with some additions of function
names {0 hoc.h. The machine is the same as before, except that it has been278 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
augmented with a second stack to keep track of nested function and procedure
calls. (A second stack is easier than piling more things into the existing one.)
Here is the beginning of code. c
$ cat code.c
#define NPROG 2000
Inst prog[NPROG]; /+ the machine */
Inst *progpt 71 next free spot for code generation «/
Inst «pe; 7» program counter during execution /
Inst *progbase = prog; /+ start of current subprogram */
int returning; 7+ 1 Af return stmt seen +/
typedef struct Frame ( /s proc/fune call stack frame +/
symbol sp; /s symbol table entry */
Inet sretpe; /+ where to reaune after return «/
Datum sargn; | /+ n-th argument on stack #/
int nargs; /+ number of arguments +/
) Frame;
#aefine NFRAME 100
Frame frane{NPRAME);
Frame +£p; /* frame pointer +/
initeode() {
progp = progbase;
stackp = stack;
fp = frame;
returning =
Since the symbol table now holds pointers to procedures and functions, and
to strings for printing, an addition is made to the union type in hoc -h:
$ cat hoo-h
typedef struct symbol { /+ symbol table entry «/
char sname;
short types
union {
@oubie vals 7s VAR 47
double («ptr)() 7s BUTIN «/
int (edeen) 5 ‘7+ FUNCTION, PROCEDURE */
char sete 7+ STRING +7
yu
struct Symbol snext; /+ to link to another +/
> symbol
’
During compilation, a function is entered into the symbol table by define,
which stores its origin in the table and updates the next free location after theCHAPTER & PROGRAM DEVELOPMENT 279
‘generated code if the compilation is successful.
define(sp) /* pat func/proc in symbol table +/
Symbol *sp;
c
sp->[Link] = (Inst)progbase; /+ start of code +/
progbase = progp: 74 next code starts here */
>
When a function or procedure is called during execution, any arguments
have already been computed and pushed onto the stack (the first argument is
the deepest). The opcode for call is followed by the symbol table pointer
and the number of arguments. A Frame is stacked that contains all the
interesting information about the routine — its entry in the symbol table,
where to return after the call, where the arguments are on the expression
stack, and the number of arguments that it was called with. The frame is
created by call, which then executes the code of the routine,
cant) /s call a function «/
«
(symbol +)pc{0]; /+ symbol table entry +/
7+ for function */
&frame[NFRAME-1])
execerror(sp->name, “call nested too deeply")
fp->ep = api
fp-onarge = (int)pel 1];
fp->retpe = pe + 2;
fp->argn = stackp ~
execute (sp->u. defn)
returning = 0;
/* last argument +/
,
This structure is illustrated in Figure 8.2.
Eventually the called routine will return by executing either a procret. or
a £uncret:
funeret() 7+ return from a function +/
‘
Datum a;
Af (£p->sp->type == PROCEDURE)
execerror(fp->sp->name, "(proc) returns value");
a= popt); /* preserve function return value +/
ret)
push(a)s280 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
Machine Frame Stack
L- stackp
eal
po-of_+sym args ara?
args Fetpe argi
=D
‘Symbol
Table
Entry
Figure 8.2: Data structures for procedure call
procret() /+ return from a procedure +/
t
Af (£p->ep->type == FUNCTION)
execerror( fp->sp->name,
“(fune) returns no value");
ret):
>
The function ret pops the arguments off the stack, restores the frame pointer
Ep, and sets the program counter.
ret) 7+ common return from funo or proc #/
{
int iy
for (4 = 0; 4 < Ep-snargs: i++)
opt}; /* pop arguments +/
pe = (Inst #)fp->retpe;
£55
returning = 1;
)
Several of the interpreter routines need minor fiddling to handle the situa-
tion when a return occurs in a nested statement. This is done inclegantly but
adequately by a flag called returning, which is true when a return state-
‘ment has been seen, ifcode, whilecode and execute terminate early if
returning is set; call resets it to zero.‘CHAPTER & PROGRAM DEVELOPMENT 281
Lfcode()
t
Datum 4;
Inst *savepe © pes 7s then part +/
execute(saveper3); 7» condition +/
@ = popt)s
af (@.va3)
execute(«((Inst ++) (savepe)));
else if (#( (Inst #+)(savepc+1))) /* else part? +/
execute(+((Inst ++) (savepe+1)));
4€ (1returning)
pe = *((Inst +4) (saveper2)); /+ next stmt +/
>
whitecode()
c
patun 4;
Inst +savepe = pes
execute (savepe+2); /+ condition +/
@ = popl);
while ([Link]) {
execute(*((Inst +#)(savepe))); /+ body +/
A€ (xeturning)
break;
execute(eavepe+2); 7+ condition +/
a= popl);
,
if (Ireturning)
pe = #((Inst +) (saveper)); /# next stmt +/
)
execute(p)
inst «pi
‘
for (pe = pj *pe I= STOP §5 Ireturning:
(lepers) OF
)
Arguments are fetched for use or assignment by getarg, which does the
correct arithmetic on the stack
double +getarg() /* return pointer to argument */
‘
Ant nares = (int) #pesss
Af (narge > £p->nargs)
execerror(fp->sp->name, "not enough arguments");
return Gfp->argn{nargs - £p->nargs].val;282 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
arg() /* push argument onto stack +/
{
patum 4;
@.val = *getarg(
pash(a);
7» store top of stack in argument +/
patum 4;
@ = popt;
push(a); 7+ leave value on stack «/
sgetarg() = [Link];
)
Printing of strings and numbers
is done by pestr and prexpr.
pretr() /» print string value +/
c
printé("%s", (char #) *per+);
>
prexpr() /* print numeric value +/
patum aj
@ = port);
print ("%.6g
+ diva);
>
‘Variables are read by a function called varread. It returns 0 if end of file
occurs; otherwise it returns 1 and sets the specified variable.‘CHAPTER § PROGRAM DEVELOPMENT 283
varread() /+ wead into variable +*/
‘
Datum a;
extern PILE «fin;
Symbol tvar = (Symbol *) «pees;
again:
switch (fecanf(fin, "x1f", Svar->[Link])) {
Lf (moreinput ())
goto Again;
[Link] = var->[Link] = 0.0;
break;
case 0:
execerror("non-nunber read into", var->name
breaks
default:
aval = 1.05
breaks
,
var-stype = VAR:
push(4);
>
If end of file occurs on the current input file, varread calls moreinput,
which opens the next argument file if there is one. moreinput reveals more
about input processing than is appropriate here; full details are given in Appen-
dix 3.
This brings us to the end of our development of hoc. For comparison pur-
poses, here is the number of non-blank lines in each version:
noe! 59
hoc2 94
noc} 248 (Lex version 229)
nocd 396
hoes 574
hocé 809
Of course the counts were computed by programs
$ sed “/"$/a" ‘pick + [ehyl]* f we -1
‘The language is by no means finished, at least in the sense that it’s still easy to
think of useful extensions, but we will go no further here. The following exer-
cises suggest some of the enhancements that are likely to be of value
Exercise 8-18. Modify hoc6 to permit named formal parameters in subroutines as an
alternative to #1, etc. 0
Bxercise 8-19. As it stands, all variables are global except for parameters. Most of the
mechanism for adding local variables maintained on the stack is already present. One
approach is to have an auto declaration that makes space on the stack for variables284 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER &
listed; variables not so named are assumed to be global. The symbol table will also
have to be extended, so that a search is made first for locals, then for globals. How
does this interact with named arguments?
Exercise 8-20. How would you add arrays to hoe? How should they be passed to fune.
tions and procedures? How are they returned? 0
Exercise 8-21. Generalize string handling, so that variables can hold strings instead of
numbers. What operators are needed? The hard part of this is storage management:
making sure that strings are stored in such a way that they are freed when they ure not
needed, s0 that storage does not leak away. As an interim step, add better facilities for
output formatting, for example, access to some form of the C print statement. ©
8.7 Performance evaluation
We compared hoc to some of the other UNIX calculator programs, to get a
rough idea of how well it works. The table below should be taken with a grain
of salt, but it does indicate that our implementation is reasonable. All times
are in seconds of user time on a PDP-11/70. There were two tasks. The first is
computing Ackermann’s function ack(3,3). This is a good test of the
function-call mechanism; it requires 2432 calls, some nested quite deeply.
fune ack() {
Af (41 == 0) return $241
if ($2 22 0) return ack($1-1, 1)
return ack($1-1, ack(#1, $2-1))
y
ack(3,3)
‘The second test is computing the Fibonacci numbers with values less than 1000
a total of one hundred times; this involves mostly arithmetic with an occasional
function call
proc £4b() {
aso
bed
while (b < $1) {
>
asp
>
)
ied
wale (4 < 100) (
#£46( 1000)
deied
)
‘The four languages were hoc, be(1), bas (an ancient BASIC dialect that
only runs on the PDP-I1), and C (using double's for all variables)
‘The numbers in Table 8.1 are the sum of the user and system CPU time asCHAPTER & PROGRAM DEVELOPMENT 285
Table 8.1: Seconds of user time (PDP-11/70)
program ack(3,3) 100% £ib( 1000)
whoc. 35 5.0
bas 13 07
be 39.7 149
c <0. <0.1
measured by time. It is also possible to instrument a C program to determine
how much of that time each function uses. The program must be recompiled
with profiling turned on, by adding the option ~p to each C compilation and
load. If we modify the makefile to read
nooé: $(0BIS)
ce S(CFLAGS) $(0BJS) ~im -o hocé
so that the ce command uses the variable CFLAGS, and then say
$ make clean; make CFLAGS=-p
the resulting program will contain the profiling code. When the program runs,
it will leave a file called [Link] of data that is interpreted by the program
prof,
To illustrate these notions briefly, we made a test on hoc6 with the
Fibonacci program above.
$ hocé 0) prints "refer |"
if (pie > 0) printf "pic f
A€ (ideal > 0) prints "ideal I *
Ae (tpl > 0) prints “epi f *
if (eqn > 0) printf “eqn ! *
printf "troft *
if (ma > 0) printé "-me"
printé "\n"
c7
’
(The -h option to egrep causes it to suppress the filename headers on each
line; unfortunately this option is not in all versions of the system.) The input
is scanned, collecting information about what kinds of components are used.
After all the input has been examined, it’s processed in the right order to print
the output, The details are specific to formatting trof£ documents with the
standard preprocessors, but the idea is general: let the machine take care of the
details,
doctype is an example, like bundle, of a program that creates a pro-
gram. As it is written, however, it requires the user to retype the line to the
shell; one of the exercises is to fix that
When it comes to running the actual trof# command, you should bear in
mind that the behavior of trofé is system-dependent: at some installations it
drives the typesetter directly, while on other systems it produces information
on its standard output that must be sent (0 the typesetter by a separate pro-
gram
By the way, the first version of this program didn't use egxep or sort;
awk itself scanned all the input. It turned out to be too slow for large docu-
ments, so we added egrep to do a fast search, and then soxt -u to toss out
duplicates. For typical documents, the overhead of creating two extra
processes to winnow the data is less than that of running awk on a lot of input.
To illustrate, here is a comparison between doctype and a version that just
runs awk, applied to the contents of this chapter (about 52000 characters):308 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER 9
$ time awk ".. doctype without egrep ...’ ch9.#
eat ch9.1 ch9.2 ch9.3 ch9.4 {pic | tbl ! eqn | troff -ms
real a
user 8
sys 2.
S time doctype ch9.+
eat ch9.1 ch9.2 ch9.3 ch9.4 { pic ! thi | eqn | troft
real 7.0
user 10
sys 2.3
s
‘The comparison is evidently in favor of the version using three processes.
(This was done on a machine with only one user; the ratio of real times would
favor the egrep version even more on a heavily loaded system.) Notice that
we did get a simple working version first, before we started to optimize.
Exercise 9-2. How did we format this chapter?
Exercise 9-3. If your eqn delimiter is a dollar sign, how do you get a dollar sign in the
‘output? Hint: investigate quotes and the pre-defined words of eqn. ©
Exercise 9-4, Why doesn’t
$ ‘doctype filenames
work? Modify doctype to run the resulting command, instead of printing it.
Exercise 9-5. Is the overhead of the extra cat in doctype important? Rewrite
doctype to avoid the extra process. Which version is simpler? ©
Exercise 9.6. Is it better to use doctype or to write a shel file containing the com-
mands to format a specific document? ©
Exercise 9-7. Experiment with various combinations of grep, egrep, farep, sed,
awk and sort to create the fastest possible version of doctype. ©
9.4 The manual page
The main documentation for a command is usually the manual page — a
one-page description in the Unix Programmer's Manual. (See Figure 9.2.) The
manual page is stored in a standard directory, usually /usr/man, in a sub-
directory numbered according (0 the section of the manual. Our hoc manual
page, for example, because it describes a user command, is kept in
Zusr/man/man1/hoe. 1
Manual pages are printed with the man(1) command, a shell file that runs
nroff -man, so man hoc prints the hoc manual. If the same name appears
in more than one section, as does man itself (Section 1 describes the command,
While Section 7 describes the macros), the section can be specified to man:CHAPTER 9 DOCUMENT PREPARATION 309
$ man 7 man
prints only the description of the macros. The default action is to print all
ages with the specified name, using nroff, but man -t generates typeset
pages using trofé
‘The author of a manual page creates a file in the proper subdirectory of
/osr/man. The man command calls nrof# or trof# with a macro package
to print the page, as we can see by searching the man command for formatter,
invocations. Our result would be
$ grep roff ‘which man‘
nroff $opt -man Sall 3
neqn fall ! nroff $opt -man
trofé $opt man all 3,
troff -t Sopt -man Sail ! te
eqn Sall | trofs Sopt -man
eqn Sall | trofe -t Sopt -man | te ii
‘The variety is to deal with options: neoff vs. trof£, whether or not to run
eqn, etc. The manual macros, invoked by troff -man, define troff com-
mands that format in the style of the manual. They are basically the same as
the ms macros, but there are differences, particularly in setting up the title and
in the font change commands. The macros are documented — briefly — in
man(7), but the basics are easy to remember. The layout of a manual page is:
‘TH COMMAND section-number
SH NAME
Command \~ brief description of function
SH SYNOPSIS
13 command
options
SH DESCRIPTION
Detaited explanation of programs and options.
Paragraphs are introduced by PP.
“PP
This is @ new paragraph.
SH FILES
Files used by the command, ¢.g., passwei{) mentions /etc/passwd
SH "SEE ALSO"
References o related documents, including other manual pages
SH DIAGNOSTICS
Description of any unusual output (e.g, see emp))
as(1), Be(1) and de(1),
Bucs
Error recovery is imperfect within function and procedure definitions,
The treatment of newlines is not exactly user-friendly,
8th Edition
Figure 9.2: noc()CHAPTER 9 DOCUMENT PREPARATION 313
9.5 Other document preparation tools
‘There are several other programs to help with document preparation. ‘The
refex(1) command looks up references by keywords and installs in your docu-
‘ment the in-line citations and a reference section at the end. By defining suit-
able macros, you can arrange that refer print references in the particular
style you want. There are existing definitions for a variety of computer science
journals. refer is part of the 7th Edition, but has not been picked up in some
other versions.
pic(1) and ideai(1) do for pictures what eqn does for equations. Pic-
tures are significantly more intricate than equations (at least to typeset), and
there is no oral tradition of how to talk about pictures, so both languages take
some work to learn and to use. To give the flavor of pic, here is a simple
picture and its expression in pic.
Ps.
:pe -1
box invis "document"; arrow
box dashed "pic"; arrow
box dashed “tbi"; arrow
box dashed "eqn"; arrow
box "troff"; arrow
box invis "typesetter*
[ box invis "macro" "package
spline right then up -> ] with .ne at 2nd last box.s
spe st
troft |—etypesetter
package —
The pictures in this book were all done with pic. pic and ideal are not
part of the 7th Edition but are now available.
refer, pic and ideal are all troff preprocessors, There are also pro-
grams to examine and comment on the prose in your documents. The best
Known of these is spe11(1), which reports on possible spelling errors in files;
wwe used it extensively. styie(1) and diction(1) analyze punctuation, gram-
‘mar and language usage. These in turn developed into the Writer's Work-
bench, a set of programs to help improve writing style. The Writer's Work-
bench’ programs are good at identifying cliches, unnecessary words and sexist
phrases.
spell is standard. The others may be on your system; you can easily find
cout by using man:314 THE UNIX PROGRAMMING ENVIRONMENT CHAPTER 9
$ man style diction wb
or by listing /bin and /usr/bin,
History and bibliographic notes
troff, written by the late Joe Ossanna for the Graphics Systems CAT-4
typesetier, has a long lineage, going back to RUNOFF, which was written by J
E. Saltzer for CTSS at MIT in the early 1960's. These programs share the
basic command syntax and ideas, although trot is certainly the most compli
cated and powerful, and the presence of eqn and the other preprocessors adds
significantly to its utility. There are several newer typesetting programs with
more civilized input format; TEX, by Don Knuth (TEX and Metafont: New
Directions in Typesetting, Digital Press, 1979), and Seribe, by Brian Reid
('Scribe: a high-level approach to computer document formatting,” 7th Sympo-
sium on the Principles of Programming Languages, 1980), are probably the
best known. ‘The paper “Document Formatting Systems: Survey, Concepts and
Issues” by Richard Furuta, Jeffrey Scofield, and Alan Shaw (Computing Sur-
veys, September, 1982) is a good survey of the field
‘The original paper on eqn is “A system for typesetting mathematics,”
(CACM, March 1975), by Brian Kernighan and Lorinda Cherry. The ms
‘macro package, tbl and refer are all by Mike Lesk; they are documented
only in the UNA Programmer's Manual, Volume 2A.
pic is described in “PIC — a language for typesetting graphics,” by Brian
Kernighan, Software—Practice and Experience, Januaty, 1982. ideal is
described in “A high-level language for describing pictures,” by Chris Van
Wyk, ACM Transactions on Graphics, April, 1982.
spell is @ command that turned from/a shell file, written by Steve John-
son, into a C program, by Doug Meliroy. The 7th Edition spe uses a hash
ing mechanism for quick lookup, and rules for automatically stripping suffixes
and prefixes to keep the dictionary small. See “Development of a spelling
list,” M, D, Meliroy, IEEE Transactions on Communications, January, 1982.
The style and Aiction programs are described in “Computer aids for
writers,” by Lorinds Cherry, SIGPLAN Symposium on Text Manipulation,
Portland, Oregon (June 1981).cHapter 0: EPILOG
The UNIX operating system is well over ten years old, but the number of
computers running it is growing faster than ever. For a system designed with
‘no marketing goals or even intentions, it has been singularly successful
‘The main reason for its commercial success is probably its portability — the
feature that everything but small parts of the compilers and kernel runs
unchanged on any computer. Manufacturers that run UNIX software on their
machines therefore have comparatively little work to do to get the system run-
ring on new hardware, and can benefit from the expanding commercial market,
for UNIX programs.
But the UNIX system was popular long before it was of commercial signifi-
cance, and even before it ran on anything but the PDP-I1, The 1974 CACM
paper by Ritchie and Thompson generated interest in the academic community,
and by 1975, 6th Edition systems were becoming common in universities
‘Through the mid-1970's UNIX knowledge spread by word of mouth: although
the system came unsupported and without guarantee, the people who used it
were enthusiastic enough to convince others to try it too. Once people tried it,
they tended to stick with it; another reason for its current success is that the
generation of programmers who used academic UNIX systems now expect to
find the UNIX environment where they work.
‘Why did it become popular in the first place? ‘The central factor is that it
‘was designed and built by a small number (two) of exceptionally talented peo-
ple, whose sole purpose was to create an environment that would be convenient
for program development, and who had the freedom to pursue that ideal. Free
of market pressure, the early systems were small enough to be understood by a
single person. John Lions taught the 6th Edition kernel in an undergraduate
operating systems course at the University of New South Wales in Australia
In notes prepared for the class, he wrote, “... the whole documentation is not
unreasonably transportable in a student's briefcase.” (This has been fixed in
recent versions.)
In that carly system were packed a number of inventive applications of
‘computer science, including stream processing (pipes), regular expressions,
language theory (yacc, lex, etc.) and more specific instances like the
ais316 THE UNIX PROGRAMMING ENVIRONMENT ‘CHAPTER 10
algorithm in ai¢¢. Binding itall together was a kernel with “features seldom
found even in larger operating systems.” As an example, consider the UO
structure: a hierarchical filesystem, rare at the time; devices installed as names
inthe file system, so they require no special utilities; and perhaps a dozen criti
cal system calls, such as an open primitive with exactly two arguments. The
software was all written in a high-level language and distributed with the sys-
tem so it could be studied and modified
“The UNIX system has since become one of the computer market's standard
‘operating systems, and with market dominance has come responsibility and the
need for “features” provided by competing systems. As a result, the kernel
has grown in size by a factor of 10 in the past decade, although it has certainly
not improved by the same amount. This growth has been accompanied by a
surfeit of ill-conceived programs that don’t build on the existing environment
Creeping featurism encrusts commands with options that obscure the original
intention of the programs. Because source code is often not distributed with
the system, models of good style are harder come by.
Fortunately, however, even the large versions are still suffused with the
ideas that made the early versions so popular. ‘The principles on which UNIX is
‘based — simplicity of structure, the lack of disproportionate means, building
‘on existing programs rather than recreating, programmability of the command
interpreter, a tree-structured file system, and so on — are therefore spreading
and displacing the ideas in the monolithic systems that preceded it. The UNIX
system can’t last forever, but systems that hope to supersede it will have to
incorporate many ofits fundamental ideas.
We said in the preface that there is a UNIX approach or philosophy, a style
of how to approach a programming task. Looking back over the book, you
should be able to see the elements of that style illustrated in our examples.
First, let the machine do the work. Use programs like grep and we and
awk to mechanize tasks that you might do by hand on other systems.
Second, let other people do the work. Use programs that already exist as
building blocks in your programs, with the shell and the programmable filter
to glue thom together. Write a small program to interface to an existing one
that does the real work, as we did with idi££. The UNIX environment is rich
in tools that can be combined in myriad ways; your job is often just to think of
the right combination
‘Third, do the job in stages. Build the simplest thing that will be useful, and
let your experience with that determine what (if anything) is worth doing next
Don't add features and options until usage patterns tell you which ones are
needed
Fourth, build tools. Write programs that mesh with the existing environ-
ment, enhancing it rather than merely adding to it. Built well, such programs
themselves become a part of everyone's toolkit.
We also said in the preface that the system was not perfect. After nine
chapters describing programs with strange conventions, pointless differences,CHAPTER 10 emoo 317
and arbitrary limitations, you will surely agree. In spite of such blemishes,
however, the positive benefits far outweigh the occasional irritating rough
edges. ‘The UNIX system is really good at what it was designed to do: providing
a comfortable programming environment
So although UNIX has begun to show some signs of middle age, it's still
viable and still gaining in popularity. And that popularity can be traced to the
clear thinking of a few people in 1969, who sketched on the blackboard a
design for a programming environment they would find comfortable
Although they didn’t expect their system to spread to tens of thousands of
computers, a generation of programmers is glad that it didAPPENDIX 1: EDITOR SUMMARY
‘The “standard” UNIX text editor is a program called ed, originally written
by Ken Thompson. ed was designed in the early 1970's, for a computing
environment on tiny machines (the first UNIX system limited user programs to
8K bytes) with hard-copy terminals running at very low speeds (10-15 charac-
ters per second). It was derived from an earlier editor called qed that was
popular at the time.
‘As technology has advanced, ed has remained much the same. You are
almost certain to find on your system other editors with appealing features; of
these, “visual” or “screen” editing, in which the screen of your terminal
reflects your editing changes as you make them, is probably the most common.
So why are we spending time on such a old-fashioned program? The
answer is that ed, in spite of its age, does some things really well. It is avail-
able on all UNIX systems; you can be sure that it will be around as you move
from one system to another. It works well over slow-speed telephone lines and
with any kind of terminal, e@ is also easy to run from a script; most screen
editors assume that they are driving a terminal, and can’t conveniently take
their input from a file.
ed provides regular expressions for pattern matching. Regular expressions
based on those in ed permeate the system: grep and sed use almost identical
ones; egrep, awk and lex extend them; the shell uses a different syntax but
the same ideas for filename matching. Some screen editors have a “line
mode" that reverts to a version of ed so that you can use regular expressions.
Finally, ed runs fast. It’s quite possible to invoke ed, make a one-line
change to a file, write out the new version, and quit, all before a bigger and
fancies screen editor has even started
Basics
ed edits one file at a time. It works on a copy of the file; to record your
changes in the original file, you have to give an explicit command. ed pro-
vides commands to manipulate consecutive lines or lines that match a pattern,
and to make changes within lines.
Each ed command is a single character, usually a letter. Most commands
319320 THE UNIX PROGRAMMING ENVIRONMENT APPENDIX 1
can be preceded by one or two line numbers, which indicate what line or lines
are to be affected by the command; a default line number is used otherwise
Line numbers can be specified by absolute position in the file (1, 2, «J, bY
shorthand like $ for the last line and ‘." for the current line, by pattern
searches using regular expressions, and by additive combinations of these.
Let us review how to create files with ed, using De Morgan’s poem from
Chapter 1
8 ed poem
?poen Warning: the file poem doesn't exist
a Start adding lines
Great fleas have little fleas
upon their backs to bite ‘em,
And Little fleas have lesser fleas,
‘and so ad infinitum.
: Type a *." 10 stop adding
w poe Write lines to file poem
424 (e8 reports [21 characters written
q uit
‘The command a adds or appends lines; the appending mode is terminated
by a line with a *.” by itself. There is no indication of which mode you are in,
80 two common mistakes to watch for are typing text without an a command,
and typing commands before typing the *.”.
4 will never write your text into a file automatically; you have (o tell ito
do so with the w command. If you try to quit without writing your changes,
however, ed prints a ? as a warning. At that point, another q command will
let you exit without writing. @ always quits regardless of changes.
$ ed poem
12 Fle exists, and has 121 characters
a ‘Add some more lines at the end
And the great fleas thenselves, in turn,
have greater fleas to go oni
Wile these again have greater still,
and greater still, and 30 on
Type a *." to stop adding
¢ Try 10 quit
? Warning: you didn’t write first
* No filename given; poem is assumed
263
@ Now it's OK to quit
3 we poem Check for sure
8 46 263 poemAPPENDIX 1 EDITOR SUMMARY 321
Escape to the shell with !
If you are running ed, you can escape temporarily to run another shell
‘command; there’s no need to quit, The ed command to do this is “!":
3 ed poem
263
we poet Run we without leaving 2
@ © 46.263 poem
' You have returned from the command
q (Quit without w is OK: no change was made
’
Printing
The lines of the file are numbered 1, 2, ...; you can print the m-th line by
giving the command mp or just the number n, and lines m through » with
mynp. The “line number” § is the last line, so you don’t have to count lines.
1 Print Ist line; same as 1p
s Print last line: same as 8p
1p Print lines 1 through last
‘You can print a file one line at a time just by pressing RETURN; you can back
up one line at a time with ‘-". Line numbers can be combined with + and
$-2,8p Print last 3 lines
1,203 Print lines 1 through 5
But you can’t print past the end or in reverse order; commands like $,$+1p
and $, tp are illegal
‘The list command 1 prints in a format that makes all characters visible; it's
‘200d for finding control characters in files, for distinguishing blanks from tabs,
and so on. (See vis in Chapter 6.)
Patterns
Once a file becomes longer than a few lines, it’s a bother to have to print it
all (o find a particular line, so e4 provides a way to search for lines that match
1 particular pattern: /pattern/ finds the next occurrence of pattern
$ ed poem
263
fleas Search for next line containing £Lea
Great fleas have little fleas
/tlea/ Search for next ome
And little fleas have lesser fleas,
“v ‘Search for next using same pattern
‘And the great fleas themselves, in turn,
2 Search backwards for same pattern
And Little fleas have lesser fleas,
ed remembers the pattern you used last, so you can repeat a search with just322 THE UNIX PROGRAMMING ENVIRONMENT APPENDIX 1
1/7. To search backwards, use ?pattern? and 22.
‘Searches with /.../ and ?...? “wrap around” at either end of the text
sp Print last tine. (°p' is optional)
‘and greater still, and so on
fleas Next Eea is near beginning
Great fleas have little fleas
?P Wrap around beginning going backwards
have greater fleas to go on:
A pattern search like /£1ea/ is a line number just as 1 oF $ is, and can be
used in the same contexts:
4,/#1ea/p Print from I to next £103
?£lea?+1,sp Print from previous €1¢a +1 1 end
Where are we anyway?
ed keeps track of the last line where you did something: printing or adding
text or reading a file. The name of this line is *.”; it is pronounced “dot” and.
is called the current line. Each command has a defined effect on dot, usually
setting it to the last line affected by the command, You can use dot in the
same way that you use $ or a number like 1
8 ed poem
263
: Print current line: same as $ after reading
and greater still, and so on.
“1p Print previous line and this one
While these again have greater still,
and greater still, and so on.
Line number expressions can be abbreviated:
Shorthand: Same as Shorthand: Same as
: 1 * 4
= or -2 1-2 tor 4242
: so 3 8
Append, change, delete, insert
The append command a adds lines after the specified line; the delete com
mand 4 deletes lines; the insert command 4 inserts lines before the specified
line; the change command ¢ changes lines, a combination of delete and insert.
na Add text after line m
ne Insert text before line n
mand Delete lines m through 1
mine (Change lines m through
If no Line numbers are given, dot is used. ‘The new text for a, ¢ and iAPPENDIX 1 EDITOR SUMMARY 323,
commands is terminated by a *." on a line by itself; dot is left at the last line
added. Dot is set to the next line after the last deleted line, except that it
doesn't go past line $
oa ‘Adal text at beginning (same as 14)
ap. Delete current line, print next (or last, If ar 8)
sap Delete from here to end, print new last
isa Delete everyting
Ppat? 18 Delete from previous ‘pat to just before dot
sap Delete last line, print new last line
se Change last line. ($a adds after last line)
180 Change all lines
Substitution; undo
It's a pain to have to re-type a whole line to change a few letters in it. The
substitute command s is the way to replace one string of letters by another:
s/old/new/ Change first 014 into mew on current line
e/old/new/p Change first 014 into new and print line
e/old/new/g Change each 014 into new on current line
s/old/new/gp Change each 024 into new and print line
Only the leftmost occurrence of the pattern in the Tine is replaced, unless a ‘g”
follows. The command doesn’t print the changed line unless there is a ‘p’ at
the end. In fact, most ed commands do their job silently, but almost any com-
mand can be followed by p to print the result
If a substitution didn’t do what you wanted, the undo command u will undo
the most recent substitution. Dot must be set to the substituted line.
a Undo most recent substitution
up Undo most recent substitution and print
Just as the p and d commands can be preceded by one or two line numbers
to indicate which lines are affected, so can the s command:
Jold/s/old/new/ Find next 014; change to new
7eld/3//new/ Find next 036; change to new
(pattern is remembered)
1,$8/ola/new/p Change first 014 to new on each line:
‘print last line changed
4,$8/ol¢/new/ep Change each 014 10 now on each line:
rin last line changed
Note that 1,$5 applies the s command to each line, but it still means only the
Teftmost match on each line; the trailing °g” is needed to replace all occurrences
in each line. Furthermore, the p prints only the last affected line; to print all
changed lines requires a global command, which we'll get to shortly,
‘The character & is shorthand; if it appears anywhere on the right side of an
s command, it is replaced by whatever was matched on the left side:324 THE UNIX PROGRAMMING ENVIRONMENT APPENDIX 1
s/big/very &/ Replace big by very big
a/big/5 &/ Replace big by big big
8/4/18) Parenuhesize entre line (see .* below)
a/and/\5/ Replace ana by & (\ turns off special meaning)
Metacharacters and regular expressions
In the same way that characters like * and > and | have special meaning to
the shell, certain characters have special meaning to e& when they appear in a
search pattern or in the left-hand part of an s command. Such characters are
called metacharacters, and the patterns that use them are called regular expres-
sions. Table 1 lists the characters and their meanings; the examples below
should be read in conjunction with the table. ‘The special meaning of any char-
acter can be turned off by preceding it with a backslash.
Table 1: Editor Regular Expressions
© any non-special character c matches itself |
\c turn off any special meaning of character ¢ |
- ‘matches beginning of line when ~ begins pattern |
s ‘matches end of line when $ ends pattern |
: ‘matches any single character |
[J matches any one of characters in ...; ranges like a~2 are legal
[7.1 matches any single character not in ..; ranges are legal
m matches zero or more occurrences of r,
where ris a character, . oF {1
8 oon right side of only, produces what was matched
X(N) tagged regular expression; the matched string
is available as \1, etc., om both left and right side
No regular expression matches a newline.
Pattern Matches:
rss empty line, i.e, newline only
ad non-empty, i-e., at least one character
ey all lines
“ehing/ ‘ching anywhere on line
7oening/ thing ar beginning of line
/ehings/ thing at end of line
7oenings/ line that contains only thing
“ching. 8/ thing plus any character at end of line
Zehing\.8/ ‘thing. at end of line
asening\// Zening/ anywhere on line
7(eryning/ thing or Thing anywhere on line
/ehingl0-91/ thing followed by one digitAPPENDIX 1 EDITOR SUMMARY 325
/ehingl*0-91/ ‘thing followed by a non-digit
‘Yebingl0-9){70-9]/ thing followed by digit, non-digit
Yehing!.*thing2/ thing! then any string then thing?
“thing!
‘thing2$/ thing at beginning and thing2 at end
Regular expressions involving + choose the leftmost match and make it as long
as possible, Note that x* can match zero characters; xx+ matches one or
Global commands
The global commands g and v apply one or more other commands to a set
of lines selected by a regular expression, The g command is most often used
for printing, substituting or deleting a set of lines:
ming/re/omd For all lines beoween m and n that match re, do cmd
mnv/re/omd For all lines beoveen m and n that don’t match re, do emd
The g or v commands can be preceded by line numbers to limit the range; the
default range is 1,8
WolB Prin all tines matching regular expression
esa Delete all lines matching
g/./a//repl/p Replace Ist. on each line by ‘repl’, print changed lines
9/../8//repl/ap Replace each. by‘repl’, print changed lines
9/../8/pat/repl/ On lines matching ... replace Ist ‘pat’ by ‘rept’
97.1 38/pat/repl/p On lines matching... replace Ist ‘pat’ by ‘rep! and print
g/../8/pat/repl/gp On lines matching ... replace all ‘pat’ by ‘rept and print
v/../e/pat/repl/sp On lines not matching .., replace all ‘pat’ by ‘repl', print
wirs/p Prin all non-blank lines
@/..femdI\ To do multiple commands with a single g,
ema append 10 each cmd
comd3 Dut the fast
The commands controlled by a g or v command can also use line numbers.
Dot is set in turn (0 each line selected.
g/thing/...+1p Print each line with thing and next
9/°\.80/.1,/°\.EN/-8/alpha/beta/gp Change alpha to beta only
between £0 and «EX, and print changed lines
Moving and copying lines
The command m moves a contiguous group of lines; the t command makes
a copy of a group of lines somewhere else
mam d Move lines m through m to after line d
mnt d Copy lines m through n to after line d
If no source lines are specified, dot is used. The destination line d cannot be
in the range m, n—1. Here are some common idioms using mand t:326 THE UNIX PROGRAMMING ENVIRONMENT APPENDIX 1
mt Move current line to after next one (interchange)
m2 ‘Move current line to before previous one
m Same: ~~ is the same as 2
Does nothing
ms Move current line 19 end (20 moves to beginning)
of Duplicate current line (€ duplicates at end)
niet Duplicate previous and current lines
rises Duplicate entre set of tines
977700 Reverse order of lines
Marks and line numbers
‘The command = prints the line number of line $ (a poor default), .= prints
the number of the current line, and so on. Dot is unchanged
‘The command ke marks the addressed line with the lower case letter ¢; the
line can subsequently be addressed as “ec. The ke command does not change
dot. Marks are convenient for moving large chunks of text, since they remain
permanently attached to lines, as in this sequence:
aan Find line ... and mark with a
a Find line. and mark with
sabe Print entre range to be sure
ca Find target line
“ay /bm. ‘Move selected lines after it
Joining, splitting and rearranging lines
Lines can be joined with the 3 command (no blanks are added):
mang Join tines m through w into one line
‘The default range is .,.+1, s0
op Join current line to next and print
ap Join previous line to current and print
Lines can be split with the substitute command by quoting a newline:
e/part tpart?/paxt 1\ Split line into ovo parts
part2/
aN Split at each blank:
4s ‘makes one word per line
Dot is left at the last line created,
To talk about parts of the matched regular expression, not just the whole
thing, use tagged regular expressions: if the construction \(...\) appears in a
regular expression, the part of the whole that it matches is available on both
the right hand side and the left as \1. There can be up to nine tagged expres-
sions, referred to as \1, \2, etc.APPENDIX 1 EDITOR SUMMARY 327
B/E NING ANI/\2\17 Move frst 3 characters to end:
AGRI Find lines that contain a repeated adjacent string
File handling commands
‘The read and write commands x and w can be preceded by line numbers:
ax file Read file: add i after tine n; set dor to last tine read
mnie file Write lines mn to file; doris unchanged
mn file Append lines mn io file; dot is unchanged
‘The default range for w and W is the whole file, The default n for x is $, an
unfortunate choice. Beware,
‘ed remembers the first file name used, either from the command line or
from an x or w command. The file command £ prints or changes the name of
the remembered file:
€ Print name of remembered file
£ fle Ser remembered name to file’
‘The edit command e reinitializes ed with the remembered file or with a new
e Begin editing remembered fle
e file Begin editing file
‘The @ command is protected the same way as q is: if you haven't written your
changes, the first e will draw an error message. E reinitializes regardless of
changes. On some systems, ed is linked to e so that the same command
(@ filename) can be used inside and outside the editor.
Encryption
Files may be encrypted upon writing and decrypted upon reading by giving
the x command; a password will be asked for. The encryption is the same as
in crypt(1). The x command has been changed to X (upper case) on some
systems, to make it harder to encrypt unintentionally.
Summary of commands
Table 2 is a summary of e@ commands, and Table 3 lists the valid line
numbers. Each command is preceded by zero, one or two line numbers that
indicate how many line numbers can be provided, and the default values if
they are not. Most commands can be followed by a p to print the last line
affected, or 1 for list format. Dot is normally set to the last line affected; it is
unchanged by £, i, w, x, =, and !
Exercise. When you think you know ed, try the editor quiz; see quiz(6). 0328 THE UNIX PROGRAMMING ENVIRONMENT APPENDIX 1
cd
e file
£ file
1, $9/re/emds
eld
q
sr file
+5 +8/re/new/
cystine
1, $w/re/emds
1,80 file
s=
temdline
Tres
Pre?
Nitn
NIWN2
NIGN2
(#1 )newline
Table 2: Summary of ea Commands
‘add text until a line containing just . is typed
change lines; new text terminated as with a
delete lines,
reinitialize with file. resets even if changes not written
set remembered file to file
do ed emds on each line matching regular expression re;
multiple emds separated by \newline
insert text before line, terminated as with a
join lines into one
mark line with letter ¢
list lines, making invisible characters visible
quit. @ quits even if changes not written
read file
substitute new for whatever matched re
copy lines after line
undo last substitution on line (only one)
do e6 emds on each line not matching re
write lines to file; W appends instead of overwriting
enter encryption mode (or ed -x filename)
print fine number
execute UNIX command cmdline
print line
Table
i; Summary of ed Line Numbers
absolute line number m,n = 0, 1, 2,
‘current line
last line of text
next line matching re; wraps around from $ to 1
previous line matching re; wraps around from 110 $
Tine with mark ¢
line NIn (additive combination)
lines N/ through N2
set dot to NZ, then evaluate N2
NJ and N2 may be specified with any of the aboveApPENDIX2: HOC MANUAL
Hoc - An Interactive Language For Floating Point Arithmetic
Brian Kernighan
Rob Pike
ABSTRACT
Hoc is a simple programmable interpreter for floating point expressions
It has C-style control flow, function definition and the usual numerical
builtin functions such as cosine and logarithm,
1. Expressions
Hoc is an expression language, much like C: although there ae several contrlflow
statements, most statements such as assignments are expressions whose value is disre-
garded. For example, the assignment operator = assigns the value ofits right operand
to is eft operand, and yields the value, so multiple assignments work. The expression
grammar is:
er: runber
| variable
| expr)
| expr binap expr
| amop espr
| fiction ( arguments )
Numbers are floating point. The input format is that recognized by seanf (3): digits,
decimal point, digits, © or E, signed exponent, At least one digit or a decimal point
rust be present; the other components are optional
Variable names are formed from a letter followed by a string of leters and
umbers. binop refers to binary operators such a addition of Togical comparison; wnop
refers 10 the two negation operators, “(logical negation, "not) and *=" (arithmetic
negetion, sign change). Table 1 lists the operators
329320
{THE UNIX PROGRAMMING ENVIRONMENT
Table 1: Operators, in decreasing order of precedence
exponentiation (FORTRAN **)
|. Fight associative
= (unary) logical and arithmetic negation
!
+ 7 multiplication, division
+ = addition, subtraction
> >= relational operators: greater, greater or equal,
< less, less or equal,
equal, not equal (all same precedence)
55 gical AND (both operands always evaluated)
H logical OR (both operands always evaluated)
: assignment, right associative
APPENDIX 2
Functions, as described later, may be defined by the user. Function arguments are
expressions separated by commas
Which take a single argument, described in Table 2.
Table 2: Built-in Functions
abs(x) [x], absolute value of x
atan(x) arc tangent of
cosix) —cos(r), cosine of x
exp(x) —_¢*, exponential of x
Ant(x) integer part of x, truncated towards zer0
Log(x) __log(x), logarithm base ¢ of x
Log10(x) logio(x), logarithm base 10 of x
sin(x) sin(x), sine of x
There are also a number of built-in functions, all of
sart(x) Vr 2
Logical expressions have value 1.0 (true) and 0.0 (false).
As in C, any non-zer0
value is taken to be true. As is always the case with floating point numbers, equality
comparisons are inherently suspect.
Hoc also has a few built-in consta
DEG —_$7.29577951308232087680 180, degrees per radian
z 2.71828182845901523536 _e, base of natural logarithms
GAMMA 0.57721566490153286060 +, Euler-Mascheroni constant
PHT 1,61803398874989484820 (\/54+1)2, the golden ratio
Pr 3.14159265358979923846 my, circular transcendental number
2, Statements and Control Flow
Hoe statements have the following grammar:APPENDIX 2 Hoc MANUAL 331
sit: er
variable = expr
procedure ( arglist)
While ( expr ) stmt
(expr } sme
if (expr ) stmt else stmt
{ sonalist }
rin expr-tist
return optional-expr
stl: (nothing)
! stmlist stmt
‘An assignment is parsed by default as a statement rather than an expression, so assign-
‘ments typed interactively do not print their value
[Note that semicolons are not special to hoc: statements are terminated by newlines.
‘This causes some peculiar behavior. The following are legal if statements:
Af (x © 0) print(y) else print(2)
Af (x <0)
print(y)
} else ¢
print(2)
?
Im the second example, the braces are mandatory: the newline after the if would tor-
‘minate the statement and produce a syntax error were the brace omitted.
‘The syntax and semantics of hoc control flow facilities are basically the same as in
C. The while and if statements are just as in C, except there are no break or continue
3. Input and Output: read and print
‘The input function read, like the other built-ins, takes a single argument. Unlike
the built-ins, though, the argument is not an expression: itis the name of a variable.
‘The next number (as defined above) is read from the standard input and assigned to the
named variable. The return value of read is | (true) if a value was read, and 0 (false)
if read encountered end of file or an error.
‘Output is generated with the print statement. The arguments to print are a comma-
separated list of expressions and strings in double quotes, as in C. Newlines must be
supplied; they are never provided automatically by print
Note that read is a special builtin function, and therefore takes a single
parenthesized argument, while print is a statement that takes a comma-separated,
‘unparenthesizd list:
while (readix)) (
print "value is ", x, "\n"
)332 THE UNIX PROGRAMMING ENVIRONMENT APPENDIX 2
44. Functions and Procedures
Functions and procedures are distinct in hoc, although they are defined by the same
mechanism. This distinction is simply for run-time error checking: it is an error for a
procedure to return a value, and for a function nor to return one,
‘The definition syntax is:
Sanction: ane name() stmt
procedure roc name() stmt
name may be the name of any variable — builtin functions are excluded. The defini.
tion, up to the opening brace or statement, must be on one line, as with the if state
ments above.
Unlike C, the body of a function or procedure may be any statement, not necessarily
1 compound (brace-enclosed) statement. Since semicolons have no meaning in hoc, a
null procedure body is formed by an empty pair of braces
Functions and procedures may take arguments, separated by commas, when
invoked. Arguments are referred to as in the shell: $3 refers to the third (I-indexed)
argument. ‘They are passed by value and within functions are semantically equivalent to
variables. It is an error to refer to an argument numbered greater than the number of
arguments passed to the routine, The error checking is done dynamically, however, so &
routine may have variable numbers of arguments if intial arguments affect the number
‘of arguments to be referenced (us in C's pring).
Functions and procedures may recurse, but the stack has limited depth (about a hun-
‘dred calls). ‘The following shows a hoc definition of Ackermann’s function:
$ hoe
fune ack() {
Lf ($1 22 0) return $2+1
Hf ($2 28 0) return ack($1-1, 1)
return ack(#1-1, ack($1, $2-1))
d
ack(3, 2)
29
ack(3, 3)
61
ack(3, 4)
hoc: stack too deep near line 85. Examples
‘Stirling's formula:
$ hoe
func stirl() (
,
stirl(10)
3620684.7
stiri(20)
2.43288 186418,
Factorial function, n!
fune fact) if ($1
HOC MANUAL 333
1
nt ~ Vinwiner at
return sqrt (208 1*PI) © ($1/B)"$I4(1 + 1/(12681))
0) return 1 elge return $1 + fac($1-1)
Ratio of factorial to Stirling approximation:
while ((i = 441) <= 20) (
10
n
2
3
4
6
16
v7
18
»
20
print i,
0000318
0000265
0000224
0000192,
‘0000166
:0000146
‘0000128,
Soo00114
‘0000102
‘0000092
‘9000083
*, fac(i)/stir1(1), "Nn"ApPENDIX 3: HOC LISTING
‘The following is a listing of noc6 in its entirety.
35336 THE UNIX PROGRAMMING ENVIRONMENT APPENDIX 3
ee eee Ces prosesAPPENDIC 3 Hoc usta 337
,338 THE UNIX PROGRAMMING ENVIRONMENT
fovtewngac, pee, saa) /+ tack ana for ve esAPPENDIX. Hocustne 3393M0__THE UNIX PROGRAMMING ENVIRONMENT APPENDIX
+ embote
fmt saateiies £4) 7+ ana pot abe o/APPENDIX 3 HocustiNG 341
Fhe ‘enon
ene eects esianveged 5/4 ey 07342 THE UNIX PROGRAMMING ENVIRONMENT APPENDIX 3
fmtot ap = bybst Ipe8 /s stat cane ant o/
ea netted 0 deeriy"itAPPENDIX 3
Hoc usTING
343344 THE UNIX PROGRAMMING ENVIRONMENT
5APPENDIX 3 Wocusrine 345
peletelateg sivas346 THE UNIX FROGRAMMING ENVIRONMENT APPENDIX 3
Veonmeatpe tt
eT aqwarda ate, Meyrorda st
ny ane, WB conete2)¥80)¢APPENDIX 3 Hoc using 347
oe‘and seas 130
ouput 29
ME command: eroee 29, 208
‘Stet dor 21 25,37,
Se
eigen 8
Tepe ii 9.8 . is 92, 18,
retgecton 9
eit
iat
gate Oneonta a5
1 Mabe aed
1} parentheses: Shell 168
ine teh
[i pic bell 28
Sparen 0,4
{ repalt expteaton 13,324
TieBleStpesion 108
fom egrenion 19,24
cet eigreson. 108
1 Frog expression 102,324
Eg Sec
stharey ne
ePingt neuen 6,53. (8
Se thel eu sius” 14
FBO ge
see preset.
Seeks as
BU Roses ble of set
ts
Wasaga
eee
2efename reieton 99
Higa
ira
Be ope a
‘Scions embedded 276
sora
Beemer?
Se
Srfoments command 13,74, 75
349
INDEX
Sigumens pea i 114, 220
egw ti ie ‘me
eee
Sigamont, comand ine 50
as,
Sas e
[Link] 129
each 108
Sh ipemw pace
‘Bik break eatement 12,
‘iecommend ih
Si stilee hy
= cE eatin im
Se ici oe MS ig
Se es TS
RE iar wae 0)
‘Eek functions tele 123
SEE ten,
Bi tine to is,
SEIS tr
ase
‘Sve nome sttemen, 122
SEs380. THE UNIX PROGRAMMING ENVIRONMENT
see mail 6
Soe pers Te hs
ve praneé statement 116
SU Epa tinction "12
SSE fi ote 125
sk eubees function 117
SO varus iain 18
i
cove vibes, abe of
SOE Varah el varies
i
SBladipnce convention 43
2Beommand,na 8
tigen pases 2 9,7,
bucks, + 86,198
SA: ead 87
Dacustaan incon 277
Sica mo Seoee, gut
oc ging eh 6.28
SEASpeEcomenion, Xb 43
retapce, ct 2
[eck Naur Form, 234
‘eckvarde command 122
Breit putern, cue U8
Bo a ater nt
Benoa sb
bin Stet ot 3, 2
sven: pena
Unpedble 2
ee,
ee ea
eee
Bourne, Seve 100, 200,
Sich BAS,
frst is 2O :
bus, eyaten 185,205,
ae Ete Tas
hte anctions, ed 245
Sandie command
Borde, chabiy of 99
Seats am
"eenie convention 45
Ssimaeno i
Ce pgs 14,
Eel io0."* Pe
Sebcommind 133,15
SEEN Gnnend 9.27. 129
ait onion
aan Rots
ita toe
eds Seeste
‘See tenet, Sal ae
Seem ae ti
Sa
She iin of 3
Sie eran 150. 198
Soot
Se op 2S, 25
Scion
eon” 299
hinge, plese 30
seees Papen “
thing dcr 25
hing permite $6
Sarge Soc RUL 18
beter cee 0D
Character Gas. neat 102
Starster dei
ce act ASCH 4, i 107
harass BREDIC 2 at
‘Secenass command 186 2
Shecenai eaten of 38
hese being
‘Ss ompate, Be
‘mod remand 3
‘Simo
Sod ox $6, 6
‘oe aap 170,171, 18,
sh
Shae Tasniat!
Sap a THO. 266
Se fant, nocd 269,
Scie senert, nee 358
Se Feat: 22h
Sede te Mee
Shae e He ase
‘oath oni, 3032,
Comer Dove 13
Saree
Saad
seu, 5
‘commands eating ell 30
Serceens,
Doce
SEE Re A
‘commands, table of fie, 24
SSS
arch
Ses
Sees
Seeley
Sea
Senate a
cere
Soe
‘Smvetion -efename 46
San cae
‘vention, St eating
Seven iy aaa
Saree
Sass
Speommand ig 61
reat gutem cll 208
Eeea ee»
eer
aia
Saas
Steet
Sone
ah ae
Siete
Sarkis
its
noe
St Fsuring output
SI sopping cor #15
Sls tne kal 6
Seppe test ble 174
‘Seypect header te 1
‘se onmandcaren etry. «21. 25,37,
ie
Seoumand, ea 101
Shum urocuier noe 282
este, es, 2
a aoaraetat
asd 10)
fe command. ero 301
Be Maren Poa ©
De Morgan, Avge 1, 20
‘ier ab i
‘tbupger. sab
‘dougeng 8, 24,258,265,
8
eft sip handing 225,227
Sefice fame a
ta
etronty fonsion 276
Betere at st, as
BHLETE. ci 9
Aspendn’y tle empty 255
ekopors ie 95,301,223
Sect onlendss 1
‘fg of stopen 1
dfs of gee fondly 10s
ese of Later TO we
ese ol Re S
‘denge of Bee 38
‘de of eprane’ 209
es of eo
Sein of ce 172,178,179, 185
Sere
sas decor 6, 66
see
eet
Pa wa
srmand_ 67
some
ee
‘0
Seen
Hg
Bnd
BEL wo
i ne 25. 51, 75
Ss ae
SS eA
oe
de, 3,80
ake
feet ee
ois
Ses peso ‘ban 81, 9,
leery. removing 2 2
Sessa te 81
reser. “emp 63 16
Sees ane Aes
gues. fag, 28,50
Sees SEARS V8
Sen. fane/ana a
res heade ie 30
Reet an
‘arg apa 6
Soceyes ome” 307,
cry soon 88
‘doabte command 120
Sato ts 98
3 ammo 0
Bare fo, 2
Since ab,
Dun oor 230
Ce eand eeee_ a8
PRS Ca or
Sle 2
fine mbes 120
Si mer, le of 2,
Se Fag Sipetion camper
2 etext of
i
Fee te
2D De be: HF: 28,28,
eo 8. 8 31.8
Sfopen fincion 182
cc
INDEX 351
Embedded con 276
eee a
atic
Sire oes
Ender ie 2h 308208
Sere
Boe,
Seine 38
Slope bei
Seer caer le 224, 280
Sierra 32,69,
oe 1 i830
tor feanery, hee 76,
Sto anu 8921202
Son eat aie"
Sa a
So Hs.
jake!
‘“eeergennyd poor Me 8,
eae
Srshnvon of hechnai 215
Seeger s
Seeccewneny?
‘tel oan mand #1
ina a
i,
se cian) 12
ale rte
ft ats of Sl ie 12
Seca
Pane tpes Se
fac fonction 34,
Bese
feuses aS ie
as352 THE UNIX PROGRAMMING ENVIRONMENT
ab Ronan 390 tee
Exexa commen 8
fala ae awe Tis
‘ht at hn 19, 10,
ae
te lee
i
HESS eee ay
oo
eden ai
fie movagg
fie, opening» 201
fins 3, 208
fle renaming «16
fea
fecal
fe Stemi,
A ten ay 3.08
{ie tine ae .
Mente conenton 26
ie Sone, 7
tieame even, “2 Sy
Herame toni, 7 38
tide ia So
AeERS Seite os
et rai ox 121
fsrepune 9-107
femur 2
fiers e101
inte Sate machine 277
Fein
Being pat aceon 202,20
fo1a command TS
fsltoslamage 0
fot Ganges 298
$2500 mote a
Seka us
Br hapa hel os
feet yaam cal ‘ee
fe decry $19,309
[nang 3
fmt Re cot 9s
formset
foemaer, neott 298
FORIRAN 77 207
Gane
ae
trexp aii
_
a ee
(sin ste aoe 2
Tnctions able of awe 128
fats: atk oe, So
fal eS Bas Lo
ne
functions tbe of wring 176
Prete aed
hime, fortune 36
Breguet
wy Davida
set comimod 16
Seeseg ctn eh
Setenar maceo 177
gecene
pe
Taree i
Samar pun 235
Eepetomie 1
Se
moving a 38
pla extensions 102
Si ee
Hates, Maron.»
ashing 13 4
ead e307 261 286
ober, ees. 228
tte te 8
EEE D,
BEET Bl an
EERE,
‘rere document 94, 98
coe
tee oe
EISmen ig one
‘hoc. evolation of 233
EELS oe
pec a
E Laem he
foe sles, ble of 283
ee
foe! main function 239
Eee
fost waensng funtion 240
ilies 38
Emus”
hoed execersor function 244
EN meram
Boca bata uncon 244
en
EREes
Sere
Siaksew’
ocd 3ex vat 8
toed mates file 282
foed 223 tinction, 268
EERE
Eitan s
Eas
‘ocd eat function 264
oc mara unctog 240
Food Beint fection. 264
EES
food yy function 364Toes {Feode Inetion 272
Eee Hg &
‘oes Lode. e te 27
hoes execute function 281
past
‘hoes insteode function 278
hoot hoes 27
Shes
foc.h, hoes 278
Eesha
mag
tas 2 ann
TELE pean tunann 95
LP ot
12Seae funcion, hoee 3
ste sme, 2,
is ae van ie 16 164
"Pong eal, 153,226
LoaScommpend 109, 116
inden "te
So comands, permed 2
Inbernce, open He 223
ee, ek saab, 91
foie-c'ne hock 29
imelsfie neck 3B
snk nwtite T,
‘ne table 20
(Bhut frmae 331
Inu erage 2900
ie Seni, agg 14
Integer fension 189
Se
Fe Se
ean pont 226, 28
pate ss
Rei?
Le
Ieson Steve x 200,238,257,
sal
sification, me 291
sas 3
ae Ae
ae
ke command. ne 255
aha
2 command 34, 25
aun bon 0,
5 imma ea 236
iSipmind wea" 78
thane crema 357
iam Oued
Ione swe af 7,171
gues Jeopment 23, 286
Inne specs,
ren
Coes
HE ge on nr
cee
ee
ie te
ez aan Shoes 36
Elana?
ee
eee
nde, ag
line «64 322
Beet mt
EE
Bibhte »
Ber ag
Eero
Sie eta,
Eee
aoa
INDEX 353
ns, ohn 8
LEPiesiary 297
sia ah ny Bs
eq tet, 352
tess
leave L020,
Sor Smads ne 36
iPhoe ta 6,103
Ens
Sheet am
Beare tr
Imsero, efning Wrote 301
He“
‘Shi peat of 8,36, 7
215 a
asi to rate 36, 07
‘naan function, noe 239
katt
‘main funcion, hocd, 260.
ES Aw,
pick 7
force yo
Bane Wee: sap 19)
‘Bake #7 cominand 2
Sik Sooea
‘ake command 24
ego
ee384 THE UNIX PROGRAMMING ENVIRONMENT
fan command 1,30)
2
Irabual,oe329
Mash, Jobe 38,199
Pra eye Je, 238
athve fe) 5053. 252
Riiboy Boog, we, 78
esi ee 121
‘emery fault
Seog command 0,68
‘Raa
revachircte 102,320
mmeacharaer, sel 38
Petecharacer ale of shell 7S
‘Rips funcion it
Sader command 25,38
‘Beda 27 261302
onsout” 28
Roce command 15
a ince pace 290
eprom Bt
‘Mute record, ave 180
IRiN Sms, a9
Sr owe ell 118
Ai eine convention 43
seit aE
fama ahi of ror 298
tne rest Seger 7
Btopy farce
ep chara css 102
spite
EEE.
aaa
BEERS
Ere ou ty
‘eee mand 10,162. 163,
e
Wap variable. aie 118
cane y
mae Us
syiieteae us
Seis
Rims
sees
fall sine in ATE 139
SESE aw
See
aaa
a28
22 ey
pe ee 208
ome ‘i inberienee 228
Bees
Se
Sane:
=
ae
aoe.
SS See ie
eae
‘options, parsing '78 i
ser rhe
Se a
acne fh
me Te
=e,
oes ae
See
Sec
SN Pn. a
Seca in,
ae
age lout 289
Pisin bet
Bacar: fener te 206
Few dean 3,75
enters, hell) 72,73
frenbese tell} [es
fase aiess 238
eee aie, 284
Eents
ae
futsal wrguoeat ToL
oe
faseoed, changing & 34
[rsenord enya 33
Ristgg We Yotcrpeene 8,
sort Seutty 70
Sn nal seen 139
ab 1,
rar te go
rene
REPrstans
= ane
pt
Sine ach 7
pattern, shell 228
acm i ees el 8
sc ac
eigen dee A, 68, 201
Ete,
Bema.
Fenian great 205
SS aw
mthcee
ome,
Eas
BEES wo
3
Psi 7,
tine examples 31
Tee a a
point ste change 20
cainpos PW
foie
fone 3
Rep 290,201
edepe inate 278 22
Bee anc 1
eine nei, hot 24
Belt Stenent noe 33)
Pane
Bein satement, ave 16
eer a as sacar
roca dts, ho?
Frost acrid 3,73,
Bs
rottcaey
eta," «
ann
en
seers
ee
Si gras
noes,
“pale oats
pti ne 220
Progam dear 10,135,147,
ees
rosa, soning 3 7.34
seg icles pie
opramabl mater 289
Flopammable st 9,
soso ae
Prompt Secondary, 76
Foc weie 9
‘Benes ancton 282
Pee
Ppa command, tof 301
BF shel vable Wo, 2
ed tel varie 18
bash function oct 262
Fann may
Pecener 172
reyomsng
ear
aaa
ee
sale
eee Ba 6,6
stig nan
Seg cs
x eg ore oven
e eahe
See
ecto, 5 102
a
segulat expression, * 102,324
tre samp
sol api, nae 10,
ssp reso grep, 02
‘falar exces, fee
‘ular expenon: ach
tia 8
‘fuly ete: a of 2d
a
TERME or Roe 3h,"74
{ly Ss eg 13
‘Fepiace command 135
Inpex 355
tecement ras, 28
reores fie
‘Sig orate 8
RETURNS, 7, 13.98,
‘Sed he
Bieteh, at'g 2,73
Fee. Denali x. 39, 9,
i 3
Soft formatter 289
feat 28)
Foot ther 82.35
Resist Lary x
ike are 17
‘vcard, sed” 108
sea
Sieames 230
Semne TI
Sin, Det. a4
Seen Th 39
meant
Saray ‘3, BT, 88, 199, 142,
Senda romp 76
SS, peswors
sa Pica 0
58 command 108
SS Seto 112
dieting newtine 111
Serene HS ht
Sea qeommeed 110
Sinn
Separator. command 3,78
separators, awe field 116
ee.
ee
EE ae gp
Eeraee g
SS periion 34356 THE UNIX PROGRAMMING ENVIRONMENT
29.68,
Seventh Eon 2,1
R7
Tesi igh rk,
agnosie
cat
$09,359
renbeses 72,73
reeset 48
2 Patera 3
Contry 28
Sat $c Pranab 1
Rana | Vaan, eof
peg AN, 8 1
Size a,
EERE al
Fee
a
See
ia
ee
Shel for sop Ts
‘ell £0 fedioction 199
Smee
Hepes
See a
Shell mets stan 138
el renee, 91
‘hel sarabe vey 237, 8
ae
set Paget
elec
ie
Shae command 135.18
sersnce enti 253, 268
Sonia aoe 3
Dia tut 238
$a Mandingo 228,227
Bs
ee
Se a a
eS
EXEao a as
tg)
odie
ses ‘able of hoe 283
SNOBOLT at
Sek ou
Recipe uae 26
pet? command 315
ck ace 1
SoS ace ie
Sand err 32. 92,177,202
anand ip 90 82.17, Sab
netions ab of
WO tary 170
ated ute 3.177202
eae heute 218
iter, pre 3
Ste am, wane 222
redeem
ce
seglonn header Ge 173
Sin’ formuts 333
Sie in
ene 2
Srctue! fie st 4
EE Shand 5,8
Bare ey
se command 217
ee an
aoe
BE
Pee
are
BS
‘econ fect 24, 229
Berm gla
Ebiaope §
file oF ek operons 8
seas
Ube of dices 63
een
eater
{iiss
table te sommands 21
SSeS nt 36,30
tube of Roe operate 330
te Se
tah of C0 tang 302
tthe of mi commands 257
1 Se Soman 36{abe se matacharacters 75
{ibe of el pater 16,
eof Sel eigen 94
SDE of sel sarisblen 3S
abe of nl names 30
‘be of sanderd UO fencons
In detnitne 174
‘eesti exrenion 105
serrerecy
ies
EL
irene, van
terminal echo 2, 43°
ears
Ceoe tecgaion
Sours
TEX formatter 314
rh
sha
mos
‘tameout command. 230
get
tens be noo 28
cate
eer
carers
nee
SEES ona
sare
soa!
kee at Be
Skeet AG command 58, 306
EESHE bp commun 30
SESE command 392,306
Eset cae ommend)
EOEE AF command 291,299
Eset eon
{EEOEE, geting backs vo
‘set
pxoéf ngs 20
orf hance ane oe
Sica
See
{EROEE ‘%8 Command 30}
Ses
Fagen fect 4, 5
Manion i223, 251,278
eta 103
Sree cnn 106
imag 107
Snieecommand 3
fants Bh
GRIX sie Echo 78
tacts sia, sbell
ener
ave cory 22 98, 68
‘aah Bey 889,65,
ons /Sit/onde dssry
Jaime ny 20
‘Jaserinclade decry 173
jets
ieee
‘hep command 39
Se
arate een 281,276
ers abe of a 118
arabe ae of Se 38
Steak nai hoot 20
‘he command 173, 175,178
SEE a HE,
va fanton 179
ESSE Meson
Yeomiandy e112
second
Siecle canmand 2
INDEX 357
wetchnto command 7
ear w
Se rari
Sr on
ce
Serre
eee
Shes
ae
ae
7
Tere
Enh,
Eoahes
Foon
Eee
ioee >
ee
Hae Bw
FEES com mos a0
Re
FES Shem wes
ic ts
pies
‘Flex function, hoes
Bist
Bes
ab
2
ee a on
eee
Bee.