%\filename{SynChart-description.tex}
%\edited{by stolfi on Fri Dec 27 14:08:52 1985}
%\edited{by plass on January 13, 1986 12:15:02 pm PST}

% Description and user manual for SynChart.tex 
% (Michael Plass's syntax chart macros).

\input SynChart

\font\NonTerminalFont=amti10 \relax
\font\TerminalFont=amtt10 \relax
\font\KeywordFont=amtt10 \relax

\newdimen\Em
\rm \Em=1em

\def\syn#1{\hbox{\SyntaxChart#1}}
\def\yields{\hbox{$\Rightarrow$}}

\def\NTF{\NonTerminalFont}

\def\sox#1{\setbox#1\hbox}

\input QuoteTeX

\def\zero{\NonTerminal{zero\/\Strut}}
\def\one{\NonTerminal{one\/\Strut}}
\def\two{\NonTerminal{two\/\Strut}}
\def\three{\NonTerminal{three\/\Strut}}
\def\four{\NonTerminal{four\/\Strut}}

% This macro will put an example on one line if it fits, or on two if not.

% The next macro puts #1 and #2 on same line with \hfill in the middle if
% they fit; otherwise put each on a separate line, left-aligned

\def\wideexample#1#2{\relax
  \begingroup
    \setbox0=\hbox{$\vcenter{#1}$}
    \setbox2=\hbox{$\vcenter{#2}$}
    \dimen0=\wd0 \advance\dimen0 by \wd2
    \advance\dimen0 by 3.1\Em
    \ifdim \dimen0>\hsize \relax
      $$\vbox{\lineskip=5pt
          \hbox to \hsize{\quad\box0\hss}
          \hbox to \hsize{\quad\box2\hss}
         }
      $$
    \else
      $$\hbox to \hsize{\quad\box0\hss\box2\quad}$$
    \fi
  \endgroup
  }
\def\title#1{\par\centerline{\bf#1}\null}

\def\section#1{\medskip\noindent{\bf #1\ }\ignorespaces}

\parindent=1\Em

\dimen0=\hsize
\hsize=78mm
\advance\dimen0 by -\hsize
\advance\hoffset by 0.5\dimen0

\def\TeX{\hbox{T\hskip-.125em\lower.5ex\hbox{E}\hskip-.075em X}}

\title{CHARTING YOUR GRAMMAR WITH \TeX}
\centerline{\it Michael F. Plass}
\centerline{Xerox Corporation}
\vskip 10pt
\centerline{Adapted for \TeX{} 80 by \it J. Stolfi}
\centerline{DEC Systems Research Center}
\null

Are you one of those people who would rather look at a syntax chart
than a BNF grammar?  Do you avoid making a syntax chart for your
language because it is too hard to draw or too hard to typeset?  If
so, this is the article for you. Pay attention, and you will learn how
to use the macros below to create your own syntax charts with {\TeX}.

First some basics.  Every component of the syntax chart is enclosed
in a {\TeX} box, with the entry and exit points on the left and right
sides of the box, aligned with the baseline.  Usually the entry point
is on the left end and the exit is on the right, but not always, as
we shall see.

\section{Symbol boxes.} The simplest components are the boxes that
represent the terminals 
and the nonterminals of the language.  Terminals are the lowest
level pieces of the language that the description deals with, such
as keywords, special characters, letters, digits, and so forth.
Nonterminals are the names for the building blocks of the language.
Some examples of nonterminal symbols might be {\NTF number}, 
{\NTF identifier}, {\NTF expression}, {\NTF statement\/},
{\NTF program}.  If you are familiar with BNF, the
nonterminals are the things in the angle brackets.

The terminals in a syntax chart are enclosed in boxes with rounded
ends, and nonterminals are enclosed in rectangular boxes. This is
how you use the syntax chart macros to make both kinds of elementary
boxes:
  \sox4{|\Terminal{+}|}              \sox5{\syn{\Terminal{+}}}
  \sox6{|\NonTerminal{statement}|}   \sox7{\syn{\NonTerminal{statement}}}
  \sox8{|\Keyword{procedure}|}       \sox9{\syn{\Keyword{procedure}}}
\wideexample{\box4}{\hbox to \wd9{\hss\box5\hss}}
\wideexample{\box6}{\hbox to \wd9{\hss\box7\hss}}
\wideexample{\box8}{\box9}
(Keep in mind that the case of letters in a {\TeX} control sequence is
significant.) You can control what fonts are used inside these boxes by
declaring the macros |\TerminalFont|,
|\NonTerminalFont|, and |\KeywordFont| to be the appropriate font selectors.
Notice each of these basic boxes has `stems' on the left and right sides,
one of them being an arrow and the other one just a line.  {\TeX} will
determine which direction to point the arrow in on the basis of how the box
is nested inside of other constructions.  

\section{Definitions} of nonterminals are written like this:
\sox8{|\Define{Letter A}\Terminal{A}\EndDef|}
\sox9{\syn{\vbox{\advance\hsize by -3\Em\parindent0pt
    \Define{Letter A}\Terminal{A}\EndDef
  }}}
\wideexample{\box8}{\box9}

More complicated charts are built up by means of {\sl sequencing}, {\sl
alternation}, and {\sl repetition} of simpler charts.  To illustrate the
way these work, we will assume that the control sequence {|\one|} has been
defined to be {|\NonTerminal{one}|}, and so forth.  

\section{Sequencing} is easy to do; just put the subcharts together:
\sox8{|\one\two\three|}   \sox9{\syn{\one\two\three}}
\wideexample{\box8}{\vbox{\null\kern10pt\box9\kern10pt\null}}

\section{Alternation} is a bit more complicated to specify. Here is an example:
\sox8{|\Alternatives{
  \Upper{\one}
  \Middle{\two}
  \Lower{\three}
  \Lower{\four}}|}
\sox9{\syn{\Alternatives{
  \Upper{\one}
  \Middle{\two}
  \Lower{\three}
  \Lower{\four}
}}}
\wideexample{\box8}{\box9}

There may be any positive number of choices listed as the argument to
{|\Alternatives|}, and each choice is marked by enclosing it in braces and
preceding it with {|\Upper|}, {|\Middle|}, or {|\Lower|}.  Things marked
with {|\Upper|} go above the baseline, things marked with {|\Lower|} go
below the baseline, and something marked with {|\Middle|} goes on the
baseline.  It is permitted to omit any one of these three kinds of tags:
\sox8{|\Alternatives{
  \Middle{\one}
  \Lower{\two}
  \Lower{\three}}|}
\sox9{\syn{\Alternatives{
  \Middle{\one}
  \Lower{\two}
  \Lower{\three}
}}}
\wideexample{\box8}{\box9}
\sox8{|\Alternatives{
  \Upper{\one}
  \Upper{\two}
  \Lower{\three}}|}
\sox9{\syn{\Alternatives{
  \Upper{\one}
  \Upper{\two}
  \Lower{\three}
}}}
\wideexample{\box8}{\box9}
\sox8{|\Alternatives{
  \Upper{\one}
  \Upper{\two}
  \Middle{\three}}|}
\sox9{\syn{\Alternatives{
  \Upper{\one}
  \Upper{\two}
  \Middle{\three}
}}}
\wideexample{\box8}{\box9}

Sometimes a stack of alternatives can get very tall; in this case it
might be better to spread them out horizontally:
\sox8{|\HorzAlternatives{
  \Alternative{\one}
  \Alternative{\two}
  \Alternative{\three}}|}
\sox9{\syn{\HorzAlternatives{
  \Alternative{\one}
  \Alternative{\two}
  \Alternative{\three}
}}}
\wideexample{\box8}{\box9}
This one is especially appropriate for a long list of short choices.

\section{Repetition} is specified in almost exactly the same way as
alternatives: 
\sox8{|\Repeat{
  \Upper{\one}
  \Middle{\two}
  \Lower{\three}}|}
\sox9{\syn{\Repeat{
  \Upper{\one}
  \Middle{\two}
  \Lower{\three}
}}}
\wideexample{\box8}{\box9}

The same rules apply as before, except that you are not allowed to leave
out the {|\Middle|}.  This is not the same as specifing an
empty middle, which you might often want to do:
\sox8{|\Repeat{
  \Upper{\one}
  \Middle{}}|}
\sox9{\syn{\Repeat{\Upper{\one}\Middle{}}}}
\wideexample{\box8}{\box9}
\sox8{|\Repeat{
  \Middle{\one}
  \Lower{}}|}
\sox9{\syn{\Repeat{\Middle{\one}\Lower{}}}}
\wideexample{\box8}{\box9}

Now you know all the essential constructions.  They can be nested in any way
you please, up to any depth (subject only to TeX's memory limitations).

\section{To use the macros,} say |\input SynChart| near the
beginning of your file.  When you actually want to make a chart, say
{|\SyntaxChart|} to set up the baselineskip, lineskip, and some
other stuff.  If you are mixing syntax charts with other text, you will
want to enclose the {|\SyntaxChart|} along with the chart
definition in braces, so all the funny definitions go away at the end of
the group and don't mess up the rest of your document.  You will probably
also want to say {|\parindent 0pt|} to eliminate the paragraph
indentation.

The call on {|\SyntaxChart|}  also tells {\TeX} to ignore
tabs and carriage returns so you can format your input more easily.
Just be careful where you add spaces---after a control sequence is OK,
but not between or after the parameters to a macro.  The reason for not
ignoring spaces is so terminals and nonterminals can have embedded
spaces; if you prefer, you can say {|\IgnoreWhiteSpace|} to
cause spaces to be ignored too, and then put in a control-space
where you really want a space.

Now would be a good time to go try making your own simple syntax chart,
using the macro definitions in Appendix A.  When defining a complex
diagram, it is often helpful to first define pieces of it as {\TeX} macros.
This makes the source much easier to read, and keeps the nesting of braces
down to a reasonable level.  This device is used extensively in the example
in Appendix B.  You may also consider saving away a frequently 
used subchart in a box register, and copy it when building more
complex charts. 

\centerline{\hbox{*}}

Now that you have a firm grasp of the essentials, here are some fine points
you may like to know:

\section{Horizontal spacing.} The horizontal lines are actually composed of
fixed-width rules and leaders filled with rules.  The control sequence
{|\ULine|} defines a fairly short fixed-width line, and {|\UULine|} defines
one twice as long.  In general, |\HLine |$\langle$dimen$\rangle$ gives an
horizontal line of the specified length.  {|\Fil|} defines a line that
stretches like glue, with a normal length of zero and the same
stretchability as {|\hfil|}; {|\Fill|} is similar, but with the
stretchability of an {|\hfill|}.  

The macro |\DefaultFil| gives a line line with stretchabilility
|1000pt|. It is implicitly inserted on both sides of every branch of a
repetition or (vertical) alternation.  Therefore, if the
branches are not all the same width, the shorter ones will be
horizontally centered.  A |\DefaultFil|
is also implicitly inserted at the
end of the |\Define| (and of each line of a multi-line chart).
Note that any |\Fil| or |\Fill| you insert will override all the
|\DefaultFil|s.  By using these macros in various combinations, you can get
any kind of horizontal spacing you want.  

\section{Vertical spacing.}
The register {|\AltSpacing|} specifies how many `units of
space' should be inserted between adjacent branches of
{|\Alternatives|} or {|\Repeat|}.  The `unit of space'
here is the radius of the circular arcs used as joints.  The default
setting is {|\AltSpacing=2|}, which gives space equal to the 
height of a symbol box. You can change this default by typing,
for example,
\sox8{|\Alternatives{
  \AltSpacing=1
  \Upper{\one}
  \Middle{\two}
  \Lower{}
  \Lower{\three}}|}
\sox9{\syn{\Alternatives{
  \AltSpacing=1
  \Upper{\one}
  \Middle{\two}
  \Lower{}
  \Lower{\three}
}}}
\wideexample{\box8}{\box9}
or
\sox8{|\Alternatives{
  \AltSpacing=3
  \Upper{\one}
  \Middle{\two}
  \Lower{}
  \Lower{\three}}|}
\sox9{\syn{\Alternatives{
  \AltSpacing=3
  \Upper{\one}
  \Middle{\two}
  \Lower{}
  \Lower{\three}
}}}
\wideexample{\box8}{\box9}

\section{Symbol alignment.}
The macros |\NonTerminal|, |\Terminal|, and |\Keyword| will raise or lower
their argument until its \TeX{} bounding box is centered with respect to
the enclosing frame. This looks fine if the symbols include only digits
and upper-case leters.  However, if the same thing is done for lower case
letters, the baselines of the words in different boxes may not line up due
to the pattern of ascenders and descenders.  This problem is solved by the
macro |\Strut|, which produces a zero-width box whose height and depth
match the extremes of the font.  If the keywords in your language are in
lower case, say {|\Strut|} after the arguments to |\Keyword| --- better
yet, define a macro that does this, as in Appendix B.  The same applies to
|\NonTerminal|. Compare the examples
\sox4{|\Keyword{go}\Keyword{to}|} 
\sox5{\syn{\Keyword{go}\Keyword{to}}}
\wideexample{\box4}{\box5}
\sox6{|\Keyword{\Strut go}\Keyword{\Strut to}|}
\sox7{\syn{\Keyword{\Strut go}\Keyword{\Strut to}}}
\wideexample{\box6}{\box7}

A similar problem arises when |\Terminal| is used for
mathematical symbols such as
$+$ and $<$, which in most \TeX{} fonts 
are not vertically centered with respect to
their bounding boxes. Moreover, some characters
like `|.|' and `|^|' are hard to recognize when vertically centered.
Those problems are usually fixed by
including in the argument the macro |\OpStrut|, which produces a 
zero-width box with the height and width of an open parenthesis.
Compare
\sox4{|\Terminal{+}|}\sox5{\syn{\Terminal{+}}}
\wideexample{\box4}{\box5}
\sox4{|\Terminal{\OpStrut+}|}\sox5{\syn{\Terminal{\OpStrut+}}}
\wideexample{\box4}{\box5}
\sox6{|\Terminal{.}|}\sox7{\syn{\Terminal{.}}}
\wideexample{\box6}{\box7}
\sox6{|\Terminal{\OpStrut.}|}\sox7{\syn{\Terminal{\OpStrut.}}}
\wideexample{\box6}{\box7}

\section{Bigger circles.}
To get bigger symbol boxes and wider turns, like the ones below,
\sox4{\syn{\BigCircles 
    \one\Alternatives{\Upper{\Terminal{+}}\Middle{\two}\Lower{\Keyword{plus}}}
    \three
}}
\wideexample{\box4}{\null}
say |\BigCircles| right after |\SyntaxChart|.

\section{Multi-line charts.}
If a chart gets too wide to fit in the page, you can break it in two (or more)
lines by using |\NewLine|, as shown below:
\sox4{|\Define{Test}
  \one\two
  \NewLine
  \three
\EndDef|}
\sox5{\syn{\vbox{\advance\hsize by -3\Em\parindent0pt
  \Define{Test}
    \one\two
    \NewLine
    \three
  \EndDef}}}
\wideexample{\box4}{\box5}

The macro |\OptionalLines| is useful when you want to construct
a sequence several items, where each item can be omitted:
\sox4{|\Define{Test}
  \zero
  \OptionalLines{
    \Line{\one}
    \Line{\two}
  }
  \three
\EndDef|}
\sox5{\syn{\vbox{\advance\hsize by -3\Em\parindent0pt
\Define{Test}
  \zero
  \OptionalLines{\Line{\one}\Line{\two}}
  \three
\EndDef}}}
\wideexample{\box4}{\box5}
Note that |\NewLine| and |\OptionalLines| can only
appear at the top level of a |\Define|; they cannot be used inside 
alternations or repetitions.

The length of lines produced by |\NewLine| and |\OptionalLines|
is determined by the parameter |\MinLineWidth|.
Every line but the last is stretched until its width (including 
the connectors on the sides) is greater than |\MinLineWidth|
(the last line is always stretched to |\hsize|).
The default is zero, which 
means that those lines will be typeset with their natural width, so
that |\Fil| and |\Fill| will not work in those lines.  

\section{Omitting arrows.}
Instead of breaking a chart into lines, you may try saying
|\OmitRightArrows| after |\SyntaxChart|, as is done in appendix B.
This removes all right-going arrows on the input side of symbol boxes.
As a last resort, |\OmitAllArrows| will remove also the
left-going ones.  In that case, you may wish to explicitly insert
|\Arrow|s and/or |\BigArrow|s in a few key places: 
\sox8{|\OmitRightArrows 
\Alternatives{ 
  \Upper{\one}
  \Middle{\Arrow}
  \Lower{\two}}|}
\sox9{\syn{\OmitRightArrows
    \Alternatives{\Upper{\one}\Middle{\Arrow}\Lower{\two}}
  }}
\wideexample{\box8}{\box9}

\vfill\bye