# yacc

## PROLOG



           This manual page is part of the POSIX Programmer's Manual.  The
           Linux implementation of this interface may differ (consult the
           corresponding Linux manual page for details of Linux behavior), or
           the interface may not be implemented on Linux.
    


## NAME



           yacc — yet another compiler compiler (**DEVELOPMENT**)
    


## SYNOPSIS



           yacc **[** -dltv**] [** -b _file_prefix_**] [** -p _sym_prefix_**]**_grammar_
    


## DESCRIPTION



           The _yacc_ utility shall read a description of a context-free
           grammar in _grammar_ and write C source code, conforming to the
           ISO C standard, to a code file, and optionally header information
           into a header file, in the current directory. The generated source
           code shall not depend on any undefined, unspecified, or
           implementation-defined behavior, except in cases where it is
           copied directly from the supplied grammar, or in cases that are
           documented by the implementation. The C code shall define a
           function and related routines and macros for an automaton that
           executes a parsing algorithm meeting the requirements in
           _Algorithms_.
    
           The form and meaning of the grammar are described in the EXTENDED
           DESCRIPTION section.
    
           The C source code and header file shall be produced in a form
           suitable as input for the C compiler (see c99(1p)).
    


## OPTIONS



           The _yacc_ utility shall conform to the Base Definitions volume of
           POSIX.1‐2017, _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. See the OUTPUT FILES section.
    
           **-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



           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 POSIX.1‐2017, _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



           Default.
    


## STDOUT



           Not used.
    


## STDERR



           If shift/reduce or reduce/reduce conflicts are detected in
           _grammar_ , _yacc_ shall write a report of those conflicts to the
           standard error in an unspecified format.
    
           Standard error shall also be used for diagnostic messages.
    


## OUTPUT FILES



           The code file, the header file, and the description file shall be
           text files. All are described in the following sections.
    
       **Code File**
           This file shall contain the C source code for the _yyparse_()
           function. It shall contain code for the various semantic actions
           with macro 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



           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‐2017, in this case <_tag_ > does not represent
           a metavariable, but the literal angle bracket characters
           surrounding a symbol.) The use of _tag_ specifies that the tokens
           named on this line shall be of the same C type as the union member
           referenced by _tag_.  This is discussed in more detail below.
    
           For lists used to define tokens, the first appearance of a given
           token can be followed by a positive integer (as a string of
           decimal digits).  If this is done, the underlying value assigned
           to it for lexical purposes shall be taken to be that number.
    
           The following declares _name_ to be a token:
    
               %token **[** <_tag_ >**]**_name_ **[**_number_**] [**_name_ **[**_number_**]]**...
    
           If _tag_ is present, the C type for all tokens on this line shall be
           declared to be the type referenced by _tag_.  If a positive integer,
           _number_ , follows a _name_ , that value shall be assigned to the token.
    
           The following declares _name_ to be a token, and assigns precedence
           to it:
    
               %left **[** <_tag_ >**]**_name_ **[**_number_**] [**_name_ **[**_number_**]]**...
               %right **[** <_tag_ >**]**_name_ **[**_number_**] [**_name_ **[**_number_**]]**...
    
           One or more lines, each beginning with one of these symbols, can
           appear in this section. All tokens on the same line have the same
           precedence level and associativity; the lines are in order of
           increasing precedence or binding strength.  **%left** denotes that the
           operators on that line are left associative, and **%right** similarly
           denotes right associative operators. If _tag_ is present, it shall
           declare a C type for _name_ s 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 _name_ s
           as described for **%token**.
    
           The following declares that union member _name_ s 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 _name_ s, _literal_ s, and _semantic action_ s
           that can then be followed by optional _precedence rule_ s.  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



           The following exit values shall be returned:
    
            0    Successful completion.
    
           >0    An error occurred.
    


## CONSEQUENCES OF ERRORS



           If any errors are encountered, the run is aborted and _yacc_ exits
           with a non-zero status. Partial code files and header files may be
           produced. The summary information in the description file shall
           always be 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 **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‐2017. 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‐2017 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.
    


* * *