% Copyright 2012-2020, Alexander Shibakov
% Copyright 2002-2014 Free Software Foundation, Inc.
% This file is part of SPLinT
%
% SPLinT is free software: you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation, either version 3 of the License, or
% (at your option) any later version.
%
% SPLinT is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details.
%
% You should have received a copy of the GNU General Public License
% along with SPLinT.  If not, see <http://www.gnu.org/licenses/>.

\ifbootstrapmode % this is a bootstrap run to extract the states
    \message{bootstrapping \jobname.tex ...}%
    \input limbo.sty
    \def\optimization{5}
    \input yy.sty
    \modebootstrap
\fi

@**The \eatone{bison}\bison\ parser stack.
The input language for \bison\ loosely follows the {\sc BNF} notation, with
a few enhancements, such as the syntax for {\em actions}, to implement
the syntax-directed translation@^syntax-directed translation@>, as
well as various declarations for tokens, nonterminals, etc.

On the one hand, the language is relatively easy to handle, is
nearly whitespace agnostic, on the other, a primitive parser is
required for some basic setup even at a very early stage, so the
design must be carefully thought out. This {\em
bootstrapping\/}@^bootstrapping@> step is discussed in more details
later on.

The path chosen here is by no means optimal. What it lacks in
efficiency, though, it may amply gain in practicality, as we reuse the
original grammar used by \bison\ to produce the parser(s) for both
pretty printing and bootstrapping. Some minor subtleties arising from
this approach are explained in later sections.

As was described in the
\ifbootstrapmode\else\locallink{parser.stacks} discussion of parser
stacks \endlink\fi@^parser stack@> above, to pretty print a variety
of grammar fragments, one may employ
a {\em parser stack\/} derived from the original grammar. The most
natural and common unit of a \bison\ grammar is a set of
productions. It is thus natural to begin our discussion of the parsers
in the \bison\ stack with the parser responsible for processing
individual rules.

One should note that the productions below are not concerned with the
typesetting of the grammar. Instead this task is delegated to the
macros in \.{yyunion.sty} and its companions. The first pass of the
parser merely constructs an `executable abstract syntax tree' (or
\EAST\footnote{One may argue that \EAST\ is still merely a syntactic
construct requiring a proper macro framework for its execution and
should be called a `weak executable syntax tree' or \WEST. This
acronym extravagnza is heading south so we shall stop here.}) which
can serve very diverse purposes: from collecting token declarations in
the boostrapping pass to typesetting the grammar rules.

It would be impossible to completely avoid the question of the visual
presentation of the \bison\ input, however. It has already been
pointed out that the syntax adopted by \bison\ is nearly insensitive
to whitespace. This makes {\em writing\/} \bison\ grammars easier. On
the other hand, {\em presenting\/} a grammar is best done using a
variety of typographic devices that take advantage of the meaningful
positioning of text on the page: skips, indents, etc. Therefore, the
macros for \bison\ pretty printing trade a number of \bison\ syntax
elements (such as \.{\yl}, \.{;}, action braces, etc.) for the careful
placement of each fragment of the input on the page. 

Let's take a short break for a broad overview of the input file. 
The basic structure is that of an ordinary \bison\ file that produces
plain \Cee\ output. The \Cee\ actions, however, are programmed to output \TeX.
The \bison\ sections (separated by \.{\%\%} (shown (pretty printed)
as \prodstyle{\%\%} below)) appear between the successive dotted lines.

@(bg.yy@>=
@G Switch to generic mode.
%{@> @<Grammar parser \Cee\ preamble@> @=%}
 @>  @<Grammar parser \bison\ options@> @= 
%union {@> @<Union of grammar parser types@> @=}
%{@> @<Grammar parser \Cee\ postamble@> @=%}
 @>  @<Tokens and types ...@> @= 
%%
 @>  @<Fake start symbol for rules only grammar@> @= 
 @>  @<Parser common productions@> @= 
 @>  @<Parser grammar productions@> @= 
%%
@g

@ Bootstrap\namedspot{bootstrapping}@^bootstrapping@> mode is next.
The reason for a separate bootstrap parser is to
collect the minimal amount of information to `spool up' the `production'
parsers. To understand the mechanics and the reasons behind it, consider what happens
following a declaration such as \.{\%token TOKEN "token"}
(or, as it would be typeset by the macros in this package
`\prodstyle{\%token} \.{TOKEN} \.{token}'; see the index entries for
more details)%
\idxinline{TOKEN}\idxinline{token}. 
The two names for the same token are treated very differently. \.{TOKEN} becomes
an |enum| constant in the \Cee\ parser generated by \bison. Even when
that parser becomes part of the `driver' program that outputs the \TeX\
version of the parser tables, there is no easy way to output the {\it
names\/} of the appropriate |enum| constants. The other name
(\.{"token"}) becomes an entry in the |yytname| array. These names
can be output by either the `driver' or \TeX\ itself after the
\.{\\yytname} table has been input. The scanner, on the other hand,
will use the first version (\.{TOKEN}). Therefore, it is important to
establish an equivalence between the two versions of the name. In the
`real' parser, the token values are output in a special header
file. Hence, one has to either parse the header file to establish the
equivalences or find some other means to find out the numerical values
of the tokens. 

One approach is to parse the file containing the {\it declarations\/}
and extract the equivalences between the names from it. This is the
function of the bootstrap parser. Since the lexer is reused, some
token values need to be known in advance (and the rest either ignored
or replaced by some `made up' values). These tokens are `hard coded'
into the parser file generated by \bison\ and output using a special
function. The switch `|@[#define@]@; BISON_BOOTSTRAP_MODE|' tells the
`driver' program to output the hard coded token values. 
@q Bizarre looking way of typing #define is due to the awkward way@>
@q \CWEB\ treats switching in and out of $-mode in inline \Cee@> 

Note that the equivalence of the two versions of token names would
have to be established every time a `string version' of a token is
declared in the \bison\ file and the `macro name version' of the token
is used by the corresponding scanner. To establish this equivalence,
however, the bootstrapping parser below is not always necessary (see
the \.{xxpression} example, specifically, the file \.{xxpression.w} in
the \.{examples} directory for an example of using a different parser
for this purpose). The reason it is necessary here is that a parser
for an appropriate subset of the \bison\ syntax is not yet available
(indeed, {\it any\/} functional parser for a \bison\ syntax subset
would have to use the same scanner (unless you want to write a custom
scanner for it), which would need to know how to output tokens, for
which it would need a parser for a subset of \bison\ syntax $\ldots$
it is a genuine `chicken and egg' problem). Hence the need for
`bootstrap'. Once a functional parser for a large enough subset of the
\bison\ input grammar is operational, {\it it\/} can be used to pair
up the token names. 

The second function of the bootstrap parser is to collect information
about the scanner's states. The mechanism is slightly different for
states. While the token equivalences are collected purely in
`\TeX\ mode', the bootstrap parser collects all the state names into a
special \Cee\ header file. The reason is simple: unlike the token
values, the numerical values of the scanner states are not passed to
the `driver' program in any data structure and are instead defined as
ordinary macros. The header file is the information the `driver' file
needs to output the state values.

An additional subtlety in the case of the state value output is that the
main lexer for the \bison\ grammar utilizes states extensively and thus
cannot be easily used with the bootstrap parser before the state
values are known. The solution is to substitute a very simple scanner barely
capable of lexing state declarations. Such a scanner is implemented
in \.{ssffo.w} (the somewhat cryptic name stands for `{\bf s}imple {\bf s}canner 
{\bf f}or {\bf f}lex {\bf o}ptions').
@(bb.yy@>=
@G Switch to generic mode.
%{
 @> @<Grammar parser \Cee\ preamble@> @= 
 @> @/#define BISON_BOOTSTRAP_MODE @= 
%}
 @> @<Grammar parser \bison\ options@> @= 
%union {@> @<Union of grammar parser types@> @=}
%{@> @<Bootstrap parser \Cee\ postamble@> @=%}
 @> @<Tokens and types ...@> @= 
%%
 @> @<Fake start symbol for bootstrap grammar@> @= 
 @> @<Parser bootstrap productions@> @= 
 @> @<\flex\ options parser productions@> @= 
 @> @<List of symbols@> @= 
 @> @<Definition of \prodstyle{symbol}@> @= 
%%
@g

@ The prologue parser is responsible for parsing various grammar
declarations as well as parser options.
@(bd.yy@>=
@G Switch to generic mode.
%{@> @<Grammar parser \Cee\ preamble@> @=%}
  @> @<Grammar parser \bison\ options@> @= 
%union {@> @<Union of grammar parser types@> @=}
%{@> @<Grammar parser \Cee\ postamble@> @=%}
  @> @<Tokens and types ...@> @= 
%%
  @> @<Fake start symbol for prologue grammar@> @= 
  @> @<Parser common productions@> @= 
  @> @<Parser prologue productions@> @= 
%%
@g

@ The full \bison\ input parser is used when a complete \bison\ file is
expected. It is also capable of parsing a `skeleton' of such a file,
similar to the one that follows this paragraph.
@(bf.yy@>=
@G Switch to generic mode.
%{@> @<Grammar parser \Cee\ preamble@> @=%}
  @> @<Grammar parser \bison\ options@> @= 
%union {@> @<Union of grammar parser types@> @=}
%{@> @<Grammar parser \Cee\ postamble@> @=%}
  @> @<Tokens and types ...@> @= 
%%
  @> @<Parser common productions@> @= 
  @> @<Parser prologue productions@> @= 
  @> @<Parser grammar productions@> @= 
  @> @<Parser full productions@> @= 
%%
@g

@ \namedspot{bison.options}The first two options below are essential
for the parser operation
as each of them makes \bison\ produce additional tables (arrays) used
in the operation (or bootstrapping) of \bison\ parsers. The
start symbol can be set implicitly by listing the appropriate
production first. Modern \bison\ also allows specifying the kind of
parsing algorithm to be used (provided the supplied grammar is in the
appropriate class): {\sc LALR}($n$), {\sc LR}($n$), {\sc GLR}, etc.
The default is to use the {\sc LALR}($1$) algorithm (with the
corresponding assumption about the grammar) which can also be set
explicitly by putting
\medskip
\beginprod
\%define lr.type canonical-lr
\endprod
\medskip
\noindent
in with the rest of the options.
Using other types of grammars will wreak havoc
on the parsing algorithm hardcoded into \splint\ (see \.{yyparse.sty})
as well as on the production of \.{\\stashed} and \.{\\format} streams.
@<Grammar parser \bison\ options@>=
@G
%token-table
%debug
%start input
@g

@*1 Token declarations. Most of the original comments present in
the grammar file used by \bison\ itself have been preserved and appear in
{\it italics\/} at the beginning of the appropriate section.

To facilitate the {\it bootstrapping\/} of the parser (see above), some
declarations have been separated into their own sections. Also, a
number of new rules have been introduced to create a hierarchy of
`subparsers' that parse subsets of the grammar. We begin by listing
most of the tokens used by the grammar. Only the string versions are
kept in the |yytname| array, which, in part is the reason for a
special bootstrapping parser as explained earlier. 
\iffalse
    \checktrailingstashtrue % see what is left at the end
    \checktabletrue % display the table
    \let\stashnext\stashnextwithnothing % collect the stash expanded
\fi
@<Tokens and types for the grammar parser@>=
@G
%token GRAM_EOF 0 "end of file"
%token STRING     "string"

%token PERCENT_TOKEN       "%token"
%token PERCENT_NTERM       "%nterm"

%token PERCENT_TYPE        "%type"
%token PERCENT_DESTRUCTOR  "%destructor"
%token PERCENT_PRINTER     "%printer"

%token PERCENT_LEFT        "%left"
%token PERCENT_RIGHT       "%right"
%token PERCENT_NONASSOC    "%nonassoc"
%token PERCENT_PRECEDENCE  "%precedence"

%token PERCENT_PREC          "%prec"
%token PERCENT_DPREC         "%dprec"
%token PERCENT_MERGE         "%merge"
@g
@<Global Declarations@>@;

@ We continue with the list of tokens below, following the layout of
the original parser.
\iffalse
    \checktrailingstashfalse
    \checktablefalse
    \let\stashnext\stashnextwithnothingnx
\fi
@<Global Declarations@>=
@G
%token
  PERCENT_CODE            "%code"
  PERCENT_DEFAULT_PREC    "%default-prec"
  PERCENT_DEFINE          "%define"
  PERCENT_DEFINES         "%defines"
  PERCENT_ERROR_VERBOSE   "%error-verbose"
  PERCENT_EXPECT          "%expect"
  PERCENT_EXPECT_RR       "%expect-rr"
  PERCENT_FLAG            "%<flag>"
  PERCENT_FILE_PREFIX     "%file-prefix"
  PERCENT_GLR_PARSER      "%glr-parser"
  PERCENT_INITIAL_ACTION  "%initial-action"
  PERCENT_LANGUAGE        "%language"
  PERCENT_NAME_PREFIX     "%name-prefix"
  PERCENT_NO_DEFAULT_PREC "%no-default-prec"
  PERCENT_NO_LINES        "%no-lines"
  PERCENT_NONDETERMINISTIC_PARSER
                          "%nondeterministic-parser"
  PERCENT_OUTPUT          "%output"
  PERCENT_REQUIRE         "%require"
  PERCENT_SKELETON        "%skeleton"
  PERCENT_START           "%start"
  PERCENT_TOKEN_TABLE     "%token-table"
  PERCENT_VERBOSE         "%verbose"
  PERCENT_YACC            "%yacc"
;

%token BRACED_CODE      "{...}"
%token BRACED_PREDICATE "%?{...}"
%token BRACKETED_ID     "[identifier]"
%token CHAR             "char"
%token EPILOGUE         "epilogue"
%token EQUAL            "="
%token ID               "identifier"
%token ID_COLON         "identifier:"
%token PERCENT_PERCENT  "%%"
%token PIPE             "|"
%token PROLOGUE         "%{...%}"
%token SEMICOLON        ";"
%token TAG              "<tag>"
%token TAG_ANY          "<*>"
%token TAG_NONE         "<>"
%token INT              "integer"
%token <param> PERCENT_PARAM "%param";
@g

@ \namedspot{flex.options}Extra tokens for typesetting \flex\ state 
declarations and options are declared in addition to the ones that a 
standard \bison\ parser recognizes. This extension of the original
grammar has become unnecessary with the addition of the \flex\ input
parser(s) but is left as part of the extended grammar for convenience and
`historical' reasons.
@<Tokens and...@>=
@G
%token FLEX_OPTION FLEX_STATE_X FLEX_STATE_S
@g

@*1 Grammar productions.
We are ready to describe the top levels of the parse tree. The first
`sub parser' we consider is a `full' parser, that is the parser that
expects a full grammar file, complete with the prologue, declarations,
etc. This parser can be used to extract information from the grammar
that is otherwise absent from the executable code generated by
\bison. This includes, for example, the `name' part of 
\.{\$}\.{[}{\rm name}\.{]}. 
This parser is therefore used to generate the `symbolic
switch' to provide support for symbolic term names similar to
the `genuine' \bison's \.{\$}\.{[}$\ldots$\.{]} syntax.

The action of the parser in this case is simply to separate the
accumulated `parse tree' from the auxiliary information carried by the
parser on the stack. 
\saveparseoutputfalse
\checktablefalse
\tracenamesfalse
@<Parser full productions@>=
@G
@t}\vb{\inline}{@>
input:
  prologue_declarations 
      "%%" grammar epilogue.opt             {@> TeX_( "/getsecond{/yy(3)}/to/table" ); @=}
;
@g

@ Another subgrammar deals with the syntax of isolated \bison\ rules. This is
the most commonly used `subparser' since a rules cluster is the most
natural `unit' to include in a \CWEB\ file.
@<Fake start symbol for rules only grammar@>=
@G
@t}\vb{\inline}{@>
input:
  grammar epilogue.opt                      {@> TeX_( "/getsecond{/yy(1)}/to/table" ); @=}
;
@g

@ The bootstrap parser has a very narrow set of goals: it is concerned
with \prodstyle{\%token} declarations only in
order to supply the token information to the lexer (since, as noted
above, such information is not kept in the |yytname| array). 
The parser can also parse \prodstyle{\%nterm} declarations but the
bootstrap lexer ignores the \prodstyle{\%nterm} token, since the
\bison\ grammar does not use one.
It also extends the syntax of a \prodstyle{grammar\_declaration} by allowing a
declaration with or without a semicolon at the end (the latter is only
allowed in the prologue). This works since the token declarations have
been carefully separated from the rest of the grammar in different
\CWEB\ sections. The range of tokens output by the bootstrap
lexer is limited, hence most of the other rules are ignored.
@<Fake start symbol for bootstrap grammar@>=
@G
@t}\vb{\inline}{@>
input:
  grammar_declarations                      {@> TeX_( "/table=/yy(1)" ); @=} 
;
@t}\vb{\resetf}{@>
grammar_declarations:
  symbol_declaration semi.opt               {@> @<Carry on@> @=}
| flex_declaration semi.opt                 {@> @<Carry on@> @=}
| grammar_declarations 
      symbol_declaration semi.opt           {@> TeX_( "/yy0{/the/yy(1)/the/yy(2)}" ); @=}
| grammar_declarations 
      flex_declaration semi.opt             {@> TeX_( "/yy0{/the/yy(1)/the/yy(2)}" ); @=}
;
@t}\vb{\inline\flatten}{@>
semi.opt: {} | ";" {};
@g

@ The following is perhaps the most common action performed by the
parser. It is done automatically by the parser code but this feature
is undocumented so we supply an explicit action in each case.
@<Carry on@>=
  @[TeX_( "/yy0{/the/yy(1)}" );@]@;

@ Next comes a subgrammar for processing prologue declarations. Finer
differentiation is possible but the `subparsers' described here work
pretty well and impose a mild style on the grammar writer. Note that
these roles are not part of the official \bison\ input grammar and are
added to make the typesetting of `file outlines' (e.g.~|@(bb.yy@>|
above) possible.
@<Fake start symbol for prologue grammar@>=
@G
@t}\vb{\inline}{@>
input:
  prologue_declarations epilogue.opt        {@> TeX_( "/getsecond{/yy(1)}/to/table" ); @=} 
| prologue_declarations 
      "%%" "%%" EPILOGUE                    {@> TeX_( "/getsecond{/yy(1)}/to/table" ); @=}
| prologue_declarations 
      "%%" "%%"                             {@> TeX_( "/getsecond{/yy(1)}/to/table" ); @=}
;
@g

@ {\it Declarations: before the first \prodstyle{\%\%}}. We are now
ready to deal with the specifics of the declarations themselves. The
\.{\\grammar} macro is a `structure', whose first `field' is the
grammar itself, whereas the second carries the type of the last
declaration added to the grammar.
@<Parser prologue productions@>=
@G
prologue_declarations:
                                            {@> TeX_( "/yy0{/nx/grammar{}{/nx/empty}}" ); @=}
| prologue_declarations 
      prologue_declaration                  {@> @<Attach a prologue declaration@> @=}
;
@g

@ @<Attach a prologue declaration@>=
  @<Attach a productions cluster@>@;

@ Here is a list of most kinds of declarations that can appear in the
prologue. The scanner returns the `stream pointers' for all the
keywords so the declaration `structures' pass on those pointers to the
grammar list. The original syntax has been left intact even though for
the purposes of this parser some of the inline rules are unnecessary.
@<Parser prologue productions@>=
@G
prologue_declaration:
  grammar_declaration                       {@> @<Carry on@> @=}
| "%{...%}"                                 {@> TeX_( "/yy0{/nx/prologuecode/the/yy(1)}" ); @=}
| "%<flag>"                                 {@> TeX_( "/yy0{/nx/optionflag/the/yy(1)}" ); @=}
| "%define" variable value                  {@> TeX_( "/yy0{/nx/vardef{/the/yy(2)}{/the/yy(3)}/the/yy(1)}" ); @=}
| "%defines"                                {@> TeX_( "/yy0{/nx/optionflag{defines}{}/the/yy(1)}" ); @=}
| "%defines" STRING                         {@> @[TeX_( "/toksa{defines}" );@]@+@<Prepare one parametric option@> @=}
| "%error-verbose"                          {@> TeX_( "/yy0{/nx/optionflag{error verbose}{}/the/yy(1)}" ); @=}
| "%expect" INT                             {@> @[TeX_( "/toksa{expect}" );@]@+@<Prepare a generic one parametric option@> @=}
| "%expect-rr" INT                          {@> @[TeX_( "/toksa{expect-rr}" );@]@+@<Prepare a generic one parametric option@> @=}
| "%file-prefix" STRING                     {@> @[TeX_( "/toksa{file prefix}" );@]@+@<Prepare one parametric option@> @=}
| "%glr-parser"                             {@> TeX_( "/yy0{/nx/optionflag{glr parser}{}/the/yy(1)}" ); @=}
| "%initial-action" "{...}"                 {@> TeX_( "/yy0{/nx/initaction/the/yy(2)}" ); @=}
| "%language" STRING                        {@> @[TeX_( "/toksa{language}" );@]@+@<Prepare one parametric option@> @=}
| "%name-prefix" STRING                     {@> @[TeX_( "/toksa{name prefix}" );@]@+@<Prepare one parametric option@> @=}
| "%no-lines"                               {@> TeX_( "/yy0{/nx/optionflag{no lines}{}/the/yy(1)}" ); @=}
| "%nondeterministic-parser"                {@> TeX_( "/yy0{/nx/optionflag{nondet. parser}{}/the/yy(1)}" ); @=}
| "%output" STRING                          {@> @[TeX_( "/toksa{output}" );@]@+@<Prepare one parametric option@> @=}
@t}\vb{\flatten}{@>
| "%param"                                  {} 
      params                                {@> TeX_( "/yy0{/nx/paramdef{/the/yy(3)}/the/yy(1)}" ); @=}
@t}\vb{\fold}{@>
| "%require" STRING                         {@> @[TeX_( "/toksa{require}" );@]@+@<Prepare one parametric option@> @=}
| "%skeleton" STRING                        {@> @[TeX_( "/toksa{skeleton}" );@]@+@<Prepare one parametric option@> @=}
| "%token-table"                            {@> TeX_( "/yy0{/nx/optionflag{token table}{}/the/yy(1)}" ); @=}
| "%verbose"                                {@> TeX_( "/yy0{/nx/optionflag{verbose}{}/the/yy(1)}" ); @=}
| "%yacc"                                   {@> TeX_( "/yy0{/nx/optionflag{yacc}{}/the/yy(1)}" ); @=}
| ";"                                       {@> TeX_( "/yy0{/nx/empty}" ); @=}
;

params:
   params "{...}"                           {@> TeX_( "/yy0{/the/yy(1)/nx/braceit/the/yy(2)}" ); @=}
| "{...}"                                   {@> TeX_( "/yy0{/nx/braceit/the/yy(1)}" ); @=}
;
@g

@ This is a typical parser action: encapsulate the `type' of the
construct just parsed and attach some auxiliary info, in this case the
stream pointers.
@<Prepare one parametric option@>=
  @[TeX_( "/yy0{/nx/oneparametricoption{/the/toksa}{/nx/stringify/the/yy(2)}/the/yy(1)}" );@]@;

@ @<Prepare a generic one parametric option@>=
  @[TeX_( "/yy0{/nx/oneparametricoption{/the/toksa}{/the/yy(2)}/the/yy(1)}" );@]@;

@ These rules handle extra declarations to typeset \flex\ options and
declarations. These are not part of the \bison\ syntax but their
structure is similar enough that they can be included in the
grammar. As was pointed out \locallink{flex.options}earlier \endlink
the addition of the \flex\ input parser to \splint\ made this
extension of the original \bison\ grammar obsolete but it was kept as
part of the extended grammar for convenience and `historical'
reasons. The convenience results from simplifying the bootstrap
procedure by using a single parser.
@<Parser prologue productions@>=
@G
prologue_declaration:
  flex_declaration                          {@> @<Carry on@> @=}
;
@g
@<\flex\ options parser productions@>@;

@ The syntax of \flex\ options was extracted from \flex\ documentation
so it is not guaranteed to be correct.
@<\flex\ options parser productions@>=
@G
flex_declaration:
  FLEX_OPTION flex_option_list              {@> @<Define \flex\ option list@> @=}
| flex_state symbols.1                      {@> @<Define \flex\ states@> @=}
;

flex_state:
  FLEX_STATE_X                              {@> TeX_( "/yy0{/nx/flexxstatedecls/the/yy(1)}" ); @=}
| FLEX_STATE_S                              {@> TeX_( "/yy0{/nx/flexsstatedecls/the/yy(1)}" ); @=}
;

flex_option_list:
  flex_option                               {@> @<Carry on@> @=}
| flex_option_list flex_option              {@> @<Add a \flex\ option@> @=}
;

flex_option:
  ID                                        {@> TeX_( "/yy0{/nx/flexoptionpair{/nx/idit/the/yy(1)}{}}" ); @=}
| ID "=" symbol                             {@> TeX_( "/yy0{/nx/flexoptionpair{/nx/idit/the/yy(1)}{/the/yy(3)}}" ); @=}
;
@g

@ @<Define \flex\ option list@>=
  @[TeX_( "/yy0{/nx/flexoptiondecls{/the/yy(2)}/the/yy(1)}" );@]@;

@ @<Define \flex\ states@>=
  @[TeX_( "/getfirst{/yy(1)}/to/toksa" );@]@;
  @[TeX_( "/getsecond{/yy(1)}/to/toksb" );@]@;
  @[TeX_( "/getthird{/yy(1)}/to/toksc" );@]@;
  @[TeX_( "/yy0{/the/toksa{/the/yy(2)}{/the/toksb}{/the/toksc}}" );@]@;

@ @<Add a \flex\ option@>=
  @[TeX_( "/getsecond{/yy(2)}/to/toksa" );@]@; /* the identifier */
  @[TeX_( "/getfourth{/toksa}/to/toksb" );@]@; /* the format pointer */
  @[TeX_( "/getfifth{/toksa}/to/toksc" );@]@; /* the stash pointer */
  @[TeX_( "/yy0{/the/yy(1)/nx/hspace{/the/toksb}{/the/toksc}/the/yy(2)}" );@]@;

@ {\it Grammar declarations}. These declarations can appear in both
the prologue and the rules sections. Their treatment is very similar to
the prologue-only options.
@<Parser common productions@>=
@G
grammar_declaration:
  precedence_declaration                    {@> @<Carry on@> @=}
| symbol_declaration                        {@> @<Carry on@> @=}
| "%start" symbol                           {@> @[TeX_( "/toksa{start}" );@]@+@<Prepare a generic one parametric option@> @=}
| code_props_type "{...}" generic_symlist   {@> @<Assign a code fragment to symbols@> @=}
| "%default-prec"                           {@> TeX_( "/yy0{/nx/optionflag{default prec.}{}/the/yy(1)}" ); @=}
| "%no-default-prec"                        {@> TeX_( "/yy0{/nx/optionflag{no default prec.}{}/the/yy(1)}" ); @=}
| "%code" "{...}"                           {@> TeX_( "/yy0{/nx/codeassoc{code}{}/the/yy(2)/the/yy(1)}" ); @=}
| "%code" ID "{...}"                        {@> TeX_( "/yy0{/nx/codeassoc{code}{/nx/idit/the/yy(2)}/the/yy(3)/the/yy(1)}" ); @=}
;

code_props_type:
  "%destructor"                             {@> TeX_( "/yy0{{destructor}/the/yy(1)}" ); @=}
| "%printer"                                {@> TeX_( "/yy0{{printer}/the/yy(1)}" ); @=}
;
@g

@ @<Assign a code fragment to symbols@>=
  @[TeX_( "/getfirst{/yy(1)}/to/toksa" );@]@; /* name of the property */
  @[TeX_( "/getfirst{/yy(2)}/to/toksb" );@]@; /* contents of the braced code */
  @[TeX_( "/getsecond{/yy(2)}/to/toksc" );@]@; /* braced code format pointer */
  @[TeX_( "/getthird{/yy(2)}/to/toksd" );@]@; /* braced code stash pointer */
  @[TeX_( "/getsecond{/yy(1)}/to/tokse" );@]@; /* code format pointer */
  @[TeX_( "/getthird{/yy(1)}/to/toksf" );@]@; /* code stash pointer */
  @[TeX_( "/yy0{/nx/codepropstype{/the/toksa}{/the/toksb}{/the/yy(3)}{/the/toksc}{/the/toksd}{/the/tokse}{/the/toksf}}" );@]@;

@ @<Tokens and types...@>=
@G
%token PERCENT_UNION "%union";
@g

@ @<Parser common productions@>=
@G
@t}\vb{\inline\flatten}{@>
union_name:
                                             {@> TeX_( "/yy0{}" ); @=}
| ID                                         {@> @<Turn an identifier into a term@> @=}
;

grammar_declaration:
  "%union" union_name "{...}"                {@> @<Prepare union definition@> @=}
;

symbol_declaration:
  "%type" TAG symbols.1                      {@> @<Define symbol types@> @=}
;
@t}\vb{\resetf\flatten}{@>
precedence_declaration:
  precedence_declarator tag.opt symbols.prec {@> @<Define symbol precedences@> @=}
;

precedence_declarator:
  "%left"                                    {@> TeX_( "/yy0{/nx/preckind{left}/the/yy(1)}" ); @=}
| "%right"                                   {@> TeX_( "/yy0{/nx/preckind{right}/the/yy(1)}" ); @=}
| "%nonassoc"                                {@> TeX_( "/yy0{/nx/preckind{nonassoc}/the/yy(1)}" ); @=}
| "%precedence"                              {@> TeX_( "/yy0{/nx/preckind{precedence}/the/yy(1)}" ); @=}
;
@t}\vb{\inline}{@>
tag.opt:
                                             {@> TeX_( "/yy0{}" ); @=}
| TAG                                        {@> @<Prepare a \prodstyle{TAG}@> @=}
;
@g

@ @<Prepare union definition@>=
  @[TeX_( "/yy0{/nx/codeassoc{union}{/the/yy(2)}/the/yy(3)/the/yy(1)}" );@]@;

@ @<Define symbol types@>=
  @[TeX_( "/yy0{/nx/typedecls{/nx/tagit/the/yy(2)}{/the/yy(3)}/the/yy(1)}" );@]@;

@ @<Define symbol precedences@>=
  @[TeX_( "/getthird{/yy(1)}/to/toksa" );@]@; /* format pointer */
  @[TeX_( "/getfourth{/yy(1)}/to/toksb" );@]@; /* stash pointer */
  @[TeX_( "/getsecond{/yy(1)}/to/toksc" );@]@; /* kind of precedence */
  @[TeX_( "/yy0{/nx/precdecls{/the/toksc}{/the/yy(2)}{/the/yy(3)}{/the/toksa}{/the/toksb}}" );@]@;

@ The bootstrap grammar forms the smallest subset of the full grammar.
@<Parser common productions@>=
  @<Parser bootstrap productions@>@;

@ @<Prepare a \prodstyle{TAG}@>=
  @[TeX_( "/yy0{/nx/tagit/the/yy(1)}" );@]@;

@ These are the two most important rules for the bootstrap parser. The reasons for
the~\prodstyle{\%token} declarations to be collected during the bootstrap pass are
outlined in the \locallink{bootstrapping}section on bootstrapping\endlink.
The~\prodstyle{\%nterm} declarations are not strictly necessary for
boostrapping the parsers included in \splint\ but they are added for
the cases when the bootstrap mode is used for purposes other than
bootstrapping \splint.
@<Parser bootstrap productions@>=
@G
@t}\vb{\flatten}{@>
symbol_declaration:
  "%nterm" {} symbol_defs.1                 {@> TeX_( "/yy0{/nx/ntermdecls{/the/yy(3)}/the/yy(1)}" ); @=}
@t}\vb{\fold\flatten}{@>
| "%token" {} symbol_defs.1                 {@> TeX_( "/yy0{/nx/tokendecls{/the/yy(3)}/the/yy(1)}" ); @=}
;
@g

@ {\it Just like \prodstyle{symbols.1} but accept \prodstyle{INT} for
the sake of \POSIX}. Perhaps the only point worth mentioning here is
the inserted separator (\.{\\hspace\{}$p_0$\.{\}\{}$p_1$\.{\}},
typeset as
|TeXa("/hspace"); TeXao(@t\TeXlit"\{\hbox{$p_0$}\}\{\hbox{$p_1$}\}\hbox{$\!$}"@>);|).
@q A string "..." is a syntactic unit in \CWEB\ so it is impossible@>
@q to insert \TeX\ material in the middle of the string directly@>
Like any other separator, it takes
two parameters, the stream pointers $p_0$ and~$p_1$. In this case, however, both pointers are null
since there seems to be no other meaningful assignment. If any
formatting or stash information is needed, it can be extracted by the
symbols themselves. 
@<Parser common productions@>=
@G
symbols.prec:
  symbol.prec                                {@> @<Carry on@> @=}
| symbols.prec symbol.prec                   {@> TeX_( "/yy0{/the/yy(1)/nx/hspace{0}{0}/the/yy(2)}" ); @=}
;

symbol.prec:
  symbol                                     {@> TeX_( "/yy0{/nx/symbolprec{/the/yy(1)}{}}" ); @=}
| symbol INT                                 {@> TeX_( "/yy0{/nx/symbolprec{/the/yy(1)}{/the/yy(2)}}" ); @=}
;
@g

@ {\it One or more symbols to be \prodstyle{\%type}'d}. The |@<List of
symbols@>| rules below are reused in the boostrap parser and are put
in a separate section for this reason.
@<Parser common productions@>=
  @<List of symbols@>@;

@ @<List of symbols@>=
@G
symbols.1:
  symbol                                     {@> @<Carry on@> @=}
| symbols.1 symbol                           {@> TeX_( "/yy0{/the/yy(1)/nx/hspace{0}{0}/the/yy(2)}" ); @=}
;
@g

@ @<Parser common productions@>=
@G
generic_symlist:
  generic_symlist_item                       {@> @<Carry on @> @=}
| generic_symlist generic_symlist_item       {@> TeX_( "/yy0{/the/yy(1)/nx/hspace{0}{0}/the/yy(2)}" ); @=}
;
@t}\vb{\flatten\inline}{@>
generic_symlist_item:
  symbol                                     {@> @<Carry on@> @=}
| tag                                        {@> @<Carry on@> @=}
;

tag:
  TAG                                        {@> @<Prepare a \prodstyle{TAG}@> @=}
| "<*>"                                      {@> @<Carry on@> @=}
| "<>"                                       {@> @<Carry on@> @=}
;
@g

@ {\it One token definition}.
@<Parser bootstrap productions@>=
@G
symbol_def:
  TAG                                        {@> @<Prepare a \prodstyle{TAG}@> @=}
@t}\vb{\flatten}{@>
| id                                         {@> TeX_( "/yy0{/nx/onesymbol{/the/yy(1)}{}{}}" ); @=}
| id INT                                     {@> TeX_( "/yy0{/nx/onesymbol{/the/yy(1)}{/the/yy(2)}{}}" ); @=}
| id string_as_id                            {@> TeX_( "/yy0{/nx/onesymbol{/the/yy(1)}{}{/the/yy(2)}}" ); @=}
| id INT string_as_id                        {@> TeX_( "/yy0{/nx/onesymbol{/the/yy(1)}{/the/yy(2)}{/the/yy(3)}}" ); @=}
;
@g

@ {\it One or more symbol definitions}.
@<Parser bootstrap productions@>=
@G
symbol_defs.1:
  symbol_def                                 {@> @<Carry on@> @=}
| symbol_defs.1 symbol_def                   {@> @<Add a symbol definition@> @=}
;
@g

@ @<Add a symbol definition@>=
  @[TeX_( "/getsecond{/yy(2)}/to/toksa" );@]@; /* the identifier */
  @[TeX_( "/getfourth{/toksa}/to/toksb" );@]@; /* the format pointer */
  @[TeX_( "/getfifth{/toksa}/to/toksc" );@]@; /* the stash pointer */
  @[TeX_( "/yy0{/the/yy(1)/nx/hspace{/the/toksb}{/the/toksc}/the/yy(2)}" );@]@;

@ {\it The grammar section: between the two
\prodstyle{\%\%}'s}. Finally, the following few short sections define
the syntax of \bison's rules. 
@<Parser grammar productions@>=
@G
grammar:
  rules_or_grammar_declaration               {@> @<Start with a production cluster@> @=}
| grammar rules_or_grammar_declaration       {@> @<Attach a productions cluster@> @=}
;
@g

@ {\it As a \bison\ extension, one can use the grammar declarations in the
body of the grammar}. What follows is the syntax of the right hand
side of a grammar rule.
@<Parser grammar productions@>=
@G
rules_or_grammar_declaration:
  rules                                      {@> @<Add a productions cluster@> @=}
| grammar_declaration ";"                    {@> @<Carry on@> @=}
| error ";"                                  {@> TeX_( "/errmessage{parsing error!}" ); @=}
;
@t}\vb{\flatten\inline}{@>
rules:
  id_colon named_ref.opt                     {@> TeX_( "/relax" ); @=}
    rhses.1                                  {@> @<Complete a production@> @=}
;
@t}\vb{\resetf}{@>
rhses.1[o]:
  rhs                                        {@> @<Start the right hand side@> @=}
| rhses.1[a] "|"[b]                          {@> @<Insert local formatting@> @=}[c]
      rhs[d]                                 {@> @<Add a right hand side to a production@> @=}
| rhses.1 ";"                                {@> @<Add an optional semicolon@> @=}
;
@g

@ The next few actions describe what happens when a left hand side is
attached to a rule.
@<Start with a production cluster@>=
  @[TeX_( "/getfirst{/yy(1)}/to/toksa" );@]@;
  @[TeX_( "/yy0{/nx/grammar{/the/yy(1)}{/the/toksa}}" );@]@;

@ @<Attach a productions cluster@>=
  @[TeX_( "/getthird{/yy(1)}/to/toksa" );@]@; /* type of the last rule */
  @[TeX_( "/getsecond{/yy(1)}/to/toksc" );@]@; /* accumulated rules */
  @[TeX_( "/getfirst{/yy(2)}/to/toksb" );@]@; /* type of the new rule */
  @[TeX_( "/let/default/positionswitchdefault" );@]@; 
  @[TeX_( "/switchon{/the/toksb}/in/positionswitch" );@]@; /* determine the position of the first token in the group */
  @[TeX_( "/edef/next{/the/toksa}" );@]@;
  @[TeX_( "/edef/default{/the/toksb}" );@]@; /* reuse \.{\\default} */
  @[TeX_( "/ifx/next/default" );@]@;
  @[TeX_( "    /let/default/separatorswitchdefaulteq" );@]@;
  @[TeX_( "    /switchon{/the/toksa}/in/separatorswitcheq" );@]@;
  @[TeX_( "/else" );@]@;
  @[TeX_( "    /concat/toksa/toksb" );@]@;
  @[TeX_( "    /let/default/separatorswitchdefaultneq" );@]@;
  @[TeX_( "    /switchon{/the/toksa}/in/separatorswitchneq" );@]@;
  @[TeX_( "/fi" );@]@;
  @[TeX_( "/yy0{/nx/grammar{/the/toksc/the/postoks/the/toksd/the/yy(2)}{/the/toksb}}" );@]@;

@ @<Add a productions cluster@>=
  @[TeX_( "/getsecond{/yy(1)}/to/toksa" );@]@; /* \.{\\prodheader} */
  @[TeX_( "/getsecond{/toksa}/to/toksb" );@]@; /* \.{\\idit} */
  @[TeX_( "/getfourth{/toksb}/to/toksc" );@]@; /* format stream pointer */
  @[TeX_( "/getfifth{/toksb}/to/toksd" );@]@; /* stash stream pointer */
  @[TeX_( "/getthird{/yy(1)}/to/toksb" );@]@; /* \.{\\rules} */
  @[TeX_( "/yy0{/nx/oneproduction{/the/toksa/the/toksb}{/the/toksc}{/the/toksd}}" );@]@;

@ @<Complete a production@>=
  @[TeX_( "/getfourth{/yy(1)}/to/toksa" );@]@; /* format stream pointer */
  @[TeX_( "/getfifth{/yy(1)}/to/toksb" );@]@; /* stash stream pointer */
  @[TeXb( "/yy0{/nx/pcluster{/nx/prodheader{/the/yy(1)}{/the/yy(2)}" );@]@;
  @[TeXao(     "{/the/toksa}{/the/toksb}}{/the/yy(4)}}" );@]@;

@ It is important to format the right hand side properly, since we
would like to indicate that an action is inlined by an
indentation. The `format' of the \.{\\rhs} `structure' includes the
stash pointers and a `boolean' to indicate whether the right hand side ends
with an action. Since the action can be implicit, this decision has to
be postponed until, say, a semicolon is seen. 
No formatting or stash pointers are added for implicit actions.
@<Start the right hand side@>=
  @[TeX_( "/rhsbool{/yy(1)}/to/toksa /the/toksa" );@]@;
  @[TeX_( "/getthird{/yy(1)}/to/toksb" );@]@; /* the format pointer */
  @[TeX_( "/getfourth{/yy(1)}/to/toksc" );@]@; /* the stash pointer */
  @[TeX_( "/ifrhsfull" );@]@;
  @[TeX_( "    /yy0{/nx/rules{/the/yy(1)}{/the/toksb}{/the/toksc}}" );@]@;
  @[TeX_( "/else" );@]@; /* it does not end with an action, fake one */
  @[TeX_( "    /rhscont{/yy(1)}/to/toksa" );@]@; /* rules */
  @[TeX_( "    /edef/next{/the/toksa}" );@]@;
  @[TeX_( "    /ifx/next/empty" );@]@;
  @[TeX_( "        /toksa{/emptyterm}" );@]@;
  @[TeX_( "    /fi" );@]@;
  @[TeXb( "    /yy0{/nx/rules{/nx/rhs{/the/toksa/nx/rarhssep{0}{0}" );@]@;
  @[TeXfo( "         /nx/actbraces{}{}{0}{0}/nx/bdend}{}{/nx/rhsfulltrue}}{/the/toksb}{/the/toksc}}" );@]@;
  @[TeX_( "/fi" );@]@;

@ Using standard notation, here is what the middle action
does. 
@<Old `Insert local formatting'@>=
  @[TeX_( "/rhscont{/yy(1)}/to{/yy(0)}" );@]@;
  @[TeX_( "/yy0{/the/yy(0)/nx/midf/the/yy(2)}" );@]@;

@ However, if the length of the rule preceding the inline action
is not known a different way of accessing the stack is necessary.
@<Insert local formatting@>=
  @[TeX_( "/bb2{/toksa}/bb1{/toksb}" );@]@;
  @[TeX_( "/rhscont{/toksa}/to{/yy(0)}" );@]@;
  @[TeX_( "/yy0{/the/yy(0)/nx/midf/the/toksb}" );@]@;

@ @<Old `Add a right hand side to a production'@>=
  @[TeX_( "/rhsbool{/yy(4)}/to/toksa /the/toksa" );@]@;
  @[TeX_( "/ifrhsfull" );@]@;
  @[TeX_( "    /yy0{/nx/rules{/the/yy(3)/nx/rrhssep/the/yy(2)/the/yy(4)}/the/yy(2)}" );@]@;
  @[TeX_( "/else" );@]@;
  @[TeX_( "    /rhscont{/yy(4)}/to/toksa" );@]@;
  @[TeX_( "    /edef/next{/the/toksa}" );@]@;
  @[TeX_( "    /ifx/next/empty" );@]@;
  @[TeX_( "        /toksa{/emptyterm}" );@]@;
  @[TeX_( "    /fi" );@]@;
  @[TeXb( "    /yy0{/nx/rules{/the/yy(3)/nx/rrhssep/the/yy(2)" );@]@;
  @[TeXf( "         /nx/rhs{/the/toksa/nx/rarhssep{0}{0}" );@]@; /* streams have already been grabbed */
  @[TeXfo( "         /nx/actbraces{}{}{0}{0}/nx/bdend}{}{/nx/rhsfulltrue}}/the/yy(2)}" );@]@;
  @[TeX_( "/fi" );@]@;

@ No pointers are provided for an {\it implicit\/} action. Processing a set of rules involves a large number of
reexpansions. This seems to be a good place to use an array to store {\sc AST} nodes ({\let\writetexidxentry\writetextxtidxentry
\def\texnspace{texline}\def\texispace{index}\inlineTeXx{/astarray}}). While
providing a noticeable speed up, this technique significantly
complicates the debugging of the grammar. In particular, inspecting a
parsed table supplies very little information if the {\sc AST} nodes are not
expanded. The macros in \.{yyunion.sty} provide a special debugging
namespace where the expansion of the parser produced control sequences
may be modified to safely expand the generated table.
@<Add a right hand side to a production@>=
  @[TeX_( "/rhsbool{/yy(4)}/to/toksa /the/toksa" );@]@;
  @[TeX_( "/ifrhsfull" );@]@;
  @[TeX_( "    /yypushx{/the/yy(3)/nx/rrhssep/the/yy(2)/the/yy(4)}/on/astarray" );@]@;
  @[TeX_( "/else" );@]@;
  @[TeX_( "    /rhscont{/yy(4)}/to/toksa" );@]@;
  @[TeX_( "    /edef/next{/the/toksa}" );@]@;
  @[TeX_( "    /ifx/next/empty" );@]@;
  @[TeX_( "        /toksa{/emptyterm}" );@]@;
  @[TeX_( "    /fi" );@]@;
  @[TeXb( "    /yypushx{/the/yy(3)/nx/rrhssep/the/yy(2)" );@]@;
  @[TeXf( "         /nx/rhs{/the/toksa/nx/rarhssep{0}{0}" );@]@; /* streams have already been grabbed */
  @[TeXfo( "         /nx/actbraces{}{}{0}{0}/nx/bdend}{}{/nx/rhsfulltrue}}/on/astarray" );@]@;
  @[TeX_( "/fi" );@]@;
  @[TeX_( "/yy0{/nx/rules{/astarraylastcs}/the/yy(2)}" );@]@;

@ @<Add an optional semicolon@>=
  @<Carry on@>@;

@ @<Tokens and types...@>=
@G
%token PERCENT_EMPTY "%empty";
@g

@ The centerpiece of the grammar is the syntax of the right hand side
of a production. Various `precedence hints' must be attached to an
appropriate portion of the rule, just before an action (which can
be inline, implicit or both in this case).
\saveparseoutputtrue
@<Parser grammar productions@>=
@G(b)
rhs:
                                             {@> @<Make an empty right hand side@> @=}
| rhs symbol named_ref.opt                   {@> @<Add a term to the right hand side@> @=}
| rhs "{...}" named_ref.opt                  {@> @<Add an action to the right hand side@> @=}
| rhs "%?{...}"                              {@> @<Add a predicate to the right hand side@> @=}
| rhs "%empty"                               {@> @<Add \prodstyle{\%empty} to the right hand side@> @=}
| rhs "%prec" symbol                         {@> @<Add a precedence directive to the right hand side@> @=}
| rhs "%dprec" INT                           {@> @<Add a \prodstyle{\%dprec} directive to the right hand side@> @=}
| rhs "%merge" TAG                           {@> @<Add a \prodstyle{\%merge} directive to the right hand side@> @=}
;

named_ref.opt:
                                             {@> @<Create an empty named reference@> @=}
| BRACKETED_ID                               {@> @<Create a named reference@> @=}
;
@g

@ \saveparseoutputfalse 
@<Make an empty right hand side@>=
  @[TeX_( "/yy0{/nx/rhs{}{}{/nx/rhsfullfalse}}" );@]@;

@ @<Add a term to the right hand side@>=
  @[TeX_( "/rhscont{/yy(1)}/to/toksa" );@]@;
  @[TeX_( "/rhscnct{/yy(1)}/to/toksb" );@]@;
  @[TeX_( "/edef/next{/the/toksb}" );@]@;
  @[TeX_( "/ifx/next/empty" );@]@;
  @[TeX_( "/else" );@]@;
  @[TeX_( "    /getfourth{/yy(2)}/to/toksc" );@]@;
  @[TeX_( "    /getfifth{/yy(2)}/to/toksd" );@]@;
  @[TeX_( "    /appendr/toksb{{/the/toksc}{/the/toksd}}" );@]@;
  @[TeX_( "/fi" );@]@;
  @[TeXb( "/yy0{/nx/rhs{/the/toksa/the/toksb" );@]@;
  @[TeXao(    "/nx/termname{/the/yy(2)}{/the/yy(3)}}{/nx/hspace}{/nx/rhsfullfalse}}" );@]@;

@ @<Add an action to the right hand side@>=
  @[TeX_( "/rhscont{/yy(1)}/to/toksa" );@]@;
  @[TeX_( "/rhsbool{/yy(1)}/to/toksb /the/toksb" );@]@;
  @[TeX_( "/ifrhsfull" );@]@; /* the first half ends with an action */
  @[TeX_( "    /appendr/toksa{/nx/arhssep{0}{0}/nx/emptyterm}" );@]@; /* no pointers to streams */
  @[TeX_( "/fi" );@]@;
  @[TeX_( "/edef/next{/the/toksa}" );@]@;
  @[TeX_( "/ifx/next/empty" );@]@;
  @[TeX_( "    /toksa{/emptyterm}" );@]@;
  @[TeX_( "/fi" );@]@;
  @[TeX_( "/getfirst{/yy(2)}/to/toksb" );@]@; /* the contents of the braced code */
  @[TeX_( "/getsecond{/yy(2)}/to/toksc" );@]@; /* the format stream pointer */
  @[TeX_( "/getthird{/yy(2)}/to/toksd" );@]@; /* the stash stream pointer */
  @[TeXb( "/yy0{/nx/rhs{/the/toksa/nx/rarhssep{/the/toksc}{/the/toksd}" );@]@;
  @[TeXf( "     /nx/actbraces{/the/toksb}{/the/yy(3)}{/the/toksc}{/the/toksd}/nx/bdend}" );@]@;
  @[TeXfo( "               {/nx/arhssep}{/nx/rhsfulltrue}}" );@]@;

@ @<Add a predicate to the right hand side@>=
  @[TeX_( "/rhscont{/yy(1)}/to/toksa" );@]@;
  @[TeX_( "/rhsbool{/yy(1)}/to/toksb /the/toksb" );@]@;
  @[TeX_( "/ifrhsfull" );@]@; /* the first half ends with an action */
  @[TeX_( "    /appendr/toksa{/nx/arhssep{0}{0}/nx/emptyterm}" );@]@; /* no pointers to streams */
  @[TeX_( "/fi" );@]@;
  @[TeX_( "/edef/next{/the/toksa}" );@]@;
  @[TeX_( "/ifx/next/empty" );@]@;
  @[TeX_( "    /toksa{/emptyterm}" );@]@;
  @[TeX_( "/fi" );@]@;
  @[TeX_( "/getfirst{/yy(2)}/to/toksb" );@]@; /* the contents of the braced code */
  @[TeX_( "/getsecond{/yy(2)}/to/toksc" );@]@; /* the format stream pointer */
  @[TeX_( "/getthird{/yy(2)}/to/toksd" );@]@; /* the stash stream pointer */
  @[TeXb( "/yy0{/nx/rhs{/the/toksa/nx/rarhssep{/the/toksc}{/the/toksd}" );@]@;
  @[TeXf( "     /nx/bpredicate{/the/toksb}{}{/the/toksc}{/the/toksd}/nx/bdend}" );@]@;
  @[TeXao(     "{/nx/arhssep}{/nx/rhsfulltrue}}" );@]@;

@ @<Add \prodstyle{\%empty} to the right hand side@>=
  @[TeX_( "/rhscont{/yy(1)}/to/toksa" );@]@;
  @[TeX_( "/rhscnct{/yy(1)}/to/toksb" );@]@;
  @[TeX_( "/edef/next{/the/toksb}" );@]@;
  @[TeX_( "/ifx/next/empty" );@]@;
  @[TeX_( "/else" );@]@;
  @[TeX_( "    /getfourth{/yy(2)}/to/toksc" );@]@;
  @[TeX_( "    /getfifth{/yy(2)}/to/toksd" );@]@;
  @[TeX_( "    /appendr/toksb{{/the/toksc}{/the/toksd}}" );@]@;
  @[TeX_( "/fi" );@]@;
  @[TeXb( "/yy0{/nx/rhs{/the/toksa/the/toksb" );@]@;
  @[TeXao(    "/nx/emptyterm}{/nx/hspace}{/nx/rhsfullfalse}}" );@]@;

@ @<Add a precedence directive to the right hand side@>=
  @[TeX_( "/rhscont{/yy(1)}/to/toksa" );@]@;
  @[TeX_( "/rhscnct{/yy(1)}/to/toksb" );@]@;
  @[TeX_( "/rhsbool{/yy(1)}/to/toksc /the/toksc" );@]@;
  @[TeX_( "/ifrhsfull" );@]@;
  @[TeX_( "    /yy0{/nx/sprecop{/the/yy(3)}/the/yy(2)}" );@]@; /* reuse \.{\\yyval} */
  @[TeX_( "    /supplybdirective/toksa/yyval" );@]@; /* the directive is `absorbed' by the action */
  @[TeX_( "    /yy0{/nx/rhs{/the/toksa}{/the/toksb}{/nx/rhsfulltrue}}" );@]@;
  @[TeX_( "/else" );@]@;
  @[TeXb( "    /yy0{/nx/rhs{/the/toksa" );@]@;
  @[TeXao(    "/nx/sprecop{/the/yy(3)}/the/yy(2)}{/the/toksb}{/nx/rhsfullfalse}}" );@]@;
  @[TeX_( "/fi" );@]@;

@ @<Add a \prodstyle{\%dprec} directive to the right hand side@>=
  @[TeX_( "/rhscont{/yy(1)}/to/toksa" );@]@;
  @[TeX_( "/rhscnct{/yy(1)}/to/toksb" );@]@;
  @[TeX_( "/rhsbool{/yy(1)}/to/toksc /the/toksc" );@]@;
  @[TeX_( "/ifrhsfull" );@]@;
  @[TeX_( "    /yy0{/nx/dprecop{/the/yy(3)}/the/yy(2)}" );@]@; /* reuse \.{\\yyval} */
  @[TeX_( "    /supplybdirective/toksa/yyval" );@]@; /* the directive is `absorbed' by the action */
  @[TeX_( "    /yy0{/nx/rhs{/the/toksa}{/the/toksb}{/nx/rhsfulltrue}}" );@]@;
  @[TeX_( "/else" );@]@;
  @[TeXb( "    /yy0{/nx/rhs{/the/toksa" );@]@;
  @[TeXao(    "/nx/dprecop{/the/yy(3)}/the/yy(2)}{/the/toksb}{/nx/rhsfullfalse}}" );@]@;
  @[TeX_( "/fi" );@]@;

@ @<Add a \prodstyle{\%merge} directive to the right hand side@>=
  @[TeX_( "/rhscont{/yy(1)}/to/toksa" );@]@;
  @[TeX_( "/rhscnct{/yy(1)}/to/toksb" );@]@;
  @[TeX_( "/rhsbool{/yy(1)}/to/toksc /the/toksc" );@]@;
  @[TeX_( "/ifrhsfull" );@]@;
  @[TeX_( "    /yy0{/nx/mergeop{/nx/tagit/the/yy(3)}/the/yy(2)}" );@]@; /* reuse \.{\\yyval} */
  @[TeX_( "    /supplybdirective/toksa/yyval" );@]@; /* the directive is `absorbed' by the action */
  @[TeX_( "    /yy0{/nx/rhs{/the/toksa}{/the/toksb}{/nx/rhsfulltrue}}" );@]@;
  @[TeX_( "/else" );@]@;
  @[TeXb( "    /yy0{/nx/rhs{/the/toksa" );@]@;
  @[TeXao(    "/nx/mergeop{/nx/tagit/the/yy(3)}/the/yy(2)}{/the/toksb}{/nx/rhsfullfalse}}" );@]@;
  @[TeX_( "/fi" );@]@;

@ @<Create an empty named reference@>=
  @[TeX_( "/yy0{}" );@]@;

@ @<Create a named reference@>=
  @<Turn an identifier into a term@>@;

@ Identifiers.
{\it Identifiers are returned as |uniqstr| values by the scanner.
Depending on their use, we may need to make them genuine symbols}. We,
on the other hand, simply copy the values returned by the scanner.
@<Parser bootstrap productions@>=
@G
id:
  ID                                         {@> @<Turn an identifier into a term@> @=}
| CHAR                                       {@> @<Turn a character into a term@> @=}
;
@g

@ @<Parser common productions@>=
  @<Definition of \prodstyle{symbol}@>@;

@ @<Definition of \prodstyle{symbol}@>=
@G
symbol:
  id                                         {@> @<Turn an identifier into a symbol@> @=}
| string_as_id                               {@> @<Turn a string into a symbol@> @=}
;
@g

@ @<Parser grammar productions@>=
@G
@t}\vb{\inline}{@>
id_colon:
  ID_COLON                                   {@> @<Prepare the left hand side@> @=}
;
@g

@ A string used as an \prodstyle{ID}.
@<Parser bootstrap productions@>=
@G
@t}\vb{\inline}{@>
string_as_id:
  STRING                                     {@> @<Prepare a string for use@> @=}                                       
;
@g

@ The remainder of the action code is trivial but we reserved the
placeholders for the appropriate actions in case the parser gains some
sophistication in processing low level types (or starts expecting
different types from the scanner).
@<Turn an identifier into a term@>=
  @[TeX_( "/yy0{/nx/idit/the/yy(1)}" );@]@;

@ @<Turn a character into a term@>=
  @[TeX_( "/yy0{/nx/charit/the/yy(1)}" );@]@;

@ @<Turn an identifier into a symbol@>=
  @<Carry on@>@;

@ @<Turn a string into a symbol@>=
  @<Carry on@>@;

@ @<Prepare the left hand side@>=
  @<Turn an identifier into a term@>@;

@ @<Prepare a string for use@>=
  @[TeX_( "/yy0{/nx/stringify/the/yy(1)}" );@]@;

@ {\it Variable and value.
The \prodstyle{STRING} form of variable is deprecated and is not \.{M4}-friendly.
For example, \.{M4} fails for \.{\%define "[" "value"}.}
@<Parser prologue productions@>=
@G
@t}\vb{\flatten\inline}{@>
variable:
  ID                                         {@> @<Turn an identifier into a term@> @=}
| STRING                                     {@> @<Prepare a string for use@> @=}
;

value:
                                             {@> TeX_( "/yy0{}" ); @=}
| ID                                         {@> @<Turn an identifier into a term@> @=}
| STRING                                     {@> @<Prepare a string for use@> @=}
| "{...}"                                    {@> TeX_( "/yy0{/nx/bracedvalue/the/yy(1)}" ); @=}
;
@g

@ @<Parser common productions@>=
@G
@t}\vb{\flatten\inline}{@>
epilogue.opt:
                                             {@> TeX_( "/yy0{}" ); @=}
| "%%" EPILOGUE                              {}
;
@g

@ \Cee\ preamble for the grammar parser. In this case, there are no `real' actions that our
grammar performs, only \TeX\ output, so this section is empty. 

@<Grammar parser \Cee\ preamble@>=

@ \Cee\ postamble for the grammar parser. It is tricky to insert function definitions that use \bison's internal types,
as they have to be inserted in a place that is aware of the internal definitions but before said 
definitions are used.

@<Grammar parser \Cee\ postamble@>=
#define YYPRINT(file, type, value)   @[yyprint (file, type, value)@]
  static void yyprint (FILE *file, int type, YYSTYPE value){}

@ @<Bootstrap parser \Cee\ postamble@>=
  @<Grammar parser \Cee\ postamble@>@;
  @<Bootstrap token output@>@;

@ @<Bootstrap token output@>=
  void bootstrap_tokens( char *bootstrap_token_format ) {
  
#define _register_token_d(name)    @[fprintf( tables_out, bootstrap_token_format, #name, name, #name );@;
  @<Bootstrap token list@>@;
#undef _register_token_d@;

  }

@ \namedspot{bootstraptokens}Here is the minimal list of tokens needed
to make the lexer operational just enough to extract the rest of the
token information from the grammar.
@<Bootstrap token list@>=
  _register_token_d(ID)@;
  _register_token_d(PERCENT_TOKEN)@;
  _register_token_d(STRING)@;

@q The tokens below are not required to make a minimal bootstrapping parser work @>
@q but they do appear in the rules the parser will encounter while extracting @>
@q token information. @>
@q  _register_token_d(INT) /* only encountered in GRAM_EOF definition which is never used */ @>
@q  _register_token_d(CHAR) /* \bison\ never declares character tokens */ @>
@q  _register_token_d(SEMICOLON) /* can be omitted in prologue */ @>
@q  _register_token_d(TAG) /* only encountered in the definition of PERCENT_PARAM */ @>

@ Union of types. This section of the \bison\ input lists the types
that may appear on the value stack. Since \TeX\ does not provide any
mechanism for type checking (nor is it clear how to translate a \Cee\
|union| into any data structure usable in \TeX), this section is left empty.
@<Union of grammar parser types@>=