yacc.html

IEEE 1003.1-2003, Single Unix Specification v3

<pre>
<tt>%token</tt> <b>[</b><tt>&lt;</tt><i>tag</i><tt>&gt;</tt><b>]</b> <i>name</i> <b>[</b><i>number</i><b>][</b><i>name</i> <b>[</b><i>number</i><b>]]</b><tt>...
</tt>
</pre>

<p>If <i>tag</i> is present, the C type for all tokens on this line shall be declared to be the type referenced by <i>tag</i>. If a
positive integer, <i>number</i>, follows a <i>name</i>, that value shall be assigned to the token.</p>

<p>The following declares <i>name</i> to be a token, and assigns precedence to it:</p>

<pre>
<tt>%left</tt> <b>[</b><tt>&lt;</tt><i>tag</i><tt>&gt;</tt><b>]</b> <i>name</i> <b>[</b><i>number</i><b>][</b><i>name</i> <b>[</b><i>number</i><b>]]</b><tt>...
%right</tt> <b>[</b><tt>&lt;</tt><i>tag</i><tt>&gt;</tt><b>]</b> <i>name</i> <b>[</b><i>number</i><b>][</b><i>name</i> <b>[</b><i>number</i><b>]]</b><tt>...
</tt>
</pre>

<p>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. <b>%left</b> denotes
that the operators on that line are left associative, and <b>%right</b> similarly denotes right associative operators. If
<i>tag</i> is present, it shall declare a C type for <i>name</i>s as described for <b>%token</b>.</p>

<p>The following declares <i>name</i> to be a token, and indicates that this cannot be used associatively:</p>

<pre>
<tt>%nonassoc</tt> <b>[</b><tt>&lt;</tt><i>tag</i><tt>&gt;</tt><b>]</b> <i>name</i> <b>[</b><i>number</i><b>][</b><i>name</i> <b>[</b><i>number</i><b>]]</b><tt>...
</tt>
</pre>

<p>If the parser encounters associative use of this token it reports an error. If <i>tag</i> is present, it shall declare a C type
for <i>name</i>s as described for <b>%token</b>.</p>

<p>The following declares that union member <i>name</i>s are non-terminals, and thus it is required to have a <i>tag</i> field at
its beginning:</p>

<pre>
<tt>%type &lt;</tt><i>tag</i><tt>&gt;</tt> <i>name</i><tt>...
</tt>
</pre>

<p>Because it deals with non-terminals only, assigning a token number or using a literal is also prohibited. If this construct is
present, <i>yacc</i> shall perform type checking; if this construct is not present, the parse stack shall hold only the <b>int</b>
type.</p>

<p>Every name used in <i>grammar</i> not defined by a <b>%token</b>, <b>%left</b>, <b>%right</b>, or <b>%nonassoc</b> declaration
is assumed to represent a non-terminal symbol. The <i>yacc</i> utility shall report an error for any non-terminal symbol that does
not appear on the left side of at least one grammar rule.</p>

<p>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, <i>yacc</i> shall assign a token number. Once this assignment is made, the token number shall not
be changed by explicit assignment.</p>

<p>The following declarators do not follow the previous pattern.</p>

<p>The following declares the non-terminal <i>name</i> to be the <i>start symbol</i>, which represents the largest, most general
structure described by the grammar rules:</p>

<pre>
<tt>%start</tt> <i>name</i>
</pre>

<p>By default, it is the left-hand side of the first grammar rule; this default can be overridden with this declaration.</p>

<p>The following declares the <i>yacc</i> value stack to be a union of the various types of values desired:</p>

<pre>
<tt>%union {</tt> <i>body of union</i> <tt>(</tt><i>in C</i><tt>) }
</tt>
</pre>

<p>By default, the values returned by actions (see below) and the lexical analyzer shall be of type <b>int</b>. The <i>yacc</i>
utility keeps track of types, and it shall insert corresponding union member names in order to perform strict type checking of the
resulting parser.</p>

<p>Alternatively, given that at least one &lt;<i>tag</i>&gt; construct is used, the union can be declared in a header file (which
shall be included in the declarations section by using a <b>#include</b> construct within <b>%{</b> and <b>%}</b>), and a
<b>typedef</b> used to define the symbol YYSTYPE to represent this union. The effect of <b>%union</b> is to provide the declaration
of YYSTYPE directly from the <i>yacc</i> input.</p>

<p>C-language declarations and definitions can appear in the declarations section, enclosed by the following marks:</p>

<pre>
<tt>%{ ... %}
</tt>
</pre>

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

<p>The application shall ensure that the declarations section is terminated by the token <b>%%</b>.</p>

<h5><a name="tag_04_174_13_04"></a>Grammar Rules in yacc</h5>

<p>The rules section defines the context-free grammar to be accepted by the function <i>yacc</i> generates, and associates with
those rules C-language actions and additional precedence information. The grammar is described below, and a formal definition
follows.</p>

<p>The rules section is comprised of one or more grammar rules. A grammar rule has the form:</p>

<pre>
<tt>A : BODY ;
</tt>
</pre>

<p>The symbol <b>A</b> represents a non-terminal name, and <b>BODY</b> represents a sequence of zero or more <i>name</i>s,
<i>literal</i>s, and <i>semantic action</i>s that can then be followed by optional <i>precedence rule</i>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 <i>yacc</i> punctuation. If there are several successive grammar rules with the same left-hand side, the
vertical bar <tt>'|'</tt> 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.</p>

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

<p>The elements comprising a BODY are:</p>

<dl compact>
<dt><i>name</i>,&nbsp;<i>literal</i></dt>

<dd>These form the rules of the grammar: <i>name</i> is either a <i>token</i> or a <i>non-terminal</i>; <i>literal</i> stands for
itself (less the lexically required quotation marks).</dd>

<dt><i>semantic action</i></dt>

<dd><br>
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 &quot;action&quot; can also refer to the actions of the parser-shift, reduce, and so on.) 

<p>These actions can return values and can obtain the values returned by previous actions. These values are kept in objects of type
YYSTYPE (see <b>%union</b>). 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 &lt;<i>tag</i>&gt; information provided in the
declarations section, the code generated by <i>yacc</i> 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.</p>

<p>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 <tt>'{'</tt> and <tt>'}'</tt> .</p>

<p>Certain pseudo-variables can be used in the action. These are macros for access to data structures known internally to
<i>yacc</i>.</p>

<dl compact>
<dt>$$</dt>

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

<dt>$<i>number</i></dt>

<dd>This refers to the value returned by the component specified by the token <i>number</i> in the right side of a rule, reading
from left to right; <i>number</i> can be zero or negative. If <i>number</i> 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, <tt>"$0"</tt> refers to the name
immediately preceding the leftmost name in the current rule to be found on the parser's stack and <tt>"$-1"</tt> refers to the
symbol to <i>its</i> left.) If <i>number</i> 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.</dd>

<dt>$&lt;<i>tag</i>&gt;<i>number</i></dt>

<dd><br>
These correspond exactly to the corresponding symbols without the <i>tag</i> inclusion, but allow for strict type checking (and
preclude unwanted type conversions). The effect is that the macro is expanded to use <i>tag</i> to select an element from the
YYSTYPE union (using <i>dataname.tag</i>). This is particularly useful if <i>number</i> is not positive.</dd>

<dt>$&lt;<i>tag</i>&gt;$</dt>

<dd>This imposes on the reference the type of the union member referenced by <i>tag</i>. This construction is applicable when a
reference to a left context value occurs in the grammar, and provides <i>yacc</i> with a means for selecting a type.</dd>
</dl>

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

<p>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 <b>%type</b>, an error message shall result.</p>
</dd>

<dt><i>precedence</i></dt>

<dd>The keyword <b>%prec</b> 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 <b>%prec</b> 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 <b>%prec</b>.</dd>
</dl>

<p>If a program section follows, the application shall ensure that the grammar rules are terminated by <b>%%</b>.</p>

<h5><a name="tag_04_174_13_05"></a>Programs Section</h5>

<p>The <i>programs</i> section can include the definition of the lexical analyzer <i>yylex</i>(), 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 <tt>"%{&nbsp;...&nbsp;%}"</tt> in the
declarations section.</p>

<h5><a name="tag_04_174_13_06"></a>Input Grammar</h5>

<p>The following input to <i>yacc</i> yields a parser for the input to <i>yacc</i>. This formal syntax takes precedence over the
preceding text syntax description.</p>

<p>The lexical structure is defined less precisely; <a href="#tag_04_174_13_02">Lexical Structure of the Grammar</a> defines most
terms. The correspondence between the previous terms and the tokens below is as follows.</p>

<dl compact>
<dt><b>IDENTIFIER</b></dt>

<dd>This corresponds to the concept of <i>name</i>, given previously. It also includes literals as defined previously.</dd>

<dt><b>C_IDENTIFIER</b></dt>

<dd>This is a name, and additionally it is known to be followed by a colon. A literal cannot yield this token.</dd>

<dt><b>NUMBER</b></dt>

<dd>A string of digits (a non-negative decimal integer).</dd>

<dt><b>TYPE</b>,&nbsp;<b>LEFT</b>,&nbsp;<b>MARK</b>,&nbsp;<b>LCURL</b>,&nbsp;<b>RCURL</b></dt>

<dd><br>
These correspond directly to <b>%type</b>, <b>%left</b>, <b>%%</b>, <b>%{</b>, and <b>%}</b>.</dd>

<dt><b>{&nbsp;...&nbsp;}</b></dt>

<dd>This indicates C-language source code, with the possible inclusion of <tt>'$'</tt> macros as discussed previously.</dd>
</dl>

<pre>
<tt>/* Grammar for the input to yacc. */
/* Basic entries. */
/* The following are recognized by the lexical analyzer. */
<br>
%token    IDENTIFIER      /* Includes identifiers and literals */
%token    C_IDENTIFIER    /* identifier (but not literal)
                             followed by a :. */
%token    NUMBER          /* [0-9][0-9]* */
<br>
/* Reserved words : %type=&gt;TYPE %left=&gt;LEFT, and so on */
<br>
%token    LEFT RIGHT NONASSOC TOKEN PREC TYPE START UNION
<br>
%token    MARK            /* The %% mark. */
%token    LCURL           /* The %{ mark. */
%token    RCURL           /* The %} mark. */
<br>
/* 8-bit character literals stand for themselves; */
/* tokens have to be defined for multi-byte characters. */
<br>
%start    spec
<br>
%%
<br>
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. */