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