home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 15 / AACD15.ISO / AACD / Programming / Python2 / Python20_source / Parser / acceler.c next >
Encoding:
C/C++ Source or Header  |  2000-10-25  |  3.2 KB  |  145 lines
  1.  
  2. /* Parser accelerator module */
  3.  
  4. /* The parser as originally conceived had disappointing performance.
  5.    This module does some precomputation that speeds up the selection
  6.    of a DFA based upon a token, turning a search through an array
  7.    into a simple indexing operation.  The parser now cannot work
  8.    without the accelerators installed.  Note that the accelerators
  9.    are installed dynamically when the parser is initialized, they
  10.    are not part of the static data structure written on graminit.[ch]
  11.    by the parser generator. */
  12.  
  13. #include "pgenheaders.h"
  14. #include "grammar.h"
  15. #include "node.h"
  16. #include "token.h"
  17. #include "parser.h"
  18.  
  19. /* Forward references */
  20. static void fixdfa(grammar *, dfa *);
  21. static void fixstate(grammar *, state *);
  22.  
  23. void
  24. PyGrammar_AddAccelerators(grammar *g)
  25. {
  26.     dfa *d;
  27.     int i;
  28. #ifdef Py_DEBUG
  29.     fprintf(stderr, "Adding parser accelerators ...\n");
  30. #endif
  31.     d = g->g_dfa;
  32.     for (i = g->g_ndfas; --i >= 0; d++)
  33.         fixdfa(g, d);
  34.     g->g_accel = 1;
  35. #ifdef Py_DEBUG
  36.     fprintf(stderr, "Done.\n");
  37. #endif
  38. }
  39.  
  40. void
  41. PyGrammar_RemoveAccelerators(grammar *g)
  42. {
  43.     dfa *d;
  44.     int i;
  45.     g->g_accel = 0;
  46.     d = g->g_dfa;
  47.     for (i = g->g_ndfas; --i >= 0; d++) {
  48.         state *s;
  49.         int j;
  50.         s = d->d_state;
  51.         for (j = 0; j < d->d_nstates; j++, s++) {
  52.             if (s->s_accel)
  53.                 PyMem_DEL(s->s_accel);
  54.             s->s_accel = NULL;
  55.         }
  56.     }
  57. }
  58.  
  59. static void
  60. fixdfa(grammar *g, dfa *d)
  61. {
  62.     state *s;
  63.     int j;
  64.     s = d->d_state;
  65.     for (j = 0; j < d->d_nstates; j++, s++)
  66.         fixstate(g, s);
  67. }
  68.  
  69. static void
  70. fixstate(grammar *g, state *s)
  71. {
  72.     arc *a;
  73.     int k;
  74.     int *accel;
  75.     int nl = g->g_ll.ll_nlabels;
  76.     s->s_accept = 0;
  77.     accel = PyMem_NEW(int, nl);
  78.     for (k = 0; k < nl; k++)
  79.         accel[k] = -1;
  80.     a = s->s_arc;
  81.     for (k = s->s_narcs; --k >= 0; a++) {
  82.         int lbl = a->a_lbl;
  83.         label *l = &g->g_ll.ll_label[lbl];
  84.         int type = l->lb_type;
  85.         if (a->a_arrow >= (1 << 7)) {
  86.             printf("XXX too many states!\n");
  87.             continue;
  88.         }
  89.         if (ISNONTERMINAL(type)) {
  90.             dfa *d1 = PyGrammar_FindDFA(g, type);
  91.             int ibit;
  92.             if (type - NT_OFFSET >= (1 << 7)) {
  93.                 printf("XXX too high nonterminal number!\n");
  94.                 continue;
  95.             }
  96.             for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
  97.                 if (testbit(d1->d_first, ibit)) {
  98. #ifdef applec
  99. #define MPW_881_BUG            /* Undefine if bug below is fixed */
  100. #endif
  101. #ifdef MPW_881_BUG
  102.                     /* In 881 mode MPW 3.1 has a code
  103.                        generation bug which seems to
  104.                        set the upper bits; fix this by
  105.                        explicitly masking them off */
  106.                     int temp;
  107. #endif
  108.                     if (accel[ibit] != -1)
  109.                         printf("XXX ambiguity!\n");
  110. #ifdef MPW_881_BUG
  111.                     temp = 0xFFFF &
  112.                         (a->a_arrow | (1 << 7) |
  113.                          ((type - NT_OFFSET) << 8));
  114.                     accel[ibit] = temp;
  115. #else
  116.                     accel[ibit] = a->a_arrow | (1 << 7) |
  117.                         ((type - NT_OFFSET) << 8);
  118. #endif
  119.                 }
  120.             }
  121.         }
  122.         else if (lbl == EMPTY)
  123.             s->s_accept = 1;
  124.         else if (lbl >= 0 && lbl < nl)
  125.             accel[lbl] = a->a_arrow;
  126.     }
  127.     while (nl > 0 && accel[nl-1] == -1)
  128.         nl--;
  129.     for (k = 0; k < nl && accel[k] == -1;)
  130.         k++;
  131.     if (k < nl) {
  132.         int i;
  133.         s->s_accel = PyMem_NEW(int, nl-k);
  134.         if (s->s_accel == NULL) {
  135.             fprintf(stderr, "no mem to add parser accelerators\n");
  136.             exit(1);
  137.         }
  138.         s->s_lower = k;
  139.         s->s_upper = nl;
  140.         for (i = 0; k < nl; i++, k++)
  141.             s->s_accel[i] = accel[k];
  142.     }
  143.     PyMem_DEL(accel);
  144. }
  145.