bison_5.htm

Lex和Yacc的Manual

   character read if not a number.  Skips all blanks
   and tabs, returns 0 for EOF. */

#include <ctype.h>

yylex ()
{
  int c;

  /* skip white space  */
  while ((c = getchar ()) == ' ' || c == '\t')  
    ;
  /* process numbers   */
  if (c == '.' || isdigit (c))                
    {
      ungetc (c, stdin);
      scanf ("%lf", &yylval);
      return NUM;
    }
  /* return end-of-file  */
  if (c == EOF)                            
    return 0;
  /* return single chars */
  return c;                                
}
</PRE>



<H3><A NAME="SEC23" HREF="index.html#SEC23">The Controlling Function</A></H3>
<P>
<A NAME="IDX36"></A>
<A NAME="IDX37"></A>

</P>
<P>
In keeping with the spirit of this example, the controlling function is
kept to the bare minimum.  The only requirement is that it call
<CODE>yyparse</CODE> to start the process of parsing.

</P>

<PRE>
main ()
{
  yyparse ();
}
</PRE>



<H3><A NAME="SEC24" HREF="index.html#SEC24">The Error Reporting Routine</A></H3>
<P>
<A NAME="IDX38"></A>

</P>
<P>
When <CODE>yyparse</CODE> detects a syntax error, it calls the error reporting
function <CODE>yyerror</CODE> to print an error message (usually but not always
<CODE>"parse error"</CODE>).  It is up to the programmer to supply <CODE>yyerror</CODE>
(see section <A HREF="bison_7.html#SEC59">Parser C-Language Interface</A>), so here is the definition we will use:

</P>

<PRE>
#include &#60;stdio.h&#62;

yyerror (s)  /* Called by yyparse on error */
     char *s;
{
  printf ("%s\n", s);
}
</PRE>

<P>
After <CODE>yyerror</CODE> returns, the Bison parser may recover from the error
and continue parsing if the grammar contains a suitable error rule
(see section <A HREF="bison_9.html#SEC81">Error Recovery</A>).  Otherwise, <CODE>yyparse</CODE> returns nonzero.  We
have not written any error rules in this example, so any invalid input will
cause the calculator program to exit.  This is not clean behavior for a
real calculator, but it is adequate in the first example.

</P>


<H3><A NAME="SEC25" HREF="index.html#SEC25">Running Bison to Make the Parser</A></H3>
<P>
<A NAME="IDX39"></A>

</P>
<P>
Before running Bison to produce a parser, we need to decide how to arrange
all the source code in one or more source files.  For such a simple example,
the easiest thing is to put everything in one file.  The definitions of
<CODE>yylex</CODE>, <CODE>yyerror</CODE> and <CODE>main</CODE> go at the end, in the
"additional C code" section of the file (see section <A HREF="bison_4.html#SEC14">The Overall Layout of a Bison Grammar</A>).

</P>
<P>
For a large project, you would probably have several source files, and use
<CODE>make</CODE> to arrange to recompile them.

</P>
<P>
With all the source in a single file, you use the following command to
convert it into a parser file:

</P>

<PRE>
bison <VAR>file_name</VAR>.y
</PRE>

<P>
In this example the file was called <TT>`rpcalc.y'</TT> (for "Reverse Polish
CALCulator").  Bison produces a file named <TT>`<VAR>file_name</VAR>.tab.c'</TT>,
removing the <SAMP>`.y'</SAMP> from the original file name. The file output by
Bison contains the source code for <CODE>yyparse</CODE>.  The additional
functions in the input file (<CODE>yylex</CODE>, <CODE>yyerror</CODE> and <CODE>main</CODE>)
are copied verbatim to the output.

</P>


<H3><A NAME="SEC26" HREF="index.html#SEC26">Compiling the Parser File</A></H3>
<P>
<A NAME="IDX40"></A>

</P>
<P>
Here is how to compile and run the parser file:

</P>

<PRE>
# List files in current directory.
% ls
rpcalc.tab.c  rpcalc.y

# Compile the Bison parser.
# <SAMP>`-lm'</SAMP> tells compiler to search math library for <CODE>pow</CODE>.
% cc rpcalc.tab.c -lm -o rpcalc

# List files again.
% ls
rpcalc  rpcalc.tab.c  rpcalc.y
</PRE>

<P>
The file <TT>`rpcalc'</TT> now contains the executable code.  Here is an
example session using <CODE>rpcalc</CODE>.

</P>

<PRE>
% rpcalc
4 9 +
13
3 7 + 3 4 5 *+-
-13
3 7 + 3 4 5 * + - n              Note the unary minus, <SAMP>`n'</SAMP>
13
5 6 / 4 n +
-3.166666667
3 4 ^                            Exponentiation
81
^D                               End-of-file indicator
%
</PRE>



<H2><A NAME="SEC27" HREF="index.html#SEC27">Infix Notation Calculator: <CODE>calc</CODE></A></H2>
<P>
<A NAME="IDX41"></A>
<A NAME="IDX42"></A>
<A NAME="IDX43"></A>

</P>
<P>
We now modify rpcalc to handle infix operators instead of postfix.  Infix
notation involves the concept of operator precedence and the need for
parentheses nested to arbitrary depth.  Here is the Bison code for
<TT>`calc.y'</TT>, an infix desk-top calculator.

</P>

<PRE>
/* Infix notation calculator--calc */

%{
#define YYSTYPE double
#include &#60;math.h&#62;
%}

/* BISON Declarations */
%token NUM
%left '-' '+'
%left '*' '/'
%left NEG     /* negation--unary minus */
%right '^'    /* exponentiation        */

/* Grammar follows */
%%
input:    /* empty string */
        | input line
;

line:     '\n'
        | exp '\n'  { printf ("\t%.10g\n", $1); }
;

exp:      NUM                { $$ = $1;         }
        | exp '+' exp        { $$ = $1 + $3;    }
        | exp '-' exp        { $$ = $1 - $3;    }
        | exp '*' exp        { $$ = $1 * $3;    }
        | exp '/' exp        { $$ = $1 / $3;    }
        | '-' exp  %prec NEG { $$ = -$2;        }
        | exp '^' exp        { $$ = pow ($1, $3); }
        | '(' exp ')'        { $$ = $2;         }
;
%%
</PRE>

<P>
The functions <CODE>yylex</CODE>, <CODE>yyerror</CODE> and <CODE>main</CODE> can be the same
as before.

</P>
<P>
There are two important new features shown in this code.

</P>
<P>
In the second section (Bison declarations), <CODE>%left</CODE> declares token
types and says they are left-associative operators.  The declarations
<CODE>%left</CODE> and <CODE>%right</CODE> (right associativity) take the place of
<CODE>%token</CODE> which is used to declare a token type name without
associativity.  (These tokens are single-character literals, which
ordinarily don't need to be declared.  We declare them here to specify
the associativity.)

</P>
<P>
Operator precedence is determined by the line ordering of the
declarations; the higher the line number of the declaration (lower on
the page or screen), the higher the precedence.  Hence, exponentiation
has the highest precedence, unary minus (<CODE>NEG</CODE>) is next, followed
by <SAMP>`*'</SAMP> and <SAMP>`/'</SAMP>, and so on.  See section <A HREF="bison_8.html#SEC71">Operator Precedence</A>.

</P>
<P>
The other important new feature is the <CODE>%prec</CODE> in the grammar section
for the unary minus operator.  The <CODE>%prec</CODE> simply instructs Bison that
the rule <SAMP>`| '-' exp'</SAMP> has the same precedence as <CODE>NEG</CODE>---in this
case the next-to-highest.  See section <A HREF="bison_8.html#SEC76">Context-Dependent Precedence</A>.

</P>
<P>
Here is a sample run of <TT>`calc.y'</TT>:

</P>

<PRE>
% calc
4 + 4.5 - (34/(8*3+-3))
6.880952381
-56 + 2
-54
3 ^ 2
9
</PRE>



<H2><A NAME="SEC28" HREF="index.html#SEC28">Simple Error Recovery</A></H2>
<P>
<A NAME="IDX44"></A>

</P>
<P>
Up to this point, this manual has not addressed the issue of <STRONG>error
recovery</STRONG>---how to continue parsing after the parser detects a syntax
error.  All we have handled is error reporting with <CODE>yyerror</CODE>.  Recall
that by default <CODE>yyparse</CODE> returns after calling <CODE>yyerror</CODE>.  This
means that an erroneous input line causes the calculator program to exit.
Now we show how to rectify this deficiency.

</P>
<P>
The Bison language itself includes the reserved word <CODE>error</CODE>, which
may be included in the grammar rules.  In the example below it has
been added to one of the alternatives for <CODE>line</CODE>:

</P>

<PRE>
line:     '\n'
        | exp '\n'   { printf ("\t%.10g\n", $1); }
        | error '\n' { yyerrok;                  }
;
</PRE>

<P>
This addition to the grammar allows for simple error recovery in the event
of a parse error.  If an expression that cannot be evaluated is read, the
error will be recognized by the third rule for <CODE>line</CODE>, and parsing
will continue.  (The <CODE>yyerror</CODE> function is still called upon to print
its message as well.)  The action executes the statement <CODE>yyerrok</CODE>, a
macro defined automatically by Bison; its meaning is that error recovery is
complete (see section <A HREF="bison_9.html#SEC81">Error Recovery</A>).  Note the difference between
<CODE>yyerrok</CODE> and <CODE>yyerror</CODE>; neither one is a misprint.
</P>
<P>
This form of error recovery deals with syntax errors.  There are other
kinds of errors; for example, division by zero, which raises an exception
signal that is normally fatal.  A real calculator program must handle this
signal and use <CODE>longjmp</CODE> to return to <CODE>main</CODE> and resume parsing
input lines; it would also have to discard the rest of the current line of
input.  We won't discuss this issue further because it is not specific to
Bison programs.

</P>


<H2><A NAME="SEC29" HREF="index.html#SEC29">Multi-Function Calculator: <CODE>mfcalc</CODE></A></H2>
<P>
<A NAME="IDX45"></A>
<A NAME="IDX46"></A>
<A NAME="IDX47"></A>

</P>
<P>
Now that the basics of Bison have been discussed, it is time to move on to
a more advanced problem.  The above calculators provided only five
functions, <SAMP>`+'</SAMP>, <SAMP>`-'</SAMP>, <SAMP>`*'</SAMP>, <SAMP>`/'</SAMP> and <SAMP>`^'</SAMP>.  It would
be nice to have a calculator that provides other mathematical functions such
as <CODE>sin</CODE>, <CODE>cos</CODE>, etc.

</P>
<P>
It is easy to add new operators to the infix calculator as long as they are
only single-character literals.  The lexical analyzer <CODE>yylex</CODE> passes
back all non-number characters as tokens, so new grammar rules suffice for
adding a new operator.  But we want something more flexible: built-in
functions whose syntax has this form:

</P>

<PRE>
<VAR>function_name</VAR> (<VAR>argument</VAR>)
</PRE>

<P>
At the same time, we will add memory to the calculator, by allowing you
to create named variables, store values in them, and use them later.
Here is a sample session with the multi-function calculator:

</P>

<PRE>
% mfcalc
pi = 3.141592653589
3.1415926536
sin(pi)
0.0000000000
alpha = beta1 = 2.3
2.3000000000
alpha
2.3000000000
ln(alpha)
0.8329091229
exp(ln(beta1))