1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
|
YACC(1P) POSIX Programmer's Manual YACC(1P)
PROLOG
This manual page is part of the POSIX Programmer's Man-
ual. The Linux implementation of this interface may
differ (consult the corresponding Linux manual page for
details of Linux behavior), or the interface may not be
implemented on Linux.
NAME
yacc - yet another compiler compiler (DEVELOPMENT)
SYNOPSIS
yacc [-dltv][-b file_prefix][-p sym_prefix] grammar
DESCRIPTION
The yacc utility shall read a description of a context-
free grammar in grammar and write C source code, con-
forming to the ISO C standard, to a code file, and
optionally header information into a header file, in the
current directory. The C code shall define a function
and related routines and macros for an automaton that
executes a parsing algorithm meeting the requirements in
Algorithms .
The form and meaning of the grammar are described in the
EXTENDED DESCRIPTION section.
The C source code and header file shall be produced in a
form suitable as input for the C compiler (see c99 ).
OPTIONS
The yacc utility shall conform to the Base Definitions
volume of IEEE Std 1003.1-2001, Section 12.2, Utility
Syntax Guidelines.
The following options shall be supported:
-b file_prefix
Use file_prefix instead of y as the prefix for
all output filenames. The code file y.tab.c, the
header file y.tab.h (created when -d is speci-
fied), and the description file y.output (created
when -v is specified), shall be changed to
file_prefix .tab.c, file_prefix .tab.h, and
file_prefix .output, respectively.
-d Write the header file; by default only the code
file is written. The #define statements associate
the token codes assigned by yacc with the user-
declared token names. This allows source files
other than y.tab.c to access the token codes.
-l Produce a code file that does not contain any
#line constructs. If this option is not present,
it is unspecified whether the code file or header
file contains #line directives. This should only
be used after the grammar and the associated
actions are fully debugged.
-p sym_prefix
Use sym_prefix instead of yy as the prefix for
all external names produced by yacc. The names
affected shall include the functions yyparse(),
yylex(), and yyerror(), and the variables yylval,
yychar, and yydebug. (In the remainder of this
section, the six symbols cited are referenced
using their default names only as a notational
convenience.) Local names may also be affected by
the -p option; however, the -p option shall not
affect #define symbols generated by yacc.
-t Modify conditional compilation directives to per-
mit compilation of debugging code in the code
file. Runtime debugging statements shall always
be contained in the code file, but by default
conditional compilation directives prevent their
compilation.
-v Write a file containing a description of the
parser and a report of conflicts generated by
ambiguities in the grammar.
OPERANDS
The following operand is required:
grammar
A pathname of a file containing instructions,
hereafter called grammar, for which a parser is
to be created. The format for the grammar is
described in the EXTENDED DESCRIPTION section.
STDIN
Not used.
INPUT FILES
The file grammar shall be a text file formatted as spec-
ified in the EXTENDED DESCRIPTION section.
ENVIRONMENT VARIABLES
The following environment variables shall affect the
execution of yacc:
LANG Provide a default value for the internationaliza-
tion variables that are unset or null. (See the
Base Definitions volume of IEEE Std 1003.1-2001,
Section 8.2, Internationalization Variables for
the precedence of internationalization variables
used to determine the values of locale cate-
gories.)
LC_ALL If set to a non-empty string value, override the
values of all the other internationalization
variables.
LC_CTYPE
Determine the locale for the interpretation of
sequences of bytes of text data as characters
(for example, single-byte as opposed to multi-
byte characters in arguments and input files).
LC_MESSAGES
Determine the locale that should be used to
affect the format and contents of diagnostic mes-
sages written to standard error.
NLSPATH
Determine the location of message catalogs for
the processing of LC_MESSAGES .
The LANG and LC_* variables affect the execution of the
yacc utility as stated. The main() function defined in
Yacc Library shall call:
setlocale(LC_ALL, "")
and thus the program generated by yacc shall also be
affected by the contents of these variables at runtime.
ASYNCHRONOUS EVENTS
Default.
STDOUT
Not used.
STDERR
If shift/reduce or reduce/reduce conflicts are detected
in grammar, yacc shall write a report of those conflicts
to the standard error in an unspecified format.
Standard error shall also be used for diagnostic mes-
sages.
OUTPUT FILES
The code file, the header file, and the description file
shall be text files. All are described in the following
sections.
Code File
This file shall contain the C source code for the
yyparse() function. It shall contain code for the vari-
ous semantic actions with macro substitution performed
on them as described in the EXTENDED DESCRIPTION sec-
tion. It also shall contain a copy of the #define state-
ments in the header file. If a %union declaration is
used, the declaration for YYSTYPE shall also be included
in this file.
Header File
The header file shall contain #define statements that
associate the token numbers with the token names. This
allows source files other than the code file to access
the token codes. If a %union declaration is used, the
declaration for YYSTYPE and an extern YYSTYPE yylval
declaration shall also be included in this file.
Description File
The description file shall be a text file containing a
description of the state machine corresponding to the
parser, using an unspecified format. Limits for internal
tables (see Limits ) shall also be reported, in an
implementation-defined manner. (Some implementations may
use dynamic allocation techniques and have no specific
limit values to report.)
EXTENDED DESCRIPTION
The yacc command accepts a language that is used to
define a grammar for a target language to be parsed by
the tables and code generated by yacc. The language
accepted by yacc as a grammar for the target language is
described below using the yacc input language itself.
The input grammar includes rules describing the input
structure of the target language and code to be invoked
when these rules are recognized to provide the associ-
ated semantic action. The code to be executed shall
appear as bodies of text that are intended to be C-lan-
guage code. The C-language inclusions are presumed to
form a correct function when processed by yacc into its
output files. The code included in this way shall be
executed during the recognition of the target language.
Given a grammar, the yacc utility generates the files
described in the OUTPUT FILES section. The code file can
be compiled and linked using c99. If the declaration and
programs sections of the grammar file did not include
definitions of main(), yylex(), and yyerror(), the com-
piled output requires linking with externally supplied
versions of those functions. Default versions of main()
and yyerror() are supplied in the yacc library and can
be linked in by using the -l y operand to c99. The yacc
library interfaces need not support interfaces with
other than the default yy symbol prefix. The application
provides the lexical analyzer function, yylex(); the lex
utility is specifically designed to generate such a rou-
tine.
Input Language
The application shall ensure that every specification
file consists of three sections in order: declarations,
grammar rules, and programs, separated by double percent
signs ( "%%" ). The declarations and programs sections
can be empty. If the latter is empty, the preceding "%%"
mark separating it from the rules section can be omit-
ted.
The input is free form text following the structure of
the grammar defined below.
Lexical Structure of the Grammar
The <blank>s, <newline>s, and <form-feed>s shall be
ignored, except that the application shall ensure that
they do not appear in names or multi-character reserved
symbols. Comments shall be enclosed in "/* ... */", and
can appear wherever a name is valid.
Names are of arbitrary length, made up of letters, peri-
ods ( '.' ), underscores ( '_' ), and non-initial dig-
its. Uppercase and lowercase letters are distinct. Con-
forming applications shall not use names beginning in yy
or YY since the yacc parser uses such names. Many of the
names appear in the final output of yacc, and thus they
should be chosen to conform with any additional rules
created by the C compiler to be used. In particular they
appear in #define statements.
A literal shall consist of a single character enclosed
in single-quotes ( '" ). All of the escape sequences
supported for character constants by the ISO C standard
shall be supported by yacc.
The relationship with the lexical analyzer is discussed
in detail below.
The application shall ensure that the NUL character is
not used in grammar rules or literals.
Declarations Section
The declarations section is used to define the symbols
used to define the target language and their relation-
ship with each other. In particular, much of the addi-
tional information required to resolve ambiguities in
the context-free grammar for the target language is pro-
vided here.
Usually yacc assigns the relationship between the sym-
bolic names it generates and their underlying numeric
value. The declarations section makes it possible to
control the assignment of these values.
It is also possible to keep semantic information associ-
ated with the tokens currently on the parse stack in a
user-defined C-language union, if the members of the
union are associated with the various names in the gram-
mar. The declarations section provides for this as well.
The first group of declarators below all take a list of
names as arguments. That list can optionally be pre-
ceded by the name of a C union member (called a tag
below) appearing within '<' and '>' . (As an exception
to the typographical conventions of the rest of this
volume of IEEE Std 1003.1-2001, in this case <tag> does
not represent a metavariable, but the literal angle
bracket characters surrounding a symbol.) The use of tag
specifies that the tokens named on this line shall be of
the same C type as the union member referenced by tag.
This is discussed in more detail below.
For lists used to define tokens, the first appearance of
a given token can be followed by a positive integer (as
a string of decimal digits). If this is done, the under-
lying value assigned to it for lexical purposes shall be
taken to be that number.
The following declares name to be a token:
%token [<tag>] name [number][name [number]]...
If tag is present, the C type for all tokens on this
line shall be declared to be the type referenced by tag.
If a positive integer, number, follows a name, that
value shall be assigned to the token.
The following declares name to be a token, and assigns
precedence to it:
%left [<tag>] name [number][name [number]]...
%right [<tag>] name [number][name [number]]...
One or more lines, each beginning with one of these sym-
bols, can appear in this section. All tokens on the same
line have the same precedence level and associativity;
the lines are in order of increasing precedence or bind-
ing strength. %left denotes that the operators on that
line are left associative, and %right similarly denotes
right associative operators. If tag is present, it shall
declare a C type for names as described for %token.
The following declares name to be a token, and indicates
that this cannot be used associatively:
%nonassoc [<tag>] name [number][name [number]]...
If the parser encounters associative use of this token
it reports an error. If tag is present, it shall declare
a C type for names as described for %token.
The following declares that union member names are non-
terminals, and thus it is required to have a tag field
at its beginning:
%type <tag> name...
Because it deals with non-terminals only, assigning a
token number or using a literal is also prohibited. If
this construct is present, yacc shall perform type
checking; if this construct is not present, the parse
stack shall hold only the int type.
Every name used in grammar not defined by a %token,
%left, %right, or %nonassoc declaration is assumed to
represent a non-terminal symbol. The yacc utility shall
report an error for any non-terminal symbol that does
not appear on the left side of at least one grammar
rule.
Once the type, precedence, or token number of a name is
specified, it shall not be changed. If the first decla-
ration of a token does not assign a token number, yacc
shall assign a token number. Once this assignment is
made, the token number shall not be changed by explicit
assignment.
The following declarators do not follow the previous
pattern.
The following declares the non-terminal name to be the
start symbol, which represents the largest, most general
structure described by the grammar rules:
%start name
By default, it is the left-hand side of the first gram-
mar rule; this default can be overridden with this dec-
laration.
The following declares the yacc value stack to be a
union of the various types of values desired:
%union { body of union (in C) }
By default, the values returned by actions (see below)
and the lexical analyzer shall be of type int. The yacc
utility keeps track of types, and it shall insert corre-
sponding union member names in order to perform strict
type checking of the resulting parser.
Alternatively, given that at least one <tag> construct
is used, the union can be declared in a header file
(which shall be included in the declarations section by
using a #include construct within %{ and %}), and a
typedef used to define the symbol YYSTYPE to represent
this union. The effect of %union is to provide the dec-
laration of YYSTYPE directly from the yacc input.
C-language declarations and definitions can appear in
the declarations section, enclosed by the following
marks:
%{ ... %}
These statements shall be copied into the code file, and
have global scope within it so that they can be used in
the rules and program sections.
The application shall ensure that the declarations sec-
tion is terminated by the token %%.
Grammar Rules in yacc
The rules section defines the context-free grammar to be
accepted by the function yacc generates, and associates
with those rules C-language actions and additional
precedence information. The grammar is described below,
and a formal definition follows.
The rules section is comprised of one or more grammar
rules. A grammar rule has the form:
A : BODY ;
The symbol A represents a non-terminal name, and BODY
represents a sequence of zero or more names, literals,
and semantic actions that can then be followed by
optional precedence rules. Only the names and literals
participate in the formation of the grammar; the seman-
tic actions and precedence rules are used in other ways.
The colon and the semicolon are yacc punctuation. If
there are several successive grammar rules with the same
left-hand side, the vertical bar '|' can be used to
avoid rewriting the left-hand side; in this case the
semicolon appears only after the last rule. The BODY
part can be empty (or empty of names and literals) to
indicate that the non-terminal symbol matches the empty
string.
The yacc utility assigns a unique number to each rule.
Rules using the vertical bar notation are distinct
rules. The number assigned to the rule appears in the
description file.
The elements comprising a BODY are:
name, literal
These form the rules of the grammar: name is
either a token or a non-terminal; literal stands
for itself (less the lexically required quotation
marks).
semantic action
With each grammar rule, the user can associate
actions to be performed each time the rule is
recognized in the input process. (Note that the
word "action" can also refer to the actions of
the parser-shift, reduce, and so on.)
These actions can return values and can obtain the val-
ues returned by previous actions. These values are kept
in objects of type YYSTYPE (see %union). The result
value of the action shall be kept on the parse stack
with the left-hand side of the rule, to be accessed by
other reductions as part of their right-hand side. By
using the <tag> information provided in the declarations
section, the code generated by yacc can be strictly type
checked and contain arbitrary information. In addition,
the lexical analyzer can provide the same kinds of val-
ues for tokens, if desired.
An action is an arbitrary C statement and as such can do
input or output, call subprograms, and alter external
variables. An action is one or more C statements
enclosed in curly braces '{' and '}' .
Certain pseudo-variables can be used in the action.
These are macros for access to data structures known
internally to yacc.
$$
The value of the action can be set by assigning
it to $$. If type checking is enabled and the
type of the value to be assigned cannot be deter-
mined, a diagnostic message may be generated.
$number
This refers to the value returned by the compo-
nent specified by the token number in the right
side of a rule, reading from left to right; num-
ber can be zero or negative. If number is zero or
negative, it refers to the data associated with
the name on the parser's stack preceding the
leftmost symbol of the current rule. (That is,
"$0" refers to the name immediately preceding the
leftmost name in the current rule to be found on
the parser's stack and "$-1" refers to the symbol
to its left.) If number refers to an element past
the current point in the rule, or beyond the bot-
tom of the stack, the result is undefined. If
type checking is enabled and the type of the
value to be assigned cannot be determined, a
diagnostic message may be generated.
$<tag>number
These correspond exactly to the corresponding
symbols without the tag inclusion, but allow for
strict type checking (and preclude unwanted type
conversions). The effect is that the macro is
expanded to use tag to select an element from the
YYSTYPE union (using dataname.tag). This is par-
ticularly useful if number is not positive.
$<tag>$
This imposes on the reference the type of the
union member referenced by tag. This construction
is applicable when a reference to a left context
value occurs in the grammar, and provides yacc
with a means for selecting a type.
Actions can occur anywhere in a rule (not just at the
end); an action can access values returned by actions to
its left, and in turn the value it returns can be
accessed by actions to its right. An action appearing
in the middle of a rule shall be equivalent to replacing
the action with a new non-terminal symbol and adding an
empty rule with that non-terminal symbol on the left-
hand side. The semantic action associated with the new
rule shall be equivalent to the original action. The use
of actions within rules might introduce conflicts that
would not otherwise exist.
By default, the value of a rule shall be the value of
the first element in it. If the first element does not
have a type (particularly in the case of a literal) and
type checking is turned on by %type, an error message
shall result.
precedence
The keyword %prec can be used to change the
precedence level associated with a particular
grammar rule. Examples of this are in cases where
a unary and binary operator have the same sym-
bolic representation, but need to be given dif-
ferent precedences, or where the handling of an
ambiguous if-else construction is necessary. The
reserved symbol %prec can appear immediately
after the body of the grammar rule and can be
followed by a token name or a literal. It shall
cause the precedence of the grammar rule to
become that of the following token name or lit-
eral. The action for the rule as a whole can fol-
low %prec.
If a program section follows, the application shall
ensure that the grammar rules are terminated by %%.
Programs Section
The programs section can include the definition of the
lexical analyzer yylex(), and any other functions; for
example, those used in the actions specified in the
grammar rules. It is unspecified whether the programs
section precedes or follows the semantic actions in the
output file; therefore, if the application contains any
macro definitions and declarations intended to apply to
the code in the semantic actions, it shall place them
within "%{ ... %}" in the declarations section.
Input Grammar
The following input to yacc yields a parser for the
input to yacc. This formal syntax takes precedence over
the preceding text syntax description.
The lexical structure is defined less precisely; Lexical
Structure of the Grammar defines most terms. The corre-
spondence between the previous terms and the tokens
below is as follows.
IDENTIFIER
This corresponds to the concept of name, given
previously. It also includes literals as defined
previously.
C_IDENTIFIER
This is a name, and additionally it is known to
be followed by a colon. A literal cannot yield
this token.
NUMBER A string of digits (a non-negative decimal inte-
ger).
TYPE, LEFT, MARK, LCURL, RCURL
These correspond directly to %type, %left, %%,
%{, and %}.
{ ... }
This indicates C-language source code, with the
possible inclusion of '$' macros as discussed
previously.
/* Grammar for the input to yacc. */
/* Basic entries. */
/* The following are recognized by the lexical analyzer. */
%token IDENTIFIER /* Includes identifiers and literals */
%token C_IDENTIFIER /* identifier (but not literal)
followed by a :. */
%token NUMBER /* [0-9][0-9]* */
/* Reserved words : %type=>TYPE %left=>LEFT, and so on */
%token LEFT RIGHT NONASSOC TOKEN PREC TYPE START UNION
%token MARK /* The %% mark. */
%token LCURL /* The %{ mark. */
%token RCURL /* The %} mark. */
/* 8-bit character literals stand for themselves; */
/* tokens have to be defined for multi-byte characters. */
%start spec
%%
spec : defs MARK rules tail
;
tail : MARK
{
/* In this action, set up the rest of the file. */
}
| /* Empty; the second MARK is optional. */
;
defs : /* Empty. */
| defs def
;
def : START IDENTIFIER
| UNION
{
/* Copy union definition to output. */
}
| LCURL
{
/* Copy C code to output file. */
}
RCURL
| rword tag nlist
;
rword : TOKEN
| LEFT
| RIGHT
| NONASSOC
| TYPE
;
tag : /* Empty: union tag ID optional. */
| '<' IDENTIFIER '>'
;
nlist : nmno
| nlist nmno
;
nmno : IDENTIFIER /* Note: literal invalid with % type. */
| IDENTIFIER NUMBER /* Note: invalid with % type. */
;
/* Rule section */
rules : C_IDENTIFIER rbody prec
| rules rule
;
rule : C_IDENTIFIER rbody prec
| '|' rbody prec
;
rbody : /* empty */
| rbody IDENTIFIER
| rbody act
;
act : '{'
{
/* Copy action, translate $$, and so on. */
}
'}'
;
prec : /* Empty */
| PREC IDENTIFIER
| PREC IDENTIFIER act
| prec ';'
;
Conflicts
The parser produced for an input grammar may contain
states in which conflicts occur. The conflicts occur
because the grammar is not LALR(1). An ambiguous grammar
always contains at least one LALR(1) conflict. The yacc
utility shall resolve all conflicts, using either
default rules or user-specified precedence rules.
Conflicts are either shift/reduce conflicts or
reduce/reduce conflicts. A shift/reduce conflict is
where, for a given state and lookahead symbol, both a
shift action and a reduce action are possible. A
reduce/reduce conflict is where, for a given state and
lookahead symbol, reductions by two different rules are
possible.
The rules below describe how to specify what actions to
take when a conflict occurs. Not all shift/reduce con-
flicts can be successfully resolved this way because the
conflict may be due to something other than ambiguity,
so incautious use of these facilities can cause the lan-
guage accepted by the parser to be much different from
that which was intended. The description file shall con-
tain sufficient information to understand the cause of
the conflict. Where ambiguity is the reason either the
default or explicit rules should be adequate to produce
a working parser.
The declared precedences and associativities (see Decla-
rations Section ) are used to resolve parsing conflicts
as follows:
1. A precedence and associativity is associated with
each grammar rule; it is the precedence and associa-
tivity of the last token or literal in the body of
the rule. If the %prec keyword is used, it overrides
this default. Some grammar rules might not have both
precedence and associativity.
2. If there is a shift/reduce conflict, and both the
grammar rule and the input symbol have precedence
and associativity associated with them, then the
conflict is resolved in favor of the action (shift
or reduce) associated with the higher precedence. If
the precedences are the same, then the associativity
is used; left associative implies reduce, right
associative implies shift, and non-associative
implies an error in the string being parsed.
3. When there is a shift/reduce conflict that cannot be
resolved by rule 2, the shift is done. Conflicts
resolved this way are counted in the diagnostic out-
put described in Error Handling .
4. When there is a reduce/reduce conflict, a reduction
is done by the grammar rule that occurs earlier in
the input sequence. Conflicts resolved this way are
counted in the diagnostic output described in Error
Handling .
Conflicts resolved by precedence or associativity shall
not be counted in the shift/reduce and reduce/reduce
conflicts reported by yacc on either standard error or
in the description file.
Error Handling
The token error shall be reserved for error handling.
The name error can be used in grammar rules. It indi-
cates places where the parser can recover from a syntax
error. The default value of error shall be 256. Its
value can be changed using a %token declaration. The
lexical analyzer should not return the value of error.
The parser shall detect a syntax error when it is in a
state where the action associated with the lookahead
symbol is error. A semantic action can cause the parser
to initiate error handling by executing the macro YYER-
ROR. When YYERROR is executed, the semantic action
passes control back to the parser. YYERROR cannot be
used outside of semantic actions.
When the parser detects a syntax error, it normally
calls yyerror() with the character string "syntax error"
as its argument. The call shall not be made if the
parser is still recovering from a previous error when
the error is detected. The parser is considered to be
recovering from a previous error until the parser has
shifted over at least three normal input symbols since
the last error was detected or a semantic action has
executed the macro yyerrok. The parser shall not call
yyerror() when YYERROR is executed.
The macro function YYRECOVERING shall return 1 if a syn-
tax error has been detected and the parser has not yet
fully recovered from it. Otherwise, zero shall be
returned.
When a syntax error is detected by the parser, the
parser shall check if a previous syntax error has been
detected. If a previous error was detected, and if no
normal input symbols have been shifted since the preced-
ing error was detected, the parser checks if the looka-
head symbol is an endmarker (see Interface to the Lexi-
cal Analyzer ). If it is, the parser shall return with a
non-zero value. Otherwise, the lookahead symbol shall be
discarded and normal parsing shall resume.
When YYERROR is executed or when the parser detects a
syntax error and no previous error has been detected, or
at least one normal input symbol has been shifted since
the previous error was detected, the parser shall pop
back one state at a time until the parse stack is empty
or the current state allows a shift over error. If the
parser empties the parse stack, it shall return with a
non-zero value. Otherwise, it shall shift over error and
then resume normal parsing. If the parser reads a looka-
head symbol before the error was detected, that symbol
shall still be the lookahead symbol when parsing is
resumed.
The macro yyerrok in a semantic action shall cause the
parser to act as if it has fully recovered from any pre-
vious errors. The macro yyclearin shall cause the parser
to discard the current lookahead token. If the current
lookahead token has not yet been read, yyclearin shall
have no effect.
The macro YYACCEPT shall cause the parser to return with
the value zero. The macro YYABORT shall cause the parser
to return with a non-zero value.
Interface to the Lexical Analyzer
The yylex() function is an integer-valued function that
returns a token number representing the kind of token
read. If there is a value associated with the token
returned by yylex() (see the discussion of tag above),
it shall be assigned to the external variable yylval.
If the parser and yylex() do not agree on these token
numbers, reliable communication between them cannot
occur. For (single-byte character) literals, the token
is simply the numeric value of the character in the cur-
rent character set. The numbers for other tokens can
either be chosen by yacc, or chosen by the user. In
either case, the #define construct of C is used to allow
yylex() to return these numbers symbolically. The
#define statements are put into the code file, and the
header file if that file is requested. The set of char-
acters permitted by yacc in an identifier is larger than
that permitted by C. Token names found to contain such
characters shall not be included in the #define declara-
tions.
If the token numbers are chosen by yacc, the tokens
other than literals shall be assigned numbers greater
than 256, although no order is implied. A token can be
explicitly assigned a number by following its first
appearance in the declarations section with a number.
Names and literals not defined this way retain their
default definition. All token numbers assigned by yacc
shall be unique and distinct from the token numbers used
for literals and user-assigned tokens. If duplicate
token numbers cause conflicts in parser generation, yacc
shall report an error; otherwise, it is unspecified
whether the token assignment is accepted or an error is
reported.
The end of the input is marked by a special token called
the endmarker, which has a token number that is zero or
negative. (These values are invalid for any other
token.) All lexical analyzers shall return zero or nega-
tive as a token number upon reaching the end of their
input. If the tokens up to, but excluding, the endmarker
form a structure that matches the start symbol, the
parser shall accept the input. If the endmarker is seen
in any other context, it shall be considered an error.
Completing the Program
In addition to yyparse() and yylex(), the functions
yyerror() and main() are required to make a complete
program. The application can supply main() and yyer-
ror(), or those routines can be obtained from the yacc
library.
Yacc Library
The following functions shall appear only in the yacc
library accessible through the -l y operand to c99; they
can therefore be redefined by a conforming application:
int main(void)
This function shall call yyparse() and exit with
an unspecified value. Other actions within this
function are unspecified.
int yyerror(const char *s)
This function shall write the NUL-terminated
argument to standard error, followed by a <new-
line>.
The order of the -l y and -l l operands given to c99 is
significant; the application shall either provide its
own main() function or ensure that -l y precedes -l l.
Debugging the Parser
The parser generated by yacc shall have diagnostic
facilities in it that can be optionally enabled at
either compile time or at runtime (if enabled at compile
time). The compilation of the runtime debugging code is
under the control of YYDEBUG, a preprocessor symbol. If
YYDEBUG has a non-zero value, the debugging code shall
be included. If its value is zero, the code shall not be
included.
In parsers where the debugging code has been included,
the external int yydebug can be used to turn debugging
on (with a non-zero value) and off (zero value) at run-
time. The initial value of yydebug shall be zero.
When -t is specified, the code file shall be built such
that, if YYDEBUG is not already defined at compilation
time (using the c99 -D YYDEBUG option, for example),
YYDEBUG shall be set explicitly to 1. When -t is not
specified, the code file shall be built such that, if
YYDEBUG is not already defined, it shall be set explic-
itly to zero.
The format of the debugging output is unspecified but
includes at least enough information to determine the
shift and reduce actions, and the input symbols. It also
provides information about error recovery.
Algorithms
The parser constructed by yacc implements an LALR(1)
parsing algorithm as documented in the literature. It is
unspecified whether the parser is table-driven or
direct-coded.
A parser generated by yacc shall never request an input
symbol from yylex() while in a state where the only
actions other than the error action are reductions by a
single rule.
The literature of parsing theory defines these concepts.
Limits
The yacc utility may have several internal tables. The
minimum maximums for these tables are shown in the fol-
lowing table. The exact meaning of these values is
implementation-defined. The implementation shall define
the relationship between these values and between them
and any error messages that the implementation may gen-
erate should it run out of space for any internal struc-
ture. An implementation may combine groups of these
resources into a single pool as long as the total avail-
able to the user does not fall below the sum of the
sizes specified by this section.
Table: Internal Limits in yacc
Minimum
Limit Maximum Description
{NTERMS} 126 Number of tokens.
{NNONTERM} 200 Number of non-terminals.
{NPROD} 300 Number of rules.
{NSTATES} 600 Number of states.
{MEMSIZE} 5200 Length of rules. The total length, in
names (tokens and non-terminals), of all
the rules of the grammar. The left-hand
side is counted for each rule, even if
it is not explicitly repeated, as speci-
fied in Grammar Rules in yacc .
{ACTSIZE} 4000 Number of actions. "Actions" here (and
in the description file) refer to parser
actions (shift, reduce, and so on) not
to semantic actions defined in Grammar
Rules in yacc .
EXIT STATUS
The following exit values shall be returned:
0 Successful completion.
>0 An error occurred.
CONSEQUENCES OF ERRORS
If any errors are encountered, the run is aborted and
yacc exits with a non-zero status. Partial code files
and header files may be produced. The summary informa-
tion in the description file shall always be produced if
the -v flag is present.
The following sections are informative.
APPLICATION USAGE
Historical implementations experience name conflicts on
the names yacc.tmp, yacc.acts, yacc.debug, y.tab.c,
y.tab.h, and y.output if more than one copy of yacc is
running in a single directory at one time. The -b option
was added to overcome this problem. The related problem
of allowing multiple yacc parsers to be placed in the
same file was addressed by adding a -p option to over-
ride the previously hard-coded yy variable prefix.
The description of the -p option specifies the minimal
set of function and variable names that cause conflict
when multiple parsers are linked together. YYSTYPE does
not need to be changed. Instead, the programmer can use
-b to give the header files for different parsers dif-
ferent names, and then the file with the yylex() for a
given parser can include the header for that parser.
Names such as yyclearerr do not need to be changed
because they are used only in the actions; they do not
have linkage. It is possible that an implementation has
other names, either internal ones for implementing
things such as yyclearerr, or providing non-standard
features that it wants to change with -p.
Unary operators that are the same token as a binary
operator in general need their precedence adjusted. This
is handled by the %prec advisory symbol associated with
the particular grammar rule defining that unary opera-
tor. (See Grammar Rules in yacc .) Applications are not
required to use this operator for unary operators, but
the grammars that do not require it are rare.
EXAMPLES
Access to the yacc library is obtained with library
search operands to c99. To use the yacc library main():
c99 y.tab.c -l y
Both the lex library and the yacc library contain
main(). To access the yacc main():
c99 y.tab.c lex.yy.c -l y -l l
This ensures that the yacc library is searched first, so
that its main() is used.
The historical yacc libraries have contained two simple
functions that are normally coded by the application
programmer. These functions are similar to the follow-
ing code:
#include <locale.h>
int main(void)
{
extern int yyparse();
setlocale(LC_ALL, "");
/* If the following parser is one created by lex, the
application must be careful to ensure that LC_CTYPE
and LC_COLLATE are set to the POSIX locale. */
(void) yyparse();
return (0);
}
#include <stdio.h>
int yyerror(const char *msg)
{
(void) fprintf(stderr, "%s\n", msg);
return (0);
}
RATIONALE
The references in may be helpful in constructing the
parser generator. The referenced DeRemer and Pennello
article (along with the works it references) describes a
technique to generate parsers that conform to this vol-
ume of IEEE Std 1003.1-2001. Work in this area contin-
ues to be done, so implementors should consult current
literature before doing any new implementations. The
original Knuth article is the theoretical basis for this
kind of parser, but the tables it generates are imprac-
tically large for reasonable grammars and should not be
used. The "equivalent to" wording is intentional to
assure that the best tables that are LALR(1) can be gen-
erated.
There has been confusion between the class of grammars,
the algorithms needed to generate parsers, and the algo-
rithms needed to parse the languages. They are all rea-
sonably orthogonal. In particular, a parser generator
that accepts the full range of LR(1) grammars need not
generate a table any more complex than one that accepts
SLR(1) (a relatively weak class of LR grammars) for a
grammar that happens to be SLR(1). Such an implementa-
tion need not recognize the case, either; table compres-
sion can yield the SLR(1) table (or one even smaller
than that) without recognizing that the grammar is
SLR(1). The speed of an LR(1) parser for any class is
dependent more upon the table representation and com-
pression (or the code generation if a direct parser is
generated) than upon the class of grammar that the table
generator handles.
The speed of the parser generator is somewhat dependent
upon the class of grammar it handles. However, the orig-
inal Knuth article algorithms for constructing LR
parsers were judged by its author to be impractically
slow at that time. Although full LR is more complex than
LALR(1), as computer speeds and algorithms improve, the
difference (in terms of acceptable wall-clock execution
time) is becoming less significant.
Potential authors are cautioned that the referenced
DeRemer and Pennello article previously cited identifies
a bug (an over-simplification of the computation of
LALR(1) lookahead sets) in some of the LALR(1) algorithm
statements that preceded it to publication. They should
take the time to seek out that paper, as well as current
relevant work, particularly Aho's.
The -b option was added to provide a portable method for
permitting yacc to work on multiple separate parsers in
the same directory. If a directory contains more than
one yacc grammar, and both grammars are constructed at
the same time (by, for example, a parallel make pro-
gram), conflict results. While the solution is not his-
torical practice, it corrects a known deficiency in his-
torical implementations. Corresponding changes were made
to all sections that referenced the filenames y.tab.c
(now "the code file"), y.tab.h (now "the header file"),
and y.output (now "the description file").
The grammar for yacc input is based on System V documen-
tation. The textual description shows there that the
';' is required at the end of the rule. The grammar and
the implementation do not require this. (The use of
C_IDENTIFIER causes a reduce to occur in the right
place.)
Also, in that implementation, the constructs such as
%token can be terminated by a semicolon, but this is not
permitted by the grammar. The keywords such as %token
can also appear in uppercase, which is again not dis-
cussed. In most places where '%' is used, '\' can be
substituted, and there are alternate spellings for some
of the symbols (for example, %LEFT can be "%<" or even
"\<" ).
Historically, <tag> can contain any characters except
'>', including white space, in the implementation. How-
ever, since the tag must reference an ISO C standard
union member, in practice conforming implementations
need to support only the set of characters for ISO C
standard identifiers in this context.
Some historical implementations are known to accept
actions that are terminated by a period. Historical
implementations often allow '$' in names. A conforming
implementation does not need to support either of these
behaviors.
Deciding when to use %prec illustrates the difficulty in
specifying the behavior of yacc. There may be situations
in which the grammar is not, strictly speaking, in
error, and yet yacc cannot interpret it unambiguously.
The resolution of ambiguities in the grammar can in many
instances be resolved by providing additional informa-
tion, such as using %type or %union declarations. It is
often easier and it usually yields a smaller parser to
take this alternative when it is appropriate.
The size and execution time of a program produced with-
out the runtime debugging code is usually smaller and
slightly faster in historical implementations.
Statistics messages from several historical implementa-
tions include the following types of information:
n/512 terminals, n/300 non-terminals
n/600 grammar rules, n/1500 states
n shift/reduce, n reduce/reduce conflicts reported
n/350 working sets used
Memory: states, etc. n/15000, parser n/15000
n/600 distinct lookahead sets
n extra closures
n shift entries, n exceptions
n goto entries
n entries saved by goto default
Optimizer space used: input n/15000, output n/15000
n table entries, n zero
Maximum spread: n, Maximum offset: n
The report of internal tables in the description file is
left implementation-defined because all aspects of these
limits are also implementation-defined. Some implementa-
tions may use dynamic allocation techniques and have no
specific limit values to report.
The format of the y.output file is not given because
specification of the format was not seen to enhance
applications portability. The listing is primarily
intended to help human users understand and debug the
parser; use of y.output by a conforming application
script would be unusual. Furthermore, implementations
have not produced consistent output and no popular for-
mat was apparent. The format selected by the implementa-
tion should be human-readable, in addition to the
requirement that it be a text file.
Standard error reports are not specifically described
because they are seldom of use to conforming applica-
tions and there was no reason to restrict implementa-
tions.
Some implementations recognize "={" as equivalent to '{'
because it appears in historical documentation. This
construction was recognized and documented as obsolete
as long ago as 1978, in the referenced Yacc: Yet Another
Compiler-Compiler. This volume of IEEE Std 1003.1-2001
chose to leave it as obsolete and omit it.
Multi-byte characters should be recognized by the lexi-
cal analyzer and returned as tokens. They should not be
returned as multi-byte character literals. The token
error that is used for error recovery is normally
assigned the value 256 in the historical implementation.
Thus, the token value 256, which is used in many multi-
byte character sets, is not available for use as the
value of a user-defined token.
FUTURE DIRECTIONS
None.
SEE ALSO
c99, lex
COPYRIGHT
Portions of this text are reprinted and reproduced in
electronic form from IEEE Std 1003.1, 2003 Edition,
Standard for Information Technology -- Portable Operat-
ing System Interface (POSIX), The Open Group Base Speci-
fications Issue 6, Copyright (C) 2001-2003 by the Insti-
tute of Electrical and Electronics Engineers, Inc and
The Open Group. In the event of any discrepancy between
this version and the original IEEE and The Open Group
Standard, the original IEEE and The Open Group Standard
is the referee document. The original Standard can be
obtained online at http://www.open-
group.org/unix/online.html .
IEEE/The Open Group 2003 YACC(1P)
|