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