The Evaluator Back End

The MathPaper back end, which we’ll call Evaluator, is a program that reads a stream of mathematical expressions and displays the result of evaluating them. If you give the back end the following input, line by line:

1+2*3+4
2+5*sin(3)
9/4
3+
(8-76+32) / 3.2

it will return this output:

11
2.7056
2.25
Syntax Error
-11.25

The Evaluator will write its output directly to standard output, and we’ll demonstrate it in a Terminal window. Later, when we run the Evaluator as a subprocess from MathPaper, the Evaluator’s standard output will be returned to the MathPaper application, which will, in turn, display the contents in an on-screen window.

In the rest of this section and the next section, we’ll discuss how to build the Evaluator back end. These sections use hardcore Unix development tools that are not essential to understanding Cocoa programming, and you can skip them if you want to download the source code from our web site ( http://www.oreilly.com/catalog/buildcocoa/). You can also download a working copy of the Evaluator program from our web site. However, we recommend that you follow the steps in the next section, even if you don’t fully understand what’s going on. All you really have to know to continue with MathPaper is that the Evaluator will perform the actual calculations for MathPaper and that it will run as a separate Unix process. So, if you plan to just download the source files, you can skip ahead to Section 10.4.

The task of the Evaluator back end breaks down into two parts: lexical analysis and parsing. Lexical analysis involves reading the input stream and determining which characters correspond to numbers and which correspond to operations. The character stream is then turned into a stream of tokens , or symbols. For example, the input to Evaluator shown earlier would generate the following token stream:

<1> <+> <2> <*> <3> <+> <4> <newline>
<2> <+> <5> <*> <sin> <(> <3> <)> <newline>
<9> </> <4> <newline>
<3> <+> <newline>
<(> <8> <-> <76> <+> <32> <)> </> <3.2> <newline>

The second part of the back end is the parser , which reads the token stream generated by the lexical analyzer, performs the requested calculations, and prints the correct result.

Parsers and lexical analyzers are not trivial programs to write. Fortunately, Mac OS X comes with two programs for constructing lexical analyzers and parsers from (relatively) simple input files. These program-generating programs are called lex and yacc. You don’t need to understand how lex and yacc work in order to understand the MathPaper program. The only thing that really matters is that, using lex and yacc, we are able to build a relatively powerful and reliable back end with only a small amount of work.

The Evaluator application is compiled from three input files:

Makefile

Input for make, the Unix utility that maintains, updates, and regenerates programs; tells make how to compile and link the Evaluator program[29]

grammar.y

Input to the yacc program

rules.l

Input to the lex program

lex and yacc

lex and yacc are programs that generate other programs. A full description of their use is beyond the scope of this book. For further information in Mac OS X, type man lex in a Terminal window. Also see the book lex & yacc, by John Levine, Tony Mason, and Doug Brown (O’Reilly).

yacc reads an input grammar file (in our case, the file grammar.y) that describes a particular grammar and generates two C source code files: y.tab.h and y.tab.c. lex reads the include file y.tab.h and a second file (in our case, the file rules.l) that describes a set of lexical rules and generates a C source file called lex.yy.c . The source code in y.tab.c and lex.yy.c is then compiled with the cc compiler and linked to form the Evaluator program.

We get a lot of power by using lex and yacc. Not only do we get a full-featured mathematical evaluator that properly interprets parentheses and order of evaluation (for example, evaluating multiplication before addition), but we also get a system to which it is easy to add new formulas and rules. For example, adding a new function to the Evaluator simply requires adding two new lines, one to the set of rules and one to the grammar. We’ll be doing much of our work from the Terminal command line, so make sure your Dock contains Mac OS X’s Terminal application.

Building the Back End

  1. Create a new folder called Evaluator in your Home folder.

  2. Using an editor (TextEdit, GNU Emacs, or vi), create a file called Makefile in your Evaluator directory containing the following:

    CFLAGS = -O
    SRCS = y.tab.c lex.yy.c
    LFLAGS =  -ly -ll -lm
    Evaluator: $(SRCS)
            cc $(CFLAGS) -o Evaluator $(SRCS) $(LFLAGS)
    
    clean:
            /bin/rm -f Evaluator $(SRCS) *.h
    
    lex.yy.c: rules.l y.tab.h 
            lex rules.l
    
    y.tab.h: grammar.y
            yacc -d grammar.y
    
    y.tab.c: grammar.y
            yacc grammar.y

Warning

It is very important that you begin the indented lines with a tab character, and not with spaces! The Unix make system distinguishes between these two types of whitespace.

This Makefile contains the targets install, clean, etc.

  1. Using an editor, create a file called grammar.y in your Evaluator directory containing the following:

    %{
    #include <libc.h>
    #include <math.h>
    
    int printingError = 0;
    %}
    
    %start list
    
    %union
    {
       int    ival;
       double dval;
    }
    
    %token <dval> NUMBER
    %token <dval> SIN COS TAN ASIN ACOS ATAN
    %token <dval> SINH COSH TANH ASINH ACOSH ATANH
    %token <dval> SQRT MOD LN LOG PI
    %type  <dval> expr number 
    
    %left '+' '-'
    %left '*' '/' 
    %left SIN COS TAN ASIN ACOS ATAN SINH COSH TANH ASINH
    %left ACOSH ATANH
    %left '^' SQRT MOD LN LOG
    %left UMINUS   /* supplies precedence for unary minus */
    
    %%             /* beginning of rules section */
    
    list : stat
         | list stat
         ;
    
    stat : expr '
    '
    {
      printf("%10g
    ",$1);
      printingError = 0;
      fflush(stdout);
    }
    ;
    
    expr   : '(' expr ')'
    {
      $$ = $2;
    }
      | expr '+' expr   { $$ = $1 + $3;}
      | expr '-' expr   { $$ = $1 - $3;}
      | expr '*' expr   { $$ = $1 * $3;}
      | expr '/' expr   { $$ = $1 / $3;}
      | SIN expr                               { $$ = sin($2);}
      | COS expr                               { $$ = cos($2);}
      | TAN expr                               { $$ = tan($2);}
      | ASIN expr                              { $$ = asin($2);}
      | ACOS expr                              { $$ = acos($2);}
      | ATAN expr                              { $$ = atan($2);}
      | SINH expr                              { $$ = sinh($2);}
      | COSH expr                              { $$ = cosh($2);}
      | TANH expr                              { $$ = tanh($2);}
      | ASINH expr                             { $$ = asinh($2);}
      | ACOSH expr                             { $$ = acosh($2);}
      | ATANH expr                             { $$ = atanh($2);}
      | expr '^' expr                          { $$ = pow($1,$3);}
      | expr MOD expr                          { $$ = fmod($1,$3);}
      | LN expr                                { $$ = log($2);}
      | LOG expr                               { $$ = log10($2);}
      | SQRT expr                              { $$ = sqrt($2);}
      | '-' expr %prec UMINUS
      {
         $$ = -$2;
      }
      | number
        ;
    
    number      : NUMBER   /* lex number */
      | PI      { $$ = M_PI;        }
      ;
    
    %% /* beginning of functions section */
    void yyerror(char *s)
    {
      if (printingError == 0) {
         printf("Syntax Error
    ");
         fflush(stdout);
         printingError = 1;
      }
    }
    
    int main(int argc,char **argv)
    {
      while (!feof(stdin)) {
         yyparse(  );
      }
      exit(0);
    }
  2. Using an editor, create a file called rules.l [30] in your Evaluator directory containing the following:

    %{
    #include "y.tab.h"
    #include <stdlib.h>
    
    #define YY_INPUT(buf,result,max_size) (buf[0])=getchar(  );result=1;
    
    int yywrap(void);
    int yywrap(  ){return 0;}
    
    %}
    
    %%
    
    "
    " return('
    '),
    
    [0-9]*("."[0-9]*("e"[-+][0-9]+)?)?  {yylval.dval = atof(yytext); 
        return(NUMBER);}
    
    sin        return(SIN);     // NOTE: In this section, be sure to use
    cos        return(COS);     // a tab after the 'sin' and each of
    tan        return(TAN);     // the other function names. If you use
    asin       return(ASIN);    // spaces, this code will not compile
    acos       return(ACOS);    // properly.
    atan       return(ATAN);
    sinh       return(SINH);
    cosh       return(COSH);
    tanh       return(TANH);
    asinh      return(ASINH);
    acosh      return(ACOSH);
    atanh      return(ATANH);
    mod        return(MOD);
    ln         return(LN);
    log        return(LOG);
    sqrt       return(SQRT);
    pi         return(PI);
    
    [ 	]     ;
    
    .         {return(yytext[0]);}
    
    %%

Unlike most lex and yacc programs, Evaluator contains all of the auxiliary C code that it needs to run in the grammar.y file. yacc automatically passes this code along to the C compiler with the parser that it generates.

  1. Open up a Unix shell window in the Terminal application.

  2. Compile the Evaluator program with the make utility by typing make in the Terminal window. What you should type is shown here in bold:

    % cd ~/Evaluator
    % make
    yacc grammar.y
    yacc -d grammar.y
    lex rules.l
    cc -O -o Evaluator y.tab.c lex.yy.c -ly -ll -lm
    %

If you get any errors, you probably made a typo.

  1. After compiling the program, test it with a few mathematical expressions, as follows:

    % cd ~/Evaluator
    % ./Evaluator
                            10+20
            302002/2001
        1.0005sin(2*pi) + cos(4*pi)
             1
    ^C%>

(Type Control-C to exit the program. The “^C”, which indicates where you should type Control-C, will show up in the Terminal window where indicated.)

Congratulations — you’re finished with the back end! If you don’t understand it all, don’t worry. All you have to know to continue with MathPaper is that Evaluator will perform the actual calculations for MathPaper and will run as a separate process.



[29] Although we use make to build the Evaluator in this chapter, in the next chapter we’ll see how to build Evaluator with Project Builder.

[30] Make sure your rules.l file extension is a lowercase letter “l” and not the digit 1! Make sure you use the letter and not the digit in rules.l in the Makefile as well.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.129.218.69