← Back to branch summary

~ubuntu-branches/ubuntu/karmic/firebird2.1/karmic

« back to all changes in this revision

Viewing changes to extern/btyacc/closure.c

  • Committer: Bazaar Package Importer
  • Author(s): Damyan Ivanov
  • Date: 2008-05-26 23:59:25 UTC
  • Revision ID: james.westby@ubuntu.com-20080526235925-2pnqj6nxpppoeaer
Tags: upstream-2.1.0.17798-0.ds2
Import upstream version 2.1.0.17798-0.ds2

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/btyacc/closure.c
 
1
#include "defs.h"
 
2
 
 
3
Yshort *itemset;
 
4
Yshort *itemsetend;
 
5
unsigned *ruleset;
 
6
 
 
7
static unsigned *first_derives;
 
8
static unsigned *EFF;
 
9
 
 
10
 
 
11
void set_EFF()
 
12
{
 
13
    register unsigned *row;
 
14
    register int symbol;
 
15
    register Yshort *sp;
 
16
    register int rowsize;
 
17
    register int i;
 
18
    register int rule;
 
19
 
 
20
    rowsize = WORDSIZE(nvars);
 
21
    EFF = NEW2(nvars * rowsize, unsigned);
 
22
 
 
23
    row = EFF;
 
24
    for (i = start_symbol; i < nsyms; i++)
 
25
    {
 
26
        sp = derives[i];
 
27
        for (rule = *sp; rule > 0; rule = *++sp)
 
28
        {
 
29
            symbol = ritem[rrhs[rule]];
 
30
            if (ISVAR(symbol))
 
31
            {
 
32
                symbol -= start_symbol;
 
33
                SETBIT(row, symbol);
 
34
            }
 
35
        }
 
36
        row += rowsize;
 
37
    }
 
38
 
 
39
    reflexive_transitive_closure(EFF, nvars);
 
40
 
 
41
#ifdef  DEBUG
 
42
    print_EFF();
 
43
#endif
 
44
}
 
45
 
 
46
 
 
47
void set_first_derives()
 
48
{
 
49
  register unsigned *rrow;
 
50
  register unsigned *vrow;
 
51
  register int j;
 
52
  register unsigned mask;
 
53
  register unsigned cword;
 
54
  register Yshort *rp;
 
55
 
 
56
  int rule;
 
57
  int i;
 
58
  int rulesetsize;
 
59
  int varsetsize;
 
60
 
 
61
  rulesetsize = WORDSIZE(nrules);
 
62
  varsetsize = WORDSIZE(nvars);
 
63
  first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
 
64
 
 
65
  set_EFF();
 
66
 
 
67
  rrow = first_derives + ntokens * rulesetsize;
 
68
  for (i = start_symbol; i < nsyms; i++)
 
69
    {
 
70
      vrow = EFF + ((i - ntokens) * varsetsize);
 
71
      cword = *vrow++;
 
72
      mask = 1;
 
73
      for (j = start_symbol; j < nsyms; j++)
 
74
        {
 
75
          if (cword & mask)
 
76
            {
 
77
              rp = derives[j];
 
78
              while ((rule = *rp++) >= 0)
 
79
                {
 
80
                  SETBIT(rrow, rule);
 
81
                }
 
82
            }
 
83
 
 
84
          mask <<= 1;
 
85
          if (mask == 0)
 
86
            {
 
87
              cword = *vrow++;
 
88
              mask = 1;
 
89
            }
 
90
        }
 
91
 
 
92
      vrow += varsetsize;
 
93
      rrow += rulesetsize;
 
94
    }
 
95
 
 
96
#ifdef  DEBUG
 
97
  print_first_derives();
 
98
#endif
 
99
 
 
100
  FREE(EFF);
 
101
}
 
102
 
 
103
 
 
104
void closure(Yshort *nucleus, int n)
 
105
{
 
106
    register int ruleno;
 
107
    register unsigned word;
 
108
    register unsigned mask;
 
109
    register Yshort *csp;
 
110
    register unsigned *dsp;
 
111
    register unsigned *rsp;
 
112
    register int rulesetsize;
 
113
 
 
114
    Yshort *csend;
 
115
    unsigned *rsend;
 
116
    int symbol;
 
117
    int itemno;
 
118
 
 
119
    rulesetsize = WORDSIZE(nrules);
 
120
    rsp = ruleset;
 
121
    rsend = ruleset + rulesetsize;
 
122
    for (rsp = ruleset; rsp < rsend; rsp++)
 
123
        *rsp = 0;
 
124
 
 
125
    csend = nucleus + n;
 
126
    for (csp = nucleus; csp < csend; ++csp)
 
127
    {
 
128
        symbol = ritem[*csp];
 
129
        if (ISVAR(symbol))
 
130
        {
 
131
            dsp = first_derives + symbol * rulesetsize;
 
132
            rsp = ruleset;
 
133
            while (rsp < rsend)
 
134
                *rsp++ |= *dsp++;
 
135
        }
 
136
    }
 
137
 
 
138
    ruleno = 0;
 
139
    itemsetend = itemset;
 
140
    csp = nucleus;
 
141
    for (rsp = ruleset; rsp < rsend; ++rsp)
 
142
    {
 
143
        word = *rsp;
 
144
        if (word == 0)
 
145
            ruleno += BITS_PER_WORD;
 
146
        else
 
147
        {
 
148
            mask = 1;
 
149
            while (mask)
 
150
            {
 
151
                if (word & mask)
 
152
                {
 
153
                    itemno = rrhs[ruleno];
 
154
                    while (csp < csend && *csp < itemno)
 
155
                        *itemsetend++ = *csp++;
 
156
                    *itemsetend++ = itemno;
 
157
                    while (csp < csend && *csp == itemno)
 
158
                        ++csp;
 
159
                }
 
160
 
 
161
                    mask <<= 1;
 
162
                    ++ruleno;
 
163
            }
 
164
        }
 
165
    }
 
166
 
 
167
    while (csp < csend)
 
168
        *itemsetend++ = *csp++;
 
169
 
 
170
#ifdef  DEBUG
 
171
  print_closure(n);
 
172
#endif
 
173
}
 
174
 
 
175
 
 
176
 
 
177
void finalize_closure()
 
178
{
 
179
  FREE(itemset);
 
180
  FREE(ruleset);
 
181
  FREE(first_derives + ntokens * WORDSIZE(nrules));
 
182
}
 
183
 
 
184
 
 
185
#ifdef  DEBUG
 
186
 
 
187
void print_closure(int n)
 
188
{
 
189
  register Yshort *isp;
 
190
 
 
191
  printf("\n\nn = %d\n\n", n);
 
192
  for (isp = itemset; isp < itemsetend; isp++)
 
193
    printf("   %d\n", *isp);
 
194
}
 
195
 
 
196
 
 
197
void print_EFF()
 
198
{
 
199
    register int i, j;
 
200
    register unsigned *rowp;
 
201
    register unsigned word;
 
202
    register unsigned mask;
 
203
 
 
204
    printf("\n\nEpsilon Free Firsts\n");
 
205
 
 
206
    for (i = start_symbol; i < nsyms; i++)
 
207
    {
 
208
        printf("\n%s", symbol_name[i]);
 
209
        rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
 
210
        word = *rowp++;
 
211
 
 
212
        mask = 1;
 
213
        for (j = 0; j < nvars; j++)
 
214
        {
 
215
            if (word & mask)
 
216
                printf("  %s", symbol_name[start_symbol + j]);
 
217
 
 
218
            mask <<= 1;
 
219
            if (mask == 0)
 
220
            {
 
221
                word = *rowp++;
 
222
                mask = 1;
 
223
            }
 
224
        }
 
225
    }
 
226
}
 
227
 
 
228
 
 
229
void print_first_derives()
 
230
{
 
231
  register int i;
 
232
  register int j;
 
233
  register unsigned *rp;
 
234
  register unsigned cword;
 
235
  register unsigned mask;
 
236
 
 
237
  printf("\n\n\nFirst Derives\n");
 
238
 
 
239
  for (i = start_symbol; i < nsyms; i++)
 
240
    {
 
241
      printf("\n%s derives\n", symbol_name[i]);
 
242
      rp = first_derives + i * WORDSIZE(nrules);
 
243
      cword = *rp++;
 
244
      mask = 1;
 
245
      for (j = 0; j <= nrules; j++)
 
246
        {
 
247
          if (cword & mask)
 
248
            printf("   %d\n", j);
 
249
 
 
250
          mask <<= 1;
 
251
          if (mask == 0)
 
252
            {
 
253
              cword = *rp++;
 
254
              mask = 1;
 
255
            }
 
256
        }
 
257
    }
 
258
 
 
259
  fflush(stdout);
 
260
}
 
261
 
 
262
#endif