Return to yacc.ms CVS log

Up to [Research Unix] / researchv10dc / vol2 / yacc

Annotation of researchv10dc/vol2/yacc/yacc.ms, revision 1.1

1.1     ! root        1: .so /n/pipe/usr/vol2/ADM/mac
        !             2: .XX yacc 347 "Yacc: A Parser Generator"
        !             3: .ds Y \f2Yacc\fP
        !             4: .ds y \f2yacc\fP
        !             5: .nr PI 4n
        !             6: .rn SH sH
        !             7: .de SH
        !             8: .SP 1.5
        !             9: .sH
        !            10: \\$1.  \\$2
        !            11: .PP
        !            12: .nr H5 0
        !            13: .nr H4 0
        !            14: .nr H3 0
        !            15: .nr H2 0
        !            16: .nr H1 \\$1
        !            17: ..
        !            18: .de SS
        !            19: .NH 2
        !            20: \\$1
        !            21: .PP
        !            22: ..
        !            23: .de Q{
        !            24: .in +20p
        !            25: .X{ \\$1
        !            26: ..
        !            27: .de P{
        !            28: .Q{ \\$1
        !            29: .tr _\(ru
        !            30: .ft CW
        !            31: .lg 0
        !            32: ..
        !            33: .de Q}
        !            34: .X} \\$1
        !            35: .in -20p
        !            36: ..
        !            37: .de P}
        !            38: .lg
        !            39: .Q} \\$1
        !            40: ..
        !            41: .de X{
        !            42: .KS
        !            43: .lg 0
        !            44: .ie \\n(.$ .SP \\$1
        !            45: .el .SP .5
        !            46: .nf
        !            47: .ft 1
        !            48: .nr t 20p
        !            49: .ta \\ntu +\\ntu +\\ntu +\\ntu +\\ntu +\\ntu +\\ntu +\\ntu +\\ntu +\\ntu +\\ntu +\\ntu +\\ntu +\\ntu +\\ntu
        !            50: ..
        !            51: .de X}
        !            52: .ft 1
        !            53: .fi
        !            54: .lg
        !            55: .ie \\n(.$ .SP \\$1
        !            56: .el .SP .5
        !            57: .KE
        !            58: ..
        !            59: .de FI
        !            60: .LP
        !            61: .DS B
        !            62: .fi
        !            63: .nr PS 9
        !            64: .ps 9
        !            65: \\f3Figure \\$1\\$2.\\f1
        !            66: ..
        !            67: .\"            EF - end figure
        !            68: .de EF
        !            69: .DE
        !            70: .fi
        !            71: .nr PS 10
        !            72: .ps 10
        !            73: .if \\n(.$ .SP \\$1
        !            74: .if !\\n(.$ .SP
        !            75: .LP
        !            76: ..
        !            77: .PS
        !            78:        arrowht = .08; arrowwid = .04   # default values are .1 and .05
        !            79:        vs = 1/6                        # 1/6 = 12p; for vertical distances
        !            80:        pagewid = 6; fillval = .98
        !            81: 
        !            82:        # ln --         line to $1, $2 chop elliptically
        !            83:        #               chopw and choph are the chop ellipse width and height
        !            84:        define ln %
        !            85:         {      [
        !            86:                        x = $1*hu; y = $2*vu
        !            87:                        xsq = x*x
        !            88:                        rsq = xsq + y*y; r = sqrt(rsq);
        !            89:                        asq = chopw*chopw/4;
        !            90:                        bsq = choph*choph/4
        !            91:                        esq = (asq - bsq)/asq
        !            92:                        p = sqrt(bsq/(1-esq*(xsq/rsq)))/r;
        !            93: 
        !            94:                O:      ""
        !            95:                B:      O + p*x, p*y
        !            96:                E:      O + (1-p)*x, (1-p)*y
        !            97:                P:      O + x,y
        !            98:                line $3 from B to E
        !            99:                ] with .O at Here
        !           100:        }
        !           101:        move to Here + $1*hu, $2*vu
        !           102:        %
        !           103:        # usage: adirection([e|n|w|s], [right|up|...], [1|0|1|0], Object)
        !           104:        define adirection %
        !           105:                axdir = $3
        !           106:                move to $4
        !           107:                $2
        !           108:        %
        !           109:        define aright % adirection(e, right, 1, $1) %
        !           110:        define aleft  % adirection(w, left,  1, $1) %
        !           111:        define anup   % adirection(n, up,    0, $1) %
        !           112:        define adown  % adirection(s, down,  0, $1) %
        !           113:        define anell %
        !           114:                ax = $1.x - Here.x; ay = $1.y - Here.y
        !           115:        Anell:  Here + ax,ay
        !           116:                if axdir then|
        !           117:                        line $3 from Here to Here + ax,0 chop 0 chop arcrad
        !           118:                        if ax*ay > 0 then@ arc @else@ arc cw @
        !           119:                        axdir = 0
        !           120:                |else|
        !           121:                        line $3 from Here to Here + 0,ay chop 0 chop arcrad
        !           122:                        if ax*ay < 0 then@ arc @else@ arc cw @
        !           123:                        axdir = 1
        !           124:                |
        !           125:                line $2 to Anell
        !           126:        % axdir = 1
        !           127: .PE
        !           128: .fp 8 SS S
        !           129: .ds BU \f8\(bu\fP
        !           130: .EQ
        !           131: define Small   % size 7 "$1" %
        !           132: define f2      % "\&" font 2 "$1" %
        !           133: define cdot    % "\s7\f8\N'183'\fP\s0" %
        !           134: define =>      % "\v'-.15m'\f8\N'222'\fP\v'.15m'" %
        !           135: define C++     % "\f1C\h'-.14m'+\h'-.18'+\fP" %
        !           136: define <!      % "\f8\N'225'\fP" %
        !           137: define >!      % "\f8\N'241'\fP" %
        !           138: delim $$
        !           139: .EN
        !           140: .ND "July 1, 1989"
        !           141: .TL
        !           142: Yacc: A Parser Generator\(dg
        !           143: .AU
        !           144: Stephen C. Johnson
        !           145: Ravi Sethi
        !           146: .AI
        !           147: .MH
        !           148: .AB
        !           149: .PP
        !           150: Since the early 1970s, \*y has been used to implement
        !           151: hundreds of languages, big and small.
        !           152: Its applications range from small desk calculators,
        !           153: to medium-sized preprocessors for typesetting,
        !           154: to large compiler front ends for complete programming languages.
        !           155: .PP
        !           156: A \*y specification is based on a collection of grammar rules
        !           157: that describe the syntax of a language; \*y turns the
        !           158: specification into a syntax analyzer.
        !           159: A pure syntax analyzer merely checks whether or not an input string
        !           160: conforms to the syntax of the language.
        !           161: .PP
        !           162: We can go beyond pure syntax analysis by attaching code in C
        !           163: or $C++$ to
        !           164: a grammar rule; such code is called an action, and is executed
        !           165: whenever the rule is applied during syntax analysis.
        !           166: Thus, a desk calculator might use actions to evaluate an expression,
        !           167: and a compiler front end might use actions to
        !           168: emit intermediate code.
        !           169: .PP
        !           170: \*Y allows us to build parsers from LALR(1) grammars
        !           171: without necessarily learning the underlying theory.
        !           172: .AE
        !           173: .@tag SH _SH1_
        !           174: .FS
        !           175: \(dg Prepared by R. Sethi from\&|reference(v7yacc)\&.
        !           176: S. C. Johnson is presently with Ardent Computer,
        !           177: 880 West Maude Ave.,
        !           178: Sunnyvale, California 94086.
        !           179: .FE
        !           180: .SH _SH1_  "Introduction"
        !           181: .LP
        !           182: \*Y is a tool for building syntax analyzers, also known as
        !           183: .I parsers .
        !           184: This section introduces the basic features of \*y.
        !           185: We review grammars, build a pure parser
        !           186: for real numbers, and then augment the parser to evaluate
        !           187: numbers during parsing.
        !           188: The language of real numbers is a toy;
        !           189: realistic examples appear in Section _SH2_.
        !           190: .PP
        !           191: Uppercase letters are distinct from lowercase letters
        !           192: in \*y specifications.
        !           193: Thus,
        !           194: .CW digit
        !           195: and
        !           196: .CW DIGIT
        !           197: are distinct names.
        !           198: The font of a name is chosen purely for readability, so
        !           199: .CW fraction ,
        !           200: and $fraction$ (within diagrams)
        !           201: refer to the same name.
        !           202: .SS "Further Reading"
        !           203: \*Y is designed to handle a single but significant part
        !           204: of the total job of building a translator or interpreter
        !           205: for a language.
        !           206: The remaining parts of the job must be implemented
        !           207: in a host programming language,
        !           208: presumed to be C|reference(Kernighan Ritchie 1988) or
        !           209: $C++$|reference(Stroustrup book 1986).
        !           210: .PP
        !           211: \f2Lex\fP|reference(latest lex), a tool for
        !           212: building lexical analyzers, works in harmony with \*y.
        !           213: It can be easily used to produce quite complicated lexical analyzers,
        !           214: but there remain some languages (Fortran, for example) whose lexical analyzers
        !           215: must be crafted by hand.
        !           216: .PP
        !           217: Kernighan and Pike|reference(Kernighan Pike) illustrate program development
        !           218: using \*y and \f2lex\fP by gradually extending an expression evaluator
        !           219: into an interpreter for a language comparable to Basic.
        !           220: Schreiner and Friedman|reference(Schreiner Friedman) conduct a book-length case
        !           221: study of how to create a compiler using \*y and \f2lex\fP.
        !           222: .PP
        !           223: Textbooks on compilers such as
        !           224: \&|reference(Aho Sethi Ullman 1986)\&
        !           225: provide more information on the behavior and
        !           226: construction of parsers than will be covered here.
        !           227: The algorithms underlying \*y are also discussed in a survey
        !           228: of LR parsing
        !           229: \&|reference(Aho Johnson surveys)\&.
        !           230: A feature that sets \*y apart \(em its ability to build fast compact
        !           231: LR parsers from ambiguous grammars \(em is based on the theory
        !           232: developed in
        !           233: \&|reference(Aho Johnson Ullman ambiguous)\&.
        !           234: .PP
        !           235: Among the earliest applications of \*y are
        !           236: .I eqn |reference(Kernighan Cherry 1975),
        !           237: a language for typesetting mathematics, and
        !           238: .I pcc ,
        !           239: the Portable C Compiler|reference(Johnson portable acm).
        !           240: .......
        !           241: .SS "Grammars, Reviewed"
        !           242: The
        !           243: .I syntax
        !           244: of a language imposes a hierarchical structure,
        !           245: called a
        !           246: .I "parse tree" ,
        !           247: on strings in the language.
        !           248: The following is a parse tree for the string
        !           249: .CW 3.14
        !           250: in a language of real numbers:
        !           251: .KS
        !           252: .ps 9
        !           253: .ft CW
        !           254: .PS
        !           255: [
        !           256:        hu = .5; vu = 1.5*vs; choph = vs; chopw = .7
        !           257:        boxht = vs; boxwid = .8*vs
        !           258: 
        !           259:        "$realNumber$"
        !           260:         {
        !           261:                ln(-1,-1); "$integerPart$"
        !           262:                ln( 0,-1); "$digit$"
        !           263:                ln( 0,-2); "3"
        !           264:        }{
        !           265:                ln( 0,-4); "."
        !           266:        }{
        !           267:                ln( 1.5,-1); "$fraction$"
        !           268:                 {
        !           269:                        ln(-0.5,-1); "$digit$"
        !           270:                        ln( 0,-2); "1"
        !           271:                }{
        !           272:                        ln( 0.5,-1); "$fraction$"
        !           273:                        ln( 0,-1); "$digit$"
        !           274:                        ln( 0,-1); "4"
        !           275:                }
        !           276:        }
        !           277: ]
        !           278: .PE
        !           279: .KE
        !           280: .PP
        !           281: The leaves at the bottom of a parse tree are labeled with
        !           282: .I terminals
        !           283: or
        !           284: .I tokens ;
        !           285: tokens represent themselves.
        !           286: By contrast, the other nodes of a parse tree are labeled with
        !           287: .I nonterminals .
        !           288: Each node in the parse tree is based on a rule,
        !           289: called a
        !           290: .I production ,
        !           291: that defines a nonterminal in terms of a sequence of
        !           292: terminals and nonterminals.
        !           293: The root of the parse tree for
        !           294: .CW 3.14
        !           295: is based on the
        !           296: following informally stated production:
        !           297: .Q{
        !           298: A real number consists of an integer part, a point, and a fraction.
        !           299: .Q}
        !           300: This production is written as follows in the notation accepted by \*y:
        !           301: .P{
        !           302: realNumber :  integerPart '.' fraction
        !           303:            ;
        !           304: .P}
        !           305: .PP
        !           306: Together, the tokens, the nonterminals, the productions, and a
        !           307: distinguished nonterminal, called the
        !           308: .I "start symbol" ,
        !           309: constitute a
        !           310: .I grammar
        !           311: for a language.
        !           312: Both tokens and nonterminals are referred to as
        !           313: .I "grammar symbols" ,
        !           314: or simply
        !           315: .I symbols .
        !           316: .SS "Grammars in Yacc Specifications"
        !           317: The three sections of a \*y specification are
        !           318: for optional declarations, productions,
        !           319: and optional user-supplied routines.
        !           320: The productions are the heart of a specification;
        !           321: they comprise all but the first two and last two
        !           322: lines of Figure _FI1_.
        !           323: The sections are separated by
        !           324: double percent
        !           325: .CW %%
        !           326: marks \(em the percent symbol
        !           327: is generally used by \*y as an escape character.
        !           328: If the user-routines section is omitted, the second
        !           329: .CW %%
        !           330: mark can be omitted as well.
        !           331: .KF
        !           332: .ps 9
        !           333: .nf
        !           334: \s5\l'\n(LLu\&\(ul'\s0
        !           335: .fi
        !           336: .P{
        !           337: %start lines
        !           338: %%
        !           339: lines       : /* empty */
        !           340:             | lines realNumber '\en'
        !           341:             ;
        !           342: realNumber  : integerPart '.' fraction
        !           343:             ;
        !           344: integerPart : digit
        !           345:             | integerPart digit
        !           346:             ;
        !           347: fraction    : digit
        !           348:             | digit fraction
        !           349:             ;
        !           350: digit       : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
        !           351:             ;
        !           352: %%
        !           353: int  yylex() { return getchar(); }
        !           354: .P}
        !           355: .@tag FI _FI1_
        !           356: .FI _FI1_
        !           357: A complete \*y specification for sequences of real numbers, one per line.
        !           358: .EF 0
        !           359: .nf
        !           360: \s5\l'\n(LLu\&\(ul'\s0
        !           361: .fi
        !           362: .SP
        !           363: .KE
        !           364: .PP
        !           365: Blanks, tabs, and newlines are ignored.
        !           366: Comments can appear wherever a name can; they are enclosed
        !           367: between
        !           368: .CW /*
        !           369: and
        !           370: .CW */ ,
        !           371: as in C.
        !           372: .PP
        !           373: It is possible, and desirable, for the start symbol of a grammar
        !           374: to be declared explicitly, using the
        !           375: .CW %start
        !           376: keyword, as in
        !           377: .P{
        !           378: %start lines
        !           379: .P}
        !           380: Otherwise, the start symbol is taken from the first production in the
        !           381: specification.
        !           382: .PP
        !           383: A name in the production section is presumed to represent a nonterminal
        !           384: unless it is explicitly declared to represent a token.
        !           385: There are no token declarations in Figure _FI1_.
        !           386: The following declaration of token
        !           387: .CW DIGIT
        !           388: is from an example later in this section.
        !           389: .P{
        !           390: %token DIGIT
        !           391: .P}
        !           392: .PP
        !           393: Single-character tokens need not be declared; a
        !           394: .I literal
        !           395: is a character enclosed in single quotes.
        !           396: As in C, the backslash
        !           397: .CW \e
        !           398: is an escape character within literals, and the following C escapes are
        !           399: recognized:
        !           400: .ft CW
        !           401: .TS
        !           402: lw4 0 l l.
        !           403:        '\en'   \f1newline\fP
        !           404:        '\er'   \f1return\fP
        !           405:        '\e''   \f1single quote \fP'\f1\fP
        !           406:        '\et'   \f1tab\fP
        !           407:        '\eb'   \f1backspace\fP
        !           408:        '\ef'   \f1form feed\fP
        !           409:        '\e$xxx$'       $xxx$\f1 in octal\fP
        !           410: .TE
        !           411: .ft 1
        !           412: For technical reasons, the
        !           413: .CW NUL
        !           414: character,
        !           415: .CW '\e0'
        !           416: or
        !           417: .CW 0 ,
        !           418: should never be used in productions.
        !           419: .PP
        !           420: A production
        !           421: .P{
        !           422: realNumber :  integerPart '.' fraction
        !           423:            ;
        !           424: .P}
        !           425: defines a nonterminal, called its
        !           426: .I "left side" ,
        !           427: in terms of a sequence of grammar symbols, called its
        !           428: .I "right side" .
        !           429: A colon separates the two sides, and a semicolon marks the end
        !           430: of the production.
        !           431: The left side of this production is
        !           432: .CW realNumber .
        !           433: Its right side consists of
        !           434: .CW integerPart ,
        !           435: the literal
        !           436: .CW '.' ,
        !           437: and
        !           438: .CW fraction .
        !           439: .PP
        !           440: The right side of a production can be empty, as in the following
        !           441: production with no symbols between the colon and the
        !           442: terminating semicolon:
        !           443: .P{
        !           444: lines : ;
        !           445: .P}
        !           446: .PP
        !           447: Productions with the same left side can be combined, and written with
        !           448: a vertical bar separating the right sides.
        !           449: The productions
        !           450: .P{
        !           451: integerPart :  digit
        !           452:             ;
        !           453: integerPart :  integerPart digit
        !           454:             ;
        !           455: .P}
        !           456: can be rewritten equivalently as
        !           457: .P{
        !           458: integerPart :  digit
        !           459:             |  integerPart digit
        !           460:             ;
        !           461: .P}
        !           462: In words, an integer part is either a single digit or a
        !           463: (smaller) integer part followed by a digit.
        !           464: Thus,
        !           465: an integer part consists of
        !           466: a string of one or more digits.
        !           467: .PP
        !           468: A fraction also consists of a string of one or more digits,
        !           469: described by the productions
        !           470: .P{
        !           471: fraction :  digit
        !           472:          |  digit fraction
        !           473:          ;
        !           474: .P}
        !           475: The nonterminals
        !           476: .CW integerPart
        !           477: and
        !           478: .CW fraction
        !           479: impose different hierarchical structures on strings of digits.
        !           480: Note how a tree for
        !           481: .CW integerPart
        !           482: grows down to the left, whereas a tree for
        !           483: .CW fraction
        !           484: grows down to the right:
        !           485: .KS
        !           486: .ps 9
        !           487: .ft CW
        !           488: .PS
        !           489: [
        !           490:        hu = .5; vu = 1.5*vs; choph = vs; chopw = .7
        !           491:        boxht = vs
        !           492: 
        !           493: IntegerPart:\
        !           494:        [
        !           495:                "$integerPart$"
        !           496:                {
        !           497:                        ln( 1,-1); "$digit$"
        !           498:                        ln( 0,-1); "3"
        !           499:                }
        !           500:                ln(-1,-1); "$integerPart$"
        !           501:                {
        !           502:                        ln( 1,-1); "$digit$"
        !           503:                        ln( 0,-1); "2"
        !           504:                }
        !           505:                ln(-1,-1); "$integerPart$"
        !           506:                {
        !           507:                        ln( 0,-1); "$digit$"
        !           508:                        ln( 0,-1); "1"
        !           509:                }{
        !           510:                        box invis wid .8 at Here
        !           511:                }
        !           512:        ]
        !           513: Fraction:\
        !           514:        [
        !           515:                "$fraction$"
        !           516:                {
        !           517:                        ln(-1,-1); "$digit$"
        !           518:                        ln( 0,-1); "7"
        !           519:                }
        !           520:                ln( 1,-1); "$fraction$"
        !           521:                {
        !           522:                        ln(-1,-1); "$digit$"
        !           523:                        ln( 0,-1); "8"
        !           524:                }
        !           525:                ln( 1,-1); "$fraction$"
        !           526:                {
        !           527:                        ln( 0,-1); "$digit$"
        !           528:                        ln( 0,-1); "9"
        !           529:                }{
        !           530:                        box invis wid .6 at Here
        !           531:                }
        !           532:        ] with .e at IntegerPart.w + pagewid-2*20/72,0
        !           533: ]
        !           534: .PE
        !           535: .KE
        !           536: .LP
        !           537: Semantic considerations influence the choice of hierarchical
        !           538: structure, and hence the choice of productions for a nonterminal,
        !           539: as we shall see in Section _SH2_.
        !           540: .SS "Using Yacc"
        !           541: When \*y is applied to a specification, the output
        !           542: is a file of C code, called
        !           543: .CW y.tab.c
        !           544: (the name might differ due to local file-system conventions).
        !           545: Suppose that the specification in Figure _FI1_ appears in a file
        !           546: .CW real.y .
        !           547: A program for reading a sequence of real numbers can then be
        !           548: compiled into a file
        !           549: .CW a.out
        !           550: by the following
        !           551: .UX
        !           552: system commands:
        !           553: .ft CW
        !           554: .TS
        !           555: lw4 0 l8 l.
        !           556:        yacc real.y     \f2generates C code into file \&\fPy.tab.c
        !           557:        cc y.tab.c -ly  \f2compiles executable program into file \&\fPa.out
        !           558: .TE
        !           559: .LP
        !           560: The flag
        !           561: .CW -ly ,
        !           562: which must appear after
        !           563: .CW y.tab.c ,
        !           564: refers to a tiny library,
        !           565: described below.
        !           566: .PP
        !           567: Figure _FI2_ illustrates the use of \*y.
        !           568: \*Y and the C compiler are represented by dashed boxes
        !           569: since they are used once, at ``compiler-construction time.''
        !           570: The constructed compiler, consists of the lexical analyzer,
        !           571: the syntax analyzer, and any user routines.
        !           572: .KF
        !           573: .nf
        !           574: \s5\l'\n(LLu\&\(ul'\s0
        !           575: .fi
        !           576: .nr PS 9
        !           577: .ps 9
        !           578: .vs 11
        !           579: .PS
        !           580: [
        !           581:        fillval = 1
        !           582:        boxht = 2.5*vs; boxwid = .6
        !           583:        lineht = vs; linewid = .25
        !           584: 
        !           585:        right
        !           586:        box invis "character" "stream" wid .7
        !           587:        line ->
        !           588:        box "lexical" "analyzer" fill
        !           589:        line ->
        !           590:        box invis "token" "stream"
        !           591:        line ->
        !           592:        box "syntax" "analyzer" fill
        !           593:        {
        !           594:                move to last box.n
        !           595:                up
        !           596:                line <-
        !           597:                box "C" "compiler" dashed
        !           598:                line <-
        !           599:                box "\*y" dashed
        !           600:                line <-
        !           601:                box invis ht 1.5*vs "grammar"
        !           602:        }
        !           603:        line ->
        !           604:        box invis "optional" "output"
        !           605: ]
        !           606: .PE
        !           607: .@tag FI _FI2_
        !           608: .FI _FI2_
        !           609: \*Y handles the syntax analysis part of an application.
        !           610: .EF 0
        !           611: .nf
        !           612: \s5\l'\n(LLu\&\(ul'\s0
        !           613: .fi
        !           614: .SP
        !           615: .KE
        !           616: .PP
        !           617: \*Y confines itself to building fast parsers.
        !           618: All other aspects of an application, such as initialization,
        !           619: lexical analysis, and error reporting, must be programmed
        !           620: separately.
        !           621: Some relevant function names in the C code are as follows:
        !           622: .SP .5
        !           623: .IP \*(BU
        !           624: .CW yyparse
        !           625: is the parser generated by \*y.
        !           626: It returns 0 if the entire input
        !           627: is parsed successfully; otherwise it returns 1.
        !           628: .SP .5
        !           629: .IP \*(BU
        !           630: .CW yylex
        !           631: is called repeatedly by
        !           632: .CW yyparse ;
        !           633: it reads input characters and returns tokens.
        !           634: A routine that groups characters into tokens is
        !           635: called a
        !           636: .I "lexical analyzer" .
        !           637: The lexical analyzer at the bottom of Figure _FI1_
        !           638: .P{ .25
        !           639: int yylex() { return getchar(); }
        !           640: .P} .25
        !           641: simply returns each individual character
        !           642: as a token.
        !           643: .SP
        !           644: .IP \*(BU
        !           645: .CW main
        !           646: is the start-up routine.
        !           647: Execution of a C program begins in a function called
        !           648: .CW main .
        !           649: In general,
        !           650: .CW main
        !           651: might read command-line arguments and options and perform initialization
        !           652: before calling
        !           653: .CW yyparse .
        !           654: .SP .5
        !           655: .IP \*(BU
        !           656: .CW yyerror
        !           657: is called by
        !           658: .CW yyparse
        !           659: if an error occurs during parsing, usually with the terse message
        !           660: .CW "syntax error" .'' ``
        !           661: Parsing terminates when an error is detected unless ``error productions''
        !           662: are used as described in Section _SH5_.
        !           663: .LP
        !           664: The library
        !           665: .CW -ly
        !           666: contains default versions of
        !           667: .CW main
        !           668: and
        !           669: .CW yyerror :
        !           670: .P{
        !           671: int main() { return yyparse(); }
        !           672: #include <stdio.h>
        !           673: void yyerror(s) char *s; { fprintf(stderr, "%s\en", s); }
        !           674: .P}
        !           675: This version of
        !           676: .CW main
        !           677: simply returns the result obtained from
        !           678: .CW yyparse ,
        !           679: and this version of
        !           680: .CW yyerror
        !           681: simply prints the message it is called with.
        !           682: .PP
        !           683: In case the
        !           684: .CW -ly
        !           685: library is not available, the specification in Figure _FI1_
        !           686: can be completed by adding these three lines at the bottom.
        !           687: .EQ
        !           688: delim off
        !           689: .EN
        !           690: .SS "Actions and Attributes"
        !           691: Actions attached to a production are
        !           692: executed each time the production is applied during parsing.
        !           693: An
        !           694: .I action
        !           695: consists of one or more C statements, enclosed in curly braces
        !           696: .CW {
        !           697: and
        !           698: .CW } .
        !           699: Within an action, pseudo-variables starting with
        !           700: .CW $
        !           701: signs refer to values associated with the symbols in the production.
        !           702: Such values are called
        !           703: .I attributes .
        !           704: The pseudo-variable for the left side is
        !           705: .CW $$ .
        !           706: In the local version of \*y,
        !           707: the pseudo-variable for a symbol on the right side
        !           708: is formed by prefixing a
        !           709: .CW $
        !           710: sign to either its name or its position.
        !           711: .PP
        !           712: The complete specification in Figure _FI3_ includes
        !           713: the production and action
        !           714: .P{
        !           715: realNumber : integerPart fraction { $$ = $integerPart + $fraction; } ;
        !           716: .P}
        !           717: The action is the single statement
        !           718: .P{
        !           719: $$ = $integerPart + $fraction;
        !           720: .P}
        !           721: .EQ
        !           722: delim @@
        !           723: .EN
        !           724: It defines the attribute value associated with
        !           725: the left side to be the sum of the
        !           726: attribute values associated with
        !           727: the two symbols on the right side.@"" sup _FS1_@
        !           728: .FS
        !           729: .@tag FS _FS1_
        !           730: @"" sup _FS1_@
        !           731: When the same symbol @s@ appears several times on the right side,
        !           732: its pseudo-variable can be written as
        !           733: .CW $@s@#1 ,
        !           734: .CW $@s@#2 ,
        !           735: .CW $@s@#3 .
        !           736: .FE
        !           737: .KF
        !           738: .ps 9
        !           739: .nf
        !           740: \s5\l'\n(LLu\&\(ul'\s0
        !           741: .P{
        !           742: %token DIGIT
        !           743: %start lines
        !           744: %{
        !           745: #def\&ine YYSTYPE double
        !           746: %}
        !           747: %%
        !           748: lines       : /* empty */
        !           749:             | lines realNumber '\en'
        !           750:                 { printf("%g\en", $realNumber); }
        !           751:             ;
        !           752: realNumber  : integerPart '.' fraction
        !           753:                 { $$ = $integerPart + $fraction; }
        !           754:             ;
        !           755: integerPart : DIGIT
        !           756:             | integerPart DIGIT
        !           757:                 { $$ = $integerPart*10 + $DIGIT; }
        !           758:             ;
        !           759: fraction    : DIGIT
        !           760:                 { $$ = $DIGIT*0.1; }
        !           761:             | DIGIT fraction
        !           762:                 { $$ = ($DIGIT + $fraction)*0.1; }
        !           763:             ;
        !           764: %%
        !           765: #include <ctype.h>
        !           766: int  yylex()   {
        !           767:     int c;
        !           768:     c = getchar();
        !           769:     if( ! isdigit(c) ) return c;
        !           770:     yylval = c - '0';
        !           771:     return DIGIT;
        !           772: }
        !           773: .P}
        !           774: .@tag FI _FI3_
        !           775: .FI _FI3_
        !           776: The actions in this \*y specification evaluate real numbers during parsing.
        !           777: .EF 0
        !           778: .nf
        !           779: \s5\l'\n(LLu\&\(ul'\s0
        !           780: .fi
        !           781: .SP
        !           782: .KE
        !           783: .PP
        !           784: All versions of \*y support pseudo-variables like
        !           785: .CW $1
        !           786: and
        !           787: .CW $2
        !           788: formed from positions on the right side.
        !           789: Using positions, this action can be rewritten equivalently as
        !           790: .EQ
        !           791: delim off
        !           792: .EN
        !           793: .P{
        !           794: realNumber :  integerPart fraction  { $$ = $1 + $2; }  ;
        !           795: .P}
        !           796: .PP
        !           797: The
        !           798: .CW $ -prefix
        !           799: notation permits one attribute per grammar symbol.
        !           800: By default, all attributes have the same type,
        !           801: .CW int .
        !           802: This default can be changed by defining
        !           803: .CW YYSTYPE ,
        !           804: as on line 4 of Figure _FI3_, where
        !           805: .CW YYSTYPE
        !           806: is defined to be
        !           807: .CW double
        !           808: because the specification deals with real numbers.
        !           809: See Section _SH6_ for how to customize the types of attributes;
        !           810: that is, to allow different attributes to have different types.
        !           811: (As in Figure _FI3_,
        !           812: any C code in the declarations section must be enclosed between
        !           813: .CW %{
        !           814: and
        !           815: .CW %} .)
        !           816: .PP
        !           817: Attributes for tokens are computed by the lexical analyzer.
        !           818: Conceptually, a lexical analyzer returns a pair, consisting
        !           819: of a token and an associated attribute value.
        !           820: Consider, for example, the token
        !           821: .CW DIGIT
        !           822: in Figure _FI3_.
        !           823: When the lexical analyzer reads the character
        !           824: .CW 1
        !           825: it returns
        !           826: .CW DIGIT
        !           827: with attribute value 1, when it reads
        !           828: .CW 2
        !           829: it returns
        !           830: .CW DIGIT
        !           831: with attribute value 2, and so on.
        !           832: .PP
        !           833: Specifically, the parser
        !           834: .CW yyparse
        !           835: expects the lexical analyzer
        !           836: .CW yylex
        !           837: to leave the attribute value in a global variable
        !           838: .CW yylval ,
        !           839: which is automatically declared by \*y to have type
        !           840: .CW YYSTYPE .
        !           841: The function
        !           842: .CW yylex
        !           843: in Figure _FI3_ assigns a value to
        !           844: .CW yylval
        !           845: just before it returns the token
        !           846: .CW DIGIT .
        !           847: .PP
        !           848: The tree in Figure _FI4_ illustrates the evaluation of the real number
        !           849: .CW 321.789 .
        !           850: Starting in the bottom-left corner of the figure,
        !           851: the lexical analyzer sets the attribute value 3 at the
        !           852: leftmost leaf for the token
        !           853: .CW DIGIT .
        !           854: The parent of this leaf is based on the production and action
        !           855: .KF
        !           856: .EQ
        !           857: delim $$
        !           858: .EN
        !           859: .nf
        !           860: \s5\l'\n(LLu\&\(ul'\s0
        !           861: .fi
        !           862: .ps 9
        !           863: .PS
        !           864: [
        !           865:        define intp % {
        !           866:                "$f2($integerPart)^=^$1$"
        !           867:        } %
        !           868:        define frac % {
        !           869:                "$f2($fraction)^=^$1$"
        !           870:        } %
        !           871:        define DIGIT % {
        !           872:                "$Small($DIGIT)^=^$1$"
        !           873:        } %
        !           874: 
        !           875:        hu = .6; vu = 2.5*vs; choph = vs; chopw = .7
        !           876:        boxht = vs
        !           877: 
        !           878:        "$f2($realNumber)^=^321.789$"
        !           879:        {
        !           880:                ln(-2,-1); intp(321)
        !           881:                {
        !           882:                        ln( 1,-1); DIGIT(1)
        !           883:                }
        !           884:                ln(-1,-1); intp(32)
        !           885:                {
        !           886:                        ln( 1,-1); DIGIT(2)
        !           887:                }
        !           888:                ln(-1,-1); intp(3)
        !           889:                {
        !           890:                        ln( 0,-1); DIGIT(3)
        !           891:                }{
        !           892:                        box invis wid .85 at Here
        !           893:                }
        !           894:        }{
        !           895:                ln( 2,-1); frac(0.789)
        !           896:                {
        !           897:                        ln(-1,-1); DIGIT(7)
        !           898:                }
        !           899:                ln( 1,-1); frac(0.89)
        !           900:                {
        !           901:                        ln(-1,-1); DIGIT(8)
        !           902:                }
        !           903:                ln( 1,-1); frac(0.9)
        !           904:                {
        !           905:                        ln( 0,-1); DIGIT(9)
        !           906:                }{
        !           907:                        box invis wid .8 at Here
        !           908:                }
        !           909:        }
        !           910: ]
        !           911: .PE
        !           912: .@tag FI _FI4_
        !           913: .FI _FI4_
        !           914: Attribute values during the evaluation of
        !           915: .CW 321.789 .
        !           916: .EF 0
        !           917: .nf
        !           918: \s5\l'\n(LLu\&\(ul'\s0
        !           919: .fi
        !           920: .SP
        !           921: .EQ
        !           922: delim off
        !           923: .EN
        !           924: .KE
        !           925: .P{
        !           926: integerPart :  DIGIT  { $$ = $1; }  ;
        !           927: .P}
        !           928: This action is omitted from the specification
        !           929: in Figure _FI3_ because, by default,
        !           930: the parser sets
        !           931: .CW $$ ,
        !           932: the attribute of the left side, to
        !           933: .CW $1 ,
        !           934: the attribute of the
        !           935: first symbol on the right side.
        !           936: .PP
        !           937: Working up the tree, the next node is based on
        !           938: .P{
        !           939: integerPart : integerPart DIGIT { $$ = $integerPart*10 + $DIGIT; } ;
        !           940: .P}
        !           941: .PP
        !           942: The effect of the actions is perhaps easier to see at the nodes
        !           943: for
        !           944: .CW fraction .
        !           945: At the only node based on
        !           946: .P{
        !           947: fraction :  DIGIT  { $$ = $DIGIT*0.1; }  ;
        !           948: .P}
        !           949: the value of
        !           950: .CW $DIGIT
        !           951: is 9 and the value of
        !           952: .CW $fraction
        !           953: is 0.9.
        !           954: .PP
        !           955: The attributes at the nodes in
        !           956: Figure _FI4_ are said to be synthesized because they
        !           957: are defined solely in terms of the attributes at the
        !           958: children of the node.
        !           959: Since \*y generates bottom-up parsers, bottom-up evaluation of
        !           960: synthesized attributes fits naturally with parsing.
        !           961: Actions can also be used to simulate some ``inherited attributes,'' which
        !           962: are context dependent.
        !           963: .PP
        !           964: Actions attached to productions are examined further in Section _SH2_;
        !           965: their execution order becomes significant when
        !           966: they do input/output, assign values to variables, call functions
        !           967: with side effects, or otherwise affect the state of a computation.
        !           968: .SS "A Style for Specifications"
        !           969: As in any language, choose a style that makes the code
        !           970: easy to read, preferably a
        !           971: consistent (and accepted) style that can be read by others.
        !           972: The main concern in a \*y specification is to make
        !           973: the productions visible through the morass of action code.
        !           974: .PP
        !           975: The following style hints owe much to Brian Kernighan:
        !           976: .SP .5
        !           977: .IP \*(BU 4
        !           978: Use all capital letters for token names, all lower case letters for
        !           979: nonterminal names.
        !           980: This hint comes under the heading of ``knowing who to blame when
        !           981: things go wrong.''
        !           982: .SP .25
        !           983: .IP \*(BU
        !           984: Put productions and actions on separate lines.
        !           985: Either can then be changed independently.
        !           986: .SP .25
        !           987: .IP \*(BU
        !           988: Put all productions with the same left side together.
        !           989: Put the left side in only once, and let all
        !           990: following productions begin with a vertical bar.
        !           991: .SP .25
        !           992: .IP \*(BU
        !           993: Put a semicolon only after the last production with a given left side,
        !           994: and put the semicolon on a separate line.
        !           995: New productions can then be easily added.
        !           996: .SP .25
        !           997: .IP \*(BU
        !           998: Indent production bodies by one tab stop, and action bodies by two
        !           999: tab stops.
        !          1000: .PP
        !          1001: The examples in this paper sometimes
        !          1002: deviate from this style to conserve space.
        !          1003: .EQ
        !          1004: delim $$
        !          1005: .EN
        !          1006: .@tag SH _SH2_
        !          1007: .SH _SH2_  "Evaluation And Translation Of Expressions"
        !          1008: Both actions and productions must be considered
        !          1009: when a \*y specification is designed.
        !          1010: Without actions, a parser would silently analyze input strings,
        !          1011: complaining only if it detects an error.
        !          1012: With suitable actions, a parser can become an evaluator or
        !          1013: a translator.
        !          1014: Typically, the desired actions
        !          1015: influence the choice of productions.
        !          1016: .PP
        !          1017: For example, the actions for evaluating the integer and fractional
        !          1018: parts of a real number motivate different productions for
        !          1019: the sequences of digits
        !          1020: represented by
        !          1021: .CW integerPart
        !          1022: and
        !          1023: .CW fraction
        !          1024: in Section _SH1_.
        !          1025: In the integer part, the contribution of a digit depends on the
        !          1026: number of digits to its right; the contribution of
        !          1027: .CW 3
        !          1028: in
        !          1029: .CW 321.789
        !          1030: is 300, where the number of zeros depends on the number of
        !          1031: digits to its right.
        !          1032: In the fractional part, however, the contribution of a digit
        !          1033: depends on the number of digits to its left; the contribution
        !          1034: of
        !          1035: .CW 9
        !          1036: in
        !          1037: .CW 321.789
        !          1038: is 0.009, where the number of zeros depends on the number of
        !          1039: digits to its left.
        !          1040: .PP
        !          1041: Arithmetic expressions are a fertile source of examples for \*y
        !          1042: because the specifications of expression evaluators and translators are
        !          1043: quite short, and the ideas carry over to richer languages.
        !          1044: This section begins with a specification for an
        !          1045: expression evaluator.
        !          1046: The evaluator benefits from \*y's facilities for
        !          1047: specifying the associativity and precedence of operators
        !          1048: within expressions.
        !          1049: The next example, a translator from infix into postfix notation,
        !          1050: illustrates parsing order.
        !          1051: .SS "Grammars for Expressions"
        !          1052: Expressions are characterized by the operators within them;
        !          1053: the choice of productions for expressions
        !          1054: depends on the associativity and precedence of operators.
        !          1055: .PP
        !          1056: An operator
        !          1057: .CW OP
        !          1058: is
        !          1059: .I "left associative"
        !          1060: if an expression
        !          1061: .P{
        !          1062: expr$"" sub 1$ OP expr$"" sub 2$ OP expr$"" sub 3$
        !          1063: .P}
        !          1064: is evaluated as if it were parenthesized as
        !          1065: .P{
        !          1066: (expr$"" sub 1$ OP expr$"" sub 2$) OP expr$"" sub 3$
        !          1067: .P}
        !          1068: Similarly, the operator is
        !          1069: .I "right associative"
        !          1070: if the expression is evaluated as if it were parenthesized as
        !          1071: .P{
        !          1072: expr$"" sub 1$ OP (expr$"" sub 2$ OP expr$"" sub 3$)
        !          1073: .P}
        !          1074: .PP
        !          1075: An operator
        !          1076: .CW OPA
        !          1077: has
        !          1078: .I "lower precedence"
        !          1079: than an operator
        !          1080: .CW OPB
        !          1081: if the following equivalences hold (that is, the expressions to the
        !          1082: left and right of the $==$ signs have the same values):
        !          1083: .ft CW
        !          1084: .TS
        !          1085: lw4 0 r2 c2 l.
        !          1086:        expr$"" sub 1$ OPA expr$"" sub 2$ OPB expr$"" sub 3$    $==$    expr$"" sub 1$ OPA (expr$"" sub 2$ OPB expr$"" sub 3$)
        !          1087:        expr$"" sub 1$ OPB expr$"" sub 2$ OPA expr$"" sub 3$    $==$    (expr$"" sub 1$ OPB expr$"" sub 2$) OPA expr$"" sub 3$
        !          1088: .TE
        !          1089: .PP
        !          1090: The traditional grammar for arithmetic expressions uses three nonterminals
        !          1091: .CW expr ,
        !          1092: .CW term ,
        !          1093: and
        !          1094: .CW factor ,
        !          1095: where
        !          1096: .CW expr
        !          1097: represents an expression and
        !          1098: .CW term
        !          1099: and
        !          1100: .CW factor
        !          1101: represent subexpressions.
        !          1102: Tokens
        !          1103: .CW NUMBER
        !          1104: and
        !          1105: .CW VAR
        !          1106: represent numbers and variables.
        !          1107: The grammar is
        !          1108: .P{
        !          1109: %token NUMBER VAR
        !          1110: %%
        !          1111: expr   :  expr '+' term  |  expr '-' term  |  term
        !          1112:        ;
        !          1113: term   :  term '*' factor  |  term '/' factor  |  factor
        !          1114:        ;
        !          1115: factor :  NUMBER  |  VAR  |  '(' expr ')'
        !          1116:        ;
        !          1117: .P}
        !          1118: In words, an expression is a sequence of terms separated
        !          1119: by
        !          1120: .CW +
        !          1121: or
        !          1122: .CW -
        !          1123: signs.
        !          1124: A term is a sequence of factors separated by
        !          1125: .CW *
        !          1126: or
        !          1127: .CW /
        !          1128: signs.
        !          1129: Thus,
        !          1130: .P{
        !          1131: b*b - 4*a*c
        !          1132: .P}
        !          1133: is an expression containing two terms
        !          1134: .CW b*b
        !          1135: and
        !          1136: .CW 4*a*c .
        !          1137: The term
        !          1138: .CW 4*a*c
        !          1139: has three factors
        !          1140: .CW 4 ,
        !          1141: .CW a ,
        !          1142: and
        !          1143: .CW c .
        !          1144: A factor is either a number, a variable, or a parenthesized expression.
        !          1145: .PP
        !          1146: The grammar for expressions
        !          1147: dates back to Backus's introduction of BNF\&|reference(Backus 1960)\&,
        !          1148: a notation for writing grammars.
        !          1149: .PP
        !          1150: A desk calculator can be based on this grammar
        !          1151: by adding actions, as in
        !          1152: .EQ
        !          1153: delim off
        !          1154: .EN
        !          1155: .P{
        !          1156: expr :  expr '-' term  { $$ = $expr - $term; } ;
        !          1157: .P}
        !          1158: .EQ
        !          1159: delim $$
        !          1160: .EN
        !          1161: This production and action respect the left associativity of
        !          1162: the minus operator, and correctly evaluate
        !          1163: .CW 7-1-2
        !          1164: to 4 \(em check it by drawing a parse tree.
        !          1165: .PP
        !          1166: The traditional grammar generalizes to operators at $n^>=^1$ precedence levels;
        !          1167: all operators at the same level have the same associativity and precedence.
        !          1168: Set up a nonterminal
        !          1169: .CW expr$"" sub i$
        !          1170: for precedence level $i$, with level $1$ being the lowest.
        !          1171: In the traditional grammar, the nonterminals
        !          1172: .CW expr ,
        !          1173: .CW term ,
        !          1174: and
        !          1175: .CW factor
        !          1176: correspond to
        !          1177: .CW expr$"" sub 1$ ,
        !          1178: .CW expr$"" sub 2$ ,
        !          1179: and
        !          1180: .CW expr$"" sub 3$ ,
        !          1181: respectively.
        !          1182: If the operators at level $i^<^n$ are left associative,
        !          1183: then the productions for
        !          1184: .CW expr$"" sub i$
        !          1185: have the form
        !          1186: .P{
        !          1187: expr$"" sub i$ :  expr$"" sub i$ OP expr$"" sub i+1$  ;
        !          1188: .P}
        !          1189: Here,
        !          1190: .CW OP
        !          1191: represents an operator at level $i$.
        !          1192: Otherwise, if the operators at level $i$ are right associative,
        !          1193: then the productions have the form
        !          1194: .P{
        !          1195: expr$"" sub i$ :  expr$"" sub i+1$ OP expr$"" sub i$  ;
        !          1196: .P}
        !          1197: .PP
        !          1198: At each precedence level $i^<^n$, there is an additional production of the
        !          1199: form
        !          1200: .P{
        !          1201: expr$"" sub i$ :  expr$"" sub i+1$  ;
        !          1202: .P}
        !          1203: .SS "Associativity and Precedence Declarations"
        !          1204: \*Y has special facilities for declaring the associativity and
        !          1205: precedence of operators, which will be introduced by considering the
        !          1206: specification in Figure _FI5_.
        !          1207: .KF
        !          1208: .EQ
        !          1209: delim off
        !          1210: .EN
        !          1211: .nf
        !          1212: \s5\l'\n(LLu\&\(ul'\s0
        !          1213: .fi
        !          1214: .ps 9
        !          1215: .P{
        !          1216: %{
        !          1217: #def\&ine YYSTYPE double
        !          1218: %}
        !          1219: %token NUMBER
        !          1220: %left '+' '-'
        !          1221: %left '*' '/'
        !          1222: %right '^'
        !          1223: %left UMINUS
        !          1224: %%
        !          1225: lines :  lines expr '\en'        { printf("%g\en", $expr); }
        !          1226:       |  lines '\en'
        !          1227:       |  /* empty */
        !          1228:       ;
        !          1229: expr  :  expr '+' expr          { $$ = $1 + $3; }
        !          1230:       |  expr '-' expr          { $$ = $1 - $3; }
        !          1231:       |  expr '*' expr          { $$ = $1 * $3; }
        !          1232:       |  expr '/' expr          { $$ = $1 / $3; }
        !          1233:       |  expr '^' expr          { $$ = pow($1, $3); }
        !          1234:       |  '-' expr %prec UMINUS  { $$ = - $expr; }
        !          1235:       |  '(' expr ')'           { $$ = $expr; }
        !          1236:       |  NUMBER
        !          1237:       ;
        !          1238: .P}
        !          1239: .@tag FI _FI5_
        !          1240: .FI _FI5_
        !          1241: An expression evaluator based on precedence declarations for tokens.
        !          1242: .EF 0
        !          1243: .nf
        !          1244: \s5\l'\n(LLu\&\(ul'\s0
        !          1245: .fi
        !          1246: .SP
        !          1247: .EQ
        !          1248: delim $$
        !          1249: .EN
        !          1250: .KE
        !          1251: .PP
        !          1252: The tokens of the evaluator in Figure _FI5_ are
        !          1253: parentheses,
        !          1254: .CW NUMBER ,
        !          1255: and the operators
        !          1256: .P{
        !          1257: \&'+' '-' '*' '/' '^' UMINUS
        !          1258: .P}
        !          1259: (Ignore
        !          1260: .CW UMINUS
        !          1261: for the moment.)
        !          1262: .PP
        !          1263: The associativity and precedence of tokens are declared on
        !          1264: lines beginning with one of the keywords
        !          1265: .CW %left ,
        !          1266: .CW %right ,
        !          1267: or
        !          1268: .CW %nonassoc .
        !          1269: All of the tokens on a line have the same associativity and
        !          1270: precedence; they have lower precedence than the tokens on successive lines.
        !          1271: These declarations will be referred to as
        !          1272: .I precedence
        !          1273: declarations.
        !          1274: .PP
        !          1275: (The keyword
        !          1276: .CW %nonassoc
        !          1277: describes operators that do not associate with themselves;
        !          1278: for example,
        !          1279: .P{
        !          1280: A .LT. B .LT. C
        !          1281: .P}
        !          1282: is illegal in Fortran because
        !          1283: .CW .LT.
        !          1284: is nonassociative.)
        !          1285: .PP
        !          1286: The precedence declarations
        !          1287: .P{
        !          1288: %left  '+' '-'
        !          1289: %left  '*' '/'
        !          1290: %right '^'
        !          1291: .P}
        !          1292: specify that
        !          1293: .CW +
        !          1294: and
        !          1295: .CW -
        !          1296: are left associative and have lower
        !          1297: precedence than the left-associative operators
        !          1298: .CW *
        !          1299: and
        !          1300: .CW / ,
        !          1301: which in turn have lower precedence than the right-associative operator
        !          1302: .CW ^ .
        !          1303: .PP
        !          1304: The operator
        !          1305: .CW ^
        !          1306: in the grammar
        !          1307: represents exponentiation, as in
        !          1308: .CW 2^3 ,
        !          1309: which evaluates to 8.
        !          1310: This operator is right associative;
        !          1311: thus,
        !          1312: .CW 2^2^3
        !          1313: is equivalent to
        !          1314: .CW 2^(2^3) ,
        !          1315: .CW 2^8 ,
        !          1316: and
        !          1317: .CW 256 .
        !          1318: .PP
        !          1319: The nonterminals of the grammar are
        !          1320: .CW lines
        !          1321: and
        !          1322: .CW expr .
        !          1323: The grammar expects a sequence of expressions, on separate lines.
        !          1324: A typical production for
        !          1325: .CW expr
        !          1326: has the form
        !          1327: .EQ
        !          1328: delim off
        !          1329: .EN
        !          1330: .P{
        !          1331: expr :  expr '+' expr   { $$ = $1 + $3; }
        !          1332: .P}
        !          1333: Alternatively, we can write the action as
        !          1334: .P{
        !          1335: expr :  expr '+' expr   { $$ = $expr#1 + $expr#2; }
        !          1336: .P}
        !          1337: .EQ
        !          1338: delim $$
        !          1339: .EN
        !          1340: .PP
        !          1341: With these precedence declarations, the expression
        !          1342: .P{
        !          1343: 2 ^ 2 ^ 3 * 4 - 5 * 6 - 7 * 8
        !          1344: .P}
        !          1345: is evaluated as if it were parenthesized as
        !          1346: .P{
        !          1347: ( (2^(2^3))*4  -  5*6 )  -  7*8
        !          1348: .P}
        !          1349: .PP
        !          1350: The user routines for the evaluator are in Figure _FI6_.
        !          1351: The lexical analyzer
        !          1352: .CW yylex
        !          1353: returns a token each time it is called.
        !          1354: It skips blanks.
        !          1355: If it sees a digit or a decimal point, it
        !          1356: returns the token
        !          1357: .CW NUMBER
        !          1358: after using the
        !          1359: C library function
        !          1360: .CW scanf
        !          1361: to read a number into the global variable
        !          1362: .CW yylval
        !          1363: (as mentioned in Section 1, the attribute value, if any,
        !          1364: associated with a token
        !          1365: must be left in
        !          1366: .CW yylval ).
        !          1367: Otherwise, the lexical analyzer returns a single character as a token.
        !          1368: .KF
        !          1369: .EQ
        !          1370: delim off
        !          1371: .EN
        !          1372: .nf
        !          1373: \s5\l'\n(LLu\&\(ul'\s0
        !          1374: .fi
        !          1375: .ps 9
        !          1376: .P{
        !          1377: %%
        !          1378: #include <stdio.h>
        !          1379: #include <ctype.h>
        !          1380: #include <math.h>
        !          1381: int yylex() {
        !          1382:        int c;
        !          1383:        while ( ( c = getchar() ) == ' ' );
        !          1384:        if ( (c == '.') || (isdigit(c)) ) {
        !          1385:                ungetc(c, stdin);
        !          1386:                scanf("%lf", &yylval);
        !          1387:                return NUMBER;
        !          1388:        }
        !          1389:        return c;
        !          1390: }
        !          1391: .P}
        !          1392: .@tag FI _FI6_
        !          1393: .FI _FI6_
        !          1394: User routines for the evaluator in Figure _FI5_.
        !          1395: .EF 0
        !          1396: .nf
        !          1397: \s5\l'\n(LLu\&\(ul'\s0
        !          1398: .fi
        !          1399: .SP
        !          1400: .EQ
        !          1401: delim $$
        !          1402: .EN
        !          1403: .KE
        !          1404: .PP
        !          1405: The parser uses precedence declarations to decide when to apply a production.
        !          1406: Suppose that the input has the form
        !          1407: .P{
        !          1408: expr * expr \&\f1$...$\fP
        !          1409: .P}
        !          1410: and the parser has to decide whether or not to apply the
        !          1411: multiplication production
        !          1412: .P{
        !          1413: expr :  expr '*' expr
        !          1414: .P}
        !          1415: If the next symbol in the input is
        !          1416: .CW + ,
        !          1417: as in
        !          1418: .P{
        !          1419: expr * expr  + \&\f1$...$\fP
        !          1420: .P}
        !          1421: the parser applies the multiplication production because the
        !          1422: token
        !          1423: .CW +
        !          1424: has lower precedence than
        !          1425: .CW * .
        !          1426: However, if the next symbol in the input is
        !          1427: .CW ^ ,
        !          1428: the parser defers the multiplication production because
        !          1429: .CW ^
        !          1430: has higher precedence than
        !          1431: .CW * .
        !          1432: .PP
        !          1433: The treatment of the unary minus operator deserves special mention.
        !          1434: The evaluator in Figure _FI5_ accepts the expression
        !          1435: .CW 10^-1
        !          1436: in lieu of $10 sup -1~==~0.1$.
        !          1437: In other words,
        !          1438: .CW 10^-1
        !          1439: is treated like
        !          1440: .CW 10^(-1) ,
        !          1441: with unary minus having higher precedence than
        !          1442: .CW ^ .
        !          1443: The precedence of the minus operator therefore depends on whether it
        !          1444: is used as a binary or as a unary operator.
        !          1445: .PP
        !          1446: .PP
        !          1447: \*Y provides the keyword
        !          1448: .CW %prec
        !          1449: for overriding the declared precedence of a token.
        !          1450: A
        !          1451: .CW %left
        !          1452: declaration in Figure _FI5_ gives
        !          1453: .CW -
        !          1454: the lowest precedence, along with
        !          1455: .CW + .
        !          1456: The keyword
        !          1457: .CW %prec
        !          1458: in
        !          1459: .P{
        !          1460: expr :  '-' expr  %prec UMINUS
        !          1461: .P}
        !          1462: overrides the declared precedence of
        !          1463: .CW - .
        !          1464: When this production is applied, the high precedence of token
        !          1465: .CW UMINUS
        !          1466: is used instead.
        !          1467: The expression
        !          1468: .CW 3-10^-1
        !          1469: is therefore equivalent to
        !          1470: .CW 3-(10^(-1)) .
        !          1471: .PP
        !          1472: When several tokens appear in a production, the parser
        !          1473: normally uses the precedence of the last token on the right
        !          1474: side to decide whether to apply a production.
        !          1475: The
        !          1476: .CW %prec
        !          1477: keyword overrides this normal behavior.
        !          1478: For example, the
        !          1479: .CW %prec
        !          1480: in
        !          1481: .P{
        !          1482: expr :  '(' TYPENAME ')' expr   %prec TYPENAME
        !          1483: .P}
        !          1484: is necessary for the production to take the precedence of
        !          1485: token
        !          1486: .CW TYPENAME ;
        !          1487: otherwise the production takes its precedence from the
        !          1488: closing parenthesis.
        !          1489: .PP
        !          1490: It is recommended that precedence declarations
        !          1491: be used in a ``cookbook'' fashion, until some experience is gained.
        !          1492: How \*y uses precedence declarations is examined further in
        !          1493: Section _SH4_.
        !          1494: .SS "Execution Order for Actions"
        !          1495: The execution order of actions is significant because actions can
        !          1496: have side effects.
        !          1497: One way to visualize the order is to imagine a traversal of
        !          1498: a parse tree in which the children of each node
        !          1499: are visited depth-first from left to right, starting at the root.
        !          1500: Suppose a node has two children $c$ and $d$, with $c$ to the left of $d$.
        !          1501: .I Depth-first
        !          1502: implies that all the nodes in the subtree for $c$
        !          1503: are visited before any nodes are visited in the subtree for $d$.
        !          1504: The tree in Figure _FI7_ includes actions as pseudo-symbols,
        !          1505: attached by dashed lines.
        !          1506: Actions are executed in the order they would be visited
        !          1507: in a depth-first left-to-right traversal.
        !          1508: .KF
        !          1509: .EQ
        !          1510: define Small % size 7 "$1" %
        !          1511: .EN
        !          1512: .nf
        !          1513: \s5\l'\n(LLu\&\(ul'\s0
        !          1514: .fi
        !          1515: .nr PS 9
        !          1516: .ps 9
        !          1517: .PS
        !          1518: [
        !          1519:        define NUM % {
        !          1520:                "$Small(NUM)$"
        !          1521:                "$Small($NUM)^=^$1$" at Here + 0,-vs
        !          1522:        } %
        !          1523: 
        !          1524:        hu = .3; vu = vs; choph = vs; chopw = .7
        !          1525:        boxht = vs
        !          1526: 
        !          1527:        "$expr$"
        !          1528:         {
        !          1529:                ln(-5,-3); "$expr$"
        !          1530: G1:""
        !          1531:                 {      ln(-2,-2); NUM(2)
        !          1532: G2:""
        !          1533:                }{      ln( 1,-2, dashed .04); "{print $Small($NUM)$}"
        !          1534: G3:""
        !          1535:                }
        !          1536:        }{
        !          1537:                ln(-1,-3); "+"
        !          1538:        }{
        !          1539:                ln( 2,-3); "$expr$"
        !          1540:                 {
        !          1541:                        ln(-3,-4); "$expr$"
        !          1542:                         {      ln(-2,-2); NUM(3)
        !          1543: G4:                            ""
        !          1544:                        }{      ln( 1,-2, dashed .04); "{print $Small($NUM)$}"
        !          1545:                        }
        !          1546:                }{
        !          1547:                        ln(-.5,-4); "\(**"
        !          1548:                }{
        !          1549:                        ln( 2.5,-4); "$expr$"
        !          1550:                         {      ln(-2,-4); NUM(5)
        !          1551:                        }{      ln( 1,-4, dashed .04); "{print $Small($NUM)$}"
        !          1552:                        }
        !          1553:                }{
        !          1554:                        ln( 5,-4, dashed .04);  "{print \(**}"
        !          1555:                        box invis wid .6 ht vs at Here
        !          1556:                }
        !          1557:        }{
        !          1558:                ln( 6,-3, dashed .04);  "{print +}"
        !          1559:        }
        !          1560: 
        !          1561: H1:    G1 + -3*hu,0
        !          1562: H2:    G2 + -5*hu,-3*vu
        !          1563: H3:    G2.x, H2.y
        !          1564: .ps 36
        !          1565:        spline -> from H1 to H2 to H3
        !          1566: .ps\n(PS
        !          1567: ]
        !          1568: .PE
        !          1569: .@tag FI _FI7_
        !          1570: .FI _FI7_
        !          1571: Actions are executed in a depth-first left-to-right order.
        !          1572: .EF 0
        !          1573: .nf
        !          1574: \s5\l'\n(LLu\&\(ul'\s0
        !          1575: .fi
        !          1576: .SP
        !          1577: .KE
        !          1578: .PP
        !          1579: The parse tree in Figure _FI7_
        !          1580: is based on the following specification of an
        !          1581: infix-to-postfix translator:
        !          1582: .EQ
        !          1583: delim off
        !          1584: .EN
        !          1585: .P{
        !          1586: %token NUM
        !          1587: %left  '+'
        !          1588: %left  '*'
        !          1589: %%
        !          1590: expr : expr '+' expr    { printf(" +"); }
        !          1591:      | expr '*' expr    { printf(" *"); }
        !          1592:      | '(' expr ')'
        !          1593:      | NUM              { printf(" %d", $NUM); }
        !          1594:      ;
        !          1595: .P}
        !          1596: .EQ
        !          1597: delim $$
        !          1598: .EN
        !          1599: The translation is emitted incrementally during parsing, so
        !          1600: the execution order of the print statements is critical.
        !          1601: The translation of
        !          1602: .CW 2+3*5
        !          1603: is
        !          1604: .P{
        !          1605:  2 3 5 * +
        !          1606: .P}
        !          1607: .SS "Actions Embedded Within Rules"
        !          1608: \*Y permits an action to be written in the middle of a production
        !          1609: as well as at the end; actions in the middle are called
        !          1610: .I embedded
        !          1611: actions.
        !          1612: .PP
        !          1613: Embedded actions are useful for keeping track of context information.
        !          1614: For example, consider the typeset text ``$E sub 1$'', specified by
        !          1615: the
        !          1616: .I eqn
        !          1617: input
        !          1618: .P{
        !          1619: E sub 1
        !          1620: .P}
        !          1621: The smaller point size of 1, relative to that of $E$,
        !          1622: is dictated by the context;
        !          1623: specifically, by the preceding keyword
        !          1624: .CW sub .
        !          1625: The
        !          1626: .I eqn
        !          1627: grammar uses embedded actions to maintain
        !          1628: the current point size in variable
        !          1629: .CW ps .
        !          1630: The embedded action
        !          1631: .CW ps$^$-=$^$del
        !          1632: in
        !          1633: .P{
        !          1634: box :  box  { ps -= del; }  SUB  box  { ps += del; }
        !          1635: .P}
        !          1636: reduces the point size before a subscript
        !          1637: is processed; the other action
        !          1638: .CW ps$^$+=$^$del
        !          1639: restores the point size.
        !          1640: Nonterminal
        !          1641: .CW box
        !          1642: represents an
        !          1643: .I eqn
        !          1644: construct, and token
        !          1645: .CW SUB
        !          1646: represents the input characters
        !          1647: .CW sub .
        !          1648: .PP
        !          1649: Each embedded action is implemented by manufacturing a fresh
        !          1650: nonterminal, called a
        !          1651: .I marker
        !          1652: nonterminal.
        !          1653: \*Y actually treats this
        !          1654: .I eqn
        !          1655: example as if it had been
        !          1656: written:
        !          1657: .EQ
        !          1658: delim @@
        !          1659: .EN
        !          1660: .P{
        !          1661: box  :  box  _ACT  SUB  box
        !          1662:             { ps += del; }
        !          1663:      ;
        !          1664: $ACT :  /* empty */
        !          1665:             { ps -= del; }
        !          1666:      ;
        !          1667: .P}
        !          1668: The fresh marker nonterminal
        !          1669: .CW _ACT
        !          1670: marks the position of the embedded action
        !          1671: .CW ps@^@-=@^@del .
        !          1672: .PP
        !          1673: Within an embedded action,
        !          1674: .CW $$
        !          1675: refers to the attribute value of its marker nonterminal.
        !          1676: Thus, the two occurrences of
        !          1677: .CW $$
        !          1678: in
        !          1679: .P{
        !          1680: a : b  { $$ = 1; }  c  { x = $2; $$ = $c; } ;
        !          1681: .P}
        !          1682: refer to different nonterminals, shown explicitly in
        !          1683: .P{
        !          1684: a    :  b  _ACT  c   { x = $2; $$ = $c; } ;
        !          1685: _ACT :  /* empty */  { $$ = 1; } ;
        !          1686: .P}
        !          1687: In words, the effect of
        !          1688: .P{
        !          1689: a : b  { $$ = 1; }  c  { x = $2; $$ = $c; } ;
        !          1690: .P}
        !          1691: is to make 1 the attribute value of the implicit
        !          1692: marker nonterminal in position 2,
        !          1693: assign 1 to variable
        !          1694: .CW x ,
        !          1695: and make
        !          1696: .CW $c
        !          1697: the attribute value of the left side
        !          1698: .CW a .
        !          1699: .PP
        !          1700: Note that
        !          1701: .CW c
        !          1702: is at position 3, so the above production can be
        !          1703: rewritten using
        !          1704: .CW $3
        !          1705: instead of
        !          1706: .CW $c :
        !          1707: .P{
        !          1708: a : b  { $$ = 1; }  c  { x = $2; $$ = $3; }
        !          1709: .P}
        !          1710: .EQ
        !          1711: delim $$
        !          1712: .EN
        !          1713: .@tag SH _SH3_
        !          1714: .SH _SH3_  "How The Parser Works"
        !          1715: The algorithm used to go from
        !          1716: a grammar to a parser is complex
        !          1717: and will not be discussed here,
        !          1718: but the parser itself is relatively simple.
        !          1719: Its two main actions are
        !          1720: .SP .5
        !          1721: .IP \*(BU 4
        !          1722: shift to the next input symbol and
        !          1723: .IP \*(BU 4
        !          1724: reduce by applying a production.
        !          1725: .SP .5
        !          1726: .LP
        !          1727: Some familiarity with such actions is
        !          1728: helpful in deciphering messages about
        !          1729: ``shift/reduce'' and ``reduce/reduce''
        !          1730: conflicts, which warn of potential ambiguities in
        !          1731: the grammar that could lead the parser astray.
        !          1732: .PP
        !          1733: \*Y places a human-readable description of the generated parser
        !          1734: into a file
        !          1735: .CW y.output ,
        !          1736: when it is invoked with the
        !          1737: .CW -v
        !          1738: (for verbose) option.
        !          1739: This section deals with the parsing background behind
        !          1740: .CW y.output
        !          1741: files; parsing conflicts themselves are considered in Section _SH4_.
        !          1742: .PP
        !          1743: The running example in this section is the following grammar for
        !          1744: real numbers:
        !          1745: .P{
        !          1746: %token D P
        !          1747: %%
        !          1748: real :  intp P frac    ;
        !          1749: intp :  D  |  intp D   ;
        !          1750: frac :  D  |  D frac   ;
        !          1751: .P}
        !          1752: The abbreviated names
        !          1753: .CW intp
        !          1754: for integer part,
        !          1755: .CW frac
        !          1756: for fraction,
        !          1757: and
        !          1758: .CW D
        !          1759: for digit, conserve space in diagrams.
        !          1760: The use of token
        !          1761: .CW P
        !          1762: for a decimal point
        !          1763: .CW '.'
        !          1764: avoids confusion with other uses of dots within
        !          1765: .CW y.output
        !          1766: files.
        !          1767: .SS "Shift-Reduce Parsing"
        !          1768: A
        !          1769: .I "bottom-up"
        !          1770: parser works from the leaves (bottom) of a parse tree towards the
        !          1771: root.
        !          1772: The following sequence of tree snapshots illustrates a bottom-up
        !          1773: parse of the token stream
        !          1774: .CW DDPDD ,
        !          1775: corresponding to the real number
        !          1776: .CW 21.89 .
        !          1777: For the moment, the digit represented by a token
        !          1778: .CW D
        !          1779: appears below the token.
        !          1780: The trees are
        !          1781: .KS
        !          1782: .ps 9
        !          1783: .PS
        !          1784: [
        !          1785:        define D % {
        !          1786:                "\f2\s8D\s0\fP"
        !          1787:                "\s6$1\s0" at Here + 0,-.5*vs
        !          1788:        } %
        !          1789:        define Pt % {
        !          1790:                "\f2\s8P\s0\fP"
        !          1791:                "." at Here + 0,-.5*vs
        !          1792:        } %
        !          1793: 
        !          1794:        hu = .125; vu = 1.5*vs; choph = vs; chopw = .4
        !          1795:        boxht = vs; boxwid = .8*vs; movewid = .5
        !          1796: 
        !          1797: S1:    [
        !          1798:                # "$real$"
        !          1799:                 {
        !          1800:                        ln(-1,-1, invis); # "$intp$"
        !          1801:                         {
        !          1802:                                ln(-1,-1, invis); # "$intp$"
        !          1803:                                ln( 0,-1, invis); D(2)
        !          1804:                        }{
        !          1805:                                ln( 0,-2, invis); D(1)
        !          1806:                        }
        !          1807:                }{
        !          1808:                        ln( 0,-3, invis); Pt
        !          1809:                }{
        !          1810:                        ln( 1,-1, invis); # "$frac$"
        !          1811:                         {
        !          1812:                                ln( 0,-2, invis); D(8)
        !          1813:                        }{
        !          1814:                                ln( 1,-1, invis); # "$frac$"
        !          1815:                                ln( 0,-1, invis); D(9)
        !          1816:                        }
        !          1817:                }
        !          1818:        ]
        !          1819:        move
        !          1820: S2:    [
        !          1821:                # "$real$"
        !          1822:                 {
        !          1823:                        ln(-1,-1, invis); # "$intp$"
        !          1824:                         {
        !          1825:                                ln(-1,-1, invis); "$intp$"
        !          1826:                                ln( 0,-1); D(2)
        !          1827:                        }{
        !          1828:                                ln( 0,-2, invis); D(1)
        !          1829:                        }
        !          1830:                }{
        !          1831:                        ln( 0,-3, invis); Pt
        !          1832:                }{
        !          1833:                        ln( 1,-1, invis); # "$~~frac$"
        !          1834:                         {
        !          1835:                                ln( 0,-2, invis); D(8)
        !          1836:                        }{
        !          1837:                                ln( 1,-1, invis); # "$frac$"
        !          1838:                                ln( 0,-1, invis); D(9)
        !          1839:                        }
        !          1840:                }
        !          1841:        ]
        !          1842:        move
        !          1843: S3:    [
        !          1844:                # "$real$"
        !          1845:                 {
        !          1846:                        ln(-1,-1, invis); "$intp~$"
        !          1847:                         {
        !          1848:                                ln(-1,-1); "$intp$"
        !          1849:                                ln( 0,-1); D(2)
        !          1850:                        }{
        !          1851:                                ln( 0,-2); D(1)
        !          1852:                        }
        !          1853:                }{
        !          1854:                        ln( 0,-3, invis); Pt
        !          1855:                }{
        !          1856:                        ln( 1,-1, invis); # "$~~frac$"
        !          1857:                         {
        !          1858:                                ln( 0,-2, invis); D(8)
        !          1859:                        }{
        !          1860:                                ln( 1,-1, invis); # "$frac$"
        !          1861:                                ln( 0,-1, invis); D(9)
        !          1862:                        }
        !          1863:                }
        !          1864:        ]
        !          1865:        move
        !          1866: S4:    [
        !          1867:                # "$real$"
        !          1868:                 {
        !          1869:                        ln(-1,-1, invis); "$intp~$"
        !          1870:                         {
        !          1871:                                ln(-1,-1); "$intp$"
        !          1872:                                ln( 0,-1); D(2)
        !          1873:                        }{
        !          1874:                                ln( 0,-2); D(1)
        !          1875:                        }
        !          1876:                }{
        !          1877:                        ln( 0,-3, invis); Pt
        !          1878:                }{
        !          1879:                        ln( 1,-1, invis); # "$frac$"
        !          1880:                         {
        !          1881:                                ln( 0,-2, invis); D(8)
        !          1882:                        }{
        !          1883:                                ln( 1,-1, invis); "$frac$"
        !          1884:                                ln( 0,-1); D(9)
        !          1885:                        }
        !          1886:                }
        !          1887:        ]
        !          1888:        move
        !          1889: S5:    [
        !          1890:                 # "$real$"
        !          1891:                 {
        !          1892:                        ln(-1,-1, invis); "$intp~~$"
        !          1893:                         {
        !          1894:                                ln(-1,-1); "$intp$"
        !          1895:                                ln( 0,-1); D(2)
        !          1896:                        }{
        !          1897:                                ln( 0,-2); D(1)
        !          1898:                        }
        !          1899:                }{
        !          1900:                        ln( 0,-3, invis); Pt
        !          1901:                }{
        !          1902:                        ln( 1,-1, invis); "$~~frac$"
        !          1903:                         {
        !          1904:                                ln( 0,-2); D(8)
        !          1905:                        }{
        !          1906:                                ln( 1,-1); "$frac$"
        !          1907:                                ln( 0,-1); D(9)
        !          1908:                        }
        !          1909:                }
        !          1910:        ]
        !          1911:        move
        !          1912: S6:    [
        !          1913:                "$real$"
        !          1914:                 {
        !          1915:                        ln(-1,-1); "$intp~~$"
        !          1916:                         {
        !          1917:                                ln(-1,-1); "$intp$"
        !          1918:                                ln( 0,-1); D(2)
        !          1919:                        }{
        !          1920:                                ln( 0,-2); D(1)
        !          1921:                        }
        !          1922:                }{
        !          1923:                        ln( 0,-3); Pt
        !          1924:                }{
        !          1925:                        ln( 1,-1); "$~~frac$"
        !          1926:                         {
        !          1927:                                ln( 0,-2); D(8)
        !          1928:                        }{
        !          1929:                                ln( 1,-1); "$frac$"
        !          1930:                                ln( 0,-1); D(9)
        !          1931:                        }
        !          1932:                }
        !          1933:        ]
        !          1934: 
        !          1935:        "$=>$" at .5<S1.e, S2.w>
        !          1936:        "$=>$" at .5<S2.e, S3.w>
        !          1937:        "$=>$" at .5<S3.e, S4.w>
        !          1938:        "$=>$" at .5<S4.e, S5.w>
        !          1939:        "$=>$" at .5<S5.e, S6.w>
        !          1940: ]
        !          1941: .PE
        !          1942: .KE
        !          1943: .LP
        !          1944: Let us redraw these trees to line up their uncovered portions;
        !          1945: that is, the roots of the completed subtrees.
        !          1946: The redrawn sequence is
        !          1947: .KS
        !          1948: .ps 9
        !          1949: .PS
        !          1950: [
        !          1951:        define D % {
        !          1952:                "\f2\s8D\s0\fP"
        !          1953:        } %
        !          1954:        define Pt % {
        !          1955:                "\f2\s8P\s0\fP"
        !          1956:        #       "." at Here + 0,-.5*vs
        !          1957:        } %
        !          1958: 
        !          1959:        hu = .125; vu = 1.5*vs; choph = vs; chopw = .4
        !          1960:        boxht = vs; boxwid = .8*vs; movewid = hu; sep = .5
        !          1961: 
        !          1962: 
        !          1963: S1:    [ 
        !          1964:                D(1); move; D(2); move; Pt; move; D(8); move; D(9)
        !          1965:        ]
        !          1966: 
        !          1967: S2:    [
        !          1968:                {
        !          1969:                        "$intp~~$"; ln( 0,-1); D(1)
        !          1970:                }
        !          1971:                move
        !          1972:                D(2); move; Pt; move; D(8); move; D(9)
        !          1973:        ] with .nw at S1.ne + sep,0
        !          1974: 
        !          1975: S3:    [
        !          1976:                {
        !          1977:                        "$intp~~$"
        !          1978:                         {
        !          1979:                                ln(-1,-1); "$intp$"
        !          1980:                                ln( 0,-1); D(1)
        !          1981:                        }{
        !          1982:                                ln( 0,-2); D(2)
        !          1983:                        }
        !          1984:                }
        !          1985:                move
        !          1986:                Pt; move; D(8); move; D(9)
        !          1987:        ] with .nw at S2.ne + sep,0
        !          1988: 
        !          1989: S4:    [
        !          1990:                {
        !          1991:                        "$intp~~$"
        !          1992:                         {
        !          1993:                                ln(-1,-1); "$intp$"
        !          1994:                                ln( 0,-1); D(1)
        !          1995:                        }{
        !          1996:                                ln( 0,-2); D(2)
        !          1997:                        }
        !          1998:                }
        !          1999:                move
        !          2000:                Pt; move; D(8)
        !          2001:                move
        !          2002:                {
        !          2003:                        "$~~frac$"; ln( 0,-1); D(9)
        !          2004:                }
        !          2005:        ] with .nw at S3.ne + sep,0
        !          2006: 
        !          2007: S5:    [
        !          2008:                {
        !          2009:                        "$intp~~$"
        !          2010:                         {
        !          2011:                                ln(-1,-1); "$intp$"
        !          2012:                                ln( 0,-1); D(1)
        !          2013:                        }{
        !          2014:                                ln( 0,-2); D(2)
        !          2015:                        }
        !          2016:                }
        !          2017:                move
        !          2018:                Pt
        !          2019:                move
        !          2020:                {
        !          2021:                        "$~~frac$"
        !          2022:                         {
        !          2023:                                ln( 0,-2); D(8)
        !          2024:                        }{
        !          2025:                                ln( 1,-1); "$frac$"
        !          2026:                                ln( 0,-1); D(9)
        !          2027:                        }
        !          2028:                }
        !          2029:        ] with .nw at S4.ne + sep,0
        !          2030: 
        !          2031: S6:    [
        !          2032:                "$real$"
        !          2033:                 {
        !          2034:                        ln(-1,-1); "$intp~~$"
        !          2035:                         {
        !          2036:                                ln(-1,-1); "$intp$"
        !          2037:                                ln( 0,-1); D(1)
        !          2038:                        }{
        !          2039:                                ln( 0,-2); D(2)
        !          2040:                        }
        !          2041:                }{
        !          2042:                        ln( 0,-3); Pt
        !          2043:                }{
        !          2044:                        ln( 1,-1); "$~~frac$"
        !          2045:                         {
        !          2046:                                ln( 0,-2); D(8)
        !          2047:                        }{
        !          2048:                                ln( 1,-1); "$frac$"
        !          2049:                                ln( 0,-1); D(9)
        !          2050:                        }
        !          2051:                }
        !          2052:        ] with .nw at S5.ne + sep,0
        !          2053: 
        !          2054:        "$=>~$" at .5<S1.ne, S2.nw>
        !          2055:        "$=>$" at .5<S2.ne, S3.nw>
        !          2056:        "$=>$" at .5<S3.ne, S4.nw>
        !          2057:        "$~~=>$" at .5<S4.ne, S5.nw>
        !          2058:        "$=>$" at .5<S5.ne, S6.nw>
        !          2059: ]
        !          2060: .PE
        !          2061: .KE
        !          2062: .PP
        !          2063: The uncovered portions suffice, as long
        !          2064: as the grammar is unambiguous.
        !          2065: The real-number grammar is indeed unambiguous, so
        !          2066: the preceding sequence of partial trees is characterized
        !          2067: by the snapshots
        !          2068: .KS
        !          2069: .ps 9
        !          2070: .PS
        !          2071: [
        !          2072:        define N % box invis $1 wid .25 %
        !          2073:        define D % box invis "\f2\s8D\s0\fP" wid .125 %
        !          2074:        define P % box invis "\f2\s8P\s0\fP" wid .125 %
        !          2075:        define derives % box invis wid .4 "$=>$" %
        !          2076: 
        !          2077:        boxht = vs; boxwid = .8*vs
        !          2078: 
        !          2079: 
        !          2080:                [ D; D; P; D; D ]
        !          2081:        derives
        !          2082:                [ N("$intp$"); D; P; D; D ]
        !          2083:        derives
        !          2084:                [ N("$intp$"); P; D; D ]
        !          2085:        derives
        !          2086:                [ N("$intp$"); P; D; N("$frac$") ]
        !          2087:        derives
        !          2088:                [ N("$intp$"); P; N("$frac$") ]
        !          2089:        derives
        !          2090:                [ N("$real$") ]
        !          2091: ]
        !          2092: .PE
        !          2093: .KE
        !          2094: .PP
        !          2095: These snapshots correspond to a sequence of
        !          2096: reduce actions;
        !          2097: a
        !          2098: .I reduce
        !          2099: action replaces the right side of a production
        !          2100: by its left side.
        !          2101: A
        !          2102: .I shift
        !          2103: action advances the parser to the next unexamined input token;
        !          2104: such tokens are called
        !          2105: .I lookahead
        !          2106: symbols.
        !          2107: .EQ
        !          2108: delim off
        !          2109: .EN
        !          2110: .PP
        !          2111: The key problem of shift-reduce parsing is that of deciding
        !          2112: when to shift and when to reduce; \*y generates tables for
        !          2113: this purpose that are explained later in this section.
        !          2114: Meanwhile, an example of a shift-reduce parse
        !          2115: appears in Figure _FI8_.
        !          2116: The input token stream is again
        !          2117: .CW DDPDD ,
        !          2118: and a special token
        !          2119: .CW $end
        !          2120: marks its end.
        !          2121: In the figure, a pointer appears before the
        !          2122: current lookahead symbol.
        !          2123: The first action, a shift, advances the pointer past the
        !          2124: leftmost
        !          2125: .CW D :
        !          2126: .EQ
        !          2127: delim $$
        !          2128: .EN
        !          2129: .KF
        !          2130: .nf
        !          2131: \s5\l'\n(LLu\&\(ul'\s0
        !          2132: .fi
        !          2133: .ps 9
        !          2134: .PS
        !          2135: [
        !          2136:        define N % box invis $1 wid .25 %
        !          2137:        define D % box invis "\f2\s8D\s0\fP" wid .125 %
        !          2138:        define P % box invis "\f2\s8P\s0\fP" wid .125 %
        !          2139:        define E % box invis "$f2($end)$" wid .3 %
        !          2140:        define action % Act: [
        !          2141:                right
        !          2142:        B:      box invis wid actionwid
        !          2143:        PTR:    box invis wid .1
        !          2144:                $1 ljust at B.w
        !          2145:        ] with .PTR.n at S.PTR.s %
        !          2146:        define shift % action("shift") %
        !          2147:        define reduce % action("reduce") %
        !          2148:        define ptr %
        !          2149:                PTR: box invis wid .1; { move left .025; up; line <- }
        !          2150:        %
        !          2151:        define handle % { line from last box.sw to last box.se } %
        !          2152: 
        !          2153:        boxht = vs
        !          2154:        arrowht = .05; arrowwid = .025; lineht = .75*vs; dy = vs
        !          2155: 
        !          2156:        down
        !          2157: 
        !          2158:        actionwid = .9
        !          2159: T1:    S:[ right
        !          2160:                ptr; D; D; P; D; D; E
        !          2161:        ]
        !          2162:  shift
        !          2163:        S:[ right
        !          2164:                D; handle; ptr; D; P; D; D; E
        !          2165:        ] with .PTR.n at Act.PTR.s
        !          2166:  reduce
        !          2167:        S:[ right
        !          2168:                N("$intp$"); ptr; D; P; D; D; E
        !          2169:        ] with .PTR.n at Act.PTR.s
        !          2170:  shift
        !          2171:        S:[ right
        !          2172:                N("$intp$"); handle; D; handle; ptr; P; D; D; E
        !          2173:        ] with .PTR.n at Act.PTR.s
        !          2174:  reduce
        !          2175:        S:[ right
        !          2176:                N("$intp$"); ptr; P; D; D; E
        !          2177:        ] with .PTR.n at Act.PTR.s
        !          2178:  shift
        !          2179: B1:    S:[ right
        !          2180:                N("$intp$"); P; ptr; D; D; E
        !          2181:        ] with .PTR.n at Act.PTR.s
        !          2182: 
        !          2183: 
        !          2184: 
        !          2185:        actionwid = 1.2
        !          2186: T2:    S:[ right
        !          2187:                box invis wid actionwid
        !          2188:          PTR:  box invis wid .05
        !          2189:        ] with .sw at T1.se + 1.2,0
        !          2190:  shift
        !          2191:        S:[ right
        !          2192:                N("$intp$"); P; D; ptr; D; E
        !          2193:        ] with .PTR.n at Act.PTR.s
        !          2194:  shift
        !          2195:        S:[ right
        !          2196:                N("$intp$"); P; D; D; handle; ptr; E
        !          2197:        ] with .PTR.n at Act.PTR.s
        !          2198:  reduce
        !          2199:        S:[ right
        !          2200:                N("$intp$"); P; D; handle; N("$frac$"); handle; ptr; E
        !          2201:        ] with .PTR.n at Act.PTR.s
        !          2202:  reduce
        !          2203:        S:[ right
        !          2204:                N("$intp$"); handle; P; handle; N("$frac$"); handle; ptr; E
        !          2205:        ] with .PTR.n at Act.PTR.s
        !          2206:  reduce
        !          2207: B2:    S:[ right
        !          2208:                N("$real$"); ptr; E
        !          2209:        ] with .PTR.n at Act.PTR.s
        !          2210: 
        !          2211: G:     .5<T1.se, T2.sw> + 0,vs
        !          2212:        line from G to G.x, B2.s.y
        !          2213: ]
        !          2214: .PE
        !          2215: .@tag FI _FI8_
        !          2216: .FI _FI8_
        !          2217: Shift-reduce parsing of
        !          2218: .CW DDPDD .
        !          2219: .EF
        !          2220: .nf
        !          2221: \s5\l'\n(LLu\&\(ul'\s0
        !          2222: .EF 0
        !          2223: .fi
        !          2224: .SP
        !          2225: .ps 9
        !          2226: .PS
        !          2227: 
        !          2228:  define N % box invis $1 wid .25 %
        !          2229:  define D % box invis "\f2\s8D\s0\fP" wid .125 %
        !          2230:  define P % box invis "\f2\s8P\s0\fP" wid .125 %
        !          2231:  define E % box invis wid .05; box invis "$f2($end)$" wid .25 %
        !          2232:  define shift  % box invis wid .8 "shift" %
        !          2233:  define reduce % box invis wid .8 "reduce" %
        !          2234:  define lookahead % box invis wid .1; { move left .05; up; line <- } %
        !          2235:  define handle % { line from last box.sw to last box.se } %
        !          2236: 
        !          2237: [
        !          2238:        boxht = vs
        !          2239:        arrowht = .05; arrowwid = .025; lineht = .75*vs
        !          2240: 
        !          2241:        lookahead; D; D; P; D; D; E
        !          2242:  shift
        !          2243:        D; lookahead; D; P; D; D; E
        !          2244: ]
        !          2245: .PE
        !          2246: .LP
        !          2247: The second action reduces the token
        !          2248: .CW D
        !          2249: immediately to the left of the pointer
        !          2250: (right sides to be reduced are underlined for clarity).
        !          2251: The reduction replaces the right side
        !          2252: .CW D
        !          2253: by its left side
        !          2254: .CW intp :
        !          2255: .ps 9
        !          2256: .PS
        !          2257: [
        !          2258:        boxht = vs
        !          2259:        arrowht = .05; arrowwid = .025; lineht = .75*vs
        !          2260: 
        !          2261:        D; handle; lookahead; D; P; D; D; E
        !          2262:  reduce
        !          2263:        N("$intp$"); lookahead; D; P; D; D; E
        !          2264: ]
        !          2265: .PE
        !          2266: .LP
        !          2267: After the next
        !          2268: .CW D
        !          2269: is shifted, the right side
        !          2270: .CW intp$~$D
        !          2271: is reduced to the left side
        !          2272: .CW intp :
        !          2273: .ps 9
        !          2274: .PS
        !          2275: [
        !          2276:        boxht = vs
        !          2277:        arrowht = .05; arrowwid = .025; lineht = .75*vs
        !          2278: 
        !          2279:        N("$intp$"); handle; D; handle; lookahead; P; D; D; E
        !          2280:  reduce
        !          2281:        N("$intp$"); lookahead; P; D; D; E
        !          2282: ]
        !          2283: .PE
        !          2284: .LP
        !          2285: Successive shift actions now advance the lookahead pointer all the way
        !          2286: to the endmarker.
        !          2287: Finally, a sequence of reduce actions completes the parse.
        !          2288: .PP
        !          2289: It is no accident that a right side to be reduced always appears
        !          2290: immediately to the left of the pointer in Figure _FI8_.
        !          2291: This observation is the basis for a stack-implementation of shift-reduce
        !          2292: parsing.
        !          2293: Informally, the symbols to the left of the pointer
        !          2294: are held on a stack, so a right side to
        !          2295: be reduced appears at the top of the stack.
        !          2296: .SS "Parser States"
        !          2297: Instead of grammar symbols, a \*y-generated parser
        !          2298: works with states, which encode some parsing context
        !          2299: together with a grammar symbol.
        !          2300: The context summarizes prior parsing actions.
        !          2301: For example, states tell a parser for
        !          2302: real numbers that a digit to the left of a decimal point
        !          2303: reduces to
        !          2304: .CW intp ,
        !          2305: but that a digit to the right reduces to
        !          2306: .CW frac .
        !          2307: .PP
        !          2308: A
        !          2309: .I state
        !          2310: consists of a collection of items, where an
        !          2311: .I item
        !          2312: is a production with a dot inserted in the right side \(em some
        !          2313: versions of \*y use an underscore in place of the dot.
        !          2314: One of the states of the real-number parser is
        !          2315: .P{
        !          2316: real :  intp.P frac 
        !          2317: intp :  intp.D 
        !          2318: .P}
        !          2319: The dot tells us that an
        !          2320: .CW intp
        !          2321: has just been seen, and that the parser expects
        !          2322: to see a
        !          2323: .CW P
        !          2324: or a
        !          2325: .CW D .
        !          2326: .PP
        !          2327: In this state, the parser shifts on lookahead
        !          2328: .CW P .
        !          2329: The shift is recorded by (conceptually) moving the dot past
        !          2330: .CW P
        !          2331: to obtain the item
        !          2332: .P{
        !          2333: real :  intp P.frac 
        !          2334: .P}
        !          2335: .PP
        !          2336: Since,
        !          2337: .CW frac
        !          2338: now appears to the right of the dot, the parser expects the
        !          2339: incoming symbols to match a
        !          2340: .CW frac .
        !          2341: Although they are not shown,
        !          2342: the productions for
        !          2343: .CW frac
        !          2344: are implicitly carried with the item.
        !          2345: The full version, or
        !          2346: .I closure ,
        !          2347: of this state is obtained by adding the
        !          2348: productions for
        !          2349: .CW frac
        !          2350: (with a dot at the beginning of the right side):
        !          2351: .P{
        !          2352: real :  intp P.frac
        !          2353: frac :  .D
        !          2354: frac :  .D frac
        !          2355: .P}
        !          2356: Since both productions for
        !          2357: .CW frac
        !          2358: begin with the token
        !          2359: .CW D ,
        !          2360: no more productions are added;
        !          2361: otherwise, we would continue adding productions until all nonterminals
        !          2362: to the right of the dot were considered.
        !          2363: .PP
        !          2364: With this closure, on lookahead
        !          2365: .CW D ,
        !          2366: the parser shifts to a state containing the items
        !          2367: .P{
        !          2368: frac :  D.
        !          2369: frac :  D.frac
        !          2370: .P}
        !          2371: .PP
        !          2372: The parser states and their transitions constitute an automaton.
        !          2373: The automaton for the real-number grammar appears in
        !          2374: Figure _FI9_.
        !          2375: The solid arrows are for shift transitions, due to tokens.
        !          2376: The dashed arrows, for transitions due to nonterminals, are used
        !          2377: during reductions.
        !          2378: .KF
        !          2379: .nf
        !          2380: \s5\l'\n(LLu\&\(ul'\s0
        !          2381: .fi
        !          2382: .nr PS 9
        !          2383: .ps 9
        !          2384: .PS
        !          2385: [
        !          2386:        define state %
        !          2387:                if "$4"!="" then 'nitems=$4' else 'nitems=1'
        !          2388:        S$1:    box fill at O + $2*hu, $3*vu ht nitems*vs
        !          2389:                "$1" at S$1.n + 0,vs/2
        !          2390:        %
        !          2391: 
        !          2392:        arcrad = vs/3; boxht = vs; boxwid = 1.2; fillval = 1
        !          2393:        dashwid = .03
        !          2394:        hu = .7; vu = 4*vs
        !          2395: 
        !          2396: O: ""
        !          2397:        state(0, 0, 0)
        !          2398:        box invis "$f2($accept)^:~cdot~real~f2($end)$" at S0
        !          2399: 
        !          2400:        state(1, 3, 0)
        !          2401:        box invis "$f2($accept)^:~real~cdot~f2($end)$" at S1
        !          2402: 
        !          2403:        state(2, 1,-1, 2)
        !          2404:        [ down
        !          2405:        B1:     box invis
        !          2406:        B2:     box invis
        !          2407:                "$real^:~intp~cdot~P~frac$" ljust at B1.w + .075,0
        !          2408:                "$intp^:~intp~cdot~D$" ljust at B2.w + .075,0
        !          2409:        ] at S2
        !          2410: 
        !          2411:        state(5, 4,-1)
        !          2412:        box invis "$intp^:~intp~D~cdot$" at S5
        !          2413: 
        !          2414:        state(4, 2,-2)
        !          2415:        box invis "$real^:~intp~P~cdot~frac$" at S4
        !          2416: 
        !          2417:        state(6, 5,-2)
        !          2418:        box invis "$real^:~intp~P~frac~cdot$" at S6
        !          2419: 
        !          2420:        state(7, 3,-3, 2)
        !          2421:        [ down
        !          2422:        B1:     box invis
        !          2423:        B2:     box invis
        !          2424:                box invis "$frac^:~D~cdot$" ljust at B1.w + .1,0
        !          2425:                box invis "$frac^:~D~cdot~frac$" ljust at B2.w + .1,0
        !          2426:        ] at S7
        !          2427: 
        !          2428:        state(8, 6,-3)
        !          2429:        box invis "$frac^:~D~frac~cdot$" at S8
        !          2430: 
        !          2431:        state(3, 0,-3)
        !          2432:        box invis "$intp^:~D~cdot$" at S3
        !          2433: 
        !          2434: S9:    box invis at O + 6*hu, 0
        !          2435:        "\0\0\f3accept\fP" ljust at S9.w
        !          2436: 
        !          2437: G02:   .66<S0.sw,S0.s>
        !          2438: G03:   .33<S0.sw,S0.s>
        !          2439: G2:    .5<S2.sw,S2.s>
        !          2440: G4:    .5<S4.sw,S4.s>
        !          2441: G7a:   .5<S7.sw,S7.s>
        !          2442: G7b:   .5<S7.s,S7.se>
        !          2443: G7c:   S7.s + 0,-1.5*vs
        !          2444: 
        !          2445:        line -> from S0.e to S1.w dashed
        !          2446:        line -> from S2.e to S5.w
        !          2447:        line -> from S4.e to S6.w dashed
        !          2448:        line -> from S7.e to S8.w dashed
        !          2449:        line -> from S1.e to S9.w
        !          2450:        line -> from G03.s to G03.x, S3.n.y
        !          2451: 
        !          2452:        adown(G02); anell(S2.w, -> dashed, dashed)
        !          2453:        adown(G2); anell(S4.w, ->)
        !          2454:        adown(G4); anell(S7.w, ->)
        !          2455:        adown(G7a); anell(G7c); anell(G7b, ->)
        !          2456: 
        !          2457:        "$real$"        at .5<S0.e, S1.w> + 0, vs/2
        !          2458:        "$intp$"        at (G02.x+S2.w.x)/2, S2.y + vs/2
        !          2459:        "$~D$" ljust    at G03.x,S4.y
        !          2460:        "$f2($end)$"    at .5<S1.e, S9.w> + 0, vs/2
        !          2461:        "$D$"           at .5<S2.e, S5.w> + 0, vs/2
        !          2462:        "$P$"           at (G2.x+S4.w.x)/2, S4.y + vs/2
        !          2463:        "$frac$"        at .5<S4.e, S6.w> + 0, vs/2
        !          2464:        "$D$"           at (G4.x+S7.w.x)/2, S7.y + vs/2
        !          2465:        "$frac$"        at .5<S7.e, S8.w> + 0, vs/2
        !          2466:        "$D$"           at G7c + 0, vs/2
        !          2467: ]
        !          2468: .PE
        !          2469: .@tag FI _FI9_
        !          2470: .FI _FI9_
        !          2471: States and transitions for the real-number grammar.
        !          2472: The solid arrows are for shifts, and the dashed arrows
        !          2473: are for transitions during reductions.
        !          2474: .EF 0
        !          2475: .nf
        !          2476: \s5\l'\n(LLu\&\(ul'\s0
        !          2477: .fi
        !          2478: .SP
        !          2479: .KE
        !          2480: .EQ
        !          2481: delim @@
        !          2482: .EN
        !          2483: .PP
        !          2484: For technical reasons,
        !          2485: \*y augments a grammar by adding a new starting nonterminal
        !          2486: .CW $accept ,
        !          2487: which derives
        !          2488: the old starting nonterminal and an endmarker
        !          2489: .CW $end .
        !          2490: The starting state 0 has an item with a dot
        !          2491: to the left of the old starting symbol, as in
        !          2492: .P{
        !          2493: $accept : .real $end
        !          2494: .P}
        !          2495: The closure of state 0 contains the items
        !          2496: .P{
        !          2497: $accept : .real $end
        !          2498: real    : .intp P frac
        !          2499: intp    : .D
        !          2500: intp    : .intp D
        !          2501: .P}
        !          2502: Since the only token to the right of a dot is
        !          2503: .CW D ,
        !          2504: the very first token must be a
        !          2505: .CW D .
        !          2506: .PP
        !          2507: Some of the states of the real-number parser
        !          2508: in Figure _FI9_ are (informally)
        !          2509: .SP .5
        !          2510: .IP 0.
        !          2511: .I "The starting state" .
        !          2512: The item
        !          2513: .CW $accept:@^@.real@^@$end
        !          2514: tells us that the entire input, upto the endmarker,
        !          2515: must match
        !          2516: .CW real .
        !          2517: .SP .5
        !          2518: .IP 2.
        !          2519: .I "Within the integer part" .
        !          2520: An
        !          2521: .CW intp
        !          2522: has been seen.
        !          2523: The lookahead token must either be a
        !          2524: .CW D
        !          2525: (another digit in the integer part)
        !          2526: or a
        !          2527: .CW P
        !          2528: (the decimal point).
        !          2529: .SP .5
        !          2530: .IP 7.
        !          2531: .I "Within the fraction part" .
        !          2532: Shift as long as the lookahead token is a
        !          2533: .CW D .
        !          2534: Otherwise, reduce the last
        !          2535: .CW D
        !          2536: to
        !          2537: .CW frac .
        !          2538: .SP .5
        !          2539: .PP
        !          2540: State 2 is displayed as follows in the
        !          2541: .CW y.output
        !          2542: file for the real-number grammar:
        !          2543: .P{
        !          2544: state 2
        !          2545:        real :  intp.P frac 
        !          2546:        intp :  intp.D 
        !          2547: .sp .5
        !          2548:        D  shift 5
        !          2549:        P  shift 4
        !          2550:        .  error
        !          2551: .P}
        !          2552: After the two items is a summary of the actions in this state.
        !          2553: With lookahead
        !          2554: .CW D ,
        !          2555: the parser shifts to state 5, and with lookahead
        !          2556: .CW P
        !          2557: it shifts to state 4.
        !          2558: The default action
        !          2559: (represented by
        !          2560: .CW . '') ``
        !          2561: is to report an error.
        !          2562: .SS "Parsing Actions"
        !          2563: .PP
        !          2564: The parser holds states on a stack, with the current state on
        !          2565: top.
        !          2566: The starting state of the automaton in Figure _FI9_ is state 0.
        !          2567: With lookahead
        !          2568: .CW D ,
        !          2569: the automaton shifts to state 3 (in the bottom-left corner of
        !          2570: the figure)
        !          2571: by pushing 3 onto the stack and removing the lookahead
        !          2572: .CW D
        !          2573: from the input.
        !          2574: For ease of comparison with Figure _FI8_, the symbol
        !          2575: .CW D
        !          2576: appears below the state in the following diagram:
        !          2577: .EQ
        !          2578: delim $$
        !          2579: .EN
        !          2580: .KS
        !          2581: .ps 9
        !          2582: .PS
        !          2583: [
        !          2584:        define Disp %
        !          2585:                box invis $2
        !          2586:                { move to last box + 0,-del; $1 }
        !          2587:        %
        !          2588:        define N % Disp($1, wid .25) %
        !          2589:        define D % Disp("\f2\s8D\s0\fP", wid .1) %
        !          2590:        define P % Disp("\f2\s8P\s0\fP", wid .1) %
        !          2591:        define E % Disp("$f2($end)$", wid .3) %
        !          2592:        define action % Act: [
        !          2593:                right
        !          2594:        B:      box invis wid 1
        !          2595:        PTR:    box invis wid .1
        !          2596:                $1 ljust at B.w
        !          2597:        ] with .PTR.n at S.PTR.s %
        !          2598:        define shift % action("shift") %
        !          2599:        define reduce % action("$1") %
        !          2600:        define ptr %
        !          2601:        PTR:    box invis wid .05
        !          2602:                        { move left .025; move up boxht/2; line <- }
        !          2603:                box invis wid .3
        !          2604:                        { move left .15; $1 }
        !          2605:                box invis wid .05
        !          2606:                        { move left .025; move up boxht/2; line <- }
        !          2607:        %
        !          2608:        define handle % { line from last box.sw to last box.se } %
        !          2609:        define state % [
        !          2610:                down
        !          2611:        ELEM:   box "$1"
        !          2612:                $2
        !          2613:                $3
        !          2614:        ] with .ELEM.w at Here; move to last [].ELEM.e; right %
        !          2615: 
        !          2616:        boxht = vs; boxwid = .2
        !          2617:        arrowht = .05; arrowwid = .025; lineht = .5*vs; dy = vs
        !          2618:        movewid = .1; del = .015
        !          2619: 
        !          2620: L1:    S:[ right
        !          2621:                state(0)
        !          2622:                ptr()
        !          2623:                D; D; P; D; D; E
        !          2624:        ]
        !          2625:  shift
        !          2626: L2:    S:[ right
        !          2627:                state(0); state(3, D)
        !          2628:                ptr()
        !          2629:                D; P; D; D; E
        !          2630:        ] with .PTR.n at Act.PTR.s + 0,-boxht/2
        !          2631: 
        !          2632: ]
        !          2633: .PE
        !          2634: .KE
        !          2635: .LP
        !          2636: The top of the state stack has its own pointer, separate from the
        !          2637: lookahead pointer to the next input symbol.
        !          2638: .PP
        !          2639: The only item in state 3 is
        !          2640: .P{
        !          2641: intp :  D.
        !          2642: .P}
        !          2643: Whenever the dot in an item is at the end of the production, one of the
        !          2644: possible actions is a reduction by that production.
        !          2645: Since this state has no other actions, the parser chooses to reduce.
        !          2646: .PP
        !          2647: A reduce action has two phases:
        !          2648: (a) pop the states corresponding to the right side,
        !          2649: and (b) push a state corresponding to the left side.
        !          2650: The following diagram illustrates the reduction of the
        !          2651: leading
        !          2652: .CW D
        !          2653: in
        !          2654: .CW DDPDD
        !          2655: to
        !          2656: .CW intp :
        !          2657: .KS
        !          2658: .ps 9
        !          2659: .PS
        !          2660: [
        !          2661:        define Disp %
        !          2662:                box invis $2
        !          2663:                { move to last box + 0,-del; $1 }
        !          2664:        %
        !          2665:        define N % Disp($1, wid .25) %
        !          2666:        define D % Disp("\f2\s8D\s0\fP", wid .1) %
        !          2667:        define P % Disp("\f2\s8P\s0\fP", wid .1) %
        !          2668:        define E % Disp("$f2($end)$", wid .3) %
        !          2669:        define action % Act: [
        !          2670:                right
        !          2671:        B:      box invis wid 1
        !          2672:        PTR:    box invis wid .1
        !          2673:                $1 ljust at B.w
        !          2674:        ] with .PTR.n at S.PTR.s  + 0,-boxht %
        !          2675:        define shift % action("shift") %
        !          2676:        define reduce % action("$1") %
        !          2677:        define ptr %
        !          2678:        PTR:    box invis wid .05
        !          2679:                        { move left .025; move up boxht/2; line <- }
        !          2680:                box invis wid .3
        !          2681:                        { move left .15; $1 }
        !          2682:                box invis wid .05
        !          2683:                        { move left .025; move up boxht/2; line <- }
        !          2684:        %
        !          2685:        define handle % { line from last box.sw to last box.se } %
        !          2686:        define state % [
        !          2687:                down
        !          2688:        ELEM:   box "$1"
        !          2689:                $2
        !          2690:                $3
        !          2691:        ] with .ELEM.w at Here; move to last [].ELEM.e; right %
        !          2692: 
        !          2693:        boxht = vs; boxwid = .2
        !          2694:        arrowht = .05; arrowwid = .025; lineht = .5*vs; dy = vs
        !          2695:        movewid = .1; del = .015
        !          2696: 
        !          2697: L1:    S:[ right
        !          2698:                state(0); state(3, D, handle)
        !          2699:                ptr()
        !          2700:                D; P; D; D; E
        !          2701:        ]
        !          2702:  reduce(pop)
        !          2703: L2:    S:[ right
        !          2704:                state(0)
        !          2705:                ptr("$intp$")
        !          2706:                D; P; D; D; E
        !          2707:        ] with .PTR.n at Act.PTR.s + 0,-boxht
        !          2708:  reduce(goto)
        !          2709: L3:    S:[ right
        !          2710:                state(0); state(2, N("$intp$"))
        !          2711:                ptr()
        !          2712:                D; P; D; D; E
        !          2713:        ] with .PTR.n at Act.PTR.s + 0,-boxht
        !          2714: 
        !          2715:        dx = .75; dy = -lineht-vs/2-del
        !          2716:        "Pop the states corresponding to the right side \f2\s8D\s0\fP."\
        !          2717:                ljust at L1.ne + dx,dy
        !          2718:        "Prepare to push a state for the left side $intp$."\
        !          2719:                ljust at L2.ne + dx,dy
        !          2720:        "State 0 goes to 2 under $intp$."\
        !          2721:                ljust at L3.ne + dx,dy
        !          2722: 
        !          2723:        box invis wid 2.75 with .nw at L1.ne + dx,dy
        !          2724: ]
        !          2725: .PE
        !          2726: .KE
        !          2727: .PP
        !          2728: The parser has only four actions available to it, called
        !          2729: shift, reduce, accept, and error.
        !          2730: A move of the parser is as follows:
        !          2731: .SP .5
        !          2732: .IP 1. 4
        !          2733: Based on its current state, the parser decides whether it needs a lookahead
        !          2734: token to choose the next action.
        !          2735: If it needs one, and does not already have one, it calls
        !          2736: .CW yylex
        !          2737: to obtain the next token.
        !          2738: .SP .5
        !          2739: .IP 2.
        !          2740: Using the current state $p$, and the lookahead token $t$
        !          2741: if needed, the parser chooses an action.
        !          2742: .RS
        !          2743: .SP .25
        !          2744: .IP a) 4
        !          2745: A
        !          2746: .I shift
        !          2747: action to state $q$ is done by pushing state $q$ onto the
        !          2748: state stack and clearing the lookahead token.
        !          2749: .SP .25
        !          2750: .IP b)
        !          2751: A
        !          2752: .I reduce
        !          2753: action by a production is done in two phases.
        !          2754: In the first phase, the parser pops from the stack a number of states
        !          2755: equal to the number of symbols on the right side.
        !          2756: Let $q$ be the
        !          2757: state uncovered after the states are popped,
        !          2758: and let the nonterminal on the left side of the production take $q$ to $r$
        !          2759: (see the dashed arrows in Figure _FI9_).
        !          2760: In the second phase, the parser pushes state $r$
        !          2761: onto the stack.
        !          2762: .SP .25
        !          2763: .EQ
        !          2764: delim off
        !          2765: .EN
        !          2766: .IP c)
        !          2767: The
        !          2768: .I accept
        !          2769: action occurs after the entire input has been seen and matched.
        !          2770: This action occurs only when the lookahead token is the endmarker
        !          2771: .CW $end .
        !          2772: .EQ
        !          2773: delim $$
        !          2774: .EN
        !          2775: .SP .25
        !          2776: .IP d)
        !          2777: An
        !          2778: .I error
        !          2779: action occurs when the parser can no longer continue parsing
        !          2780: according to the productions.
        !          2781: That is, the input tokens seen so far and the current lookahead
        !          2782: cannot possibly be followed by anything that would result
        !          2783: in a legal input.
        !          2784: See Section _SH5_ for error recovery.
        !          2785: .RE
        !          2786: .@tag SH _SH4_
        !          2787: .SH _SH4_  "Ambiguity and Conflicts"
        !          2788: A
        !          2789: .I "shift/reduce conflict"
        !          2790: occurs if the parser cannot decide between
        !          2791: a shift action and a reduce action.
        !          2792: Similarly, a
        !          2793: .I "reduce/reduce conflict"
        !          2794: occurs if the parser cannot decide between
        !          2795: two legal reductions.
        !          2796: .PP
        !          2797: Conflicts definitely occur when a grammar is
        !          2798: .I ambiguous ;
        !          2799: that is, if some input string has more than one parse tree.
        !          2800: Conflicts can also occur when a grammar, although consistent,
        !          2801: requires a more complex parser than \*y is capable of
        !          2802: constructing.
        !          2803: Finally, conflicts are sometimes introduced when an action is embedded
        !          2804: into the middle of a production.
        !          2805: .PP
        !          2806: \*Y produces a parser even when conflicts occur.
        !          2807: Rules used to choose between two competing actions are
        !          2808: called
        !          2809: .I "disambiguating rules" .
        !          2810: The default disambiguating rules are:
        !          2811: .SP .5
        !          2812: .IP 1. 4
        !          2813: In a shift/reduce conflict, the default is to shift.
        !          2814: .SP .25
        !          2815: .IP 2.
        !          2816: In a reduce/reduce conflict, the default is to reduce by
        !          2817: the earlier production in the specification.
        !          2818: .SP .5
        !          2819: .PP
        !          2820: Although the effect of disambiguating rules can often be achieved
        !          2821: by rewriting the grammar to avoid conflicts,
        !          2822: experience suggests that this rewriting is somewhat unnatural
        !          2823: and produces slower parsers.
        !          2824: .PP
        !          2825: The rest of this section considers two situations,
        !          2826: one in which the default disambiguating rules do not
        !          2827: have the intended effect, and one in which they do.
        !          2828: It is recommended that shift/reduce conflicts be
        !          2829: investigated using the
        !          2830: .CW y.output
        !          2831: file created by running \*y with the
        !          2832: .CW -v
        !          2833: option.
        !          2834: .......
        !          2835: .SS "To Shift or To Reduce"
        !          2836: \*Y reports 2 shift/reduce conflicts when it is applied to
        !          2837: .EQ
        !          2838: delim off
        !          2839: .EN
        !          2840: .P{
        !          2841: %token NUM
        !          2842: %%
        !          2843: expr  :  expr '\en'       { printf("\en"); }
        !          2844:       |  expr '-' expr   { printf(" -"); }
        !          2845:       |  NUM             { printf(" %g", $NUM); }
        !          2846:       ;
        !          2847: .P}
        !          2848: .EQ
        !          2849: delim $$
        !          2850: .EN
        !          2851: .PP
        !          2852: The hope here is to translate an infix expression,
        !          2853: terminated by a newline, into postfix
        !          2854: notation.
        !          2855: Thus, we want
        !          2856: .P{
        !          2857: 2 - 1 - 1 \en
        !          2858: .P}
        !          2859: to be translated into
        !          2860: .P{
        !          2861: 2 1 - 1 - \en
        !          2862: .P}
        !          2863: The answer would be 0 if the expression were evaluated by
        !          2864: subtracting 1 from 2, and then subtracting 1 from the result.
        !          2865: Unfortunately, the output of the parser (with a suitable user-routines
        !          2866: section) is
        !          2867: .P{
        !          2868:  2 1 1 \en - -
        !          2869: .P}
        !          2870: What happened?
        !          2871: The problem can be traced to the preference for shift in a shift/reduce
        !          2872: conflict, which makes
        !          2873: .CW -
        !          2874: right associative, and gives
        !          2875: .CW \en
        !          2876: higher precedence than
        !          2877: .CW - .
        !          2878: .PP
        !          2879: A slightly edited version of the
        !          2880: .CW y.output
        !          2881: file for this grammar appears in Figure _FI10_.
        !          2882: Unfortunately, both productions and states are numbered,
        !          2883: leaving room for confusion.
        !          2884: The action
        !          2885: .P{
        !          2886:        .  reduce 2
        !          2887: .P}
        !          2888: refers to \f4production\fP 2, whereas the action
        !          2889: .P{
        !          2890:        \en  shift 3
        !          2891: .P}
        !          2892: refers to \f4state\fP 3.
        !          2893: .KF
        !          2894: .EQ
        !          2895: delim off
        !          2896: .EN
        !          2897: .nf
        !          2898: \s5\l'\n(LLu\&\(ul'\s0
        !          2899: .fi
        !          2900: .ps 9
        !          2901: .ft CW
        !          2902: .PS
        !          2903: [
        !          2904:        define text % [
        !          2905:                boxht = vs
        !          2906:        B:      box $2 invis
        !          2907:                $1 ljust at B.w
        !          2908:        ] %
        !          2909: 
        !          2910:        boxht = vs
        !          2911: 
        !          2912: C1:    [
        !          2913:                boxwid = 2; down
        !          2914: 
        !          2915:                text("state 0")
        !          2916:                text("", ht vs/4)
        !          2917:                text("    $accept : .expr $end ")
        !          2918:                text("", ht vs/4)
        !          2919:                text("    NUM  shift 2")
        !          2920:                text("    .  error")
        !          2921:                text("    expr  goto 1")
        !          2922:                text("", ht vs/2)
        !          2923:                text("state 1")
        !          2924:                text("", ht vs/4)
        !          2925:                text("    $accept :  expr.$end ")
        !          2926:                text("    expr :  expr.\en ")
        !          2927:                text("    expr :  expr.- expr ")
        !          2928:                text("    $end  accept")
        !          2929:                text("", ht vs/4)
        !          2930:                text("    \en  shift 3")
        !          2931:                text("    -  shift 4")
        !          2932:                text("    .  error")
        !          2933:                text("", ht vs/2)
        !          2934:                text("state 2")
        !          2935:                text("", ht vs/4)
        !          2936:                text("    expr :  NUM.    (3)")
        !          2937:                text("", ht vs/4)
        !          2938:                text("    .  reduce 3")
        !          2939:        ]
        !          2940: 
        !          2941: C2:    [
        !          2942:                boxwid = 2.5; down
        !          2943: 
        !          2944:                text("state 3")
        !          2945:                text("", ht vs/4)
        !          2946:                text("    expr :  expr \en.    (1)")
        !          2947:                text("", ht vs/4)
        !          2948:                text("    .  reduce 1")
        !          2949:                text("", ht vs/2)
        !          2950:                text("state 4")
        !          2951:                text("", ht vs/4)
        !          2952:                text("    expr :  expr -.expr ")
        !          2953:                text("", ht vs/4)
        !          2954:                text("    NUM  shift 2")
        !          2955:                text("    .  error")
        !          2956:                text("    expr  goto 5")
        !          2957:                text("", ht vs/2)
        !          2958: .ft CB
        !          2959:                text("5: conflict (shift \en, reduce 2)")
        !          2960:                text("5: conflict (shift -, reduce 2)")
        !          2961: .ft CW
        !          2962:                text("state 5")
        !          2963:                text("", ht vs/4)
        !          2964:                text("    expr :  expr.\en ")
        !          2965:                text("    expr :  expr.- expr ")
        !          2966:                text("    expr :  expr - expr.    (2)")
        !          2967:                text("", ht vs/4)
        !          2968:                text("    \en  shift 3")
        !          2969:                text("    -  shift 4")
        !          2970:                text("    .  reduce 2")
        !          2971:        ] with .ne at C1.nw + pagewid-.75,0
        !          2972: ]
        !          2973: .PE
        !          2974: .EQ
        !          2975: delim $$
        !          2976: .EN
        !          2977: .@tag FI _FI10_
        !          2978: .FI _FI10_
        !          2979: A slightly edited
        !          2980: .CW y.output
        !          2981: file.
        !          2982: .EF 0
        !          2983: .nf
        !          2984: \s5\l'\n(LLu\&\(ul'\s0
        !          2985: .fi
        !          2986: .SP
        !          2987: .KE
        !          2988: .PP
        !          2989: The two shift/reduce conflicts are in state 5.
        !          2990: In this state,
        !          2991: by default, the parser shifts the lookahead symbols
        !          2992: .CW \en
        !          2993: and
        !          2994: .CW -
        !          2995: instead of using the item
        !          2996: .P{
        !          2997: expr :  expr - expr.    (2)
        !          2998: .P}
        !          2999: to reduce by production (2).
        !          3000: This reduction can occur only when the right side is on
        !          3001: top of the stack, so, when the conflict occurs, the
        !          3002: stack must contain states corresponding to
        !          3003: .ps 9
        !          3004: .ft CW
        !          3005: .PS
        !          3006: Indent: box wid pagewid ht 0 invis
        !          3007: [
        !          3008:        boxwid = .45; boxht = 1/6
        !          3009: 
        !          3010: Bot:   box "\f1$...$\fP" invis
        !          3011:        box "expr$\"\" sub a$"
        !          3012:        box "-"
        !          3013:        box "expr$\"\" sub b$"
        !          3014: 
        !          3015:        line from Bot.nw to Bot.ne to Bot.se to Bot.sw
        !          3016: ] with .w at Indent.w + 20/72,0
        !          3017: .PE
        !          3018: .LP
        !          3019: (The subscripts merely distinguish between the
        !          3020: two occurrences of
        !          3021: .CW expr .)
        !          3022: .PP
        !          3023: The other items in state 5 tell us more about the choices
        !          3024: faced by the parser.
        !          3025: With lookahead
        !          3026: .CW \en
        !          3027: the parser shifts, by the default disambiguating rule.
        !          3028: Thus, it treats
        !          3029: .CW expr$"" sub b$
        !          3030: on top of the stack as if it were in the item
        !          3031: .P{
        !          3032: expr :  expr$"" sub b$.\en
        !          3033: .P}
        !          3034: instead of the item
        !          3035: .P{
        !          3036: expr :  expr$"" sub a$ - expr$"" sub b$.    (2)
        !          3037: .P}
        !          3038: Similarly, with lookahead
        !          3039: .CW - ,
        !          3040: the parser treats
        !          3041: .CW expr$"" sub b$
        !          3042: as if it were the first subexpression in
        !          3043: .P{
        !          3044: expr :  expr$"" sub b$.- expr
        !          3045: .P}
        !          3046: .PP
        !          3047: Putting these observations together, the input
        !          3048: .CW 2-1-1\en
        !          3049: results in the stack eventually containing
        !          3050: .P{
        !          3051: expr - expr - expr \en
        !          3052: .P}
        !          3053: .PP
        !          3054: A sequence of reductions now occurs; the corresponding actions
        !          3055: print a newline and two minus signs.$"" sup _FS2_$
        !          3056: .FS
        !          3057: .SP
        !          3058: .@tag FS _FS2_
        !          3059: $"" sup _FS2_$
        !          3060: This explanation assumes that the newline is the last character
        !          3061: of the input.
        !          3062: If it is not, the parser will wait for more input after
        !          3063: reducing the right side
        !          3064: .CW expr\en .
        !          3065: At this point, the stack contains
        !          3066: .P{ .25
        !          3067: expr - expr - expr
        !          3068: .P} .25
        !          3069: The parser needs more input before it can choose whether to
        !          3070: shift on newline, shift on minus, or reduce on any other
        !          3071: token.
        !          3072: .FE
        !          3073: .PP
        !          3074: The addition of the precedence declarations
        !          3075: .P{
        !          3076: %nonassoc '\en'
        !          3077: %left     '-'
        !          3078: .P}
        !          3079: eliminates the conflicts in state 5, resulting in the
        !          3080: new state
        !          3081: .P{
        !          3082: state 5
        !          3083:     expr :  expr.\en 
        !          3084:     expr :  expr.- expr 
        !          3085:     expr :  expr - expr.    (2)
        !          3086: .sp .5
        !          3087:     .  reduce 2
        !          3088: .P}
        !          3089: Here, the reduction takes precedence over the potential shifts,
        !          3090: thereby implementing the left associativity of
        !          3091: .CW -
        !          3092: and its higher precedence over
        !          3093: .CW \en .
        !          3094: .SS "Precedence Declarations"
        !          3095: Precedence declarations give rise to disambiguating
        !          3096: rules for resolving parsing conflicts.
        !          3097: .PP
        !          3098: As mentioned in Section _SH2_, a precedence declaration
        !          3099: starts with
        !          3100: .CW %left ,
        !          3101: .CW %right ,
        !          3102: or
        !          3103: .CW %nonassoc .
        !          3104: These keywords specify the associativity of the tokens in a declaration.
        !          3105: All the tokens in a declaration have the same precedence; tokens
        !          3106: in successive declarations have higher precedence.
        !          3107: A token in a precedence declaration need not be, but can be,
        !          3108: declared by
        !          3109: .CW %token
        !          3110: as well.
        !          3111: .PP
        !          3112: The disambiguating rules are as follows.
        !          3113: .SP .5
        !          3114: .IP 1. 4
        !          3115: Although declared only for tokens and literals, precedence
        !          3116: information is attached to each production as well.
        !          3117: The precedence and associativity of a production
        !          3118: is that of the last token or literal
        !          3119: on its right side.
        !          3120: The
        !          3121: .CW %prec
        !          3122: construction overrides this default.
        !          3123: .SP .5
        !          3124: .IP 2.
        !          3125: If there is a shift/reduce conflict, and both
        !          3126: the lookahead symbol (to be shifted)
        !          3127: and the production (to be reduced)
        !          3128: have precedence declarations, then
        !          3129: the conflict is resolved in favor of the action (shift or reduce)
        !          3130: with the higher precedence.
        !          3131: If the precedences are the same, then the associativity is used;
        !          3132: left associative implies reduce, right associative
        !          3133: implies shift, and nonassociative implies error.
        !          3134: .SP .5
        !          3135: .IP 3.
        !          3136: In the absence of precedence information, the default
        !          3137: disambiguating rules given earlier in this section are used.
        !          3138: More precisely, suppose that there is no
        !          3139: precedence information for either the lookahead symbol or
        !          3140: a production to be reduced by.
        !          3141: A shift/reduce conflict is resolved by shifting.
        !          3142: A reduce/reduce conflict is resolved by reducing by the
        !          3143: production that appears earlier in the specification.
        !          3144: Conflicts resolved by these default rules are reported.
        !          3145: .SP .5
        !          3146: .LP
        !          3147: Conflicts resolved by precedence are not counted in the shift/reduce
        !          3148: and reduce/reduce conflicts reported by \*y.
        !          3149: Thus, mistakes in precedence declarations can mask errors in
        !          3150: the design of the productions.
        !          3151: .SS "Shift a Dangling Else"
        !          3152: As an example of the power of the default disambiguating rules
        !          3153: consider a fragment from a programming language involving an
        !          3154: if-then-else construction:
        !          3155: .P{
        !          3156: stmt :  IF '(' expr ')' stmt
        !          3157:      |  IF '(' expr ')' stmt ELSE stmt
        !          3158:      ;
        !          3159: .P}
        !          3160: Here,
        !          3161: .CW IF
        !          3162: and
        !          3163: .CW ELSE
        !          3164: are tokens,
        !          3165: .CW stmt
        !          3166: is a nonterminal for statements, and
        !          3167: .CW expr
        !          3168: is a nonterminal for expressions.
        !          3169: Call the first production the
        !          3170: .I "simple-if"
        !          3171: production and the second the
        !          3172: .I "else-if"
        !          3173: production.
        !          3174: .PP
        !          3175: These two productions are ambiguous, since
        !          3176: .P{
        !          3177: IF ( expr$"" sub 1$ ) IF ( expr$"" sub 2$ ) stmt$"" sub a$ ELSE stmt$"" sub b$
        !          3178: .P}
        !          3179: can be structured in two ways
        !          3180: .ft CB
        !          3181: .TS
        !          3182: lw4 0 l7 | l.
        !          3183:        IF ( expr$"" sub 1$ ) { IF ( expr$"" sub 1$ ) {
        !          3184:            \f(CWIF ( expr$"" sub 2$ ) stmt$"" sub a$\f(CB          \f(CWIF ( expr$"" sub 2$ ) stmt$"" sub a$\f(CB
        !          3185:        \f(CW}\f(CB         \f(CWELSE stmt$"" sub b$\f(CB
        !          3186:        ELSE stmt$"" sub b$     }
        !          3187: .TE
        !          3188: .LP
        !          3189: The second interpretation, with an
        !          3190: .CW ELSE
        !          3191: matching the nearest preceding unmatched
        !          3192: .CW IF ,
        !          3193: is the one taken by most programming languages.
        !          3194: It is the interpretation obtained when shift/reduce conflicts are
        !          3195: resolved in favor of shift actions.
        !          3196: .PP
        !          3197: The
        !          3198: .CW y.output
        !          3199: file for a grammar containing the simple-if and if-else productions
        !          3200: contains a shift/reduce conflict, illustrated by
        !          3201: .P{
        !          3202: 8: shift/reduce conflict (shift 9, red'n 1) on ELSE
        !          3203: state 8
        !          3204:     stmt :  IF ( expr ) stmt.    (1)
        !          3205:     stmt :  IF ( expr ) stmt.ELSE stmt 
        !          3206: .sp .5
        !          3207:     ELSE  shift 9
        !          3208:     .  reduce 1
        !          3209: .P}
        !          3210: This conflict occurs when the lookahead symbol is
        !          3211: .CW ELSE
        !          3212: and the parser stack contains the right side of the simple-if production
        !          3213: .P{
        !          3214: \f1$...$\fP IF ( expr ) stmt
        !          3215: .P}
        !          3216: The parser chooses to shift the
        !          3217: .CW ELSE
        !          3218: rather than reduce by the simple-if production.
        !          3219: This choice allows
        !          3220: .P{
        !          3221: \f1$...$\fP IF ( expr ) stmt ELSE stmt
        !          3222: .P}
        !          3223: to be successfully reduced by the if-else production.
        !          3224: Note that a premature application of the simple-if rule
        !          3225: (with lookahead
        !          3226: .CW ELSE )
        !          3227: would lead to the stack contents
        !          3228: .P{
        !          3229: \f1$...$\fP stmt ELSE stmt
        !          3230: .P}
        !          3231: which cannot be parsed further.
        !          3232: .PP
        !          3233: A shift on lookahead
        !          3234: .CW ELSE
        !          3235: also matches an
        !          3236: .CW ELSE
        !          3237: with the nearest preceding unmatched
        !          3238: .CW IF .
        !          3239: With stack contents
        !          3240: .P{
        !          3241: \f1$...$\fP \f(CWIF ( expr )\fP IF ( expr ) stmt
        !          3242: .P}
        !          3243: and lookahead
        !          3244: .CW ELSE ,
        !          3245: the parser shifts, so the stack eventually holds
        !          3246: .P{
        !          3247: \f1$...$\fP \f(CWIF ( expr )\fP IF ( expr ) stmt ELSE stmt
        !          3248: .P}
        !          3249: A reduction by the if-else production now yields
        !          3250: .P{
        !          3251: \f1$...$\fP \f(CWIF ( expr )\fP stmt
        !          3252: .P}
        !          3253: which can be reduced by the simple-if production.
        !          3254: .@tag SH _SH5_
        !          3255: .SH _SH5_  "Error Handling"
        !          3256: Error handling is an extremely difficult area, and many of the problems are
        !          3257: semantic ones.
        !          3258: When an error is found, it may be necessary to undo the effect of
        !          3259: actions \(em for example, to reclaim parse-tree storage, to delete or alter
        !          3260: symbol-table entries \(em and, typically, set flags to avoid generation of
        !          3261: further output.
        !          3262: .PP
        !          3263: It is seldom acceptable to stop all processing when an error is found;
        !          3264: further syntax errors might be found if parsing continues.
        !          3265: But, how do we get the parser ``restarted'' after an error is detected.
        !          3266: One approach is to discard tokens from the input until parsing can be
        !          3267: continued.
        !          3268: .PP
        !          3269: \*Y provides a simple, but reasonably general, feature for discarding
        !          3270: tokens.
        !          3271: The token name
        !          3272: .CW error
        !          3273: is reserved for error handling.
        !          3274: On the right side of a production,
        !          3275: .CW error
        !          3276: suggests a place where error recovery is planned.
        !          3277: When an error occurs, the parser pops its stack until it enters a
        !          3278: state where the token
        !          3279: .CW error
        !          3280: is legal.
        !          3281: It then behaves as if
        !          3282: .CW error
        !          3283: were the current lookahead, and performs the action encountered.
        !          3284: The lookahead is then reset to the token that caused the error.
        !          3285: If no error productions are specified, parsing halts when an
        !          3286: error is detected.
        !          3287: .PP
        !          3288: In order to prevent a cascade of error messages, the parser, after
        !          3289: detecting an error, remains in the error state until
        !          3290: three tokens have been successfully
        !          3291: read and shifted.
        !          3292: If an error is detected when the parser is already in error state,
        !          3293: no message is given, and the input token is quietly deleted.
        !          3294: .PP
        !          3295: For example, a production
        !          3296: .P{
        !          3297: stmt :  error
        !          3298: .P}
        !          3299: would, in effect, mean that on a syntax error
        !          3300: the parser would attempt to skip over the statement
        !          3301: in which the error was seen.
        !          3302: More precisely, the parser will
        !          3303: scan ahead, looking for three tokens that might legally follow
        !          3304: a statement, and start processing at the first of these; if
        !          3305: the beginnings of statements are not sufficiently distinctive, it may make a
        !          3306: false start in the middle of a statement, and end up reporting a
        !          3307: second error where there is in fact no error.
        !          3308: .PP
        !          3309: Actions can be used with these special error rules.
        !          3310: These actions might attempt to reinitialize tables, reclaim symbol table space, etc.
        !          3311: .PP
        !          3312: Productions with just
        !          3313: .CW error
        !          3314: on the right side are very general, but difficult to control.
        !          3315: Somewhat easier are productions such as
        !          3316: .P{
        !          3317: stmt :  error  ';'
        !          3318: .P}
        !          3319: Here, upon error, the parser attempts to skip over the statement, but
        !          3320: will do so by skipping to the next semicolon.
        !          3321: All tokens after the error and before the next semicolon
        !          3322: cannot be shifted, and are discarded.
        !          3323: When the semicolon is seen, this right side will be reduced,
        !          3324: and any ``cleanup''
        !          3325: action associated with it performed.
        !          3326: .PP
        !          3327: Another form of error production arises in interactive applications, where
        !          3328: it may be desirable to permit a line to be reentered after an error.
        !          3329: A possible error production might be
        !          3330: .EQ
        !          3331: delim off
        !          3332: .EN
        !          3333: .P{
        !          3334: input :  error '\en'
        !          3335:              {  printf("Reenter last line: ");  }
        !          3336:          input
        !          3337:              { $$ = $input;  }
        !          3338:       ;
        !          3339: .P}
        !          3340: One potential difficulty with this approach is that
        !          3341: the parser must correctly process three input tokens before it
        !          3342: admits that it has correctly resynchronized after the error.
        !          3343: If the reentered line contains an error
        !          3344: in the first two tokens, the parser deletes the offending tokens,
        !          3345: and gives no message; this is clearly unacceptable.
        !          3346: For this reason, there is a mechanism that
        !          3347: can be used to force the parser
        !          3348: to believe that an error has been fully recovered from.
        !          3349: The statement
        !          3350: .P{
        !          3351: yyerrok;
        !          3352: .P}
        !          3353: in an action
        !          3354: resets the parser to its normal mode.
        !          3355: The last example is better written
        !          3356: .P{
        !          3357: input :  error '\en'
        !          3358:              { yyerrok; printf("Reenter last line: "); }
        !          3359:          input
        !          3360:              { $$ = $input; }
        !          3361:       ;
        !          3362: .P}
        !          3363: .EQ
        !          3364: delim $$
        !          3365: .EN
        !          3366: .PP
        !          3367: As mentioned above, the token seen immediately
        !          3368: after the
        !          3369: .CW error
        !          3370: symbol is the input token at which the
        !          3371: error was discovered.
        !          3372: Sometimes, this is inappropriate; for example, an
        !          3373: error recovery action might
        !          3374: take upon itself the job of finding the correct place to resume input.
        !          3375: In this case,
        !          3376: the previous lookahead token must be cleared.
        !          3377: The statement
        !          3378: .P{
        !          3379: yyclearin;
        !          3380: .P}
        !          3381: in an action has this effect.
        !          3382: For example, suppose the action after error
        !          3383: is to call some sophisticated resynchronization routine,
        !          3384: supplied by the user, that attempts to advance the input to the
        !          3385: beginning of the next valid statement.
        !          3386: After this routine is called, the next token returned by
        !          3387: .CW yylex
        !          3388: is presumably the first token in a legal statement;
        !          3389: the old, illegal token must be discarded, and the error state reset.
        !          3390: This can be done by a rule like
        !          3391: .P{
        !          3392: stmt :  error 
        !          3393:             { resynch(); yyerrok; yyclearin; }
        !          3394:      ;
        !          3395: .P}
        !          3396: .PP
        !          3397: These mechanisms are admittedly crude, but do allow for a simple,
        !          3398: fairly effective recovery of the parser
        !          3399: from many errors;
        !          3400: moreover, the user can get control to deal with
        !          3401: the error actions required by other portions of the program.
        !          3402: .@tag SH _SH6_
        !          3403: .SH _SH6_  "The Yacc Environment"
        !          3404: From a specification, \*y creates a file of C programs, called
        !          3405: .CW y.tab.c
        !          3406: on most systems.
        !          3407: .SS "Program Organization"
        !          3408: Consider a specification file of the form
        !          3409: .P{
        !          3410: %{
        !          3411:       $<!$\f2user supplied code within declarations\fP$>!$
        !          3412: #define YYSTYPE $<!$\f1desired type\fP$>!$
        !          3413: %}
        !          3414:       $<!$\f2declarations section\fP$>!$
        !          3415: %%
        !          3416:       $<!$\f2productions\fP$>!$
        !          3417: %%
        !          3418:       $<!$\f2user-routines section\fP$>!$
        !          3419: .P}
        !          3420: From this specification, \*y creates a file
        !          3421: .CW y.tab.c ,
        !          3422: organized as follows:
        !          3423: .P{
        !          3424:       $<!$\&\f2user supplied code within declarations\fP$>!$
        !          3425: #define YYSTYPE $<!$\f1desired type\fP$>!$
        !          3426:       $<!$\f2token and other declarations\fP$>!$
        !          3427:       $<!$\f2user-routines section\fP$>!$
        !          3428:       $<!$\f2parser tables\fP$>!$
        !          3429: yyparse() {  \&\f1$...$\fP }
        !          3430: .P}
        !          3431: Actions are incorporated into
        !          3432: .CW yyparse .
        !          3433: .PP
        !          3434: As mentioned in Section _SH1_,
        !          3435: .CW yyparse ,
        !          3436: the code for the parser, expects the following functions
        !          3437: to be supplied:
        !          3438: .P{
        !          3439: int yylex() {
        !          3440:        \f2a lexical analyzer; returns a token\fP
        !          3441: }
        !          3442: int main(\f1$...$\fP) {
        !          3443:        \f1$...$\fP yyparse(); \f1$...$\fP
        !          3444: }
        !          3445: void yyerror(s) char *s; {
        !          3446:        \f2print an error message pointed to by\fP s
        !          3447: }
        !          3448: .P}
        !          3449: .PP
        !          3450: The function
        !          3451: .CW main
        !          3452: decides when it wants to call
        !          3453: .CW yyparse ,
        !          3454: which returns 0 if the parser accepts, and 1 if an error is detected
        !          3455: and no error recovery is possible.
        !          3456: .PP
        !          3457: A user-supplied function
        !          3458: .CW yyerror
        !          3459: is called with a string containing an error message.
        !          3460: Applications typically do more than simply print the
        !          3461: message; for example, the message might be
        !          3462: accompanied by the input line number on which the error was detected.
        !          3463: The external integer variable
        !          3464: .CW yychar
        !          3465: contains the lookahead token number at the time an error is
        !          3466: detected; this may be of some interest in giving better
        !          3467: diagnostics.
        !          3468: .PP
        !          3469: The external variable
        !          3470: .CW yydebug
        !          3471: is normally set to 0.
        !          3472: It it is set to a nonzero value, the parser will output a
        !          3473: verbose description of its actions, including the tokens
        !          3474: read and the parser actions.
        !          3475: Depending on the operating environment, it may be possible
        !          3476: to set this variable by using a debugging system.
        !          3477: .SS "Lexical Tie-Ins"
        !          3478: The lexical analyzer
        !          3479: .CW yylex
        !          3480: must return an integer, the token number, representing
        !          3481: the lookahead token.
        !          3482: An attribute value associated with the token must be
        !          3483: placed in the global variable
        !          3484: .CW yylval .
        !          3485: The lexical-analyzer generator \f2lex\fP|reference(latest lex)
        !          3486: can be used together with \*y.
        !          3487: .PP
        !          3488: The parser and the lexical analyzer must agree on the
        !          3489: token numbers in order for communication between them to
        !          3490: take place.
        !          3491: Token numbers may be chosen by \*y, or chosen by the user.
        !          3492: In either case, the
        !          3493: .CW #def\&ine
        !          3494: mechanism of C is used to allow the lexical analyzer
        !          3495: to refer to these numbers symbolically.
        !          3496: For example, the declarations section
        !          3497: .P{
        !          3498: %token IF ELSE
        !          3499: .P}
        !          3500: leads to the following definitions in the file
        !          3501: .CW y.tab.c :
        !          3502: .P{
        !          3503: # define IF 257
        !          3504: # define ELSE 258
        !          3505: .P}
        !          3506: .PP
        !          3507: If
        !          3508: .CW yylex
        !          3509: is included in the user-routines section, it is within the scope
        !          3510: of these definitions, so
        !          3511: .CW IF
        !          3512: and
        !          3513: .CW ELSE
        !          3514: can be used as the names of token numbers in
        !          3515: .CW yylex .
        !          3516: .PP
        !          3517: A file
        !          3518: .CW y.tab.h
        !          3519: containing the definition of token numbers can be
        !          3520: created by running \*y with the
        !          3521: .CW -d
        !          3522: option.
        !          3523: .PP
        !          3524: The approach of treating token names as defined constants
        !          3525: leads to clear, easily modified lexical analyzers; the only
        !          3526: pitfall is the need to avoid using any token names that are
        !          3527: reserved or significant in C or the parser.
        !          3528: For example, the use of the token names
        !          3529: .CW if
        !          3530: and
        !          3531: .CW while
        !          3532: will almost certainly cause severe difficulties when
        !          3533: the lexical analyzer is compiled.
        !          3534: The token name
        !          3535: .CW error
        !          3536: is reserved for error handling; see Section _SH5_.
        !          3537: .PP
        !          3538: \*Y chooses token numbers if the user does not.
        !          3539: The default token number for a literal character
        !          3540: is the numerical value of the character in the
        !          3541: local character set.
        !          3542: Other names are assigned token numbers starting at
        !          3543: 257.
        !          3544: .PP
        !          3545: To assign a number to a token (including a literal), the first
        !          3546: appearance of the token name or literal in the declarations section
        !          3547: can be immediately followed by a nonnegative integer.
        !          3548: This integer is taken to be the token number of the name or literal.
        !          3549: Names and literals not defined by this mechanism retain their default
        !          3550: definition.
        !          3551: It is important that all token numbers be distinct.
        !          3552: .PP
        !          3553: For historical reasons, the endmarker must have token number
        !          3554: 0 or negative.
        !          3555: This token number cannot be redefined by the user;
        !          3556: thus, all lexical analyzers must be prepared to return
        !          3557: 0 or negative as a token number upon reaching the end of
        !          3558: their input.
        !          3559: .SS "Communicating Context to the Lexical Analyzer"
        !          3560: Some lexical decisions depend on context.
        !          3561: For example, the lexical analyzer might want to
        !          3562: delete blanks normally, but not within quoted strings.
        !          3563: Or names might be entered into a symbol table in declarations,
        !          3564: but not in expressions.
        !          3565: .PP
        !          3566: One way of handling this situation is
        !          3567: to create a global flag that is
        !          3568: examined by the lexical analyzer, and set by actions.
        !          3569: For example, suppose a program
        !          3570: consists of zero or more declarations,
        !          3571: followed by zero or more statements.
        !          3572: Consider:
        !          3573: .P{
        !          3574: %{
        !          3575:     int dflag;
        !          3576: %}
        !          3577: \&\f2$...$  other declarations $...$\fP
        !          3578: %%
        !          3579: prog  :  decls stmts
        !          3580:       ;
        !          3581: decls :  /* empty */          { dflag = 1; }
        !          3582:       |  decls  declaration
        !          3583:       ;
        !          3584: stmts :  /* empty */          { dflag = 0; }
        !          3585:       |  stmts  statement
        !          3586:       ;
        !          3587: \&\f2$...$  other productions $...$\fP
        !          3588: .P}
        !          3589: .PP
        !          3590: The flag
        !          3591: .CW dflag
        !          3592: is now 1 when reading declarations and 0 when reading statements,
        !          3593: .ul
        !          3594: except for the first token in the first statement.
        !          3595: This token must be seen by the parser before it can tell that
        !          3596: the declarations have ended and the productions have
        !          3597: begun.
        !          3598: In many cases, this single token exception does not
        !          3599: affect the lexical scan.
        !          3600: .PP
        !          3601: This kind of ``backdoor'' approach can be elaborated
        !          3602: to a noxious degree.
        !          3603: Nevertheless, it represents a way of doing some things
        !          3604: that are difficult, if not impossible, to
        !          3605: do otherwise.
        !          3606: .PP
        !          3607: Some programming languages
        !          3608: permit the user to
        !          3609: use words like
        !          3610: .CW if ,
        !          3611: which are normally reserved,
        !          3612: as label or variable names, provided that such use does not
        !          3613: conflict with the legal use of these names in the programming language.
        !          3614: This is extremely hard to do in the framework of \*y;
        !          3615: it is difficult to pass information to the lexical analyzer
        !          3616: telling it ``this instance of 
        !          3617: .CW if
        !          3618: is a keyword, and that instance is a variable''.
        !          3619: The user can make a stab at it, using flags like
        !          3620: .CW dflag ,
        !          3621: above, but it is difficult.
        !          3622: It is better that the keywords be
        !          3623: .I reserved ;
        !          3624: that is, be forbidden for use as variable names.
        !          3625: There are powerful stylistic reasons for preferring this, anyway.
        !          3626: .SS "Support for Arbitrary Attribute Types"
        !          3627: By default, the values returned by actions and
        !          3628: the lexical analyzer are integers.
        !          3629: Other types can be supported by defining
        !          3630: .CW YYSTYPE
        !          3631: in the declarations section, as in
        !          3632: .P{
        !          3633: %{
        !          3634: #define YYSTYPE double
        !          3635: %}
        !          3636: .P}
        !          3637: .CW YYSTYPE
        !          3638: is not a normal variable, because the parser contains the following
        !          3639: lines to define it to be
        !          3640: .CW int
        !          3641: if it has not already been defined by the user:
        !          3642: .P{
        !          3643: #ifndef YYSTYPE
        !          3644: #define YYSTYPE int
        !          3645: #endif
        !          3646: .P}
        !          3647: .PP
        !          3648: Clearly,
        !          3649: .CW YYSTYPE
        !          3650: can be defined to be any type, including a union type.
        !          3651: .PP
        !          3652: The
        !          3653: .CW %union
        !          3654: mechanism of \*y attempts to make the underlying union
        !          3655: transparent, in all but a few places where \*y needs
        !          3656: help in determining which field of the union is intended.
        !          3657: .PP
        !          3658: Unions are declared in the declarations section, an example being
        !          3659: .P{
        !          3660: %union {
        !          3661:     int    ival;
        !          3662:     double dval;
        !          3663:     char * sval;
        !          3664: }
        !          3665: .P}
        !          3666: A union type with these members is created for the \*y value stack,
        !          3667: and for the global variables
        !          3668: .CW yylval
        !          3669: and
        !          3670: .CW yyval .
        !          3671: With the
        !          3672: .CW -d
        !          3673: option, \*y copies the union type into the
        !          3674: .CW y.tab.h
        !          3675: file.
        !          3676: The type of the union can be referred to as
        !          3677: .CW YYSTYPE .
        !          3678: .PP
        !          3679: The type of each attribute must now correspond to one of
        !          3680: the union members.
        !          3681: The construction
        !          3682: .P{
        !          3683: <name>
        !          3684: .P}
        !          3685: indicates a union member name.
        !          3686: If the construction follows
        !          3687: .CW %token ,
        !          3688: .CW %left ,
        !          3689: .CW %right ,
        !          3690: or
        !          3691: .CW %nonassoc ,
        !          3692: then the union member name is associated with the tokens in
        !          3693: that declaration.
        !          3694: Another keyword
        !          3695: .CW %type
        !          3696: is used similarly to associate union member names with nonterminals.
        !          3697: Thus, we might use
        !          3698: .P{
        !          3699: %type <dval> expr term
        !          3700: .P}
        !          3701: .EQ
        !          3702: delim off
        !          3703: .EN
        !          3704: .PP
        !          3705: There remain a couple of cases where these mechanisms are insufficient.
        !          3706: If there is an action within a rule, the value returned
        !          3707: by this action has no a priori type.
        !          3708: Similarly, reference to left context values
        !          3709: leaves \*y with no easy way of knowing the type.
        !          3710: In this case, a type can be imposed on the reference by inserting
        !          3711: a union member name, between
        !          3712: .CW <
        !          3713: and
        !          3714: .CW > ,
        !          3715: immediately after
        !          3716: the first
        !          3717: .CW $
        !          3718: and immediately before the symbol name or number.
        !          3719: An example of this usage is
        !          3720: .P{
        !          3721: rule :  aaa  {  $<intval>$  =  3;  }
        !          3722:         bbb  {  fun( $<intval>2, $<other>0 );  }
        !          3723:      ;
        !          3724: .P}
        !          3725: where the union member names
        !          3726: .CW intval
        !          3727: and
        !          3728: .CW other
        !          3729: are inserted within references.
        !          3730: This syntax has little to recommend it, but the situation arises rarely.
        !          3731: .PP
        !          3732: The facilities in this subsection are not triggered until they are used:
        !          3733: in particular, the use of
        !          3734: .CW %type
        !          3735: will turn on these mechanisms.
        !          3736: When they are used, there is a fairly strict level of checking.
        !          3737: For example, use of
        !          3738: .CW $\f2n\fP
        !          3739: or
        !          3740: .CW $$
        !          3741: to refer to something with no defined type
        !          3742: is diagnosed.
        !          3743: If these facilities are not triggered, the \*y value stack is used to
        !          3744: hold
        !          3745: .CW int s,
        !          3746: as was true historically.
        !          3747: .EQ
        !          3748: delim $$
        !          3749: .EN
        !          3750: .@tag SH _SH8_
        !          3751: .SH _SH8_  "Acknowledgements"
        !          3752: The original acknowledgements, from |reference(v7yacc), are as follows.
        !          3753: ``\*Y owes much to a
        !          3754: most stimulating collection of users, who have goaded
        !          3755: me beyond my inclination, and frequently beyond my
        !          3756: ability, in their endless search for `one more feature'.
        !          3757: Their irritating unwillingness to learn how to
        !          3758: do things my way has usually led to my doing things their way;
        !          3759: most of the time, they have been right.
        !          3760: B. W. Kernighan, P. J. Plauger, S. I. Feldman, C. Imagna,
        !          3761: M. E. Lesk,
        !          3762: and A. Snyder will recognize some of their ideas in the current version
        !          3763: of \*y.
        !          3764: C. B. Haley contributed to the error recovery algorithm.
        !          3765: D. M. Ritchie, B. W. Kernighan, and M. O. Harris helped translate this document into English.
        !          3766: Al Aho also deserves special credit for bringing
        !          3767: the mountain to Mohammed, and other favors.''
        !          3768: .PP
        !          3769: This version of \*y has benefited from thoughtful comments
        !          3770: by B. W. Kernighan, M. F. Fernandez, and M. Tasman.
        !          3771: .NH 1
        !          3772: References
        !          3773: .LP
        !          3774: |reference_placement
        !          3775: .SH "Appendix A" "Yacc Input Syntax"
        !          3776: This appendix has a description of the \*y input syntax, as a \*y specification.
        !          3777: Context dependencies, etc., are not considered.
        !          3778: Ironically, the \*y input specification language
        !          3779: is most naturally specified as an LR(2) grammar; the sticky
        !          3780: part comes when an identifier is seen in a rule, immediately
        !          3781: following an action.
        !          3782: If this identifier is followed by a colon, it is the start of the
        !          3783: next rule; otherwise
        !          3784: it is a continuation of the current rule, which just happens to have
        !          3785: an action embedded in it.
        !          3786: As implemented, the lexical analyzer looks
        !          3787: ahead after seeing an identifier, and
        !          3788: decide whether the next token (skipping blanks, newlines, comments, etc.)
        !          3789: is a colon.
        !          3790: If so, it returns the token
        !          3791: .CW C_IDENTIFIER .
        !          3792: Otherwise, it returns
        !          3793: .CW IDENTIFIER .
        !          3794: Literals (quoted strings) are also returned as
        !          3795: .CW IDENTIFIER s,
        !          3796: but never as part of
        !          3797: .CW C_IDENTIFIER s.
        !          3798: .P{
        !          3799:         /* grammar for the input to \*y */
        !          3800: 
        !          3801:         /* basic entities */
        !          3802: %token  IDENTIFIER     /* includes identifiers and literals */
        !          3803: %token  C_IDENTIFIER   /* identifier (but not literal) followed by colon */
        !          3804: %token  NUMBER         /* [0-9]+ */
        !          3805: 
        !          3806:         /* reserved words: %type => TYPE, %left => LEFT, etc. */
        !          3807: .sp .5
        !          3808: %token LEFT  RIGHT  NONASSOC  TOKEN  PREC  TYPE  START  UNION
        !          3809: .sp .5
        !          3810: %token MARK    /*  the  %%  mark  */
        !          3811: %token LCURL   /*  the  %{  mark  */
        !          3812: %token RCURL   /*  the  %}  mark  */
        !          3813: .sp .5
        !          3814:         /*  ascii  character  literals  stand  for  themselves  */
        !          3815: 
        !          3816: %start  spec
        !          3817: .P} 0
        !          3818: .P{
        !          3819: %%
        !          3820: .sp .5
        !          3821: spec    :  defs  MARK  rules  tail
        !          3822:         ;
        !          3823: .sp .5
        !          3824: tail    :  MARK        {    \f2In  this  action,  eat  up  the  rest  of  the  file\fP    }
        !          3825:         |  /*  empty:  the  second  MARK  is  optional  */
        !          3826:         ;
        !          3827: .sp .5
        !          3828: defs    :  /*  empty  */
        !          3829:         |  defs  def
        !          3830:         ;
        !          3831: .sp .5
        !          3832: def     :  START  IDENTIFIER
        !          3833:         |  UNION  {  \f2Copy union  definition  to  output\fP  }
        !          3834:         |  LCURL  {  \f2Copy  C  code  to  output  file\fP   }  RCURL
        !          3835:         |  ndefs  rword  tag  nlist
        !          3836:         ;
        !          3837: .sp .5
        !          3838: rword  :  TOKEN
        !          3839:         |  LEFT
        !          3840:         |  RIGHT
        !          3841:         |  NONASSOC
        !          3842:         |  TYPE
        !          3843:         ;
        !          3844: tag     :  /*  empty:  union  tag  is  optional  */
        !          3845:         |  \'<\'  IDENTIFIER  \'>\'
        !          3846:         ;
        !          3847: .sp .5
        !          3848: nlist   :  nmno
        !          3849:         |  nlist  nmno
        !          3850:         |  nlist  \',\'  nmno
        !          3851:         ;
        !          3852: .sp .5
        !          3853: nmno    :  IDENTIFIER           /*  NOTE:  literal  illegal  with  %type  */
        !          3854:         |  IDENTIFIER  NUMBER   /*  NOTE:  illegal  with  %type  */
        !          3855:         ;
        !          3856: .P}
        !          3857: .P{
        !          3858:         /*  rules  section  */
        !          3859: .sp .5
        !          3860: rules   :  C_IDENTIFIER  rbody  prec
        !          3861:         |  rules  rule
        !          3862:         ;
        !          3863: .sp .5
        !          3864: rule    :  C_IDENTIFIER  rbody  prec
        !          3865:         |  '|'  rbody  prec
        !          3866:         ;
        !          3867: .sp .5
        !          3868: rbody   :  /*  empty  */
        !          3869:         |  rbody  IDENTIFIER
        !          3870:         |  rbody  act
        !          3871:         ;
        !          3872: .sp .5
        !          3873: act    :  \'{\'  {  \f2Copy  action,  translate  $$,  etc.\fP  }  \'}\'
        !          3874:         ;
        !          3875: .sp .5
        !          3876: prec    :  /*  empty  */
        !          3877:         |  PREC  IDENTIFIER
        !          3878:         |  PREC  IDENTIFIER  act
        !          3879:         |  prec  \';\'
        !          3880:         ;
        !          3881: .P}

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.