  % -*- Mode:TeX -*-

\chapter{Data Structures}
\label{data-structures-chapter}

\section{Lexical Tokens and Parse Trees}
\label{parsetrees}

\subsection{Lexical Tokens}

As discussed in Chapter \ref{IntroductionChapter}, lexical tokens\index{lexical
token} may or may not be used in a compiler implementation depending on the
parser chosen.  An implementation for tokens is given here, however, because it
is expected that most compilers will use a regular-expression lexical
analyzer/LALR parser\index{lexical analyzer}\index{LALR parser} pair as their
parser.

The job of the lexical analyzer is to break the source text into small,
contiguous pieces called {\it tokens}\footnote{Lexical tokens, of course, are not to
be confused with tokens that carry data in a dataflow machine!}, some of which
are passed on to the parser.  Each token is a conceptually indivisible
syntactic unit, such as an identifier, a number, a keyword, a mark of
punctuation, etc.  A token has at least two slots: a {\it class}, which indicates
what kind of syntactic unit the token represents, and the {\it value}, which
gives the actual fragment of source text corresponding to the token.  For
example, the fragment {\tt Var1} might result in a token whose class is
{\tt :INTEGER} and whose value is {\tt "Var1"}.  The parser only examines the class
slot when making parsing decisions, but may include the data from the value
slot in the parse tree it produces.  It is worth pointing out that the lexical
analyzer may suppress the generation of tokens for some pieces of the program
text such as whitespace and comments; the parser never sees these.

In addition to the class and value slots, a token has a slot for a
{\it place}\index{place}, which indicates the token's position within the source
file.  This information is transferred to the parse tree by the parser, and is
used by later compiler phases to construct messages to the user that refer to
specific places within his/her program.  Places are described in Section
\ref{PlaceSubSection}.

The relationship between the lexical analyzer and the parser is somewhat
unusual in that the lexical analyzer supplies tokens to the parser only upon
demand.  This is in contrast to all other modules of the compiler, which are
invoked by a top-level procedure that passes data from one module to another.
As a result, lexical tokens are quite short-lived in that the parser removes
the information from a token and discards it shortly after receiving the token.
To help prevent needless consing and garbage collection, a list of unused
tokens is maintained\index{free token list}, to which tokens should be
explicitly returned when they are no longer needed.

\subsubsection{Selectors}

\lispdoc token-class token [Function]
Returns the contents of the {\tt class} slot of {\it token}, which is a keyword
symbol indicating to what lexical class the token belongs.  May be used with
{\tt setf}.

\lispdoc token-value token [Function]
Returns the contents of the {\tt value} slot of {\it token}, which is a string
giving the fragment of source text corresponding to the token.  May be used
with {\tt setf}.

\lispdoc token-place token [Function]
Returns the contents of the {\tt place} slot of {\it token}, which indicates where
in the source text the token occurred.  May be used with {\tt setf}.

\subsubsection{Constructors}

\lispdoc make-token class value \optional place [Function]
Returns a token whose {\tt class}, {\tt value}, and {\tt place} slots have been
initialized from the corresponding arguments.  The {\tt place} slot will be
{\tt nil} if no {\it place\/} argument is given.  {\tt make-token} uses a token on the
free token list if one exists, otherwise it creates
{\tt *token-allocation-quantum*}\lispindex{Name = "*token-allocation-quantum*",
Type = "Variable"} new tokens, puts them on the free list, and then
uses one of them.\index{free token list}

\lispdoc return-token token [Function]
Puts {\it token\/} onto the list of free tokens, where it can be reused.\index{free
token list}

\lispdoc *token-allocation-quantum* [Variable]
Controls how many new tokens are created when the list of free tokens
becomes empty.\index{free token list}

\subsection{Parse Tree Nodes}
\label{ParseTreeNodeSubsection}

The parse tree\index{parse tree} is the data structure that is produced by the
compiler's parser, and represents the source program in a form that reflects
its syntactic structure.  Following parsing, the parse tree may be subjected to
several transformation phases such as macro expansion or type checking.  These
phases may annotate the parse tree (add information to nodes already existing
in the tree) or alter the tree itself (add or delete nodes).  Finally, the
transformed parse tree is passed to code generation phases of the compiler.  A
fuller description of parse tree manipulations can be found in Chapter
\ref{IntroductionChapter}.

As the name suggests, the parse tree is a tree structure, where each node of
the tree is called a {\it Parse Tree Node}, or ptnode for
short.\index{ptnode}\index{parse tree node}  The
representation of a parse tree in the Id Compiler differs somewhat from the
usual theoretician's conception of a parse tree.  Consider the following
(admittedly ambiguous) grammar:

\begin{enumerate}
\item{\it Expression} $\leftarrow$ {\it Expression} {\tt +} {\it Expression}

\item{\it Expression} $\leftarrow$ {\it Expression} {\tt *} {\it Expression}

\item{\it Expression} $\leftarrow$ {\tt -} {\it Expression}

\item{\it Expression} $\leftarrow$ {\it Identifier}

\item{\it Expression} $\leftarrow$ {\it Number}
\end{enumerate}

Note that the grammar contains three types of symbols: {\it
Non-Terminals}\index{non-terminal}, which always appear on the left hand side
of productions as well as on the right; {\it Keyword Terminals\/}\index{keyword
terminal} like {\tt +}, which appear in the source exactly as they do in the
grammar; and {\it Pseudo-Terminals\/}\index{pseudo-terminal} like {\it
Identifier\/} and {\it Number}, which actually represent classes of terminals
that are treated exactly the same by the parser.  The distinction between
keyword terminals and pseudo-terminals is one not normally drawn in the
literature, but as will be seen is quite important here.

Now consider the following fragment of source code: {\tt Var1 + 6.847}.  A
theoretician might draw the parse tree for this expression as a node with three
descendants: a node with the single descendant {\tt Var1}, the character {\tt +},
and a node with the single descendant {\tt 6.847}.  This kind of representation
is awkward in a compiler for two reasons.  First, the compiler must search the
descendants for keywords to determine whether the expression is an addition,
multiplication, or negation.  Second, the parse tree contains nodes for
productions (4) and (5) which are pretty much information-free.

A more useful representation is used here.  To address the first problem, each
node of the parse tree contains not only a list of descendants, but also a
tag\index{ptnode tag} indicating which production of the grammar was
responsible for that node.  The presence of this tag means that the only
descendants included in the parse tree are non-terminals (other parse tree
nodes) and pseudo-terminals; keyword terminals are not found anywhere in the
parse tree.  To address the second problem, the writer of the grammar may
indicate that certain productions are not to produce parse tree
nodes.\index{suppressed productions} Note that it is reasonable to suppress a
particular production only if its right hand side is a single non-terminal or
pseudo-terminal.

A parse tree node, therefore, has at least two slots:  a tag identifying a
production, and a list of descendants (children).  Several other slots are
also included: a pointer to the node's parent, for ease in traversing the parse
tree, a {\it place\/}\index{place} which indicates the position within the source
file of the text that produced the node, and an {\tt other-slots} slot which holds any
additional information or annotations modules of the compiler wish to attach. 

Pseudo-terminals are also represented as ptnodes; they can be distinguished
from ptnodes representing internal parse tree nodes by the value of their
production tag slot.  While pseudo-terminals have no children, they do have a
{\it value}.\index{pseudo-terminal value} The value of a pseudo-terminal
immediately after parsing is just the string corresponding to that
pseudo-terminal as taken from the source text.  Processing phases immediately
following parsing may change the values of pseudo-terminals to more convenient
representations; for example, the value of a pseudo-terminal representing a
constant may be changed from a string to an actual integer or flonum.  When a
ptnode is used for a pseudo-terminal, the {\tt children} slot holds the value.

Production tags are keyword symbols.  For pseudo-terminals, the symbol is
pseudo-terminal name as it appears in the grammar, for example, {\tt :IDENTIFIER}
for the pseudo-terminal {\it Identifier}.  For productions, the tag is assigned
by the parser generator, and will consist of the left-hand side's non-terminal
followed by a slash and a unique number, for example, the parser generator
might assign the tags {\tt :EXPRESSION/1}, {\tt :EXPRESSION/2}, and
{\tt :EXPRESSION/3} to the first three productions of the grammar above.
Later phases of compilation may add ptnodes to the graph, and care must be
taken to either choose an appropriate pseudo-terminal or non-terminal tag, or
invent a new tag, depending on how the new node is to be treated by the
succeeding phases of compilation.  A facility is provided for dispatching on
the tag slot without knowing the precise tag; see the {\tt grammarcase} macro.

\begin{fig}{parsetreefigure}{Parse Tree for {\tt Var1 + 6.847}}
\illustration{csg261-2}
\end{fig}

Figure \ref{parsetreefigure} shows the parse tree for the expression {\tt Var1 +
6.847} with respect to the grammar given above.

\subsubsection{Selectors}
\label{ParseTreeSelectorsParagraph}

\lispdoc ptnode-tag ptnode [Function]
Returns the production or pseudo-terminal tag for the node.  May be used with
{\tt setf}.

\lispdoc ptnode-children ptnode [Function]
If {\it ptnode\/} represents a pseudo-terminal, as indicated by the {\tt tag}
slot of {\it ptnode}, {\tt ptnode-children} returns the value of the terminal.
Immediately after parsing, the value of a terminal is a string giving the exact
appearance of the terminal in the source program, but a later analysis phase
might change this to some other type such as a symbol or fixnum.

If {\it ptnode\/} is not a pseudo-terminal, {\tt ptnode-children} returns a list of
ptnodes which are the children of {\it ptnode}, where the first element of the
list is the leftmost child.

May be used with {\tt setf}.

\lispdoc ptnode-value ptnode [Function]
A synonym for {\tt ptnode-children}\lispindex{Name = "ptnode-children"}, which
can be used with pseudo-terminal ptnodes for clarity.  May be used with
{\tt setf}.

\lispdoc ptnode-parent ptnode [Function]
Returns the {\it ptnode\/}s parent ptnode, or {\tt nil} if {\it ptnode\/} has no parent.
May be used with {\tt setf}.

\lispdoc ptnode-place ptnode [Function]
         Returns a {\it place\/} identifying where in the source file the
construct represented by {\it ptnode\/} occurred.  Exactly what place is
indicated depends on the production and the parser: for example, if the
production is something like {\it Let-Expression\/} $\leftarrow$ {\tt let} {\it
Binding-list\/} {\tt in} {\it Expression}, the place might indicate the first
character of the keyword {\tt let}, while for a production like {\it
Expression\/} $\leftarrow$ {\it Expression\/} {\tt +} {\it Expression\/} it
might indicate the {\tt +}.  May be used with {\tt setf}.

Additional selectors may be defined by {\tt define-ptnode-slot}\lispindex{Name =
"define-ptnode-slot", Type = "Macro"} ({\it q.v.}).

\subsubsection{Constructors}

\lispdoc make-ptnode tag children \key :parent :place [Function]
Makes and returns a new ptnode, initializing its {\tt tag}, {\tt children},
{\tt parent}, and {\tt place} slots from the corresponding arguments.  Both
non-terminal and pseudo-terminal ptnodes can be created with {\tt make-ptnode}.

\lispdoc make-parent-ptnode tag children \key :parent :place [Function]
Makes a new non-terminal ptnode, initializing its {\tt tag}, {\tt children},
{\tt parent}, and {\tt place} slots from the corresponding arguments; the argument
{\it children\/} must be a list of ptnodes.  The new ptnode is returned, and is
also stored as the parent of each of the elements of {\it children}, regardless
of whether those ptnodes already have a value in their parent slot.  This will
often be more useful than {\tt make-ptnode}\lispindex{Name = "make-ptnode"}.

\subsubsection{Mutators}

In addition to the functions below, all of the selectors in Section
\ref{ParseTreeSelectorsParagraph} and any selectors defined by
{\tt define-ptnode-slot}\lispindex{Name = "define-ptnode-slot", Type = "Macro"}
may be used with {\tt setf}.

\lispdoc replace-ptnode-child ptnode n new-child [Function]
Replaces the {\it n\/}th element of the {\tt children} slot of {\it ptnode\/} with
{\it new-child}, and replaces the {\tt parent} slot of {\it new-child\/} with
{\it ptnode}.  {\it Ptnode\/} must be a non-terminal ptnode and have at least {\it n\/}+1
children.  Children are numbered from the left beginning with zero (just as are
elements of lists for Common Lisp's {\tt nth} function).

\lispdoc replace-ptnode-children ptnode new-children [Function]
Replaces the {\tt children} slot of {\it ptnode\/} with {\it new-children}, which must
be a list of ptnodes, and replaces the {\tt parent} slot of each of the elements
of {\it new-children\/} with {\it ptnode}.  (Note: the list is not copied.)

\subsubsection{Miscellaneous}

\lispdoc define-ptnode-slot selector-name [Macro]
Defines a new ``slot'' for ptnodes which may be used as if it were one of the
slots already provided by the compiler substrate.  For example, the form
\begin{verbatim}
(define-ptnode-slot ptnode-desired-type)
\end{verbatim}
defines a new ptnode slot called {\tt desired-type}, which may be accessed by
{\tt (ptnode-desired-type {\it ptnode\/})} and written by {\tt (setf
(ptnode-desired-type {\it ptnode\/}) {\it value\/})}.  {\it Selector-name\/} must be a
symbol whose print name begins with {\tt ptnode-}, and may not be any of the
symbols {\tt ptnode-tag}, {\tt ptnode-children}, {\tt ptnode-value},
{\tt ptnode-parent}, {\tt ptnode-place}, or {\tt ptnode-other-slots}.  The slot is
actually implemented as a property stored on the property list contained in the
{\tt other-slots} slot of ptnodes.  The indicator used is a keyword symbol giving
the name of the slot; for the example given, the indicator would be
{\tt :desired-type}.  Note that initial values for slots defined by
{\tt define-ptnode-slot} may not given in calls to {\tt make-ptnode}\lispindex{Name
= "make-ptnode"} or {\tt make-parent-ptnode}\lispindex{Name =
"make-parent-ptnode"}; they are always initialized to {\tt nil}.

\begin{aside}
{\bf Rationale:} The ``other slots'' mechanism was designed to meet three goals: to
provide a convenient way to annotate ptnodes, to keep different annotations
separated, and to provide an easy way of making commonly used annotations a
permanent part of the compiler substrate.  The latter might be desirable
because built-in slots are both faster and take up less space.  Changing an
annotation from a {\tt define-ptnode-slot} slot to a built-in slot will require
no changes in programs that make use of the slot, since both kinds of slots are
manipulated in the same way.
\end{aside}

\subsection{Places}
\label{PlaceSubSection}

A {\it place\/}\index{place} is a small data structure that indicates a particular
place within the source file.  It has three slots: {\tt line}, which gives the
line number of the place, {\tt column}, which gives the horizontal position
within that line, and {\tt character}, which gives the position within the text
when viewed as a sequence of characters.  All tree fields are zero-based.  The
idea is that {\tt line} and {\tt column} are most useful when printing messages,
while {\tt character} is most useful for use with text editors and other programs
that actually manipulate the source file.  [The definition of places is subject
to change.]

\subsubsection{Selectors and Constructors}

\lispdoc place-line place [Function]
Returns the contents of the {\tt line} slot of {\it place}.  May be used with {\tt setf}.

\lispdoc place-column place [Function]
Returns the contents of the {\tt column} slot of {\it place}.  May be used with {\tt setf}.

\lispdoc place-character place [Function]
Returns the contents of the {\tt character} slot of {\it place}.  May be used with
{\tt setf}.

\lispdoc make-place line column character [Function]
Returns a new place whose slots are initialized according to the arguments.

\subsection{Parse Trees}
\label{ParseTreeSubSection}

When passing a complete parse tree from module to module, it is often necessary
to pass along some additional information, such as the compiler version,
{\it etc}.  The {\tt parse-tree} abstraction is provided for this purpose:  it
contains the root node of the parse tree along with a property list that can
give any additional information needed.

\lispdoc make-parse-tree root-ptnode \optional plist [Function]
Creates and returns a new parse tree, whose root node is {\it root-ptnode}, and
with property list {\it plist}.  The default for {\it plist\/} is an empty property
list. 

\lispdoc parse-tree-root parse-tree [Function]
Returns the root node of parse tree {\it parse-tree}.  May be used with {\tt setf}.

\lispdoc parse-tree-plist parse-tree [Function]
Returns the property list of parse tree {\it parse-tree}.  May be used with
{\tt setf}.  The following function is probably more useful.

\lispdoc parse-tree-get parse-tree indicator \optional default [Function]
Returns the {\it indicator\/} property of {\it parse-tree\/}'s plist, or {\it default\/} if
that property does not exist.  In other words, {\tt parse-tree-get} combines
{\tt parse-tree-plist} with {\tt getf}.  May be used with {\tt setf}.

