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
YYERROR_DECL()188 YYERROR_DECL()
189 {
190 fprintf(stderr, "%s\n", s);
191 }
192
193 /* lexical analysis */
194
195 static int
YYLEX_DECL()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
hilo(double a,double b,double c,double d)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
vmul(double a,double b,INTERVAL v)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
dcheck(INTERVAL v)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
vdiv(double a,double b,INTERVAL v)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