Ignore:
Timestamp:
Mar 19, 2014, 11:11:30 AM (11 years ago)
Author:
dmik
Message:

python: Update vendor to 2.7.6.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • python/vendor/current/Parser/pgen.c

    r2 r388  
    1818
    1919typedef struct _nfaarc {
    20         int     ar_label;
    21         int     ar_arrow;
     20    int         ar_label;
     21    int         ar_arrow;
    2222} nfaarc;
    2323
    2424typedef struct _nfastate {
    25         int     st_narcs;
    26         nfaarc  *st_arc;
     25    int         st_narcs;
     26    nfaarc      *st_arc;
    2727} nfastate;
    2828
    2929typedef struct _nfa {
    30         int             nf_type;
    31         char            *nf_name;
    32         int             nf_nstates;
    33         nfastate        *nf_state;
    34         int             nf_start, nf_finish;
     30    int                 nf_type;
     31    char                *nf_name;
     32    int                 nf_nstates;
     33    nfastate            *nf_state;
     34    int                 nf_start, nf_finish;
    3535} nfa;
    3636
    3737/* Forward */
    3838static void compile_rhs(labellist *ll,
    39                         nfa *nf, node *n, int *pa, int *pb);
     39                        nfa *nf, node *n, int *pa, int *pb);
    4040static void compile_alt(labellist *ll,
    41                         nfa *nf, node *n, int *pa, int *pb);
     41                        nfa *nf, node *n, int *pa, int *pb);
    4242static void compile_item(labellist *ll,
    43                         nfa *nf, node *n, int *pa, int *pb);
     43                        nfa *nf, node *n, int *pa, int *pb);
    4444static void compile_atom(labellist *ll,
    45                         nfa *nf, node *n, int *pa, int *pb);
     45                        nfa *nf, node *n, int *pa, int *pb);
    4646
    4747static int
    4848addnfastate(nfa *nf)
    4949{
    50         nfastate *st;
    51        
    52         nf->nf_state = (nfastate *)PyObject_REALLOC(nf->nf_state,
    53                                     sizeof(nfastate) * (nf->nf_nstates + 1));
    54         if (nf->nf_state == NULL)
    55                 Py_FatalError("out of mem");
    56         st = &nf->nf_state[nf->nf_nstates++];
    57         st->st_narcs = 0;
    58         st->st_arc = NULL;
    59         return st - nf->nf_state;
     50    nfastate *st;
     51
     52    nf->nf_state = (nfastate *)PyObject_REALLOC(nf->nf_state,
     53                                sizeof(nfastate) * (nf->nf_nstates + 1));
     54    if (nf->nf_state == NULL)
     55        Py_FatalError("out of mem");
     56    st = &nf->nf_state[nf->nf_nstates++];
     57    st->st_narcs = 0;
     58    st->st_arc = NULL;
     59    return st - nf->nf_state;
    6060}
    6161
    … …  
    6363addnfaarc(nfa *nf, int from, int to, int lbl)
    6464{
    65         nfastate *st;
    66         nfaarc *ar;
    67        
    68         st = &nf->nf_state[from];
    69         st->st_arc = (nfaarc *)PyObject_REALLOC(st->st_arc,
    70                                       sizeof(nfaarc) * (st->st_narcs + 1));
    71         if (st->st_arc == NULL)
    72                 Py_FatalError("out of mem");
    73         ar = &st->st_arc[st->st_narcs++];
    74         ar->ar_label = lbl;
    75         ar->ar_arrow = to;
     65    nfastate *st;
     66    nfaarc *ar;
     67
     68    st = &nf->nf_state[from];
     69    st->st_arc = (nfaarc *)PyObject_REALLOC(st->st_arc,
     70                                  sizeof(nfaarc) * (st->st_narcs + 1));
     71    if (st->st_arc == NULL)
     72        Py_FatalError("out of mem");
     73    ar = &st->st_arc[st->st_narcs++];
     74    ar->ar_label = lbl;
     75    ar->ar_arrow = to;
    7676}
    7777
    … …  
    7979newnfa(char *name)
    8080{
    81         nfa *nf;
    82         static int type = NT_OFFSET; /* All types will be disjunct */
    83        
    84         nf = (nfa *)PyObject_MALLOC(sizeof(nfa));
    85         if (nf == NULL)
    86                 Py_FatalError("no mem for new nfa");
    87         nf->nf_type = type++;
    88         nf->nf_name = name; /* XXX strdup(name) ??? */
    89         nf->nf_nstates = 0;
    90         nf->nf_state = NULL;
    91         nf->nf_start = nf->nf_finish = -1;
    92         return nf;
     81    nfa *nf;
     82    static int type = NT_OFFSET; /* All types will be disjunct */
     83
     84    nf = (nfa *)PyObject_MALLOC(sizeof(nfa));
     85    if (nf == NULL)
     86        Py_FatalError("no mem for new nfa");
     87    nf->nf_type = type++;
     88    nf->nf_name = name; /* XXX strdup(name) ??? */
     89    nf->nf_nstates = 0;
     90    nf->nf_state = NULL;
     91    nf->nf_start = nf->nf_finish = -1;
     92    return nf;
    9393}
    9494
    9595typedef struct _nfagrammar {
    96         int             gr_nnfas;
    97         nfa             **gr_nfa;
    98         labellist       gr_ll;
     96    int                 gr_nnfas;
     97    nfa                 **gr_nfa;
     98    labellist           gr_ll;
    9999} nfagrammar;
    100100
    … …  
    105105newnfagrammar(void)
    106106{
    107         nfagrammar *gr;
    108        
    109         gr = (nfagrammar *)PyObject_MALLOC(sizeof(nfagrammar));
    110         if (gr == NULL)
    111                 Py_FatalError("no mem for new nfa grammar");
    112         gr->gr_nnfas = 0;
    113         gr->gr_nfa = NULL;
    114         gr->gr_ll.ll_nlabels = 0;
    115         gr->gr_ll.ll_label = NULL;
    116         addlabel(&gr->gr_ll, ENDMARKER, "EMPTY");
    117         return gr;
     107    nfagrammar *gr;
     108
     109    gr = (nfagrammar *)PyObject_MALLOC(sizeof(nfagrammar));
     110    if (gr == NULL)
     111        Py_FatalError("no mem for new nfa grammar");
     112    gr->gr_nnfas = 0;
     113    gr->gr_nfa = NULL;
     114    gr->gr_ll.ll_nlabels = 0;
     115    gr->gr_ll.ll_label = NULL;
     116    addlabel(&gr->gr_ll, ENDMARKER, "EMPTY");
     117    return gr;
    118118}
    119119
    … …  
    121121addnfa(nfagrammar *gr, char *name)
    122122{
    123         nfa *nf;
    124        
    125         nf = newnfa(name);
    126         gr->gr_nfa = (nfa **)PyObject_REALLOC(gr->gr_nfa,
    127                                       sizeof(nfa*) * (gr->gr_nnfas + 1));
    128         if (gr->gr_nfa == NULL)
    129                 Py_FatalError("out of mem");
    130         gr->gr_nfa[gr->gr_nnfas++] = nf;
    131         addlabel(&gr->gr_ll, NAME, nf->nf_name);
    132         return nf;
     123    nfa *nf;
     124
     125    nf = newnfa(name);
     126    gr->gr_nfa = (nfa **)PyObject_REALLOC(gr->gr_nfa,
     127                                  sizeof(nfa*) * (gr->gr_nnfas + 1));
     128    if (gr->gr_nfa == NULL)
     129        Py_FatalError("out of mem");
     130    gr->gr_nfa[gr->gr_nnfas++] = nf;
     131    addlabel(&gr->gr_ll, NAME, nf->nf_name);
     132    return nf;
    133133}
    134134
    … …  
    138138
    139139#define REQN(i, count) \
    140         if (i < count) { \
    141                 fprintf(stderr, REQNFMT, count); \
    142                 Py_FatalError("REQN"); \
    143         } else
     140    if (i < count) { \
     141        fprintf(stderr, REQNFMT, count); \
     142        Py_FatalError("REQN"); \
     143    } else
    144144
    145145#else
    146 #define REQN(i, count)  /* empty */
     146#define REQN(i, count)  /* empty */
    147147#endif
    148148
    … …  
    150150metacompile(node *n)
    151151{
    152         nfagrammar *gr;
    153         int i;
    154 
    155         if (Py_DebugFlag)
    156                 printf("Compiling (meta-) parse tree into NFA grammar\n");
    157         gr = newnfagrammar();
    158         REQ(n, MSTART);
    159         i = n->n_nchildren - 1; /* Last child is ENDMARKER */
    160         n = n->n_child;
    161         for (; --i >= 0; n++) {
    162                 if (n->n_type != NEWLINE)
    163                         compile_rule(gr, n);
    164         }
    165         return gr;
     152    nfagrammar *gr;
     153    int i;
     154
     155    if (Py_DebugFlag)
     156        printf("Compiling (meta-) parse tree into NFA grammar\n");
     157    gr = newnfagrammar();
     158    REQ(n, MSTART);
     159    i = n->n_nchildren - 1; /* Last child is ENDMARKER */
     160    n = n->n_child;
     161    for (; --i >= 0; n++) {
     162        if (n->n_type != NEWLINE)
     163            compile_rule(gr, n);
     164    }
     165    return gr;
    166166}
    167167
    … …  
    169169compile_rule(nfagrammar *gr, node *n)
    170170{
    171         nfa *nf;
    172        
    173         REQ(n, RULE);
    174         REQN(n->n_nchildren, 4);
    175         n = n->n_child;
    176         REQ(n, NAME);
    177         nf = addnfa(gr, n->n_str);
    178         n++;
    179         REQ(n, COLON);
    180         n++;
    181         REQ(n, RHS);
    182         compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);
    183         n++;
    184         REQ(n, NEWLINE);
     171    nfa *nf;
     172
     173    REQ(n, RULE);
     174    REQN(n->n_nchildren, 4);
     175    n = n->n_child;
     176    REQ(n, NAME);
     177    nf = addnfa(gr, n->n_str);
     178    n++;
     179    REQ(n, COLON);
     180    n++;
     181    REQ(n, RHS);
     182    compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);
     183    n++;
     184    REQ(n, NEWLINE);
    185185}
    186186
    … …  
    188188compile_rhs(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
    189189{
    190         int i;
    191         int a, b;
    192        
    193         REQ(n, RHS);
    194         i = n->n_nchildren;
    195         REQN(i, 1);
    196         n = n->n_child;
    197         REQ(n, ALT);
    198         compile_alt(ll, nf, n, pa, pb);
    199         if (--i <= 0)
    200                 return;
    201         n++;
    202         a = *pa;
    203         b = *pb;
    204         *pa = addnfastate(nf);
    205         *pb = addnfastate(nf);
    206         addnfaarc(nf, *pa, a, EMPTY);
    207         addnfaarc(nf, b, *pb, EMPTY);
    208         for (; --i >= 0; n++) {
    209                 REQ(n, VBAR);
    210                 REQN(i, 1);
    211                 --i;
    212                 n++;
    213                 REQ(n, ALT);
    214                 compile_alt(ll, nf, n, &a, &b);
    215                 addnfaarc(nf, *pa, a, EMPTY);
    216                 addnfaarc(nf, b, *pb, EMPTY);
    217         }
     190    int i;
     191    int a, b;
     192
     193    REQ(n, RHS);
     194    i = n->n_nchildren;
     195    REQN(i, 1);
     196    n = n->n_child;
     197    REQ(n, ALT);
     198    compile_alt(ll, nf, n, pa, pb);
     199    if (--i <= 0)
     200        return;
     201    n++;
     202    a = *pa;
     203    b = *pb;
     204    *pa = addnfastate(nf);
     205    *pb = addnfastate(nf);
     206    addnfaarc(nf, *pa, a, EMPTY);
     207    addnfaarc(nf, b, *pb, EMPTY);
     208    for (; --i >= 0; n++) {
     209        REQ(n, VBAR);
     210        REQN(i, 1);
     211        --i;
     212        n++;
     213        REQ(n, ALT);
     214        compile_alt(ll, nf, n, &a, &b);
     215        addnfaarc(nf, *pa, a, EMPTY);
     216        addnfaarc(nf, b, *pb, EMPTY);
     217    }
    218218}
    219219
    … …  
    221221compile_alt(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
    222222{
    223         int i;
    224         int a, b;
    225        
    226         REQ(n, ALT);
    227         i = n->n_nchildren;
    228         REQN(i, 1);
    229         n = n->n_child;
    230         REQ(n, ITEM);
    231         compile_item(ll, nf, n, pa, pb);
    232         --i;
    233         n++;
    234         for (; --i >= 0; n++) {
    235                 REQ(n, ITEM);
    236                 compile_item(ll, nf, n, &a, &b);
    237                 addnfaarc(nf, *pb, a, EMPTY);
    238                 *pb = b;
    239         }
     223    int i;
     224    int a, b;
     225
     226    REQ(n, ALT);
     227    i = n->n_nchildren;
     228    REQN(i, 1);
     229    n = n->n_child;
     230    REQ(n, ITEM);
     231    compile_item(ll, nf, n, pa, pb);
     232    --i;
     233    n++;
     234    for (; --i >= 0; n++) {
     235        REQ(n, ITEM);
     236        compile_item(ll, nf, n, &a, &b);
     237        addnfaarc(nf, *pb, a, EMPTY);
     238        *pb = b;
     239    }
    240240}
    241241
    … …  
    243243compile_item(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
    244244{
    245         int i;
    246         int a, b;
    247        
    248         REQ(n, ITEM);
    249         i = n->n_nchildren;
    250         REQN(i, 1);
    251         n = n->n_child;
    252         if (n->n_type == LSQB) {
    253                 REQN(i, 3);
    254                 n++;
    255                 REQ(n, RHS);
    256                 *pa = addnfastate(nf);
    257                 *pb = addnfastate(nf);
    258                 addnfaarc(nf, *pa, *pb, EMPTY);
    259                 compile_rhs(ll, nf, n, &a, &b);
    260                 addnfaarc(nf, *pa, a, EMPTY);
    261                 addnfaarc(nf, b, *pb, EMPTY);
    262                 REQN(i, 1);
    263                 n++;
    264                 REQ(n, RSQB);
    265         }
    266         else {
    267                 compile_atom(ll, nf, n, pa, pb);
    268                 if (--i <= 0)
    269                         return;
    270                 n++;
    271                 addnfaarc(nf, *pb, *pa, EMPTY);
    272                 if (n->n_type == STAR)
    273                         *pb = *pa;
    274                 else
    275                         REQ(n, PLUS);
    276         }
     245    int i;
     246    int a, b;
     247
     248    REQ(n, ITEM);
     249    i = n->n_nchildren;
     250    REQN(i, 1);
     251    n = n->n_child;
     252    if (n->n_type == LSQB) {
     253        REQN(i, 3);
     254        n++;
     255        REQ(n, RHS);
     256        *pa = addnfastate(nf);
     257        *pb = addnfastate(nf);
     258        addnfaarc(nf, *pa, *pb, EMPTY);
     259        compile_rhs(ll, nf, n, &a, &b);
     260        addnfaarc(nf, *pa, a, EMPTY);
     261        addnfaarc(nf, b, *pb, EMPTY);
     262        REQN(i, 1);
     263        n++;
     264        REQ(n, RSQB);
     265    }
     266    else {
     267        compile_atom(ll, nf, n, pa, pb);
     268        if (--i <= 0)
     269            return;
     270        n++;
     271        addnfaarc(nf, *pb, *pa, EMPTY);
     272        if (n->n_type == STAR)
     273            *pb = *pa;
     274        else
     275            REQ(n, PLUS);
     276    }
    277277}
    278278
    … …  
    280280compile_atom(labellist *ll, nfa *nf, node *n, int *pa, int *pb)
    281281{
    282         int i;
    283        
    284         REQ(n, ATOM);
    285         i = n->n_nchildren;
    286         REQN(i, 1);
    287         n = n->n_child;
    288         if (n->n_type == LPAR) {
    289                 REQN(i, 3);
    290                 n++;
    291                 REQ(n, RHS);
    292                 compile_rhs(ll, nf, n, pa, pb);
    293                 n++;
    294                 REQ(n, RPAR);
    295         }
    296         else if (n->n_type == NAME || n->n_type == STRING) {
    297                 *pa = addnfastate(nf);
    298                 *pb = addnfastate(nf);
    299                 addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str));
    300         }
    301         else
    302                 REQ(n, NAME);
     282    int i;
     283
     284    REQ(n, ATOM);
     285    i = n->n_nchildren;
     286    REQN(i, 1);
     287    n = n->n_child;
     288    if (n->n_type == LPAR) {
     289        REQN(i, 3);
     290        n++;
     291        REQ(n, RHS);
     292        compile_rhs(ll, nf, n, pa, pb);
     293        n++;
     294        REQ(n, RPAR);
     295    }
     296    else if (n->n_type == NAME || n->n_type == STRING) {
     297        *pa = addnfastate(nf);
     298        *pb = addnfastate(nf);
     299        addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str));
     300    }
     301    else
     302        REQ(n, NAME);
    303303}
    304304
    … …  
    306306dumpstate(labellist *ll, nfa *nf, int istate)
    307307{
    308         nfastate *st;
    309         int i;
    310         nfaarc *ar;
    311        
    312         printf("%c%2d%c",
    313                 istate == nf->nf_start ? '*' : ' ',
    314                 istate,
    315                 istate == nf->nf_finish ? '.' : ' ');
    316         st = &nf->nf_state[istate];
    317         ar = st->st_arc;
    318         for (i = 0; i < st->st_narcs; i++) {
    319                 if (i > 0)
    320                         printf("\n    ");
    321                 printf("-> %2d  %s", ar->ar_arrow,
    322                         PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));
    323                 ar++;
    324         }
    325         printf("\n");
     308    nfastate *st;
     309    int i;
     310    nfaarc *ar;
     311
     312    printf("%c%2d%c",
     313        istate == nf->nf_start ? '*' : ' ',
     314        istate,
     315        istate == nf->nf_finish ? '.' : ' ');
     316    st = &nf->nf_state[istate];
     317    ar = st->st_arc;
     318    for (i = 0; i < st->st_narcs; i++) {
     319        if (i > 0)
     320            printf("\n    ");
     321        printf("-> %2d  %s", ar->ar_arrow,
     322            PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));
     323        ar++;
     324    }
     325    printf("\n");
    326326}
    327327
    … …  
    329329dumpnfa(labellist *ll, nfa *nf)
    330330{
    331         int i;
    332        
    333         printf("NFA '%s' has %d states; start %d, finish %d\n",
    334                 nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);
    335         for (i = 0; i < nf->nf_nstates; i++)
    336                 dumpstate(ll, nf, i);
     331    int i;
     332
     333    printf("NFA '%s' has %d states; start %d, finish %d\n",
     334        nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);
     335    for (i = 0; i < nf->nf_nstates; i++)
     336        dumpstate(ll, nf, i);
    337337}
    338338
    … …  
    343343addclosure(bitset ss, nfa *nf, int istate)
    344344{
    345         if (addbit(ss, istate)) {
    346                 nfastate *st = &nf->nf_state[istate];
    347                 nfaarc *ar = st->st_arc;
    348                 int i;
    349                
    350                 for (i = st->st_narcs; --i >= 0; ) {
    351                         if (ar->ar_label == EMPTY)
    352                                 addclosure(ss, nf, ar->ar_arrow);
    353                         ar++;
    354                 }
    355         }
     345    if (addbit(ss, istate)) {
     346        nfastate *st = &nf->nf_state[istate];
     347        nfaarc *ar = st->st_arc;
     348        int i;
     349
     350        for (i = st->st_narcs; --i >= 0; ) {
     351            if (ar->ar_label == EMPTY)
     352                addclosure(ss, nf, ar->ar_arrow);
     353            ar++;
     354        }
     355    }
    356356}
    357357
    358358typedef struct _ss_arc {
    359         bitset  sa_bitset;
    360         int     sa_arrow;
    361         int     sa_label;
     359    bitset      sa_bitset;
     360    int         sa_arrow;
     361    int         sa_label;
    362362} ss_arc;
    363363
    364364typedef struct _ss_state {
    365         bitset  ss_ss;
    366         int     ss_narcs;
    367         struct _ss_arc  *ss_arc;
    368         int     ss_deleted;
    369         int     ss_finish;
    370         int     ss_rename;
     365    bitset      ss_ss;
     366    int         ss_narcs;
     367    struct _ss_arc      *ss_arc;
     368    int         ss_deleted;
     369    int         ss_finish;
     370    int         ss_rename;
    371371} ss_state;
    372372
    373373typedef struct _ss_dfa {
    374         int     sd_nstates;
    375         ss_state *sd_state;
     374    int         sd_nstates;
     375    ss_state *sd_state;
    376376} ss_dfa;
    377377
    378378/* Forward */
    379379static void printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
    380                        labellist *ll, char *msg);
     380                       labellist *ll, char *msg);
    381381static void simplify(int xx_nstates, ss_state *xx_state);
    382382static void convert(dfa *d, int xx_nstates, ss_state *xx_state);
    … …  
    385385makedfa(nfagrammar *gr, nfa *nf, dfa *d)
    386386{
    387         int nbits = nf->nf_nstates;
    388         bitset ss;
    389         int xx_nstates;
    390         ss_state *xx_state, *yy;
    391         ss_arc *zz;
    392         int istate, jstate, iarc, jarc, ibit;
    393         nfastate *st;
    394         nfaarc *ar;
    395        
    396         ss = newbitset(nbits);
    397         addclosure(ss, nf, nf->nf_start);
    398         xx_state = (ss_state *)PyObject_MALLOC(sizeof(ss_state));
    399         if (xx_state == NULL)
    400                 Py_FatalError("no mem for xx_state in makedfa");
    401         xx_nstates = 1;
    402         yy = &xx_state[0];
    403         yy->ss_ss = ss;
    404         yy->ss_narcs = 0;
    405         yy->ss_arc = NULL;
    406         yy->ss_deleted = 0;
    407         yy->ss_finish = testbit(ss, nf->nf_finish);
    408         if (yy->ss_finish)
    409                 printf("Error: nonterminal '%s' may produce empty.\n",
    410                         nf->nf_name);
    411        
    412         /* This algorithm is from a book written before
    413            the invention of structured programming... */
    414 
    415         /* For each unmarked state... */
    416         for (istate = 0; istate < xx_nstates; ++istate) {
    417                 size_t size;
    418                 yy = &xx_state[istate];
    419                 ss = yy->ss_ss;
    420                 /* For all its states... */
    421                 for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {
    422                         if (!testbit(ss, ibit))
    423                                 continue;
    424                         st = &nf->nf_state[ibit];
    425                         /* For all non-empty arcs from this state... */
    426                         for (iarc = 0; iarc < st->st_narcs; iarc++) {
    427                                 ar = &st->st_arc[iarc];
    428                                 if (ar->ar_label == EMPTY)
    429                                         continue;
    430                                 /* Look up in list of arcs from this state */
    431                                 for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {
    432                                         zz = &yy->ss_arc[jarc];
    433                                         if (ar->ar_label == zz->sa_label)
    434                                                 goto found;
    435                                 }
    436                                 /* Add new arc for this state */
    437                                 size = sizeof(ss_arc) * (yy->ss_narcs + 1);
    438                                 yy->ss_arc = (ss_arc *)PyObject_REALLOC(
    439                                                             yy->ss_arc, size);
    440                                 if (yy->ss_arc == NULL)
    441                                         Py_FatalError("out of mem");
    442                                 zz = &yy->ss_arc[yy->ss_narcs++];
    443                                 zz->sa_label = ar->ar_label;
    444                                 zz->sa_bitset = newbitset(nbits);
    445                                 zz->sa_arrow = -1;
    446                          found: ;
    447                                 /* Add destination */
    448                                 addclosure(zz->sa_bitset, nf, ar->ar_arrow);
    449                         }
    450                 }
    451                 /* Now look up all the arrow states */
    452                 for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {
    453                         zz = &xx_state[istate].ss_arc[jarc];
    454                         for (jstate = 0; jstate < xx_nstates; jstate++) {
    455                                 if (samebitset(zz->sa_bitset,
    456                                         xx_state[jstate].ss_ss, nbits)) {
    457                                         zz->sa_arrow = jstate;
    458                                         goto done;
    459                                 }
    460                         }
    461                         size = sizeof(ss_state) * (xx_nstates + 1);
    462                         xx_state = (ss_state *)PyObject_REALLOC(xx_state,
    463                                                                     size);
    464                         if (xx_state == NULL)
    465                                 Py_FatalError("out of mem");
    466                         zz->sa_arrow = xx_nstates;
    467                         yy = &xx_state[xx_nstates++];
    468                         yy->ss_ss = zz->sa_bitset;
    469                         yy->ss_narcs = 0;
    470                         yy->ss_arc = NULL;
    471                         yy->ss_deleted = 0;
    472                         yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish);
    473                  done:  ;
    474                 }
    475         }
    476        
    477         if (Py_DebugFlag)
    478                 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
    479                                                 "before minimizing");
    480        
    481         simplify(xx_nstates, xx_state);
    482        
    483         if (Py_DebugFlag)
    484                 printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
    485                                                 "after minimizing");
    486        
    487         convert(d, xx_nstates, xx_state);
    488        
    489         /* XXX cleanup */
    490         PyObject_FREE(xx_state);
     387    int nbits = nf->nf_nstates;
     388    bitset ss;
     389    int xx_nstates;
     390    ss_state *xx_state, *yy;
     391    ss_arc *zz;
     392    int istate, jstate, iarc, jarc, ibit;
     393    nfastate *st;
     394    nfaarc *ar;
     395
     396    ss = newbitset(nbits);
     397    addclosure(ss, nf, nf->nf_start);
     398    xx_state = (ss_state *)PyObject_MALLOC(sizeof(ss_state));
     399    if (xx_state == NULL)
     400        Py_FatalError("no mem for xx_state in makedfa");
     401    xx_nstates = 1;
     402    yy = &xx_state[0];
     403    yy->ss_ss = ss;
     404    yy->ss_narcs = 0;
     405    yy->ss_arc = NULL;
     406    yy->ss_deleted = 0;
     407    yy->ss_finish = testbit(ss, nf->nf_finish);
     408    if (yy->ss_finish)
     409        printf("Error: nonterminal '%s' may produce empty.\n",
     410            nf->nf_name);
     411
     412    /* This algorithm is from a book written before
     413       the invention of structured programming... */
     414
     415    /* For each unmarked state... */
     416    for (istate = 0; istate < xx_nstates; ++istate) {
     417        size_t size;
     418        yy = &xx_state[istate];
     419        ss = yy->ss_ss;
     420        /* For all its states... */
     421        for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {
     422            if (!testbit(ss, ibit))
     423                continue;
     424            st = &nf->nf_state[ibit];
     425            /* For all non-empty arcs from this state... */
     426            for (iarc = 0; iarc < st->st_narcs; iarc++) {
     427                ar = &st->st_arc[iarc];
     428                if (ar->ar_label == EMPTY)
     429                    continue;
     430                /* Look up in list of arcs from this state */
     431                for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {
     432                    zz = &yy->ss_arc[jarc];
     433                    if (ar->ar_label == zz->sa_label)
     434                        goto found;
     435                }
     436                /* Add new arc for this state */
     437                size = sizeof(ss_arc) * (yy->ss_narcs + 1);
     438                yy->ss_arc = (ss_arc *)PyObject_REALLOC(
     439                                            yy->ss_arc, size);
     440                if (yy->ss_arc == NULL)
     441                    Py_FatalError("out of mem");
     442                zz = &yy->ss_arc[yy->ss_narcs++];
     443                zz->sa_label = ar->ar_label;
     444                zz->sa_bitset = newbitset(nbits);
     445                zz->sa_arrow = -1;
     446             found:             ;
     447                /* Add destination */
     448                addclosure(zz->sa_bitset, nf, ar->ar_arrow);
     449            }
     450        }
     451        /* Now look up all the arrow states */
     452        for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {
     453            zz = &xx_state[istate].ss_arc[jarc];
     454            for (jstate = 0; jstate < xx_nstates; jstate++) {
     455                if (samebitset(zz->sa_bitset,
     456                    xx_state[jstate].ss_ss, nbits)) {
     457                    zz->sa_arrow = jstate;
     458                    goto done;
     459                }
     460            }
     461            size = sizeof(ss_state) * (xx_nstates + 1);
     462            xx_state = (ss_state *)PyObject_REALLOC(xx_state,
     463                                                        size);
     464            if (xx_state == NULL)
     465                Py_FatalError("out of mem");
     466            zz->sa_arrow = xx_nstates;
     467            yy = &xx_state[xx_nstates++];
     468            yy->ss_ss = zz->sa_bitset;
     469            yy->ss_narcs = 0;
     470            yy->ss_arc = NULL;
     471            yy->ss_deleted = 0;
     472            yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish);
     473         done:          ;
     474        }
     475    }
     476
     477    if (Py_DebugFlag)
     478        printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
     479                                        "before minimizing");
     480
     481    simplify(xx_nstates, xx_state);
     482
     483    if (Py_DebugFlag)
     484        printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
     485                                        "after minimizing");
     486
     487    convert(d, xx_nstates, xx_state);
     488
     489    /* XXX cleanup */
     490    PyObject_FREE(xx_state);
    491491}
    492492
    493493static void
    494494printssdfa(int xx_nstates, ss_state *xx_state, int nbits,
    495            labellist *ll, char *msg)
    496 {
    497         int i, ibit, iarc;
    498         ss_state *yy;
    499         ss_arc *zz;
    500        
    501         printf("Subset DFA %s\n", msg);
    502         for (i = 0; i < xx_nstates; i++) {
    503                 yy = &xx_state[i];
    504                 if (yy->ss_deleted)
    505                         continue;
    506                 printf(" Subset %d", i);
    507                 if (yy->ss_finish)
    508                         printf(" (finish)");
    509                 printf(" { ");
    510                 for (ibit = 0; ibit < nbits; ibit++) {
    511                         if (testbit(yy->ss_ss, ibit))
    512                                 printf("%d ", ibit);
    513                 }
    514                 printf("}\n");
    515                 for (iarc = 0; iarc < yy->ss_narcs; iarc++) {
    516                         zz = &yy->ss_arc[iarc];
    517                         printf("  Arc to state %d, label %s\n",
    518                                 zz->sa_arrow,
    519                                 PyGrammar_LabelRepr(
    520                                         &ll->ll_label[zz->sa_label]));
    521                 }
    522         }
     495           labellist *ll, char *msg)
     496{
     497    int i, ibit, iarc;
     498    ss_state *yy;
     499    ss_arc *zz;
     500
     501    printf("Subset DFA %s\n", msg);
     502    for (i = 0; i < xx_nstates; i++) {
     503        yy = &xx_state[i];
     504        if (yy->ss_deleted)
     505            continue;
     506        printf(" Subset %d", i);
     507        if (yy->ss_finish)
     508            printf(" (finish)");
     509        printf(" { ");
     510        for (ibit = 0; ibit < nbits; ibit++) {
     511            if (testbit(yy->ss_ss, ibit))
     512                printf("%d ", ibit);
     513        }
     514        printf("}\n");
     515        for (iarc = 0; iarc < yy->ss_narcs; iarc++) {
     516            zz = &yy->ss_arc[iarc];
     517            printf("  Arc to state %d, label %s\n",
     518                zz->sa_arrow,
     519                PyGrammar_LabelRepr(
     520                    &ll->ll_label[zz->sa_label]));
     521        }
     522    }
    523523}
    524524
    … …  
    536536samestate(ss_state *s1, ss_state *s2)
    537537{
    538         int i;
    539        
    540         if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish)
    541                 return 0;
    542         for (i = 0; i < s1->ss_narcs; i++) {
    543                 if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow ||
    544                         s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label)
    545                         return 0;
    546         }
    547         return 1;
     538    int i;
     539
     540    if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish)
     541        return 0;
     542    for (i = 0; i < s1->ss_narcs; i++) {
     543        if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow ||
     544            s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label)
     545            return 0;
     546    }
     547    return 1;
    548548}
    549549
    … …  
    551551renamestates(int xx_nstates, ss_state *xx_state, int from, int to)
    552552{
    553         int i, j;
    554        
    555         if (Py_DebugFlag)
    556                 printf("Rename state %d to %d.\n", from, to);
    557         for (i = 0; i < xx_nstates; i++) {
    558                 if (xx_state[i].ss_deleted)
    559                         continue;
    560                 for (j = 0; j < xx_state[i].ss_narcs; j++) {
    561                         if (xx_state[i].ss_arc[j].sa_arrow == from)
    562                                 xx_state[i].ss_arc[j].sa_arrow = to;
    563                 }
    564         }
     553    int i, j;
     554
     555    if (Py_DebugFlag)
     556        printf("Rename state %d to %d.\n", from, to);
     557    for (i = 0; i < xx_nstates; i++) {
     558        if (xx_state[i].ss_deleted)
     559            continue;
     560        for (j = 0; j < xx_state[i].ss_narcs; j++) {
     561            if (xx_state[i].ss_arc[j].sa_arrow == from)
     562                xx_state[i].ss_arc[j].sa_arrow = to;
     563        }
     564    }
    565565}
    566566
    … …  
    568568simplify(int xx_nstates, ss_state *xx_state)
    569569{
    570         int changes;
    571         int i, j;
    572        
    573         do {
    574                 changes = 0;
    575                 for (i = 1; i < xx_nstates; i++) {
    576                         if (xx_state[i].ss_deleted)
    577                                 continue;
    578                         for (j = 0; j < i; j++) {
    579                                 if (xx_state[j].ss_deleted)
    580                                         continue;
    581                                 if (samestate(&xx_state[i], &xx_state[j])) {
    582                                         xx_state[i].ss_deleted++;
    583                                         renamestates(xx_nstates, xx_state,
    584                                                      i, j);
    585                                         changes++;
    586                                         break;
    587                                 }
    588                         }
    589                 }
    590         } while (changes);
     570    int changes;
     571    int i, j;
     572
     573    do {
     574        changes = 0;
     575        for (i = 1; i < xx_nstates; i++) {
     576            if (xx_state[i].ss_deleted)
     577                continue;
     578            for (j = 0; j < i; j++) {
     579                if (xx_state[j].ss_deleted)
     580                    continue;
     581                if (samestate(&xx_state[i], &xx_state[j])) {
     582                    xx_state[i].ss_deleted++;
     583                    renamestates(xx_nstates, xx_state,
     584                                 i, j);
     585                    changes++;
     586                    break;
     587                }
     588            }
     589        }
     590    } while (changes);
    591591}
    592592
    … …  
    599599convert(dfa *d, int xx_nstates, ss_state *xx_state)
    600600{
    601         int i, j;
    602         ss_state *yy;
    603         ss_arc *zz;
    604        
    605         for (i = 0; i < xx_nstates; i++) {
    606                 yy = &xx_state[i];
    607                 if (yy->ss_deleted)
    608                         continue;
    609                 yy->ss_rename = addstate(d);
    610         }
    611        
    612         for (i = 0; i < xx_nstates; i++) {
    613                 yy = &xx_state[i];
    614                 if (yy->ss_deleted)
    615                         continue;
    616                 for (j = 0; j < yy->ss_narcs; j++) {
    617                         zz = &yy->ss_arc[j];
    618                         addarc(d, yy->ss_rename,
    619                                 xx_state[zz->sa_arrow].ss_rename,
    620                                 zz->sa_label);
    621                 }
    622                 if (yy->ss_finish)
    623                         addarc(d, yy->ss_rename, yy->ss_rename, 0);
    624         }
    625        
    626         d->d_initial = 0;
     601    int i, j;
     602    ss_state *yy;
     603    ss_arc *zz;
     604
     605    for (i = 0; i < xx_nstates; i++) {
     606        yy = &xx_state[i];
     607        if (yy->ss_deleted)
     608            continue;
     609        yy->ss_rename = addstate(d);
     610    }
     611
     612    for (i = 0; i < xx_nstates; i++) {
     613        yy = &xx_state[i];
     614        if (yy->ss_deleted)
     615            continue;
     616        for (j = 0; j < yy->ss_narcs; j++) {
     617            zz = &yy->ss_arc[j];
     618            addarc(d, yy->ss_rename,
     619                xx_state[zz->sa_arrow].ss_rename,
     620                zz->sa_label);
     621        }
     622        if (yy->ss_finish)
     623            addarc(d, yy->ss_rename, yy->ss_rename, 0);
     624    }
     625
     626    d->d_initial = 0;
    627627}
    628628
    … …  
    633633maketables(nfagrammar *gr)
    634634{
    635         int i;
    636         nfa *nf;
    637         dfa *d;
    638         grammar *g;
    639        
    640         if (gr->gr_nnfas == 0)
    641                 return NULL;
    642         g = newgrammar(gr->gr_nfa[0]->nf_type);
    643                         /* XXX first rule must be start rule */
    644         g->g_ll = gr->gr_ll;
    645        
    646         for (i = 0; i < gr->gr_nnfas; i++) {
    647                 nf = gr->gr_nfa[i];
    648                 if (Py_DebugFlag) {
    649                         printf("Dump of NFA for '%s' ...\n", nf->nf_name);
    650                         dumpnfa(&gr->gr_ll, nf);
    651                         printf("Making DFA for '%s' ...\n", nf->nf_name);
    652                 }
    653                 d = adddfa(g, nf->nf_type, nf->nf_name);
    654                 makedfa(gr, gr->gr_nfa[i], d);
    655         }
    656        
    657         return g;
     635    int i;
     636    nfa *nf;
     637    dfa *d;
     638    grammar *g;
     639
     640    if (gr->gr_nnfas == 0)
     641        return NULL;
     642    g = newgrammar(gr->gr_nfa[0]->nf_type);
     643                    /* XXX first rule must be start rule */
     644    g->g_ll = gr->gr_ll;
     645
     646    for (i = 0; i < gr->gr_nnfas; i++) {
     647        nf = gr->gr_nfa[i];
     648        if (Py_DebugFlag) {
     649            printf("Dump of NFA for '%s' ...\n", nf->nf_name);
     650            dumpnfa(&gr->gr_ll, nf);
     651            printf("Making DFA for '%s' ...\n", nf->nf_name);
     652        }
     653        d = adddfa(g, nf->nf_type, nf->nf_name);
     654        makedfa(gr, gr->gr_nfa[i], d);
     655    }
     656
     657    return g;
    658658}
    659659
    … …  
    661661pgen(node *n)
    662662{
    663         nfagrammar *gr;
    664         grammar *g;
    665        
    666         gr = metacompile(n);
    667         g = maketables(gr);
    668         translatelabels(g);
    669         addfirstsets(g);
    670         PyObject_FREE(gr);
    671         return g;
     663    nfagrammar *gr;
     664    grammar *g;
     665
     666    gr = metacompile(n);
     667    g = maketables(gr);
     668    translatelabels(g);
     669    addfirstsets(g);
     670    PyObject_FREE(gr);
     671    return g;
    672672}
    673673
    … …  
    703703
    704704[Aho&Ullman 77]
    705         Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977
    706         (first edition)
     705    Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977
     706    (first edition)
    707707
    708708*/
Note: See TracChangeset for help on using the changeset viewer.