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