yacc.html

IEEE 1003.1-2003, Single Unix Specification v3

      | '<' IDENTIFIER '>'
      ;
nlist : nmno
      | nlist nmno
      ;
nmno  : IDENTIFIER         /* Note: literal invalid with % type. */
      | IDENTIFIER NUMBER  /* Note: invalid with % type. */
      ;
<br>
/* Rule section */
<br>
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 ';'
      ;
</tt>
</pre>

<h5><a name="tag_04_174_13_07"></a>Conflicts</h5>

<p>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 <i>yacc</i> utility shall resolve all
conflicts, using either default rules or user-specified precedence rules.</p>

<p>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.</p>

<p>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.</p>

<p>The declared precedences and associativities (see <a href="#tag_04_174_13_03">Declarations Section</a> ) are used to resolve
parsing conflicts as follows:</p>

<ol>
<li>
<p>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 <b>%prec</b> keyword is used, it overrides this default. Some grammar rules might not have
both precedence and associativity.</p>
</li>

<li>
<p>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.</p>
</li>

<li>
<p>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 <a href="#tag_04_174_13_08">Error Handling</a> .</p>
</li>

<li>
<p>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 <a href="#tag_04_174_13_08">Error Handling</a> .</p>
</li>
</ol>

<p>Conflicts resolved by precedence or associativity shall not be counted in the shift/reduce and reduce/reduce conflicts reported
by <i>yacc</i> on either standard error or in the description file.</p>

<h5><a name="tag_04_174_13_08"></a>Error Handling</h5>

<p>The token <b>error</b> shall be reserved for error handling. The name <b>error</b> can be used in grammar rules. It indicates
places where the parser can recover from a syntax error. The default value of <b>error</b> shall be 256. Its value can be changed
using a <b>%token</b> declaration. The lexical analyzer should not return the value of <b>error</b>.</p>

<p>The parser shall detect a syntax error when it is in a state where the action associated with the lookahead symbol is
<b>error</b>. 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.</p>

<p>When the parser detects a syntax error, it normally calls <i>yyerror</i>() with the character string
<tt>"syntax&nbsp;error"</tt> 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 <i>yyerrok</i>. The
parser shall not call <i>yyerror</i>() when YYERROR is executed.</p>

<p>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.</p>

<p>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 <a href="#tag_04_174_13_09">Interface to the Lexical Analyzer</a> ). If it is,
the parser shall return with a non-zero value. Otherwise, the lookahead symbol shall be discarded and normal parsing shall
resume.</p>

<p>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 <b>error</b>. If the parser empties the parse stack, it shall return
with a non-zero value. Otherwise, it shall shift over <b>error</b> 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.</p>

<p>The macro <i>yyerrok</i> in a semantic action shall cause the parser to act as if it has fully recovered from any previous
errors. The macro <i>yyclearin</i> shall cause the parser to discard the current lookahead token. If the current lookahead token
has not yet been read, <i>yyclearin</i> shall have no effect.</p>

<p>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.</p>

<h5><a name="tag_04_174_13_09"></a>Interface to the Lexical Analyzer</h5>

<p>The <i>yylex</i>() function is an integer-valued function that returns a <i>token number</i> representing the kind of token
read. If there is a value associated with the token returned by <i>yylex</i>() (see the discussion of <i>tag</i> above), it shall
be assigned to the external variable <i>yylval</i>.</p>

<p>If the parser and <i>yylex</i>() 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 <i>yacc</i>, or chosen by the user. In either case, the <b>#define</b> construct of C is
used to allow <i>yylex</i>() to return these numbers symbolically. The <b>#define</b> statements are put into the code file, and
the header file if that file is requested. The set of characters permitted by <i>yacc</i> in an identifier is larger than that
permitted by C. Token names found to contain such characters shall not be included in the <b>#define</b> declarations.</p>

<p>If the token numbers are chosen by <i>yacc</i>, 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
<i>yacc</i> 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, <i>yacc</i> shall report an error; otherwise, it is unspecified whether the token
assignment is accepted or an error is reported.</p>

<p>The end of the input is marked by a special token called the <i>endmarker</i>, 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.</p>

<h5><a name="tag_04_174_13_10"></a>Completing the Program</h5>

<p>In addition to <i>yyparse</i>() and <i>yylex</i>(), the functions <i>yyerror</i>() and <i>main</i>() are required to make a
complete program. The application can supply <i>main</i>() and <i>yyerror</i>(), or those routines can be obtained from the
<i>yacc</i> library.</p>

<h5><a name="tag_04_174_13_11"></a>Yacc Library</h5>

<p>The following functions shall appear only in the <i>yacc</i> library accessible through the <b>-l&nbsp;y</b> operand to <a href=
"../utilities/c99.html"><i>c99</i></a>; they can therefore be redefined by a conforming application:</p>

<dl compact>
<dt><b>int&nbsp;</b> <i>main</i>(<b>void</b>)</dt>

<dd><br>
This function shall call <i>yyparse</i>() and exit with an unspecified value. Other actions within this function are
unspecified.</dd>

<dt><b>int&nbsp;</b> <i>yyerror</i>(<b>const&nbsp;char</b>&nbsp;*<i>s</i>)</dt>

<dd><br>
This function shall write the NUL-terminated argument to standard error, followed by a &lt;newline&gt;.</dd>
</dl>

<p>The order of the <b>-l&nbsp;y</b> and <b>-l&nbsp;l</b> operands given to <a href="../utilities/c99.html"><i>c99</i></a> is
significant; the application shall either provide its own <i>main</i>() function or ensure that <b>-l&nbsp;y</b> precedes
<b>-l&nbsp;l</b>.</p>

<h5><a name="tag_04_174_13_12"></a>Debugging the Parser</h5>

<p>The parser generated by <i>yacc</i> 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.</p>

<p>In parsers where the debugging code has been included, the external <b>int</b> <i>yydebug</i> can be used to turn debugging on
(with a non-zero value) and off (zero value) at runtime. The initial value of <i>yydebug</i> shall be zero.</p>

<p>When <b>-t</b> is specified, the code file shall be built such that, if YYDEBUG is not already defined at compilation time
(using the <a href="../utilities/c99.html"><i>c99</i></a> <b>-D</b> YYDEBUG option, for example), YYDEBUG shall be set explicitly
to 1. When <b>-t</b> is not specified, the code file shall be built such that, if YYDEBUG is not already defined, it shall be set
explicitly to zero.</p>

<p>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.</p>

<h5><a name="tag_04_174_13_13"></a>Algorithms</h5>

<p>The parser constructed by <i>yacc</i> implements an LALR(1) parsing algorithm as documented in the literature. It is unspecified
whether the parser is table-driven or direct-coded.</p>

<p>A parser generated by <i>yacc</i> shall never request an input symbol from <i>yylex</i>() while in a state where the only
actions other than the error action are reductions by a single rule.</p>

<p>The literature of parsing theory defines these concepts.</p>

<h5><a name="tag_04_174_13_14"></a>Limits</h5>

<p>The <i>yacc</i> 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.<br>
</p>

<center><b>Table: Internal Limits in <i>yacc</i></b></center>

<center>
<table border="1" cellpadding="3" align="center">
<tr valign="top">
<th align="center">
<p class="tent"><b>&nbsp;</b></p>
</th>
<th align="center">
<p class="tent"><b>Minimum</b></p>
</th>
<th align="center">
<p class="tent"><b>&nbsp;</b></p>
</th>
</tr>

<tr valign="top">
<th align="center">
<p class="tent"><b>Limit</b></p>
</th>
<th align="center">
<p class="tent"><b>Maximum</b></p>
</th>
<th align="center">
<p class="tent"><b>Description</b></p>
</th>
</tr>

<tr valign="top">
<td align="left">
<p class="tent">{NTERMS}</p>
</td>
<td align="left">
<p class="tent">126</p>
</td>
<td align="left">
<p class="tent">Number of tokens.</p>
</td>
</tr>

<tr valign="top">
<td align="left">
<p class="tent">{NNONTERM}</p>
</td>
<td align="left">
<p class="tent">200</p>
</td>
<td align="left">
<p class="tent">Number of non-terminals.</p>
</td>
</tr>

<tr valign="top">
<td align="left">
<p class="tent">{NPROD}</p>
</td>
<td align="left">
<p class="tent">300</p>
</td>
<td align="left">
<p class="tent">Number of rules.</p>
</td>
</tr>

<tr valign="top">
<td align="left">
<p class="tent">{NSTATES}</p>
</td>
<td align="left">
<p class="tent">600</p>
</td>
<td align="left">
<p class="tent">Number of states.</p>
</td>
</tr>