Debian Codegraph @

doc/bibclean.ltx

raw
1 % -*-latex-*-
2 % Document name: /u/sy/beebe/tex/bibclean/doc/bibclean.ltx
3 % Creator: Nelson H.F. Beebe <[email protected]>
4 % Creation Date: Tue Dec 15 22:38:15 1992
5
6 %%% ====================================================================
7 %%% @LaTeX-file{
8 %%% author = "Nelson H. F. Beebe",
9 %%% version = "1.02",
10 %%% date = "31 December 1993",
11 %%% time = "12:46:45 MST",
12 %%% filename = "bibclean.ltx",
13 %%% address = "Center for Scientific Computing
14 %%% Department of Mathematics
15 %%% University of Utah
16 %%% Salt Lake City, UT 84112
17 %%% USA",
18 %%% telephone = "+1 801 581 5254",
19 %%% FAX = "+1 801 581 4148",
20 %%% checksum = "13962 3724 13766 111894",
21 %%% email = "[email protected] (Internet)",
22 %%% codetable = "ISO/ASCII",
23 %%% keywords = "BibTeX, bibliography, prettyprint, syntax check",
24 %%% supported = "yes",
25 %%% abstract = "This document describes bibclean, a BibTeX
26 %%% prettyprinter and syntax checker. It
27 %%% proposes a rigorous grammar for BibTeX, and
28 %%% provides a sample implementation of a lexical
29 %%% analyzer and parser to demonstrate the
30 %%% correctness and feasibility of the grammar.",
31 %%% docstring = "This document introduces bibclean, a BibTeX
32 %%% prettyprinter and syntax checker. It
33 %%% describes the features provided by bibclean
34 %%% for processing BibTeX files, and for
35 %%% producing output that can be readily used by
36 %%% other, simpler, programs.
37 %%%
38 %%% It argues that the current version of BibTeX
39 %%% has an unsound grammatical foundation, and
40 %%% that its user-friendliness could be improved
41 %%% by better error checking, and by new
42 %%% facilities.
43 %%%
44 %%% It then proposes a remedy in the form of a
45 %%% rigorous grammar that can be used to generate
46 %%% a lexical analyzer and parser for BibTeX
47 %%% files, and provides a sample implementation
48 %%% using the lex and yacc programs.
49 %%%
50 %%% The checksum field above contains a CRC-16
51 %%% checksum as the first value, followed by the
52 %%% equivalent of the standard UNIX wc (word
53 %%% count) utility output of lines, words, and
54 %%% characters. This is produced by Robert
55 %%% Solovay's checksum utility.",
56 %%% }
57 %%% ====================================================================
58
59 %%:=====================================================================
60 %%: ** NOTE ** NOTE ** NOTE ** NOTE ** NOTE ** NOTE ** NOTE ** NOTE **
61 %%: This paper is available with the bibclean distribution by the kind
62 %%: permission of the Editor of TUGboat, The Communications of the TeX
63 %%: User's Group. The index in the published paper was set in 3-column
64 %%: mode, but that style is not universally available in LaTeX
65 %%: implementations; in this version, it is set in 2-column mode, giving
66 %%: a few extra pages. At the time of publication, the most
67 %%: recently-available ltugboat.sty and tugboat.cmn files (included in
68 %%: the bibclean distribution) differ somewhat from those used to
69 %%: typeset the journal, so the page breaking in this version differs
70 %%: from the published article. This will be remedied as soon as
71 %%: possible.
72 %%:
73 %%: Because the index requires some editing which can be automated under
74 %%: the UNIX operating system, but not under some others, the bibclean
75 %%: distribution includes all of the intermediate files, and the TeX DVI
76 %%: file, so all that is needed to print the paper is a suitable DVI
77 %%: driver program. Only standard TeX fonts are required.
78 %%:
79 %%: The proper bibliographic reference to the published paper is
80 %%:
81 %%: @String{TUGboat = "TUGBoat"}
82 %%:
83 %%: @Article{Beebe:TB14-4-395-419,
84 %%: author = "Nelson H. F. Beebe",
85 %%: title = "Bibliography Prettyprinting and Syntax Checking",
86 %%: journal = TUGboat,
87 %%: year = "1993",
88 %%: volume = "14",
89 %%: number = "4",
90 %%: pages = "395--419",
91 %%: note = dec,
92 %%: bibdate = "Fri Dec 31 12:15:07 1993",
93 %%: }
94 %%:=====================================================================
95
96 \documentstyle[makeidx,path,texnames,bibclean]{ltugboat}
97
98 \setcounter{page}{395} % initial page number in TUGboat
99
100 \PrelimDraftfalse
101
102 \vol 14, 4.
103
104 \issdate December, 1993.
105
106 %=================================================
107
108 \title{%
109 Bibliography Prettyprinting and Syntax
110 Checking
111 }
112
113 \author{%
114 Nelson H. F. Beebe
115 }
116
117 \address{%
118 Center for Scientific Computing\\
119 Department of Mathematics\\
120 University of Utah\\
121 Salt Lake City, UT 84112\\
122 USA\\
123 Tel: +1 801 581 5254\\
124 FAX: +1 801 581 4148
125 }
126
127 \netaddress[\network{Internet}]{[email protected]}
128
129 \makeindex
130
131 %=================================================
132
133 \begin{document}
134
135 \mbox{}\newpage % force empty first column to match TUGboat copy
136
137 \maketitle
138
139 \tableofcontents
140
141 \listoftables
142
143 \bibliographystyle{is-plain}
144
145 \section{Introduction}%
146 \label{sec:intro}
147
148 \BibTeX{}
149 \cite[Appendix~B]{Lamport:LDP85}%
150 \index{Lamport, Leslie}
151 is a convenient tool for solving the vexing issue
152 of bibliography formatting. The user identifies
153 fields of bibliography entries via field\slash
154 value pairs and provides a unique citation key%
155 \index{citation!key}
156 and a document type for each entry. A simple
157 string substitution%
158 \index{string!substitution}
159 facility makes it easy to reuse
160 frequently-occurring strings. A typical example
161 looks like this:
162
163 \begin{verbatim}
164 @String{pub-AW =
165 "Ad{\-d}i{\-s}on-Wes{\-l}ey"}
166
167 @Book{Lamport:LDP85,
168 author = "Leslie Lamport",
169 title = "{\LaTeX}---A Document
170 Preparation System---User's
171 Guide and Reference Manual",
172 publisher = pub-AW,
173 year = "1985",
174 ISBN = "0-201-15790-X",
175 }
176 \end{verbatim}
177
178 The \TeX{} file contains citations of the form
179 \verb=\cite{Lamport:LDP85}=,%
180 \index{Lamport, Leslie}
181 together with a
182 \CS{bibliographystyle} command to choose a
183 citation%
184 \index{citation!style}
185 and bibliography style,%
186 \index{bibliography!style}
187 and a \CS{bibliography} command to specify
188 which \BibTeX{} files are to be used. \TeX{}
189 records this information in an auxiliary file.%
190 \index{auxiliary file}
191
192 A subsequent \BibTeX{} job step reads this
193 auxiliary file, extracts the requested
194 bibliographic entries from the specified \BibTeX{}
195 files, and outputs the entries into a bibliography
196 file%
197 \index{bibliography!file}%
198 \index{file!bibliography}
199 formatted according to the specified style.
200 Several dozen such styles%
201 \index{bibliography!style}%
202 \index{style!bibliography}
203 are currently available to help cope with the
204 bizarre variations in bibliography formats that
205 publishers have invented.
206
207 In a second \TeX{} step, the \CS{cite}
208 commands are not correctly expandable until the
209 \CS{bibliography} command is processed and the
210 bibliography file output by \BibTeX{} is read.
211 However, at that point, the desired form of the
212 citations is finally known, and at the end of the
213 job, an updated auxiliary file is written.
214
215 A third \TeX{} step finally has the necessary
216 information from the auxiliary file and the
217 bibliography file to correctly typeset the
218 \CS{cite} commands and the bibliography in
219 the specified style.
220
221 With the GNU Emacs text editor%
222 \index{GNU!Emacs}%
223 \index{Emacs}
224 \cite{Cameron:LGE91,%
225 Schoonover:GEU92},%
226 \index{Cameron, Debra}%
227 \index{Rosenblatt, Bill}
228 powerful \BibTeX{} editing support makes it simple
229 to generate bibliography entry descriptions via
230 templates%
231 \index{template!editor}
232 that can be inserted with a couple of
233 keystrokes, or on workstations, selected from a
234 pop-up menu.%
235 \index{pop-up menu}%
236 \index{menu!pop-up}
237 This editor is freely available on
238 \UNIX{}, \VAX{} \VMS{}, and the larger members of
239 the IBM PC family under \PCDOS{}.
240
241 The major benefits of using \BibTeX{} are the
242 potential for data reuse, the separation of form
243 and content (like the descriptive markup of
244 \LaTeX{} and \SGML{}%
245 \cite{Bryan:SAG88,%
246 vanHerwijnen:PS90}),%
247 \index{Bryan, Martin}%
248 \index{van Herwijnen, Eric}%
249 \index{Herwijnen, Eric van}
250 and the many stylistic variants of the typeset
251 bibliography. During the preparation of this
252 article, a scan of our Mathematics Department
253 workstation file system located about 14~000
254 \TeX{} files, and 445 \BibTeX{} files. The latter
255 contained about 870~000 lines and almost 94~000
256 bibliography entries. These files form a valuable
257 resource that authors and researchers can use to
258 track and properly cite literature in their
259 publications.
260
261 During my term as TUG President, I initiated a
262 project to collect%
263 \index{TUG bibliography collection}
264 \BibTeX{} styles and
265 bibliography data base files of material related
266 to \TeX{} and its uses, and electronic document
267 production and typography in general. This
268 dynamic collection also covers a few journals,
269 including more than 1000 entries for \TUB{}.%
270 \index{TUGboat@{\protect\TUB{}}}
271 A snapshot of part of the collection was published
272 in the 1991 TUG Resource Directory%
273 \index{TUG Resource Directory}
274 \cite{Beebe:TB12S-2-176,%
275 Beebe:TB12S-2-183}.%
276 \index{Beebe, Nelson H. F.}
277
278 One drawback of \BibTeX{} is that errors in a
279 bibliography file, such as unmatched quotation
280 marks around a value string, can sometimes be hard
281 to locate, because the current version of the
282 program raises an error at the end of a scan when
283 internal tables overflow after gobbling several
284 thousand characters of input. The result is that
285 the error location is completely bogus, and
286 actually lies much earlier in the file. We can
287 hope that this serious deficiency will be remedied
288 in the final version of \BibTeX{}, 1.0, which is
289 expected to appear when the \LaTeX{} 3.0
290 development is completed.
291
292 Another drawback is that such bibliography files
293 are normally prepared by human typists, and
294 consequently there are formatting variations that
295 reduce readability, and inconsistencies that
296 persist into the final typeset bibliography. Some
297 examples of such inconsistencies are variations in
298 naming of publishers and journals, spacing around
299 author and editor initials, and variations in
300 letter case in titles. In addition, there are
301 usually numerous typographical errors of omission,
302 doubling, spelling, transcription, translation,
303 and transposition.
304
305 In the fall of 1990, faced with a growing
306 collection of \BibTeX{} files, I set out to write
307 a software tool to deal with these problems. This
308 program is called \BIBCLEAN{}. It is a syntax
309 checker, portability verifier, and prettyprinter,
310 and was made freely available in 1991. In the
311 fall of 1992, after considerable experience with
312 the first version, I embarked on a set of
313 enhancements that produced major version 2.0, and
314 the purpose of this paper is to describe the new
315 version, and to widely advertise its existence to
316 the \TeX{} community.
317
318 \section{\protect\BibTeX{} needs improvement}
319
320 \BibTeX{}, like \TeX{}, assumes that its input is
321 prepared correctly, and works best when that is
322 the case. Both programs attempt to recover from
323 errors, but that recovery may be unsuccessful, and
324 errors may be detected only after lengthy
325 processing. In neither case is the output of
326 these programs suitable for input to them. That
327 is, their knowledge of how their input streams are
328 to be parsed is available only to them, and cannot
329 be applied independently and used by other
330 software. Both programs have a hazily-defined
331 input syntax, and \TeX{}'s is extensible, making
332 it even harder to give a precise description to
333 the user.
334
335 The trend of compiler technology development of
336 the last two decades, largely on \UNIX{} systems,
337 has been to separate the compilation task into
338 several steps.
339
340 The first is generally called {\em lexical
341 analysis},%
342 \index{lexical analysis}
343 or lexing. It breaks the input stream up into
344 identifiable tokens%
345 \index{token}
346 that can be represented by small integer constants
347 and constant strings.
348
349 The second step is called {\em parsing},%
350 \index{parsing}
351 which involves the verification that the tokens
352 streaming from the lexer conform to the
353 grammatical requirements of the language, that is,
354 that they make sense.
355
356 As parsing proceeds, an intermediate
357 representation is prepared that is suitable for
358 the third step, namely, {\em code generation\/}%
359 \index{code generation}
360 or
361 {\em interpretation}.%
362 \index{interpretation of code}
363
364 This division into subtasks diminishes the
365 complexity of writing a compiler, reduces its
366 memory requirements, and importantly, partitions
367 the job into two parts: a language-dependent, but
368 {\em architecture-independent}, part consisting of
369 lexing and parsing, and a language-independent,
370 but {\em architecture-dependent}, part where code
371 is generated or interpreted.
372
373 This makes it possible to write a front end%
374 \index{front end}
375 for
376 each language, and a back end%
377 \index{back end}
378 for each
379 architecture, and by combining them, obtain
380 compilers for all languages and all architectures.
381 The most successful example of this approach at
382 present is almost certainly the Free Software
383 Foundation's%
384 \index{Free Software Foundation}
385 GNU Project compilers, which support
386 all common computer architectures with the back
387 ends, and C, C++,%
388 \index{C++}
389 and Objective C%
390 \index{Objective C}
391 with the front
392 ends. Additional front ends for several other
393 popular languages are in preparation.
394
395 When a lexer is available as a separate program,
396 its output can be conveniently used by other
397 programs for tasks such as database lookup,
398 floating-point precision conversion, language
399 translation, linguistic analysis, portability
400 verification, prettyprinting, and checking of
401 grammar, syntax, and spelling.
402
403 In response to a command-line request, \BIBCLEAN{}
404 will function as a lexer%
405 \index{lexical analyzer}
406 instead of as a
407 prettyprinter.%
408 \index{prettyprinter}
409 An example is given later in
410 Section~\ref{sec:lexer}.
411
412 \section{Run-time options}
413
414 On several operating systems, \BIBCLEAN{} is run
415 by a command of the form
416 %
417 \begin{verbatim}
418 bibclean [options] bibfile(s) >newfile
419 \end{verbatim}
420 %
421 One or more bibliography files%
422 \index{bibliography!file}%
423 \index{file!bibliography}
424 can be specified; if none are given, input is
425 taken from the standard input stream. A specific
426 example is:
427 %
428 \begin{verbatim}
429 bibclean -no-fix-name mybib.bib >mybib.new
430 \end{verbatim}
431 %
432
433 Command-line switches may be abbreviated to a
434 unique leading prefix, and letter case is not
435 significant. All options are parsed before any
436 input bibliography files are read, no matter what
437 their order on the command line. Options that
438 correspond to a {\em yes\slash no\/} setting of a
439 flag have a form with a prefix \verb=no-= to set
440 the flag to {\em no}. For such options, the last
441 setting determines the flag value used. This is
442 significant when options are also specified in
443 initialization files (see Section~\ref{sec:init}).
444
445 On \VAX{} \VMS{} and IBM \PCDOS{}, the leading
446 hyphen on option names may be replaced by a slash;
447 however, the hyphen option prefix is always
448 recognized.
449
450 \begin{description}
451 \OPTIONITEM{author}
452 Display an author credit on the standard
453 error unit,%
454 \index{standard error unit}
455 \path=stderr=.%
456 \PATHINDEX{stderr}
457 Sometimes an executable program is separated
458 from its documentation and source code; this
459 option provides a way to recover from that.
460
461 \OPTIONITEM{error-log filename}
462 Redirect \path=stderr=%
463 \PATHINDEX{stderr}
464 to the indicated file,
465 which will then contain all of the error and
466 warning messages.%
467 \index{message!redirecting}%
468 \index{error!message!redirecting}%
469 \index{warning message!redirecting}
470 This option is provided
471 for those systems that have difficulty
472 redirecting \path=stderr=.%
473 \PATHINDEX{stderr}
474
475 \OPTIONITEM{help {\rm or} -?}
476 Display a help message%
477 \index{message!help}
478 on \path=stderr=,%
479 \PATHINDEX{stderr}
480 giving a sample command usage, and option
481 descriptions similar to the ones here.
482
483 \OPTIONITEM{init-file filename}
484 Provide an explicit value pattern
485 initialization file.%
486 \index{initialization file}%
487 \index{file!initialization}
488 It will be processed
489 after any system-wide and job-wide
490 initialization files found on the
491 \path=PATH=%
492 \PATHINDEX{PATH}
493 (for \VAX{} \VMS{}, \path=SYS$SYSTEM=)%
494 \PATHINDEX{SYS\$SYSTEM} and
495 \path=BIBINPUTS=%
496 \PATHINDEX{BIBINPUTS}
497 search paths, respectively,
498 and may override them. It in turn may be
499 overridden by a subsequent file-specific
500 initialization file. The initialization file
501 name can be changed at compile time, or at
502 run time through a setting of the environment
503 variable%
504 \index{environment variable}
505 \path=BIBCLEANINI=,%
506 \PATHINDEX{BIBCLEANINI}
507 but defaults to \path=.bibcleanrc=%
508 \PATHINDEX{.bibcleanrc}
509 on \UNIX{}, and to \path=bibclean.ini=%
510 \PATHINDEX{bibclean.ini}
511 elsewhere. For further details, see
512 Section~\ref{sec:init}.
513
514 \OPTIONITEM{max-width nnn}
515 Normally, \BIBCLEAN{} limits output line
516 widths%
517 \index{line!width limit}
518 to 72 characters, and in the interests
519 of consistency, that value should not be
520 changed. Occasionally, special-purpose
521 applications may require different maximum
522 line widths, so this option provides that
523 capability. The number following the option
524 name can be specified in decimal,%
525 \index{decimal}
526 octal%
527 \index{octal}
528 (starting with 0), or hexadecimal%
529 \index{hexadecimal}
530 (starting with 0x). A zero or negative value
531 is interpreted to mean unlimited, so
532 \OPTION{max-width 0} can be used to ensure
533 that each field/value pair appears on a
534 single line.
535
536 When \OPTION{no-prettyprint} requests
537 \BIBCLEAN{} to act as a lexical analyzer, the
538 default line width is unlimited, unless
539 overridden by this option.
540
541 When \BIBCLEAN{} is prettyprinting, line
542 wrapping%
543 \index{wrapping!of long lines}%
544 \index{line!wrapping}
545 will be done only at a space. Consequently,
546 an extremely long non-blank character
547 sequence may result in the output exceeding
548 the requested line width. Such sequences are
549 extremely unlikely to occur, at least in
550 English-language text, since even the
551 45-letter giant
552 \cite[p.~451]{Knuth:ct-a}%
553 \index{Knuth, Donald E.}
554 {\it pneu\-monoul\-tra\-mi\-cro\-scop\-ic%
555 \-sil\-i\-co\-vol\-canoco\-nio\-sis}
556 will fit in \BIBCLEAN{}'s standard
557 72-character output line, and so will
558 58-letter Welsh city names.
559
560 When \BIBCLEAN{} is lexing, line wrapping is
561 done by inserting a backslash-newline%
562 \index{backslash-newline}
563 pair
564 when the specified maximum is reached, so no
565 line length will ever exceed the maximum.
566
567 \OPTIONITEM{[no-]check-values}
568 With the positive form, apply heuristic
569 pattern matching to field values in order to
570 detect possible errors
571 (e.g.\ \path|year = "192"| instead of
572 \path|year = "1992"|), and issue warnings
573 when unexpected patterns are found.
574
575 This checking is usually beneficial, but if
576 it produces too many bogus warnings for a
577 particular bibliography file, you can disable
578 it with the negative form of this option.%
579 \index{warning message!disabling}
580 Default: {\em yes}.
581
582 \OPTIONITEM{[no-]delete-empty-values}
583 With the positive form, remove all
584 field\slash value pairs for which the value
585 is an empty string.%
586 \index{empty!values!deleting}
587 This is helpful in
588 cleaning up bibliographies generated from
589 text editor templates. Compare this option
590 with \OPTION{[no-]remove-OPT-prefixes}
591 described below.
592 Default: {\em no}.
593
594 \OPTIONITEM{[no-]file-position}
595 With the positive form, give detailed file
596 position information in warning and error
597 messages. Default: {\em no}.
598
599 \OPTIONITEM{[no-]fix-font-changes}
600 With the positive form, supply an additional
601 brace level around font changes%
602 \index{font changes!fixing}
603 in titles to
604 protect against downcasing by some \BibTeX{}
605 styles. Font changes that already have more
606 than one level of braces are not modified.
607
608 For example, if a title contains the
609 Latin phrase
610 {\tt \verb={\em= Dictyostelium
611 Discoideum\verb=}=} or
612 {\tt \verb={\em= \verb={D}=ictyostelium
613 \verb={D}=iscoideum\verb=}=}, then
614 downcasing will incorrectly convert the
615 phrase to lower-case letters. Most \BibTeX{}
616 users are surprised that bracing the initial
617 letters does not prevent the downcase action.
618 The correct coding is
619 {\tt \verb={{\em= Dictyostelium Discoideum\verb=}}=}.
620 However, there are also legitimate cases
621 where an extra level of bracing wrongly
622 protects from downcasing. Consequently,
623 \BIBCLEAN{} will normally not supply an extra
624 level of braces, but if you have a
625 bibliography where the extra braces are
626 routinely missing, you can use this option to
627 supply them.
628
629 If you think that you need this option, it is
630 strongly recommended that you apply
631 \BIBCLEAN{} to your bibliography file with
632 and without \OPTION{fix-font-changes}, then
633 compare the two output files to ensure that
634 extra braces are not being supplied in titles
635 where they should not be present. You will
636 have to decide which of the two output files
637 is the better choice, then repair the
638 incorrect title bracing by hand.
639
640 Since font changes in titles are uncommon,
641 except for cases of the type which this
642 option is designed to correct, it should do
643 more good than harm. Default: {\em no}.
644
645 \OPTIONITEM{[no-]fix-initials}
646 With the positive form, insert a space after
647 a period following author initials.%
648 \index{author name!period after initials}%
649 \index{editor name!period after initials}
650 Default:
651 {\em yes}.
652
653 \OPTIONITEM{[no-]fix-names}
654 With the positive form, reorder author and
655 editor name lists%
656 \index{author name!reordering}%
657 \index{editor name!reordering}
658 to remove commas at brace
659 level zero, placing first names or initials
660 before last names. Default: {\em yes}.
661
662 \OPTIONITEM{[no-]par-breaks}
663 With the negative form, a paragraph break
664 (either a formfeed, or a line containing only
665 spaces) is not permitted in value strings, or
666 between field\slash value pairs. This may be
667 useful to quickly trap runaway strings%
668 \index{runaway string argument}%
669 \index{string!runaway}
670 arising from mismatched delimiters.%
671 \index{mismatched delimiters}%
672 \index{delimiters!mismatched}
673 Default:
674 {\em yes}.
675
676 \OPTIONITEM{[no-]prettyprint}
677 Normally, \BIBCLEAN{} functions as a
678 prettyprinter.%
679 \index{prettyprinter}
680 However, with the negative
681 form of this option, it acts as a lexical
682 analyzer%
683 \index{lexical analyzer}
684 instead, producing a stream of
685 lexical tokens. See Section~\ref{sec:lexer}
686 for further details. Default: {\em yes}.
687
688 \OPTIONITEM{[no-]print-patterns}
689 With the positive form, print the value
690 patterns read from initialization files%
691 \index{initialization file!patterns in}%
692 \index{file!initialization!patterns in}
693 as
694 they are added to internal tables. Use this
695 option to check newly-added patterns, or to
696 see what patterns are being used.
697
698 When \BIBCLEAN{} is compiled with native
699 pattern-matching code (the default), these
700 patterns are the ones that will be used in
701 checking value strings for valid syntax, and
702 all of them are specified in initialization
703 files, rather than hard-coded into the
704 program. For further details, see
705 Section~\ref{sec:init}. Default: {\em no}.
706
707 \OPTIONITEM{[no-]read-init-files}
708 With the negative form, suppress loading of
709 system-, user-, and file-specific
710 initialization files.%
711 \index{initialization file}%
712 \index{file!initialization}
713 Initializations will
714 come only from those files explicitly given
715 by \OPTION{init-file filename} options.
716 Default: {\em yes}.
717
718 \OPTIONITEM{[no-]remove-OPT-prefixes}
719 With the positive form, remove the \verb=OPT=
720 prefix from each field name where the
721 corresponding value is not an empty string.%
722 \index{OPT- prefix@{\tt OPT-} prefix!removing}
723 The prefix \verb=OPT= must be entirely in
724 upper-case to be recognized.
725
726 This option is for bibliographies generated
727 with the help of the GNU Emacs%
728 \index{GNU!Emacs}%
729 \index{Emacs}
730 \BibTeX{}
731 editing support, which generates templates
732 with optional fields identified by the
733 \verb=OPT= prefix. Although the function
734 \path=M-x bibtex-remove-OPT= normally bound
735 to the keystrokes {\tt C-c C-o} does the job,
736 users often forget, with the result that
737 \BibTeX{} does not recognize the field name,
738 and ignores the value string. Compare this
739 option with \OPTION{[no-]delete-empty-values}
740 described above. Default: {\em no}.
741
742 \OPTIONITEM{[no-]scribe}
743 With the positive form, accept input syntax
744 conforming to the \SCRIBE{} document system.
745 The output will be converted to conform to
746 \BibTeX{} syntax. See
747 Section~\ref{sec:scribe} for further details.
748 Default: {\em no}.
749
750 \OPTIONITEM{[no-]trace-file-opening}
751 With the positive form, record in the error
752 log file%
753 \index{error!log file}%
754 \index{file!error log}
755 the names of all files which
756 \BIBCLEAN{} attempts to open. Use this
757 option to identify where initialization
758 files%
759 \index{initialization file!locating}%
760 \index{file!initialization!locating}
761 are located. Default: {\em no}.
762
763 \OPTIONITEM{[no-]warnings}
764 With the positive form, allow all warning
765 messages.%
766 \index{warning message!disabling}%
767 \index{message!disabling warning}
768 The negative form is not
769 recommended since it may mask problems that
770 should be repaired. Default: {\em yes}.
771
772 \OPTIONITEM{version}
773 Display the program version%
774 \index{program!version}
775 \index{version!of program}
776 number on
777 \path=stderr=.%
778 \PATHINDEX{stderr}
779 This will also include an
780 indication of who compiled the program, the
781 host name on which it was compiled, the time
782 of compilation, and the type of string-value
783 matching code selected, when that information
784 is available to the compiler.
785 \end{description}
786
787 \section{Prettyprinting}
788
789 \index{prettyprinting}%
790 A prettyprinter for any language must be able to
791 deal with more than just those files that strictly
792 conform to the language grammar. For programming
793 languages, most compilers implement language
794 extensions that prettyprinters must recognize and
795 try to deal with gracefully. \BIBCLEAN{}
796 recognizes two such input languages: \BibTeX{} and
797 \SCRIBE{}.
798
799 Ideally, a prettyprinter should be able to produce
800 output even in the presence of input errors,
801 displaying it in such a way as to make the
802 location of the errors more evident. \BIBCLEAN{}
803 provides detailed error and warning messages to
804 help pinpoint errors. With the
805 \OPTION{file-position} command-line option, it
806 will flag the byte, column, and line, positions of
807 the start and end of the current token in both
808 input and output files.
809
810 Here is a summary of the actions taken by
811 \BIBCLEAN{} on its input stream.
812 \begin{itemize}
813 \item
814 Space between entries is discarded, and
815 replaced by a single blank line.
816
817 \item
818 Space around string concatenation
819 operators is standardized.
820
821 \item
822 Leading and trailing space in value
823 strings is discarded, and embedded
824 multiple spaces are collapsed to a single
825 space.
826
827 \item
828 String lengths are tested against the
829 limit in standard \BibTeX{}, and warnings
830 issued when the limit is exceeded. The
831 standard limit has proven to be too small
832 in practice, and many sites install
833 enlarged versions of \BibTeX{}. Perhaps
834 \BibTeX{} version 1.0 will use more
835 realistic values, or eliminate string
836 length limits altogether.
837
838 \item
839 Outer parentheses in entries are
840 standardized to braces.
841
842 \item
843 Braced value strings are standardized to
844 quoted value strings.
845
846 \item
847 Field\slash value pairs are output on
848 separate lines, wrapping long lines to not
849 exceed a user-definable standard width
850 whenever possible.
851
852 \item
853 A trailing comma is supplied after the
854 last field\slash value assignment. This
855 is convenient if assignments are later
856 reordered during editing.
857
858 \item
859 \OPTION{fix-font-changes} provides for
860 protecting value string text inside font
861 changes from downcasing.
862
863 \item
864 Brace-level zero upper-case acronyms in
865 titles are braced to protect from
866 downcasing.
867
868 \item
869 \OPTION{no-par-breaks} provides a way to
870 check for blank lines in string values,
871 which may be indicative of unclosed
872 delimiter errors.
873
874 \item
875 Umlaut accents, \verb=\"x=, inside value
876 strings at brace-level zero are converted
877 to \verb={\"x}=. This has been found to
878 be a common user error. \BibTeX{} requires
879 embedded quotes to be nested inside
880 braces.
881
882 \item
883 Letter-case usage in entry and field names
884 is standardized, so for example,
885 \verb=mastersthesis= and
886 \verb=MASTERSTHESIS= become
887 \verb=MastersThesis=.
888
889 \item
890 ISBN%
891 \index{ISBN (International Standard Book Number)}%
892 and ISSN
893 \index{ISSN (International Standard Serial Number)}%
894 checksums are validated. \BibTeX{} style
895 files that recognize field names for them
896 are available in the TUG bibliography
897 collection,%
898 \index{TUG bibliography collection}
899 and the bibliography for this document
900 uses them.
901
902 \item
903 Name modifiers like Jr, Sr, etc.\ are
904 recognized and handled by
905 \OPTION{fix-names}, and names are put into
906 a standard order, so that {\tt Bach,
907 P.~D.~Q.} becomes {\tt P.~D.~Q.~Bach}.%
908 \index{Bach, P. D. Q.}%
909 \index{Schickele, Peter}
910
911 \item
912 With \OPTION{fix-initials}, uniform
913 spacing is supplied after brace-level zero
914 initials in personal names.
915
916 \item
917 With \OPTION{check-values}, citation key
918 and field values are matched against
919 patterns to catch irregularities and
920 possible errors.
921
922 \item
923 Dates of the month, like {\tt "July 14"},
924 are converted to use month abbreviations,
925 {\tt jul \# "~14"}.
926
927 \item
928 Page number ranges are converted to use
929 en-dashes, instead of hyphens or
930 em-dashes.
931
932 \item
933 With \OPTION{check-values}, year numbers
934 are checked against patterns, then if no
935 match is found, the year values are
936 checked against reasonable limits.
937
938 \item
939 With \OPTION{trace-file-opening}, file
940 open attempts are logged. This helps in
941 the diagnosis of problems such as missing
942 files, or incorrect file permissions.
943
944 \item
945 On lexing or parsing errors, \BIBCLEAN{}
946 attempts to resynchronize by flushing the
947 input until it finds the next line
948 containing an initial \TT{@} character
949 preceded by nothing other than optional
950 white space.
951
952 \item
953 When an \TT{@} character begins a line, a
954 new bibliography entry is assumed to have
955 started. The current brace balance is
956 then tested to make sure it is zero. A
957 non-zero brace level is strongly
958 suggestive of an error, so \BIBCLEAN{}
959 issues an error message, and zeros the
960 brace level.
961
962 \item
963 At end-of-file, the brace level is tested.
964 A non-zero brace level is very likely an
965 error, and occasions an error message.
966
967 \end{itemize}
968
969
970 \section{Pattern matching and initialization files}%
971 \label{sec:init}
972
973 \BIBCLEAN{} can be compiled with one of three
974 different types of pattern matching;%
975 \index{pattern matching}
976 the choice is
977 made by the installer at compile time:
978
979 \begin{itemize}
980 \item
981 The original version uses explicit
982 hand-coded tests of value-string syntax.
983
984 \item
985 The second version uses regular-expression
986 pattern-matching%
987 \index{regular expression!pattern matching}%
988 \index{pattern matching!regular expression}
989 host library routines
990 together with regular-expression patterns
991 that come entirely from initialization
992 files.
993
994 \item
995 The third version uses special patterns
996 that come entirely from initialization
997 files.
998 \end{itemize}
999
1000 The second and third versions are the ones of most
1001 interest here, because they allow the user to
1002 control what values are considered acceptable.
1003 However, command-line options can also be
1004 specified in initialization files,%
1005 \index{initialization file}%
1006 \index{file!initialization}
1007 no matter which pattern-matching choice was
1008 selected.
1009
1010 When \BIBCLEAN{} starts, it searches for
1011 initialization files,%
1012 \index{initialization file}%
1013 \index{file!initialization}
1014 finding the first one in the
1015 system executable program search path%
1016 \index{program!search path}%
1017 \index{search path}
1018 (on \UNIX{}
1019 and IBM \PCDOS{}, \path=PATH=)%
1020 \PATHINDEX{PATH}
1021 and the first one
1022 in the \path=BIBINPUTS=%
1023 \PATHINDEX{BIBINPUTS}
1024 search path, and processes
1025 them in turn. Then, when command-line arguments%
1026 \index{options}
1027 are processed, any additional files specified by
1028 \OPTION{init-file filename} options are also
1029 processed. Finally, immediately before each named
1030 bibliography file is processed, an attempt is made
1031 to process an initialization file with the same
1032 name, but with the extension changed to
1033 \verb=.ini=.%
1034 \PATHINDEX{.ini}
1035 The default extension can be changed by a setting
1036 of the environment variable \path=BIBCLEANEXT=.%
1037 \PATHINDEX{BIBCLEANEXT}
1038 This scheme permits system-wide,
1039 user-wide, session-wide, and file-specific
1040 initialization files to be supported.
1041
1042 When input is taken from \path=stdin=,%
1043 \PATHINDEX{stdin}
1044 there is no file-specific initialization.
1045
1046 For precise control, the \OPTION{no-init-files}
1047 option suppresses all initialization files except
1048 those explicitly named by
1049 \OPTION{init-file filename} options, either on the
1050 command line, or in requested initialization
1051 files.
1052
1053 Recursive execution of initialization files%
1054 \index{initialization file!nested}%
1055 \index{file!initialization!nested}
1056 with nested \OPTION{init-file filename} options is
1057 permitted; if the recursion is circular,
1058 \BIBCLEAN{} will finally get a non-fatal
1059 initialization file open failure after opening too
1060 many files. This terminates further
1061 initialization file processing. As the recursion%
1062 \index{recursion}
1063 unwinds, the files are all
1064 closed, then execution proceeds normally.
1065
1066 An initialization file may contain empty lines,
1067 comments from percent to end of line (just like
1068 \TeX{}), option switches, and field\slash pattern
1069 or field\slash pattern\slash message assignments.
1070 Leading and trailing spaces are ignored. This is
1071 best illustrated by the short example in
1072 Table~\ref{tab:initfile}.
1073 %
1074 \begin{table}[tbh]
1075 \hrule
1076 \caption{Sample \protect\BIBCLEAN{} initialization file.}%
1077 \label{tab:initfile}%
1078 \index{initialization file!sample}%
1079 \index{file!sample initialization}
1080 \begin{verbatim}
1081 %% Start with our departmental patterns
1082 -init-file /u/math/bib/.bibcleanrc
1083
1084 %% Make some small additions
1085 chapter = "\"D\"" %% 23
1086
1087 pages = "\"D--D\"" %% 23--27
1088
1089 volume = "\"D \\an\\d D\"" %% 11 and 12
1090
1091 year = \
1092 "\"dddd, dddd, dddd\"" \
1093 "Multiple years specified."
1094 %% 1989, 1990, 1991
1095
1096 -no-fix-names %% do not modify
1097 %% author/editor lists
1098 \end{verbatim}
1099 \hrule
1100 \end{table}
1101 %
1102 Long logical lines can be split into multiple
1103 physical lines by breaking at a backslash-newline%
1104 \index{backslash-newline}
1105 pair; the backslash-newline pair is discarded.
1106 This processing happens while characters are being
1107 read, before any further interpretation of the
1108 input stream.
1109
1110 Each logical line must contain a complete option
1111 (and its value, if any), or a complete field\slash
1112 pattern pair, or a field\slash pattern\slash
1113 message triple.
1114
1115 Comments are stripped during the parsing of the
1116 field, pattern, and message values. The comment
1117 start symbol is not recognized inside quoted
1118 strings, so it can be freely used in such strings.
1119
1120 Comments on logical lines that were input as
1121 multiple physical lines via the backslash-newline%
1122 \index{backslash-newline}
1123 convention must appear on the last physical line;
1124 otherwise, the remaining physical lines will
1125 become part of the comment.
1126
1127 Pattern strings must be enclosed in quotation
1128 marks; within such strings, a backslash starts an
1129 escape mechanism that is commonly used in \UNIX{}
1130 software. The recognized escape sequences%
1131 \index{escape sequence}
1132 are
1133 given in Table~\ref{tab:escape}.
1134 Backslash followed by any other character produces
1135 just that character. Thus, \ESCAPE{\char34}
1136 produces a quotation mark, and \ESCAPE{\char92}
1137 produces a single backslash.
1138
1139 \begin{table}[tbh]
1140 \hrule
1141 \caption{Escape sequences in quoted strings.}%
1142 \index{escape sequence!table}%
1143 \label{tab:escape}
1144 \begin{center}
1145 \begin{tabular}{lp{2in}}
1146 \ESCAPE{a} & alarm bell (octal 007)\\
1147 %
1148 \ESCAPE{b} & backspace (octal 010)\\
1149 %
1150 \ESCAPE{f} & formfeed (octal 014)\\
1151 %
1152 \ESCAPE{n} & newline (octal 012)\\
1153 %
1154 \ESCAPE{r} & carriage return (octal 015)\\
1155 %
1156 \ESCAPE{t} & horizontal tab (octal 011)\\
1157 %
1158 \ESCAPE{v} & vertical tab (octal 013)\\
1159 %
1160 \ESCAPE{ooo} & character number octal
1161 \verb=ooo= (e.g.\ \ESCAPE{012} is
1162 linefeed). Up to 3 octal
1163 digits may be used.\\
1164 %
1165 \ESCAPE{0xhh}
1166 & character number hexadecimal
1167 \verb=hh= (e.g.\ \ESCAPE{0x0a}
1168 is linefeed). \verb=xhh= may
1169 be in either letter case.
1170 Any number of hexadecimal
1171 digits may be used.
1172 \end{tabular}
1173 \end{center}
1174 \hrule
1175 \end{table}
1176
1177 An ASCII NUL%
1178 \index{NUL (0)!in string}
1179 (\ESCAPE{0}) in a string will
1180 terminate it; this is a feature of the C
1181 programming language in which \BIBCLEAN{} is
1182 implemented.
1183
1184 Field\slash pattern pairs can be separated by
1185 arbitrary space, and optionally, either an equals
1186 sign or colon functioning as an assignment
1187 operator. Thus, the following are equivalent:
1188 %
1189 \begin{verbatim}
1190 pages="\"D--D\""
1191 pages:"\"D--D\""
1192 pages "\"D--D\""
1193 pages = "\"D--D\""
1194 pages : "\"D--D\""
1195 pages "\"D--D\""
1196 \end{verbatim}
1197 %
1198 Each field name can have an arbitrary number of
1199 patterns associated with it; however, they must be
1200 specified in separate field\slash pattern
1201 assignments.
1202
1203 An empty pattern string causes previously-loaded
1204 patterns for that field name to be forgotten.
1205 This feature permits an initialization file to
1206 completely discard patterns from earlier
1207 initialization files.
1208
1209 Patterns for value strings are represented in a
1210 tiny special-purpose language that is both
1211 convenient and suitable for bibliography
1212 value-string syntax checking. While not as
1213 powerful as the language of regular-expression
1214 patterns, its parsing can be portably implemented
1215 in less than 3\% of the code in a widely-used
1216 regular-expression parser (the GNU%
1217 \index{GNU!regexp package@{\tt regexp} package}
1218 \path=regexp=%
1219 \PATHINDEX{regexp}
1220 package).
1221
1222 The patterns are represented by the special
1223 characters given in Table~\ref{tab:patterns}.
1224
1225 \begin{table}[tbh]
1226 \hrule
1227 \caption{Initialization file pattern characters.}%
1228 \index{initialization file!pattern characters}%
1229 \index{file!initialization!pattern characters}%
1230 \label{tab:patterns}
1231 \begin{center}
1232 \begin{tabular}{lp{2in}}
1233 \verb*= = & one or more spaces\\
1234 %
1235 \TT{a} & exactly one letter\\
1236 %
1237 \TT{A} & one or more letters\\
1238 %
1239 \TT{d} & exactly one digit\\
1240 %
1241 \TT{D} & one or more digits\\
1242 %
1243 \TT{r} & exactly one Roman numeral\\
1244 %
1245 \TT{R} & one or more Roman
1246 numerals (i.e. a Roman
1247 number)\\
1248 %
1249 \TT{w} & exactly one word (one or
1250 more letters and digits)\\
1251 %
1252 \TT{W} & one or more words, separated
1253 by space, beginning and ending
1254 with a word\\
1255 %
1256 \TT{.} & one `special' character,
1257 one of the characters
1258 \verb*= !#()*+,-./:;?[]~=,
1259 a subset of punctuation
1260 characters that are
1261 typically used in string
1262 values\\
1263 %
1264 \TT{:} & one or more `special'
1265 characters\\
1266 %
1267 \TT{X} & one or more
1268 `special'-separated words,
1269 beginning and ending with a
1270 word\\
1271 %
1272 \ESCAPE{x} & exactly one \TT{x}
1273 (\TT{x} is any
1274 character), possibly with
1275 an escape sequence
1276 interpretation given
1277 earlier\\
1278 %
1279 \TT{x} & exactly the character
1280 \TT{x} (\TT{x} is
1281 anything but one of these
1282 pattern characters:
1283 \verb*=aAdDrRwW.: \=)
1284 \end{tabular}
1285 \end{center}
1286 \hrule
1287 \end{table}
1288
1289 The \TT{X} pattern character is very powerful,
1290 but generally inadvisable, since it will match
1291 almost anything likely to be found in a \BibTeX{}
1292 value string. The reason for providing pattern
1293 matching on the value strings is to uncover
1294 possible errors, not mask them.
1295
1296 There is no provision for specifying ranges or
1297 repetitions of characters, but this can usually be
1298 done with separate patterns. It is a good idea to
1299 accompany the pattern with a comment showing the
1300 kind of thing it is expected to match. Here is a
1301 portion of an initialization file giving a few of
1302 the patterns used to match \TT{number} value
1303 strings:
1304 %
1305 \begin{verbatim}
1306 number = "\"D\"" %% 23
1307 number = "\"A AD\"" %% PN LPS5001
1308 number = "\"A D(D)\"" %% RJ 34(49)
1309 number = "\"A D\"" %% XNSS 288811
1310 number = "\"A D\\.D\"" %% Version 3.20
1311 number = "\"A-A-D-D\"" %% UMIAC-TR-89-11
1312 number = "\"A-A-D\"" %% CS-TR-2189
1313 number = "\"A-A-D\\.D\"" %% CS-TR-21.7
1314 \end{verbatim}
1315 %
1316 For a bibliography that contains only
1317 \verb=Article= entries, this list should probably
1318 be reduced to just the first pattern, so that
1319 anything other than a digit string fails the
1320 pattern-match test. This is easily done by
1321 keeping bibliography-specific patterns%
1322 \index{bibliography-specific pattern}%
1323 \index{pattern!bibliography-specific}
1324 in a
1325 corresponding file with extension \verb=.ini=,%
1326 \PATHINDEX{.ini}
1327 since that file is read automatically.
1328 You should be sure to use empty pattern%
1329 \index{empty!pattern}%
1330 \index{pattern!empty}
1331 strings in
1332 this pattern file to discard patterns from earlier
1333 initialization files.
1334
1335 The value strings passed to the pattern matcher
1336 contain surrounding quotes, so the patterns should
1337 also.%
1338 \index{quote!in pattern}%
1339 \index{pattern!quotes in}
1340 However, you could use a pattern
1341 specification like \verb="\"D"= to match an
1342 initial digit string followed by anything else;
1343 the omission of the final quotation mark
1344 \ESCAPE{\char34} in the pattern allows the match
1345 to succeed without checking that the next
1346 character in the value string is a quotation mark.
1347
1348 Because the value strings are intended to be
1349 processed by \TeX, the pattern matching ignores
1350 braces,%
1351 \index{pattern matching!brace ignored in}%
1352 \index{brace!ignored in pattern matching}
1353 and \TeX{} control sequences, together
1354 with any space following those control sequences.
1355 Spaces around braces are preserved.%
1356 \index{brace!space around}
1357 This
1358 convention allows the pattern fragment
1359 \verb=A-AD-D= to match the value string
1360 \path=TN-K\slash 27-70=, because the value is
1361 implicitly collapsed to \path=TN-K27-70= during
1362 the matching operation.
1363
1364 \BIBCLEAN{}'s normal action when a string value
1365 fails to match any of the corresponding patterns
1366 is to issue a warning message similar to this:
1367 {\tt Unexpected value in ``year = "192"''}. In
1368 most cases, that is sufficient to alert the user
1369 to a problem. In some cases, however, it may be
1370 desirable to associate a different message with a
1371 particular pattern.%
1372 \index{pattern!changing warning message}%
1373 \index{warning message!changing}
1374 This can be done by supplying
1375 a message string following the pattern string.
1376 Format items%
1377 \index{format!item}
1378 \FORMAT{\%} (single percent), \FORMAT{e}
1379 (entry name), \FORMAT{f} (field name), \FORMAT{k}
1380 (citation key), and \FORMAT{v} (string value) are
1381 available to get current values expanded in the
1382 messages. Here is an example:
1383 %
1384 \begin{verbatim}
1385 chapter = "\"D:D\"" \
1386 "Colon found in ``%f = %v''" %% 23:2
1387 \end{verbatim}
1388 %
1389
1390 To be consistent with other messages output by
1391 \BIBCLEAN{}, the message string should not end
1392 with punctuation.
1393
1394 If you wish to make the message an error, rather
1395 than just a warning, begin it with a query%
1396 \index{query (?)!in messages}
1397 (?),%
1398 \index{?}
1399 like this:
1400 %
1401 \begin{verbatim}
1402 chapter = "\"D:D\"" \
1403 "?Colon found in ``%f = %v''" %% 23:2
1404 \end{verbatim}
1405 %
1406 The query will {\em not\/} be included in the
1407 output message.
1408
1409 Escape sequences%
1410 \index{escape sequence!in message text}
1411 are supported in message strings,
1412 just as they are in pattern strings. You can use
1413 this to advantage for fancy things, such as
1414 terminal display mode control. If you rewrite the
1415 previous example as
1416 %
1417 \begin{verbatim}
1418 chapter = "\"D:D\"" \
1419 "?\033[7mColon found \
1420 in ``%f = %v''\033[0m" %% 23:2
1421 \end{verbatim}
1422 %
1423 the error message will appear in inverse video on
1424 display screens that support ANSI terminal control
1425 sequences. Such practice is not normally
1426 recommended, since it may have undesirable effects
1427 on some output devices. Nevertheless, you may
1428 find it useful for restricted applications.
1429
1430 For some types of bibliography fields, \BIBCLEAN{}
1431 contains special-purpose code to supplement or
1432 replace the pattern matching:
1433 \begin{itemize}
1434 \item
1435 \TT{ISBN} and \TT{ISSN} field values
1436 are handled this way because their
1437 validation requires evaluation of
1438 checksums%
1439 \index{checksum!in ISBN and ISSN@in {\tt ISBN} and {\tt ISSN}}
1440 that cannot be expressed by
1441 simple patterns; no patterns are even used
1442 in these two cases.
1443
1444 \item
1445 When \BIBCLEAN{} is compiled with
1446 pattern-matching code support,
1447 \TT{chapter}, \TT{number},
1448 \TT{pages}, and \TT{volume} values are
1449 checked only by pattern matching.
1450
1451 \item
1452 \TT{month} values are first checked
1453 against the standard \BibTeX{}
1454 month name abbreviations, and only if no
1455 match is found are patterns then used.
1456
1457 \item
1458 \TT{year} values are first checked
1459 against patterns, then if no match is
1460 found, the year numbers are found and
1461 converted to integer values for testing
1462 against reasonable bounds.
1463 \end{itemize}
1464
1465 Values for other fields are checked only against
1466 patterns. You can provide patterns for any field
1467 you like, even ones \BIBCLEAN{} does not already
1468 know about. New ones are simply added to an
1469 internal table that is searched for each string to
1470 be validated.
1471
1472 The special field, \TT{key}, represents the
1473 bibliographic citation key.%
1474 \index{citation!key}
1475 It can be given
1476 patterns, like any other field. Here is an
1477 initialization file pattern assignment that will
1478 match an author name, a colon, an alphabetic
1479 string, and a two-digit year:
1480 %
1481 \begin{verbatim}
1482 key = "A:Add" %% Knuth:TB86
1483 \end{verbatim}
1484 %
1485 Notice that no quotation marks are included in the
1486 pattern, because the citation keys are not quoted.
1487 You can use such patterns to help enforce uniform
1488 naming conventions for citation keys, which is
1489 increasingly important as your bibliography data
1490 base grows.
1491
1492 \section{Lexical analysis}\label{sec:lexer}
1493
1494 The command-line option \OPTION{no-prettyprint}
1495 requests \BIBCLEAN{} to function as a lexical
1496 analyzer%
1497 \index{lexical analyzer}
1498 instead of as a prettyprinter.%
1499 \index{prettyprinter}
1500 Its output is then a stream of lines, each of
1501 which contains one token. For the bibliography
1502 entries shown in Section~\ref{sec:intro}, here is
1503 what the output looks like; the long lines have
1504 been wrapped by a backslash-newline%
1505 \index{backslash-newline}
1506 to fit in these narrow journal columns:
1507 %
1508 \begin{verbatim}
1509 # line 1 "stdin"
1510 2 AT "@"
1511 18 STRING "String"
1512 11 LBRACE "{"
1513 1 ABBREV "pub-AW"
1514 6 EQUALS "="
1515 # line 2 "stdin"
1516 19 VALUE "\"Ad{\\-d}i{\\-s}on-Wes{\
1517 \\-l}ey\""
1518 15 RBRACE "}"
1519 # line 4 "stdin"
1520 13 NEWLINE "\n"
1521 13 NEWLINE "\n"
1522 2 AT "@"
1523 5 ENTRY "Book"
1524 11 LBRACE "{"
1525 10 KEY "Lamport:LDP85"
1526 3 COMMA ","
1527 13 NEWLINE "\n"
1528 # line 5 "stdin"
1529 7 FIELD "author"
1530 6 EQUALS "="
1531 19 VALUE "\"Leslie Lamport\""
1532 3 COMMA ","
1533 13 NEWLINE "\n"
1534 # line 6 "stdin"
1535 7 FIELD "title"
1536 6 EQUALS "="
1537 # line 8 "stdin"
1538 19 VALUE "\"{\\LaTeX}---{A} Docume\
1539 nt Preparation System---User's Guide and \
1540 Reference Manual\""
1541 3 COMMA ","
1542 13 NEWLINE "\n"
1543 # line 9 "stdin"
1544 7 FIELD "publisher"
1545 6 EQUALS "="
1546 1 ABBREV "pub-AW"
1547 3 COMMA ","
1548 13 NEWLINE "\n"
1549 # line 10 "stdin"
1550 7 FIELD "year"
1551 6 EQUALS "="
1552 19 VALUE "\"1985\""
1553 3 COMMA ","
1554 13 NEWLINE "\n"
1555 # line 11 "stdin"
1556 7 FIELD "ISBN"
1557 6 EQUALS "="
1558 19 VALUE "\"0-201-15790-X\""
1559 3 COMMA ","
1560 13 NEWLINE "\n"
1561 # line 12 "stdin"
1562 15 RBRACE "}"
1563 # line 13 "stdin"
1564 13 NEWLINE "\n"
1565 \end{verbatim}
1566 \TOKENINDEX{TOKEN_ABBREV}%
1567 \TOKENINDEX{TOKEN_AT}%
1568 \TOKENINDEX{TOKEN_COMMA}%
1569 \TOKENINDEX{TOKEN_ENTRY}%
1570 \TOKENINDEX{TOKEN_EQUALS}%
1571 \TOKENINDEX{TOKEN_FIELD}%
1572 \TOKENINDEX{TOKEN_KEY}%
1573 \TOKENINDEX{TOKEN_LBRACE}%
1574 \TOKENINDEX{TOKEN_NEWLINE}%
1575 \TOKENINDEX{TOKEN_RBRACE}%
1576 \TOKENINDEX{TOKEN_STRING}%
1577 \TOKENINDEX{TOKEN_VALUE}%
1578 \index{Lamport, Leslie}%
1579 %
1580 Each line begins with a small integer token type%
1581 \index{token!type}
1582 number for the convenience of computer programs,
1583 then a token type name for human readers, followed
1584 by a quoted token string.%
1585 \index{token!string}
1586
1587 Lines beginning with a sharp,%
1588 \index{sharp@sharp ({\tt\char35})}
1589 \verb=#=, are
1590 ANSI\slash ISO Standard C preprocessor%
1591 \index{preprocessor}
1592 line-number directives%
1593 \index{line!number directive}
1594 \cite[Section~3.8.4]{ANSI:c89}%
1595 \index{ANSI/ISO Standard C@ANSI\slash ISO Standard C}
1596 to record the input line number and file name.
1597
1598 There are currently 19 token types%
1599 \index{token!type}
1600 defined
1601 in the documentation that accompanies \BIBCLEAN{}.
1602 Because \BibTeX{} styles can define new field
1603 names, there is little point in the lexical
1604 analyzer of attempting to classify field names
1605 more precisely; that job is left for other
1606 software.
1607
1608 Inside quoted strings, the ANSI\slash ISO Standard
1609 C
1610 \cite[Section~3.1.3.4]{ANSI:c89}%
1611 \index{ANSI/ISO Standard C@ANSI\slash ISO Standard C}
1612 backslash escape sequences%
1613 \index{escape sequence}
1614 shown in
1615 Table~\ref{tab:escape} on
1616 page~\pageref{tab:escape} are used to encode
1617 non-printable characters. In this way, a
1618 multi-line string value can be represented on a
1619 single line. This is convenient for
1620 string-searching applications. If the long output
1621 lines prove a problem on some systems, the
1622 \OPTION{max-width nnn} command-line option can be
1623 used to wrap lines%
1624 \index{wrapping!of long lines}%
1625 \index{line!wrapping}
1626 at a specified column number by the
1627 insertion of a backslash-newline%
1628 \index{backslash-newline}
1629 pair.
1630
1631 As a simple example of how this token stream might
1632 be processed, the \UNIX{} command pipeline%
1633 \index{pipeline}
1634 %
1635 \begin{verbatim}
1636 bibclean -no-prettyprint mylib.bib | \
1637 awk '$2 == "KEY" {print $3}' | \
1638 sed -e 's/"//g' | \
1639 sort
1640 \end{verbatim}
1641 will extract a sorted list of all citation keys in
1642 the file \path=mylib.bib=.
1643
1644 As a more complex example, consider locating
1645 duplicate abbreviations and citation keys in a
1646 large collection of bibliography files. This is a
1647 daunting task if it must be done by visual
1648 scanning of the files. It took me less than 10
1649 minutes to write and debug a 35-line
1650 \PROGRAM{nawk}
1651 \cite{Aho:APL87}%
1652 \index{Aho, Alfred V.}%
1653 \index{Kernighan, Brian W.}%
1654 \index{Weinberger, Peter J.}
1655 program (15 lines of comments, 20 of code) that
1656 processed the token stream from \BIBCLEAN{} and
1657 printed warnings about such duplicates.
1658
1659 The processing steps can be represented by the
1660 simple \UNIX{} pipeline
1661 %
1662 \begin{verbatim}
1663 bibclean -no-prettyprint bibfiles | \
1664 tr '[A-Z]' '[a-z]' | \
1665 nawk -f bibdup.awk
1666 \end{verbatim}
1667 \PATHINDEX{tr}%
1668 \PATHINDEX{bibclean}%
1669 \PATHINDEX{bibdup.awk}%
1670 \PATHINDEX{nawk}%
1671 \PATHINDEX{tr}%
1672 %
1673 \noindent
1674 which is most conveniently encapsulated in a
1675 command script so that it can be invoked more
1676 simply as
1677 %
1678 \begin{verbatim}
1679 bibdup *.bib
1680 \end{verbatim}
1681 %
1682 \PATHINDEX{bibdup}%
1683 \noindent
1684 to produce output like this:
1685 %
1686 \begin{verbatim}
1687 Duplicate string abbreviation ["pub-aw"]:
1688 # line 1 "ll.bib"
1689 # line 141 "master.bib"
1690 Duplicate key ["lamport:ldp85"]:
1691 # line 4 "ll.bib"
1692 # line 4172 "master.bib"
1693 ...
1694 \end{verbatim}
1695
1696 \BibTeX{}'s grammar is somewhat hazy, so it is not
1697 easy to perform a lexical analysis without some
1698 context sensitivity. \BIBCLEAN{} therefore
1699 produces the lexical token stream merely as an
1700 alternate output format. In particular, this
1701 means that any requested run-time formatting
1702 options will have been applied to the tokens {\em
1703 before\/} they are output to the lexical token
1704 stream. For example, a \SCRIBE{} bibliography
1705 file can be converted to a \BibTeX{} token stream
1706 so that software that processes \BIBCLEAN{}'s
1707 output need not be \SCRIBE{}-aware.
1708
1709 \section{Portability}
1710
1711 \index{portability}%
1712 \index{testing}%
1713 \BIBCLEAN{} is written in ANSI\slash ISO Standard
1714 C
1715 \cite{ANSI:c89}%
1716 \index{ANSI/ISO Standard C@ANSI\slash ISO Standard C}
1717 with great care taken to produce
1718 maximum portability. It has been successfully
1719 tested with more than 30 different compilers on
1720 all major workstation, and one mainframe, \UNIX{}
1721 systems, plus \VAX{} \VMS{}, \PCDOS{}, \OSTWO{},
1722 and Atari%
1723 \index{Atari}
1724 \TOS{}.
1725
1726 The C programming language has become the language
1727 of choice today for most personal computer and
1728 \UNIX{} software development, and the increasing
1729 availability of C implementations conforming to
1730 the 1989 Standard
1731 \cite{ANSI:c89}%
1732 \index{ANSI/ISO Standard C@ANSI\slash ISO Standard C}
1733 makes it easier to write code that will compile
1734 and run without modification on a wide variety of
1735 systems.
1736
1737 C does not have Pascal's%
1738 \index{Pascal}
1739 problems with character
1740 strings and dynamic memory allocation that forced
1741 Don Knuth%
1742 \index{Knuth, Donald E.}
1743 to implement the \WEB{} string pool%
1744 \index{string!pool}
1745 feature and to use compile-time array allocation
1746 in the \TeX{} software development. C's rich
1747 operator syntax, its powerful run-time library,
1748 and generally excellent operating-system
1749 interfaces have made it widely popular. More than
1750 a million copies of the first edition of {\em The
1751 C Programming Language\/} book
1752 \cite{Kernighan:CPL78}%
1753 \index{Kernighan, Brian W.}%
1754 \index{Ritchie, Dennis M.}
1755 have been sold, and the
1756 second edition
1757 \cite{Kernighan:CPL88}
1758 may do even better.
1759
1760 Nevertheless, C has some serious problems.
1761 Philippe Kahn,%
1762 \index{Kahn, Philippe}
1763 the founder of Borland
1764 International,%
1765 \index{Borland International}
1766 has called C a {\em write-only\/}
1767 language. Two books have been written about its
1768 syntactical peculiarities
1769 \cite{Feuer:CPB89,%
1770 Koenig:CTP89},%
1771 \index{Feuer, Alan~R.}%
1772 \index{Koenig, Andrew}
1773 and one of them has already appeared in a second
1774 edition.
1775
1776 The only way to overcome these problems is
1777 meticulous care in programming, and experience
1778 with as many compilers and computer architectures
1779 as possible. Several books offer valuable advice
1780 on C portability
1781 \cite{Harbison:CAR91,%
1782 Jaeschke:PCL89,%
1783 Lapin:PCU87,%
1784 Plauger:SCL92,%
1785 Rabinowitz:PC90,%
1786 Rochkind:AUP85,%
1787 Stevens:UNP90}.
1788 \index{Harbison, Samuel P.}%
1789 \index{Steele Jr., Guy L.}%
1790 \index{Jaeschke, Rex}%
1791 \index{Lapin, J. E.}%
1792 \index{Plauger, P. J.}%
1793 \index{Rabinowitz, Henry}%
1794 \index{Schaap, Chaim}%
1795 \index{Rochkind, Marc J.}%
1796 \index{Stevens, W. Richard}
1797
1798 C++%
1799 \index{C++}
1800 \cite{Ellis:ACR90,%
1801 Stroustrup:CPL91}%
1802 \index{Ellis, Margaret A.}%
1803 \index{Stroustrup, Bjarne}
1804 is an extension of C to support object-oriented
1805 programming,%
1806 \index{object-oriented programming}
1807 and has an enthusiastic following.
1808 ANSI\slash ISO standardization efforts are in
1809 progress, sadly while the language is still
1810 evolving.
1811
1812 From the point of view of a C programmer, the
1813 advantage of C++ over C is its much stricter
1814 checking of type conversions and intermodule
1815 interfaces. \BIBCLEAN{} has been carefully
1816 written to be compilable under C++ as well as C,
1817 and to date, has been tested with more than a
1818 dozen C++ and Objective C%
1819 \index{Objective C}
1820 (another C superset) compilers.
1821 % DEC Alpha AXP OSF/1
1822 % g++ (DECstation ULTRIX, NeXT, SGI, Sun)
1823 % HP BSD 4.3
1824 % HP UX
1825 % IBM 3090
1826 % IBM PS/2
1827 % IBM RS/6000
1828 % SGI
1829 % Sun
1830 % Turbo C++
1831
1832 All of the extra features of the C++ language are
1833 strictly avoided, because using them would
1834 seriously limit \BIBCLEAN{}'s portability. Not
1835 only is the syntax of the C++ language under
1836 evolution, but the C++ class libraries%
1837 \index{class library}
1838 are for the
1839 most part {\em completely dependent\/} on the
1840 particular implementation. Microsoft's 1020-page
1841 documentation of its C++ class library is 10\%
1842 larger than that of its C run-time library.
1843
1844 Nevertheless, I {\em strongly recommend\/} use of
1845 C++ compilers in preference to C compilers, so as
1846 to catch bugs at compile time that would otherwise
1847 not be found until post-mortem dump%
1848 \index{dump!post-mortem}%
1849 \index{post-mortem dump}%
1850 \index{core dump}
1851 time, or when
1852 the code is ported to a new architecture.
1853
1854 \section{\protect\SCRIBE{} bibliography format}%
1855 \label{sec:scribe}
1856
1857 The \SCRIBE{} document formatting system
1858 \cite{Reid:SUM80}%
1859 \index{Reid, Brian}
1860 greatly influenced \LaTeX{} and
1861 \BibTeX{}, as well as the GNU Emacs%
1862 \index{GNU!Emacs}%
1863 \index{Emacs}
1864 \TeX{}info system.%
1865 \index{GNU!texinfo@\protect\TeX{}info}%
1866 \index{texinfo@\protect\TeX{}info}
1867
1868 With care, it is possible to share bibliography
1869 files between \SCRIBE{} and \BibTeX{}.
1870 Nevertheless, there are some differences, so here
1871 is a summary of features of the \SCRIBE{}
1872 bibliography file format. We record them because
1873 they are difficult to determine from the published
1874 manual, and because readers may sometimes acquire
1875 files in this format without having prior exposure
1876 to \SCRIBE{}.
1877
1878 \begin{enumerate}
1879 \item
1880 Letter case is not significant in field
1881 names and entry names, but case is preserved
1882 in value strings.
1883
1884 \item
1885 In field\slash value pairs, the field and
1886 value may be separated by one of three
1887 characters: \verb|=|, \verb=/=, or
1888 \verb*= = (space). Space may optionally
1889 surround these separators.
1890
1891 \item
1892 Value delimiters%
1893 \index{delimiters!in scribe@in \protect\SCRIBE{}}
1894 are any of these seven
1895 pairs:
1896 \verb={ }=, \verb=[ ]=, \verb=( )=,
1897 \verb=< >=, \verb=' '=, \verb=" "=, and
1898 \verb=` `=.
1899
1900 \item\label{item:4}
1901 Value delimiters may not be nested, even
1902 though with the first four delimiter pairs,
1903 nested balanced delimiters would be
1904 unambiguous.
1905
1906 \item
1907 Delimiters can be omitted around values that
1908 contain only letters, digits, sharp
1909 (\verb=#=), ampersand (\verb=&=), period
1910 (\verb=.=), and percent (\verb=%=).
1911
1912 \item
1913 Outside of delimited values, a literal
1914 at-sign%
1915 \index{at-sign}
1916 (\TT{\char64}) is represented by doubled
1917 at-signs (\TT{\char64\char64}).
1918
1919 \item
1920 Bibliography entries begin with
1921 \TT{\char64name}, as for \BibTeX{}, but any
1922 of the seven \SCRIBE{} value delimiter pairs
1923 may be used to surround the values in
1924 field\slash value pairs. As in
1925 (\ref{item:4}), nested delimiters are
1926 forbidden.
1927
1928 \item
1929 Arbitrary space may separate entry names
1930 from the following delimiters.
1931
1932 \item
1933 \TT{\char64Comment} is a special command
1934 whose delimited value is discarded. As in
1935 (\ref{item:4}), nested delimiters are
1936 forbidden.
1937
1938 \item
1939 The special form
1940 %
1941 \begin{verbatim}
1942 @Begin{comment}
1943 ...
1944 @End{comment}
1945 \end{verbatim}
1946 %
1947 permits encapsulating arbitrary text
1948 containing any characters or delimiters,
1949 other than
1950 \TT{\char64End\optbreak\protect\{comment\protect\}}.
1951 Any of the seven delimiter pairs may be used
1952 around the word \TT{comment} following the
1953 \TT{\char64Begin} or \TT{\char64End}; the
1954 delimiters in the two cases need not be the
1955 same, and consequently,
1956 \TT{\char64Begin\optbreak\protect\{comment\protect\}}\slash
1957 \TT{\char64End\optbreak\protect\{comment\protect\}}
1958 pairs may not be nested.
1959
1960 \item
1961 The \TT{key} field is required in each
1962 bibliography entry.
1963
1964 \item
1965 A backslashed quote%
1966 \index{backslash-quote}%
1967 \index{escape sequence}
1968 in a string will be
1969 assumed to be a \TeX{} accent, and braced
1970 appropriately. While such accents do not
1971 conform to \SCRIBE{} syntax,
1972 \SCRIBE{}-format bibliographies have been
1973 found that appear to be intended for \TeX{}
1974 processing.
1975 \end{enumerate}
1976
1977 Because of this loose syntax, \BIBCLEAN{}'s normal
1978 error detection heuristics are less effective, and
1979 consequently, \SCRIBE{} mode input is not the
1980 default; it must be explicitly requested.
1981
1982 \section{Recommendations for \protect\BibTeX{} design}%
1983 \label{sec:recommendations}
1984
1985 The documentation available for \BibTeX{} leaves
1986 several points about the input syntax unclear, and
1987 I had to obtain answers to the following questions
1988 by experiment:
1989 \begin{itemize}
1990 \item Can an at-sign occur inside a
1991 \TT{\char64Comment\optbreak\protect\{...\protect\}}?
1992 {\em No}.
1993
1994 \item Can string abbreviation names be used on
1995 the right-hand side of string definitions?
1996 {\em Yes}.
1997
1998 \item Can the argument of \TT{\char64String} be
1999 empty? {\em No}.
2000
2001 \item Can a citation key be omitted in an entry?
2002 {\em No}.
2003
2004 \item Can the list of assignments in an entry be
2005 empty? {\em Yes}.
2006
2007 \item Can a
2008 \TT{\char64Comment\optbreak\protect\{...\protect\}}
2009 occur between arbitrary tokens? {\em No}.
2010
2011 \item Are newlines preserved in the argument of
2012 a \TT{\char64Preamble\optbreak\protect\{...\protect\}}?
2013 The answer is relevant if the user
2014 includes \TeX{} comments in the preamble material.
2015 {\em No}.
2016 \end{itemize}
2017 I view the experimental answers to these questions
2018 as pure happenstance, and could reasonably argue
2019 for the opposite answers to the ones obtained.
2020
2021 \subsection*{Grammar}
2022
2023 \index{grammar}%
2024 The most important recommendation that I can make
2025 for the next version of \BibTeX{} is that it {\em
2026 must\/} have a rigorous grammar, including a
2027 well-defined comment syntax.
2028
2029 The grammar can almost be of the simple class
2030 LL(0)%
2031 \index{LL(0) grammar}%
2032 \index{grammar!LL(0)}
2033 \cite{Aho:CPT86},%
2034 \index{Aho, Alfred V.}%
2035 \index{Sethi, Ravi}%
2036 \index{Ullman, Jeffrey D.}
2037 requiring no lookahead during parsing, and
2038 one-character lookahead during lexical analysis.
2039 However, the presence of the string concatenation
2040 operator complicates things sufficiently to
2041 require at least an LL(1) grammar.%
2042 \index{LL(1)!grammar}%
2043 \index{grammar!LL(1)}
2044
2045 Such grammars are straightforward to handle with
2046 either hand-coded parsers, or with parsers
2047 automatically generated from grammar files by
2048 compiler development tools like the \UNIX{}
2049 \PROGRAM{lex} \cite{Lesk:lex}%
2050 \index{Lesk, Michael E.}%
2051 \index{Schmidt, Eric}
2052 and \PROGRAM{yacc}
2053 \cite{Johnson:yacc,%
2054 Levine:LY92,%
2055 Mason:LY90,%
2056 Schreiner:ICC85}%
2057 \index{Johnson, Steven C.}%
2058 \index{Levine, John R.}%
2059 \index{Mason, Tony}%
2060 \index{Brown, Doug}%
2061 \index{Schreiner, Axel T.}%
2062 \index{Friedman, Jr., H. George}
2063 programs, or the Free Software Foundation%
2064 \index{Free Software Foundation}
2065 equivalents, \PROGRAM{flex} and \PROGRAM{bison}.%
2066
2067 \PROGRAM{yacc} and \PROGRAM{bison} implement
2068 LALR(1) parsers;%
2069 \index{LALR(1)!parser}%
2070 \index{parser!LALR(1)}
2071 the acronym stands for ``Look-Ahead at
2072 most 1 token with a Left-to-Right derivation''.
2073 These are simpler than the LR($k$) grammars%
2074 \index{LR($k$) grammar}%
2075 \index{grammar!LR($k$)}
2076 introduced by none other than the author of \TeX{}
2077 in the fundamental paper on the theory of parsing
2078 \cite{Knuth:j-IC-8-6-607}.%
2079 \index{Knuth, Donald E.}
2080 Nevertheless, they are sufficient for a broad
2081 class of language grammars, including most major
2082 programming languages, and importantly, they
2083 produce compact, efficient, fast, and reliable
2084 parsers. LL(1) grammars%
2085 \index{LL(1)!grammar}%
2086 \index{grammar!LL(1)}
2087 are a special case of
2088 LALR(1) grammars,%
2089 \index{LALR(1)!grammar}%
2090 \index{grammar!LALR(1)}
2091 and we will later define a
2092 \BibTeX{} grammar in LALR(1) form in
2093 Section~\ref{sec:yacc-grammar}.
2094
2095 \subsection*{Comment syntax}
2096
2097 The comment syntax%
2098 \index{comment!syntax}
2099 should preferably be identical
2100 to that of \TeX{}, so that a comment runs from
2101 percent to end-of-line, and then {\em additionally
2102 gobbles all leading horizontal space on the next
2103 line, up to, but not including, its end-of-line}.
2104 This permits breaking of long lines without having
2105 to destroy indentation that is so necessary for
2106 readability. Percent-initiated comments are
2107 already supported in \BibTeX{} style files, though
2108 such comments end after the first following
2109 newline.
2110
2111 For \SCRIBE{} compatibility, \BibTeX{} should also
2112 support a
2113 \TT{\char64Comment\optbreak\protect\{...\protect\}}
2114 entry type. This will require additions to {\em
2115 all\/} \BibTeX{} style files, since the entry
2116 types are known there, and not in the \BibTeX{}
2117 code itself. \BibTeX{} 0.99c already knows about
2118 \TT{\char64Comment\optbreak\protect\{...\protect\}},
2119 but the \WEB{} code section ``Process a
2120 \verb=comment= command'' will have to be extended
2121 to deal with the grammar changes.
2122
2123 It is important that \BibTeX{} not discard
2124 \TT{\char64Comment\optbreak\protect\{...\protect\}}
2125 entries, because it would then not be possible to
2126 write a \BibTeX{} style file that converted a
2127 bibliography file to another format without loss
2128 of information. One such style already exists to
2129 convert \BibTeX{} files to \UNIX{}
2130 \PROGRAM{bib}\slash \PROGRAM{refer} format.
2131
2132 \subsection*{Characters in names}
2133
2134 The characters that can appear in key, entry, and
2135 field names {\em must\/} be defined by
2136 enumeration, rather than by exclusion, as is
2137 currently done
2138 \cite[Section~B.1.3]{Lamport:LDP85}.%
2139 \index{Lamport, Leslie}
2140 The reason is that character sets vary between
2141 computers, and the new, and very much larger,
2142 ISO10646M character set%
2143 \index{ISO10646M character set}
2144 may be widely available in
2145 this decade. These variations make the set of
2146 admissible name characters vary between systems,
2147 compromising portability. I strongly recommend
2148 following the conventions for identifiers in
2149 widely-used programming languages to define the
2150 grammar of key, entry, and field names. It seems
2151 to me that letters, digits, colon, hyphen, and
2152 possibly plus and slash, should be adequate, and
2153 names should be required to begin with a letter.
2154 `Letter' here should include {\em only\/} the 26
2155 Roman letters `A' through `Z', because allowing
2156 letters from other alphabets opens a horrid can of
2157 worms that will seriously impact portability of
2158 bibliography files until the computer world has a
2159 single uniform character set.
2160
2161 I tested this set of characters against 92~500
2162 entries in local bibliography files, and found
2163 only a few keys that used other characters: the
2164 new ones were period%
2165 \index{period!in citation key}
2166 and apostrophe%
2167 \index{apostrophe!in citation key}
2168 (e.g.\
2169 O'Malley:TB92). They might therefore be permitted
2170 as well, though I would prefer to omit them, and
2171 retrofit changes in a few citation keys.
2172
2173 The characters permitted in citation keys should
2174 be the same as those in entry and field names, so
2175 as to avoid user confusion.
2176
2177 \subsection*{Error reporting}
2178
2179 \index{error!reporting}%
2180 When \BibTeX{} begins to collect a token, it
2181 should record the current line number.%
2182 \index{line!number}
2183 When
2184 an unclosed string%
2185 \index{runaway string argument}%
2186 \index{string!runaway}
2187 later causes internal buffer
2188 overflow,%
2189 \index{buffer overflow}%
2190 \index{overflow of string buffer}
2191 it could report something like {\tt
2192 String buffer overflow on input lines 24--82}
2193 that would better help locate the offending string
2194 by giving its starting and ending line numbers.
2195
2196 To simplify error recovery in such cases,
2197 \BibTeX{} could additionally require that the
2198 \TT{\char64} character that starts a new entry
2199 must be the first non-space character on a line.
2200
2201 \subsection*{File inclusion}
2202
2203 \BibTeX{} sorely needs a file inclusion%
2204 \index{file!inclusion}
2205 facility.
2206 With \BibTeX{} 0.99c, this feature is available in
2207 a crude fashion by listing several files in the
2208 \CS{bibliography} command. However, this is
2209 not sufficiently general, and requires unnecessary
2210 knowledge on the part of the user of the
2211 bibliography.
2212
2213 The author of a \BibTeX{} file should be free to
2214 restructure it into subfiles without requiring
2215 modifications to all documents that use it. File
2216 inclusion is important to allow sharing of common
2217 material, such as
2218 \TT{\char64String\optbreak\protect\{...\protect\}}
2219 definitions.
2220
2221 \SCRIBE{} uses the form
2222 %
2223 \begin{verbatim}
2224 @Include{filename}
2225 \end{verbatim}
2226 %
2227 and \BibTeX{} should too. It must be possible to
2228 nest file inclusions to a reasonable depth, at
2229 least five levels.
2230
2231 \section{A lexical grammar for \protect \BibTeX{}}%
2232 \label{sec:lex-grammar}
2233
2234 \index{grammar!lexical}%
2235 \index{lexical grammar}%
2236 To test the recommendations of
2237 Section~\ref{sec:recommendations}, I wrote and
2238 tested a \PROGRAM{lex} grammar for \BibTeX{}. It
2239 took just 22 rules to identify the 19 basic token
2240 types. The complete \PROGRAM{lex} file was about
2241 510 lines long, with about 340 lines of C code
2242 mostly concerned with the input and output of
2243 strings, and 120 lines of function and variable
2244 declarations. After \PROGRAM{lex} processing, the
2245 complete C program was about 1130 lines long; with
2246 \PROGRAM{flex}, it is 1700 lines long.%
2247 \index{grammar!size of}
2248 This program is named \PROGRAM{biblex}, and its
2249 output is compatible with that of \BIBCLEAN{} with
2250 the \OPTION{no-prettyprint} option. However, it
2251 offers none of \BIBCLEAN{}'s other services.
2252
2253 The \PROGRAM{lex} grammar is presented in this
2254 section in the style of literate programming,%
2255 \index{literate programming}
2256 with
2257 grammar rules interspersed with descriptive text.
2258 The index at the end of this document provides an
2259 essential feature of a literate program. To my
2260 knowledge, no \WEB{} facility yet exists for
2261 \PROGRAM{lex} and \PROGRAM{yacc}, so this literate
2262 program must be handcrafted.
2263
2264 \subsection*{File structure}
2265
2266 A \PROGRAM{lex} file has this general structure:
2267
2268 \begin{verbatim}
2269 definitions
2270 %%
2271 rules
2272 %%
2273 user functions
2274 \end{verbatim}
2275 \index{\%\%@{\protect\tt \%\%}}
2276
2277 C declarations and definitions can be included in
2278 the declarations part if they are enclosed in
2279 \verb=%{=%
2280 \index{\%(@{\protect\tt \%\{\iffalse "}\fi}}
2281 and \verb=%}=.%
2282 \index{\%)@{\protect\tt \iffalse "{\fi \%\}}}
2283 Such text is copied verbatim to the output code
2284 file, together with additional
2285 \PROGRAM{lex}-supplied header code.
2286
2287 Running \PROGRAM{lex} on this file produces a C
2288 file that can be compiled and linked with a main
2289 program from the \PROGRAM{lex} library to produce
2290 a working lexical analyzer. Alternatively, the
2291 user can write a customized main program which is
2292 linked with the \PROGRAM{lex}-generated code to
2293 make a functional lexer.
2294
2295 In the following subsections, we describe the
2296 contents of the definitions and rules parts, but
2297 omit the user functions, since they are not
2298 relevant to understanding the grammar.
2299
2300 \subsection*{Macro definitions}
2301
2302 The \PROGRAM{lex} grammar begins with macro
2303 definitions.%
2304 \index{macro definition!lex@{\tt lex}}
2305 \PROGRAM{lex} macros are single letters
2306 followed by a regular expression that defines
2307 them.
2308
2309 In regular expressions,%
2310 \index{regular expression!syntax of}
2311 square brackets delimit
2312 sets of characters, hyphen is used for character
2313 ranges inside sets, asterisk means zero or more of
2314 the preceding pattern, and plus means one or more.
2315 A period%
2316 \index{period!in regular expression}
2317 represents any character other than a
2318 newline.
2319
2320 \PROGRAM{lex} macro names are braced%
2321 \index{macro use!lex@{\tt lex}}
2322 to request
2323 expansion when they are used in grammar rules.
2324
2325 The first macro, \MACRO{N}, represents the set of
2326 characters permitted in \BibTeX{} names of
2327 abbreviations, citation keys, entries, and fields.
2328 If this set is ever modified, this is the {\em
2329 only\/} place where that job has to be done.
2330
2331 \begin{verbatim}
2332 N [A-Za-z][---A-Za-z0-9:.+/']*
2333 \end{verbatim}
2334 \noindent
2335
2336 It is not reasonable to make this set differ for
2337 these four different uses, because the differences
2338 are insufficient to distinguish between them
2339 lexically. We'll see later that we have to
2340 examine surrounding context to tell them apart.
2341
2342 Macro \MACRO{O} represents the set of open
2343 delimiters that start a \BibTeX{} entry argument.
2344 We could extend this grammar for \SCRIBE{} by
2345 adding additional characters to the set.
2346
2347 \begin{verbatim}
2348 O [({]
2349 \end{verbatim}
2350
2351 Macro \MACRO{W} represents a single horizontal
2352 space character.%
2353 \index{horizontal space character}
2354
2355 \begin{verbatim}
2356 W [ \f\r\t\013]
2357 \end{verbatim}
2358
2359 \noindent
2360 Notice that we include formfeed,%
2361 \index{formfeed}
2362 \ESCAPE{f}, and
2363 vertical tab,%
2364 \index{vertical!tab}
2365 \ESCAPE{v}, in the set of horizontal space
2366 characters, even though they produce vertical
2367 motion on an output device. The reason is that we
2368 want to treat them just like blanks, and
2369 distinguish them from newlines, which are handled
2370 separately. \PROGRAM{lex} does not recognize the
2371 escape sequence \ESCAPE{v}, so we have to reencode
2372 it in octal as \ESCAPE{013}.
2373
2374 Carriage return,%
2375 \index{carriage return}
2376 \ESCAPE{r}, is not normally used
2377 in \UNIX{} text files, but is common in some other
2378 operating systems. On the Apple Macintosh,%
2379 \index{Apple Macintosh}%
2380 \index{Macintosh!Apple}
2381 carriage return is used instead of newline as an
2382 end-of-line marker. Fortunately, this will be
2383 transparent to us, because the C language requires
2384 \cite[Section~2.2.2]{ANSI:c89}%
2385 \index{ANSI/ISO Standard C@ANSI\slash ISO Standard C}
2386 that the implementation map host line
2387 terminators to newline on input, and newline back
2388 to host line terminators on output, so we will
2389 never see carriage returns on that system.
2390
2391 The last macro, \MACRO{S}, represents optional
2392 horizontal space.
2393
2394 \begin{verbatim}
2395 S {W}*
2396 \end{verbatim}
2397
2398 \subsection*{Format of grammar rules}
2399
2400 \index{format!of grammar rules}%
2401 \index{grammar!format of rules}%
2402 The remainder of the grammar consists of pairs of
2403 regular expression patterns and C code to execute
2404 when the pattern is matched. \PROGRAM{lex} uses a
2405 ``maximal munch'' strategy in matching the longest
2406 possible sequence to handle the case where two
2407 rules have common leading patterns.
2408
2409 In the grammar file, the pairs are each written on
2410 a single line, but we wrap lines%
2411 \index{wrapping!of long lines}%
2412 \index{line!wrapping}
2413 here to fit in
2414 the narrow journal columns, with the
2415 backslash-newline%
2416 \index{backslash-newline}
2417 convention used earlier.
2418
2419 \subsection*{{\tt @} token}
2420
2421 The first grammar rule says that an \TT{\char64}
2422 character should be recognized as the token named
2423 \TOKEN{TOKEN_AT}.
2424
2425 \begin{verbatim}
2426 [@] RETURN (out_token(TOKEN_AT));
2427 \end{verbatim}
2428 \MACROINDEX{RETURN}%
2429 \FUNCTIONINDEX{out_token}%
2430 \TOKENINDEX{TOKEN_AT}%
2431
2432 On a successful match, the output function
2433 optionally emits the token, then returns its
2434 argument as a function value which the lexer in
2435 turn returns to the parser.
2436
2437 The C \TT{return} statement is hidden inside the
2438 \MACRO{RETURN} macro, because for \PROGRAM{yacc}
2439 and \PROGRAM{bison}, we need to bias \BIBCLEAN{}'s
2440 small integer token values to move them beyond the
2441 range of character ordinals.
2442
2443 \subsection*{{\tt Comment}, {\tt Include},
2444 {\tt Preamble}, and {\tt String} tokens}
2445
2446 The next four rules ignore letter case in matching
2447 the words \TT{Comment}, \TT{Include},
2448 \TT{Preamble}, or \TT{String}. If they follow an
2449 \verb=@= character, they are identified as special
2450 tokens; otherwise, they are regarded as string
2451 abbreviation names.
2452
2453 \begin{verbatim}
2454 [Cc][Oo][Mm][Mm][Ee][Nn][Tt] \
2455 RETURN ((last_token == TOKEN_AT) ?
2456 out_token(TOKEN_COMMENT) :
2457 out_token(TOKEN_ABBREV));
2458
2459 [Ii][Nn][Cc][Ll][Uu][Dd][Ee]/{S}{O} \
2460 RETURN ((last_token == TOKEN_AT) ?
2461 out_token(TOKEN_INCLUDE) :
2462 out_token(TOKEN_ABBREV));
2463
2464 [Pp][Rr][Ee][Aa][Mm][Bb][Ll][Ee]/{S}{O} \
2465 RETURN ((last_token == TOKEN_AT) ?
2466 out_token(TOKEN_PREAMBLE) :
2467 out_token(TOKEN_ABBREV));
2468
2469 [Ss][Tt][Rr][Ii][Nn][Gg]/{S}{O} \
2470 RETURN ((last_token == TOKEN_AT) ?
2471 out_token(TOKEN_STRING) :
2472 out_token(TOKEN_ABBREV));
2473 \end{verbatim}
2474 \MACROINDEX{RETURN}%
2475 \VARIABLEINDEX{last_token}%
2476 \FUNCTIONINDEX{out_token}%
2477 \TOKENINDEX{TOKEN_AT}%
2478 \TOKENINDEX{TOKEN_COMMENT}%
2479 \TOKENINDEX{TOKEN_INCLUDE}%
2480 \TOKENINDEX{TOKEN_PREAMBLE}%
2481 \TOKENINDEX{TOKEN_STRING}%
2482
2483 Although \PROGRAM{lex} supports examination of
2484 trailing context in order to identify tokens more
2485 precisely, the presence of arbitrary whitespace
2486 and in-line comments in this grammar makes it
2487 impossible to use this feature. The output
2488 routines remember the last non-space, non-comment
2489 token seen in order to make use of leading context
2490 to assist in token identification.
2491
2492 \subsection*{Abbreviation, entry, field, and key tokens}
2493
2494 Several token types are recognized by a match with
2495 the name macro, \MACRO{N}. Since the same set of
2496 characters can occur in abbreviations,%
2497 \index{abbreviation}
2498 entry names,%
2499 \index{entry!name}
2500 field names,%
2501 \index{field name}
2502 and key names,
2503 \index{key name}
2504 we have to use the record of leading context to
2505 distinguish between the various possibilities.
2506
2507 \begin{verbatim}
2508 {N} {
2509 if (last_object == TOKEN_STRING)
2510 RETURN(out_token(TOKEN_ABBREV));
2511 switch (last_token)
2512 {
2513 case TOKEN_COMMA:
2514 RETURN(out_token(TOKEN_FIELD));
2515 case TOKEN_LBRACE:
2516 RETURN(out_token(TOKEN_KEY));
2517 case TOKEN_AT:
2518 RETURN(out_token(TOKEN_ENTRY));
2519 default:
2520 RETURN(out_token(TOKEN_ABBREV));
2521 }
2522 }
2523 \end{verbatim}
2524 \MACROINDEX{RETURN}%
2525 \VARIABLEINDEX{last_object}%
2526 \VARIABLEINDEX{last_token}%
2527 \FUNCTIONINDEX{out_token}%
2528 \TOKENINDEX{TOKEN_ABBREV}%
2529 \TOKENINDEX{TOKEN_COMMA}%
2530 \TOKENINDEX{TOKEN_ENTRY}%
2531 \TOKENINDEX{TOKEN_FIELD}%
2532 \TOKENINDEX{TOKEN_KEY}%
2533 \TOKENINDEX{TOKEN_STRING}%
2534
2535 In the event of errors in the input stream, this
2536 identification of token types may be unreliable;
2537 such errors will be detected later in the parsing
2538 program.
2539
2540 \subsection*{Digit string}
2541
2542 A {\em digit string\/}%
2543 \index{digit string}
2544 is an undelimited value
2545 string. The output function will supply the
2546 missing quotation mark delimiters, so that all
2547 strings take a standard form.
2548
2549 \begin{verbatim}
2550 [0-9]+ RETURN (out_protected_string( \
2551 TOKEN_VALUE));
2552 \end{verbatim}
2553 \MACROINDEX{RETURN}%
2554 \FUNCTIONINDEX{out_protected_string}%
2555 \TOKENINDEX{TOKEN_VALUE}%
2556
2557 \subsection*{In-line comment token}
2558
2559 A percent initiates an {\em in-line comment\/}%
2560 \index{in-line comment}%
2561 \index{comment!in-line}
2562 that continues to the end of line and then over
2563 all leading horizontal space on the next line.
2564
2565 \begin{verbatim}
2566 [%].*[\n]{S} \
2567 RETURN (out_token(TOKEN_INLINE));
2568 \end{verbatim}
2569 \MACROINDEX{RETURN}%
2570 \FUNCTIONINDEX{out_token}%
2571 \TOKENINDEX{TOKEN_INLINE}%
2572
2573 Because this pattern marks the start of a new
2574 token, the previous token has already been
2575 terminated. Thus, an line-line comment {\em
2576 cannot\/} split a token. The same is true for
2577 \TeX{} macros, though not for ordinary \TeX{}
2578 text.
2579
2580 \subsection*{String concatenation token}
2581
2582 A sharp%
2583 \index{sharp@sharp ({\tt\char35})}
2584 sign is the \BibTeX{} {\em string concatenation
2585 operator}.%
2586 \index{string!concatenation operator}%
2587 \index{operator!string concatenation}
2588
2589 \begin{verbatim}
2590 [#] RETURN (out_token(TOKEN_SHARP));
2591 \end{verbatim}
2592 \MACROINDEX{RETURN}%
2593 \FUNCTIONINDEX{out_token}%
2594 \TOKENINDEX{TOKEN_SHARP}%
2595
2596 \subsection*{Delimited string token}
2597
2598 A quotation mark initiates a {\em delimited
2599 string}.%
2600 \index{delimited string}
2601
2602 \begin{verbatim}
2603 ["] RETURN (out_string());
2604 \end{verbatim}
2605 \MACROINDEX{RETURN}%
2606 \FUNCTIONINDEX{out_string}%
2607
2608 The complete string must be collected by the C
2609 function \FUNCTION{out_string} because regular
2610 expressions cannot count balanced delimiters.
2611
2612 \BibTeX{}'s quoted string syntax is a little
2613 unusual, in that an embedded quote%
2614 \index{embedded quote}%
2615 \index{quote!embedded}
2616 is not
2617 represented by double quotes, as in Fortran, or by
2618 an escape sequence,%
2619 \index{escape sequence}
2620 as in C, but rather by putting
2621 the quote character in braces.
2622
2623 \subsection*{Brace tokens}
2624
2625 Left and right {\em braces\/}%
2626 \index{brace}
2627 are recognized as single tokens.
2628
2629 \begin{verbatim}
2630 [{] RETURN (out_lbrace());
2631
2632 [}] RETURN (out_rbrace());
2633 \end{verbatim}
2634 \MACROINDEX{RETURN}%
2635 \FUNCTIONINDEX{out_rbrace}%
2636 \FUNCTIONINDEX{out_lbrace}%
2637
2638 The output functions keep track of the current
2639 brace level to distinguish between outer braces
2640 delimiting a \BibTeX{} entry, and inner braces
2641 delimiting a string value, and return
2642 \TOKEN{TOKEN_LBRACE}, \TOKEN{TOKEN_LITERAL},
2643 \TOKEN{TOKEN_RBRACE}, or \TOKEN{TOKEN_STRING},
2644 depending on preceding context.
2645
2646 \TOKEN{TOKEN_LITERAL} is used for the argument of
2647 a \TT{Comment} and \TT{Include} entries, and
2648 contains the delimiting braces.
2649
2650 \subsection*{Parenthesis tokens}
2651
2652 In order to simplify the parser grammar, we remap
2653 outer {\em parentheses\/}%
2654 \index{parenthesis}
2655 delimiting arguments of
2656 \BibTeX{} entries to {\em braces}.%
2657 \index{brace}
2658 However, if the
2659 parentheses are not preceded by a valid entry
2660 name, they are output instead as single-character
2661 tokens of type \TOKEN{TOKEN_LITERAL}. They cannot
2662 legally occur in this context, but that error will
2663 be detected during the parsing stage. During
2664 lexical analysis, we do not want to have any error
2665 conditions.
2666
2667 \begin{verbatim}
2668 [(] RETURN (out_lparen());
2669
2670 [)] RETURN (out_rparen());
2671 \end{verbatim}
2672 \FUNCTIONINDEX{out_rparen}%
2673 \FUNCTIONINDEX{out_lparen}%
2674
2675 To support \SCRIBE{}, we would need to add
2676 patterns for other delimiters here.
2677
2678 \subsection*{Assignment and separator tokens}
2679
2680 The {\em assignment operator\/}%
2681 \index{assignment!operator}
2682 \index{operator!assignment}
2683 and {\em assignment separator\/}%
2684 \index{assignment!separator}%
2685 \index{separator!assignment}
2686 are returned as single tokens.
2687
2688 \begin{verbatim}
2689 [=] RETURN (out_token(TOKEN_EQUALS));
2690
2691 [,] RETURN (out_token(TOKEN_COMMA));
2692 \end{verbatim}
2693 \MACROINDEX{RETURN}%
2694 \FUNCTIONINDEX{out_token}%
2695 \TOKENINDEX{TOKEN_COMMA}%
2696 \TOKENINDEX{TOKEN_EQUALS}%
2697
2698 \subsection*{Newline token}
2699
2700 A {\em newline\/}%
2701 \index{newline}
2702 is returned as a separate token
2703 because we want to be able to preserve line
2704 boundaries so that filter tools that make minimal
2705 perturbations on the input stream can be
2706 constructed.
2707
2708 \begin{verbatim}
2709 [\n] RETURN (out_token(TOKEN_NEWLINE));
2710 \end{verbatim}
2711 \MACROINDEX{RETURN}%
2712 \FUNCTIONINDEX{out_token}%
2713 \TOKENINDEX{TOKEN_NEWLINE}%
2714
2715 \subsection*{Horizontal space token}
2716
2717 Consecutive horizontal space characters%
2718 \index{horizontal space character}
2719 are returned as a single space token, for the same
2720 reason that newlines%
2721 \index{newline}
2722 are recognized as distinct tokens by the preceding
2723 rule.
2724
2725 \begin{verbatim}
2726 {W}+ RETURN (out_token(TOKEN_SPACE));
2727 \end{verbatim}
2728 \MACROINDEX{RETURN}%
2729 \FUNCTIONINDEX{out_token}%
2730 \TOKENINDEX{TOKEN_SPACE}%
2731
2732 \subsection*{Unclassifiable tokens}
2733
2734 \index{unclassifiable token}%
2735 \index{token!unclassifiable}%
2736 Finally, we have a catch-all rule: any character
2737 not recognized by one of the preceding rules is
2738 returned as a literal single-character token, and
2739 will cause an error during the parsing. The
2740 regular-expression character period
2741 \index{period!in regular expression}
2742 matches anything but a newline,%
2743 \index{newline}
2744 and we already have a rule for newline.
2745
2746 \begin{verbatim}
2747 . RETURN (out_token(TOKEN_LITERAL));
2748 \end{verbatim}
2749 \MACROINDEX{RETURN}%
2750 \FUNCTIONINDEX{out_token}%
2751 \TOKENINDEX{TOKEN_LITERAL}%
2752
2753 \subsection*{Lexical grammar summary}
2754
2755 We now have a complete lexical grammar suitable
2756 for \PROGRAM{lex} that can complete tokenize an
2757 arbitrary input stream containing any character
2758 values whatever.
2759
2760 The associated C code functions normalize entries
2761 by changing outer parentheses to braces, brace
2762 string delimiters to quotes, and undelimited digit
2763 strings to quoted strings.
2764
2765 All string tokens of type \TOKEN{TOKEN_VALUE}
2766 output by the lexer will contain surrounding
2767 quotes, and any nested quotes will be braced, with
2768 proper care taken to handle \ESCAPE{\char34}
2769 accent control sequences%
2770 \index{accent control sequence}
2771 properly.
2772
2773 All special characters inside the quoted strings
2774 will be represented by the escape sequences given
2775 in Table~\ref{tab:escape} on
2776 page~\pageref{tab:escape}. Thus, even with a
2777 binary input stream, the output of the lexer will
2778 contain only printable characters.
2779
2780 It must be observed that \PROGRAM{lex} is not
2781 capable of handling all 256 8-bit characters. In
2782 particular, it treats an ASCII NUL%
2783 \index{NUL (0)!in string}
2784 (\ESCAPE{0}) in a string as an end-of-file
2785 condition. Older versions of \PROGRAM{lex} are
2786 not {\em 8-bit clean};%
2787 \index{8-bit clean}
2788 they will not reliably handle characters 128--255.
2789 This latter deficiency is being remedied by the
2790 X/Open Consortium%
2791 \index{X/Open Consortium}
2792 activities to internationalize and standard
2793 \UNIX{} applications
2794 \cite{xopen:XPG89-1}.
2795
2796 \section{A parsing grammar for \protect\BibTeX{}}%
2797 \label{sec:yacc-grammar}
2798
2799 \index{grammar!parsing}%
2800 \index{parsing grammar}%
2801 To complete the job, I wrote a \PROGRAM{yacc}
2802 grammar for \BibTeX{}. This was considerably more
2803 work than the \PROGRAM{lex} grammar, mostly due to
2804 my relative inexperience with writing LALR(1)
2805 grammars, and it took several days to understand
2806 the process well enough to eliminate the
2807 grammatical ambiguities that initially plagued me.
2808
2809 The final complete \PROGRAM{yacc} program is about
2810 270 lines long, and produces a parser of 760
2811 (\PROGRAM{yacc}) to 1000 (\PROGRAM{bison}) lines,
2812 excluding the lexer. The grammar contains just 35
2813 rules.%
2814 \index{grammar!size of}
2815 Ten of these rules could be eliminated if
2816 we arranged for the lexer to discard space%
2817 \index{space}
2818 and
2819 in-line comments,%
2820 \index{in-line comment}%
2821 \index{comment!in-line}
2822 but for a prettyprinter and
2823 other \BibTeX{} tools, they must be preserved.
2824 This parsing program is called \PROGRAM{bibparse};
2825 it can be used with the output of either
2826 \BIBCLEAN{} \OPTION{no-prettyprint}, or
2827 \PROGRAM{biblex}.
2828
2829 The complete \BibTeX{} grammar is given below,
2830 expressed as \PROGRAM{yacc} rules, again in
2831 literate programming%
2832 \index{literate programming}
2833 style. It must be augmented by about
2834 180 lines of C code to provide a working parser.
2835
2836 \subsection*{File structure}
2837
2838 A \PROGRAM{yacc} file has this general structure:
2839
2840 \begin{verbatim}
2841 declarations
2842 %%
2843 rules
2844 %%
2845 user functions
2846 \end{verbatim}
2847 \index{\%\%@{\protect\tt \%\%}}
2848
2849 C declarations and definitions can be included in
2850 the declarations part if they are enclosed in
2851 \verb=%{=%
2852 \index{\%(@{\protect\tt \%\{\iffalse "}\fi}}
2853 and \verb=%}=.%
2854 \index{\%)@{\protect\tt \iffalse "{\fi \%\}}}
2855 Such text is copied verbatim to the output code
2856 file, together with additional
2857 \PROGRAM{yacc}-supplied header code.
2858
2859 Running \PROGRAM{yacc} on this file produces a C
2860 file that can be compiled and linked with the
2861 lexical analyzer code to produce a working parser.
2862
2863 In the following subsections, we describe the
2864 contents of the declarations and rules parts, but
2865 omit the declaration C code and the user
2866 functions, since they are not relevant to
2867 understanding the grammar.
2868
2869 \subsection*{Format of grammar rules}
2870
2871 \index{format!of grammar rules}%
2872 \index{grammar!format of rules}%
2873 The grammar rules will be presented in top-down
2874 order, from most general, to most particular,
2875 since this seems to be the best way to understand
2876 the overall structure of the grammar, and to
2877 ensure that it describes current \BibTeX{} usage,
2878 plus our suggested extensions and clarifications.
2879
2880 The colon%
2881 \index{colon}
2882 in a grammar rule should be read ``is''
2883 or ``produces'', because the rule is also known as
2884 a {\em production}. A vertical bar%
2885 \index{vertical!bar}
2886 separates
2887 alternatives, and can be read ``or''. A
2888 semicolon%
2889 \index{semicolon}
2890 terminates the rule.
2891
2892 Lower-case letters are used for {\em
2893 non-terminals},%
2894 \index{non-terminal}
2895 which are names of rules in the parser grammar.
2896 Upper-case letters are used for {\em terminals},%
2897 \index{terminal}
2898 which are names of tokens recognized by the lexer.
2899
2900 The spacing shown is arbitrary, but conventional
2901 for \PROGRAM{yacc} grammars:%
2902 \index{grammar!formatting conventions}
2903 each rule starts a new line, with the right-hand
2904 side indented from the margin, and the semicolon%
2905 \index{semicolon}
2906 occupies a separate line.
2907
2908 \subsection*{Token declarations}
2909
2910 The \TT{\%token} declarations merely provide
2911 symbolic names for the integer token types
2912 returned by the lexer. The values are arbitrary,
2913 except that they must exceed 257, and must agree
2914 with the definitions in the lexer code. We simply
2915 increment the token types output from \BIBCLEAN{}
2916 by 1000, matching the offset added in the
2917 \MACRO{RETURN} macro in the lexer.
2918
2919 \begin{verbatim}
2920 %token TOKEN_ABBREV 1001
2921 %token TOKEN_AT 1002
2922 %token TOKEN_COMMA 1003
2923 %token TOKEN_COMMENT 1004
2924 %token TOKEN_ENTRY 1005
2925 %token TOKEN_EQUALS 1006
2926 %token TOKEN_FIELD 1007
2927 %token TOKEN_INCLUDE 1008
2928 %token TOKEN_INLINE 1009
2929 %token TOKEN_KEY 1010
2930 %token TOKEN_LBRACE 1011
2931 %token TOKEN_LITERAL 1012
2932 %token TOKEN_NEWLINE 1013
2933 %token TOKEN_PREAMBLE 1014
2934 %token TOKEN_RBRACE 1015
2935 %token TOKEN_SHARP 1016
2936 %token TOKEN_SPACE 1017
2937 %token TOKEN_STRING 1018
2938 %token TOKEN_VALUE 1019
2939 \end{verbatim}
2940 \TOKENINDEX{TOKEN_ABBREV}%
2941 \TOKENINDEX{TOKEN_AT}%
2942 \TOKENINDEX{TOKEN_COMMA}%
2943 \TOKENINDEX{TOKEN_COMMENT}%
2944 \TOKENINDEX{TOKEN_ENTRY}%
2945 \TOKENINDEX{TOKEN_EQUALS}%
2946 \TOKENINDEX{TOKEN_FIELD}%
2947 \TOKENINDEX{TOKEN_INCLUDE}%
2948 \TOKENINDEX{TOKEN_INLINE}%
2949 \TOKENINDEX{TOKEN_KEY}%
2950 \TOKENINDEX{TOKEN_LBRACE}%
2951 \TOKENINDEX{TOKEN_LITERAL}%
2952 \TOKENINDEX{TOKEN_NEWLINE}%
2953 \TOKENINDEX{TOKEN_PREAMBLE}%
2954 \TOKENINDEX{TOKEN_RBRACE}%
2955 \TOKENINDEX{TOKEN_SHARP}%
2956 \TOKENINDEX{TOKEN_SPACE}%
2957 \TOKENINDEX{TOKEN_STRING}%
2958 \TOKENINDEX{TOKEN_VALUE}%
2959
2960 \subsection*{Precedence declarations}
2961
2962 \index{precedence declaration}%
2963 The \TT{\%nonassoc}%
2964 \index{nonassoc@{\tt \%nonassoc}}
2965 declaration makes the
2966 assignment operator%
2967 \index{assignment!operator!associativity of}%
2968 \index{associativity}
2969 non-associative, so input of
2970 the form {\tt a = b = c} is illegal.
2971
2972 \begin{verbatim}
2973 %nonassoc TOKEN_EQUALS
2974 \end{verbatim}
2975 \TOKENINDEX{TOKEN_EQUALS}%
2976
2977 The first \TT{\%left}%
2978 \index{left@{\tt \%left}}
2979 declaration makes space,%
2980 \index{space!associativity of}
2981 in-line comment,%
2982 \index{in-line comment!associativity of}%
2983 \index{comment!in-line!associativity of}
2984 and newline%
2985 \index{newline!associativity of}
2986 tokens left associative, and of equal precedence.
2987
2988 \begin{verbatim}
2989 %left TOKEN_SPACE TOKEN_INLINE \
2990 TOKEN_NEWLINE
2991 \end{verbatim}
2992 \TOKENINDEX{TOKEN_INLINE}%
2993 \TOKENINDEX{TOKEN_NEWLINE}%
2994 \TOKENINDEX{TOKEN_SPACE}%
2995
2996 The second \TT{\%left}%
2997 \index{left@{\tt \%left}}
2998 declaration makes the
2999 \BibTeX{} string concatenation character,%
3000 \index{string!concatenation operator}%
3001 \index{operator!string concatenation}
3002 \verb=#=, left associative, and of higher
3003 precedence than space,%
3004 \index{space!precedence of}
3005 in-line comment,%
3006 \index{in-line comment!precedence of}%
3007 \index{comment!in-line!precedence of}
3008 and newline.
3009
3010 \begin{verbatim}
3011 %left TOKEN_SHARP
3012 \end{verbatim}
3013 \TOKENINDEX{TOKEN_SHARP}%
3014
3015 These precedence settings are crucial for
3016 resolving conflicts in this grammar which arise
3017 in assignments when the parser has seen an
3018 assignment operator and a value. Without the
3019 operator precedences, it cannot decide whether to
3020 complete the assignment, or to read ahead looking
3021 for a concatenation operator.
3022
3023 \subsection*{\protect \BibTeX{} file}
3024
3025 The beginning of the grammar rules is indicated by
3026 a pair of percent characters.
3027
3028 \begin{verbatim}
3029 %%
3030 \end{verbatim}
3031
3032 The first rule defines what we are going to parse,
3033 namely, a {\em \BibTeX{} file}. The left-hand
3034 side of the first rule is known as the grammar's
3035 {\em start symbol}.
3036
3037 \begin{verbatim}
3038 bibtex_file:
3039 opt_space
3040 | opt_space object_list opt_space
3041 ;
3042 \end{verbatim}
3043 \RULEINDEX{bibtex_file}%
3044 \RULEINDEX{object_list}%
3045 \RULEINDEX{opt_space}%
3046
3047 This rule says that a \BibTeX{} file contains
3048 either optional space, or optional space followed
3049 by a list of objects followed by optional space.
3050 This definition permits a file to be empty, or
3051 contain only space tokens, or have leading and
3052 trailing space.
3053
3054 \subsection*{Object lists}
3055
3056 A {\em list of objects\/}%
3057 \index{list!of objects}%
3058 \index{object!list}
3059 is either a single
3060 object, or a list of such objects, separated by
3061 optional space from another object.
3062
3063 \begin{verbatim}
3064 object_list:
3065 object
3066 | object_list opt_space object
3067 ;
3068 \end{verbatim}
3069 \RULEINDEX{opt_space}%
3070 \RULEINDEX{object}%
3071 \RULEINDEX{object_list}%
3072
3073 For LL(1)%
3074 \index{LL(1)!parser}%
3075 \index{parser!LL(1)}
3076 parsers, usually implemented by
3077 hand-coded recursive descent programs, this kind
3078 of left-recursive rule%
3079 \index{left-recursive rule}
3080 must be rewritten by
3081 standard methods
3082 \cite[pp.~47--48, 176--178]{Aho:CPT86}%
3083 \index{Aho, Alfred V.}%
3084 \index{Sethi, Ravi}%
3085 \index{Ullman, Jeffrey D.}
3086 to avoid an infinite loop in the parser. In this
3087 rule, we would instead define a list as an object,
3088 separated by optional space from another list.
3089 However, for LALR(1) parsers, left-recursive
3090 definitions are preferable, because they avoid
3091 parser stack overflow with long lists.
3092
3093 \subsection*{Objects}
3094
3095 An {\em object\/}%
3096 \index{object}
3097 is one of the \BibTeX{}
3098 \TT{\char64name\protect\{...\protect\}}
3099 constructs. Notice that we allow optional space
3100 between the \TT{\char64} and the \TT{name}.
3101
3102 \begin{verbatim}
3103 object:
3104 TOKEN_AT opt_space at_object
3105 ;
3106 \end{verbatim}
3107 \RULEINDEX{at_object}%
3108 \RULEINDEX{opt_space}%
3109 \TOKENINDEX{TOKEN_AT}%
3110 \RULEINDEX{object}%
3111
3112 In this grammar, we will consistently allow
3113 optional space%
3114 \index{space!between tokens}
3115 between {\em any\/} pair of
3116 \BibTeX{} tokens; space is described more
3117 precisely below. This convention is easy to
3118 remember, and easy to implement in the grammar
3119 rules.
3120
3121 While it would be possible to include the
3122 \TT{\char64} as part of the \TT{name}, making
3123 \TT{\char64name} a single lexical token, both
3124 \BibTeX{} and \SCRIBE{} permit intervening space,
3125 so we cannot collapse the two into a single token.
3126
3127 \subsection*{Entry types and error recovery}
3128
3129 Here are the possibilities for the \TT{name}
3130 following an \TT{\char64}, which we call an
3131 \RULE{at_object}.
3132
3133 \begin{verbatim}
3134 at_object:
3135 comment
3136 | entry
3137 | include
3138 | preamble
3139 | string
3140 | error TOKEN_RBRACE
3141 ;
3142 \end{verbatim}
3143 \TOKENINDEX{TOKEN_RBRACE}%
3144 \RULEINDEX{error}%
3145 \RULEINDEX{string}%
3146 \RULEINDEX{preamble}%
3147 \RULEINDEX{include}%
3148 \RULEINDEX{entry}%
3149 \RULEINDEX{comment}%
3150 \RULEINDEX{at_object}%
3151
3152 \TT{Comment}, \TT{Include}, \TT{Preamble},
3153 and \TT{String} must be handled separately from
3154 other types of entries, like \TT{Article} and
3155 \TT{Book}, because their braced arguments have a
3156 different syntax.
3157
3158 The rule with \RULE{error} is a special one
3159 supported by \PROGRAM{yacc} and \PROGRAM{bison}.
3160 It says that if an \RULE{at_object} cannot be
3161 recognized at the current state of the parse, then
3162 the input should be discarded until a right brace
3163 is found. An error message%
3164 \index{error!message}%
3165 \index{message!error}
3166 will be issued when
3167 this happens, but recovery%
3168 \index{error!recovery}%
3169 \index{recovery!from error}
3170 will be attempted
3171 following that right brace. Without this error
3172 handling, any input error will immediately
3173 terminate the parser, hardly a user-friendly thing
3174 to do.
3175
3176 This is the only place where we will attempt error
3177 repair, although we could certainly do so in other
3178 rules, such as in the assignment rule%
3179 \index{assignment!rule!error recovery in}
3180 below. The
3181 goal here is to present a rigorous complete
3182 grammar, without additional embellishments that
3183 would complicate understanding.
3184
3185 \subsection*{Comment entry}
3186
3187 \index{comment!entry}%
3188 A \BibTeX{}
3189 \TT{\char64Comment\optbreak\protect\{...\protect\}}
3190 is special in that the only requirement on the
3191 argument is that delimiters be balanced. The
3192 lexer returns the delimited argument as a single
3193 literal string, including the delimiters, and
3194 standardizes the delimiters to braces.
3195
3196 \begin{verbatim}
3197 comment:
3198 TOKEN_COMMENT opt_space
3199 TOKEN_LITERAL
3200 ;
3201 \end{verbatim}
3202 \TOKENINDEX{TOKEN_LITERAL}%
3203 \RULEINDEX{opt_space}%
3204 \TOKENINDEX{TOKEN_COMMENT}%
3205 \RULEINDEX{comment}%
3206
3207 \subsection*{Bibliography entry}
3208
3209 A \BibTeX{} {\em bibliography entry}%
3210 \index{bibliography!entry}
3211 is braced
3212 text containing a citation key,%
3213 \index{citation!key}
3214 a comma,%
3215 \index{comma}
3216 and a
3217 list of assignments.%
3218 \index{list!of assignments}%
3219 \index{assignment!list}
3220 The rules provide for an
3221 optional assignment list, and for an optional
3222 trailing comma.%
3223 \index{trailing context}
3224 To shorten the rules, we
3225 introduce a subsidiary rule, \RULE{entry_head}, to
3226 represent their common prefix.
3227
3228 \begin{verbatim}
3229 entry: entry_head
3230 assignment_list
3231 TOKEN_RBRACE
3232 | entry_head
3233 assignment_list
3234 TOKEN_COMMA opt_space
3235 TOKEN_RBRACE
3236 | entry_head TOKEN_RBRACE
3237 ;
3238
3239 entry_head:
3240 TOKEN_ENTRY opt_space
3241 TOKEN_LBRACE opt_space
3242 key_name opt_space
3243 TOKEN_COMMA opt_space
3244 ;
3245 \end{verbatim}
3246 \RULEINDEX{key_name}%
3247 \TOKENINDEX{TOKEN_LBRACE}%
3248 \TOKENINDEX{TOKEN_ENTRY}%
3249 \TOKENINDEX{TOKEN_COMMA}%
3250 \TOKENINDEX{TOKEN_RBRACE}%
3251 \RULEINDEX{opt_space}%
3252 \RULEINDEX{assignment_list}%
3253 \RULEINDEX{entry_head}%
3254 \RULEINDEX{entry}%
3255
3256 There is no \TT{opt_space} item following
3257 \TT{assignment_list} because it is included in the
3258 definition of the latter. This infelicity seems
3259 to be necessary to obtain a grammar that conforms
3260 to the LALR(1)%
3261 \index{LALR(1)!grammar}%
3262 \index{grammar!LALR(1)}
3263 requirements of \PROGRAM{yacc} and \PROGRAM{bison}.
3264
3265 \subsection*{Key name}
3266
3267 \index{key name}%
3268 Because of intervening newlines%
3269 \index{newline}
3270 and in-line comments,%
3271 \index{in-line comment}%
3272 \index{comment!in-line}
3273 the lexical analyzer cannot always
3274 correctly recognize a {\em citation key\/}%
3275 \index{citation!key!problems in recognizing}
3276 from trailing context.%
3277 \index{trailing context}
3278 It might instead erroneously identify the token as
3279 an abbreviation. We therefore need to account for
3280 both possibilities:
3281 \typeout{key_name may no longer need to allow for abbrevs}%
3282
3283 \begin{verbatim}
3284 key_name:
3285 TOKEN_KEY
3286 | TOKEN_ABBREV
3287 ;
3288 \end{verbatim}
3289 \TOKENINDEX{TOKEN_ABBREV}%
3290 \TOKENINDEX{TOKEN_KEY}%
3291 \RULEINDEX{key_name}%
3292
3293 \subsection*{{\protect\tt Include} entry}
3294
3295 \index{file!inclusion}%
3296 The \TT{Include} entry is followed by a file
3297 name enclosed in balanced braces.
3298
3299 \begin{verbatim}
3300 include:
3301 TOKEN_INCLUDE opt_space
3302 TOKEN_LITERAL
3303 ;
3304 \end{verbatim}
3305 \TOKENINDEX{TOKEN_LITERAL}%
3306 \RULEINDEX{opt_space}%
3307 \TOKENINDEX{TOKEN_INCLUDE}%
3308 \RULEINDEX{include}%
3309
3310 Because file names%
3311 \index{file!name!syntax of}
3312 are operating-system dependent,
3313 the only restrictions that are placed on the file
3314 name are that it cannot contain unbalanced braces,
3315 and that it cannot contain leading or trailing
3316 space. However, the file name can have embedded
3317 space%
3318 \index{file!name!space in}
3319 if the operating system permits.
3320
3321 \BibTeX{} should discard the delimiting braces and
3322 surrounding space in the \path=TOKEN_LITERAL= to
3323 isolate the file name. It should search for this
3324 file in its standard input path, so that the file
3325 name need not contain an absolute directory path.
3326 This feature is not supported in \BibTeX{} 0.99c,
3327 but \BIBCLEAN{} and the lexer and parser recognize
3328 it in anticipation of its eventual incorporation.
3329
3330 \subsection*{{\protect\tt Preamble} entry}
3331
3332 The \TT{Preamble} entry argument is a braced
3333 \BibTeX{} string value. \BibTeX{} outputs the
3334 argument verbatim, minus the outer delimiters, to
3335 the \verb=.bbl=%
3336 \PATHINDEX{.bbl}
3337 file for \TeX{} to process.
3338
3339 \begin{verbatim}
3340 preamble:
3341 TOKEN_PREAMBLE opt_space
3342 TOKEN_LBRACE opt_space
3343 value opt_space
3344 TOKEN_RBRACE
3345 ;
3346 \end{verbatim}
3347 \TOKENINDEX{TOKEN_RBRACE}%
3348 \TOKENINDEX{TOKEN_LBRACE}%
3349 \RULEINDEX{value}%
3350 \RULEINDEX{opt_space}%
3351 \TOKENINDEX{TOKEN_PREAMBLE}%
3352 \RULEINDEX{preamble}%
3353
3354 \subsection*{{\protect\tt String} entry}
3355
3356 The \TT{String} entry argument is a braced
3357 single assignment.
3358
3359 \begin{verbatim}
3360 string:
3361 TOKEN_STRING opt_space
3362 TOKEN_LBRACE opt_space
3363 assignment opt_space
3364 TOKEN_RBRACE
3365 ;
3366 \end{verbatim}
3367 \TOKENINDEX{TOKEN_RBRACE}%
3368 \RULEINDEX{assignment}%
3369 \RULEINDEX{opt_space}%
3370 \TOKENINDEX{TOKEN_LBRACE}%
3371 \RULEINDEX{opt_space}%
3372 \TOKENINDEX{TOKEN_STRING}%
3373 \RULEINDEX{string}%
3374
3375 \subsection*{Value string}
3376
3377 A \BibTeX{} {\em value\/}%
3378 \index{value}
3379 is a string, which may
3380 be a simple value, or a list of strings separated
3381 by the string concatenation operator.%
3382 \index{string!concatenation operator}%
3383 \index{operator!string concatenation}
3384
3385 \begin{verbatim}
3386 value: simple_value
3387 | value opt_space
3388 TOKEN_SHARP opt_space
3389 simple_value
3390 ;
3391 \end{verbatim}
3392 \RULEINDEX{simple_value}%
3393 \TOKENINDEX{TOKEN_SHARP}%
3394 \RULEINDEX{opt_space}%
3395 \RULEINDEX{simple_value}%
3396 \RULEINDEX{value}%
3397
3398 \subsection*{Simple values}
3399
3400 A {\em simple value\/}%
3401 \index{simple value}
3402 is either a delimited
3403 string,%
3404 \index{delimited string}
3405 returned by the lexer as a
3406 \TOKEN{TOKEN_VALUE}, or a string abbreviation,%
3407 \index{abbreviation}
3408 returned as a \TOKEN{TOKEN_ABBREV}.
3409
3410 \begin{verbatim}
3411 simple_value:
3412 TOKEN_VALUE
3413 | TOKEN_ABBREV
3414 ;
3415 \end{verbatim}
3416 \TOKENINDEX{TOKEN_ABBREV}%
3417 \TOKENINDEX{TOKEN_VALUE}%
3418 \RULEINDEX{simple_value}%
3419
3420 The lexer can distinguish between these two
3421 because of the string delimiters. It is up to the
3422 parser support code to verify that an abbreviation
3423 is actually defined before it is used.
3424
3425 \subsection*{Assignment list}
3426
3427 The body of most \BibTeX{} entries consists of a
3428 list of one or more assignments, separated by
3429 commas. Notice that this definition does not
3430 provide for an optional trailing comma%
3431 \index{comma!optional after assignment}
3432 after the last assignment. We handled that above
3433 in the rules for \RULE{entry}.
3434
3435 \begin{verbatim}
3436 assignment_list:
3437 assignment
3438 | assignment_list
3439 TOKEN_COMMA opt_space
3440 assignment
3441 ;
3442 \end{verbatim}
3443 \TOKENINDEX{TOKEN_COMMA}%
3444 \RULEINDEX{opt_space}%
3445 \RULEINDEX{assignment_list}%
3446 \RULEINDEX{assignment}%
3447 \RULEINDEX{assignment_list}%
3448
3449 \subsection*{Assignment}
3450
3451 An {\em assignment\/}%
3452 \index{assignment}
3453 has a left-hand side separated from a value by the
3454 assignment operator,%
3455 \index{assignment!operator}
3456 \index{operator!assignment}
3457 \verb|=|.
3458
3459 \begin{verbatim}
3460 assignment:
3461 assignment_lhs opt_space
3462 TOKEN_EQUALS opt_space value
3463 opt_space
3464 ;
3465 \end{verbatim}
3466 \RULEINDEX{value}%
3467 \TOKENINDEX{TOKEN_EQUALS}%
3468 \RULEINDEX{opt_space}%
3469 \RULEINDEX{assignment_lhs}%
3470 \RULEINDEX{assignment}%
3471
3472 Trailing optional space is included here, and
3473 omitted before the comma in \TT{assignment_list},
3474 in order to allow the LALR(1) parser to
3475 successfully distinguish between space between a
3476 value and a comma, and space between a value and a
3477 string concatenation operator.
3478
3479 My initial version of this grammar did not have
3480 this optional space item, and the resulting parser
3481 proved unable to recognize input in which a space
3482 separated a value from a comma or closing brace;
3483 it took quite a bit of experimentation to
3484 determine how to rewrite the grammar to remove
3485 this problem.
3486
3487 The left-hand side of an assignment is either a
3488 field name,%
3489 \index{field name}
3490 like \TT{author} or \TT{title}, or
3491 a string abbreviation%
3492 \index{abbreviation}
3493 name. The lexer must
3494 distinguish between the two by remembering the
3495 last entry type seen, because they are made up of
3496 exactly the same set of possible characters.
3497
3498 \begin{verbatim}
3499 assignment_lhs:
3500 TOKEN_FIELD
3501 | TOKEN_ABBREV
3502 ;
3503 \end{verbatim}
3504 \TOKENINDEX{TOKEN_ABBREV}%
3505 \TOKENINDEX{TOKEN_FIELD}%
3506 \RULEINDEX{assignment_lhs}%
3507
3508 \subsection*{Optional space}
3509
3510 Optional space is either an empty string,%
3511 \index{empty!string}
3512 here
3513 indicated by the \TT{/*...*/} comment, or space.
3514
3515 \begin{verbatim}
3516 opt_space:
3517 /* empty */
3518 | space
3519 ;
3520 \end{verbatim}
3521 \RULEINDEX{space}%
3522 \RULEINDEX{/* empty */}%
3523 \RULEINDEX{opt_space}%
3524
3525 \subsection*{Space}
3526
3527 {\em Space\/}%
3528 \index{space}
3529 is an important part of the grammar. It is one or
3530 more single spaces.
3531
3532 \begin{verbatim}
3533 space: single_space
3534 | space single_space
3535 ;
3536 \end{verbatim}
3537 \RULEINDEX{single_space}%
3538 \RULEINDEX{space}%
3539
3540 We include space handling to support tools that
3541 process \BibTeX{} files and wish to preserve the
3542 input form. In normal compiler design, space is
3543 recognized by the lexer, and discarded, so the
3544 parser never has to deal with it, and the grammar
3545 can be considerably simpler.
3546
3547 \subsection*{Single space}
3548
3549 The final rule of the grammar defines a {\em
3550 single space\/}%
3551 \index{single space}
3552 as a literal space%
3553 \index{space}
3554 character, or
3555 an in-line comment,%
3556 \index{in-line comment}%
3557 \index{comment!in-line}
3558 or a literal newline%
3559 \index{newline}
3560 character.
3561
3562 \begin{verbatim}
3563 single_space:
3564 TOKEN_SPACE
3565 | TOKEN_INLINE
3566 | TOKEN_NEWLINE
3567 ;
3568 \end{verbatim}
3569 \TOKENINDEX{TOKEN_NEWLINE}%
3570 \TOKENINDEX{TOKEN_INLINE}%
3571 \TOKENINDEX{TOKEN_SPACE}%
3572 \RULEINDEX{single_space}%
3573
3574 Although we could arrange for the lexer to merge
3575 \TOKEN{TOKEN_SPACE} and \TOKEN{TOKEN_NEWLINE} into
3576 a single token, this would interfere with
3577 heuristics used by a prettyprinter to detect empty
3578 lines inside string values, which are possibly
3579 indicative of missing delimiters.%
3580 \index{mismatched delimiters}%
3581 \index{delimiters!mismatched}
3582
3583 \subsection*{Parsing grammar summary}
3584
3585 We have now completed a \PROGRAM{yacc} grammar for
3586 \BibTeX{} that provides a rigorous grammatical
3587 analysis of a stream of tokens recognized by the
3588 lexers in Sections~\ref{sec:lexer}
3589 and~\ref{sec:lex-grammar}.
3590
3591 Notice that there is no character-string
3592 processing whatever in the parser, because it has
3593 all been done in the lexer. Parsing operations
3594 just manipulate small integer values.
3595
3596 In this version, no actions have been supplied as
3597 C code fragments in the \PROGRAM{yacc} grammar.
3598 The only output of the parser will be the token
3599 stream from the lexer, interspersed by error
3600 messages when the input fails to match a grammar
3601 rule.
3602
3603 Error recovery has been kept simple: input is
3604 flushed to the next closing brace, which is
3605 presumably the end of an entry. Braces of type
3606 \path=TOKEN_LBRACE=%
3607 \TOKENINDEX{TOKEN_LBRACE}
3608 and \path=TOKEN_RBRACE=%
3609 \TOKENINDEX{TOKEN_RBRACE}
3610 do not
3611 occur except around apparent entries in the lexer
3612 output; other braces are returned as tokens of
3613 type \path=TOKEN_LITERAL=.%
3614 \TOKENINDEX{TOKEN_LITERAL}
3615
3616 No more than one token of lookahead is required by
3617 this grammar, although the lexer often looked
3618 several characters ahead to examine trailing
3619 context%
3620 \index{trailing context}
3621 in order to distinguish between otherwise
3622 similar tokens.
3623
3624 \BibTeX{} users should be able to read this
3625 grammar and decide whether a questionable
3626 \BibTeX{} construct is legal or not, without
3627 having to resort to software experiments as I did
3628 to clarify fuzzy grammatical points.
3629
3630 \section{Software availability}
3631
3632 The source code%
3633 \index{source code}
3634 and documentation%
3635 \index{documentation}
3636 for \BIBCLEAN{}
3637 are in the {\em public domain}, in the interests
3638 of the widest availability and greatest benefit to
3639 the \TeX{} community. Commercial vendors of
3640 \TeX{}ware are encouraged to include \BIBCLEAN{}
3641 with their distributions.
3642
3643 The distribution also includes the separate
3644 complete lexer and parser grammar and code, which
3645 can be processed by \PROGRAM{lex} or
3646 \PROGRAM{flex}, and \PROGRAM{yacc} or
3647 \PROGRAM{bison}, respectively. The output C code
3648 from these tools is included so that recipients
3649 need not have them installed to actually compile
3650 and run the lexer and parser.
3651
3652 If you have Internet anonymous%
3653 \index{anonymous ftp@anonymous {\tt ftp}}
3654 \PROGRAM{ftp} access,
3655 you can retrieve the distribution in a variety of
3656 archive formats from the machine
3657 \path=ftp.math.utah.edu=%
3658 \PATHINDEX{ftp.math.utah.edu}
3659 in the directory
3660 \path=pub/tex/bib=.%
3661 \PATHINDEX{pub/tex/bib}
3662 Major \TeX{} Internet archive hosts%
3663 \index{Internet archive hosts}%
3664 \index{archive hosts!Internet}
3665 around the world will also have \BIBCLEAN{},
3666 but the author's site will always have the most
3667 up-to-date version. If you lack \PROGRAM{ftp}
3668 capability but have electronic mail%
3669 \index{electronic mail server}
3670 access, a
3671 message to \[email protected]=%
3672 \PATHINDEX{tuglib\char64math.utah.edu}
3673 with the text
3674 %
3675 \begin{verbatim}
3676 help
3677 send index from tex/bib
3678 \end{verbatim}
3679 \TTINDEX{send}%
3680 \TTINDEX{help}%
3681 %
3682 will get you started.
3683
3684 The \BIBCLEAN{} distribution includes a
3685 substantial collection of torture tests%
3686 \index{testing}
3687 that
3688 should be run at installation time to verify
3689 correctness. As with the \TeX{} \PROGRAM{trip}
3690 and \MF{} \PROGRAM{trap} tests, this testing
3691 has proved valuable in uncovering problems
3692 before the code is installed for general
3693 use.
3694
3695 \bibliography{bibclean}
3696
3697 \index{command-line options|see{options}}%
3698 \index{concatenation|see{string}}%
3699 \index{editor|see{Emacs}}%
3700 \index{lexer|see{lexical analyzer}}%
3701 \index{macro|seealso{control sequence}}
3702 \index{run-time options|see{options}}%
3703 \index{text editor|see{Emacs}}%
3704 \index{token|see{terminal}}%
3705
3706 \printindex
3707
3708 \makesignature
3709
3710 \end{document}
3711
3712 %%% This is for GNU Emacs file-specific customization:
3713 %%% Local Variables:
3714 %%% fill-column: 50
3715 %%% abbrev-mode: t
3716 %%% eval: (define-abbrev LaTeX-mode-abbrev-table "bc" "\\BIBCLEAN{}" nil)
3717 %%% eval: (define-abbrev LaTeX-mode-abbrev-table "unix" "\\UNIX{}" nil)
3718 %%% eval: (define-abbrev LaTeX-mode-abbrev-table "scribe" "\\SCRIBE{}" nil)
3719 %%% eval: (local-set-key "_" (quote self-insert-command))
3720 %%% eval: (modify-syntax-entry ?\_ "w")
3721 %%% eval: (setq LaTeX-index-start-with-newline t)
3722 %%% eval: (setq LaTeX-index-end-with-newline t)
3723 %%% eval: (setq LaTeX-index-macro nil)
3724 %%% End: