share/doc/psd/15.yacc/ssc

   1 .\" Copyright (C) Caldera International Inc. 2001-2002.  All rights reserved.
   2 .\"
   3 .\" Redistribution and use in source and binary forms, with or without
   4 .\" modification, are permitted provided that the following conditions are
   5 .\" met:
   6 .\"
   7 .\" Redistributions of source code and documentation must retain the above
   8 .\" copyright notice, this list of conditions and the following
   9 .\" disclaimer.
  10 .\"
  11 .\" Redistributions in binary form must reproduce the above copyright
  12 .\" notice, this list of conditions and the following disclaimer in the
  13 .\" documentation and/or other materials provided with the distribution.
  14 .\"
  15 .\" All advertising materials mentioning features or use of this software
  16 .\" must display the following acknowledgement:
  17 .\"
  18 .\" This product includes software developed or owned by Caldera
  19 .\" International, Inc.  Neither the name of Caldera International, Inc.
  20 .\" nor the names of other contributors may be used to endorse or promote
  21 .\" products derived from this software without specific prior written
  22 .\" permission.
  23 .\"
  24 .\" USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
  25 .\" INTERNATIONAL, INC.  AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
  26 .\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  27 .\" WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  28 .\" DISCLAIMED.  IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE
  29 .\" FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR
  30 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  31 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  32 .\" BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  33 .\" WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
  34 .\" OR OTHERWISE) RISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
  35 .\" IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36 .\"     @(#)ssc 8.1 (Berkeley) 8/14/93
  37 .\"
  38 .\" $FreeBSD$
  39 .SH
  40 Appendix C: An Advanced Example
  41 .PP
  42 This Appendix gives an example of a grammar using some
  43 of the advanced features discussed in Section 10.
  44 The desk calculator example in Appendix A is
  45 modified to provide a desk calculator that
  46 does floating point interval arithmetic.
  47 The calculator understands floating point
  48 constants, the arithmetic operations +, \-, *, /,
  49 unary \-, and = (assignment), and has 26 floating
  50 point variables, ``a'' through ``z''.
  51 Moreover, it also understands
  52 .I intervals ,
  53 written
  54 .DS
  55         ( x , y )
  56 .DE
  57 where
  58 .I x
  59 is less than or equal to
  60 .I y .
  61 There are 26 interval valued variables ``A'' through ``Z''
  62 that may also be used.
  63 The usage is similar to that in Appendix A; assignments
  64 return no value, and print nothing, while expressions print
  65 the (floating or interval) value.
  66 .PP
  67 This example explores a number of interesting features
  68 of Yacc and C.
  69 Intervals are represented by a structure, consisting of the
  70 left and right endpoint values, stored as
  71 .I double 's.
  72 This structure is given a type name, INTERVAL, by using
  73 .I typedef .
  74 The Yacc value stack can also contain floating point scalars, and
  75 integers (used to index into the arrays holding the variable values).
  76 Notice that this entire strategy depends strongly on being able to
  77 assign structures and unions in C.
  78 In fact, many of the actions call functions that return structures
  79 as well.
  80 .PP
  81 It is also worth noting the use of YYERROR to handle error conditions:
  82 division by an interval containing 0, and an interval presented in
  83 the wrong order.
  84 In effect, the error recovery mechanism of Yacc is used to throw away the
  85 rest of the offending line.
  86 .PP
  87 In addition to the mixing of types on the value stack,
  88 this grammar also demonstrates an interesting use of syntax to
  89 keep track of the type (e.g. scalar or interval) of intermediate
  90 expressions.
  91 Note that a scalar can be automatically promoted to an interval if
  92 the context demands an interval value.
  93 This causes a large number of conflicts when the grammar is run through
  94 Yacc: 18 Shift/Reduce and 26 Reduce/Reduce.
  95 The problem can be seen by looking at the two input lines:
  96 .DS
  97         2.5 + ( 3.5 \- 4. )
  98 .DE
  99 and
 100 .DS
 101         2.5 + ( 3.5 , 4. )
 102 .DE
 103 Notice that the 2.5 is to be used in an interval valued expression
 104 in the second example, but this fact is not known until
 105 the ``,'' is read; by this time, 2.5 is finished, and the parser cannot go back
 106 and change its mind.
 107 More generally, it might be necessary to look ahead an arbitrary number of
 108 tokens to decide whether to convert a scalar to an interval.
 109 This problem is evaded by having two rules for each binary interval
 110 valued operator: one when the left operand is a scalar, and one when
 111 the left operand is an interval.
 112 In the second case, the right operand must be an interval,
 113 so the conversion will be applied automatically.
 114 Despite this evasion, there are still many cases where the
 115 conversion may be applied or not, leading to the above
 116 conflicts.
 117 They are resolved by listing the rules that yield scalars first
 118 in the specification file; in this way, the conflicts will
 119 be resolved in the direction of keeping scalar
 120 valued expressions scalar valued until they are forced to become
 121 intervals.
 122 .PP
 123 This way of handling multiple types is very instructive, but not very general.
 124 If there were many kinds of expression types, instead of just two,
 125 the number of rules needed would increase dramatically, and the conflicts
 126 even more dramatically.
 127 Thus, while this example is instructive, it is better practice in a
 128 more normal programming language environment to
 129 keep the type information as part of the value, and not as part
 130 of the grammar.
 131 .PP
 132 Finally, a word about the lexical analysis.
 133 The only unusual feature is the treatment of floating point constants.
 134 The C library routine
 135 .I atof
 136 is used to do the actual conversion from a character string
 137 to a double precision value.
 138 If the lexical analyzer detects an error,
 139 it responds by returning a token that
 140 is illegal in the grammar, provoking a syntax error
 141 in the parser, and thence error recovery.
 142 .LD
 143
 144 %{
 145
 146 #  include  <stdio.h>
 147 #  include  <ctype.h>
 148
 149 typedef  struct  interval  {
 150         double  lo,  hi;
 151         }  INTERVAL;
 152
 153 INTERVAL  vmul(),  vdiv();
 154
 155 double  atof();
 156
 157 double  dreg[ 26 ];
 158 INTERVAL  vreg[ 26 ];
 159
 160 %}
 161
 162 %start    lines
 163
 164 %union    {
 165         int  ival;
 166         double  dval;
 167         INTERVAL  vval;
 168         }
 169
 170 %token  <ival>  DREG  VREG      /*  indices  into  dreg,  vreg  arrays  */
 171
 172 %token  <dval>  CONST           /*  floating  point  constant  */
 173
 174 %type  <dval>  dexp             /*  expression  */
 175
 176 %type  <vval>  vexp             /*  interval  expression  */
 177
 178         /*  precedence  information  about  the  operators  */
 179
 180 %left   \'+\'  \'\-\'
 181 %left   \'*\'  \'/\'
 182 %left   UMINUS        /*  precedence  for  unary  minus  */
 183
 184 %%
 185
 186 lines   :       /*  empty  */
 187         |       lines  line
 188         ;
 189
 190 line    :       dexp  \'\en\'
 191                         {       printf(  "%15.8f\en",  $1  );  }
 192         |       vexp  \'\en\'
 193                         {       printf(  "(%15.8f  ,  %15.8f  )\en",  $1.lo,  $1.hi  );  }
 194         |       DREG  \'=\'  dexp  \'\en\'
 195                         {       dreg[$1]  =  $3;  }
 196         |       VREG  \'=\'  vexp  \'\en\'
 197                         {       vreg[$1]  =  $3;  }
 198         |       error  \'\en\'
 199                         {       yyerrok;  }
 200         ;
 201
 202 dexp    :       CONST
 203         |       DREG
 204                         {       $$  =  dreg[$1];  }
 205         |       dexp  \'+\'  dexp
 206                         {       $$  =  $1  +  $3;  }
 207         |       dexp  \'\-\'  dexp
 208                         {       $$  =  $1  \-  $3;  }
 209         |       dexp  \'*\'  dexp
 210                         {       $$  =  $1  *  $3;  }
 211         |       dexp  \'/\'  dexp
 212                         {       $$  =  $1  /  $3;  }
 213         |       \'\-\'  dexp    %prec  UMINUS
 214                         {       $$  =  \- $2;  }
 215         |       \'(\'  dexp  \')\'
 216                         {       $$  =  $2;  }
 217         ;
 218
 219 vexp    :       dexp
 220                         {       $$.hi  =  $$.lo  =  $1;  }
 221         |       \'(\'  dexp  \',\'  dexp  \')\'
 222                         {
 223                         $$.lo  =  $2;
 224                         $$.hi  =  $4;
 225                         if(  $$.lo  >  $$.hi  ){
 226                                 printf(  "interval  out  of  order\en"  );
 227                                 YYERROR;
 228                                 }
 229                         }
 230         |       VREG
 231                         {       $$  =  vreg[$1];    }
 232         |       vexp  \'+\'  vexp
 233                         {       $$.hi  =  $1.hi  +  $3.hi;
 234                                 $$.lo  =  $1.lo  +  $3.lo;    }
 235         |       dexp  \'+\'  vexp
 236                         {       $$.hi  =  $1  +  $3.hi;
 237                                 $$.lo  =  $1  +  $3.lo;    }
 238         |       vexp  \'\-\'  vexp
 239                         {       $$.hi  =  $1.hi  \-  $3.lo;
 240                                 $$.lo  =  $1.lo  \-  $3.hi;    }
 241         |       dexp  \'\-\'  vexp
 242                         {       $$.hi  =  $1  \-  $3.lo;
 243                                 $$.lo  =  $1  \-  $3.hi;    }
 244         |       vexp  \'*\'  vexp
 245                         {       $$  =  vmul(  $1.lo,  $1.hi,  $3  );  }
 246         |       dexp  \'*\'  vexp
 247                         {       $$  =  vmul(  $1,  $1,  $3  );  }
 248         |       vexp  \'/\'  vexp
 249                         {       if(  dcheck(  $3  )  )  YYERROR;
 250                                 $$  =  vdiv(  $1.lo,  $1.hi,  $3  );  }
 251         |       dexp  \'/\'  vexp
 252                         {       if(  dcheck(  $3  )  )  YYERROR;
 253                                 $$  =  vdiv(  $1,  $1,  $3  );  }
 254         |       \'\-\'  vexp    %prec  UMINUS
 255                         {       $$.hi  =  \-$2.lo;    $$.lo  =  \-$2.hi;    }
 256         |       \'(\'  vexp  \')\'
 257                         {       $$  =  $2;  }
 258         ;
 259
 260 %%
 261
 262 #  define  BSZ  50        /*  buffer  size  for  floating  point  numbers  */
 263
 264         /*  lexical  analysis  */
 265
 266 yylex(){
 267         register  c;
 268
 269         while(  (c=getchar())  ==  \' \'  ){  /*  skip  over  blanks  */  }
 270
 271         if(  isupper(  c  )  ){
 272                 yylval.ival  =  c  \-  \'A\';
 273                 return(  VREG  );
 274                 }
 275         if(  islower(  c  )  ){
 276                 yylval.ival  =  c  \-  \'a\';
 277                 return(  DREG  );
 278                 }
 279
 280         if(  isdigit(  c  )  ||  c==\'.\'  ){
 281                 /*  gobble  up  digits,  points,  exponents  */
 282
 283                 char  buf[BSZ+1],  *cp  =  buf;
 284                 int  dot  =  0,  exp  =  0;
 285
 286                 for(  ;  (cp\-buf)<BSZ  ;  ++cp,c=getchar()  ){
 287
 288                         *cp  =  c;
 289                         if(  isdigit(  c  )  )  continue;
 290                         if(  c  ==  \'.\'  ){
 291                                 if(  dot++  ||  exp  )  return(  \'.\'  );    /*  will  cause  syntax  error  */
 292                                 continue;
 293                                 }
 294
 295                         if(  c  ==  \'e\'  ){
 296                                 if(  exp++  )  return(  \'e\'  );    /*  will  cause  syntax  error  */
 297                                 continue;
 298                                 }
 299
 300                         /*  end  of  number  */
 301                         break;
 302                         }
 303                 *cp  =  \'\e0\';
 304                 if(  (cp\-buf)  >=  BSZ  )  printf(  "constant  too  long:  truncated\en"  );
 305                 else  ungetc(  c,  stdin  );    /*  push  back  last  char  read  */
 306                 yylval.dval  =  atof(  buf  );
 307                 return(  CONST  );
 308                 }
 309         return(  c  );
 310         }
 311
 312 INTERVAL  hilo(  a,  b,  c,  d  )  double  a,  b,  c,  d;  {
 313         /*  returns  the  smallest  interval  containing  a,  b,  c,  and  d  */
 314         /*  used  by  *,  /  routines  */
 315         INTERVAL  v;
 316
 317         if(  a>b  )  {  v.hi  =  a;    v.lo  =  b;  }
 318         else  {  v.hi  =  b;    v.lo  =  a;  }
 319
 320         if(  c>d  )  {
 321                 if(  c>v.hi  )  v.hi  =  c;
 322                 if(  d<v.lo  )  v.lo  =  d;
 323                 }
 324         else  {
 325                 if(  d>v.hi  )  v.hi  =  d;
 326                 if(  c<v.lo  )  v.lo  =  c;
 327                 }
 328         return(  v  );
 329         }
 330
 331 INTERVAL  vmul(  a,  b,  v  )  double  a,  b;    INTERVAL  v;  {
 332         return(  hilo(  a*v.hi,  a*v.lo,  b*v.hi,  b*v.lo  )  );
 333         }
 334
 335 dcheck(  v  )  INTERVAL  v;  {
 336         if(  v.hi  >=  0.  &&  v.lo  <=  0.  ){
 337                 printf(  "divisor  interval  contains  0.\en"  );
 338                 return(  1  );
 339                 }
 340         return(  0  );
 341         }
 342
 343 INTERVAL  vdiv(  a,  b,  v  )  double  a,  b;    INTERVAL  v;  {
 344         return(  hilo(  a/v.hi,  a/v.lo,  b/v.hi,  b/v.lo  )  );
 345         }
 346 .DE
 347 .bp