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
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.
Create a new folder called Evaluator
in your
Home folder.
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
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.
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); }
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.
Open up a Unix shell window in the Terminal application.
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.
(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.
3.129.218.69