  % -*- Mode:TeX -*-

%%% First draft of a document for PAGEN.

\documentstyle[11pt,inchmar]{article}

%\input{laktex}
%\input{lispdoc}

% short forms for ``i.e.'', ``e.g.'', ``etc.''
\newcommand{\ie}{{\em i.e.,\/}}
\newcommand{\eg}{{\em e.g.,\/}}
\newcommand{\etc}{{\em etc.\/}}

\newcommand{\term}[1]{{\tt #1}}
\newcommand{\bslash}{\mbox{\tt $\backslash$}}

\title{PAGEN --- PArser GENerator for Common Lisp}
\author{Program: Ken Traub, Documentation: Jamey Hicks}

% Allow @ in control sequence names  
\makeatletter

%%% Environments:

%%% The example environment.   This is similar to verbatim, but only treats end
%%% of line and space as verbatim; control sequences, braces, and such work as
%%% before.  One situation in which this is useful is when you want to include
%%% italic text.  Unfortunately, if you include {\it stuff} the space between
%%% \it and stuff is typeset, since spaces are treated verbatim.  One way to
%%% avoid this is to type {\it{}stuff}.  A better way is to say \i{stuff}; \i
%%% is defined within example for just this purpose.

%%% We reuse as much LaTeX code as possible -- in a sneaky way by making
%%% \dospecials be a no-op, thus preventing the deactivation of the special
%%% characters.  Because special characters still work, we don't need the
%%% hackery needed by \endverbatim.
%%% Adjacent lines of an example environment get \examplepenalty inserted
%%% between them.  Beginning a line with \hinge removes the immediately
%%% preceding penalty.  Thus, setting \examplepenalty to 10000 prevents
%%% line breaks except between lines separated by \hinge.
\newcount\examplepenalty
\examplepenalty=0
\def\example{%
  \def\{{\relax\char`\{}%
  \def\}{\relax\char`\}}%
  \let\temp=\dospecials\let\dospecials=\relax
  \let\@@@par=\@@par
  \def\@@par{\@@@par\penalty\examplepenalty}%
  \@verbatim
  \def\hinge{\penalty0\relax}%
  \let\dospecials=\temp
  \def\i##1{{\it ##1}}%
  \def\t##1{{\tt ##1}}%
  \def\b##1{{\bf ##1}}%
  \frenchspacing\@vobeyspaces}
\def\endexample{\penalty0\endtrivlist}

%%% Environment vtrivlist are designed to provide the same vertical spacing
%%% of trivlist, but instead of having items in its body should just contain
%%% vertical mode material.  Quite often the vertical mode material is just an
%%% alignment.
\def\vtrivlist{%
  \@topsep\topsep
  \advance\@topsep\partopsep
  \advance\@topsep\parskip
  \vskip\@topsep}
\def\endvtrivlist{%
  \@topsep\topsep
  \advance\@topsep\partopsep
  \vskip\@topsep}

% Restore @ to "other" status.
\makeatother

%%% Defines environment: BNF style definitions
%%% Control sequences:
%%%   \is             - Separates LHS from RHS.
%%%   \Or             - Separates alternatives.
%%%   \OR             - Separates alternatives and continues on next line.
%%%   \NEWLINE        - Continues entry on next line.
%%%   \\              - Terminates an entry.
%%%   \arbno{foo}     - Zero or more occurences of nonterm `foo'.
%%%   \ntimes{n}{foo} - N occurences of nonterm `foo'.
%%%   \term{foo}      - Terminal symbol `foo'.
%%%   \nterm{foo}{n}  - Terminal symbol `foo', whose value is called `n'.
%%%   \tok{foo}       - Token named `foo'.
%%%   \Long           - Precedes line with unusually long LHS; this LHS won't
%%%                     affect the alignment of other entries.
%%% Example:
%%%   \begin{defines}
%%%     contents \is dm-contents \Or im-contents \\
%%%     module \is \arbno{record}\\
%%%     \Long define-broadcast-area-record \is \tok{define-area} name mtype
%%%       pe pe pe \NEWLINE address address address bool \\
%%%   \end{defines}
\newcommand{\equals}{$=$}
\def\defines{%
  \def\par{}%                                   % Allows gratuitous blank lines.
  \def\\{\cr\noalign{\penalty5000}}%
  \def\blankline{\noalign{\penalty0\vskip\baselineskip}}%
  \def\is{&$\rightarrow$&}%
  \def\equals{&$=$&}
  \def\Or{{$|$} }%
  \def\OR{\Or\NEWLINE}%
  \def\NEWLINE{\cr\noalign{\penalty10000}&&}%
  \def\arbno##1{$\lbrace\hbox{##1}\rbrace^*$}%
  \def\ntimes##1##2{$\lbrace\hbox{##2}\rbrace^{##1}$}%
  \def\nterm##1##2{$\hbox{\tt ##1}(##2)$}%      % Named terminal
  \def\term##1{{\tt ##1}}%
  \def\tok##1{{\tt <##1>}}%
  %% \spaceskip=0.5em in \Long and in the template so that there's more space
  %% between things on the RHS.
  \def\Long{\multispan3\sc
            \def\is{\unskip\quad$\rightarrow$\quad\spaceskip=0.5em\relax}%
            \def\\{\hfil\cr\noalign{\penalty5000}}%
            \def\NEWLINE{\hfil\cr\noalign{\penalty10000}&&}}%
  \begin{vtrivlist}
    \halign\bgroup
      \sc##\hfil&\quad\hfil##\hfil\quad&\sc\spaceskip=0.5em\relax##\hfil\cr}
\def\enddefines{%
      \crcr
      \noalign{\penalty0}%
    \egroup
  \end{vtrivlist}}

\begin{document}

\maketitle

PAGEN is a parser generator for Common Lisp\cite{cltl}.  It takes a
definition of a grammar and generates tables for a table driven scanner
and parser.  Both PAGEN itself and the resulting scanner/parser are
written in Common Lisp.

\section{PAGEN Input}

 A PAGEN grammar definitions is similar to a Backus-Nauer Format (BNF)
grammar definition, with a few extensions (shorthand for common cases).

The PAGEN input file consists of a series of statements that do such
things as tell what machines to generate scanners for, what package the
resulting file should be in, \etc.  The grammar for PAGEN itself is
defined by a PAGEN file, and PAGEN generated the parser for PAGEN.

In this document, I will give the grammar for PAGEN in BNF.
Appendix{pagen-pagen} contains the PAGEN file for PAGEN's grammar.
Terminals will be written as \term{terminal}.

\section{Grammar}

 A PAGEN grammar definition consists of a series of statements.  Each
statement starts with a PAGEN keyword, and may be on more than one line.
Keywords in PAGEN start with a `\$' sign and are case-insensitive.

\section{Lexical Analyzer}

The lexical analyzer, or scanner, is defined by a series of lexical statements.

\subsection{Target Statement}

The {\tt target} statement specifies what target language/OS pairs to
make scanners for.  Some targets have different character sets from
others, and so a mapping from native character codes to internal
character codes will be made for each target.  In addition, characters
that are indistinguishable in the grammar, \eg, whitespace characters,
will be mapped to the same internal code in order to compact the scanner
tables.

\begin{defines}
target-statement \is \term{\$target} \term{identifier} \\
\end{defines}

The targets are: {\tt lispm} and {\tt unix}.

\subsection{Regular Expressions}

Lexical tokens are defined by regular expressions.  The scanner runs
along the input stream, and finds the largest match against one of the
lexical token's regular expressions, and then returns the correct kind
of lexical token.

\begin{defines}
\term{identifier} \equals alpha \arbno{(alpha \Or digit)} \\
\term{set} \equals ``\{'' \arbno{(set-contents \Or ``\bslash'' any)} ``\}'' \\
\term{string} \equals ``\verb|"|'' \arbno{(string-contents \Or ``\bslash'' any)} ``\verb|"|'' \\
\term{caseless-string} \equals ``\verb|`|'' \arbno{(caseless-string-contents \Or ``\bslash'' any)} ``\verb|'|'' \\
\end{defines}

The definitions of {\em alpha}, and {\em digit} are self explanatory.
{\em Any} means any character in the character set.  {\em Set-contents}
is any character except right brace (\verb"}") and backslash, unless
these are quoted with the escapes character, backslash.  {\em
String-contents} is any character except double-quotes and backslash.  {\em
Caseless-string-contents} is any character except close-quote and backslash.

\begin{defines}
regular-expression \is disjunction-expression \\
\\
disjunction-expression \is concatenation-expression \\
disjunction-expression \is disjunction-expression "|" concatenation-expression \\
\\
concatenation-expression \is multiple-expression \\
concatenation-expression \is concatenation-expression multiple-expression \\
\\
multiple-expression \is primary-regular-expression \\
multiple-expression \is multiple-expression "*" \\
multiple-expression \is multiple-expression "+" \\
\\
primary-regular-expression \is identifier \\
primary-regular-expression \is set \\
primary-regular-expression \is string \\
primary-regular-expression \is caseless-string \\
primary-regular-expression \is "\~" primary-regular-expression \\
primary-regular-expression \is "(" primary-regular-expression ")" \\
\end{defines}

As in BNF, ``{\tt *}'' means zero or more occurences of the preceding
regular expression (Kleene recursion), and ``{\tt +}'' means at least on
occurence of the preceding regular expression.

\subsection{Let Statements}

A {\tt let} statement maps an identifier to a regular expression for use
in definition of lexical tokens.

\begin{defines}
let-statement \is \term{\$let} \term{identifier} = regular-expression \\
\end{defines}

\subsection{Lexical Tokens}

There are three kinds of lexical tokens in Pagen: {\em terminals},
{\em pseudo-terminals}, and {\em discards}.

\begin{defines}
terminal-statement \is \term{\$terminal} \term{identifier} = regular-expression \\
pseudo-terminal-statement \is \term{\$pseudo} \term{identifier} = regular-expression \\
discard-statement \is \term{\$discard} \term{identifier} = regular-expression \\
\end{defines}

A terminal is just a lexical token, used by the parser.  Discard tokens
are recognized by the scanner and then discarded.

A pseudo-terminal, is used by the parser in parsing, but also becomes a
ptnode itself.  For instance, {\em identifiers} are pseudo-terminals ---
the {\tt ptnode-value} of an identifier is the string of characters that
names the identifier.  Pseudo-terminals have values that are used during
the static-analysis phase of compilation.

\section{The Parser}

The parser is defined by a series of grammar statements.  There are four
kinds of grammar statements:
 \begin{description}
\item[significant]
 This defines a normal production.  When the parser reduces this
production it makes a ptnode whose tag is derived from the name of this
production, and leaves the new ptnode on the stack.

\item[no-node]
 This defines a {\em linear} production, that is, the right hand side
contains only one non-terminal.  It is used for parsing, but it really
conveys no useful information beyond the parser, so no ptnode is made
for this production.  For example:
\begin{verbatim}
     $no-node primary-regular-expression -> identifier
\end{verbatim}
 When the parser reduces the identifier to a primary-regular-expression,
it just leaves the identifier on the stack instead of making a
primary-regular-expression ptnode out of it.

\item[n-ary]
 This is an extension to the normal syntax of context-free grammars.
For example, the statement
\begin{verbatim}
     $n-ary   tuple-expression -> expression $separated-by ","
\end{verbatim}
 defines {\em tuple-expression} to be any number of {\em expressions}
separated-by commas.  This production takes the place of a number of
simpler productions.  The ptnode formed will have as its children a list
of all the child ptnodes that were separated by the separator tokens.

 To specify a number of non-terminals separated by whitespace, use the
following format.
 \begin{verbatim}
     $n-ary   production-rhs -> production-rhs-primary $separated-by
\end{verbatim}

\item[n-ary-1]
 The {\tt n-ary-1} is a combination of {\tt n-ary} and {\tt no-node}.
If there is at least one separator token, then it behaves like an {\tt
n-ary} production.  If there is no separator, then it behaves like a
{\tt no-node} production.  This is what we actually use for {\em
tuple-expressions}:
\begin{verbatim}
     $n-ary-1  tuple-expression -> expression $separated-by ","
\end{verbatim}

\end{description}

\subsection{Places}

\subsection{Acceptance Statement}

The acceptance statement tells the parser what to return as a parse
tree.  When the parser is called, it will parse until it processes the
accept production, and return the parse tree.  There are two forms: {\em
accept} and {\em accept-each}.  The identifier below names a
non-terminal in the grammar being defined.

\begin{defines}
accept-statement \is \term{accept} \term{identifier} \\
accept-each-statement \is \term{accept-each} \term{identifier} \\
\end{defines}

The {\em accept} form means that the whole file or stream must parse
into exactly one parse-tree.  The {\em accept-each} form means that the
parser can be called repeatedly until the file is empty.  Each time the
parser is called, it will parse and return one parse-tree.


\section{Using PAGEN}

\subsection{Installation}

Load the tape onto your file system, in the root directory of Id World.  

You can load PAGEN by doing the following:
\begin{verbatim}
    (load "../pagen/pagen.system")
    
    (defprogram:make-program 'pagen :load)
\end{verbatim}

\subsection{Running Pagen}

First, make a grammar definition, in a pagen file (extension {\tt ".pagen"}).

Then:
\begin{example}
    (pagen:pagen \i{file})
\end{example}
 will generate a file with the extension {\tt ".pagen-output"} that
contains the tables for the scanner and parser, plus the functions that
perform the shifts and reductions in the parser.  This file will include
an {\tt in-package} statement naming the package specified by the
package-statement in the PAGEN file.

\subsection{Using the Parser}

 The parser should be in a package that {\em uses} the Lisp and DFCS
package.  See the {\em DFCS: Dataflow Compiler Substrate Manual} for
support manipulating parse trees.  

 Also, see the file: {\tt "parser.lisp"}, {\tt "parser-tables.lisp"} and
{\tt "grammar.lisp"} in the id-compiler directory.


\bibliographystyle{plain}
\bibliography{jamey}

\end{document}
