guide.tex

PL/0源码

\documentstyle[guide,sortbib,11pt]{article}

\thispagestyle{empty}

\begin{document}

\title{A Guide to the Rochester PL/0 Compiler
    \thanks{Copyright \copyright\ 1994--1999 Michael L. Scott}}

\author{Michael L. Scott\\[2ex]
Computer Science Department\\
University of Rochester}

\date{Revised July 1999}

\maketitle

Rochester's PL/0 compiler attempts to illustrate the
characteristics of a ``real'' compiler on a modest scale.
It runs on Unix systems and generates MIPS~I assembler.
Unlike many pedagogical
compilers, it has multiple passes, employs a table-driven scanner and
parser, performs high-quality syntax error repair, and issues
well-formatted diagnostic messages.  It does not
include any significant code improvement (optimization), though this
is planned for the future.  For now, it generates very poor code.

\section{The PL/0 Language}

The PL/0 compiler is small mainly because it compiles a very small
language.  PL/0 was defined by Niklaus Wirth (the inventor of Pascal
and Modula) as part of an extended example in his 1976 book, {\it
  Algorithms + Data Structures = Languages\/} (pp.\ 307--347).  It is
essentially a subset of Pascal, with nested procedures, but without
parameters; functions; case, for, or repeat statements; else clauses;
or any types other than integer.  The PL/0 compiler implements the
language exactly as defined by Wirth, with the addition of primitive
I/O.

\subsection{Tokens}

Case is insignificant in PL/0.  The PL/0 tokens are:

\begin{itemize}
\item keywords \\
  {\tt begin}, {\tt call}, {\tt const}, {\tt do}, {\tt
    end}, {\tt if}, {\tt odd}, {\tt procedure}, {\tt then}, {\tt var},
  {\tt while}.

\item identifiers \\
Any other string of letters and digits beginning
  with a letter.

\item numbers \\
  A string of (decimal) digits.

\item operators, relations, and punctuation marks \\ 
  {\tt +}, {\tt -}, {\tt *}, {\tt /}, {\tt =}, {\tt \#}, {\tt <}, {\tt
    >}, {\tt <=}, {\tt >=}, {\tt (}, {\tt )}, {\tt ,}, {\tt ;}, {\tt
    .}, {\tt :=}.
\end{itemize}

\subsection{Syntax}

In the EBNF below,
{\tt typewriter font} is used for tokens and {\em italicized font\/}
is used for non-terminals.  Bold parentheses are
used for grouping.  The vertical bar is used for alternation (``or'').
Bold curly brackets indicate an optional item.  A Kleene star (\kstar)
indicates that the preceding item can be repeated zero or more times.
Epsilon (\nothing) denotes the empty string.
White space (spaces, tabs, and newlines) is required in PL/0 programs to
separate characters that could otherwise be considered part of the same
token.  Otherwise, input is ``free format'': indentation and additional
white space are irrelevant.
\begin{grammar}
\item[program] block \lit{.}
\item[block]
    \lcurly \lit{CONST} \lit{identifier} \lit{=} \lit{number}
        \lparen \lit{,} \lit{identifier} \lit{=} \lit{number}
        \rparen\kstar\ \lit{;} \rcurly\\
    \lcurly \lit{VAR} \lit{identifier}
        \lparen \lit{,} \lit{identifier} \rparen\kstar\ \lit{;} \rcurly\\
    \lparen \lit{PROCEDURE} \lit{identifier} \lit{;}
        block \lit{;} \rparen\kstar\\
    statement
\item[statement]
    \lit{identifier} \lit{:=} expression\\
    \alt \lit{CALL} \lit{identifier}\\
    \alt \lit{BEGIN} statement \lparen \lit{;}
        statement \rparen\kstar\ \lit{END}\\
    \alt \lit{IF} condition \lit{THEN} statement\\
    \alt \lit{WHILE} condition \lit{DO} statement\\
    \alt \nothing
\item[expression]
    fragment \lparen
        \lparen \lit{+} \alt \lit{-} \alt \lit{*} \alt \lit{/} \rparen
        fragment \rparen\kstar
\item[fragment]
    \lit{identifier}
    \alt \lit{number}
    \alt \lparen {\tt +} \alt {\tt -} \rparen fragment
    \alt \lit{(} expression \lit{)}
\item[condition]
    \lit{ODD} expression
    \alt expression
        \lparen \lit{=} \alt \lit{\#} \alt \lit{<} \alt \lit{>}
        \alt \lit{<=} \alt \lit{>=} \rparen expression
\end{grammar}

\subsection{Semantics}

PL/0 is simple enough that semantic issues generally amount to common
sense.  The checks performed by the PL/0 compiler are listed in
section~\ref{sec-semantic-checks} below.  Constants, variables, and
procedures declared within a block are local to that block, and cannot
be referenced outside it.  The arithmetic operators associate
left-to-right.  Precedence is as follows: unary \code{+} and \code{-}
group most
tightly, followed by binary \code{*} and \code{/},
and then binary \code{+} and \code{-}.
Conditions (comparisons) are above the level of expressions in the
grammar, effectively giving them the lowest precedence of all.  The
symbol \code{\#} means ``not equal''.

Two special ``variables'' are pre-defined:  The variable \code{input},
when read, yields the next integer from the standard input stream.
The variable \code{output}, when written, produces an integer (with
trailing linefeed) on the standard output stream.

\section{Tools}

Construction and operation of the PL/0 compiler are assisted by a
number of tools, as illustrated in figure~\ref{fig-structure}.

\begin{figure}
\centerline{%\epsfysize 6in
\epsfbox{structure.eps}}
\caption{Construction and operation of the PL/O compiler.}
\label{fig-structure}
\end{figure}

\subsection{Scanner and Parser Generators}

{\tt Scangen} and {\tt fmq} are scanner and parser generators,
respectively.  They were written by students of Charles Fischer at the
University of Wisconsin around about 1980, and are described in detail in
appendices B, C, and E of Fischer and LeBlanc's book, {\it Crafting a
Compiler}.\footnote{Note that {\tt fmq} is
referred to as {\tt LLgen} in the book.  In the standard tool distribution,
{\tt llgen} is a version of {\tt fmq} without error repair.}
{\tt Scangen} takes as input a set of regular expressions, and produces DFA
tables (file {\tt tables}) to drive a scanner for the tokens described by
the regular expressions.  {\tt Fmq} takes as input a context free grammar,
and produces tables (file {\tt ptablebin}) to drive an LL(1) parser for
that grammar.  {\tt Fmq} takes its name from the Fischer/Milton/Quiring
syntax error repair algorithm, for which it also generates tables (file
{\tt etablebin}).

Both {\tt scangen} and {\tt fmq} produce numeric tables, in contrast to the
C code produced by Unix's standard {\tt lex} and {\tt yacc}.  ({\tt
Scangen} produces tables in {\sc ascii}.
{\tt Fmq} can produce tables in either {\sc ascii} or binary; the PL/0
compiler uses the binary option.)  These tables
are turned into initialized data structures by the tools {\tt makescan} and
{\tt makeparse}.  The C++ output files, {\tt scantab.cc} and {\tt
parsetab.cc} are then compiled by the GNU C++ compiler, {\tt g++}, with the
other C++ source files.  The files {\tt scantab.h} and {\tt parsetab.h}
contain definitions for variables exported by {\tt scantab.cc} and {\tt
parsetab.cc} respectively.

\subsection{Mungegrammar}

Several source files for the PL/0 compiler contain redundant information
about the PL/0 syntax.  These include the input to {\tt scangen} and {\tt
fmq} ({\tt scangen.in} and {\tt fmq.in}, respectively), semantic action
routine numbers (switch statement labels in {\tt actions.cc}), and
declarations of token numbers used in semantic analysis ({\tt tokens.h}).
To free the programmer from the need to keep these files mutually
consistent, they are all generated automatically by a preprocessor named
{\tt mungegrammar}.  The input to {\tt mungegrammar} is roughly a merger of
the input expected by {\tt scangen} and {\tt fmq}, with some syntactic
changes necessary to make the merger work and to simplify the specification
of long productions and action routines.  The {\tt grammar} file
distributed with the PL/0 compiler contains extensive self-descriptive
comments.  Read them carefully before making any changes.  Principal
features include the following:

\begin{itemize}
\item Ada-style (double dash through end-of-line) comments are allowed
  anywhere in the {\tt grammar} file.

\item Tokens are declared in a single list that includes alphabetic token
  names, optional character string images (for error messages), insertion
  and deletion costs (for syntax error repair), and lexical definitions
  (regular expressions).  A token may have {\em variants}, which will all
  appear the same to the parser, but may be distinguished by semantic
  action routines.  Variants are output as tokens with matching major token
  numbers in {\tt scangen.in}.

  Note the following limitations: the semicolon that terminates a token
  definition must be the last thing on its input line (other than white
  space or a comment).  Similarly, the comma that separates token variants
  must be the last thing (ther than white space or a comment) on its line,
  and a comma within a regular expression must {\em not\/} be the last thing
  (other than white space or a comment) on its line.

\item Two special token names {\em must\/} appear: \lit{IDENT} and
  \lit{SPACE}.  Reserve words must match the lexical definition of
  \lit{IDENT}, but appear in the token list with a double-quoted character
  string definition, rather than a regular expression.  \lit{SPACE} is the
  only token recognized by the scanner but not passed to the parser.

\item Semantic action routines can be embedded directly in productions,
  delimited by double square brackets (\verb|[[|\ldots\verb|]]|).  The
  code in {\tt actions.cc} will
  look better if you leave the square brackets on lines by themselves, but
  this is not required.

\item Second and subsequent lines of multi-line productions do not
  begin with ellipsis (\lit{\dots}), as they do in {\tt fmq.in}.  First
  lines of productions, however, must begin in column 1, and second and
  subsequent lines must not do so.
\end{itemize}

In addition to generating {\tt scangen.in} and {\tt fmq.in}, {\tt
mungegrammar} collects action routines into the arms of a large switch
statement, which it then embeds in a procedure named {\tt do\_action} in
file {\tt actions.cc}.  The parser calls {\tt do\_action} when it reaches
the appropriate point in the right-hand side of a production.  Finally,
{\tt mungegrammar} generates file {\tt tokens.h}, containing a definition
({\tt \#define}) for every major and minor token number.  Major token
numbers distinguish non-terminals in the context-free grammar understood by
the parser.  Minor token numbers distinguish token variants.  For example,
in PL/0 the multiplication and division operators play identical roles in
the grammar, and are therefore defined as variants of a single token named
MULOP.  {\tt Tokens.h} defines the symbol {\tt MAJ\_MULOP} to contain the
major token number for MULOP.  The two variants of MULOP are named TIMES
and SLASH, with minor token numbers {\tt MIN\_TIMES} and {\tt MIN\_SLASH},
respectively in {\tt tokens.h}.  The character string image for MULOP is
``*'', which the syntax error repair routines will use in error messages
when they insert a MULOP.  If an image is not provided, the repair routines
will use the token name.

With the exceptions noted above, the token definitions (regular expressions)
and productions in the {\tt grammar} file conform to the syntax expected by
{\tt scangen} and {\tt fmq}.  One potentially confusing feature is the
``\{TOSS\}'' annotation in regular expressions: it indicates that the
preceding character will not be important to the rest of the compiler, and
may be discarded by the scanner.  In general, characters of tokens that
represent only a single possible string (e.g.\ \lit{:=} or \lit{IF}) can
safely be tossed; characters of tokens for which there are many possible
strings (e.g.\ \lit{IDENT} or \lit{NUMBER}) should not be tossed.
Sometimes (e.g.\ in character strings, which are not present in PL/0 as
originally defined) it makes sense to toss some characters (the quote
marks) and save the rest.

\subsection{RCS}

I strongly recommend that you use RCS (the Revision Control System, developed
by Walter Tichy of Purdue University) to manage your compiler source.
As you make changes over time, RCS can be used to keep track of all the old
versions of all your files, in an organized and highly space-efficient way.
Read the man pages for {\tt ci}, {\tt co}, {\tt rcs}, {\tt rlog}, and 
{\tt rcsdiff}, in that order.

\subsection{The {\tt Makefile}}

Creation of the PL/0 compiler is automated by a {\tt Makefile}.
You should read the {\tt Makefile} and figure out how it works.
You should also learn to use the extra rules it provides, in addition to
{\tt make pl0}.
In particular, you will want to use the following:
\begin{description}

\item[{\tt make depend}]
This rule modifies the {\tt Makefile} itself to incorporate knowledge of
which files {\tt \#include} which others.
If you add or alter inclusions anywhere in the compiler, you will want to
re-run {\tt make depend}.

\item [{\tt make tags}]
This rule creates cross-reference indices (files {\tt tags} and {\tt
TAGS}), which are used by editors such as {\tt vi} and {\tt emacs} to assist
in source perusal.
Typing the appropriate command to the editor
will cause the cursor to move to the file and
line at which the identifier is declared.
In {\tt vi}, the command is {\tt :ta tag\_name},
or control-\verb|]| when the cursor is positioned on the identifier.
In {\tt emacs}, the command is meta-{\tt x find-tag} {\em tag-name},
or meta-{\tt .} {\em tag-name}.
If the cursor is on or near an identifier, {\tt emacs} will supply it
as a default when prompting for {\em tag-name}.
To pop back to the previous tag in {\tt vi}, type control-{\tt t}.
To pop back in {\tt emacs}, type meta-{\tt-} meta-{\tt x find-tag},
or meta-{\tt -} meta-{\tt .}.
Note that the algorithm used to build the tag cross-reference database is
heuristic; tags work most of the time but not always.
{\tt Vi} keeps track of a single location for each tag.
{\tt Emacs} keeps track of several possibilities, and jumps to the most
``likely'' one first. If you don't like that one and want to try the
next, type control-{\tt u} meta-{\tt .}.

In addition to creating cross-references for identifiers,
{\tt make tags} creates cross-ref\-er\-ences for action routines, grammar
symbols, and production numbers.
Tag search for a grammar symbol moves the cursor to a production in
the grammar in which that symbol appears on the left hand side.
Tag search for {\tt R37} (and similarly {\tt R$n$} for any 
appropriate $n$) moves to the 37th ($n$th) action routine.
This is useful for finding syntax errors in action routines, since the C++
compiler produces error messages for the file {\tt actions.cc}, not for
{\tt grammar}.
Tag search for {\tt P37} (in general P$n$) moves to the 37th ($n$th)
production in
the grammar. This is useful for debugging the parser, and shouldn't be
necessary unless you break something.

\item[{\tt make sources}]
This rule simply prints the names of all the source files required to build
the compiler.
It is useful when embedded in backward quotes in the argument lists of other
programs.
For example, 
\begin{verbatim}
    grep foobar `make sources`
\end{verbatim}
will find all occurrences of {\tt foobar} in the source of
the compiler.  Similarly, 
\begin{verbatim}
    ls -l `make sources` | grep "^\\-rw"
\end{verbatim}
will list all source files that are currently writable.
If you use RCS with strict locking, these will be the files that you have
checked out to make modifications.
If you don't want the long version of the listing,
\begin{verbatim}
    ls -l `make sources` | grep "^\\-rw" | awk '{print $8}'
\end{verbatim}