YACC(1P) POSIX Programmer's Manual YACC(1P)
PROLOG
This manual page is part of the POSIX Programmer's Manual. 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, conforming to the ISO C standard, to a
code file, and optionally header information into a header file, in the
current directory. The generated source code shall not depend on any
undefined, unspecified, or implementation-defined behavior, except in
cases where it is copied directly from the supplied grammar, or in
cases that are documented by the implementation. 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
POSIX.1-2008, Section 12.2, Utility Syntax Guidelines, except for
Guideline 9.
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 specified), 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 writ-
ten. 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 con-
structs. If this option is not present, it is unspecified
whether the code file or header file contains #line direc-
tives. 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 vari-
ables 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 permit compila-
tion 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 com-
pilation.
-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 for-
mat 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 specified in the
EXTENDED DESCRIPTION section.
ENVIRONMENT VARIABLES
The following environment variables shall affect the execution of yacc:
LANG Provide a default value for the internationalization vari-
ables that are unset or null. (See the Base Definitions vol-
ume of POSIX.1-2008, Section 8.2, Internationalization Vari-
ables for the precedence of internationalization variables
used to determine the values of locale categories.)
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 messages 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 messages.
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 various semantic actions with macro sub-
stitution performed on them as described in the EXTENDED DESCRIPTION
section. It also shall contain a copy of the #define statements 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 declara-
tion 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 lan-
guage 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-lan-
guage 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 -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 ana-
lyzer function, yylex(); the lex utility is specifically designed to
generate such a routine.
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-sign> characters ("%%"). The declarations
and programs sections can be empty. If the latter is empty, the preced-
ing "%%" mark separating it from the rules section can be omitted.
The input is free form text following the structure of the grammar
defined below.
Lexical Structure of the Grammar
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 let-
ters are distinct. Conforming applications shall not use names begin-
ning 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 cho-
sen 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 con-
stants 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 relationship with each other. In particu-
lar, 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 argu-
ments. 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-2008, 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 pur-
poses 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, num-
ber, 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 prece-
dence or binding strength. %left denotes that the operators on that
line are left associative, and %right similarly denotes right associa-
tive 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 can-
not 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 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 grammar rule; this
default can be overridden with this declaration.
The following declares the yacc value stack to be a union of the vari-
ous types of values desired.
%union { body of union (in C) }
The body of the union shall not contain unbalanced curly brace prepro-
cessing 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 per-
form 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 sec-
tions. The statements shall not contain "%}" outside a comment, string
literal, or multi-character constant.
The application shall ensure that the declarations section is termi-
nated 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 lit-
erals participate in the formation of the grammar; the semantic actions
and precedence rules are used in other ways. The <colon> and the <semi-
colon> 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 <semi-
colon> 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 lexi-
cally 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 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 vari-
ables. 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 cur-
rent 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 deter-
mined, a diagnostic message may be generated.
$<tag>number
These correspond exactly to the corresponding sym-
bols 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-termi-
nal symbol on the left-hand side. The semantic action associ-
ated with the new rule shall be equivalent to the original
action. The use of actions within rules might introduce con-
flicts 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 check-
ing 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 follow-
ing 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 %%.
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 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) con-
flict. 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 sym-
bol, both a shift action and a reduce action are possible. A
reduce/reduce conflict is where, for a given state and lookahead sym-
bol, 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 Declarations 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 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 prece-
dences are the same, then the associativity is used; left associa-
tive implies reduce, right associative implies shift, and non-asso-
ciative 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 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 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 ana-
lyzer 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 "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 recov-
ering 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. Oth-
erwise, 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 Interface to the Lexical 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 sym-
bol 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.
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 associ-
ated 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 cho-
sen by yacc, or chosen by the user. In either case, the #define con-
struct of C is used to allow yylex() to return these numbers symboli-
cally. 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.
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 yyerror(), or those routines can be obtained from the
yacc library.
Yacc Library
The following functions shall appear only in the yacc library accessi-
ble 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 <newline>.
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 runtime. The initial value of yydebug shall be
zero.
When -t is specified, the code file shall be built such that, if YYDE-
BUG is not already defined at compilation time (using the c99 -D YYDE-
BUG 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: 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 information in the description file shall always be pro-
duced 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 override 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 different
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
operator. (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 following 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 Referenced Documents 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 volume of POSIX.1-2008. Work in this area
continues 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 impractically 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 generated.
There has been confusion between the class of grammars, the algorithms
needed to generate parsers, and the algorithms needed to parse the lan-
guages. They are all reasonably orthogonal. In particular, a parser
generator that accepts the full range of LR(1) grammars need not gener-
ate 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 implementation need not recognize the case, either; table com-
pression 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 compression (or the code generation if a direct parser is gener-
ated) 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 original Knuth article algorithms
for constructing LR parsers were judged by its author to be impracti-
cally 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 Pen-
nello 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, par-
ticularly 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 historical practice,
it corrects a known deficiency in historical implementations. Corre-
sponding changes were made to all sections that referenced the file-
names 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 documentation. The tex-
tual 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 ter-
minated 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 discussed. In most places where '%' is used, <backslash> 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. However, since the tag must refer-
ence an ISO C standard union member, in practice conforming implementa-
tions 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 unambigu-
ously. The resolution of ambiguities in the grammar can in many
instances be resolved by providing additional information, 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 appropri-
ate.
The size and execution time of a program produced without the runtime
debugging code is usually smaller and slightly faster in historical
implementations.
Statistics messages from several historical implementations 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 implemen-
tation-defined because all aspects of these limits are also implementa-
tion-defined. Some implementations may use dynamic allocation tech-
niques 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 list-
ing 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 out-
put and no popular format was apparent. The format selected by the
implementation 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 applications and there was no reason to
restrict implementations.
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 POSIX.1-2008 chose to
leave it as obsolete and omit it.
Multi-byte characters should be recognized by the lexical 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
The Base Definitions volume of POSIX.1-2008, Chapter 8, Environment
Variables, Section 12.2, Utility Syntax Guidelines
COPYRIGHT
Portions of this text are reprinted and reproduced in electronic form
from IEEE Std 1003.1, 2013 Edition, Standard for Information Technology
-- Portable Operating System Interface (POSIX), The Open Group Base
Specifications Issue 7, Copyright (C) 2013 by the Institute of Electri-
cal and Electronics Engineers, Inc and The Open Group. (This is
POSIX.1-2008 with the 2013 Technical Corrigendum 1 applied.) 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.unix.org/online.html .
Any typographical or formatting errors that appear in this page are
most likely to have been introduced during the conversion of the source
files to man page format. To report such errors, see https://www.ker-
nel.org/doc/man-pages/reporting_bugs.html .
IEEE/The Open Group 2013 YACC(1P)
Linux-Distributionen
Huschi als Linux-Admin