yacc.html

unix 下的C开发手册,还用详细的例程。

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 will be
equivalent to the original action.
The use of actions within rules might
introduce conflicts that would not otherwise exist.
<p>
By default, the value of a rule is 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 will result.
<p>
<dt><i>precedence</i><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 will 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>.
<p>
</dl>
<p>
If a program section follows, the grammar rules must be terminated by
<b>%%</b>.
<h5><a name = "tag_001_014_2954_005">&nbsp;</a>Programs Section</h5>
<xref type="5" name="yaccprog"></xref>
The <i>programs</i> section can
include the definition of the lexical analyser
<i>yylex()</i>,
and any other functions, for example those used in the
actions specified in the grammar rules.
This is C-language code, and will be included in
the code file after the tables and code generated by
<i>yacc</i>.
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 must place them within
<b>%{...%}</b>
in the declarations section.
<h5><a name = "tag_001_014_2954_006">&nbsp;</a>Input Grammar</h5>
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>
The lexical structure is defined less precisely;
<xref href=yacclex><a href="#tag_001_014_2954_002">
Lexical Structure of the Grammar
</a></xref>
defines most terms.
The correspondence
between the previous terms and the tokens below is as follows.
<dl compact>

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

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

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

<dt><b>TYPE</b><dd>
<dt><b>LEFT</b><dd>
<dt><b>MARK</b><dd>
<dt>and so on<dd>
These correspond directly to
<b>%type</b>,
<b>%left</b>,
<b>%%</b>
and so on.

<dt><b>{ </b>...<b> }</b><dd>This indicates C-language source code, with the possible inclusion of
"$" macros as discussed previously.

</dl>
<pre>
<code>
/* Grammar for the input to yacc */
/* Basic entries */
/* The following are recognised by the lexical analyser */

%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=&gt;TYPE %left=&gt;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 */
      | '&lt;' IDENTIFIER '&gt;'
      ;
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 ';'
      ;
</code>
</pre>
<h5><a name = "tag_001_014_2954_007">&nbsp;</a>Conflicts</h5>
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 will resolve all conflicts, using either
default rules or user-specified precedence rules.
<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>
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
will 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>
The declared precedences and associativities (see
<xref href=yaccdecl><a href="#tag_001_014_2954_003">
Declarations Section
</a></xref>)
are used to resolve parsing conflicts as follows:
<ol>
<p>
<li>
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>
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
favour 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>
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
<xref href=yaccerr><a href="#tag_001_014_2954_008">
Error Handling
</a></xref>.
<p>
<li>
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
<xref href=yaccerr><a href="#tag_001_014_2954_008">
Error Handling
</a></xref>.
<p>
</ol>
<p>
Conflicts resolved by precedence
or associativity will 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.
<br>
<h5><a name = "tag_001_014_2954_008">&nbsp;</a>Error Handling</h5>
<xref type="5" name="yaccerr"></xref>
The token
<b>error</b>
is 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>
is 256.
Its value can be changed using a
<b>%token</b>
declaration.
The lexical analyser should not return the value of
<b>error</b>.
(Multi-byte characters should be recognised by
the lexical analyser and returned as tokens.
They should not be returned as multi-byte character literals.
The token
<b>error</b>
that is used for error recovery is normally assigned
the value 256 in the historical implementation.
Thus, the token value 256, which used in many
multi-byte character sets, is not available for
use as the value of a user-defined token.)
<p>
The parser will 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 will pass control back to the parser.
YYERROR cannot be used outside of semantic actions.
<p>
When the parser detects a syntax error, it normally calls
<b>yyerror</b>
with the character string
syntax&nbsp;error
as its argument.
The call will 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
<b>yyerrok</b>.
The parser will not call
<b>yyerror</b>
when YYERROR is executed.
<p>
The macro function YYRECOVERING() will return 1 if a syntax error has
been detected and the parser has not yet fully recovered from it.
Otherwise, zero will be returned.
<p>
When a syntax error is detected by the parser, the
parser will 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
<xref href=yaccilex><a href="#tag_001_014_2954_009">
Interface to the Lexical Analyser
</a></xref>).
If it is, the parser will return with a non-zero value.
Otherwise, the lookahead symbol will be
discarded and normal parsing will resume.
<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
will 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
will return with a non-zero value.
Otherwise, it will shift over
<b>error</b>
and then resume normal parsing.
If the parser reads a lookahead symbol before the error
was detected, that symbol will still be the lookahead
symbol when parsing is resumed.
<p>
The macro
<b>yyerrok</b>
in a semantic action will cause the
parser to act as if it has fully recovered from any
previous errors.
The macro
<b>yyclearin</b>
will cause the parser to discard the current lookahead token.
If the current lookahead token has not yet been read,
<b>yyclearin</b>
will have no effect.
<p>
The macro YYACCEPT will cause the parser to return with the value zero.
The macro YYABORT will cause the parser to return with a non-zero value.
<h5><a name = "tag_001_014_2954_009">&nbsp;</a>Interface to the Lexical Analyser</h5>
<xref type="5" name="yaccilex"></xref>
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 will be assigned to
the external variable