summaryrefslogtreecommitdiff
path: root/support/splint/cweb/bo.w
blob: 2185f2f65eeb64de8253a3de55af0de49b356c4b (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
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
% Copyright 2012-2014, 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/>.

\input limbo.sty
\input frontmatter.sty
\def\optimization{5}
\input yy.sty
% multi-column output
\input dcols.sty

\let\hostparsernamespace\mainnamespace % the namespace where tokens are looked up
                                       % for typesetting purposes
\let\currentparsernamespace\parsernamespace
    \let\parsernamespace\mainnamespace
    \let\currenttokeneq\tokeneq
        %\def\tokeneq#1#2{\prettytoken{#1}}
        \let\tokeneq\prettywordpair@@
            \let\optstrextra\optstrextraesc
            \input bo.tok % re-use token equivalence table to set the typesetting of tokens
    \let\tokeneq\currenttokeneq
    \input btokenset.sty
    % index entries
    \let\parsernamespace\indexpseudonamespace
    \prettywordpair{emptyrhs}{$\circ$ {\rm(empty rhs)}}%
    \prettywordpair{inline_action}{$\diamond$ {\rm(inline action)}}%
    \prettywordpair{TOKEN}{{\tt TOKEN} {\rm(example)}}%
    \prettywordpair{token}{{\tt "token"} {\rm(example)}}%
\let\parsernamespace\currentparsernamespace

\immediate\openout\exampletable=\jobname.exl

\def\nontitle#1{{\ttl #1}}
\def\cite[#1]{%
    \def\next{#1}\setbox0=\hbox{l}%
    [\ifx\next\empty$\,$\hbox{\vrule width\wd0 height\ht0 depth\dp0}$\,$\else \locallink{#1bibref}#1\endlink\fi]%
}

\let\oldN\N
\let\N\textN
\let\M\textM

\defreserved{Y}{\.{Y}}
\showlastactiontrue

@**Introduction. 
\setupfootnotes
\splint\footnote{I was tempted to call the package {\tt ParLALRgram}
which stands for Parsing {\sc LALR} Grammars or {\tt PinT} for
`Parsing in \TeX' but both sounded too generic.} (Simple Parsing and
Lexing in \TeX, or, following the great GNU
tradition of creating recursive names, \splint\ Parses Languages
in \TeX) is a system (or
rather a m\'elange of systems) designed to 
facilitate developing parsing macros in \TeX\ and (to a lesser
degree) documenting parsers written in other languages. As
an application, a parser for \bison\ input file syntax has been
developed, along with a macro collection that makes it possible to
design and pretty print \bison\ grammars using \CWEB.

Developing software in \CWEB\ involves two programs. The first of these is
\CTANGLE\ that outputs the actual code, intended to be in
\Cee. In reality, \CTANGLE\ cares very little about the language it
produces. Exceptions are \Cee\ comments and |@[#line@]| directives that might
confuse lesser software, although \bison\ is all too happy to swallow them
(there are also some \Cee\ specific constructs that \CTANGLE\ tries to
recognize). \CTANGLE's main function is to rearrange the text of the
program as written by the programmer (in a way that, hopefully,
emphasizes the internal logic of the code) into an appropriate
sequence (e.g.~all variable declaration must textually precede their
use). All that is required to adopt \CTANGLE\ to produce \bison\
output is some very rudimentary post- and pre-processing.

Our main concern is thus \CWEAVE\ that not only pretty prints the
program but also creates an index, cross-references all the
sections, etc. Getting \CWEAVE\ to pretty print a language other than
\Cee\ requires some additional attention. A true digital warrior would
probably try to decipher \CWEAVE's output `in the raw' but, alas, my
WebFu is not that strong. The loophole comes in the form of a rarely
(for a good reason) used \CWEB\ command: the verbatim (\.{@@=...@@>})
output. The material to be output by this construct undergoes minimal
processing and is put inside \.{\\vb\{}$\ldots$\.{\}}. All that is
needed now is a way to process this virtually straight text inside \TeX.

@*1 Using the \bison\ parser.
The process of using \splint\ for writing parsing macros in \TeX\ is
treated in considerable detail later in this document. A shorter
(albeit somewhat outdated but still applicable) version of this
process is outlined in \cite[Sh]. We begin,
instead, by explaining how one such parser can be used to pretty print a
\bison\ grammar. Following the convention mentioned above and putting
all non-\Cee\ code inside \CWEAVE's verbatim blocks, consider the
following (meaningless) code fragment. The fragment contains a mixture
of \Cee\ and \bison\ code, the former appears outside of the verbatim blocks.
\begindemo
^@@= non_terminal:                        @@>
^@@=   term.1 term.2      {@@> a = b;   @@=}@@>
^@@= **H term.3 other_term  {@@> $$ = $1; @@=}@@>
^@@= **H still more terms   {@@> f($1);   @@=}@@>
^@@= ;                                    @@>
\enddemo
The fragment above will appear as (the output of \CTANGLE\ can be
examined in \.{sill.y})
@<A silly example@>=
@G
non_terminal:
  term.1 term.2       {@> a = b;   @=}
| term.3 other_term   {@> $$ = $1; @=}
| still more terms    {@> f($1);   @=}
;
@g

@ $\ldots$ if the syntax is correct. 
In case it is a bit off, the parser will give up and
you will see a different result. The code in the fragment below is easily
recognizable, and some parts of it (all of \Cee\ code, in fact) are
still pretty printed in \CWEAVE. Only the verbatim portion is left
unprocessed.
@<A silly example@>=
@G
whoops
  term.1 term.2         {@>@+ a = b;   @+@=}
| term.3 other_term     {@>@+ $$ = $1; @+@=}
| still more terms      {@>@+ f($1);   @+@=}
;
@g

@ The \TeX\ header that makes such output possible is quite plain. In this case
(i.e.\ this very file) it begins as
\begindemo
^\input limbo.sty
^\input frontmatter.sty
^\input yy.sty
\nooutput
\enddemo
The first two lines are presented here merely for completeness: there is
no parsing-relevant code in them. The line that
follows loads the macros that implement the parsing and scanning
machinery. This is enough to set up all the basic 
mechanisms used by the parsing and lexing macros. The rest of the header
provides a few definitions to fine tune the typesetting of
grammar productions. It starts with
\begindemo
^\let\currentparsernamespace\parsernamespace
^    \let\parsernamespace\mainnamespace
^    \let\currenttokeneq\tokeneq
^        \def\tokeneq#1#2{\prettytoken{#1}}
^            \input bo.tok % re-use token equivalence table to set the typesetting of tokens
^    \let\tokeneq\currenttokeneq
^    \input btokenset.sty
\nooutput
\enddemo
We will have a chance to discuss all the \.{\\}$\ldots$\.{namespace}
macros later, at this point it will suffice to say that the lines
above are responsible for controlling the typesetting of term names. The
file \.{bo.tok} consists of a number of lines like the ones below:
\begindemo
^\tokeneq {STRING}{{34}{115}{116}{114}{105}{110}{103}{34}}
^\tokeneq {PERCENT_TOKEN}{{34}{37}{116}{111}{107}{101}{110}{34}}
\nooutput
\enddemo
The cryptic looking sequences of integers above are strings of {\sc ASCII}
codes of the letters that form the name \bison\ uses when it needs to
refer to the corresponding token (thus, the second one is
\toksa{}\numberstochars{34}{37}{116}{111}{107}{101}{110}{34}\end
\.{\the\toksa} which might help explain why such an elaborate scheme
has been chosen).  The macro \.{\\tokeneq} is defined in
\.{yymisc.sty}, which in turn is input by \.{yy.sty} but what about
the token names themselves? In this case they were extracted
automatically from the \CWEB\ source file by the parser during the
\CWEAVE\ processing stage.  All of these definitions can be
overwritten to get the desired output (say, one might want to typeset
\.{ID} in a roman font, as `identifier'; all that needs to be done is
a macro that says \.{\\prettywordpair\{ID\}\{\{\\rm
identifier\}\}}). The file \.{btokenset.sty} input above contains a
number of such definitions.

@ To round off this short overview, I must mention a caveat associated
with using the macros in this collection: while one of the greatest
advantages of using \CWEB\ is its ability to rearrange the code in a
very flexible way, the parser will either give up or produce
unintended output if this feature is abused while describing the
grammar. For example, in the code below
@<A silly example@>=
@G
next_term:
  stuff        @> @<Rest of line@> @={@> a = f( x ); @=}            
@g
@<A production@>@;

@ the line titled |@<A production@>| is intended to be a rule defined
later. Notice that while it seems that the parser was able to recognize
the first code fragment as a valid \bison\ input, it misplaced the
|@<Rest of line@>|, having erroneously assumed it to be a part of
the action code for this grammar (later on we will go into the details of
why it is necessary to collect all the non-verbatim output of \CWEAVE,
even the one that contains no interesting \Cee\ code; hint: it has
something to do with money (\.{\$}), also known as math and the way
\CWEAVE\ processes the `gaps' between verbatim sections). The production
line that follows did not fare as well: the parser gave up. There
is simply no point in including such a small language fragment as a
valid input for the grammar the parser uses to process the verbatim
output.
@<A production@>=
@G
  more stuff in this line {@> @[b = g(y);@]@=}
@g

@ Finally, if you forget that only the verbatim part of the output is
looked at by the parser you might get something unrecognizable, such
as
@<Rest of line@>=
  but not all of it

@ To correct this, one can provide a more complete grammar fragment to
allow the parser to complete its task successfully. In some cases,
this imposes too strict a constraint on the programmer. Instead, the
parser that pretty prints \bison\ grammars allows one to add {\it
hidden context\/} to the code fragments above. The context is added
inside \.{\\vb} sections using \CWEB's \.{@@t}$\ldots$\.{@@>} facility. The \CTANGLE\
output is not affected by this while the code above can now be typeset as:
@<A silly example@>=
@G
next_term:
  stuff        @> @t}\vb{\formatlocal{\let\peekstash\stashtoterm}}{@> @<Rest of line@> @t}\vb{FAKE}{@> @={@> a = f( x ); @=}            
@g
@<A production@>@;

@ $\ldots$ even a single line can now be displayed properly.
@<A production@>=
@G
@t}\vb{\formatlocal{\skipheader} FAKE:}{@>
  more stuff in this line {@> b = g( y ); @=}
@g

@ With enough hidden context, even a small rule fragment can be
typeset as intended. The `action star' was inserted to reveal some of
the context.
@<Rest of line@>=
@G
@t}\vb{\formatlocal{\skipheader} FAKE:}{@>
  but not all of it
@t}\vb{\{\stashed{$\star$}\}}{@>
@g
@ What makes all of this even more confusing is that \CTANGLE\ will
have no trouble outputting this as a(n almost, due to the
intentionally bad \.{whoops} production above) valid \bison\ file
(as can be checked by looking into \.{sill.y}). The author
happens to think that one should not fragment the software into pieces
that are too small: \bison\ is not \Cee\ so it makes sense to write
\bison\ code differently. However, if the logic behind your code
organization demands such fine fragmentation, hidden context provides
you with a tool to show it off. A look inside the source of this
document shows that adding hidden context can be a bit ugly so it is
not recommended for routine use. The short example above is output in
the file below. 
@(sill.y@>=
  @<A silly example@>@;

@*1 On debugging. This concludes a short introduction to the \bison\
grammar pretty printing using this macro collection. It would be
incomplete, however, without a short reference to debugging\footnote{Here
we are talking about debugging the output produced by \CWEAVE\ when
the included \bison\ parser is used, {\it not\/} debugging parsers
written with the help of this software: the latter topic is covered in more
detail later on}. There is a
fair amount of debugging information that the macros can output,
unfortunately, very little of it is tailored to the {\it use\/} of the
macros in the \bison\ parser. Most of it is designed to help {\it
build\/} a new parser. If you find that the parser gives up too often
or even crashes (the latter is most certainly a bug in the parser
itself), the first approach is to make sure that your code {\it
compiles\/} i.e.\ forget about the printed output and try to see if
the `real' \bison\ accepts the code (just the syntax, no need to
worry about conflicts and such).

If this does not shed any light on why the macros seem to fail, turn
on the debugging output by saying \.{\\trace$\ldots$true} for various
trace macros.  This can produce {\it a lot\/} of output, even for
small fragments, so turn it on only for a section at a time.  If you
need still {\it more\/} details of the inner workings of the parser
and the lexer, various other debugging conditionals are available. For
example, \.{\\yyflexdebugtrue} turns on the debugging output for the
scanner. There are a number of such conditionals that are discussed in
the commentary for the appropriate \TeX\ macros.

Remember, what you are seeing at this point is the parsing process of
the \bison\ input file, not the one for {\it your\/} grammar (which
might not even be complete at this point). However, if this fails, you
are on your own: drop me a line if you figure out how to fix any bugs
you find.

@*1 Terminology. We now list a few definitions of the concepts used
repeatedly in this documentation. Most of this terminology is
rather standard. Formal precision is not the goal here, and intuitive
explanations are substituted whenever possible. 
{%
\def\aterm#1{\item{\sqebullet}{\ttl #1}: \ignorespaces}%
\setbox0=\hbox{\sqebullet\enspace}
\parindent=0pt
\advance\parindent by \wd0
\smallskip
\aterm{bison parser} while, strictly speaking, not a formally defined
term, this combination will always stand for one of the parsers generated
by this package designed to parse a subset of the `official' grammar for
\bison\ input files. All of these parsers are described later in
this documentation. The term {\it main parser\/} will be
used as a substitute in example documentation for the same purpose.

\aterm{driver} a generic but poorly defined concept. In this
documentation it is used predominantly to mean both the \Cee\ code and
the resulting executable that outputs the \TeX\ macros that contain the
parser tables, token values, etc., for the parsers built by the user. It
is understood that the \Cee\ code of the `driver' is unchanged and the
information about the parser itself is obtained by {\it including\/} the \Cee\
file produced by \bison\ in the `driver' (see the examples supplied 
with the package).

\aterm{lexer} a synonym for {\it scanner}, a subroutine that performs the {\it
lexical analysis\/} phase of the parsing process, i.e.\ groups various
characters from the input stream into parser {\it tokens}.

\aterm{namespace} this is an overused bit of terminology meaning a
set of names grouped together according to some relatively
well defined principle. In a language without a well developed type
system (such as \TeX) it is usually accompanied by a specially designed
naming scheme. {\it Parser namespaces\/} are commonly used in this
documentation to mean a collection of all the data structures describing a
parser and its state, including tables, stacks, etc., named by using the
`root' name (say \.{\\yytable}) and adding the name of the parser (for
example, \.{[main]}). To support this naming scheme, a number of
macros work in unison to create and rename the `data macros' accordingly.

\aterm{symbolic switch} a macro (or an associative array of macros)
that let the \TeX\ parser generated by the package associate {\it
symbolic term names\/} with the terms. Unlike the `real' parser, the
parser created with this suite requires some extra setup as explained
in the included examples (one can also consult the source for this
documentation which creates but does not use a symbolic switch).

\aterm{symbolic term name} a (relatively new) way to refer to stack
values in \bison. In addition to using the `positional' names such as
\.{\$}$n$ to refer to term values, one can utilize the new syntax:
\.{\$}\.{[}{\it name\/}\.{]}. The `{\it name}' can be assigned by the
user or can be the name of the nonterminal or token used in the
productions.

\aterm{term} in a narrow sense, an `element' of a grammar. Instead of
a long winded definition, an example, such as \prodstyle{ID} should
suffice. Terms are further classified into {\it terminals\/} (tokens)
and {\it nonterminals\/} (which can be intuitively thought of as
composite terms).

\aterm{token} in short, an element of a set. Usually encoded as an
integer by most parsers, an indivisible {\it term\/}
produced for the parser by the scanner. \TeX's scanner uses a more
sophisticated token classification, for example, $($character code,
character category$)$ pairs, etc. 

}
@** Languages, scanners, parsers, and \TeX. % Or $\ldots$
$$\vbox{\halign to\hsize{\kern-1.5pt\it#\hfil\tabskip0pt plus1fil\cr
Tokens and tables keep macros in check.\cr 
Make 'em with \bison, use \.{WEAVE} as a tool.\cr 
Add \TeX\ and \CTANGLE, and \Cee\ to the pool.\cr
Reduce 'em with actions, look forward, not back.\cr
Macros, productions, recursion and stack!\cr
\noalign{\vskip2pt}
\omit\hfil\eightpoint Computer generated (most likely)\cr}}
$$
\def\recount#1{${}^{(#1)}$}%
In order to understand the parsing routines in this collection, 
it would help to gain some familiarity with the internals of the
parsers produced by \bison\ for its intended target: \Cee. A person
looking inside a parser delivered by \bison\ would
quickly discover that the parsing procedure itself (|yyparse|)
occupies a rather small portion of the file. If (s)he were to further
reduce the size of the file by removing all the preprocessor
directives intended to anticipate every conceivable combination of the
operating system, compiler, and \Cee\ dialect, and various reporting
and error logging functions it would become very clear that the most
valuable product of \bison's labor is a collection of integer {\it
tables\/} that control the actions of the parser routine. Moreover,
the routine itself is an extremely concise and well-structured loop
composed of |goto|'s and a number of numerical conditionals. If one
were to think of a way of accessing arrays and processing conditionals
in the language of one's choice, once the tables produced by \bison\
have been converted into a form suitable for the consumption by the
appropriate language engine, the parser implementation becomes
straightforward. Or nearly so.

The {\it scanning\/} (or {\it lexing\/}) step of this process---a way
to convert a stream of symbols into a stream of integers, also
deserves some attention here. There are a number of excellent tools
written to automate this step in much the same fashion as \bison\
automates the generation of parsers. One such tool, \flex, though
(in the opinion of this author) slightly lacking in the simplicity and
elegance as compared to \bison, was used to implement the lexer for
this software suite. Lexing in \TeX\ will be discussed in considerable
detail later in this manual.

The language of interest in our case is, of course, \TeX, so our
future discussion will revolve around the five elements mentioned
above: \recount{1}data structures (mainly arrays and stacks), 
\recount{2}converting
\bison's output into a form suitable for \TeX's consumption, 
\recount{3}processing raw streams of \TeX's tokens and converting them into
streams of parser tokens, \recount{4}the implementation of \bison's
|yyparse| in \TeX, and, finally, \recount{5}producing \TeX\ output via {\it
syntax-directed translation} (which requires an appropriate
abstraction to represent \bison's actions inside \TeX). We shall
begin by discussing the parsing process itself.

@*1 Arrays, stacks and the parser.
Let us briefly examine the programming environment offered by \TeX.
Designed for typesetting, \TeX's remarkable language
provides a layer of macro processing atop of a set of commands that
produce the output fulfilling its primary mission: delivering page
layouts. In The \TeX book, macro {\it expansion\/} is likened to
mastication, whereas \TeX's main product, the typographic output is the
result of its `digestion' process. Not everything that goes through
\TeX's digestive tract ends up leaving a trace on the final page: a
file full of \.{\\relax}'s will produce no output, even though
\.{\\relax} is not a macro, and thus would have to be processed by
\TeX\ at the lowest level. 

It is time to describe the details of defining suitable data structures
in \TeX. At first glance, \TeX\ provides rather standard means of
organizing and using general memory. At the core of its generic
programming environment is an array of \.{\\count}$\,n$ {\it
registers\/}, which may be viewed as general purpose integer variables
that are randomly accessible by their indices. The integer arithmetic
machinery offered by \TeX\ is spartan but is very adequate for the sort of
operations a parser would perform: mostly additions and
comparisons.

Is the \.{\\count} array a good way to store tables in \TeX? Probably
not. The first factor is the {\it size\/} of this array: only 256
\.{\\count} registers exist in a standard \TeX\ (the actual number of
such registers on a typical machine running \TeX\ is significantly
higher but this author is a great believer in standards, and to his
knowledge, none of the standardization efforts in the \TeX\ world has
resulted in anything even close to the definitive masterpiece that is
The \TeX book). The issue of size can be mitigated to some extent by
using a number of other similar arrays used by \TeX\ (\.{\\catcode},
\.{\\uccode}, \.{\\dimen}, \.{\\sfcode} and others can be used for
this purpose as long as one takes care to restore the `sane' values
before control is handed off to \TeX's typesetting mechanisms). If a
table has to span several such arrays, however, the complexity of
accessing code would have to increase significantly, and the issue of
size would still haunt the programmer.

The second factor is the use of several registers by \TeX\ for special
purposes (in addition, some of these registers can only store a
limited range of values). Thus, the first 10 \.{\\count} registers are
used by plain \TeX\ for (well, {\it intended\/} for, anyway) the
purposes of page accounting: their values would have to be carefully
saved and restored before and after each parsing call,
respectively. Other registers (\.{\\catcode} in particular) have even
more disrupting effects on \TeX's internal mechanisms. While all of
this can be managed (after all, using \TeX\ as an arithmetic engine
such as a parser suspends the need for any typographic or other
specialized functions controlled by these arrays), the added
complexity of using several memory banks simultaneously and the speed penalty
caused by the need to store and restore register values make this
approach much less attractive.

What other means of storing arrays are provided by \TeX? Essentially,
only three options remain: \.{\\token} registers, macros holding whole
arrays, and associative arrays accessed through
\.{\\csname}$\,\ldots\,$\.{\\endcsname}. In the first two cases if care
is taken to store such arrays in an
appropriate form one can use \TeX's \.{\\ifcase} primitive to access
individual elements. The trade-off is the speed of such
access: it is {\it linear\/} in the size of the array for most
operations, and worse than that for others, such as removing the last 
item of an array. Using clever ways
of organizing such arrays, one can improve the linear access time to
$O(\log n)$ by simply modifying the access macros but at the moment, a
straightforward \.{\\ifcase} is used after expanding a list macro or
the contents of a \.{\\token}$\,n$ register in an {\it un\/}optimized
parser. An {\it optimized\/} parser uses associative arrays. 

The array discussion above is just as applicable to {\it stacks\/}
(indeed, an array is the most common form of stack
implementation). Since stacks pop up and disappear frequently (what
else are stacks to do?), list macros are usually used to store
them. The optimized parser uses a separate \.{\\count} register to
keep track of the top of the stack in the appropriate associative
array.

Let us now switch our attention
to the code that implements the parser and scanner {\it functions\/}. 
If one has spent some time writing \TeX\ macros of any sophistication
(or any macros, for that matter) (s)he must be familiar with the general
feeling of frustration and the desire to `just call a function here and move
on'. Macros produce {\it tokens\/}, however, and tokens must either
expand to nothing or stay and be contributed to your input, or worse,
be out of place and produce an error. One way to sustain a stream
of execution with macros is {\it tail recursion\/} (i.e.~always expanding the
{\it last token left standing}).

As we have already discussed, \bison's
|yyparse()| is a well laid out loop organized as a sequence of
|goto|'s (no reason to become religious about structured programming
here). This fact, and the following well known trick, make \Cee\ to \TeX\
translation almost straightforward. 

% The macro mess below looks painful but this is the only place such layout is used
% The approach can be easily generalized and put in limbo.sty but it seems
% a bit redundant at this point.

\newcount\piccount
\newdimen\lasthsize

\setbox5=\vtop{
\demomargin=0pt
\let\demoastyle\empty
\begindemo
^label A: ...
\nooutput
^    if**L**Krm(condition)**N
^         goto C;
\nooutput          
^label B: ...
\nooutput
^         goto A;
\nooutput
^label C: ...
\nooutput
\enddemo
}
\dp5=\z@@

\setbox3=\vtop{
\demomargin=0pt
\let\demoastyle\empty
\begindemo
^\if**L**Krm(condition)**N
^    \let\next=\labelC
^\else
^    \let\next=\labelAtail 
\enddemo
}
\dp3=\z@@

\newdimen\lastdepth

\def\startfitpar{%
    \bgroup
        \lasthsize=\hsize
        \advance\lasthsize-1.5in
        \vsize=\baselineskip
        \topskip=\z@@
        \setbox0\box2 % empty it
        % this sounds good at first but there is no good way to pull the insertions out after the 
        % box manipulations that follow; 
        % insertions will thus be contributed to whatever page was being worked on when the
        % picture insertions {\it started}; hence, if these happen to start at the very top of the page,
        % any insertion that follows will be contributed to the previous page; we correct this for footnotes
        % below
        %    \holdinginserts=1
        \output{%
            \global\setbox2=\vbox{
                \ifvoid2 
                \else
                    \prevdepth=\dp2
                    \unvbox2
                \fi
                \lastdepth=\dp255
                \unvbox255
                % this would be tempting, however, the \eject that follows should disappear
                % in addition, one really should not be playing with page breaking in the middle of
                % such tricky insertions
                %     \penalty\outputpenalty
                %     \kern-\lastdepth % to make sure \baselineskip is accounted for
            }%
        }\eject
        \output{%
            \setbox0=\vbox{%
                \unvbox255%
            }% \lastbox would almost work ... if not for insertions
            \global\advance\piccount1
            \global\setbox2=\vbox{%
                \prevdepth=\dp2 \unvbox2 
                \hbox to\hsize{%
                    \ifnum\piccount<15
                        \hbox to1.5in{%
                            \ifnum\piccount=1 
                                \ \box5
                            \fi
                        \hfill}%
                    \fi
                    \box0 \hfill
                    \ifnum\piccount=1 
                        \box3 \ %
                    \fi
                    \ifvoid\footins % reinsert footnotes
                    \else
                        \insert\footins{\unvbox\footins}%
                    \fi
                }%
            }%
        }%
        \parshape=15
             0pt 2.7in
             0pt 2.7in
             0pt 2.7in
             0pt 2.7in
             0pt 2.7in
             0pt 2.7in
             0pt 2.7in
             0pt \lasthsize
             0pt \lasthsize
             0pt \lasthsize
             0pt \lasthsize
             0pt \lasthsize
             0pt \lasthsize
             0pt \lasthsize
             0pt \hsize
}

\def\endfitpar{%
    \par
    \eject
    \egroup
    % see the comment above
    %     \holdinginserts=0
    \prevdepth=\dp2
    \unvbox2
}

\startfitpar
\noindent Given the code on the left (where |goto|'s
are the only means of branching but can appear inside conditionals),
one way to translate it into \TeX\ is to define a set of macros (call
them \.{\\labelA}, \.{\\labelAtail} and so forth for clarity) that end in
\.{\\next} (a common name for this purpose). Now, \.{\\labelA} will
implement the code that comes between \.{label A:} and \.{goto C;},
whereas \.{\\labelAtail} is responsible for the code after \.{goto C;}
and before \.{label B:}
(provided no other |goto|'s intervene which can always be
arranged). The conditional which precedes \.{goto C;} can now be written in
\TeX\ as presented on the right, where (condition) is an appropriate 
translation of the corresponding condition
in the code being translated (usually, one of `$=$' or `$\not=$'). Further
details can be extracted from the \TeX\ code that implements these
functions where the corresponding \Cee\ code is presented alongside
the macros that mimic its functionality%
\footnote{Running the risk of overloading the reader with details, the author 
would like to note that the actual implementation follows a {\it slightly\/} different
route in order to avoid any \.{\\let} assignments or changing the
meaning of \.{\\next}}. 
This concludes an overview of the general approach,
It is time to consider the way characters get consumed
on the lower levels of the macro hierarchy and the interaction between the different
layers of the package.
\endfitpar

@*1 \TeX\ into tokens. 
Thus far we have covered the ideas
behind items \recount{1} and \recount{4} on our list. It is time to
discuss the lowest level of processing done by these macros:
converting \TeX's tokens into the tokens consumed by the parser,
i.e.\ part\recount{3} of the plan. Perhaps, it would be most appropriate
to begin by defining the term {\it token}. 

As commonly defined, a token is simply an element of a set. Depending on
how much structure the said set possesses, a token can be represented by
an integer or a more complicated data structure. In the discussion
below, we will be dealing with two kinds of tokens: the tokens
consumed by the parsers and the \TeX\ tokens seen by the input
routines. The latter play the role of {\it characters\/} that combine
to become the former. \bison's internal representation for its tokens
is non-negative integers so this is what a scanner must
produce. 

\TeX's tokens are a good deal more sophisticated: they can be
either pairs $(c_{\rm ch}, c_{\rm cat})$, where $c_{\rm ch}$ is the
character code and $c_{\rm cat}$ is \TeX's category code ($1$ and $2$ for
group characters, $5$ for end of line, etc.), or {\it control
sequences\/}, such as \.{\\relax}. Some of these tokens (control
sequences and {\it active}, i.e.~category~13 characters) can have
complicated internal structure (expansion). The situation is further
complicated by \TeX's \.{\\let} facility, which can create
`character-like' control sequences, and the lack of conditionals
to distinguish them from the `real' characters. Finally, not all pairs
can appear as part of the input (say, there is no $(n, 0)$ token for
any $n$, in the terminology above).

The scanner expects to see {\it characters} in its input, which are
represented by their {\sc ASCII} codes, i.e.~integers between $0$ and
$255$ (actually, a more general notion of the Unicode character is
supported but we will not discuss it further). Before character codes
appear as the input to the scanner, however, and make its integer
table-driven mechanism `tick', a lot of work must be done to collect
and process the stream of \TeX\ tokens produced after \CWEAVE\ is done
with your input. This work becomes further complicated when the
typesetting routines that interpret the parser's output must sneak
outside of the parsed stream of text (which is structured by the
parser) and insert the original \TeX\ code produced by \CWEAVE\ into
the page.

\splint\ comes with a customizeable input routine of
moderate complexity (\.{\\yyinput}) that classifies all \TeX\ tokens
into seven categories: `normal' spaces (i.e.~category~10 tokens, 
skipped by \TeX's parameter scanning mechanism), 
`explicit' spaces (includes the control sequences \.{\\let} to \.{\ },
as well as \.{\\\ }), groups ({\it avoid} using \.{\\bgroup} and \.{\\egroup} in
your input but `real', \.{\{}$\ldots$\.{\}} groups are fine), active
characters, normal characters (of all character categories that can
appear in \TeX\ input, including \.{\$}, \.{\^}, \.{\#}, \.{a}--\.{Z},
etc.), single letter control sequences, and multi-letter control
sequences. Each of these categories can be processed separately to
`fine-tune' the input routine to the problem at hand. The input
routine is not very fast, instead, flexibility was the main
goal. Therefore, if speed is desirable, a customized input routine  
is a great place to start. As an example, a minimalistic
\.{\\yyinputtrivial} macro is included.

When \.{\\yyinput} `returns' by calling \.{\\yyreturn} (which is a
macro you design), your lexing routines have access to three
registers: \.{\\yycp@@}, that holds the character value of the
character just consumed by \.{\\yyinput}, \.{\\yybyte}, that most of
the time holds the token just removed from the input, 
and \.{\\yybytepure}, that (again, with very few
exceptions) holds a `normalized' version of the read character (i.e.~a
character of the same character code as \.{\\yycp@@}, and category~11
(to be even more precise (and to use nested parentheses), `normalized'
characters have the same category code as the current category code of
\.{@@})).

Most of the time it is the character code one needs (say, in the case
of \.{\\\{}, \.{\\\}}, \.{\\\&} and so on) but under some circumstances the
distinction is important (outside of \.{\\vb\{}$\ldots$\.{\}}, the sequence
\.{\\1} has nothing to do with the digit `\.{1}'). This mechanism
makes it easy to examine the consumed token. It also forms
the foundation of the `hidden context' passing mechanism described later.

The remainder of this section discusses the internals of \.{\\yyinput}
and some of the design trade-offs one has to make while working on
processing general \TeX\ token streams. It is typeset in `small print'
and can be skipped if desired.
\smallskip
\begingroup
\abovedisplayskip=5pt%
\abovedisplayshortskip=2pt%
\belowdisplayskip=5pt%
\belowdisplayshortskip=2pt%
\fnotesstart=1
\fnotesspan=2
\noofcolumns=2 
\icgap=1em%
\eightpoint
\linecount=73 
\setmcparams
\def\.#1{{\chardef\\=`\\\chardef\&=`\&\tt #1}}%
\dsskip=0pt%
\begindoublecols
To examine every token in its path (including spaces that are easy to
skip), the input routine uses one of the two well-known {\sc \TeX}nologies:
\.{\\futurelet\\next\\examinenext} or equally effective
\hbox{\.{\\afterassignment\\next\\let={\tt\char"20}}}.
Recursively inserting one of these sequences, \.{\\yyinput} can go
through any list of tokens, as long as it knows where to stop
(i.e.~return an end of file character). The
signal to stop is provided by the \.{\\yyeof}
primitive which should not appear in any `ordinary' text
presented for parsing, other than for the purpose of providing such a
stop signal. Even the dependence on \.{\\yyeof} can be eliminated if
one is willing to invest the time in writing macros that juggle \TeX's
\.{\\token} registers and only limit oneself to input from such
registers (which is, aside from an obvious efficiency hit, a strain on
\TeX's memory, as you have to store multiple (3 in the general case)
copies of your input to be able to back up when the lexer makes a
wrong choice). There does not seem to be a way of doing it unless the
text has been stored in a \.{\\token} register first (or storing the
whole input as a {\it parameter\/} for the appropriate macro: this
scheme is remarkably powerful and leads to {\it expandable\/} versions
of very complicated macros, although the amount of effort required to
write such macros grows at a frightening rate). All of these are
non-issues for the text inside \.{\\vb\{}$\ldots$\.{\}} and the care that
\.{\\yyinput} takes in processing characters inside such lists is an
overkill. In a more `hostile' environment (such as the one encountered
by the now obsolete \.{\\Tex} macros), this extra attention to detail pays
off in the form of a more robust input mechanism.

One subtlety deserves a special mention here, as it can be important
to the designer of `higher-level' scanning macros. Two types of tokens
are extremely difficult to deal with whenever \TeX's own lexing
mechanisms are used: (implicit) spaces and even more so, braces. We
will only discuss braces here, however, almost everything that follows
applies equally well to spaces (category 10 tokens to be precise), with
a few simplifications (or complications, in a couple of places). To
understand the difficulty, let's consider one of the approaches above:
$$
\.{\\futurelet\\next\\examinenext}.
$$
The macro \.{\\examinenext}
usually looks at \.{\\next} and inserts another macro (usually also called
\.{\\next}) at the very end of its expansion list. This macro usually
takes one parameter, to consume the next token. This mechanism works
flawlessly, until the lexer encounters a \.{\{}br\.{,}sp\.{\}}ace. The \.{\\next}
sequence, seen by \.{\\examinenext} contains a lot of information
about the brace ahead: it knows its category code (left brace, so $1$), its
character code (in case there was, say a \.{\\catcode`\\[=1{\tt\char`\ }}
earlier) but not whether it is a `real' brace (i.e.\ a character
\.{\{}$_1$) or an implicit one (a \.{\\bgroup}). There is no way to find
that out until the control sequence `launched' by \.{\\examinenext}
sees the token as a parameter. 

If the next token is a `real' brace, however,
\.{\\examinenext}'s successor will never see the token itself: the
braces are stripped by \TeX's scanning mechanism. Even if it finds a
\.{\\bgroup} as the parameter, there is no guarantee that the actual
input was not \.{\{\\bgroup\}}. One way to handle this is by using
\.{\\string} ahead of any consumption of the next token. If prior to
expanding \.{\\string} care has been taken to set the \.{\\escapechar}
appropriately (remember, we know the character code in advance), as
soon as one sees a character with \.{\\escapechar}'s character code,
(s)he knows that an implicit brace has just been seen. One added
complication to all this is that a very determined programmer can
insert an {\it active\/} character (using, say, the \.{\\uccode}
mechanism) that has the {\it same\/} character code as the {\it
brace\/} token that it has been \.{\\let} to! Setting this possibility
aside, the \.{\\string} mechanism (or, its cousin, \.{\\meaning}) is
not perfect: both produce a sequence of category 12 and 10 tokens. If
it is indeed a brace character that we just saw, we can consume the next
token and move on but what if this was a control sequence? After all,
just as easily as \.{\\string} makes a sequence into characters,
\.{\\csname}$\,\ldots\,$\.{\\endcsname} pair will make any sequence of
characters into a control sequence. Huh~$\ldots$

What we need is a backup mechanism: if one has a copy of the
token sequence ahead, one can use \.{\\string} to see if it is a real
brace first, and if it is, consume it and move on (the active character
case can be handled as the implicit case below, with one extra backup
to count how many tokens have been consumed). At this point one has to {\it
reinsert\/} the brace in case, at some point, a future `back up'
requires that the rest of the tokens are removed from the output (to
avoid `\.{Too many \}'s}' complaints from \TeX). This can be done by using
the \.{\\iftrue\{\\else\}\\fi} trick but of course, some bookkeeping is
needed to keep track of how far inside the brace groups we
are.

If it is an implicit brace, more work is needed: read all the
characters that \.{\\string} produced (an maybe more), then remember
the number of characters consumed. Remove the rest of the input using
the method described above and restart the scanning from the same point
knowing that the next token can be scanned as a parameter. 

Another strategy is to design a general enough macro that counts
tokens in a token register and simply recount the tokens after every
brace was consumed. 

Either way, it takes a lot of work. If anyone would
like to pursue the counting strategy, simple counting macros
are provided in \.{/examples/count/count.sty}.
The macros in this example
supply a very general counting mechanism that does not depend on
\.{\\yyeof} (or {\it any\/} other token) being `special' and can count the
tokens in any token register, as long as none of those tokens is an
\.{\\outer} control sequence. In other words, if the macro is used
immediately after the assignment to the token register, it should
always produce a correct count.

Needless to say, if such a general mechanism is desired, one has to
look elsewhere. The added complications of treating spaces (\TeX\
tends to ignore them most of the time) make this a torturous exercise
in \TeX's macro wizardry. The included \.{\\yyinput} has two ways of
dealing with braces: strip them or view the whole group as a
token. Pick one or write a different \.{\\yyinput}. Spaces, implicit
or explicit are reported as a specially selected character code and
consumed with a likeness of
$$
\hbox{\.{\\afterassignment\\moveon\\let\\next={\tt\char`\ }}}.
$$

Now that a steady stream of character codes is arriving at \.{\\yylex}
after \.{\\yyreturn} the job of converting it into numerical tokens  
is performed by the {\it scanner} (or {\it lexer\/}, or {\it tokenizer\/}, 
or even {\it tokener}), discussed in the next section.
\enddoublecols
\endgroup

@*1 Lexing in \TeX. In a typical system that uses a parser to process
text, the parsing pass is usually split into several stages: the raw
input, the lexical analysis (or simply {\it lexing}), and the parsing
proper. The {\it lexing\/} (also called {\it scanning}, we use these
terms interchangeably) clumps various sequences of characters into
{\it tokens\/} to facilitate the parsing stage. The reasons for this
particular hierarchy are largely pragmatic and are partially historic
(there is no reason that {\it parsing\/} cannot be done in multiple 
phases, as well, although it usually isn't).

If one remembers a few basic facts from the formal language theory, it
becomes obvious that a lexer, that parses {\it regular\/} languages,
can (theoretically) be replaced by an {\sc LALR} parser, that parses {\it
context-free\/} ones (or some subset thereof, which is
still a super set of all regular languages). A common justification given for
creating specialized lexers is efficiency and speed. The
reality is somewhat more subtle. While we do care about the efficiency of
parsing in \TeX, having a specialized scanner is important for
a number of different reasons.

The real advantage of having a dedicated scanner is the ease with which it
can match incomplete inputs and back up. A parser can, of course,
{\it recognize\/} any valid input that is also acceptable to a lexer, as well
as {\it reject\/} any input that does not form a valid token. Between
those two extremes, however, lies a whole realm of options that a
traditional parser will have great difficulty exploring. Thus, to
mention just one example, it 
is relatively easy to set up a DFA\footnote{Which stands for
Deterministic Finite Automaton, a common (and mathematically unique)
way of implementing a scanner for regular languages. Incidentally {\sc
LALR} mentioned above is short for Look Ahead Left to Right.} 
so that the {\it longest\/}
matching input is accepted. The only straightforward way to do this
with a traditional parser is to parse longer and longer inputs again
and again. While this process can be optimized to a certain degree,
the fact that a parser has a {\it stack\/} to maintain limits its
ability to back up.

As an aside, the mechanism by which \CWEB\ assembles its `scraps'
into chunks of recognized code is essentially iterative lexing,
very similar to what a human does to make sense of complicated
texts. Instead of trying to match the longest running piece of text,
\CWEB\ simply looks for patterns to combine inputs into larger
chunks, which can later be further combined. Note that this is not
quite the same as the approach taken by, say {\sc GLR} parsers, where
the parser must match the {\it whole\/} input or declare a
failure. Where a \CWEB-type parser may settle for the first available
match (or the longest available) a {\sc GLR} parser must try {\it
all\/} possible matches or use an algorithm to reject the majority of
the ones that are bound to fail in the end. 

This `\CWEB\ way' is also different from a traditional `strict' {\sc
LR} parser/scanner approach and certainly deserves serious
consideration when the text to be parsed possesses some rigid
structure but the parser is only allowed to process it one small
fragment at a time.

Returning to the present macro suite, the lexer produced by \flex\
uses integer tables similar to those employed by \bison\ so the
usual {\sc\TeX}niques used in implementing \.{\\yyparse} are fully
applicable to \.{\\yylex}. 

An additional advantage provided by having a \flex\ scanner implemented
as part of the suite is the availability of the original \bison\ scanner written
in \Cee\ for the use by the macro package.

This said, the code generated by \flex\ contains a few idiosyncrasies
not present in the \bison\ output. These `quirks' mostly involve
handling of end of input and error conditions. A quick glance at the
\.{\\yylex} implementation will reveal a rather extensive collection of
macros designed to deal with end of input actions.

Another difficulty one has to face in translating \flex\ output into
\TeX\ is a somewhat unstructured namespace delivered in the final
output (this is partially due to the \POSIX\ standard that \flex\
strives to follow). One consequence of this `messy' approach is that the
writer of a \flex\ scanner targeted to \TeX\ has to declare \flex\
`states' (more properly called {\it subautomata}) twice: first for the
benefit of \flex\ itself, and then again, in the {\it \Cee\ preamble\/}
portion of the code to output the states to be used by the action code
in the lexer. \.{Define\_State($\ldots$)} macro is provided for this
purpose. This macro can be used explicitly by the programmer or be
inserted by a specially designed parser. 
Using \CWEB\ helps to keep these declarations together.

The `hand-off' from the scanner to the parser is implemented
through a pair of registers: \.{\\yylval}, a token register
containing the value of the returned token and \.{\\yychar}, a
\.{\\count} register that contains the numerical value of the
token to be returned.

Upon matching a token, the scanner passes one crucial piece of
information to the user: the character sequence representing the token
just matched (\.{\\yytext}). This is not the whole story
though. There are three more token sequences that are made available
to the parser writer whenever a token is matched.

The first of these is simply a `normalized' version of
\.{\\yytext} (called \.{\\yytextpure}). In most cases it
is a sequence of \TeX\ tokens with the same character codes as the one
in \.{\\yytext} but with their category codes set to 11. In
cases when the tokens in \.{\\yytext} are {\it not}
$(c_{\rm ch}, c_{\rm cat})$ pairs, a few simple
conventions are followed, some of which will be explained below. This
sequence is provided merely for convenience and its typical use is to
generate a key for an associate array.

The other two sequences are special `stream pointers' that provide
access to the extended scanner mechanism in order to implement passing
of `formatting hints' to the parser without introducing any changes to
the original grammar. As the mechanism itself and the motivation
behind it are somewhat subtle, let me spend a few moments discussing
the range of formatting options desirable in a generic pretty-printer.

Unlike strict parsers employed by most compilers, a parser designed
for pretty printing cannot afford being too picky about the structure
of its input (\cite[Go] calls such parsers `loose').  To provide 
a simple illustration, an isolated identifier, such as `\.{lg\_integer}'
can be a type name, a variable name, or a structure tag (in a language like
\Cee\ for example). If one expects the pretty printer to typeset this
identifier in a correct style, some context must be supplied, as
well. There are several strategies a pretty printer can employ to get
a hold of the necessary context. Perhaps the simplest way to handle
this, and to reduce the complexity of the pretty printing algorithm is
to insist on the user providing enough context for the parser to do
its job. For short examples like the one above, this is an acceptable
strategy. Unfortunately, it is easy to come up with longer snippets of
grammatically deficient text that a pretty printer should be expected
to handle. Some pretty printers, such as the one employed by \CWEB\
and its ilk (the original \.{WEB}, \.{FWEB}), use a very flexible
bottom-up technique that tries to make sense of as large a portion of
the text as it can before outputting the result (see also \cite[Wo],
which implements a similar algorithm in \LaTeX).

The expectation is that this algorithm will handle the majority (about
90\%? it would be interesting to carry out a study in the spirit of
the ones discussed in \cite[Jo] to find out) of the
cases with the remaining few left for the author to correct. The
question is, how can such a correction be applied?

\CWEB\ itself provides two rather different mechanisms for handling
these exceptions. The first uses direct typesetting commands (for
example, \.{@@/} and \.{@@\#} for canceling and
introducing a line break, resp.) to change the typographic output.

The second (preferred) way is to supply {\it hidden context\/} to the
pretty-printer. Two commands, \.{@@;} and
\.{@@[}$\ldots$\.{@@]} are used for this purpose. The
former introduces a `virtual semicolon' that acts in every way like a
real one except it is not typeset (it is not output in the source file
generated by \CTANGLE, either but this has nothing to do with pretty
printing, so I will not mention \CTANGLE\ anymore). For
instance, from the parser's point of view, if the preceding text was
parsed as a `scrap' of type {\it exp}, the addition of \.{@@;}
will make it into a `scrap' of type {\it stmt\/} in \CWEB's
parlance. The second construct (\.{@@[}$\ldots$\.{@@]}),
is used to create an {\it exp\/} scrap out of whatever happens to be
inside the brackets.

This is a powerful tool at the author's disposal. Stylistically,
this is the right way to handle exceptions as it forces the writer to
emphasize the {\it logical\/} structure of the formal
text. If the pretty printing style is changed
extensively later, the texts with such hidden contexts should be able to
survive intact in the final document (as an example, using a break
after every statement in \Cee\ may no longer be considered
appropriate, so any forced break introduced to support this convention
would now have to be removed, whereas \.{@@;}'s would simply
quietly disappear into the background).

The same hidden context idea has another important advantage: with
careful grammar fragmenting (facilitated by \CWEB's or any other
literate programming tool's `hypertext' structure) and a more diverse
hidden context (or even arbitrary hidden text) mechanism, it is
possible to use a strict parser to parse incomplete language
fragments. For example, the productions that are needed to parse
\Cee's expressions form a complete subset of the grammar. If the
grammar's `start' symbol is changed to {\it expression\/} (instead of
the {\it translation-unit\/} as it is in the full \Cee\ grammar), a
variety of incomplete \Cee\ fragments can now be parsed and
pretty-printed. Whenever such granularity is still too `coarse',
carefully supplied hidden context will give the pretty printer enough
information to adequately process each fragment. A number of such {\it
sub}-parsers can be tried on each fragment (this may sound
computationally expensive, however, in practice, a carefully chosen
hierarchy of parsers will finish the job rather quickly) until a
correct parser produced the desired output (this approach is similar
to, although not quite the same one employed by the {\it General LR
parsers}).

This somewhat lengthy discussion brings us to the question directly
related to the tools described in this article: how does one provide
typographical hints or hidden context to the parser?

One obvious solution is to build such hints directly into the
grammar. The parser designer can, for instance, add new tokens
(say, \.{BREAK\_LINE}) to the grammar and extend the
production set to incorporate the new additions. The risk of
introducing new conflicts into the grammar is low (although not
entirely non-existent, due to the lookahead limitations of LR(1)
grammars) and the changes required are easy, although very tedious, to
incorporate.

In addition to being labor intensive, this solution has two other
significant shortcomings: it alters the original grammar and hides its
logical structure; it also `bakes in' the pretty-printing conventions
into the language structure (making `hidden' context much less
`stealthy'). It does avoid the `synchronicity problem' mentioned
below.

A marginally better technique is to introduce a new regular expression
recognizable by the scanner which will then do all the necessary
bookkeeping upon matching the sequence. All the difficulties with
altering the grammar mentioned above apply in this case, as well, only
at the `lexical analysis level'. At a minimum, the set of tokens
matched by the scanner would have to be changed.

A much better approach involves inserting the hints at the input stage and
passing this information to the scanner and parser as part of the token `values'. The
hints themselves can masquerade as characters ignored by the scanner
(white space, for example) and preprocessed by a specially designed
input routine. The scanner then simply passes on the values to the
parser. This makes hints, in effect, invisible.

The difficulty lies in synchronizing the token production with the
parser. This subtle complication is very familiar to anyone who has
designed \TeX's output routines: the parser and the lexer are not
synchronous, in the sense that the scanner might be reading several
(in the case of the general LR$(n)$ parsers) tokens ahead of the
parser before deciding on how to proceed (the same way \TeX\ can
consume a whole paragraph's worth of text before exercising its page
builder).

If we simple-mindedly let the scanner return every hint it has encountered
so far, we may end up feeding the parser the hints meant for the token
that appears {\it after\/} the fragment the parser is currently working
on. In other words, when the scanner `backs up' it must correctly back
up the hints as well.

This is exactly what the scanner produced by the tools in this package
does: along with the main stream of tokens meant for the parser, it
produces two hidden streams (called the \.{\\format} stream and
the \.{\\stash} stream) and provides the parser with two
strings (currently only strings of digits are used although arbitrary
sequences of \TeX\ tokens can be used as pointers) with the promise
that {\it all the `hints' between the beginning of the corresponding
stream and the point labeled by the current stream pointer appeared
among the characters up to and, possibly, including the ones matched
as the current token}. The macros to extract the relevant parts of the
streams (\.{\\yyreadfifo} and its cousins) are provided for the
convenience of the parser designer. The interested reader can consult
the input routine macros for the details of the internal
representation of the streams.

In the interest of full disclosure, let me point out that this simple
technique introduces a significant strain on \TeX's
computational resources: the lowest level macros, the ones that handle
character input and are thus executed (sometimes multiple times), for
{\it every\/} character in the input stream are rather complicated and
therefore, slow. Whenever the use of such streams is not desired a simpler
input routine can be written to speed up the process (see
\.{\\yyinputtrivial} for a working example of such macro).

Finally, while probably not directly related to the present
discussion, this approach has one more interesting feature: after the
parser is finished, the parser output and the streams exist
`statically', fully available for any last minute preprocessing or for
debugging purposes, if necessary. Under most circumstances, the parser
output is `executed' and the macros in the output are the ones reading
the various streams using the pointers supplied at the parsing stage
(at least, this is the case for all the parsers supplied with the
package).

@*1 Inside semantic actions: switch statements and `functions' in \TeX. 
Now you have a lexer for your input, and a grammar ready to be put into
action (we will talk about actions a bit later). It is time to discuss
how the tables produced by \bison\ get converted into \TeX\ {\it macros\/}
that drive the parser in {\it \TeX}.

The tables that drive the \bison\ input parsers
are collected in various \.{\{b,d,f,g,n\}yytab.tex} and \.{small\_tab.tex}. Each
one of these files contains the tables that implement a specific parser
used during different stages of processing.
Their exact function is well explained
in the source file produced by \bison\ ({\it how} this is done is
explained elsewhere, see \cite[Ah] for a good reference). It would
suffice to mention here that there are three types of tables in this
file: \recount{1}numerical tables such as \.{\\yytable} and
\.{\\yycheck} (both are either \TeX's token registers in an
unoptimized parser or associate arrays in an optimized version of such
as discussed below),
\recount{2}a string array \.{\\yytname}, and \recount{3}an action
switch. The action switch is what gets called when the parser does a
{\it reduction}. It is easy to notice that the numerical tables come
`premade' whereas the string array consisting of token names 
is difficult to recognize. This is intentional: this form of initialization 
is designed to allow the widest range of
characters to appear inside names. The macros that do this reside in
\.{yymisc.sty}. The generated table files also contain 
constant and token declarations used by the parser.

The description of the process used to output \bison\ tables in an
appropriate form continues in the section about
\locallink{bsfile}outputting \TeX\ tables\endlink, we pick it up here
with the description of the syntax-directed translation and the
actions.  The line
$$
\.{\\switchon\\next\\in\\currentswitch}
$$
is responsible for calling an appropriate action in the current
switch, as is easy to infer. A {\it switch\/} is also a macro that
consists of strings of \TeX\ tokens intermixed with \TeX\ macros
inside braces. Each group of macros
gets executed whenever the character or the group of characters in
\.{\\next} matches a substring preceding the braced group. If there
are two different substrings
that match, only the earliest group of macros gets expanded.
Before a state is
used, a special control sequence,
\.{\\setspecialcharsfrom\\switchname} can be used to put the \TeX\
tokens in a form suitable for the consumption by \.{\\switchon}'s. The
most important step it performs is it {\it turns every token in the
list into a character with the same character code and category
12\/}.  Thus \.{\\\{} becomes \.{\{}$_{12}$. There are other ways of
inserting tokens into a state: enclosing a token or a string of tokens in
\.{\\raw...\\raw} adds it to the state macro unchanged. If you have
a sequence of category 12 characters you want to add to the state, put
it after \.{\\classexpand} (such sequences are usually prepared by the
\.{\\setspecialchars} macro that uses the token tables generated by
\bison\  from your grammar). 

You can give a case a readable label (say, \.{brackets}) and enclose
this label in \.{\\raw}$\ldots$\.{\\raw}. A word of caution: an `a'
inside of \.{\\raw}$\ldots$\.{\\raw} (which is most likely an
\.{a}$_{11}$ unless you played with category codes before loading the
\.{\\switchon} macros) and the one outside it are two different
characters, as one is no longer a letter (category 11) in the eyes of
\TeX\ whereas the other one still is. For this reason one should not
use characters other than letters in h\.{\{}is\.{,}er\.{\}} state
names: the way a state picks an action does not distinguish between,
say, a `\.{(}' in `\.{(letter)}' and a stand alone `\.{(}' and may
pick an action that you did not intend. This applies even if `\.{(}'
is not among the characters explicitly inserted in the state macro: if
an action for a given character is not found in the state macro, the
\.{\\switchon} macro will insert a current \.{\\default} action
instead, which most often you would want to be \.{\\yylex} or
\.{\\yyinput} (i.e.\ skip this token). If `\.{(}' or `\.{)}' matches
the braced group that follows `\.{(letter)}' chaos may ensue (most
likely \TeX\ will keep reading past the \.{\\end} or \.{\\yyeof} that
should have terminated the input).  Make the names of character
categories as unique as possible: the \.{\\switchon} is simply a
string matching mechanism, with the added distinction between
characters of different categories.

Finally, the construct \.{\\statecomment}{\it
anything\/}\.{\\statecoment} allows you to insert comments in the
state sequence (note that the state {\it name\/} is put at the
beginning of the state macro (by \.{\\setspecialcharsfrom})
in the form of a special control sequence
that expands to nothing: this elaborate scheme is needed because
another control sequence can be \.{\\let} to the state macro which
makes the debugging information difficult to decipher). The debugging
mode for the lexer implemented with these macros is activated by 
\.{\\tracedfatrue}.

The functionality of the \.{\\switchon} macros (for `historical'
reasons, one can also use \.{\\action} as a synonym) has been
implemented in a number of other macro packages (see \cite[Fi] that
discusses the well-known and widely used \.{\\CASE} and \.{\\FIND}
macros). The macros in this collection have the additional property
that the only assignments that persist after the \.{\\switchon}
completes are the ones performed by the user code inside the selected
case.

This last property of the switch macros is implemented using another
mechanism that is part of this macro suite: the `subroutine-like'
macros, \.{\\begingroup}$\ldots$\.{\\tokreturn}. For examples, an
interested reader can take a look at the macros included with the
package. A typical use is
\.{\\begingroup}$\ldots$\.{\\tokreturn\{\}\{\\toks0 \}\{\}} which will
preserve all the changes to \.{\\toks0} and have no other side effects
(if, for example, in typical \TeX\ vernacular, \.{\\next} is used
to implement tail recursion inside the group, after the
\.{\\tokreturn}, \.{\\next} will still have the same value it
had before the group was entered). This functionality comes at the
expense of some computational efficiency.

This covers most of the routine computations inside semantic actions,
all that is left is a way to `tap' into the stack automaton
built by \bison\ using an interface similar to the special
\.{\$$n$} variables utilized by the `genuine' \bison\ parsers
(i.e.\ written in \Cee\ or any other target language supported by
\bison).

This role is played by the several varieties of \.{\\yy$\,p$} command
sequences (for the sake of completeness, $p$ stands for one of \.{($n$)},
\.{[{\rm name}]}, \.{]{\rm name}[} or $n$, here $n$ is a
string of digits, and a `name' is any name acceptable as a symbolic
name for a term in \bison). Instead
of going into the minutia of various flavors of \.{\\yy}-macros, let me
just mention that one can get by with only two `idioms' and still
be able to write parsers of arbitrary sophistication:
\.{\\yy($n$)} can be treated as a token register containing the
value of the $n$-th term of the rule's right hand side, $n>0$. The left
hand side of a production is accessed through \.{\\yyval}. A
convenient shortcut is \.{\\yy0\{{\rm \TeX\space material}\}} which
will expand the `\TeX\ material' inside the braces. Thus, a simple way
to concatenate the values of the first two production terms is
\.{\\yy0\{\\the\\yy(1)\\the\\yy(2)\}}. The included \bison\
parser can also be used to provide support for `symbolic names',
analogous to \bison's \.{{\$}[{\rm name}]} but a
bit more effort is required on the user's part to initialize such support. 
Using symbolic names can make the parser more readable and maintainable, 
however.

There is also a \.{\\bb$\,n$} macro, that provides access to the term
values in the `natural order' (e.g.~\.{\\bb1} is the last term read). Its
intended use is with the `inline' rules (see the main parser for
such examples). As of version \.{3.0} \bison\ no longer outputs
|yyrhs| and |yyprhs|, which makes it impossible to produce the
|yyrthree| array necessary for processing such rules in the `left to right'
order. One might also note that the new notation is better suited for
the inline rules since the value that is pushed on the stack is that
of \.{\\bb0}, i.e.~the term implicitly inserted by \bison. Be aware
that there are no \.{\\bb[$\cdot$]} or \.{\\bb($\cdot$)} versions of
these macros, for obvious reasons. A less obvious feature of this
macro is its `nonexpandable' nature. This means they cannot be used
inside \.{\\edef}. Thus, the most common use pattern is
\.{\\bb$\,n$\{\\toks$\,m$\}} with a subsequent expansion of
\.{\\toks$\,m$}. Making these macros expandable is certainly possible
but does not seem crucial for the intended limited use pattern.

Naturally, a parser writer may need a number of other data
abstractions to complete the task. Since these are highly dependent on
the nature of the processing the parser is supposed to provide, we
refer the interested reader to the parsers included in the package as
a source of examples of such specialized data structures.

One last remark about the parser operation is worth making here:
the parser automaton itself does not make any \.{\\global}
assignments. This (along with some careful semantic action writing)
can be used to `localize' the effects of the parser operation and,
most importantly, to create `reentrant' parsers that can, e.g.\ call
{\it themselves\/} recursively.

@*1 `Optimization'.
By default, the generated parser and scanner keep all of their tables
in separate token registers. Each stack is kept in a single macro (this
description is further complicated by the support for parser {\it
namespaces\/} that exists even for unoptimized parsers but this
subtlety will not be mentioned again---see the macros in the package
for further details). Thus, every time a table
is accessed, it has to be expanded making the table access latency
linear in {\it the size of the table}. The same holds for stacks and
the action `switches', of
course. While keeping the parser tables (which are immutable) in token
registers does not have any better rationale than saving the control
sequence memory (the most abundant memory in \TeX), this way of
storing {\it stacks} does have an advantage when multiple parsers get
to play simultaneously. All one has to do to switch from one parser to
another is to save the state by renaming the stack control sequences
accordingly. 

When the parser and scanner are `optimized', all these control
sequenced are `spread over' appropriate associative arrays. One caveat
to be aware of: the action switches for both the parser and the scanner
have to be output differently (a command line option is used to
control this) for optimized and unoptimized parsers. While it is
certainly possible to optimize only some of the parsers (if your
document uses multiple) or even only some {\it parts\/} of a given
parser (or scanner), the details of how to do this are rather
technical and are left for the reader to discover by reading the
examples supplied with the package. At least at the beginning it is
easier to simply set the highest optimization level and use it
consistently throughout the document.

@*1 {\it \TeX\/} with a different {\sl slant} or do you C an escape?. 
%\def\texnspace{other}
Some \TeX\ productions below probably look like alien script. 
The authors of \cite[Er] cite a number of reasons pretty printing of
\TeX\ in general is a nearly impossible task. The macros included with
the package follow a very straightforward strategy and do not try to
be very comprehensive. Instead, the burden of presenting \TeX\ code in
a readable form is placed on the programmer. Appropriate hints can be
supplied by means of indenting the code, using assignments ($=$) where
appropriate, etc. If you would rather look at straight \TeX\ 
instead, the line \.{\\def\\texnspace\{other\}} at the beginning of
this section can be uncommented and 
|TeX_( "/noexpand/inmath{/yy0{/yy1{}}}" );| becomes
\def\texnspace{other}%
|TeX_( "/noexpand/inmath{/yy0{/yy1{}}}" );|.
\def\texnspace{texline}%
There is, however, more to this story. A look at the actual file will
reveal that the line above was typed as 
$$
\.{TeX\_( "/noexpand/inmath\{/yy0\{/yy1\{\}\}\}" );}
$$ 
The `escape character' is leaning the other way! 
The lore of \TeX\ is uncompromising: `\.{\\}' is {\it the\/} escape 
character. What is the reason to avoid it in this case? 

The mystery is not very deep: `\.{/}' was chosen as an escape character
by the parser macros (a quick glance at \.{?yytab.tex} will reveal as
much). There is, of course, nothing sacred (other than tradition,
which this author is trying his hardest to follow) about what character code
the escape character has. The reason to look for the alternative is straightforward: `\.{\\}' is
a special character in \Cee, as well (also an `escape' in fact). The line
\.{TeX\_( "..." );} is a {\it macro-call\/} but $\ldots$ in \Cee. This
function simply prints out (almost `as-is') the line in
parenthesis. An attempt at \.{TeX\_( "\\noexpand" );} would result in
\numberlinestrue
\begindemo
^
^oexpand
\enddemo 
\numberlinesfalse
Other escape combinations\footnote{Here is a full list of {\it
defined\/} escaped characters in \Cee: \.{\\a}, \.{\\b}, \.{\\f}, \.{\\n},
\.{\\r}, \.{\\t}, \.{\\v}, \.{\\}{$[$\it octal digit$]$}, \.{\\'},
\.{\\"}, \.{\\?}, \.{\\\\}, \.{\\x}, \.{\\u}, \.{\\U}. Note that the
last three combinations must be followed by a specific string of
characters to appear in the input without generating errors.}  are
even worse: most are simply undefined. If anyone feels trapped without 
an escape, however, the same line can be typed as
$$
\.{TeX\_( "\\\\noexpand\\\\inmath\{\\\\yy0\{\\\\yy1\{\}\}\}" );}
$$
Twice the escape! 

If one were to look closer at the code, another oddity stands
out: there are no \.{\$}'s anywhere in sight. 
The big money, \.{\$} is a beloved character in
\bison. It is used in action code to reference the values of the
appropriate terms in a production. If mathematics pays your bills, use
\.{\\inmath} instead.

@*1 The \bison\ parser(s). 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. 

@s TeX_  TeX
@s TeXa  TeX
@s TeXb  TeX
@s TeXf  TeX
@s TeXfo TeX
@s TeXao TeX

@(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 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 `chicken and egg'). Hence the name `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 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').
\saveparseoutputtrue
@(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.
\saveparseoutputfalse
%\traceparserstatestrue
%\tracestackstrue
%\tracerulestrue
%\traceactionstrue
\saveparseoutputtrue
@(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

@ 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.
\traceparserstatesfalse
\tracestacksfalse
\tracerulesfalse
\traceactionsfalse
\checktablefalse 
\saveparseoutputfalse
@(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

@ The first two options are essential for the parser operation. The
start symbol can be set implicitly by listing the appropriate
production first.
@q %define lr.type canonical-lr @>
@q Make not on this and lexing too much lookahead and the \stashed trick@>
@q Explain other options @>
@<Grammar parser \bison\ options@>=
@G
%token-table
%debug
%start input
@g

@*2 Grammar rules. 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 each 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. 
@<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.
@<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

@ Extra tokens for typesetting \flex\ state 
declarations and options are declared in addition to the ones that a 
standard \bison\ parser recognizes.
@<Tokens and...@>=
@G
%token FLEX_OPTION FLEX_STATE_X FLEX_STATE_S
@g

@ 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
`genuine' \bison's \.{\$}\.{[}$\ldots$\.{]} syntax.
@<Parser full productions@>=
@G
@t}\vb{\inline}{@>
input:
  prologue_declarations 
      "%%" grammar epilogue.opt             {@> @<Finish the input setup@> @=}
;
@g

@ 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. 
@<Finish the input setup@>=
  @[TeX_( "/getsecond{/yy(3)}/to/toksa" );@]@; /* extract grammar contents */
  @[TeX_( "/yy0{/the/toksa}/table=/yy(0)" );@]@;

@ 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, 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.
@<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 one parametric option@> @=}
| "%expect-rr" INT                          {@> @[TeX_( "/toksa{expect-rr}" );@]@+@<Prepare 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}{/the/yy(2)}/the/yy(1)}" );@]@;

@ Some 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.
@<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{/the/yy(1)}{}}" ); @=}
| ID "=" symbol                             {@> TeX_( "/yy0{/nx/flexoptionpair{/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
prologue and the rules sections. Their treatment is very similar to
prologue-only options.
@<Parser common productions@>=
@G
grammar_declaration:
  precedence_declaration                    {@> @<Carry on@> @=}
| symbol_declaration                        {@> @<Carry on@> @=}
| "%start" symbol                           {@> @[TeX_( "/toksa{start}" );@]@+@<Prepare 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}{/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                                         {@> @<Carry on@> @=}
;

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                                        {@> @<Carry on@> @=}
;
@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{/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@>@;

@ These are the two most important rules for the bootstrap parser.
@<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}). Like any other separator, it takes
two parameters, stream pointers. 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}.
@<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                                        {@> @<Carry on@> @=}
| "<*>"                                      {@> @<Carry on@> @=}
| "<>"                                       {@> @<Carry on@> @=}
;
@g

@ {\it One token definition}.
@<Parser bootstrap productions@>=
@G
symbol_def:
  TAG                                        {@> @<Carry on@> @=}
@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 such implicit action.
@<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}" );@]@;

@ No pointers are provided for an {\it implicit\/} action.
@<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" );@]@;

@ @<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).
@<Parser grammar productions@>=
@G
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

@ @<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{/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{/the/yy(3)}/the/yy(2)}{/the/toksb}{/nx/rhsfullfalse}}" );@]@;
  @[TeX_( "/fi" );@]@;

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

@ @<Create a named reference@>=
  @<Carry on@>@;

@ 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@>=
  @<Carry on@>@;

@ @<Turn a character into a term@>=
  @<Carry on@>@;

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

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

@ @<Prepare the left hand side@>=
  @<Carry on@>@;

@ @<Prepare a string for use@>=
  @<Carry on@>@;

@ {\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                                         {@> @<Carry on@> @=}
| STRING                                     {@> @<Carry on@> @=}
;

value:
                                             {@> TeX_( "/yy0{}" ); @=}
| ID                                         {@> @<Carry on@> @=}
| STRING                                     {@> @<Carry on@> @=}
| "{...}"                                    {@> 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.
@<Union of grammar parser types@>=