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