summaryrefslogtreecommitdiff
path: root/support/splint/cweb/bo.w
blob: fe7bf59f52eaf36b0548845ed95f25e7bd2fb103 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
% 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@>=