PROLOG | NAME | SYNOPSIS | DESCRIPTION | OPTIONS | OPERANDS | STDIN | INPUT FILES | ENVIRONMENT VARIABLES | ASYNCHRONOUS EVENTS | STDOUT | STDERR | OUTPUT FILES | EXTENDED DESCRIPTION | EXIT STATUS | CONSEQUENCES OF ERRORS | APPLICATION USAGE | EXAMPLES | RATIONALE | FUTURE DIRECTIONS | SEE ALSO | COPYRIGHT

YACC(1P)                  POSIX Programmer's Manual                 YACC(1P)

PROLOG         top

       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         top

       yacc — yet another compiler compiler (DEVELOPMENT)

SYNOPSIS         top

       yacc [−dltv] [−b file_prefix] [−p sym_prefix] grammar

DESCRIPTION         top

       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(1p)).

OPTIONS         top

       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
                 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 contained in the code
                 file, but by default conditional compilation directives
                 prevent their compilation.

       −v        Write a file containing a description of the parser and a
                 report of conflicts generated by ambiguities in the
                 grammar.

OPERANDS         top

       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         top

       Not used.

INPUT FILES         top

       The file grammar shall be a text file formatted as specified in the
       EXTENDED DESCRIPTION section.

ENVIRONMENT VARIABLES         top

       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 POSIX.1‐2008, Section 8.2, Internationalization
                 Variables 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         top

       Default.

STDOUT         top

       Not used.

STDERR         top

       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         top

       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
       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 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         top

       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
       −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 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 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>, <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.

   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 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‐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 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 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
       various types of values desired.

           %union { body of union (in C) }

       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 %%.

   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 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).

       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
                 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 %%.

   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)
       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 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
           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 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
       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 Analyzer).  If
       it is, the parser shall return with a non-zero value. Otherwise, the
       lookahead symbol shall be discarded and normal parsing shall resume.

       When YYERROR is executed or when the parser detects a syntax error
       and no previous error has been detected, or at least one normal input
       symbol has been shifted since the previous error was detected, the
       parser shall pop back one state at a time until the parse stack is
       empty or the current state allows a shift over error.  If the parser
       empties the parse stack, it shall return with a non-zero value.
       Otherwise, it shall shift over error and then resume normal parsing.
       If the parser reads a 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
       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.

   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
       accessible through the −l y operand to c99; they can therefore be
       redefined by a conforming application:

       int main(void)
             This function shall call yyparse() and exit with an unspecified
             value. Other actions within this function are unspecified.

       int yyerror(const char *s)
             This function shall write the NUL-terminated argument to
             standard error, followed by a <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
       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: 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        │
              │           │         │ specified 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         top

       The following exit values shall be returned:

        0    Successful completion.

       >0    An error occurred.

CONSEQUENCES OF ERRORS         top

       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 produced if the −v flag is present.

       The following sections are informative.

APPLICATION USAGE         top

       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         top

       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         top

       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 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 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 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 example, a parallel make
       program), conflict results. While the solution is not historical
       practice, it corrects a known deficiency in historical
       implementations.  Corresponding changes were made to all sections
       that referenced the filenames y.tab.c (now ``the code file''),
       y.tab.h (now ``the header file''), and y.output (now ``the
       description file'').

       The grammar for yacc input is based on System V documentation. The
       textual description shows there that the ';' is required at the end
       of the rule. The grammar and the implementation do not require this.
       (The use of C_IDENTIFIER causes a reduce to occur in the right
       place.)

       Also, in that implementation, the constructs such as %token can be
       terminated by a <semicolon>, but this is not permitted by the
       grammar. The keywords such as %token can also appear in uppercase,
       which is again not 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
       reference an ISO C standard union member, in practice conforming
       implementations need to support only the set of characters for ISO C
       standard identifiers in this context.

       Some historical implementations are known to accept actions that are
       terminated by a period. Historical implementations often allow '$' in
       names. A conforming implementation does not need to support either of
       these behaviors.

       Deciding when to use %prec illustrates the difficulty in specifying
       the behavior of yacc.  There may be situations in which the grammar
       is not, strictly speaking, in error, and yet yacc cannot interpret it
       unambiguously. The resolution of ambiguities in the grammar can in
       many instances be resolved by providing additional 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 conforming application script
       would be unusual. Furthermore, implementations have not produced
       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 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         top

       None.

SEE ALSO         top

       c99(1p), lex(1p)

       The Base Definitions volume of POSIX.1‐2008, Chapter 8, Environment
       Variables, Section 12.2, Utility Syntax Guidelines

COPYRIGHT         top

       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 Electrical 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.kernel.org/doc/man-pages/reporting_bugs.html .

IEEE/The Open Group                 2013                            YACC(1P)

Pages that refer to this page: cflow(1p)lex(1p)make(1p)