home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1989 / 06 / yaccex.asc < prev   
Text File  |  1989-05-27  |  10KB  |  373 lines
  1. _GENERATING PARSERS WITH PCYACC_
  2. by Alex Lane
  3.  
  4. [LISTING ONE]
  5.  
  6. yacc specification
  7.  
  8. /* TEST.Y
  9.  
  10. This specification is based largely on the yacc
  11. specification for a simple desk calculator from "Compilers:
  12. Principles, Techniques and Tools," by Aho, et al. (p. 259,
  13. Addison-Wesley, 1986).
  14.  
  15.    2/2/89 a.lane
  16. */
  17.  
  18. %{
  19. #include <stdio.h>
  20. #include <ctype.h>
  21. %}
  22.  
  23. %token DIGIT
  24. %left '+'
  25. %left '*'
  26.  
  27. %%
  28.  
  29. line  :   /* nothing */
  30.       |   expr '\n'           { printf("%d\n", $1); }
  31.       ;   
  32. expr  :   expr '+' term       { $$ = $1 + $3; }
  33.       |   term
  34.       ;
  35. term  :   term '*' factor     { $$ = $1 * $3; }
  36.       |   factor
  37.       ;
  38. factor:   '(' expr ')'        { $$ = $2; }
  39.       |   DIGIT
  40.       ;
  41. %%
  42. main()    {
  43. yyparse();
  44. }
  45.  
  46. yylex()   {
  47.      int c;
  48.      if ( isdigit( ( c = getchar() ) ) )  {
  49.           yylval = c - '0';
  50.           return DIGIT;
  51.      }
  52.      return c;
  53. }
  54.  
  55. yyerror(s)
  56. char *s;
  57. {
  58.      fprintf(stderr, "PYERR: %s\n", s);
  59. }
  60.  
  61.  
  62. [LISTING TWO]
  63.  
  64.  
  65. # line 11 "test.y"
  66. #include <stdio.h>
  67. #include <ctype.h>
  68. #define DIGIT 257
  69. #ifndef YYSTYPE
  70. #define YYSTYPE int
  71. #endif
  72. YYSTYPE yylval, yyval;
  73. #define YYERRCODE 256
  74.  
  75. # line 33 "test.y"
  76.  
  77. main()    {
  78. yyparse();
  79. }
  80.  
  81. yylex()   {
  82.      int c;
  83.      if ( isdigit( ( c = getchar() ) ) )  {
  84.           yylval = c - '0';
  85.           return DIGIT;
  86.      }
  87.      return c;
  88. }
  89.  
  90. yyerror(s)
  91. char *s;
  92. {
  93.      fprintf(stderr, "PYERR: %s\n", s);
  94. }
  95.  
  96. FILE *yytfilep;
  97. char *yytfilen;
  98. int yytflag = 0;
  99. int svdprd[2];
  100. char svdnams[2][2];
  101.  
  102. int yyexca[] = {
  103.   -1, 1,
  104.   0, -1,
  105.   -2, 0,
  106.   0,
  107. };
  108.  
  109. #define YYNPROD 9
  110. #define YYLAST 218
  111.  
  112. int yyact[] = {
  113.        5,       7,      13,       4,       8,       9,       3,       1,
  114.        2,       0,       0,       0,       0,      12,      10,      11,
  115.        4,       0,       3,       2,       0,       0,       0,       0,
  116.        0,       0,       0,       0,       0,       0,       0,       0,
  117.        0,       0,       8,       0,       0,       0,       0,       0,
  118.        0,       0,       0,       0,       0,       0,       0,       0,
  119.        0,       0,       0,       0,       0,       0,       0,       0,
  120.        0,       0,       0,       0,       0,       0,       0,       0,
  121.        0,       0,       0,       0,       0,       0,       0,       0,
  122.        0,       0,       0,       0,       0,       0,       0,       0,
  123.        0,       0,       0,       0,       0,       0,       0,       0,
  124.        0,       0,       0,       0,       0,       0,       0,       0,
  125.        0,       0,       0,       0,       0,       0,       0,       0,
  126.        0,       0,       0,       0,       0,       0,       0,       0,
  127.        0,       0,       0,       0,       0,       0,       0,       0,
  128.        0,       0,       0,       0,       0,       0,       0,       0,
  129.        0,       0,       0,       0,       0,       0,       0,       0,
  130.        0,       0,       0,       0,       0,       0,       0,       0,
  131.        0,       0,       0,       0,       0,       0,       0,       0,
  132.        0,       0,       0,       0,       0,       0,       0,       0,
  133.        0,       0,       0,       0,       0,       0,       0,       0,
  134.        0,       0,       0,       0,       0,       0,       0,       0,
  135.        0,       0,       0,       0,       0,       0,       0,       0,
  136.        0,       0,       0,       0,       0,       0,       0,       0,
  137.        0,       0,       0,       0,       0,       0,       0,       0,
  138.        0,       0,       0,       0,       0,       0,       0,       0,
  139.        0,       0,       0,       0,       0,       0,       0,       0,
  140.        0,       6,
  141. };
  142.  
  143. int yypact[] = {
  144.      -40,   -1000,      -9,     -37,   -1000,     -40,   -1000,   -1000,
  145.      -40,     -40,     -39,     -37,   -1000,   -1000,
  146. };
  147.  
  148. int yypgo[] = {
  149.        0,       7,       8,       6,       3,
  150. };
  151.  
  152. int yyr1[] = {
  153.        0,       1,       1,       2,       2,       3,       3,       4,
  154.        4,
  155. };
  156.  
  157. int yyr2[] = {
  158.        2,       0,       2,       3,       1,       3,       1,       3,
  159.        1,
  160. };
  161.  
  162. int yychk[] = {
  163.    -1000,      -1,      -2,      -3,      -4,      40,     257,      10,
  164.       43,      42,      -2,      -3,      -4,      41,
  165. };
  166.  
  167. int yydef[] = {
  168.        1,      -2,       0,       4,       6,       0,       8,       2,
  169.        0,       0,       0,       3,       5,       7,
  170. };
  171.  
  172. int *yyxi;
  173.  
  174.  
  175. /*****************************************************************/
  176. /* PCYACC LALR parser driver routine -- a table driven procedure */
  177. /* for recognizing sentences of a language defined by the        */
  178. /* grammar that PCYACC analyzes. An LALR parsing table is then   */
  179. /* constructed for the grammar and the skeletal parser uses the  */
  180. /* table when performing syntactical analysis on input source    */
  181. /* programs. The actions associated with grammar rules are       */
  182. /* inserted into a switch statement for execution.               */
  183. /*****************************************************************/
  184.  
  185.  
  186. #ifndef YYMAXDEPTH
  187. #define YYMAXDEPTH 200
  188. #endif
  189. #ifndef YYREDMAX
  190. #define YYREDMAX 1000
  191. #endif
  192. #define PCYYFLAG -1000
  193. #define WAS0ERR 0
  194. #define WAS1ERR 1
  195. #define WAS2ERR 2
  196. #define WAS3ERR 3
  197. #define yyclearin pcyytoken = -1
  198. #define yyerrok   pcyyerrfl = 0
  199. YYSTYPE yyv[YYMAXDEPTH];     /* value stack */
  200. int pcyyerrct = 0;           /* error count */
  201. int pcyyerrfl = 0;           /* error flag */
  202. int redseq[YYREDMAX];
  203. int redcnt = 0;
  204. int pcyytoken = -1;          /* input token */
  205.  
  206.  
  207. yyparse()
  208. {
  209.   int statestack[YYMAXDEPTH]; /* state stack */
  210.   int      j, m;              /* working index */
  211.   YYSTYPE *yypvt;
  212.   int      tmpstate, tmptoken, *yyps, n;
  213.   YYSTYPE *yypv;
  214.  
  215.  
  216.   tmpstate = 0;
  217.   pcyytoken = -1;
  218. #ifdef YYDEBUG
  219.   tmptoken = -1;
  220. #endif
  221.   pcyyerrct = 0;
  222.   pcyyerrfl = 0;
  223.   yyps = &statestack[-1];
  224.   yypv = &yyv[-1];
  225.  
  226.  
  227.   enstack:    /* push stack */
  228. #ifdef YYDEBUG
  229.     printf("at state %d, next token %d\n", tmpstate, tmptoken);
  230. #endif
  231.     if (++yyps - &statestack[YYMAXDEPTH] > 0) {
  232.       yyerror("pcyacc internal stack overflow");
  233.       return(1);
  234.     }
  235.     *yyps = tmpstate;
  236.     ++yypv;
  237.     *yypv = yyval;
  238.  
  239.   newstate:
  240.     n = yypact[tmpstate];
  241.     if (n <= PCYYFLAG) goto defaultact; /*  a simple state */
  242.  
  243.  
  244.     if (pcyytoken < 0) if ((pcyytoken=yylex()) < 0) pcyytoken = 0;
  245.     if ((n += pcyytoken) < 0 || n >= YYLAST) goto defaultact;
  246.  
  247.  
  248.     if (yychk[n=yyact[n]] == pcyytoken) { /* a shift */
  249. #ifdef YYDEBUG
  250.       tmptoken  = pcyytoken;
  251. #endif
  252.       pcyytoken = -1;
  253.       yyval = yylval;
  254.       tmpstate = n;
  255.       if (pcyyerrfl > 0) --pcyyerrfl;
  256.       goto enstack;
  257.     }
  258.  
  259.   defaultact:
  260.  
  261.     if ((n=yydef[tmpstate]) == -2) {
  262.       if (pcyytoken < 0) if ((pcyytoken=yylex())<0) pcyytoken = 0;
  263.       for (yyxi=yyexca; (*yyxi!= (-1)) || (yyxi[1]!=tmpstate); yyxi += 2);
  264.       while (*(yyxi+=2) >= 0) if (*yyxi == pcyytoken) break;
  265.       if ((n=yyxi[1]) < 0) { /* an accept action */
  266.         if (yytflag) {
  267.           int ti; int tj;
  268.           yytfilep = fopen(yytfilen, "w");
  269.           if (yytfilep == NULL) {
  270.             fprintf(stderr, "Can't open t file: %s\n", yytfilen);
  271.             return(0);          }
  272.           for (ti=redcnt-1; ti>=0; ti--) {
  273.             tj = svdprd[redseq[ti]];
  274.             while (strcmp(svdnams[tj], "$EOP"))
  275.               fprintf(yytfilep, "%s ", svdnams[tj++]);
  276.             fprintf(yytfilep, "\n");
  277.           }
  278.           fclose(yytfilep);
  279.         }
  280.         return (0);
  281.       }
  282.     }
  283.  
  284.  
  285.     if (n == 0) {        /* error situation */
  286.       switch (pcyyerrfl) {
  287.         case WAS0ERR:          /* an error just occurred */
  288.           yyerror("syntax error");
  289.           yyerrlab:
  290.             ++pcyyerrct;
  291.         case WAS1ERR:
  292.         case WAS2ERR:           /* try again */
  293.           pcyyerrfl = 3;
  294.         /* find a state for a legal shift action */
  295.           while (yyps >= statestack) {
  296.           n = yypact[*yyps] + YYERRCODE;
  297.           if (n >= 0 && n < YYLAST && yychk[yyact[n]] == YYERRCODE) {
  298.             tmpstate = yyact[n];  /* simulate a shift of "error" */
  299.             goto enstack;
  300.             }
  301.           n = yypact[*yyps];
  302.  
  303.  
  304.           /* the current yyps has no shift on "error", pop stack */
  305. #ifdef YYDEBUG
  306.             printf("error: pop state %d, recover state %d\n", *yyps, yyps[-
  307. 1]);
  308. #endif
  309.           --yyps;
  310.           --yypv;
  311.         }
  312.  
  313.  
  314.         yyabort:
  315.             if (yytflag) {
  316.               int ti; int tj;
  317.               yytfilep = fopen(yytfilen, "w");
  318.               if (yytfilep == NULL) {
  319.                 fprintf(stderr, "Can't open t file: %s\n", yytfilen);
  320.                 return(1);              }
  321.               for (ti=1; ti<redcnt; ti++) {
  322.                 tj = svdprd[redseq[ti]];
  323.                 while (strcmp(svdnams[tj], "$EOP"))
  324.                   fprintf(yytfilep, "%s ", svdnams[tj++]);
  325.                 fprintf(yytfilep, "\n");
  326.               }
  327.               fclose(yytfilep);
  328.             }
  329.           return(1);
  330.  
  331.  
  332.       case WAS3ERR:  /* clobber input char */
  333. #ifdef YYDEBUG
  334.           printf("error: discard token %d\n", pcyytoken);
  335. #endif
  336.           if (pcyytoken == 0) goto yyabort; /* quit */
  337.         pcyytoken = -1;
  338.         goto newstate;      } /* switch */
  339.     } /* if */
  340.  
  341.  
  342.     /* reduction, given a production n */
  343. #ifdef YYDEBUG
  344.     printf("reduce with rule %d\n", n);
  345. #endif
  346.     if (yytflag && redcnt<YYREDMAX) redseq[redcnt++] = n;
  347.     yyps -= yyr2[n];
  348.     yypvt = yypv;
  349.     yypv -= yyr2[n];
  350.     yyval = yypv[1];
  351.     m = n;
  352.     /* find next state from goto table */
  353.     n = yyr1[n];
  354.     j = yypgo[n] + *yyps + 1;
  355.     if (j>=YYLAST || yychk[ tmpstate = yyact[j] ] != -n) tmpstate =
  356. yyact[yypgo[n]];
  357.     switch (m) { /* actions associated with grammar rules */
  358.  
  359.       case 2:
  360. # line 22 "test.y"
  361.       { printf("%d\n", yypvt[-1]); } break;
  362.       case 3:
  363. # line 24 "test.y"
  364.       { yyval = yypvt[-2] + yypvt[-0]; } break;
  365.       case 5:
  366. # line 27 "test.y"
  367.       { yyval = yypvt[-2] * yypvt[-0]; } break;
  368.       case 7:
  369. # line 30 "test.y"
  370.       { yyval = yypvt[-1]; } break;    }
  371.     goto enstack;
  372. }
  373.