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 associated semantic action. The code to be
executed shall appear as bodies of text that are intended to be C-language code. These bodies of text
shall not contain C-language trigraphs. 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 compiled 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 -ly 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 routine.
InputLanguage
The application shall ensure that every specification file consists of three sections in order:
declarations, grammarrules, and programs, separated by double <percent-sign> characters ("%%"). The
declarations and programs sections can be empty. If the latter is empty, the preceding "%%" mark
separating it from the rules section can be omitted.
The input is free form text following the structure of the grammar defined below.
LexicalStructureoftheGrammar
The <blank>, <newline>, and <form-feed> character 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, periods ('.'), underscores ('_'), and non-initial
digits. Uppercase and lowercase letters are distinct. Conforming 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-quote characters. 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.
DeclarationsSection
The declarations section is used to define the symbols used to define the target language and their
relationship with each other. In particular, much of the additional information required to resolve
ambiguities in the context-free grammar for the target language is provided here.
Usually yacc assigns the relationship between the symbolic 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 associated 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 grammar. 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
preceded 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 POSIX.1‐2017, 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 underlying 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 symbols, 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 binding 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
declaration 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 startsymbol, 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 grammar rule; this default can be overridden with this
declaration.
The following declares the yacc value stack to be a union of the various types of values desired.
%union { bodyofunion (inC) }
The body of the union shall not contain unbalanced curly brace preprocessing tokens.
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 corresponding 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 declaration 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 statements shall not contain "%}" outside a comment, string
literal, or multi-character constant.
The application shall ensure that the declarations section is terminated by the token %%.
GrammarRulesinyacc
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 semanticactions that can then be followed by optional precedencerules. Only the names
and literals participate in the formation of the grammar; the semantic 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-line> ('|') 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).
semanticaction
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 values 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 values
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 '}'. The statements shall not contain unbalanced curly brace preprocessing tokens.
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 determined, a diagnostic message
may be generated.
$number This refers to the value returned by the component specified by the token number in
the right side of a rule, reading from left to right; number 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 bottom 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 particularly 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
symbolic representation, but need to be given different 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 literal. The action for the rule as a whole can follow %prec.
If a program section follows, the application shall ensure that the grammar rules are terminated by %%.
ProgramsSection
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.
InputGrammar
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; LexicalStructureoftheGrammar defines most terms. The
correspondence 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 integer).
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
conflicts 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 language accepted by the parser to be much
different from that which was intended. The description file shall contain 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 DeclarationsSection) are used to resolve parsing
conflicts as follows:
1. A precedence and associativity is associated with each grammar rule; it is the precedence and
associativity 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 output described in ErrorHandling.
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
ErrorHandling.
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.
ErrorHandling
The token error shall be reserved for error handling. The name error can be used in grammar rules. It
indicates 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 YYERROR. 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
"syntaxerror" 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 syntax 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
preceding error was detected, the parser checks if the lookahead symbol is an endmarker (see InterfacetotheLexicalAnalyzer). 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 lookahead
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 previous 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.
InterfacetotheLexicalAnalyzer
The yylex() function is an integer-valued function that returns a tokennumber 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 current 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 characters 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 declarations.
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 negative 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.
CompletingtheProgram
In addition to yyparse() and yylex(), the functions yyerror() and main() are required to make a complete
program. The application can supply main() and yyerror(), or those routines can be obtained from the yacc
library.
YaccLibrary
The following functions shall appear only in the yacc library accessible through the -ly operand to c99;
they can therefore be redefined by a conforming application:
intmain(void)
This function shall call yyparse() and exit with an unspecified value. Other actions within this
function are unspecified.
intyyerror(constchar *s)
This function shall write the NUL-terminated argument to standard error, followed by a <newline>.
The order of the -ly and -ll operands given to c99 is significant; the application shall either provide
its own main() function or ensure that -ly precedes -ll.
DebuggingtheParser
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 intyydebug can be used to turn
debugging on (with a non-zero value) and off (zero value) at runtime. 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 explicitly 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
following 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 generate should it run out of space for any internal structure. An implementation may
combine groups of these resources into a single pool as long as the total available to the user does not
fall below the sum of the sizes specified by this section.
Table:InternalLimitsinyacc
┌────────────┬─────────┬────────────────────────────────┐
│ │ 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 │
│ │ │ specified in GrammarRulesin │
│ │ │ 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 │
│ │ │ GrammarRulesinyacc. │
└────────────┴─────────┴────────────────────────────────┘
Install Now
PNG Icons
Emojis