ELC_parser.c

Go to the documentation of this file.
00001 /******************************************************************************
00002  *                                S Y N T A X
00003  *-----------------------------------------------------------------------------
00004  *   Copyright (C) 1972-2008 INRIA (Institut National de Recherche en
00005  *   Informatique et Automatique)
00006  *-----------------------------------------------------------------------------
00007  *   URL: http://syntax.gforge.inria.fr
00008  *-----------------------------------------------------------------------------
00009  *   The source code of SYNTAX is distributed with two different licenses,
00010  *   depending on the files:
00011  *   - The recursive content of src/ and incl/ and the non-recursive content
00012  *     of SYNTAX's root directory are distributed under the CeCILL-C license
00013  *   - The recursive content of all other repertories is distributed under
00014  *     the CeCILL license
00015  *   All code produced by SYNTAX must be considered as being under the
00016  *   CeCILL-C license. Information about the CeCILL and CeCILL-C licenses
00017  *   can be found at, e.g., http://www.cecill.fr
00018  *****************************************************************************/
00019 /*** THIS FILE IS NOT PART OF THE SYNTAX LIBRARY libsx.a ***/ 
00020 
00021 
00022 
00023 /* ABANDON le 3/5/2002 17:00
00024    Les temps d'analyse (compares au RCG) sont trop importants...
00025 */
00026 
00027 /* Parseur a la Earley qui utilise un automate sous-jacent Left_corner */
00028 /* Fonde' sur une ide'e de Mustapha Tounsi */
00029 /* Il y a 2 versions */
00030 /* Une version de reconnaisseur en temps cubique qui utilise "p_dispatch" et ... */
00031 /* ... une version exponentielle qui utilise "e_dispatch" */
00032 /* Le nombre "node_hd_calls" (compiler avec l'option -DEBUG2), montre une complexite exactement cubique
00033    sur la grammaire S -> S S, S -> a */
00034 
00035 
00036 /*
00037 -DEBUG4 : Qq verifications de coherence
00038 -DEBUG2 : Qq tailles
00039 -DEBUG3 : Les temps d'analyses intermediaires tous les 50 tokens
00040 */
00041 
00042 #include "sxversion.h"
00043 #include "sxunix.h"
00044 #include "sxelc.h"
00045 #include "sxmatrix2vector.h"
00046 
00047 char WHAT_ELC_PARSER[] = "@(#)SYNTAX - $Id: ELC_parser.c 1429 2008-07-03 14:28:41Z rlacroix $" WHAT_DEBUG;
00048 
00049 /* BAG_mngr */
00050 typedef struct {
00051   struct bag_disp_hd {
00052     SXINT       size;
00053     SXBA_ELT    *set;
00054   }     *hd;
00055   SXBA_ELT  *pool_top;
00056   SXINT     hd_size, hd_top, hd_high, pool_size, room;
00057   char  *name;
00058   SXINT     used_size, prev_used_size, total_size; /* #if statistics */
00059   FILE        *file_name;
00060 } bag_header;
00061 
00062 void
00063 bag_alloc (pbag, name, size, file_name)
00064     bag_header  *pbag;
00065     char    *name;
00066     SXINT   size;
00067     FILE        *file_name;
00068 {
00069   SXBA_ELT  *ptr;
00070 
00071   pbag->name = name;
00072   pbag->hd_top = 0;
00073   pbag->hd_high = 0;
00074   pbag->hd_size = 1;
00075   pbag->pool_size = size;
00076   pbag->hd = (struct bag_disp_hd*) sxalloc (pbag->hd_size, sizeof (struct bag_disp_hd));
00077   pbag->pool_top = pbag->hd [0].set = (SXBA_ELT*) sxcalloc (pbag->pool_size + 2, sizeof (SXBA_ELT));
00078   pbag->hd [0].size = pbag->pool_size;
00079   pbag->room = pbag->pool_size;
00080 
00081   if (pbag->file_name = file_name) {
00082     pbag->total_size = pbag->pool_size + 2;
00083     pbag->used_size = pbag->prev_used_size = 0;
00084   }
00085 }
00086 
00087 
00088 
00089 SXBA
00090 bag_get (pbag, size)
00091     bag_header  *pbag;
00092     SXINT       size;
00093 {
00094   SXINT     slice_nb = SXNBLONGS (size) + 1;
00095   SXBA  set;
00096 
00097   if (slice_nb > pbag->room)
00098     {
00099       if (++pbag->hd_top >= pbag->hd_size)
00100     pbag->hd = (struct bag_disp_hd*) sxrealloc (pbag->hd,
00101                             pbag->hd_size *= 2,
00102                             sizeof (struct bag_disp_hd));
00103 
00104       if (pbag->hd_top <= pbag->hd_high) {
00105     pbag->pool_size = pbag->hd [pbag->hd_top].size;
00106 
00107     while (slice_nb > (pbag->room = pbag->pool_size)) {
00108       if (++pbag->hd_top >  pbag->hd_high)
00109         break;
00110 
00111       pbag->pool_size = pbag->hd [pbag->hd_top].size;
00112     }
00113       }
00114 
00115       if (pbag->hd_top > pbag->hd_high) {       
00116     while (slice_nb > (pbag->room = pbag->pool_size))
00117       pbag->pool_size *= 2;
00118 
00119     if (pbag->file_name) {
00120       fprintf (pbag->file_name, "Bag %s: New bag of size %i is created.\n", pbag->name, pbag->pool_size *= 2);
00121       pbag->total_size += pbag->pool_size + 2;
00122     }
00123 
00124     pbag->hd_high = pbag->hd_top;
00125     pbag->hd [pbag->hd_top].set = (SXBA) sxcalloc (pbag->pool_size + 2, sizeof (SXBA_ELT));
00126     pbag->hd [pbag->hd_top].size = pbag->pool_size;
00127       }
00128 
00129       pbag->pool_top = pbag->hd [pbag->hd_top].set;
00130     }
00131 
00132   *(set = pbag->pool_top) = size;
00133   pbag->pool_top += slice_nb;
00134   pbag->room -= slice_nb;
00135 
00136   if (pbag->file_name) {
00137     pbag->used_size += slice_nb;
00138   }
00139 
00140   return set;
00141 }
00142 
00143 
00144 void
00145 bag_reuse (pbag, set)
00146     bag_header  *pbag;
00147     SXBA    set;
00148 {
00149   /* On recupere la place allouee depuis set. */
00150   /* Dangereux, c'est la responsabilite de l'utilisateur */
00151   SXINT slice_nb;
00152 
00153   if (set < pbag->hd [pbag->hd_top].set || set > pbag->pool_top) {
00154     /* set pointe ne pointe plus ds le courant, on recupere tout le courant */
00155     set = pbag->hd [pbag->hd_top].set;
00156   }
00157 
00158   if ((slice_nb = pbag->pool_top - set) > 0) {
00159     pbag->room += slice_nb;
00160 
00161     if (pbag->file_name) {
00162       pbag->used_size -= slice_nb;
00163     }
00164 
00165     /* On nettoie */
00166     do {
00167       *--pbag->pool_top = 0;
00168     } while (pbag->pool_top > set);
00169   }
00170 }
00171     
00172 
00173 void
00174 bag_free (pbag)
00175     bag_header  *pbag;
00176 {
00177   if (pbag->file_name) {
00178     fprintf (pbag->file_name, "Bag %s: used_size = %i bytes, total_size = %i bytes\n",
00179          pbag->name,
00180          (pbag->used_size > pbag->prev_used_size ? pbag->used_size : pbag->prev_used_size) *
00181          sizeof (SXBA_ELT) + (pbag->hd_high + 1) * sizeof (struct bag_disp_hd),
00182          pbag->total_size * sizeof (SXBA_ELT) + pbag->hd_size * sizeof (struct bag_disp_hd));
00183   }
00184 
00185   do {
00186     sxfree (pbag->hd [pbag->hd_high].set);
00187   } while (--pbag->hd_high >= 0);
00188 
00189   sxfree (pbag->hd);
00190 }
00191     
00192 
00193 static void
00194 bag_clear (pbag)
00195     bag_header  *pbag;
00196 {
00197   /* On suppose que les SXBA sont empty. */
00198   pbag->hd_top = 0;
00199   pbag->pool_top = pbag->hd [0].set;
00200   pbag->pool_size = pbag->hd [0].size;
00201   pbag->room = pbag->pool_size;
00202 
00203   if (pbag->file_name) {
00204     if (pbag->prev_used_size < pbag->used_size)
00205       pbag->prev_used_size = pbag->used_size;
00206 
00207     pbag->used_size = 0;
00208   }
00209 }
00210 /* END BAG_mngr */
00211 
00212 #define TOP(t)      (*t)
00213 #define POP(t)      t[TOP(t)--]
00214 #define PUSH(t,x)   (((++TOP(t) >= t[-1]) ? (t=(SXINT*) sxrealloc (t-1, (t[-1] *= 2)+2, sizeof (SXINT))+1) : (0)), t[TOP(t)]=x)
00215 /* Secure PUSH */
00216 #define SPUSH(t,x)  (t[++TOP(t)]=x)
00217 /* before SPUSHes */
00218 #define CHECK(t,n)  (((TOP(t)+n >= t[-1]) ? (t=(SXINT*) sxrealloc (t-1, (t[-1] *= 2)+2, sizeof (SXINT))+1) : (0)))
00219 #define RAZ(t)      *t=0
00220 #define ALLOC(t,s)      t = (SXINT*) sxalloc (s+2, sizeof (SXINT))+1, t [-1] = s;
00221 #define FREE(t)         sxfree (t-1), t = NULL;
00222 #define IS_EMPTY(t)     (TOP(t)==0)
00223 
00224 #if is_sdag
00225 #define SCAN(i,t)   (SXBA_bit_is_set (glbl_source [i], t))
00226 #else
00227 #define SCAN(i,t)   (glbl_source [i] == t)
00228 #endif
00229 
00230 #if is_rfsa 
00231 #define RFSA_CHECKED(r,i)    (prod2lbs == NULL || SXBA_bit_is_set (prod2lbs [prolis [state2item [r]]], i)) 
00232 #else
00233 #define RFSA_CHECKED(r,i)    SXTRUE
00234 #endif
00235 
00236 FILE    *sxstdout, *sxstderr;
00237 FILE    *sxtty;
00238 
00239 #include ELC_tables /* A la compilation, une option -DELC_tables = ... doit activer les bonnes tables produites
00240              par une execution de csynt_lc -elc L */
00241 
00242 static SXINT          max_node_set_size /* Estimation de la taille des ensembles node2node_set pour la tranche j */;
00243 static SXBOOLEAN      membership;
00244 
00245 #if EBUG2
00246 static SXINT  node_hd_calls;
00247 #endif
00248 
00249 #include "XxY.h"
00250 static XxY_header   node_hd;
00251 static SXBA         *node2node_set;
00252 static SXBA         node2node_set_kind;
00253 static bag_header   bag;
00254 static SXINT          *stack1, *stack2, *cur_scan_stack, *scan_stack;
00255 
00256 
00257 #if is_parse_forest
00258 static SXBA         *node2i_set;
00259 #if is_epsilon
00260 static SXBA         *eps_prod2i_set;
00261 #endif /* is_epsilon */
00262 static void
00263 output (prod, i, j) 
00264      SXINT prod, i, j;
00265 {
00266   SXINT clause;
00267 
00268   /* Attention : la bnf ne contient ni les clauses multiples, ni les loops */
00269   /* Donc clause (qui est le representant de prod) peut ne pas se retrouver ds une analyse RCG
00270      car elle a pu ne pas etre validee par des &Lex eventuels associes */
00271   clause = (semact == NULL) ? prod : semact [prod];
00272 
00273   printf ("%i: %s(%i..%i)\n", clause, ntstring [lhs [prod]], i, j);
00274 }
00275 #endif /* is_parse_forest */
00276 
00277 #if is_1LA && is_sdag
00278 static SXBOOLEAN
00279 IS_AND (lhs_bits_array, rhs_bits_array)
00280     SXBA    lhs_bits_array, rhs_bits_array;
00281 {
00282     SXBA    lhs_bits_ptr, rhs_bits_ptr;
00283     SXINT           lhs_slices_number = SXNBLONGS (SXBASIZE (lhs_bits_array));
00284 
00285     lhs_bits_ptr = lhs_bits_array + lhs_slices_number, rhs_bits_ptr = rhs_bits_array + lhs_slices_number;
00286 
00287     while (lhs_slices_number-- > 0)
00288     {
00289     if (*lhs_bits_ptr-- & *rhs_bits_ptr--)
00290         return SXTRUE;
00291     }
00292 
00293     return SXFALSE;
00294 }
00295 #endif /* is_1LA && is_sdag */
00296 
00297 
00298 static void p_dispatch ();
00299 
00300 static void
00301 node_hd_oflw (old_size, new_size)
00302      SXINT old_size, new_size;
00303 {
00304   node2node_set = (SXBA *) sxrealloc (node2node_set, new_size+1, sizeof (SXBA));
00305   node2node_set_kind = sxba_resize (node2node_set_kind, new_size+1);
00306 #if is_parse_forest
00307   node2i_set = sxbm_resize (node2i_set, old_size+1, new_size+1, n+1);
00308 #endif /* is_parse_forest */
00309 }
00310 
00311 #if 0
00312 /* NOUVELLE VERSION EN FIN */
00313 /* On vient de faire un reduce A -> \alpha */
00314 /* p ->Aij r */
00315 /* node_ip  */
00316 static void
00317 A_shift (j, p, r, node_ip)
00318      SXINT j, p, r, node_ip;
00319 {
00320   SXINT  node_jr, node, size;
00321   SXBA node_jr2node_set, node_ip2node_set;
00322         
00323   if (XxY_set (&node_hd, j, r, &node_jr)) {
00324     /* old */
00325     node_jr2node_set = node2node_set [node_jr];
00326 
00327     if (p+1 == r) {
00328       if (node_jr2node_set [0] < (size = node2node_set [node_ip] [0]))
00329     node_jr2node_set [0] = size; /* On change la taille!! */
00330     }
00331     else {
00332       if (node_ip >= node_jr2node_set [0])
00333     node_jr2node_set [0] = node_ip+1; /* On change la taille!! */
00334     }
00335   }
00336   else {
00337     /* new */
00338     node_jr2node_set = node2node_set [node_jr] = bag_get (&bag, max_node_set_size);
00339     node_jr2node_set [0] = node_jr+1; /* On change la taille!! */
00340   }
00341 
00342   if (p+1 == r) {
00343     /* Transition non-terminale ds le kernel */
00344     node_ip2node_set = node2node_set [node_ip];
00345 
00346     node = 0;
00347 
00348     while ((node = sxba_scan (node_ip2node_set, node)) > 0) {
00349       /* La complexite en temps cubique provient d'ici, une re'duction peut provoquer O(n) calculs */
00350 #if EBUG2
00351       node_hd_calls++;
00352 #endif
00353 
00354       if (SXBA_bit_is_reset_set (node_jr2node_set, node)) {
00355     p_dispatch (j, r, node_jr, node);
00356       }
00357     }
00358   }
00359   else {
00360     /* Transition non-terminale non-kernel */
00361 #if EBUG2
00362     node_hd_calls++;
00363 #endif
00364 
00365     /* On ajoute node_ip a` node_jr2node_set */
00366     if (SXBA_bit_is_reset_set (node_jr2node_set, node_ip)) {
00367       p_dispatch (j, r, node_jr, node_ip);
00368     }
00369   }
00370 }
00371 
00372 
00373 /* On vient de faire une transition vers l'etat q a l'index j */
00374 /* l'item kernel de q est de la forme A -> \alpha X . \beta */
00375 /* Le noeud characteristique de A -> . \alpha X \beta est node_ip */
00376 static void
00377 p_dispatch (j, q, node_jq, node_ip)
00378      SXINT j, q, node_jq, node_ip;
00379 {
00380   SXINT item, Y, prod, t, i, p, p1, q1, base, A, r, bot, top, k, node_kr, node_jr; 
00381   SXBOOLEAN new, ntk_trans;
00382   SXBA node_kr2node_set, node_jr2node_set, glbl_source_line;
00383 
00384   item = state2item [q];
00385   Y = lispro [item];
00386   /* \beta = Y \beta'  */
00387     
00388   if (Y < 0) {
00389     /* (unique) transition terminale ds le kernel */
00390     /* Y est un t ... */
00391     if (SCAN (j+1, -Y)) {
00392       if (q == 2)
00393     /* j == n */
00394     membership = SXTRUE;
00395       else {
00396     /* On cree le noeud <j+1, q+1> on lui associe {node_ip} a la 1ere creation de node = <j+1, q+1>, on PUSH node_ip */
00397     k = j+1;
00398     r = q+1;
00399 #if EBUG2
00400     node_hd_calls++;
00401 #endif
00402 
00403     if (XxY_set (&node_hd, k, r, &node_kr)) {
00404       /* old */
00405       node_kr2node_set = node2node_set [node_kr];
00406 
00407       if (node_ip >= node_kr2node_set [0])
00408         node_kr2node_set [0] = node_ip+1; /* On change la taille!! */
00409     }
00410     else {
00411       /* new */
00412       node_kr2node_set = node2node_set [node_kr] = bag_get (&bag, max_node_set_size);
00413       node_kr2node_set [0] = ((node_ip > node_kr) ? node_ip : node_kr)+1; /* On change la taille!! */
00414       SPUSH (scan_stack, node_kr);
00415     }
00416 
00417     SXBA_1_bit (node_kr2node_set, node_ip);
00418       }
00419     }
00420   }
00421   else {
00422     if (Y == 0) {
00423       /* Le kernel de q est un reduce (unique) */
00424       prod = prolis [item];
00425       /* item est de la forme prod: A -> \alpha . */
00426       /* Le look-ahead est ai+1 */
00427 
00428 #if is_1LA
00429 #if is_sdag
00430       if (!IS_AND (glbl_source [j+1], prod2la_set [prod]))
00431     /* Le test du look-ahead a echoue */
00432     return;
00433 #else /* !is_sdag */
00434       t = source [j+1];
00435 
00436       if (!SXBA_bit_is_set (prod2la_set [prod], t))
00437     /* Le test du look-ahead a echoue */
00438     return;
00439 #endif /* !is_sdag */
00440 #endif /* is_1LA */
00441 
00442       i = XxY_X (node_hd, node_ip); /* On a Aij */
00443 
00444 #if is_parse_forest
00445       if (SXBA_bit_is_reset_set (node2i_set [node_jq], i))
00446     output (prod, i, j);
00447 #endif /* is_parse_forest */
00448 
00449       p =  XxY_Y (node_hd, node_ip);
00450 
00451       A = lhs [prod];
00452 
00453       /* On traite d'abord la transition kernel si elle existe */
00454       if ((base = vector_base (knt_shift, p)) != 0 &&
00455       (r = knt_shift_vector_get (p, A, base)) != knt_shift_ERROR) {
00456 #if EBUG4
00457     if (r > max_state)
00458       sxtrap (ME, "p_dispatch");
00459 #endif
00460     /* On ne guide pas (par RFSA_CHECKED (r, i)) la transition kernel
00461        La selection de la prod courante a deja ete effectuee */
00462     A_shift (j, p, r, node_ip);
00463       }
00464 
00465       /* ... puis les transitions non-kernel */
00466       if ((p1 = state2ntstate ? state2ntstate [p] : p) > 0 /* On prend le representant pour les nknt-transitions */
00467       && (base = vector_base (nknt_shift, p1)) != 0
00468       && (r = nknt_shift_vector_get (p1, A, base)) != nknt_shift_ERROR) {
00469     if (r <= max_state) {
00470       /* transition nk deterministe p -> r sur A */
00471       if (RFSA_CHECKED (r, i))
00472         /* Utilisation du guide rfsa */
00473         /* Transition non-terminale non-kernel */
00474         /* validee par l'analyse rfsa */
00475         A_shift (j, p, r, node_ip);
00476     }
00477     else {
00478       r -= max_state;
00479       bot = trans_disp [r];
00480       top = trans_disp [r+1];
00481 
00482       do {
00483         r = trans_list [bot];
00484         /* transition nk non deterministe p -> r sur A */
00485         if (RFSA_CHECKED (r, i))
00486           A_shift (j, p, r, node_ip);
00487       } while (++bot < top);
00488     }
00489       }
00490     }
00491     else {
00492       /* Y est un nt */
00493       /* q est de la forme A -> \alpha X . Y \beta' et Y est un nt */
00494       /* On traite les transitions terminales non kernel */
00495       k = j+1;
00496 
00497       if ((q1 = state2tstate ? state2tstate [q] : q) > 0 /* On prend le representant pour les t-transitions */
00498       && (base = vector_base (t_shift, q1)) != 0) {
00499 #if is_sdag
00500     t = -1;
00501     glbl_source_line = glbl_source [k];
00502 
00503     while ((t = sxba_scan (glbl_source_line, t)) >= 0) {
00504 #else /* !is_sdag */
00505       t = glbl_source [k];
00506 #endif /* !is_sdag */
00507 
00508       if ((r = t_shift_vector_get (q1, t, base)) != t_shift_ERROR) {
00509         /* L'etat q a des transitions terminales q ->aj+1 r */
00510         if (r <= max_state) {
00511           /* transition deterministe */
00512           if (RFSA_CHECKED (r, k)) {
00513         /* Utilisation eventuelle du guide rfsa */
00514         /* Transition terminale non-kernel validee par l'analyse rfsa :
00515            on est au debute une bonne clause au bon indice */
00516 #if EBUG2
00517         node_hd_calls++;
00518 #endif
00519 
00520         if (XxY_set (&node_hd, k, r, &node_kr)) {
00521           /* old */
00522           node_kr2node_set = node2node_set [node_kr];
00523 
00524           if (node_jq >= node_kr2node_set [0])
00525             node_kr2node_set [0] = node_jq+1; /* On change la taille!! */
00526         }
00527         else {
00528           /* new */
00529           node_kr2node_set = node2node_set [node_kr] = bag_get (&bag, max_node_set_size);
00530           node_kr2node_set [0] = ((node_jq > node_kr) ? node_jq : node_kr)+1; /* On change la taille!! */
00531           SPUSH (scan_stack, node_kr);
00532         }
00533 
00534         SXBA_1_bit (node_kr2node_set, node_jq); 
00535           } 
00536         }
00537         else {
00538           /* transition non deterministe */
00539           r -= max_state;
00540           bot = trans_disp [r];
00541           top = trans_disp [r+1];
00542 
00543           do {
00544         r = trans_list [bot];
00545         if (RFSA_CHECKED (r, k)) {
00546           /* Utilisation eventuelle du guide rfsa */
00547           /* Transition terminale non-kernel validee par l'analyse rfsa */
00548       
00549 #if EBUG2
00550           node_hd_calls++;
00551 #endif
00552 
00553           if (XxY_set (&node_hd, k, r, &node_kr)) {
00554             /* old */
00555             node_kr2node_set = node2node_set [node_kr];
00556 
00557             if (node_jq >= node_kr2node_set [0])
00558               node_kr2node_set [0] = node_jq+1; /* On change la taille!! */
00559           }
00560           else {
00561             /* new */
00562             node_kr2node_set = node2node_set [node_kr] = bag_get (&bag, max_node_set_size);
00563             node_kr2node_set [0] = ((node_jq > node_kr) ? node_jq : node_kr)+1; /* On change la taille!! */
00564             SPUSH (scan_stack, node_kr);
00565           }
00566 
00567           SXBA_1_bit (node_kr2node_set, node_jq); 
00568         }
00569           } while (++bot < top);
00570         }
00571       }
00572 #if is_sdag
00573     }
00574 #endif /* is_sdag */
00575       }
00576 
00577 #if is_epsilon
00578       /* On traite les reduce non kernel i.e., les epsilon_reduce
00579      prod: B -> \beta . avec \beta =>* \epsilon */
00580       /* On sort "prod: Bii", la transition sur B est traitee statiquement, sauf si B==Y
00581          cad une des reductions vides que l'on vient de faire a son lhs nt qui est la transition kernel */
00582       ntk_trans = SXFALSE;
00583       bot = eps_red_disp [q];
00584       top = eps_red_disp [q+1];
00585 
00586       if (bot < top) {
00587     do {
00588       prod = eps_red_list [bot];
00589 #if is_1LA
00590 #if is_sdag
00591       if (IS_AND (glbl_source [j+1], prod2la_set [prod]))
00592 #else /* !is_sdag */
00593         t = source [j+1];
00594 
00595       if (SXBA_bit_is_set (prod2la_set [prod], t))
00596 #endif /* !is_sdag */
00597         /* Le test du look-ahead a marche' */
00598 #endif /* is_1LA */
00599         {
00600 #if is_parse_forest
00601           if (SXBA_bit_is_reset_set (eps_prod2i_set [prod], j))
00602         output (prod, j, j);
00603 #endif /* is_parse_forest */
00604           if (lhs [prod] == Y) {
00605         ntk_trans = SXTRUE;
00606           }
00607         }
00608     } while (++bot < top);
00609       }
00610 
00611       if (ntk_trans) {
00612     /* Attention, on ne peut pas appeler
00613        A_shift (j, q, q+1, node_ip);
00614        pour incompatibilite transition kernel/node_ip (ici node_ip est correct alors que A_shift attendrait
00615        un node_jq.
00616        On simule donc ici directement la transition sur le Y vide */
00617     r = q+1; /* Transition sur Y ds le kernel */
00618 
00619     if (XxY_set (&node_hd, j, r, &node_jr)) {
00620       /* old */
00621       node_jr2node_set = node2node_set [node_jr];
00622 
00623       if (node_ip >= node_jr2node_set [0])
00624         node_jr2node_set [0] = node_ip+1; /* On change la taille!! */
00625     }
00626     else {
00627       /* new */
00628       node_jr2node_set = node2node_set [node_jr] = bag_get (&bag, max_node_set_size);
00629       node_jr2node_set [0] = node_jr+1; /* On change la taille!! */
00630     }
00631 
00632 #if EBUG2
00633     node_hd_calls++;
00634 #endif
00635 
00636     /* On ajoute node_ip a` node_jr2node_set */
00637     if (SXBA_bit_is_reset_set (node_jr2node_set, node_ip)) {
00638       p_dispatch (j, r, node_jr, node_ip);
00639     }
00640       }
00641 #endif /* is_epsilon */
00642 
00643     }
00644   }
00645 }
00646 
00647 
00648 
00649 
00650 SXBOOLEAN
00651 sxelc_parse_it ()
00652 {
00653   SXINT j, q, node_00, node_01, node_jq, node_ip, *stack;
00654   SXBA node_ip_set;
00655 #if EBUG3
00656   char str [12];
00657 #endif /* EBUG3 */
00658 
00659   XxY_alloc (&node_hd, "node_hd", n*n+1, 1, 0, 0, node_hd_oflw, statistics);
00660   bag_alloc (&bag, "bag", XxY_size (node_hd)+1, statistics);
00661   node2node_set = (SXBA *) sxalloc (XxY_size (node_hd)+1, sizeof (SXBA));
00662 
00663 #if is_parse_forest
00664   node2i_set = sxbm_calloc (XxY_size (node_hd)+1, n+1);
00665 #if is_epsilon
00666   eps_prod2i_set = sxbm_calloc (nbpro+1, n+1);;
00667 #endif /* is_epsilon */
00668 
00669 #endif /* is_parse_forest */
00670 
00671   ALLOC (stack1, max_state);
00672   ALLOC (stack2, max_state);
00673 
00674   cur_scan_stack = stack1;
00675   scan_stack = stack2;
00676 
00677 #if EBUG2
00678   node_hd_calls = 2;
00679 #endif
00680   XxY_set (&node_hd, 0, 0, &node_00);
00681   XxY_set (&node_hd, 0, 1, &node_01);
00682   node2node_set [node_01] = bag_get (&bag, node_01+1);
00683   SXBA_1_bit (node2node_set [node_01], node_00);
00684 
00685   /* On simule une transition depuis l'etat 0 sur eof vers l'etat (initial) 1 */
00686   PUSH (scan_stack, node_01);
00687 
00688   for (j = 0; j <= n; j++) {
00689     stack = cur_scan_stack;
00690     cur_scan_stack = scan_stack;
00691     scan_stack = stack;
00692 
00693     if (IS_EMPTY (cur_scan_stack))
00694       break;
00695 
00696 #if EBUG3
00697     /* Pour mesurer la complexite' en temps */
00698     if (j % 50 == 0) {
00699       sprintf (str, "%i", j);
00700       sxtime (TIME_FINAL, str);
00701     }
00702 #endif /* EBUG3 */
00703 
00704     /* Estimation (genereuse) de la taille des ensembles node2node_set pour la tranche j */
00705     /* On pourrait, pour la tranche j-1 "compacter les node2node_set */
00706     max_node_set_size = XxY_top (node_hd) + max_state + 1;
00707 
00708     do {
00709       node_jq = POP (cur_scan_stack);
00710       q = XxY_Y (node_hd, node_jq);
00711       node_ip_set = node2node_set [node_jq];
00712       
00713       node_ip = 0;
00714 
00715       while ((node_ip = sxba_scan (node_ip_set, node_ip)) > 0) {
00716     p_dispatch (j, q, node_jq, node_ip);
00717       }
00718     } while (!IS_EMPTY (cur_scan_stack));
00719   }
00720 
00721 #if EBUG2
00722   printf ("Polynomial run (%s): node_calls = %i, nodes = %i\n", membership ? "SXTRUE" : "SXFALSE", node_hd_calls, XxY_top (node_hd));
00723 #endif
00724 
00725   XxY_free (&node_hd);
00726   bag_free (&bag);
00727   sxfree (node2node_set), node2node_set = NULL;
00728   FREE (stack1);
00729   FREE (stack2);
00730 
00731 #if is_parse_forest
00732   sxbm_free (node2i_set), node2i_set = NULL;
00733 #if is_epsilon
00734   sxbm_free (eps_prod2i_set), eps_prod2i_set = NULL;
00735 #endif /* is_epsilon */
00736 #endif
00737 
00738   return membership;
00739 }
00740 #endif /* 0 */
00741 
00742 
00743 
00744 #if 0
00745 /* Ici, analyse en temps exponentiel par un parseur backtrack */
00746 /* Exponential run data */
00747 #include "XxYxZ.h"
00748 static XxYxZ_header Prodij_hd;
00749 
00750 
00751 
00752 static SXINT        null_assoc [6];
00753 static XxYxZ_header chart_hd;
00754 
00755 #if EBUG2
00756 static SXINT    memo_hit, *i2chart_nb;
00757 #endif
00758 
00759 
00760 /* dispatch a une complexite en temps (et place ds chart_hd) exponentielle */
00761 /* L'item kernel de p est de la forme A -> \alpha . \beta */
00762 /* Le look-ahead est ai+1 */
00763 static void
00764 e_dispatch (i, p, chart)
00765      SXINT i, p, chart;
00766 {
00767   SXINT X, item, cur_chart, base, q, bot, top, prod, t, A, j, prodji, r, bot_chart;
00768   SXBA glbl_source_line;
00769 
00770   /* p est de la forme A -> \alpha . \beta */
00771   item = state2item [p];
00772   X = lispro [item];
00773   /* item est de la forme A -> \alpha . X \beta'  */
00774     
00775   if (X < 0) {
00776     /* (unique) transition terminale ds le kernel */
00777     /* X est un t ... */
00778     if (SCAN (i+1, -X)) {
00779       /* ... et c'est le t du source */
00780       if (X == -tmax)
00781     /* X == eof et p est le seul etat depuis lequel il existe une transition sur eof */
00782     membership = SXTRUE;
00783       else
00784     e_dispatch (i+1, p+1, chart);
00785     }
00786   }
00787   else {
00788     if (XxYxZ_set (&chart_hd, i, p, chart, &cur_chart)) {
00789       /* existe deja */
00790 #if EBUG2
00791       memo_hit++;
00792 #endif
00793       return;
00794     }
00795 
00796 #if EBUG2
00797     i2chart_nb [i]++;
00798 #endif
00799 
00800     if (X > 0) {
00801       /* p est de la forme A -> \alpha . X \beta' et X est un nt */
00802       /* On traite les transitions terminales non kernel */
00803       if ((base = vector_base (t_shift, p)) != 0) { 
00804 #if is_sdag
00805     t = -1;
00806     glbl_source_line = glbl_source [k];
00807 
00808     while ((t = sxba_scan (glbl_source_line, t)) >= 0) {
00809 #else /* !is_sdag */
00810       t = glbl_source [i+1];
00811 #endif /* !is_sdag */
00812 
00813       if ((q = t_shift_vector_get (p, t, base)) != t_shift_ERROR) {
00814         /* L'etat p a des transitions terminales p ->ai+1 q */
00815         if (q <= max_state)
00816           /* transition deterministe */
00817           e_dispatch (i+1, q, cur_chart);
00818         else {
00819           /* transition non deterministe */
00820           q -= max_state;
00821           bot = trans_disp [q];
00822           top = trans_disp [q+1];
00823 
00824           do {
00825         e_dispatch (i+1, trans_list [bot], cur_chart);
00826           } while (++bot < top);
00827         }
00828       }
00829 #if is_sdag
00830     }
00831 #endif /* is_sdag */
00832       }
00833 
00834 #if is_parse_forest && is_epsilon
00835       /* On traite les reduce non kernel i.e., les epsilon_reduce
00836      prod: B -> \beta . avec \beta =>* \epsilon */
00837       /* On se contente de sortir "prod: Bii", la transition sur B est traitee statiquement */
00838       bot = eps_red_disp [p];
00839       top = eps_red_disp [p+1];
00840 
00841       if (bot < top) {
00842     do {
00843       prod = eps_red_list [bot];
00844 #if is_1LA
00845 #if is_sdag
00846       if (IS_AND (glbl_source [i+1], prod2la_set [prod]))
00847 #else /* !is_sdag */
00848         t = source [i+1];
00849 
00850       if (SXBA_bit_is_set (prod2la_set [prod], t))
00851 #endif /* !is_sdag */
00852         /* Le test du look-ahead a marche' */
00853 #endif /* is_1LA */
00854         output (prod, i, i);
00855     } while (++bot < top);
00856       }
00857 #endif /* is_parse_forest && is_epsilon */
00858     }
00859     else {
00860       /* Le kernel est un reduce (unique) */
00861       /* p est de la forme A -> \alpha .   (\beta == \epsilon) */
00862       /* Le look-ahead est ai+1 */
00863       prod = prolis [item];
00864 
00865 #if is_1LA
00866 #if is_sdag
00867       if (!IS_AND (glbl_source [i+1], prod2la_set [prod]))
00868     /* Le test du look-ahead a echoue */
00869     return;
00870 #else /* !is_sdag */
00871       t = source [i+1];
00872 
00873       if (!SXBA_bit_is_set (prod2la_set [prod], t))
00874     /* Le test du look-ahead a echoue */
00875     return;
00876 #endif /* !is_sdag */
00877 #endif /* is_1LA */
00878 
00879 #if is_parse_forest
00880       j = XxYxZ_X (chart_hd, chart); /* On a Aji */
00881 
00882       if (!XxYxZ_set (&Prodij_hd, prod, j, i, &prodji))
00883     output (prod, j, i);
00884 #endif /* is_parse_forest */
00885 
00886       q = XxYxZ_Y (chart_hd, chart);
00887 
00888       base = vector_base (nknt_shift, q);
00889 
00890 #if EBUG4
00891       if (base == 0)
00892     sxtrap (ME, "e_dispatch");
00893 #endif
00894 
00895       r = nknt_shift_vector_get (q, lhs [prod], base); /* q ->A r et q ->\alpha p */
00896 
00897 #if EBUG4
00898       if (r == nknt_shift_ERROR)
00899     sxtrap (ME, "e_dispatch");
00900 #endif
00901 
00902       bot_chart = XxYxZ_Z (chart_hd, chart);
00903 
00904       if (r <= max_state)
00905     /* transition deterministe p -> r sur A */
00906     /* Si q+1==r <=> transition kernel */
00907     e_dispatch (i, r, (q+1 == r) ? bot_chart : chart);
00908       else {
00909     r -= max_state;
00910     bot = trans_disp [r];
00911     top = trans_disp [r+1];
00912 
00913     do {
00914       r = trans_list [bot];
00915       /* transition non deterministe p -> r sur A */
00916       /* Si q+1==r <=> transition kernel */
00917       e_dispatch (i, r, (q+1 == r) ? bot_chart : chart);
00918     } while (++bot < top);
00919       }
00920     }
00921   }
00922 }
00923 
00924 SXBOOLEAN
00925 sxelc_parse_it ()
00926 {
00927   SXINT j, q, node_00, node_01, node_jq, node_ip, *stack;
00928   SXBA node_ip_set;
00929 
00930   /* Exponential run */
00931 #if is_parse_forest
00932   XxYxZ_alloc (&Prodij_hd, "Prodij_hd",  n*n*ntmax+1, 1, null_assoc, NULL, statistics);
00933 #endif /* is_parse_forest */
00934 
00935   XxYxZ_alloc (&chart_hd, "chart_hd", (1<<(n+1))+1, 1, null_assoc, NULL, statistics);
00936 
00937 #if EBUG2
00938   i2chart_nb = (SXINT*) sxcalloc (n+2, sizeof (SXINT));
00939 #endif
00940 
00941   e_dispatch (0, 1, 1); /* finesse : chart autoreference */
00942 
00943 #if EBUG2
00944   printf ("Exponential run (%s): charts = %i, top_charts = %i, memo_hit = %i\n",
00945       membership ? "SXTRUE" : "SXFALSE", XxYxZ_top (chart_hd), i2chart_nb [n], memo_hit);
00946 
00947   sxfree (i2chart_nb), i2chart_nb = NULL;
00948 #endif
00949 
00950   XxYxZ_free (&chart_hd);
00951 
00952 #if is_parse_forest
00953   XxYxZ_free (&Prodij_hd);
00954 #endif
00955 
00956   return membership;
00957 }
00958 #endif /* 0 */
00959 
00960 static void
00961 SXBA_OR (lhs_bits_array, rhs_bits_array)
00962     SXBA    lhs_bits_array, rhs_bits_array;
00963 /*
00964  * If the size of rhs_bits_array is > lhs_bits_array, the size of lhs_bits_array is modified
00965  * (we assume that there is enough room in lhs_bits_array)
00966  * It modified its first argument.
00967  */
00968 {
00969   SXBA  lhs_bits_ptr, rhs_bits_ptr;
00970   SXINT         rhs_size = SXBASIZE (rhs_bits_array);
00971   SXINT         slices_number;
00972 
00973   if (rhs_size > SXBASIZE (lhs_bits_array)) {
00974     SXBASIZE (lhs_bits_array) = rhs_size;
00975   }
00976 
00977   slices_number = SXNBLONGS (rhs_size);
00978     
00979 
00980   lhs_bits_ptr = lhs_bits_array + slices_number, rhs_bits_ptr = rhs_bits_array + slices_number;
00981 
00982   while (slices_number-- > 0) {
00983     *lhs_bits_ptr-- |= *rhs_bits_ptr--;
00984   }
00985 }
00986 
00987 static SXBOOLEAN
00988 SXBA_OR_MINUS (lhs_bits_array, lhs2_bits_array, rhs_bits_array)
00989     SXBA    lhs_bits_array, lhs2_bits_array, rhs_bits_array;
00990 /*
00991  * SXBASIZE (lhs2_bits_array) == SXBASIZE (rhs_bits_array)
00992  * If the size of rhs_bits_array is > lhs_bits_array, the size of lhs_bits_array is modified
00993  * (we assume that there is enough room in lhs_bits_array)
00994  * It modified its first and second argument.
00995  * lhs2_bits_array = rhs_bits_array - lhs_bits_array
00996  * lhs_bits_array = lhs_bits_array | rhs_bits_array
00997  */
00998 {
00999   SXBA  lhs_bits_ptr, lhs2_bits_ptr, rhs_bits_ptr;
01000   SXINT         rhs_size = SXBASIZE (rhs_bits_array);
01001   SXINT         slices_number;
01002   SXBOOLEAN ret_val = SXFALSE;
01003 
01004   if (rhs_size > SXBASIZE (lhs_bits_array)) {
01005     SXBASIZE (lhs_bits_array) = rhs_size;
01006   }
01007 
01008   slices_number = SXNBLONGS (rhs_size);
01009 
01010   lhs_bits_ptr = lhs_bits_array + slices_number;
01011   lhs2_bits_ptr = lhs2_bits_array + slices_number;
01012   rhs_bits_ptr = rhs_bits_array + slices_number;
01013 
01014   while (slices_number-- > 0) {
01015     if (*lhs2_bits_ptr = *rhs_bits_ptr-- & ~*lhs_bits_ptr) {
01016       ret_val = SXTRUE;
01017       *lhs_bits_ptr-- |= *lhs2_bits_ptr--;
01018     }
01019     else {
01020       lhs_bits_ptr--;
01021     }
01022   }
01023 
01024   return ret_val;
01025 }
01026 
01027 /* On vient de faire un reduce A -> \alpha */
01028 /* p ->Aij r */
01029 /* node_ip  */
01030 static void
01031 A_shift (j, p, r, node_ip)
01032      SXINT j, p, r, node_ip;
01033 {
01034   SXINT  node_jr, node, size;
01035   SXBA node_jr2node_set, node_ip2node_set, wset;
01036         
01037 #if EBUG2
01038   node_hd_calls++;
01039 #endif
01040 
01041   if (XxY_set (&node_hd, j, r, &node_jr)) {
01042     /* old */
01043     node_jr2node_set = node2node_set [node_jr];
01044 
01045     if (p+1 == r) {
01046       /* Transition non-terminale ds le kernel */
01047       if (SXBA_bit_is_set_reset (node2node_set_kind, node_jr)) {
01048     /* allocation et recopie */
01049     wset = node2node_set [node_jr];
01050     node_jr2node_set = node2node_set [node_jr] = bag_get (&bag, max_node_set_size);
01051     node_jr2node_set [0] = wset [0];
01052     sxba_copy (node_jr2node_set, wset);
01053       }
01054 
01055       node_ip2node_set = node2node_set [node_ip];
01056       wset = bag_get (&bag, node_ip2node_set [0]);
01057       
01058       if (SXBA_OR_MINUS (node2node_set [node_jr], wset, node_ip2node_set))
01059     /* wset = node_ip2node_set - node2node_set [node_jr]; cad les les nouveaux nodes
01060        node2node_set [node_jr] = node2node_set [node_jr] | node_ip2node_set;
01061     */
01062     p_dispatch (j, r, node_jr, 0, wset);
01063     }
01064     else {
01065       /* Transition non-terminale non-kernel */
01066       node_jr2node_set = node2node_set [node_jr];
01067 
01068       if (node_ip >= node_jr2node_set [0])
01069     node_jr2node_set [0] = node_ip+1; /* On change la taille!! */
01070 
01071       if (SXBA_bit_is_reset_set (node_jr2node_set, node_ip)) {
01072     p_dispatch (j, r, node_jr, node_ip, NULL);
01073       }
01074     }
01075   }
01076   else {
01077     /* new */
01078     if (p+1 == r) {
01079       /* Transition non-terminale ds le kernel */
01080       /* A la 1ere creation, on met node2node_set [node_ip] */
01081       node_jr2node_set = node2node_set [node_jr] = node2node_set [node_ip];
01082       SXBA_1_bit (node2node_set_kind, node_jr);
01083       p_dispatch (j, r, node_jr, 0, node_jr2node_set);
01084     }
01085     else {
01086       /* Transition non-terminale non-kernel */
01087       node_jr2node_set = node2node_set [node_jr] = bag_get (&bag, max_node_set_size);
01088       node_jr2node_set [0] = node_jr+1; /* On change la taille!! */
01089 
01090       /* On initialise node_jr2node_set avec node_ip */
01091       SXBA_1_bit (node_jr2node_set, node_ip);
01092       p_dispatch (j, r, node_jr, node_ip, NULL);
01093     }
01094   }
01095 }
01096 
01097 
01098 /* On vient de faire une transition vers l'etat Q a l'index j */
01099 /* Q peut etre le resultat d'une transition non_deterministe */
01100 /* l'item kernel de q est de la forme A -> \alpha X . \beta */
01101 /* Le noeud characteristique de A -> . \alpha X \beta est node_ip */
01102 static void
01103 p_dispatch (j, Q, node_jQ, node_ip, node_ip_set)
01104      SXINT j, Q, node_jQ, node_ip;
01105      SXBA node_ip_set;
01106 {
01107   SXINT item, Y, prod, t, i, p, p1, q, q1, base, A, r, bot, top, k, node_kr, node_jr; 
01108   SXBOOLEAN new, ntk_trans;
01109   SXBA node_kr2node_set, node_jr2node_set, glbl_source_line, wset;
01110 
01111   if (Q <= max_state) {
01112     q = Q;
01113     bot = top = 0;
01114   }
01115   else {
01116     Q -= max_state;
01117     bot = trans_disp [Q];
01118     top = trans_disp [Q+1];
01119     q = trans_list [bot];
01120   }
01121 
01122   do {
01123     item = state2item [q];
01124     Y = lispro [item];
01125     /* \beta = Y \beta'  */
01126     
01127     if (Y < 0) {
01128       /* (unique) transition terminale ds le kernel */
01129       /* Y est un t ... */
01130       if (SCAN (j+1, -Y)) {
01131     if (q == 2)
01132       /* j == n */
01133       membership = SXTRUE;
01134     else {
01135       /* On cree le noeud <j+1, q+1> on lui associe {node_ip} a la 1ere creation de node = <j+1, q+1>, on PUSH node_ip */
01136       k = j+1;
01137       r = q+1;
01138 #if EBUG2
01139       node_hd_calls++;
01140 #endif
01141 
01142       if (XxY_set (&node_hd, k, r, &node_kr)) {
01143         /* old */
01144         node_kr2node_set = node2node_set [node_kr];
01145 
01146         if (SXBA_bit_is_set_reset (node2node_set_kind, node_kr)) {
01147           /* allocation et recopie */
01148           wset = node_kr2node_set;
01149           node_kr2node_set = node2node_set [node_kr] = bag_get (&bag, max_node_set_size);
01150           node_kr2node_set [0] = wset [0];
01151           sxba_copy (node_kr2node_set, wset);
01152         }
01153 
01154         /* union avec node_ip_set */
01155         if (node_ip_set)
01156           SXBA_OR (node2node_set [node_kr], node_ip_set);
01157         else
01158           SXBA_1_bit (node2node_set [node_kr], node_ip);
01159       }
01160       else {
01161         /* new */
01162         /* A la 1ere creation, on met node_ip_set */
01163         if (node_ip_set) {
01164           node2node_set [node_kr] = node_ip_set;
01165           SXBA_1_bit (node2node_set_kind, node_kr);
01166         }
01167         else {
01168           node_kr2node_set = node2node_set [node_kr] = bag_get (&bag, max_node_set_size);
01169           node_kr2node_set [0] = node_kr+1;
01170           SXBA_1_bit (node_kr2node_set, node_ip);
01171         }
01172 
01173         SPUSH (scan_stack, node_kr); /* node_kr > 0 => pas de RFSA_CHECKED */
01174       }
01175     }
01176       }
01177     }
01178     else {
01179       if (Y == 0) {
01180     /* Le kernel de q est un reduce (unique) */
01181     prod = prolis [item];
01182     /* item est de la forme prod: A -> \alpha . */
01183     /* Le look-ahead est ai+1 */
01184 
01185 #if is_1LA
01186 #if is_sdag
01187     if (!IS_AND (glbl_source [j+1], prod2la_set [prod]))
01188       /* Le test du look-ahead a echoue */
01189       return;
01190 #else /* !is_sdag */
01191     t = source [j+1];
01192 
01193     if (!SXBA_bit_is_set (prod2la_set [prod], t))
01194       /* Le test du look-ahead a echoue */
01195       return;
01196 #endif /* !is_sdag */
01197 #endif /* is_1LA */
01198 
01199     if (node_ip_set)
01200       node_ip = sxba_scan (node_ip_set, 0);
01201 
01202     do {
01203 #if is_parse_forest
01204       i = XxY_X (node_hd, node_ip); /* On a Aij */
01205 
01206       if (SXBA_bit_is_reset_set (node2i_set [node_jQ], i))
01207         output (prod, i, j);
01208 #endif /* is_parse_forest */
01209 
01210       p =  XxY_Y (node_hd, node_ip);
01211       A = lhs [prod];
01212 
01213       /* On traite d'abord la transition kernel si elle existe */
01214       if ((base = vector_base (knt_shift, p)) != 0 &&
01215           (r = knt_shift_vector_get (p, A, base)) != knt_shift_ERROR) {
01216 #if EBUG4
01217         if (r > max_state)
01218           sxtrap (ME, "p_dispatch");
01219 #endif
01220         /* On ne guide pas (par RFSA_CHECKED (r, i)) la transition kernel
01221            La selection de la prod courante a deja ete effectuee */
01222         A_shift (j, p, r, node_ip);
01223       }
01224 
01225       /* ... puis les transitions non-kernel */
01226       if ((p1 = state2ntstate ? state2ntstate [p] : p) > 0 /* On prend le representant pour les nknt-transitions */
01227           && (base = vector_base (nknt_shift, p1)) != 0
01228           && (r = nknt_shift_vector_get (p1, A, base)) != nknt_shift_ERROR) {
01229         if (r <= max_state) {
01230           /* transition nk deterministe p -> r sur A */
01231           if (RFSA_CHECKED (r, i))
01232         /* Utilisation du guide rfsa */
01233         /* Transition non-terminale non-kernel */
01234         /* validee par l'analyse rfsa */
01235         A_shift (j, p, r, node_ip);
01236         }
01237         else {
01238           r -= max_state;
01239           bot = trans_disp [r];
01240           top = trans_disp [r+1];
01241 
01242           do {
01243         r = trans_list [bot];
01244         /* transition nk non deterministe p -> r sur A */
01245         if (RFSA_CHECKED (r, i))
01246           A_shift (j, p, r, node_ip);
01247           } while (++bot < top);
01248         }
01249       }
01250     } while (node_ip_set ? ((node_ip = sxba_scan (node_ip_set, node_ip)) > 0) : SXFALSE);
01251       }
01252       else {
01253     /* Y est un nt */
01254     /* q est de la forme A -> \alpha X . Y \beta' et Y est un nt */
01255     /* On traite les transitions terminales non kernel */
01256     k = j+1;
01257 
01258     if ((q1 = state2tstate ? state2tstate [q] : q) > 0 /* On prend le representant pour les t-transitions */
01259         && (base = vector_base (t_shift, q1)) != 0) {
01260 #if is_sdag
01261       t = -1;
01262       glbl_source_line = glbl_source [k];
01263 
01264       while ((t = sxba_scan (glbl_source_line, t)) >= 0)
01265 #else /* !is_sdag */
01266         t = glbl_source [k];
01267 #endif /* !is_sdag */
01268       {
01269 
01270         if ((r = t_shift_vector_get (q1, t, base)) != t_shift_ERROR) {
01271           /* L'etat q a des transitions terminales q ->aj+1 r */
01272 #if EBUG2
01273           node_hd_calls++;
01274 #endif
01275 
01276           if (XxY_set (&node_hd, k, r, &node_kr)) {
01277         /* old */
01278         node_kr2node_set = node2node_set [node_kr];
01279 
01280         if (node_jQ >= node_kr2node_set [0])
01281           node_kr2node_set [0] = node_jQ+1;
01282 
01283         SXBA_1_bit (node_kr2node_set, node_jQ);
01284           }
01285           else {
01286         /* new */
01287         node_kr2node_set = node2node_set [node_kr] = bag_get (&bag, max_node_set_size);
01288         node_kr2node_set [0] = node_kr+1;
01289         SXBA_1_bit (node_kr2node_set, node_jQ);
01290         SPUSH (scan_stack, -node_kr); /* node_kr < 0 => il faudra faire RFSA_CHECKED */
01291           }
01292         }
01293       }
01294     }
01295 
01296 #if is_epsilon
01297     /* On traite les reduce non kernel i.e., les epsilon_reduce
01298        prod: B -> \beta . avec \beta =>* \epsilon */
01299     /* On sort "prod: Bii", la transition sur B est traitee statiquement, sauf si B==Y
01300        cad une des reductions vides que l'on vient de faire a son lhs nt qui est la transition kernel */
01301     ntk_trans = SXFALSE;
01302     bot = eps_red_disp [q];
01303     top = eps_red_disp [q+1];
01304 
01305     if (bot < top) {
01306       do {
01307         prod = eps_red_list [bot];
01308 #if is_1LA
01309 #if is_sdag
01310         if (IS_AND (glbl_source [j+1], prod2la_set [prod]))
01311 #else /* !is_sdag */
01312           t = source [j+1];
01313 
01314         if (SXBA_bit_is_set (prod2la_set [prod], t))
01315 #endif /* !is_sdag */
01316           /* Le test du look-ahead a marche' */
01317 #endif /* is_1LA */
01318           {
01319 #if is_parse_forest
01320         if (SXBA_bit_is_reset_set (eps_prod2i_set [prod], j))
01321           output (prod, j, j);
01322 #endif /* is_parse_forest */
01323         if (lhs [prod] == Y) {
01324           ntk_trans = SXTRUE;
01325         }
01326           }
01327       } while (++bot < top);
01328     }
01329 
01330     if (ntk_trans) {
01331       /* Attention, on ne peut pas appeler
01332          A_shift (j, q, q+1, node_ip);
01333          pour incompatibilite transition kernel/node_ip (ici node_ip est correct alors que A_shift attendrait
01334          un node_jq.
01335          On simule donc ici directement la transition sur le Y vide */
01336       r = q+1; /* Transition sur Y ds le kernel */
01337         
01338 #if EBUG2
01339       node_hd_calls++;
01340 #endif
01341 
01342       if (XxY_set (&node_hd, j, r, &node_jr)) {
01343         /* old */
01344         if (SXBA_bit_is_set_reset (node2node_set_kind, node_jr)) {
01345           /* allocation et recopie */
01346           wset = node2node_set [node_jr];
01347           node_jr2node_set = node2node_set [node_jr] = bag_get (&bag, max_node_set_size);
01348           node_jr2node_set [0] = wset [0];
01349           sxba_copy (node_jr2node_set, wset);
01350         }
01351         else
01352           node_jr2node_set = node2node_set [node_jr];
01353 
01354         if (node_ip_set) {
01355           wset = bag_get (&bag, node_ip_set [0]);
01356       
01357           if (SXBA_OR_MINUS (node_jr2node_set, wset, node_ip_set))
01358         /* wset = node_ip_set - node2node_set [node_jr]; cad les les nouveaux nodes
01359            node2node_set [node_jr] = node2node_set [node_jr] | node_ip_set;
01360         */
01361         p_dispatch (j, r, node_jr, 0, wset);
01362         }
01363         else {
01364           if (node_ip >= node_jr2node_set [0])
01365         node_jr2node_set [0] = node_ip+1; /* On change la taille!! */
01366 
01367           if (SXBA_bit_is_reset_set (node_jr2node_set, node_ip))
01368         p_dispatch (j, r, node_jr, node_ip, NULL);
01369         }
01370       }
01371       else {
01372         /* new */
01373         if (node_ip_set) {
01374           node2node_set [node_jr] = node_ip_set;
01375           SXBA_1_bit (node2node_set_kind, node_jr);
01376           p_dispatch (j, r, node_jr, 0, node_ip_set);
01377         }
01378         else {
01379           node_jr2node_set = node2node_set [node_jr] = bag_get (&bag, max_node_set_size);
01380           node_jr2node_set [0] = node_jr+1; /* On change la taille!! */
01381           SXBA_1_bit (node_jr2node_set, node_ip);
01382           p_dispatch (j, r, node_jr, node_ip, NULL);
01383         }
01384       }
01385     }
01386 #endif /* is_epsilon */
01387 
01388       }
01389     }
01390   } while ((++bot < top) && (q = trans_list [bot]));
01391 }
01392 
01393 
01394 
01395 SXBOOLEAN
01396 sxelc_parse_it ()
01397 {
01398   SXINT j, q, bot, top, node_00, node_01, node_jq, *stack;
01399   SXBA node_jq_set;
01400   SXBOOLEAN RFSA_CHECK_done;
01401 #if EBUG3
01402   char str [12];
01403 #endif /* EBUG3 */
01404 
01405   XxY_alloc (&node_hd, "node_hd", n*n+1, 1, 0, 0, node_hd_oflw, statistics);
01406   node2node_set_kind = sxba_calloc (XxY_size (node_hd)+1);
01407   bag_alloc (&bag, "bag", XxY_size (node_hd)+1, statistics);
01408   node2node_set = (SXBA *) sxalloc (XxY_size (node_hd)+1, sizeof (SXBA));
01409 
01410 #if is_parse_forest
01411   node2i_set = sxbm_calloc (XxY_size (node_hd)+1, n+1);
01412 #if is_epsilon
01413   eps_prod2i_set = sxbm_calloc (nbpro+1, n+1);;
01414 #endif /* is_epsilon */
01415 
01416 #endif /* is_parse_forest */
01417 
01418   ALLOC (stack1, max_state);
01419   ALLOC (stack2, max_state);
01420 
01421   cur_scan_stack = stack1;
01422   scan_stack = stack2;
01423 
01424 #if EBUG2
01425   node_hd_calls = 2;
01426 #endif
01427   XxY_set (&node_hd, 0, 0, &node_00);
01428   XxY_set (&node_hd, 0, 1, &node_01);
01429   node2node_set [node_01] = bag_get (&bag, node_01+1);
01430   SXBA_1_bit (node2node_set [node_01], node_00);
01431 
01432   /* On simule une transition depuis l'etat 0 sur eof vers l'etat (initial) 1 */
01433   PUSH (scan_stack, node_01);
01434 
01435   for (j = 0; j <= n; j++) {
01436     stack = cur_scan_stack;
01437     cur_scan_stack = scan_stack;
01438     scan_stack = stack;
01439 
01440     if (IS_EMPTY (cur_scan_stack))
01441       break;
01442 
01443 #if EBUG3
01444     /* Pour mesurer la complexite' en temps */
01445     if (j % 50 == 0) {
01446       sprintf (str, "%i", j);
01447       sxtime (TIME_FINAL, str);
01448     }
01449 #endif /* EBUG3 */
01450 
01451     /* Estimation (genereuse) de la taille des ensembles node2node_set pour la tranche j */
01452     /* On pourrait, pour la tranche j-1 "compacter les node2node_set */
01453     max_node_set_size = XxY_top (node_hd) + max_state + 1;
01454 
01455     do {
01456       if ((node_jq = POP (cur_scan_stack)) < 0) {
01457     RFSA_CHECK_done = SXFALSE;
01458     node_jq = -node_jq;
01459       }
01460       else
01461     RFSA_CHECK_done = SXTRUE;
01462 
01463       node_jq_set = node2node_set [node_jq];
01464       q = XxY_Y (node_hd, node_jq);
01465 
01466       if (q <= max_state) {
01467     /* transition deterministe */
01468     if (RFSA_CHECK_done || RFSA_CHECKED (q, j)) {
01469       /* Utilisation eventuelle du guide rfsa */
01470       /* Transition terminale non-kernel validee par l'analyse rfsa :
01471          on est au debute une bonne clause au bon indice */
01472       p_dispatch (j, q, node_jq, 0, node_jq_set);
01473     }
01474       }
01475       else {
01476     /* transition non deterministe */
01477     q -= max_state;
01478     bot = trans_disp [q];
01479     top = trans_disp [q+1];
01480 
01481     do {
01482       q = trans_list [bot];
01483 
01484       if (RFSA_CHECK_done || RFSA_CHECKED (q, j)) {
01485         /* Utilisation eventuelle du guide rfsa */
01486         /* Transition terminale non-kernel validee par l'analyse rfsa */
01487         p_dispatch (j, q, node_jq, 0, node_jq_set);
01488       }
01489     } while (++bot < top);
01490       }
01491     } while (!IS_EMPTY (cur_scan_stack));
01492   }
01493 
01494 #if EBUG2
01495   printf ("Polynomial run (%s): node_calls = %i, nodes = %i\n", membership ? "SXTRUE" : "SXFALSE", node_hd_calls, XxY_top (node_hd));
01496 #endif
01497 
01498   XxY_free (&node_hd);
01499   bag_free (&bag);
01500   sxfree (node2node_set), node2node_set = NULL;
01501   sxfree (node2node_set_kind), node2node_set_kind = NULL;
01502   FREE (stack1);
01503   FREE (stack2);
01504 
01505 #if is_parse_forest
01506   sxbm_free (node2i_set), node2i_set = NULL;
01507 #if is_epsilon
01508   sxbm_free (eps_prod2i_set), eps_prod2i_set = NULL;
01509 #endif /* is_epsilon */
01510 #endif
01511 
01512   return membership;
01513 }
01514 

Generated on Wed Apr 21 16:39:32 2010 for syntax-6.0b7 by  doxygen 1.6.1