| 1 | .SH |
| 2 | Appendix C: An Advanced Example |
| 3 | .PP |
| 4 | This Appendix gives an example of a grammar using some |
| 5 | of the advanced features discussed in Section 10. |
| 6 | The desk calculator example in Appendix A is |
| 7 | modified to provide a desk calculator that |
| 8 | does floating point interval arithmetic. |
| 9 | The calculator understands floating point |
| 10 | constants, the arithmetic operations +, \-, *, /, |
| 11 | unary \-, and = (assignment), and has 26 floating |
| 12 | point variables, ``a'' through ``z''. |
| 13 | Moreover, it also understands |
| 14 | .I intervals , |
| 15 | written |
| 16 | .DS |
| 17 | ( x , y ) |
| 18 | .DE |
| 19 | where |
| 20 | .I x |
| 21 | is less than or equal to |
| 22 | .I y . |
| 23 | There are 26 interval valued variables ``A'' through ``Z'' |
| 24 | that may also be used. |
| 25 | The usage is similar to that in Appendix A; assignments |
| 26 | return no value, and print nothing, while expressions print |
| 27 | the (floating or interval) value. |
| 28 | .PP |
| 29 | This example explores a number of interesting features |
| 30 | of Yacc and C. |
| 31 | Intervals are represented by a structure, consisting of the |
| 32 | left and right endpoint values, stored as |
| 33 | .I double 's. |
| 34 | This structure is given a type name, INTERVAL, by using |
| 35 | .I typedef . |
| 36 | The Yacc value stack can also contain floating point scalars, and |
| 37 | integers (used to index into the arrays holding the variable values). |
| 38 | Notice that this entire strategy depends strongly on being able to |
| 39 | assign structures and unions in C. |
| 40 | In fact, many of the actions call functions that return structures |
| 41 | as well. |
| 42 | .PP |
| 43 | It is also worth noting the use of YYERROR to handle error conditions: |
| 44 | division by an interval containing 0, and an interval presented in |
| 45 | the wrong order. |
| 46 | In effect, the error recovery mechanism of Yacc is used to throw away the |
| 47 | rest of the offending line. |
| 48 | .PP |
| 49 | In addition to the mixing of types on the value stack, |
| 50 | this grammar also demonstrates an interesting use of syntax to |
| 51 | keep track of the type (e.g. scalar or interval) of intermediate |
| 52 | expressions. |
| 53 | Note that a scalar can be automatically promoted to an interval if |
| 54 | the context demands an interval value. |
| 55 | This causes a large number of conflicts when the grammar is run through |
| 56 | Yacc: 18 Shift/Reduce and 26 Reduce/Reduce. |
| 57 | The problem can be seen by looking at the two input lines: |
| 58 | .DS |
| 59 | 2.5 + ( 3.5 \- 4. ) |
| 60 | .DE |
| 61 | and |
| 62 | .DS |
| 63 | 2.5 + ( 3.5 , 4. ) |
| 64 | .DE |
| 65 | Notice that the 2.5 is to be used in an interval valued expression |
| 66 | in the second example, but this fact is not known until |
| 67 | the ``,'' is read; by this time, 2.5 is finished, and the parser cannot go back |
| 68 | and change its mind. |
| 69 | More generally, it might be necessary to look ahead an arbitrary number of |
| 70 | tokens to decide whether to convert a scalar to an interval. |
| 71 | This problem is evaded by having two rules for each binary interval |
| 72 | valued operator: one when the left operand is a scalar, and one when |
| 73 | the left operand is an interval. |
| 74 | In the second case, the right operand must be an interval, |
| 75 | so the conversion will be applied automatically. |
| 76 | Despite this evasion, there are still many cases where the |
| 77 | conversion may be applied or not, leading to the above |
| 78 | conflicts. |
| 79 | They are resolved by listing the rules that yield scalars first |
| 80 | in the specification file; in this way, the conflicts will |
| 81 | be resolved in the direction of keeping scalar |
| 82 | valued expressions scalar valued until they are forced to become |
| 83 | intervals. |
| 84 | .PP |
| 85 | This way of handling multiple types is very instructive, but not very general. |
| 86 | If there were many kinds of expression types, instead of just two, |
| 87 | the number of rules needed would increase dramatically, and the conflicts |
| 88 | even more dramatically. |
| 89 | Thus, while this example is instructive, it is better practice in a |
| 90 | more normal programming language environment to |
| 91 | keep the type information as part of the value, and not as part |
| 92 | of the grammar. |
| 93 | .PP |
| 94 | Finally, a word about the lexical analysis. |
| 95 | The only unusual feature is the treatment of floating point constants. |
| 96 | The C library routine |
| 97 | .I atof |
| 98 | is used to do the actual conversion from a character string |
| 99 | to a double precision value. |
| 100 | If the lexical analyzer detects an error, |
| 101 | it responds by returning a token that |
| 102 | is illegal in the grammar, provoking a syntax error |
| 103 | in the parser, and thence error recovery. |
| 104 | .DS L |
| 105 | |
| 106 | %{ |
| 107 | |
| 108 | # include <stdio.h> |
| 109 | # include <ctype.h> |
| 110 | |
| 111 | typedef struct interval { |
| 112 | double lo, hi; |
| 113 | } INTERVAL; |
| 114 | |
| 115 | INTERVAL vmul(), vdiv(); |
| 116 | |
| 117 | double atof(); |
| 118 | |
| 119 | double dreg[ 26 ]; |
| 120 | INTERVAL vreg[ 26 ]; |
| 121 | |
| 122 | %} |
| 123 | |
| 124 | %start lines |
| 125 | |
| 126 | %union { |
| 127 | int ival; |
| 128 | double dval; |
| 129 | INTERVAL vval; |
| 130 | } |
| 131 | |
| 132 | %token <ival> DREG VREG /* indices into dreg, vreg arrays */ |
| 133 | |
| 134 | %token <dval> CONST /* floating point constant */ |
| 135 | |
| 136 | %type <dval> dexp /* expression */ |
| 137 | |
| 138 | %type <vval> vexp /* interval expression */ |
| 139 | |
| 140 | /* precedence information about the operators */ |
| 141 | |
| 142 | %left \'+\' \'\-\' |
| 143 | %left \'*\' \'/\' |
| 144 | %left UMINUS /* precedence for unary minus */ |
| 145 | |
| 146 | %% |
| 147 | |
| 148 | lines : /* empty */ |
| 149 | | lines line |
| 150 | ; |
| 151 | |
| 152 | line : dexp \'\en\' |
| 153 | { printf( "%15.8f\en", $1 ); } |
| 154 | | vexp \'\en\' |
| 155 | { printf( "(%15.8f , %15.8f )\en", $1.lo, $1.hi ); } |
| 156 | | DREG \'=\' dexp \'\en\' |
| 157 | { dreg[$1] = $3; } |
| 158 | | VREG \'=\' vexp \'\en\' |
| 159 | { vreg[$1] = $3; } |
| 160 | | error \'\en\' |
| 161 | { yyerrok; } |
| 162 | ; |
| 163 | |
| 164 | dexp : CONST |
| 165 | | DREG |
| 166 | { $$ = dreg[$1]; } |
| 167 | | dexp \'+\' dexp |
| 168 | { $$ = $1 + $3; } |
| 169 | | dexp \'\-\' dexp |
| 170 | { $$ = $1 \- $3; } |
| 171 | | dexp \'*\' dexp |
| 172 | { $$ = $1 * $3; } |
| 173 | | dexp \'/\' dexp |
| 174 | { $$ = $1 / $3; } |
| 175 | | \'\-\' dexp %prec UMINUS |
| 176 | { $$ = \- $2; } |
| 177 | | \'(\' dexp \')\' |
| 178 | { $$ = $2; } |
| 179 | ; |
| 180 | |
| 181 | vexp : dexp |
| 182 | { $$.hi = $$.lo = $1; } |
| 183 | | \'(\' dexp \',\' dexp \')\' |
| 184 | { |
| 185 | $$.lo = $2; |
| 186 | $$.hi = $4; |
| 187 | if( $$.lo > $$.hi ){ |
| 188 | printf( "interval out of order\en" ); |
| 189 | YYERROR; |
| 190 | } |
| 191 | } |
| 192 | | VREG |
| 193 | { $$ = vreg[$1]; } |
| 194 | | vexp \'+\' vexp |
| 195 | { $$.hi = $1.hi + $3.hi; |
| 196 | $$.lo = $1.lo + $3.lo; } |
| 197 | | dexp \'+\' vexp |
| 198 | { $$.hi = $1 + $3.hi; |
| 199 | $$.lo = $1 + $3.lo; } |
| 200 | | vexp \'\-\' vexp |
| 201 | { $$.hi = $1.hi \- $3.lo; |
| 202 | $$.lo = $1.lo \- $3.hi; } |
| 203 | | dexp \'\-\' vexp |
| 204 | { $$.hi = $1 \- $3.lo; |
| 205 | $$.lo = $1 \- $3.hi; } |
| 206 | | vexp \'*\' vexp |
| 207 | { $$ = vmul( $1.lo, $1.hi, $3 ); } |
| 208 | | dexp \'*\' vexp |
| 209 | { $$ = vmul( $1, $1, $3 ); } |
| 210 | | vexp \'/\' vexp |
| 211 | { if( dcheck( $3 ) ) YYERROR; |
| 212 | $$ = vdiv( $1.lo, $1.hi, $3 ); } |
| 213 | | dexp \'/\' vexp |
| 214 | { if( dcheck( $3 ) ) YYERROR; |
| 215 | $$ = vdiv( $1, $1, $3 ); } |
| 216 | | \'\-\' vexp %prec UMINUS |
| 217 | { $$.hi = \-$2.lo; $$.lo = \-$2.hi; } |
| 218 | | \'(\' vexp \')\' |
| 219 | { $$ = $2; } |
| 220 | ; |
| 221 | |
| 222 | %% |
| 223 | |
| 224 | # define BSZ 50 /* buffer size for floating point numbers */ |
| 225 | |
| 226 | /* lexical analysis */ |
| 227 | |
| 228 | yylex(){ |
| 229 | register c; |
| 230 | |
| 231 | while( (c=getchar()) == \' \' ){ /* skip over blanks */ } |
| 232 | |
| 233 | if( isupper( c ) ){ |
| 234 | yylval.ival = c \- \'A\'; |
| 235 | return( VREG ); |
| 236 | } |
| 237 | if( islower( c ) ){ |
| 238 | yylval.ival = c \- \'a\'; |
| 239 | return( DREG ); |
| 240 | } |
| 241 | |
| 242 | if( isdigit( c ) || c==\'.\' ){ |
| 243 | /* gobble up digits, points, exponents */ |
| 244 | |
| 245 | char buf[BSZ+1], *cp = buf; |
| 246 | int dot = 0, exp = 0; |
| 247 | |
| 248 | for( ; (cp\-buf)<BSZ ; ++cp,c=getchar() ){ |
| 249 | |
| 250 | *cp = c; |
| 251 | if( isdigit( c ) ) continue; |
| 252 | if( c == \'.\' ){ |
| 253 | if( dot++ || exp ) return( \'.\' ); /* will cause syntax error */ |
| 254 | continue; |
| 255 | } |
| 256 | |
| 257 | if( c == \'e\' ){ |
| 258 | if( exp++ ) return( \'e\' ); /* will cause syntax error */ |
| 259 | continue; |
| 260 | } |
| 261 | |
| 262 | /* end of number */ |
| 263 | break; |
| 264 | } |
| 265 | *cp = \'\e0\'; |
| 266 | if( (cp\-buf) >= BSZ ) printf( "constant too long: truncated\en" ); |
| 267 | else ungetc( c, stdin ); /* push back last char read */ |
| 268 | yylval.dval = atof( buf ); |
| 269 | return( CONST ); |
| 270 | } |
| 271 | return( c ); |
| 272 | } |
| 273 | |
| 274 | INTERVAL hilo( a, b, c, d ) double a, b, c, d; { |
| 275 | /* returns the smallest interval containing a, b, c, and d */ |
| 276 | /* used by *, / routines */ |
| 277 | INTERVAL v; |
| 278 | |
| 279 | if( a>b ) { v.hi = a; v.lo = b; } |
| 280 | else { v.hi = b; v.lo = a; } |
| 281 | |
| 282 | if( c>d ) { |
| 283 | if( c>v.hi ) v.hi = c; |
| 284 | if( d<v.lo ) v.lo = d; |
| 285 | } |
| 286 | else { |
| 287 | if( d>v.hi ) v.hi = d; |
| 288 | if( c<v.lo ) v.lo = c; |
| 289 | } |
| 290 | return( v ); |
| 291 | } |
| 292 | |
| 293 | INTERVAL vmul( a, b, v ) double a, b; INTERVAL v; { |
| 294 | return( hilo( a*v.hi, a*v.lo, b*v.hi, b*v.lo ) ); |
| 295 | } |
| 296 | |
| 297 | dcheck( v ) INTERVAL v; { |
| 298 | if( v.hi >= 0. && v.lo <= 0. ){ |
| 299 | printf( "divisor interval contains 0.\en" ); |
| 300 | return( 1 ); |
| 301 | } |
| 302 | return( 0 ); |
| 303 | } |
| 304 | |
| 305 | INTERVAL vdiv( a, b, v ) double a, b; INTERVAL v; { |
| 306 | return( hilo( a/v.hi, a/v.lo, b/v.hi, b/v.lo ) ); |
| 307 | } |
| 308 | .DE |
| 309 | .bp |