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
yylex(void)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
hilo(double a,double b,double c,double d)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
vmul(double a,double b,INTERVAL v)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
dcheck(INTERVAL v)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
vdiv(double a,double b,INTERVAL v)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