guide.tex

PL/0源码

will print just the names of the checked-out files.
You may want to create aliases for these, e.g.\ {\tt llrw} and
{\tt lsrw}.
I frequently type {\tt rcsdiff `lsrw`} to find out what changes I've
made recently, and {\tt ci -u `lsrw`} to check them all in.
\end{description}

\section{Creating and Running Your Copy of the Compiler}

The root directory of the PL/0 distribution
contains a copy of the source for the PL/0
compiler, together with a {\tt Makefile}, a {\tt README} file, and a
{\tt NEWUSER} script.
The {\tt README} file explains how to use the {\tt NEWUSER} script.
This script will copy the source, create an RCS archive of it, run {\tt make}
to build the compiler, and create a test directory.

The {\tt Makefile} places the final PL/0 compiler in a file named
{\tt pl0} .
The compiler reads a PL/0 source program from standard input or from
a file named in its command-line arguments.
In the latter case, the name must end with ``{\tt .0}''.
The compiler prints
error messages and diagnostics to standard output (fatal errors to
standard error), and writes MIPS~I assembler target code
to a file whose name is created by replacing the
``{\tt .0}'' in the source file name with ``{\tt .s}''
or, if compiling standard input, to a file named {\tt plzero.s} .

With a {\tt -sgi} command-line argument, the compiler generates the MIPS
dialect understood by assemblers for Silicon Graphics computers.
By default, or with a {\tt -spim} argument, it generates the dialect
understood by James Larus's MIPS interpreter, {\tt spim}, from the
University of Wisconsin.
To compile and run a PL/0 program under {\tt spim}, type:
\begin{verbatim}
    pl0 foo.0
    spim -file foo.s
\end{verbatim}

The pl0 compiler accepts a few additional arguments:

\begin{itemize}
\item {\tt -g}, Include partial symbol table information in the target
  code, to make it a little easier to debug PL/0 programs.
\item {\tt -C}, Include PL/0 source lines in the target code as comments.
\item {\tt -O+c}, Evaluate most constant expressions at compile time.
\item {\tt -O-p}, Do not do peephole optimization.  At present, the
  only optimization performed is to avoid moving the contents of a
  register into itself.
\end{itemize}

\section{PL/0 Compilation Phases}

The PL/0 compiler consists of just under 11,000 lines of
heavily-commented C++, plus automatically-generated scanner and parser
tables.  Constants in the code are printed entirely in capital letters,
with sub-words separated by underscores, e.g.\ {\tt SCRATCH\_REG}.  All
other identifiers are printed entirely in lower case, with sub-words
separated by underscores.  User-defined type and class names end with
{\tt \_t}, e.g. {\tt token\_attrib\_t}.

\subsection{Source Buffering and Diagnostic Messages}

Files {\tt inpbuf.[h,cc]}

The compiler reads its source on demand, and keeps it all buffered in a linked
list.  Together with each line, it keeps a list of diagnostic messages
associated with that line.
Buffering allows messages to be generated out of order, but printed in order.
The later phases of the compiler keep track, for each syntactic
construct, of the location (line and column) at which that construct began.
Messages pertaining to that construct can then be issued at the appropriate
location.

Each diagnostic has a key letter in column 2 that indicates what kind of a
message it is.
\begin{itemize}
\item {\tt S} means syntax repair.
\item {\tt W} means warning.
\item {\tt E} means semantic error.
\end{itemize}
Semantic errors inhibit code generation; syntax repairs and warnings
do not.

\subsection{Scanner}
Files {\tt scantab.[h,cc]}, {\tt scanner.[h,cc]}

The scanner is a straightforward finite automaton.
It keeps a copy of tokens whose characters are significant (identifiers
and numbers).
Its main entry point is the function {\tt token\_get}, called by the parser.
The only tricky part of the scanner is the mechanism for backtracking,
employed when one token in the language is a prefix of another,
but more than one character of lookahead is required to
distinguish between the two.
(For example, consider {\tt 3.1459} and {\tt 3..14} in Pascal, or
{\tt DO5I=1,10} and {\tt DO5I=1.10} in Fortran.)
No such tokens occur in PL/0, but they could easily be added, and the
scanner will support them.

\subsection{Parser and Syntax Error Repair Routines}

Files {\tt parsetab.[h,cc]}, {\tt parser.[h,cc]}

The parser is a straightforward LL(1) pushdown automaton, augmented with
error repair routines and with markers to support automatic
management of space for attributes (see below).
The error repair routines employ
a locally least cost technique due to Fischer, Milton, and Quiring.
Basically, they calculate the ``cheapest''
set of insertions and/or deletions that will allow the parser to consume one
more token of real input.
Insertion and deletion costs are specified in the {\tt grammar} file.
The choice among alternative repairs can be tuned by changing the
relative costs of various insertions and deletions.
Generally speaking, it should be easy to insert or delete tokens that
a programmer is likely to forget or to type by mistake, and hard to
insert or delete tokens that require matching constructs later in the program,
since incorrect repairs of this type are guaranteed to lead to future errors.

\subsection{Syntax Tree Construction}

Files {\tt attributes.[h,cc]}

The semantic action routines in the grammar file do one thing only:
construct an abstract syntax tree.
They perform no symbol table manipulations, nor do they check for any
error conditions.
Space for attributes is maintained in a so-called
``attribute stack'',
which is pushed and popped automatically at appropriate times in the
parse.
At any particular point in time, the attribute stack contains a
vertical slice of the parse tree: one record for each symbol in each
production between the current node and the root.
The full parse tree is never in memory at once.
When the parser predicts a production, it calls into the attribute
manager to push records onto the attribute stack for all the symbols on
the right-hand side (RHS).
It also pushes a marker onto the parse stack.
The marker allows it to tell when it has popped all the RHS symbols off
the parse stack, at which point it calls into the attribute manager to
pop the RHS symbols off the attribute stack.

Each element of the attribute stack contains either the synthetic
attributes of a token from the scanner or a pointer to a syntax tree
node (or, often, nothing at all).
The purpose of the action routines in the grammar is to pull the token
information out of the attribute stack, construct appropriate
pieces of the syntax tree, and hang them off of records in the
attribute stack that will be available to routines later in the parse
(higher in the parse tree).
When parsing is completed, the root of the complete syntax tree is
found in the attribute record of the goal symbol, the last remaining
record on the attribute stack.

\subsection{Semantic Checks}
\label{sec-semantic-checks}

Files {\tt semantics.[h,cc]}

The semantic checker enters identifiers into the (scoped) symbol 
table, and performs all static semantic checks.
For PL/0, the only checks are the following:
\begin{itemize}
\item is every identifier declared before use?
\item is no identifier declared more than once in the same scope?
\item is every left-hand side of an assignment a variable?
\item is every identifier in an expression a variable or constant?
\item is every called identifier a subroutine?
\end{itemize}

In addition, the PL/0 compiler performs the following ``sanity checks'',
and issues warnings (not error messages) if they fail:

\begin{itemize}
\item is every variable both written and read?
\item is every constant read?
\item is every subroutine called?
\end{itemize}

\subsection{Code Improvement (Optimization)}

Files {\tt optimize.[h,cc]}

The purpose of the code improver is to make machine-independent modifications
to the abstract syntax tree that are likely to result in code that is
significantly faster and/or smaller.
The main entry point is {\tt optimize\_syntax\_tree}.
At present it doesn't do much: it computes the values of arithmetic
expressions and conditions consisting entirely of constants.
It does not use arithmetic identities to re-order expressions in order to
uncover additional constants, nor does it perform copy propagation.
More to the point, it does not perform any of the other standard
machine-independent optimizations, such as identification and exploitation
of loop invariants, induction variables, common subexpressions, live and
dead variables, or available and very busy expressions.

\subsection{Code Generation}

Files {\tt codegen.[h,cc]}, {\tt mips.[h,cc]}

There are two sub-phases to code generation.
The first assigns frame pointer offsets for local variables, and allocates
registers; the second generates code.
Register allocation is extremely naive: the registers of the target
machine not reserved for any other purpose are used as a LIFO evaluation
stack.
Most programs use nowhere near the full register set.
Any program requiring more than the available number of registers produces
a fatal compiler error.
A good compiler (with a code improver and a smart register allocator) would
keep many variables in registers much of the time, spilling them to memory
only when absolutely necessary.

For the purposes of code generation, additional fields are required in
both the nodes of the syntax tree and the records of the symbol table.
These fields are maintained in separate records so that they need
not be visible to the early phases.

The main entry point for code generation is {\tt generate\_code}, in 
{\tt codegen.cc}.  The routines in {\tt mips.[h,cc]} encapsulate the 
MIPS assembler syntax by overloading the function {\tt mips\_op}.

\subsection{Symbol Table}

Files {\tt symtab.[h,cc]}

The symbol table has a wide interface (many subroutines declared in symtab.h),
but a simple internal structure.
There is a single main hash table, keyed by \{name, scope\} pairs,
and a stack of open scopes.
To look up an element, the symbol table routines traverse the open scope stack
from top to bottom, probing the hash table at each level to see if the desired
name was declared in that scope.
Faster schemes are possible, but this one is simple, works well, and is
not outlandishly slow.

\section{Compiler Classes}

\subsection{Syntax Tree Nodes}

Every node in the attributed syntax tree is an object belonging to one of
the concrete subtypes of the abstract type {\tt syntax\_tree\_t}.
Figure~\ref{fig-syntax} shows the hierarchy of PL/0 syntax tree classes.

\begin{figure}
\centerline{\epsfxsize\textwidth
\epsfbox{syntax.eps}}
\caption{Syntax tree classes.}
\label{fig-syntax}
\end{figure}

Each subclass of {\tt syntax\_tree\_t} must implement the following
member functions:
\begin{itemize}
\item constructor (in {\tt attributes.cc})
\item {\tt check\_semantics} (in {\tt semantics.cc}) \\
    Checks the semantics of the node and any of its children.
\item {\tt optimize} (in {\tt optimize.cc}) \\
    Performs any code optimizations on a node and its children.
\item {\tt allocate\_registers} (in {\tt codegen.cc}) \\
    Allocates any registers used by the node and lets its children also
    allocate their needed registers.  Returns a pointer to its
    {\tt syntax\_code\_t} structure which details register usage and
    where the node's parent can locate any results generated by the node.
\item {\tt generate\_code} (in {\tt codegen.cc}) \\
    Generates any inline assembly code need by the node and its
    children and dumps code to the output file using the {\tt mips\_op}
    functions.
\item {\tt generate\_lcode} (in {\tt codegen.cc}) \\
    Generates any inline code needed to access a node's lvalue.
\item {\tt dump\_object\_data} (in {\tt attributes.cc}) \\
    Dumps all useful debugging information about a syntax tree node
    to {\tt stdout}.
\item destructor (in {\tt attributes.cc}) \\
    Deallocates the node and its children.
\end{itemize}

\subsection{Symbol Table Entries}

All entries in the symbol table must be members of a concrete type which
is derived from the abstract type {\tt symbol\_entry\_t}.
Figure~\ref{fig-symbol} shows the PL/0 symbol table entry classes.

\begin{figure}
\centerline{%\epsfysize 2in
\epsfbox{symbol.eps}}
\caption{Symbol table classes.}
\label{fig-symbol}
\end{figure}

Each subclass of {\tt symbol\_entry\_t} must implement the following
member functions:
\begin{itemize}
\item constructor (in {\tt symtab.cc})
\item {\tt allocate\_space} (in {\tt codegen.cc}) \\
    Allocates any space either in the stack frame or globally which
    will be needed to represent the symbol in the compiled program.
\item {\tt generate\_data} (in {\tt codegen.cc}) \\
    Outputs any pseudo-symbols or other code for creating the symbol
    in the output assembly file.  For example, global variables output the
    pseudo-opcode ``{\tt .dword 0}''.
\item {\tt generate\_code} (in {\tt codegen.cc}) \\
    Generates any inline code needed to access a symbol.
\item {\tt dump\_object\_data} (in {\tt symtab.cc}) \\
    Dumps all useful debugging information about a symbol table entry
    to {\tt stdout}.
\end{itemize}

No destructor is needed for {\tt symbol\_entry\_t}; once created, symbol
table entries remain allocated through the end of the compiler run.

\section*{Acknowledgments}

Michael Scott wrote the original version of the PL/0 compiler (and the {\tt
makeparse} and {\tt makescan} tools) in Pascal in the summer of 1992.  He
borrowed some of the code from his compiler for the Lynx programming
language, which in turn contained pieces of his undergraduate compiler
course project from the University of Wisconsin.  He based the general
structure of the parser and error repair routines on code written by Jon
Mauney to accompany the
distribution of {\tt fmq}.  In the fall of 1993 Micha\l\ Cierniak replaced
the original code generator (which produced a subset of C) with code to
generate MIPS assembly language.  Micha\l\ also introduced a simple code
improvement phase.  Galen Hunt re-wrote the compiler in C++ in the fall of
1994, introducing the {\tt symbol\_entry\_t} and {\tt syntax\_tree\_t}
class hierarchies, substantially simplifying code generation via overloaded
functions, and introducing a variety of other improvements.  Michael Scott
created the {\tt mungegrammar} tool in the summer of 1995, replacing an
earlier pre-processor (called {\tt prefmq}) that did not produce {\tt
tokens.h} or {\tt scangen.in}.

\bibliography{pragmatics}
\bibliographystyle{plain}

\end{document}