home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / doc / yacc / ssc < prev    next >
Encoding:
Text File  |  1979-01-10  |  8.3 KB  |  310 lines
  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
  310.