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