1 .\" Copyright (C) Caldera International Inc. 2001-2002. All rights reserved.
3 .\" Redistribution and use in source and binary forms, with or without
4 .\" modification, are permitted provided that the following conditions are
7 .\" Redistributions of source code and documentation must retain the above
8 .\" copyright notice, this list of conditions and the following
11 .\" Redistributions in binary form must reproduce the above copyright
12 .\" notice, this list of conditions and the following disclaimer in the
13 .\" documentation and/or other materials provided with the distribution.
15 .\" All advertising materials mentioning features or use of this software
16 .\" must display the following acknowledgement:
18 .\" This product includes software developed or owned by Caldera
19 .\" International, Inc. Neither the name of Caldera International, Inc.
20 .\" nor the names of other contributors may be used to endorse or promote
21 .\" products derived from this software without specific prior written
24 .\" USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
25 .\" INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
26 .\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
27 .\" WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
28 .\" DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE
29 .\" FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
32 .\" BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
33 .\" WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
34 .\" OR OTHERWISE) RISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
35 .\" IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 .\" @(#)ssc 8.1 (Berkeley) 8/14/93
40 Appendix C: An Advanced Example
42 This Appendix gives an example of a grammar using some
43 of the advanced features discussed in Section 10.
44 The desk calculator example in Appendix A is
45 modified to provide a desk calculator that
46 does floating point interval arithmetic.
47 The calculator understands floating point
48 constants, the arithmetic operations +, \-, *, /,
49 unary \-, and = (assignment), and has 26 floating
50 point variables, ``a'' through ``z''.
51 Moreover, it also understands
59 is less than or equal to
61 There are 26 interval valued variables ``A'' through ``Z''
62 that may also be used.
63 The usage is similar to that in Appendix A; assignments
64 return no value, and print nothing, while expressions print
65 the (floating or interval) value.
67 This example explores a number of interesting features
69 Intervals are represented by a structure, consisting of the
70 left and right endpoint values, stored as
72 This structure is given a type name, INTERVAL, by using
74 The Yacc value stack can also contain floating point scalars, and
75 integers (used to index into the arrays holding the variable values).
76 Notice that this entire strategy depends strongly on being able to
77 assign structures and unions in C.
78 In fact, many of the actions call functions that return structures
81 It is also worth noting the use of YYERROR to handle error conditions:
82 division by an interval containing 0, and an interval presented in
84 In effect, the error recovery mechanism of Yacc is used to throw away the
85 rest of the offending line.
87 In addition to the mixing of types on the value stack,
88 this grammar also demonstrates an interesting use of syntax to
89 keep track of the type (e.g. scalar or interval) of intermediate
91 Note that a scalar can be automatically promoted to an interval if
92 the context demands an interval value.
93 This causes a large number of conflicts when the grammar is run through
94 Yacc: 18 Shift/Reduce and 26 Reduce/Reduce.
95 The problem can be seen by looking at the two input lines:
103 Notice that the 2.5 is to be used in an interval valued expression
104 in the second example, but this fact is not known until
105 the ``,'' is read; by this time, 2.5 is finished, and the parser cannot go back
107 More generally, it might be necessary to look ahead an arbitrary number of
108 tokens to decide whether to convert a scalar to an interval.
109 This problem is evaded by having two rules for each binary interval
110 valued operator: one when the left operand is a scalar, and one when
111 the left operand is an interval.
112 In the second case, the right operand must be an interval,
113 so the conversion will be applied automatically.
114 Despite this evasion, there are still many cases where the
115 conversion may be applied or not, leading to the above
117 They are resolved by listing the rules that yield scalars first
118 in the specification file; in this way, the conflicts will
119 be resolved in the direction of keeping scalar
120 valued expressions scalar valued until they are forced to become
123 This way of handling multiple types is very instructive, but not very general.
124 If there were many kinds of expression types, instead of just two,
125 the number of rules needed would increase dramatically, and the conflicts
126 even more dramatically.
127 Thus, while this example is instructive, it is better practice in a
128 more normal programming language environment to
129 keep the type information as part of the value, and not as part
132 Finally, a word about the lexical analysis.
133 The only unusual feature is the treatment of floating point constants.
134 The C library routine
136 is used to do the actual conversion from a character string
137 to a double precision value.
138 If the lexical analyzer detects an error,
139 it responds by returning a token that
140 is illegal in the grammar, provoking a syntax error
141 in the parser, and thence error recovery.
149 typedef struct interval {
153 INTERVAL vmul(), vdiv();
170 %token <ival> DREG VREG /* indices into dreg, vreg arrays */
172 %token <dval> CONST /* floating point constant */
174 %type <dval> dexp /* expression */
176 %type <vval> vexp /* interval expression */
178 /* precedence information about the operators */
182 %left UMINUS /* precedence for unary minus */
191 { printf( "%15.8f\en", $1 ); }
193 { printf( "(%15.8f , %15.8f )\en", $1.lo, $1.hi ); }
194 | DREG \'=\' dexp \'\en\'
196 | VREG \'=\' vexp \'\en\'
213 | \'\-\' dexp %prec UMINUS
220 { $$.hi = $$.lo = $1; }
221 | \'(\' dexp \',\' dexp \')\'
226 printf( "interval out of order\en" );
233 { $$.hi = $1.hi + $3.hi;
234 $$.lo = $1.lo + $3.lo; }
236 { $$.hi = $1 + $3.hi;
237 $$.lo = $1 + $3.lo; }
239 { $$.hi = $1.hi \- $3.lo;
240 $$.lo = $1.lo \- $3.hi; }
242 { $$.hi = $1 \- $3.lo;
243 $$.lo = $1 \- $3.hi; }
245 { $$ = vmul( $1.lo, $1.hi, $3 ); }
247 { $$ = vmul( $1, $1, $3 ); }
249 { if( dcheck( $3 ) ) YYERROR;
250 $$ = vdiv( $1.lo, $1.hi, $3 ); }
252 { if( dcheck( $3 ) ) YYERROR;
253 $$ = vdiv( $1, $1, $3 ); }
254 | \'\-\' vexp %prec UMINUS
255 { $$.hi = \-$2.lo; $$.lo = \-$2.hi; }
262 # define BSZ 50 /* buffer size for floating point numbers */
264 /* lexical analysis */
269 while( (c=getchar()) == \' \' ){ /* skip over blanks */ }
272 yylval.ival = c \- \'A\';
276 yylval.ival = c \- \'a\';
280 if( isdigit( c ) || c==\'.\' ){
281 /* gobble up digits, points, exponents */
283 char buf[BSZ+1], *cp = buf;
284 int dot = 0, exp = 0;
286 for( ; (cp\-buf)<BSZ ; ++cp,c=getchar() ){
289 if( isdigit( c ) ) continue;
291 if( dot++ || exp ) return( \'.\' ); /* will cause syntax error */
296 if( exp++ ) return( \'e\' ); /* will cause syntax error */
304 if( (cp\-buf) >= BSZ ) printf( "constant too long: truncated\en" );
305 else ungetc( c, stdin ); /* push back last char read */
306 yylval.dval = atof( buf );
312 INTERVAL hilo( a, b, c, d ) double a, b, c, d; {
313 /* returns the smallest interval containing a, b, c, and d */
314 /* used by *, / routines */
317 if( a>b ) { v.hi = a; v.lo = b; }
318 else { v.hi = b; v.lo = a; }
321 if( c>v.hi ) v.hi = c;
322 if( d<v.lo ) v.lo = d;
325 if( d>v.hi ) v.hi = d;
326 if( c<v.lo ) v.lo = c;
331 INTERVAL vmul( a, b, v ) double a, b; INTERVAL v; {
332 return( hilo( a*v.hi, a*v.lo, b*v.hi, b*v.lo ) );
335 dcheck( v ) INTERVAL v; {
336 if( v.hi >= 0. && v.lo <= 0. ){
337 printf( "divisor interval contains 0.\en" );
343 INTERVAL vdiv( a, b, v ) double a, b; INTERVAL v; {
344 return( hilo( a/v.hi, a/v.lo, b/v.hi, b/v.lo ) );