yacc - phpMan

YACC(P) YACC(P)

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 option-
ally 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 exe-
cutes a parsing algorithm meeting the requirements in Algorithms .

The form and meaning of the grammar are described in the EXTENDED DESCRIPTION sec-
tion.

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 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 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 permit compilation of debugging
code in the code file. Runtime debugging statements shall always be con-
tained 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 con-
flicts 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 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 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 interna-
tionalization 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 char-
acters 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 con-
tain code for the various semantic actions with macro substitution 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 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 inter-
nal tables (see Limits ) shall also be reported, in an implementation-defined man-
ner. (Some implementations may use dynamic allocation techniques and have no spe-
cific 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 lan-
guage 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-language 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 compiled output requires linking with externally sup-
plied 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 routine.

Input Language
The application shall ensure that every specification file consists of three sec-
tions in order: declarations, grammar rules, and programs, separated by double per-
cent 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 omitted.

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 appli-
cation 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. 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 relationship 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 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 con-
trol the assignment of these values.

It is also possible to keep semantic information associated with the tokens cur-
rently 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 sec-
tion 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 conven-
tions 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 fol-
lowed 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 num-
ber.

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 associativ-
ity; 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 start symbol, which repre-
sents 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 { 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
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 sym-
bol YYSTYPE to represent this union. The effect of %union is to provide the decla-
ration 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 section 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 semantic actions and precedence rules are used in other ways. The
colon and the semicolon are yacc punctuation. If there are several successive gram-
mar 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-termi-
nal; 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 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 gener-
ated 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 sub-
programs, 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 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 inclu-
sion, but allow for strict type checking (and preclude unwanted type conver-
sions). 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 con-
struction 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 %%.

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 syn-
tax 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) 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 pos-
sible.

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 suffi-
cient 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 con-
flict 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 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 analyzer should not return the value of error.

The parser shall detect a syntax error when it is in a state where the action asso-
ciated 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 exe-
cuted, 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 char-
acter 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 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 Interface to the Lexical Ana-
lyzer ). 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. Other-
wise, 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 rep-
resenting 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 communica-
tion 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 iden-
tifier is larger than that permitted by C. Token names found to contain such char-
acters 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; other-
wise, 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 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 applica-
tion:

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 applica-
tion 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 YYDE-
BUG, 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 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 docu-
mented 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 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 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 may be helpful in constructing the parser generator. The refer-
enced DeRemer and Pennello article (along with the works it references) describes a
technique to generate parsers that conform to this volume of IEEE Std 1003.1-2001.
Work in this area continues to be done, so implementors should consult current lit-
erature 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 algorithms needed to parse the languages. They are all
reasonably 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 implementation need not recognize the case, either; table
compression can yield the SLR(1) table (or one even smaller than that) without rec-
ognizing 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 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 original 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 exam-
ple, a parallel make program), conflict results. While the solution is not histor-
ical practice, it corrects a known deficiency in historical implementations. Corre-
sponding 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 documentation. The textual
description shows there that the â€â€™;â€â€™ is required at the end of the rule. The gram-
mar 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 discussed. 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. However, 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 imple-
mentation 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 ambigui-
ties 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 appropriate.

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 implementation-
defined because all aspects of these limits are also implementation-defined. Some
implementations 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 conform-
ing application script would be unusual. Furthermore, implementations have not pro-
duced consistent output 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 his-
torical 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 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.