1 %{ 2 3 /* http://dinosaur.compilertools.net/yacc/index.html */ 4 5 #include <stdlib.h> 6 #include <stdio.h> 7 #include <ctype.h> 8 #include <math.h> 9 10 typedef struct interval 11 { 12 double lo, hi; 13 } 14 INTERVAL; 15 16 INTERVAL vmul(double, double, INTERVAL); 17 INTERVAL vdiv(double, double, INTERVAL); 18 19 extern int yylex(void); 20 static void yyerror(const char *s); 21 22 int dcheck(INTERVAL); 23 24 double dreg[26]; 25 INTERVAL vreg[26]; 26 27 %} 28 %expect 18 29 30 %start line 31 %union 32 { 33 int ival; 34 double dval; 35 INTERVAL vval; 36 } 37 38 %token <ival> DREG VREG /* indices into dreg, vreg arrays */ 39 %token <dval> CONST /* floating point constant */ 40 41 %type <dval> dexp /* expression */ 42 %type <vval> vexp /* interval expression */ 43 44 /* precedence information about the operators */ 45 46 %left '+' '-' 47 %left '*' '/' 48 %left UMINUS /* precedence for unary minus */ 49 50 %% /* beginning of rules section */ 51 52 lines : /* empty */ 53 | lines line 54 ; 55 56 line : dexp '\n' 57 { 58 (void) printf("%15.8f\n", $1); 59 } 60 | vexp '\n' 61 { 62 (void) printf("(%15.8f, %15.8f)\n", $1.lo, $1.hi); 63 } 64 | DREG '=' dexp '\n' 65 { 66 dreg[$1] = $3; 67 } 68 | VREG '=' vexp '\n' 69 { 70 vreg[$1] = $3; 71 } 72 | error '\n' 73 { 74 yyerrok; 75 } 76 ; 77 78 dexp : CONST 79 | DREG 80 { 81 $$ = dreg[$1]; 82 } 83 | dexp '+' dexp 84 { 85 $$ = $1 + $3; 86 } 87 | dexp '-' dexp 88 { 89 $$ = $1 - $3; 90 } 91 | dexp '*' dexp 92 { 93 $$ = $1 * $3; 94 } 95 | dexp '/' dexp 96 { 97 $$ = $1 / $3; 98 } 99 | '-' dexp %prec UMINUS 100 { 101 $$ = -$2; 102 } 103 | '(' dexp ')' 104 { 105 $$ = $2; 106 } 107 ; 108 109 vexp : dexp 110 { 111 $$.hi = $$.lo = $1; 112 } 113 | '(' dexp ',' dexp ')' 114 { 115 $$.lo = $2; 116 $$.hi = $4; 117 if ( $$.lo > $$.hi ) 118 { 119 (void) printf("interval out of order\n"); 120 YYERROR; 121 } 122 } 123 | VREG 124 { 125 $$ = vreg[$1]; 126 } 127 | vexp '+' vexp 128 { 129 $$.hi = $1.hi + $3.hi; 130 $$.lo = $1.lo + $3.lo; 131 } 132 | dexp '+' vexp 133 { 134 $$.hi = $1 + $3.hi; 135 $$.lo = $1 + $3.lo; 136 } 137 | vexp '-' vexp 138 { 139 $$.hi = $1.hi - $3.lo; 140 $$.lo = $1.lo - $3.hi; 141 } 142 | dexp '-' vexp 143 { 144 $$.hi = $1 - $3.lo; 145 $$.lo = $1 - $3.hi; 146 } 147 | vexp '*' vexp 148 { 149 $$ = vmul( $1.lo, $1.hi, $3 ); 150 } 151 | dexp '*' vexp 152 { 153 $$ = vmul ($1, $1, $3 ); 154 } 155 | vexp '/' vexp 156 { 157 if (dcheck($3)) YYERROR; 158 $$ = vdiv ( $1.lo, $1.hi, $3 ); 159 } 160 | dexp '/' vexp 161 { 162 if (dcheck ( $3 )) YYERROR; 163 $$ = vdiv ($1, $1, $3 ); 164 } 165 | '-' vexp %prec UMINUS 166 { 167 $$.hi = -$2.lo; 168 $$.lo = -$2.hi; 169 } 170 | '(' vexp ')' 171 { 172 $$ = $2; 173 } 174 ; 175 176 %% /* beginning of subroutines section */ 177 178 #define BSZ 50 /* buffer size for floating point numbers */ 179 180 /* lexical analysis */ 181 182 static void 183 yyerror(const char *s) 184 { 185 fprintf(stderr, "%s\n", s); 186 } 187 188 int 189 yylex(void) 190 { 191 int c; 192 193 while ((c = getchar()) == ' ') 194 { /* skip over blanks */ 195 } 196 197 if (isupper(c)) 198 { 199 yylval.ival = c - 'A'; 200 return (VREG); 201 } 202 if (islower(c)) 203 { 204 yylval.ival = c - 'a'; 205 return (DREG); 206 } 207 208 if (isdigit(c) || c == '.') 209 { 210 /* gobble up digits, points, exponents */ 211 char buf[BSZ + 1], *cp = buf; 212 int dot = 0, expr = 0; 213 214 for (; (cp - buf) < BSZ; ++cp, c = getchar()) 215 { 216 217 *cp = (char) c; 218 if (isdigit(c)) 219 continue; 220 if (c == '.') 221 { 222 if (dot++ || expr) 223 return ('.'); /* will cause syntax error */ 224 continue; 225 } 226 227 if (c == 'e') 228 { 229 if (expr++) 230 return ('e'); /* will cause syntax error */ 231 continue; 232 } 233 234 /* end of number */ 235 break; 236 } 237 *cp = '\0'; 238 239 if ((cp - buf) >= BSZ) 240 printf("constant too long: truncated\n"); 241 else 242 ungetc(c, stdin); /* push back last char read */ 243 yylval.dval = atof(buf); 244 return (CONST); 245 } 246 return (c); 247 } 248 249 static INTERVAL 250 hilo(double a, double b, double c, double d) 251 { 252 /* returns the smallest interval containing a, b, c, and d */ 253 /* used by *, / routines */ 254 INTERVAL v; 255 256 if (a > b) 257 { 258 v.hi = a; 259 v.lo = b; 260 } 261 else 262 { 263 v.hi = b; 264 v.lo = a; 265 } 266 267 if (c > d) 268 { 269 if (c > v.hi) 270 v.hi = c; 271 if (d < v.lo) 272 v.lo = d; 273 } 274 else 275 { 276 if (d > v.hi) 277 v.hi = d; 278 if (c < v.lo) 279 v.lo = c; 280 } 281 return (v); 282 } 283 284 INTERVAL 285 vmul(double a, double b, INTERVAL v) 286 { 287 return (hilo(a * v.hi, a * v.lo, b * v.hi, b * v.lo)); 288 } 289 290 int 291 dcheck(INTERVAL v) 292 { 293 if (v.hi >= 0. && v.lo <= 0.) 294 { 295 printf("divisor interval contains 0.\n"); 296 return (1); 297 } 298 return (0); 299 } 300 301 INTERVAL 302 vdiv(double a, double b, INTERVAL v) 303 { 304 return (hilo(a / v.hi, a / v.lo, b / v.hi, b / v.lo)); 305 } 306