← Back to branch summary

~ubuntu-branches/ubuntu/maverick/python3.1/maverick

« back to all changes in this revision

Viewing changes to Parser/acceler.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2009-03-23 00:01:27 UTC
  • Revision ID: james.westby@ubuntu.com-20090323000127-5fstfxju4ufrhthq
Tags: upstream-3.1~a1+20090322
Import upstream version 3.1~a1+20090322

Show diffs side-by-side

added added

removed removed

Lines of Context:
Parser/acceler.c
 
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
        d = g->g_dfa;
 
29
        for (i = g->g_ndfas; --i >= 0; d++)
 
30
                fixdfa(g, d);
 
31
        g->g_accel = 1;
 
32
}
 
33
 
 
34
void
 
35
PyGrammar_RemoveAccelerators(grammar *g)
 
36
{
 
37
        dfa *d;
 
38
        int i;
 
39
        g->g_accel = 0;
 
40
        d = g->g_dfa;
 
41
        for (i = g->g_ndfas; --i >= 0; d++) {
 
42
                state *s;
 
43
                int j;
 
44
                s = d->d_state;
 
45
                for (j = 0; j < d->d_nstates; j++, s++) {
 
46
                        if (s->s_accel)
 
47
                                PyObject_FREE(s->s_accel);
 
48
                        s->s_accel = NULL;
 
49
                }
 
50
        }
 
51
}
 
52
 
 
53
static void
 
54
fixdfa(grammar *g, dfa *d)
 
55
{
 
56
        state *s;
 
57
        int j;
 
58
        s = d->d_state;
 
59
        for (j = 0; j < d->d_nstates; j++, s++)
 
60
                fixstate(g, s);
 
61
}
 
62
 
 
63
static void
 
64
fixstate(grammar *g, state *s)
 
65
{
 
66
        arc *a;
 
67
        int k;
 
68
        int *accel;
 
69
        int nl = g->g_ll.ll_nlabels;
 
70
        s->s_accept = 0;
 
71
        accel = (int *) PyObject_MALLOC(nl * sizeof(int));
 
72
        if (accel == NULL) {
 
73
                fprintf(stderr, "no mem to build parser accelerators\n");
 
74
                exit(1);
 
75
        }
 
76
        for (k = 0; k < nl; k++)
 
77
                accel[k] = -1;
 
78
        a = s->s_arc;
 
79
        for (k = s->s_narcs; --k >= 0; a++) {
 
80
                int lbl = a->a_lbl;
 
81
                label *l = &g->g_ll.ll_label[lbl];
 
82
                int type = l->lb_type;
 
83
                if (a->a_arrow >= (1 << 7)) {
 
84
                        printf("XXX too many states!\n");
 
85
                        continue;
 
86
                }
 
87
                if (ISNONTERMINAL(type)) {
 
88
                        dfa *d1 = PyGrammar_FindDFA(g, type);
 
89
                        int ibit;
 
90
                        if (type - NT_OFFSET >= (1 << 7)) {
 
91
                                printf("XXX too high nonterminal number!\n");
 
92
                                continue;
 
93
                        }
 
94
                        for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
 
95
                                if (testbit(d1->d_first, ibit)) {
 
96
                                        if (accel[ibit] != -1)
 
97
                                                printf("XXX ambiguity!\n");
 
98
                                        accel[ibit] = a->a_arrow | (1 << 7) |
 
99
                                                ((type - NT_OFFSET) << 8);
 
100
                                }
 
101
                        }
 
102
                }
 
103
                else if (lbl == EMPTY)
 
104
                        s->s_accept = 1;
 
105
                else if (lbl >= 0 && lbl < nl)
 
106
                        accel[lbl] = a->a_arrow;
 
107
        }
 
108
        while (nl > 0 && accel[nl-1] == -1)
 
109
                nl--;
 
110
        for (k = 0; k < nl && accel[k] == -1;)
 
111
                k++;
 
112
        if (k < nl) {
 
113
                int i;
 
114
                s->s_accel = (int *) PyObject_MALLOC((nl-k) * sizeof(int));
 
115
                if (s->s_accel == NULL) {
 
116
                        fprintf(stderr, "no mem to add parser accelerators\n");
 
117
                        exit(1);
 
118
                }
 
119
                s->s_lower = k;
 
120
                s->s_upper = nl;
 
121
                for (i = 0; k < nl; i++, k++)
 
122
                        s->s_accel[i] = accel[k];
 
123
        }
 
124
        PyObject_FREE(accel);
 
125
}