porttour1

unix v7是最后一个广泛发布的研究型UNIX版本

.PP
It is frequently desirable to know if a node represents a leaf (no descendants), a unary operator (one
descendant) or a binary operator (two descendants).
The macro
.I optype(o)
returns one of the manifest constants LTYPE, UTYPE, or BITYPE, respectively, depending
on the node number
.I o .
Similarly,
.I asgop(o)
returns true if
.I o
is an assignment operator number (=, +=, etc. ), and
.I logop(o)
returns true if
.I o
is a relational or logical (&&, \(or\(or, or !) operator.
.PP
C has a rich typing structure, with a potentially infinite number of types.
To begin with, there are the basic types: CHAR, SHORT, INT, LONG, the unsigned versions
known as
UCHAR, USHORT, UNSIGNED, ULONG, and FLOAT, DOUBLE,
and finally
STRTY (a structure), UNIONTY, and ENUMTY.
Then, there are three operators that can be applied to types to make others:
if
.I t
is a type, we may potentially have types
.I "pointer to t" ,
.I "function returning t" ,
and
.I "array of t's"
generated from
.I t .
Thus, an arbitrary type in C consists of a basic type, and zero or more of these operators.
.PP
In the compiler, a type is represented by an unsigned integer; the rightmost four bits hold the basic
type, and the remaining bits are divided into two-bit fields, containing
0 (no operator), or one of the three operators
described above.
The modifiers are read right to left in the word, starting with the two-bit
field adjacent to the basic type, until a field with 0 in it is reached.
The macros PTR, FTN, and ARY represent the
.I "pointer to" ,
.I "function returning" ,
and
.I "array of"
operators.
The macro values are shifted so that they align with the first two-bit
field; thus PTR+INT
represents the type for an integer pointer, and
.DS
ARY + (PTR<<2) + (FTN<<4) + DOUBLE
.DE
represents the type of an array of pointers to functions returning doubles.
.PP
The type words are ordinarily manipulated by macros.
If
.I t
is a type word,
.I BTYPE(t)
gives the basic type.
.I ISPTR(t) ,
.I ISARY(t) ,
and
.I ISFTN(t)
ask if an object of this type is a pointer, array, or a function,
respectively.
.I MODTYPE(t,b)
sets the basic type of
.I t
to
.I b .
.I DECREF(t)
gives the type resulting from removing the first operator from
.I t .
Thus, if
.I t
is a pointer to
.I t' ,
a function returning
.I t' ,
or an array of
.I t' ,
then
.I DECREF(t)
would equal
.I t' .
.I INCREF(t)
gives the type representing a pointer to
.I t .
Finally, there are operators for dealing with the unsigned types.
.I ISUNSIGNED(t)
returns true if
.I t
is one of the four basic unsigned types;
in this case,
.I DEUNSIGN(t)
gives the associated `signed' type.
Similarly,
.I UNSIGNABLE(t)
returns true if
.I t
is one of the four basic types that could become unsigned, and
.I ENUNSIGN(t)
returns the unsigned analogue of
.I t
in this case.
.PP
The other important global data structure is that of expression trees.
The actual shapes of the nodes are given in
.I mfile1
and
.I mfile2 .
They are not the same in the two passes; the first pass nodes contain
dimension and size information, while the second pass
nodes contain register allocation information.
Nevertheless, all nodes contain fields called
.I op ,
containing the node number,
and
.I type ,
containing the type word.
A function called
.I talloc()
returns a pointer to a new tree node.
To free a node, its
.I op
field need merely be set to FREE.
The other fields in the node will remain intact at least until the next allocation.
.PP
Nodes representing binary operators contain fields,
.I left
and
.I right ,
that contain pointers to the left and right descendants.
Unary operator nodes have the
.I left
field, and a value field called
.I rval .
Leaf nodes, with no descendants, have two value fields:
.I lval
and
.I rval .
.PP
At appropriate times, the function
.I tcheck()
can be called, to check that there are no busy nodes remaining.
This is used as a compiler consistency check.
The function
.I tcopy(p)
takes a pointer
.I p
that points to an expression tree, and returns a pointer
to a disjoint copy of the tree.
The function
.I walkf(p,f)
performs a postorder walk of the tree pointed to by
.I p ,
and applies the function
.I f
to each node.
The function
.I fwalk(p,f,d)
does a preorder walk of the tree pointed to by
.I p .
At each node, it calls a function
.I f ,
passing to it the node pointer, a value passed down
from its ancestor, and two pointers to values to be passed
down to the left and right descendants (if any).
The value
.I d
is the value passed down to the root.
.a
.I Fwalk
is used for a number of tree labeling and debugging activities.
.PP
The other major data structure, the symbol table, exists only in pass one,
and will be discussed later.
.SH
Pass One
.PP
The first pass does lexical analysis, parsing, symbol table maintenance,
tree building, optimization, and a number of machine dependent things.
This pass is largely machine independent, and the machine independent
sections can be pretty successfully ignored.
Thus, they will be only sketched here.
.SH
Lexical Analysis
.PP
The lexical analyzer is a conceptually simple routine that reads the input
and returns the tokens of the C language as it encounters them:
names, constants, operators, and keywords.
The conceptual simplicity of this job is confounded a bit by several
other simple jobs that unfortunately must go on simultaneously.
These include
.IP \(bu
Keeping track of the current filename and line number, and occasionally
setting this information as the result of preprocessor control lines.
.IP \(bu
Skipping comments.
.IP \(bu
Properly dealing with octal, decimal, hex, floating
point, and character constants, as well as character strings.
.PP
To achieve speed, the program maintains several tables
that are indexed into by character value, to tell
the lexical analyzer what to do next.
To achieve portability, these tables must be initialized
each time the compiler is run, in order that the
table entries reflect the local character set values.
.SH
Parsing
.PP
As mentioned above, the parser is generated by Yacc from the grammar on file
.I cgram.y.
The grammar is relatively readable, but contains some unusual features
that are worth comment.
.PP
Perhaps the strangest feature of the grammar is the treatment of
declarations.
The problem is to keep track of the basic type
and the storage class while interpreting the various
stars, brackets, and parentheses that may surround a given name.
The entire declaration mechanism must be recursive,
since declarations may appear within declarations of
structures and unions, or even within a
.B sizeof
construction
inside a dimension in another declaration!
.PP
There are some difficulties in using a bottom-up parser,
such as produced by Yacc, to handle constructions where a lot
of left context information must be kept around.
The problem is that the original PDP-11 compiler is top-down in
implementation, and some of the semantics of C reflect this.
In a top-down parser, the input rules are restricted
somewhat, but one can naturally associate temporary
storage with a rule at a very early stage in the recognition
of that rule.
In a bottom-up parser, there is more freedom in the
specification of rules, but it is more difficult to know what
rule is being matched until the entire rule is seen.
The parser described by
.I cgram.c
makes effective use of
the bottom-up parsing mechanism in some places (notably the treatment
of expressions), but struggles against the
restrictions in others.
The usual result is that it is necessary to run a stack of values
``on the side'', independent of the Yacc value stack,
in order to be able to store and access information
deep within inner constructions, where the relationship of the
rules being recognized to the total picture is not yet clear.
.PP
In the case of declarations, the attribute information
(type, etc.) for a declaration is carefully
kept immediately to the left of the declarator
(that part of the declaration involving the name).
In this way, when it is time to declare the name, the
name and the type information can be quickly brought together.
The ``$0'' mechanism of Yacc is used to accomplish this.
The result is not pretty, but it works.
The storage class information changes more slowly,
so it is kept in an external variable, and stacked if
necessary.
Some of the grammar could be considerably cleaned up by using
some more recent features of Yacc, notably actions within
rules and the ability to return multiple values for actions.
.PP
A stack is also used to keep track of the current location
to be branched to when a
.B break
or
.B continue
statement is processed.
.PP
This use of external stacks dates from the time when Yacc did not permit
values to be structures.
Some, or most, of this use of external stacks
could be eliminated by redoing the grammar to use the mechanisms now provided.
There are some areas, however, particularly the processing of structure, union,
and enum declarations, function
prologs, and switch statement processing, when having
all the affected data together in an array speeds later
processing; in this case, use of external storage seems essential.
.PP
The
.I cgram.y
file also contains some small functions used as
utility functions in the parser.
These include routines for saving case values and labels in processing switches,
and stacking and popping 
values on the external stack described above.
.SH
Storage Classes
.PP
C has a finite, but fairly extensive, number of storage classes
available.
One of the compiler design decisions was to
process the storage class information totally in the first pass;
by the second pass, this information must have
been totally dealt with.
This means that all of the storage allocation must take place in the first
pass, so that references to automatics and
parameters can be turned into references to cells lying a certain
number of bytes offset from certain machine registers.
Much of this transformation is machine dependent, and strongly
depends on the storage class.
.PP
The classes include EXTERN (for externally declared, but not defined variables),
EXTDEF (for external definitions), and similar distinctions for
USTATIC and STATIC, UFORTRAN and FORTRAN (for fortran functions) and
ULABEL and LABEL.
The storage classes REGISTER and AUTO are obvious, as
are STNAME, UNAME, and ENAME (for structure, union, and enumeration
tags), and the associated MOS, MOU, and MOE (for the members).
TYPEDEF is treated as a storage class as well.
There are two special storage classes: PARAM and SNULL.
SNULL is used to distinguish the case where no explicit
storage class has been given; before an entry is made
in the symbol table the true storage class is discovered.
Similarly, PARAM is used for the temporary entry in the symbol
table made before the declaration of function parameters is completed.
.PP
The most complexity in the storage class process comes from
bit fields.
A separate storage class is kept for each width bit field;
a
.I k
bit bit field has storage class
.I k
plus FIELD.
This enables the size to be quickly recovered from the storage class.
.SH
Symbol Table Maintenance.
.PP
The symbol table routines do far more than simply enter
names into the symbol table;
considerable semantic processing and checking is done as well.
For example, if a new declaration comes in, it must be checked
to see if there is a previous declaration of the same symbol.
If there is, there are many cases.
The declarations may agree and be compatible (for example,
an extern declaration can appear twice) in which case the
new declaration is ignored.
The new declaration may add information (such as an explicit array
dimension) to an already present declaration.
The new declaration may be different, but still correct (for example,
an extern declaration of something may be entered,
and then later the definition may be seen).
The new declaration may be incompatible, but appear in an inner block;
in this case, the old declaration is carefully hidden away, and
the new one comes into force until the block is left.
Finally, the declarations may be incompatible, and an error
message must be produced.
.PP
A number of other factors make for additional complexity.
The type declared by the user is not always the type
entered into the symbol table (for example, if an formal parameter to a function
is declared to be an array, C requires that this be changed into
a pointer before entry in the symbol table).
Moreover, there are various kinds of illegal types that
may be declared which are difficult to
check for syntactically (for example,
a function returning an array).
Finally, there is a strange feature in C that requires
structure tag names and member names for structures and unions
to be taken from a different logical symbol table than ordinary identifiers.
Keeping track of which kind of name is involved is a bit of struggle
(consider typedef names used within structure declarations, for example).
.PP
The symbol table handling routines have been rewritten a number of times to
extend features, improve performance, and fix bugs.
They address the above problems with reasonable effectiveness