Return to ssc CVS log

Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps1 / 15.yacc

Annotation of 43BSDReno/share/doc/ps1/15.yacc/ssc, revision 1.1

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.