1235723Sbapt%{ 2235723Sbapt 3235723Sbapt/* http://dinosaur.compilertools.net/yacc/index.html */ 4235723Sbapt 5235723Sbapt#include <stdlib.h> 6235723Sbapt#include <stdio.h> 7235723Sbapt#include <ctype.h> 8235723Sbapt#include <math.h> 9235723Sbapt 10235723Sbapttypedef struct interval 11235723Sbapt{ 12235723Sbapt double lo, hi; 13235723Sbapt} 14235723SbaptINTERVAL; 15235723Sbapt 16235723SbaptINTERVAL vmul(double, double, INTERVAL); 17235723SbaptINTERVAL vdiv(double, double, INTERVAL); 18235723Sbapt 19235723Sbaptextern int yylex(void); 20235723Sbaptstatic void yyerror(const char *s); 21235723Sbapt 22235723Sbaptint dcheck(INTERVAL); 23235723Sbapt 24235723Sbaptdouble dreg[26]; 25235723SbaptINTERVAL vreg[26]; 26235723Sbapt 27235723Sbapt%} 28235723Sbapt%expect 18 29235723Sbapt 30235723Sbapt%start line 31235723Sbapt%union 32235723Sbapt{ 33235723Sbapt int ival; 34235723Sbapt double dval; 35235723Sbapt INTERVAL vval; 36235723Sbapt} 37235723Sbapt 38235723Sbapt%token <ival> DREG VREG /* indices into dreg, vreg arrays */ 39235723Sbapt%token <dval> CONST /* floating point constant */ 40235723Sbapt 41235723Sbapt%type <dval> dexp /* expression */ 42235723Sbapt%type <vval> vexp /* interval expression */ 43235723Sbapt 44235723Sbapt /* precedence information about the operators */ 45235723Sbapt 46235723Sbapt%left '+' '-' 47235723Sbapt%left '*' '/' 48235723Sbapt%left UMINUS /* precedence for unary minus */ 49235723Sbapt 50235723Sbapt%% /* beginning of rules section */ 51235723Sbapt 52235723Sbaptlines : /* empty */ 53235723Sbapt | lines line 54235723Sbapt ; 55235723Sbapt 56235723Sbaptline : dexp '\n' 57235723Sbapt { 58235723Sbapt (void) printf("%15.8f\n", $1); 59235723Sbapt } 60235723Sbapt | vexp '\n' 61235723Sbapt { 62235723Sbapt (void) printf("(%15.8f, %15.8f)\n", $1.lo, $1.hi); 63235723Sbapt } 64235723Sbapt | DREG '=' dexp '\n' 65235723Sbapt { 66235723Sbapt dreg[$1] = $3; 67235723Sbapt } 68235723Sbapt | VREG '=' vexp '\n' 69235723Sbapt { 70235723Sbapt vreg[$1] = $3; 71235723Sbapt } 72235723Sbapt | error '\n' 73235723Sbapt { 74235723Sbapt yyerrok; 75235723Sbapt } 76235723Sbapt ; 77235723Sbapt 78235723Sbaptdexp : CONST 79235723Sbapt | DREG 80235723Sbapt { 81235723Sbapt $$ = dreg[$1]; 82235723Sbapt } 83235723Sbapt | dexp '+' dexp 84235723Sbapt { 85235723Sbapt $$ = $1 + $3; 86235723Sbapt } 87235723Sbapt | dexp '-' dexp 88235723Sbapt { 89235723Sbapt $$ = $1 - $3; 90235723Sbapt } 91235723Sbapt | dexp '*' dexp 92235723Sbapt { 93235723Sbapt $$ = $1 * $3; 94235723Sbapt } 95235723Sbapt | dexp '/' dexp 96235723Sbapt { 97235723Sbapt $$ = $1 / $3; 98235723Sbapt } 99235723Sbapt | '-' dexp %prec UMINUS 100235723Sbapt { 101235723Sbapt $$ = -$2; 102235723Sbapt } 103235723Sbapt | '(' dexp ')' 104235723Sbapt { 105235723Sbapt $$ = $2; 106235723Sbapt } 107235723Sbapt ; 108235723Sbapt 109235723Sbaptvexp : dexp 110235723Sbapt { 111235723Sbapt $$.hi = $$.lo = $1; 112235723Sbapt } 113235723Sbapt | '(' dexp ',' dexp ')' 114235723Sbapt { 115235723Sbapt $$.lo = $2; 116235723Sbapt $$.hi = $4; 117235723Sbapt if ( $$.lo > $$.hi ) 118235723Sbapt { 119235723Sbapt (void) printf("interval out of order\n"); 120235723Sbapt YYERROR; 121235723Sbapt } 122235723Sbapt } 123235723Sbapt | VREG 124235723Sbapt { 125235723Sbapt $$ = vreg[$1]; 126235723Sbapt } 127235723Sbapt | vexp '+' vexp 128235723Sbapt { 129235723Sbapt $$.hi = $1.hi + $3.hi; 130235723Sbapt $$.lo = $1.lo + $3.lo; 131235723Sbapt } 132235723Sbapt | dexp '+' vexp 133235723Sbapt { 134235723Sbapt $$.hi = $1 + $3.hi; 135235723Sbapt $$.lo = $1 + $3.lo; 136235723Sbapt } 137235723Sbapt | vexp '-' vexp 138235723Sbapt { 139235723Sbapt $$.hi = $1.hi - $3.lo; 140235723Sbapt $$.lo = $1.lo - $3.hi; 141235723Sbapt } 142235723Sbapt | dexp '-' vexp 143235723Sbapt { 144235723Sbapt $$.hi = $1 - $3.lo; 145235723Sbapt $$.lo = $1 - $3.hi; 146235723Sbapt } 147235723Sbapt | vexp '*' vexp 148235723Sbapt { 149235723Sbapt $$ = vmul( $1.lo, $1.hi, $3 ); 150235723Sbapt } 151235723Sbapt | dexp '*' vexp 152235723Sbapt { 153235723Sbapt $$ = vmul ($1, $1, $3 ); 154235723Sbapt } 155235723Sbapt | vexp '/' vexp 156235723Sbapt { 157235723Sbapt if (dcheck($3)) YYERROR; 158235723Sbapt $$ = vdiv ( $1.lo, $1.hi, $3 ); 159235723Sbapt } 160235723Sbapt | dexp '/' vexp 161235723Sbapt { 162235723Sbapt if (dcheck ( $3 )) YYERROR; 163235723Sbapt $$ = vdiv ($1, $1, $3 ); 164235723Sbapt } 165235723Sbapt | '-' vexp %prec UMINUS 166235723Sbapt { 167235723Sbapt $$.hi = -$2.lo; 168235723Sbapt $$.lo = -$2.hi; 169235723Sbapt } 170235723Sbapt | '(' vexp ')' 171235723Sbapt { 172235723Sbapt $$ = $2; 173235723Sbapt } 174235723Sbapt ; 175235723Sbapt 176235723Sbapt%% /* beginning of subroutines section */ 177235723Sbapt 178235723Sbapt#define BSZ 50 /* buffer size for floating point numbers */ 179235723Sbapt 180235723Sbapt /* lexical analysis */ 181235723Sbapt 182235723Sbaptstatic void 183235723Sbaptyyerror(const char *s) 184235723Sbapt{ 185235723Sbapt fprintf(stderr, "%s\n", s); 186235723Sbapt} 187235723Sbapt 188235723Sbaptint 189235723Sbaptyylex(void) 190235723Sbapt{ 191235723Sbapt int c; 192235723Sbapt 193235723Sbapt while ((c = getchar()) == ' ') 194235723Sbapt { /* skip over blanks */ 195235723Sbapt } 196235723Sbapt 197235723Sbapt if (isupper(c)) 198235723Sbapt { 199235723Sbapt yylval.ival = c - 'A'; 200235723Sbapt return (VREG); 201235723Sbapt } 202235723Sbapt if (islower(c)) 203235723Sbapt { 204235723Sbapt yylval.ival = c - 'a'; 205235723Sbapt return (DREG); 206235723Sbapt } 207235723Sbapt 208235723Sbapt if (isdigit(c) || c == '.') 209235723Sbapt { 210235723Sbapt /* gobble up digits, points, exponents */ 211235723Sbapt char buf[BSZ + 1], *cp = buf; 212235723Sbapt int dot = 0, expr = 0; 213235723Sbapt 214235723Sbapt for (; (cp - buf) < BSZ; ++cp, c = getchar()) 215235723Sbapt { 216235723Sbapt 217235723Sbapt *cp = c; 218235723Sbapt if (isdigit(c)) 219235723Sbapt continue; 220235723Sbapt if (c == '.') 221235723Sbapt { 222235723Sbapt if (dot++ || expr) 223235723Sbapt return ('.'); /* will cause syntax error */ 224235723Sbapt continue; 225235723Sbapt } 226235723Sbapt 227235723Sbapt if (c == 'e') 228235723Sbapt { 229235723Sbapt if (expr++) 230235723Sbapt return ('e'); /* will cause syntax error */ 231235723Sbapt continue; 232235723Sbapt } 233235723Sbapt 234235723Sbapt /* end of number */ 235235723Sbapt break; 236235723Sbapt } 237235723Sbapt *cp = '\0'; 238235723Sbapt 239235723Sbapt if ((cp - buf) >= BSZ) 240235723Sbapt printf("constant too long: truncated\n"); 241235723Sbapt else 242235723Sbapt ungetc(c, stdin); /* push back last char read */ 243235723Sbapt yylval.dval = atof(buf); 244235723Sbapt return (CONST); 245235723Sbapt } 246235723Sbapt return (c); 247235723Sbapt} 248235723Sbapt 249235723Sbaptstatic INTERVAL 250235723Sbapthilo(double a, double b, double c, double d) 251235723Sbapt{ 252235723Sbapt /* returns the smallest interval containing a, b, c, and d */ 253235723Sbapt /* used by *, / routines */ 254235723Sbapt INTERVAL v; 255235723Sbapt 256235723Sbapt if (a > b) 257235723Sbapt { 258235723Sbapt v.hi = a; 259235723Sbapt v.lo = b; 260235723Sbapt } 261235723Sbapt else 262235723Sbapt { 263235723Sbapt v.hi = b; 264235723Sbapt v.lo = a; 265235723Sbapt } 266235723Sbapt 267235723Sbapt if (c > d) 268235723Sbapt { 269235723Sbapt if (c > v.hi) 270235723Sbapt v.hi = c; 271235723Sbapt if (d < v.lo) 272235723Sbapt v.lo = d; 273235723Sbapt } 274235723Sbapt else 275235723Sbapt { 276235723Sbapt if (d > v.hi) 277235723Sbapt v.hi = d; 278235723Sbapt if (c < v.lo) 279235723Sbapt v.lo = c; 280235723Sbapt } 281235723Sbapt return (v); 282235723Sbapt} 283235723Sbapt 284235723SbaptINTERVAL 285235723Sbaptvmul(double a, double b, INTERVAL v) 286235723Sbapt{ 287235723Sbapt return (hilo(a * v.hi, a * v.lo, b * v.hi, b * v.lo)); 288235723Sbapt} 289235723Sbapt 290235723Sbaptint 291235723Sbaptdcheck(INTERVAL v) 292235723Sbapt{ 293235723Sbapt if (v.hi >= 0. && v.lo <= 0.) 294235723Sbapt { 295235723Sbapt printf("divisor interval contains 0.\n"); 296235723Sbapt return (1); 297235723Sbapt } 298235723Sbapt return (0); 299235723Sbapt} 300235723Sbapt 301235723SbaptINTERVAL 302235723Sbaptvdiv(double a, double b, INTERVAL v) 303235723Sbapt{ 304235723Sbapt return (hilo(a / v.hi, a / v.lo, b / v.hi, b / v.lo)); 305235723Sbapt} 306