util/LLgen/lib/nc_rec

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 /*
   5         compile with -DNOFIRST to disable firstset optimization
   6                 -DFOLLOW_OPT to enable followset optimization
   7                 NOTE: Followset optimization is not
   8                         supported when using -s option of LLgen
   9                 -DDEBUG to print debug information
  10 */
  11
  12 extern int      LLsymb;
  13 extern int      LLstartsymb;
  14
  15 #if LL_ANSI_C
  16 void            LLmessage(int);
  17 #endif
  18
  19
  20 struct stacks {
  21
  22         /* Acces to the stacks is through a 'dynamic array' of pointers
  23          * to the heads. We implemented it this way to save on the number
  24          * of Malloc() calls. nr_heads is the number of heads; heads_buf_size
  25          * is the current size of heads_buf.
  26          */
  27
  28         int nr_heads;
  29         struct stack_elt **heads_buf;
  30         int heads_buf_size;
  31
  32         /* r_rec contains nonterminals already tried to build a new
  33          * stack with, to prevent right-recursive rules making the
  34          * process loop forever
  35          */
  36
  37         char r_rec[(LLNNONTERMINALS + 7)/8];
  38
  39         /* join_array contains pointers to already substituted stack
  40          * elements, so that if the same nonterminal turns up again
  41          * we can make a link
  42          */
  43
  44         struct stack_elt *join_array[LLNNONTERMINALS];
  45
  46         /* cleanup_buf contains pointerts to elements that can possibly
  47          * be deleted. Again this is implemented as a `growing array'.
  48          * Although it's not so clean to do it this way, it DOES save
  49          * a lot of time, mainly because much less pointer manipulation
  50          * is required, and because it's not necessary to deallocate
  51          * the buffer after each turn. Just set nr_cleanups to 0...
  52          */
  53
  54         int nr_cleanups;
  55         int cleanup_buf_size;
  56         struct stack_elt **cleanup_buf;
  57
  58         /* visited_buf contains pointers to elements whose flags
  59          * need to be cleared
  60          */
  61
  62         int nr_visited;
  63         int visited_buf_size;
  64         struct stack_elt **visited_buf;
  65
  66
  67         /* start_seen indicates if the last prediction phase
  68          * has matched the start symbol
  69          */
  70
  71         int start_seen;
  72
  73         /* exp_terminals will contain the terminals that are `on top'
  74          * of the prediction graph after a prediction phase
  75          */
  76
  77         char exp_terminals[LLSETSIZE];
  78
  79         /* check_run_ok indicates whether a stack element can be deleted
  80          * or not
  81         */
  82
  83         int check_run_ok;
  84 };
  85
  86
  87 #ifdef DEBUG
  88 static int allocates = 0;
  89 static int deallocates = 0;
  90 static int max_in_use = 0;
  91 static int edge_allocates = 0;
  92 static int edge_deallocates = 0;
  93 static int edge_max_in_use = 0;
  94 #endif
  95
  96 static int grammar_index = 0;
  97
  98 /* The grammar should only be build the first time we enter the
  99  * recovery routine. grammar_read == 0 indicates this has not
 100  * been done yet
 101  */
 102
 103 static int grammar_read = 0;
 104
 105 /* 'terminals' is an array indexed by the number of a terminal and links
 106  * all rules containing this terminal in the RHS
 107  */
 108
 109 static struct terminal *terminals;
 110
 111 /* 'nonterminals' is an array indexed by the number of a nonterminal
 112  * and contains all rules with this nonterminal in the LHS and links all
 113  * rules containing this nonterminal in the RHS
 114  */
 115
 116 static struct nonterminal *nonterminals;
 117
 118
 119 /* These functions must be called instead of the original functions in
 120  * 'malloc.h'. They offer a checking allocation mechanism.
 121 */
 122 #if LL_ANSI_C
 123 static char *Malloc(unsigned);
 124 static char *Realloc(char*, unsigned);
 125
 126 #else
 127
 128 static char *Malloc();
 129 static char *Realloc();
 130 #endif
 131
 132
 133 /* These functions build the grammar */
 134 #if LL_ANSI_C
 135 static void init_grammar(void);
 136 static void build_grammar(void);
 137 static struct lhs *build_rule(void);
 138 static struct symbol *build_rhs(struct lhs*);
 139 static struct symbol *make_link(struct symbol*);
 140
 141 #else
 142
 143 static init_grammar();
 144 static build_grammar();
 145 static struct lhs *build_rule();
 146 static struct symbol *build_rhs();
 147 static struct symbol *make_link();
 148 #endif
 149
 150
 151 /* These functions operate on the stacks */
 152 #if LL_ANSI_C
 153 static int optimize(struct stacks*, struct symbol*, int);
 154 static void read_token(void);
 155 static void start_stack(struct stacks*, int, int);
 156 static void continuation(struct stacks*, int, int);
 157 static struct stack_elt *push_rule(struct stack_elt*, struct symbol*);
 158 static void new_head(struct stacks*, struct stack_elt*);
 159 static void to_delete(struct stacks*, struct stack_elt*);
 160 static void substitute(struct stacks*, struct stack_elt*, int);
 161 static int join(struct stacks*, struct stack_elt*, int);
 162 static int path(struct stack_elt*, struct stack_elt*);
 163 static int part_of_loop(struct stack_elt*);
 164 static void generate_heads(struct stacks*, struct stack_elt*, int);
 165 static void delete(struct stacks*, struct stack_elt*);
 166 static void hyp_run(struct stack_elt*);
 167 static void check_run(struct stacks*, struct stack_elt*);
 168 static struct stack_elt *split(struct stack_elt*);
 169 #ifdef DEBUG
 170 static void test(struct stacks*);
 171 static void dump_stack(struct stack_elt*, int);
 172 #endif
 173 static void clear_flags(struct stack_elt*, char);
 174 static void clear_gen_flags(struct stacks*);
 175 static void match_heads(struct stacks*, int);
 176 static void cleanup(struct stacks*);
 177 static void initialize(struct stacks*);
 178 static void calculate(struct stacks*, int);
 179 static void kill_stack(struct stacks *stack);
 180 void LLnc_recover(void);
 181
 182 #else
 183
 184 static int optimize();
 185 static read_token();
 186 static start_stack();
 187 static continuation();
 188 static struct stack_elt *push_rule();
 189 static new_head();
 190 static to_delete();
 191 static substitute();
 192 static int join();
 193 static int path();
 194 static int part_of_loop();
 195 static generate_heads();
 196 static delete();
 197 static hyp_run();
 198 static check_run();
 199 static struct stack_elt *split();
 200 static test();
 201 static dump_stack();
 202 static clear_flags();
 203 static clear_gen_flags();
 204 static match_heads();
 205 static cleanup();
 206 static initialize();
 207 static calculate();
 208 static kill_stack();
 209 LLnc_recover();
 210 #endif
 211
 212
 213 #if LL_ANSI_C
 214 static char *Malloc(unsigned size)
 215 #else
 216 static char *Malloc(size)
 217 unsigned size;
 218 #endif
 219 {
 220         char *p;
 221
 222         if ((p = malloc(size)) == (char *)0) {
 223                 fprintf(stderr, "fatal error: out of memory\n");
 224                 exit(1);
 225         }
 226         return p;
 227 }
 228
 229
 230 #if LL_ANSI_C
 231 static char *Realloc(char *ptr, unsigned size)
 232 #else
 233 static char *Realloc(ptr, size)
 234 char *ptr;
 235 unsigned size;
 236 #endif
 237 {
 238         char *p;
 239
 240         if ((p = realloc(ptr, size)) == (char *)0) {
 241                 fprintf(stderr, "fatal error: out of memory\n");
 242                 exit(1);
 243         }
 244         return p;
 245 }
 246
 247
 248 #if LL_ANSI_C
 249 static void init_grammar(void)
 250 #else
 251 static init_grammar()
 252 #endif
 253 {
 254 /* Allocate and initialize an array for terminals and nonterminals */
 255
 256         int i;
 257
 258         terminals = (struct terminal *)
 259                 Malloc((unsigned) LLFIRST_NT * sizeof(struct terminal));
 260         for (i = 0; i < LLFIRST_NT; i++) {
 261                 (terminals + i)->link = (struct symbol *)0;
 262         }
 263
 264         nonterminals = (struct nonterminal *)
 265                 Malloc((unsigned)LLNNONTERMINALS * sizeof(struct nonterminal));
 266         for (i = 0; i < LLNNONTERMINALS; i++) {
 267                 (nonterminals + i)->rule = (struct lhs *)0;
 268                 (nonterminals + i)->link = (struct symbol *)0;
 269         }
 270 }
 271
 272
 273 #if LL_ANSI_C
 274 static void build_grammar(void)
 275 #else
 276 static build_grammar()
 277 #endif
 278 {
 279 /* Build a rule for every nonterminal. The LHS must be saved first because
 280  * of the fact that the right side of an assignment statement (in C) will
 281  * be evaluated before the left side
 282  */
 283         int nt, j;
 284
 285         init_grammar();
 286         for (j = 0; j < LLNNONTERMINALS; j++) {
 287                 nt = LLgrammar[grammar_index];
 288                 (nonterminals + nt - LLFIRST_NT)->rule = build_rule();
 289         }
 290 }
 291
 292
 293 #if LL_ANSI_C
 294 static struct lhs *build_rule(void)
 295 #else
 296 static struct lhs *build_rule()
 297 #endif
 298 {
 299 /* Build LHS and call a funcion to create RHS */
 300
 301         struct lhs *l;
 302         int j;
 303
 304         l = (struct lhs *)Malloc(sizeof(struct lhs));
 305         l->nr = LLgrammar[grammar_index++];
 306
 307         /* Build first set */
 308         for (j = 0; j < LLSETSIZE; j++) {
 309                 l->first[j] = LLgrammar[grammar_index++];
 310         }
 311
 312         /* Build follow set */
 313         for (j = 0; j < LLSETSIZE; j++) {
 314                 l->follow[j] = LLgrammar[grammar_index++];
 315         }
 316
 317         l->empty = LLgrammar[grammar_index++];  /* Can NT produce empty? */
 318
 319         l->rhs = build_rhs(l);
 320
 321         return l;
 322 }
 323
 324
 325 #if LL_ANSI_C
 326 static struct symbol *build_rhs(struct lhs *l)
 327 #else
 328 static struct symbol *build_rhs(l)
 329 struct lhs *l;
 330 #endif
 331 {
 332 /* Build RHS by creating structs for all symbols including ALT and
 333  * EORULE. Also call a function for linking same terminals and
 334  * nonterminals.
 335  */
 336
 337         struct symbol *r;
 338
 339         r = (struct symbol *)Malloc(sizeof(struct symbol));
 340         if (LLgrammar[grammar_index] == LLALT) {
 341                 grammar_index++;
 342                 r->x = LLALT;
 343                 r->nr = -1;                     /* Not applicable */
 344                 r->link = (struct symbol *)0;   /* Not applicable */
 345                 r->next = build_rhs(l);
 346                 r->lhs = l;
 347         }
 348         else if (LLgrammar[grammar_index] == LLEORULE) {
 349                 grammar_index++;
 350                 r->x = LLEORULE;
 351                 r->nr = -1;                     /* Not applicable */
 352                 r->link = (struct symbol *)0;   /* Not applicable */
 353                 r->next = (struct symbol *)0;   /* Not applicable */
 354                 r->lhs = l;
 355         }
 356         else if (LLgrammar[grammar_index] < LLFIRST_NT) {
 357                 r->x = LLTERMINAL;
 358                 r->nr = LLgrammar[grammar_index++];
 359                 r->link = make_link(r);
 360                 r->next = build_rhs(l);
 361                 r->lhs = l;
 362         }
 363         else {
 364                 r->x = LLNONTERMINAL;
 365                 r->nr = LLgrammar[grammar_index++];
 366                 r->link = make_link(r);
 367                 r->next = build_rhs(l);
 368                 r->lhs = l;
 369         }
 370         return r;
 371 }
 372
 373
 374 #if LL_ANSI_C
 375 static struct symbol *make_link(struct symbol *r)
 376 #else
 377 static struct symbol *make_link(r)
 378 struct symbol *r;
 379 #endif
 380 {
 381 /* Link same terminals and nonterminals. Every new symbol is appended
 382  * in front of the corresponding list for efficiency.
 383  */
 384
 385         struct symbol *tmp;
 386
 387         if (r->nr < LLFIRST_NT) {
 388                 /* Terminal array */
 389                 tmp = (terminals + r->nr)->link;
 390                 (terminals + r->nr)->link = r;
 391         }
 392         else {                                  /* Nonterminal array */
 393                 tmp = (nonterminals + (r->nr - LLFIRST_NT))->link;
 394                 (nonterminals + (r->nr - LLFIRST_NT))->link = r;
 395         }
 396         return tmp;
 397 }
 398
 399
 400 /*****************************************************************************/
 401
 402
 403 #if LL_ANSI_C
 404 static int optimize(struct stacks* stack, struct symbol *symb_ptr, int l_ahead)
 405 #else
 406 static int optimize(stack, symb_ptr, l_ahead)
 407 struct stacks *stack;
 408 struct symbol *symb_ptr;
 409 int l_ahead;
 410 #endif
 411
 412 /* Return 1 if rule symb_ptr can start with terminal l_ahead, else return 0.
 413  * The array with expected terminals will also be filled in.
 414  */
 415 {
 416         struct lhs *l;
 417         int i;
 418
 419 #ifdef NOFIRST
 420         return(1);
 421 #else
 422
 423         if ((l_ahead <= 0) || (l_ahead == EOFILE)) return 1;
 424
 425         switch(symb_ptr->x) {
 426         case LLTERMINAL:
 427                 LLPUTIN(stack->exp_terminals, LLindex[symb_ptr->nr]);
 428                 if (symb_ptr->nr != l_ahead) return 0;
 429                 else return 1;/*???*/
 430
 431         case LLNONTERMINAL:
 432                 l = (nonterminals + symb_ptr->nr - LLFIRST_NT)->rule;
 433                 if (LLIN(l->first, LLindex[l_ahead])) return 1;
 434                 else if (l->empty) {
 435                         /* Try next symbol */
 436                         return optimize(stack, symb_ptr->next, l_ahead);
 437                 }
 438                 else {
 439                         for (i = 0; i < LLSETSIZE; i++) {
 440                                 stack->exp_terminals[i] |= (l->first)[i];
 441                         }
 442                         return 0;
 443                 }
 444
 445         default:
 446
 447 #ifndef FOLLOW_OPT
 448                 return(1);
 449 #else
 450
 451                 l = (nonterminals + symb_ptr->lhs->nr - LLFIRST_NT)->rule;
 452
 453                 if (LLIN(l->follow, LLindex[l_ahead])) return 1;
 454                 else {
 455                         for (i = 0; i < LLSETSIZE; i++) {
 456                                 stack->exp_terminals[i] |= (l->follow)[i];
 457                         }
 458                         return 0;
 459                 }
 460 #endif /*FOLLOW_OPT */
 461         }
 462 #endif /* NOFIRST */
 463 }
 464
 465
 466 #if LL_ANSI_C
 467 static void read_token(void)
 468 #else
 469 static read_token()
 470 #endif
 471
 472 /* Read token and put it in global variable LLsymb, skipping
 473  * invalid tokens
 474  */
 475 {
 476         LLsymb = LL_LEXI();
 477         while (LLindex[LLsymb] < 0) {
 478                 /* Skip garbage tokens */
 479                 LLmessage(0);
 480                 LLsymb = LL_LEXI();
 481         }
 482 }
 483
 484
 485 #if LL_ANSI_C
 486 static void start_stack(struct stacks *stack, int base, int l_ahead)
 487 #else
 488 static start_stack(stack, base, l_ahead)
 489 struct stacks *stack;
 490 int base, l_ahead;
 491 #endif
 492
 493 /* Start stack on base symbol base with lookahead l_ahead */
 494
 495 {
 496         struct stack_elt *bottom, *top;
 497         struct symbol *symb_ptr;
 498         int i;
 499
 500         /* Find first applicable rule */
 501         symb_ptr = (terminals + base)->link;
 502
 503         /* Now try all applicable rules */
 504         while (symb_ptr != (struct symbol *)0) {
 505
 506                 /* If the current rule cannot start with l_ahead,
 507                  * try the next one
 508                  */
 509                 if (!optimize(stack, symb_ptr->next, l_ahead)) {
 510                         symb_ptr = symb_ptr->link;
 511                         continue;
 512                 }
 513
 514                 if (    (symb_ptr->next->x == LLTERMINAL)
 515                 ||      (symb_ptr->next->x == LLNONTERMINAL)
 516                 ) {
 517                         /* Allocate an end-of-stack */
 518 #ifdef DEBUG
 519                         allocates++;
 520                         if (allocates - deallocates > max_in_use) {
 521                                 max_in_use = allocates - deallocates;
 522                         }
 523 #endif
 524                         bottom = (struct stack_elt *)
 525                                         Malloc(sizeof(struct stack_elt));
 526                         bottom->edges = (struct edge *)0;
 527                         bottom->nr = LLEOSTACK;
 528                         bottom->flags = 0;
 529                         bottom->nr_nexts = 0;
 530                         bottom->ref_count = 0;
 531                         bottom->hyp_ref_count = -1;
 532
 533                         /* And use the rule to build a stack on it */
 534                         top = push_rule(bottom, symb_ptr->next);
 535
 536                         /* Remember that we're now trying to match the LHS
 537                          * of the used rule
 538                          */
 539                         bottom->matched = symb_ptr->lhs->nr;
 540
 541                         if (top->nr >= LLFIRST_NT) {
 542                                 substitute(stack, top, l_ahead);
 543                         }
 544                         else {
 545                                 new_head(stack, top);
 546                         }
 547
 548                         /* Perhaps this only has produced an empty stack, in
 549                          * that case bottom can be deallocated.
 550                          */
 551                         if (bottom->ref_count == 0) {
 552                                 to_delete(stack, bottom);
 553                         }
 554                 }
 555                 else {
 556                         /* base was the last element of the rule, so we
 557                          * figure we have matched the LHS of this rule.
 558                          */
 559                         if (symb_ptr->lhs->nr == LLstartsymb) {
 560                                 stack->start_seen = 1;
 561                         }
 562
 563                         continuation(stack, symb_ptr->lhs->nr, l_ahead);
 564                 }
 565                 symb_ptr = symb_ptr->link;
 566         }
 567
 568
 569         /* Reinitialize some arrays */
 570         for (i = 0; i < (LLNNONTERMINALS + 7)/8; i++) {
 571                 stack->r_rec[i] = (char) 0;
 572         }
 573
 574         for (i = 0; i < LLNNONTERMINALS; i++) {
 575                 stack->join_array[i] = (struct stack_elt *)0;
 576         }
 577
 578         /* Delete all HEAD flags */
 579         for (i = 0; i < stack->nr_heads; i++) {
 580                 (*(stack->heads_buf + i))->flags &= ~LLHEAD;
 581         }
 582
 583         /* Delete flags turned on by 'generate_heads()' */
 584                 clear_gen_flags(stack);
 585         /* Try to delete elements on cleanup_buf */
 586         cleanup(stack);
 587 }
 588
 589
 590 #if LL_ANSI_C
 591 static void continuation(struct stacks *stack, int nt, int l_ahead)
 592 #else
 593 static continuation(stack, nt, l_ahead)
 594 struct stacks *stack;
 595 int nt, l_ahead;
 596 #endif
 597
 598 /* We have 'eaten' a whole stack, and think we recognized nt. Now
 599 look for rules that we can proceed with, ie containing nt in the RHS.
 600 Each rule found will be developed untill a terminal is at the top
 601 of the stack.*/
 602 {
 603
 604         struct symbol *symb_ptr;
 605         struct stack_elt *bottom, *top;
 606
 607         /* If we've already tried this nt, don't do it again.
 608          * Otherwise we may loop forever on right-recursive rules
 609          */
 610         if (LLIN(stack->r_rec, nt - LLFIRST_NT)) return;
 611
 612         /* Mark that we have looked for a continuation for nt */
 613         LLPUTIN(stack->r_rec, nt - LLFIRST_NT);
 614
 615         /* Find first applicable rule */
 616         symb_ptr = (nonterminals + nt - LLFIRST_NT)->link;
 617
 618         /* Try all applicable rules */
 619         while (symb_ptr != (struct symbol *)0) {
 620
 621                 /* If the current rule cannot start with l_ahead,
 622                  * try the next one
 623                  */
 624                 if (!optimize(stack, symb_ptr->next, l_ahead)) {
 625                         symb_ptr = symb_ptr->link;
 626                         continue;
 627                 }
 628
 629                 if (    (symb_ptr->next->x == LLTERMINAL)
 630                 ||      (symb_ptr->next->x == LLNONTERMINAL)
 631                 ) {
 632 #ifdef DEBUG
 633                         allocates++;
 634                         if (allocates - deallocates > max_in_use) {
 635                                         max_in_use = allocates - deallocates;
 636                                 }
 637 #endif
 638                         bottom = (struct stack_elt *)
 639                                         Malloc(sizeof(struct stack_elt));
 640                         bottom->edges = (struct edge *)0;
 641                         bottom->nr = LLEOSTACK;
 642                         bottom->flags = 0;
 643                         bottom->nr_nexts = 0;
 644                         bottom->ref_count = 0;
 645                         bottom->hyp_ref_count = -1;
 646
 647                         /* Use the rule to build a stack on bottom */
 648                         top = push_rule(bottom, symb_ptr->next);
 649
 650                         /* Remember that we're now trying to match the LHS
 651                          * of the used rule
 652                          */
 653                         bottom->matched = symb_ptr->lhs->nr;
 654
 655                         if (top->nr >= LLFIRST_NT) {
 656                                 substitute(stack, top, l_ahead);
 657                         }
 658                         else {
 659                                 new_head(stack, top);
 660                         }
 661
 662                         /* Perhaps this only has produced an empty stack, in
 663                          * that case bottom can be deallocated.
 664                          */
 665                         if (bottom->ref_count == 0) {
 666                                 delete(stack, bottom);
 667                         }
 668                 }
 669                 else {
 670                         /* Stack is still empty */
 671                         if (symb_ptr->lhs->nr == LLstartsymb) {
 672                                 stack->start_seen = 1;
 673                         }
 674
 675                         continuation(stack, symb_ptr->lhs->nr, l_ahead);
 676                 }
 677
 678                 symb_ptr = symb_ptr->link;
 679         }
 680 }
 681
 682
 683 #if LL_ANSI_C
 684 static struct stack_elt *push_rule(struct stack_elt *element,
 685                                         struct symbol *symb_ptr)
 686 #else
 687 static struct stack_elt *push_rule(element, symb_ptr)
 688 struct stack_elt *element;
 689 struct symbol *symb_ptr;
 690 #endif
 691
 692 /* Append the rule symb_ptr to stack element 'element'. Return a
 693  * pointer to the new top of the stack
 694  */
 695 {
 696         struct stack_elt *se, *top;
 697
 698         if (    (symb_ptr->next->x == LLTERMINAL)
 699         ||      (symb_ptr->next->x == LLNONTERMINAL)
 700         ) {
 701                 top = push_rule(element, symb_ptr->next);
 702         }
 703         else {
 704                 top = element;
 705         }
 706
 707 #ifdef DEBUG
 708         allocates++;
 709         if (allocates - deallocates > max_in_use) {
 710                 max_in_use = allocates - deallocates;
 711         }
 712 #endif
 713
 714         se = (struct stack_elt *)Malloc(sizeof(struct stack_elt));
 715         se->flags = 0;
 716         se->nr = symb_ptr->nr;
 717         se->ref_count = 0;
 718         se->hyp_ref_count = -1;
 719         se->matched = -1;
 720         se->nr_nexts = 1;
 721
 722 #ifdef DEBUG
 723         edge_allocates++;
 724         if (edge_allocates - edge_deallocates > edge_max_in_use) {
 725                 edge_max_in_use = edge_allocates - edge_deallocates;
 726         }
 727 #endif
 728
 729         se->edges = (struct edge *)Malloc(sizeof(struct edge));
 730         se->edges->ptr = top;
 731         se->edges->flags = 0;
 732
 733         top->ref_count++;
 734         return se;
 735 }
 736
 737
 738 #if LL_ANSI_C
 739 static void new_head(struct stacks *stack, struct stack_elt *ptr)
 740 #else
 741 static new_head(stack, ptr)
 742 struct stacks *stack;
 743 struct stack_elt *ptr;
 744 #endif
 745
 746 /* Make ptr a head of stack */
 747 {
 748
 749         /* Is this already a head?*/
 750         if (ptr->flags & LLHEAD) return;
 751
 752         if (stack->heads_buf_size == 0) {
 753                 stack->heads_buf_size = LLHEADS_BUF_INCR;
 754                 stack->heads_buf = (struct stack_elt **)
 755                         Malloc(LLHEADS_BUF_INCR * sizeof(struct stack_elt *));
 756         }
 757         else if (stack->nr_heads == stack->heads_buf_size) {
 758                 /* buffer full? */
 759                 stack->heads_buf_size += LLHEADS_BUF_INCR;
 760                 stack->heads_buf = (struct stack_elt **)
 761                         Realloc((char *)
 762                                 stack->heads_buf, (unsigned)
 763                                 stack->heads_buf_size *
 764                                         sizeof(struct stack_elt *)
 765                         );
 766         }
 767
 768         *(stack->heads_buf + stack->nr_heads) = ptr;    /* Add at the tail */
 769         stack->nr_heads++;              /* Increase number of heads */
 770         ptr->flags |= LLHEAD;           /* Mark it as a head */
 771         ptr->ref_count++;               /* Increase reference count */
 772         LLPUTIN(stack->exp_terminals, LLindex[ptr->nr]);
 773 }
 774
 775
 776 #if LL_ANSI_C
 777 static void to_delete(struct stacks *stack, struct stack_elt *ptr)
 778 #else
 779 static to_delete(stack, ptr)
 780 struct stacks *stack;
 781 struct stack_elt *ptr;
 782 #endif
 783
 784 /* Remember that ptr has to be deleted */
 785 {
 786
 787         int i;
 788
 789 #ifdef NOCLEAN
 790         return;
 791 #endif
 792
 793
 794
 795         for (i = 0; i < stack->nr_cleanups; i++) {
 796                 /* Check if already in buffer */
 797                 if (*(stack->cleanup_buf + i) == ptr) return;
 798         }
 799
 800         if (stack->cleanup_buf_size == 0) {
 801                 stack->cleanup_buf_size = LLCLEANUP_BUF_INCR;
 802                 stack->cleanup_buf = (struct stack_elt **)
 803                 Malloc(LLCLEANUP_BUF_INCR * sizeof(struct stack_elt *));
 804         }
 805         else if (stack->nr_cleanups == stack->cleanup_buf_size) {
 806                 stack->cleanup_buf_size += LLCLEANUP_BUF_INCR;
 807                 stack->cleanup_buf = (struct stack_elt **)
 808                         Realloc((char *) stack->cleanup_buf,
 809                                 (unsigned) stack->cleanup_buf_size *
 810                                 sizeof(struct stack_elt *));
 811         }
 812         *(stack->cleanup_buf + stack->nr_cleanups) = ptr;
 813         stack->nr_cleanups++;
 814 }
 815
 816
 817 #if LL_ANSI_C
 818 static void substitute(struct stacks *stack, struct stack_elt *top, int l_ahead)
 819 #else
 820 static substitute(stack, top, l_ahead)
 821 struct stacks *stack;
 822 struct stack_elt *top;
 823 int l_ahead;
 824 #endif
 825
 826 /* This function substitutes the NT pointed to by 'top'. 'top' should be a top
 827  * of a stack
 828  */
 829 {
 830         struct symbol *symb_ptr;
 831         struct stack_elt *new_top;
 832
 833         /* Try to join top NT */
 834         if (join(stack, top, l_ahead)) return;
 835
 836         /* Find RHS of the rule of nonterminal 'top->nr' */
 837         symb_ptr = (nonterminals + top->nr - LLFIRST_NT)->rule->rhs;
 838
 839         /* Mark top as dummy */
 840         top->flags |= LLDUMMY;
 841
 842         while (1) {
 843                 /* If this an empty production, search down the stack for
 844                  * terminals
 845                  */
 846                 if ((symb_ptr->x == LLALT) || (symb_ptr->x == LLEORULE)) {
 847                         generate_heads(stack, top, l_ahead);
 848                 }
 849
 850                 /* Skip other empty productions, they have no effect. */
 851                 while (symb_ptr->x == LLALT) {
 852                         symb_ptr = symb_ptr->next;
 853                 }
 854
 855                 if (symb_ptr->x == LLEORULE) {
 856                         /* If there are only empty productions, the NT on top
 857                          * can be deleted
 858                          */
 859                         if (top->ref_count == 0) {
 860                                 to_delete(stack, top);
 861                         }
 862                         return;
 863                 }
 864
 865                 /* If this rule can produce 'l_ahead' on the top of the stack
 866                  * substitute the nonterminal
 867                  */
 868                 if (optimize(stack, symb_ptr, l_ahead)) {
 869                         new_top = push_rule(top, symb_ptr);
 870
 871                         /* If the new element on top is a nonterminal
 872                          * substitute it, else make it a head
 873                          */
 874                         if (new_top->nr >= LLFIRST_NT) {
 875                                 substitute(stack, new_top, l_ahead);
 876                         }
 877                         else {
 878                                 new_head(stack, new_top);
 879                         }
 880                 }
 881
 882                 /* Search to next alternative */
 883                 while ( (symb_ptr->x == LLTERMINAL)
 884                 ||      (symb_ptr->x == LLNONTERMINAL)
 885                 ) {
 886                         symb_ptr = symb_ptr->next;
 887                 }
 888
 889                 if (symb_ptr->x == LLEORULE) {
 890                         if (top->ref_count == 0) {
 891                                 to_delete(stack, top);
 892                         }
 893                         return;
 894                 }
 895                 else {
 896                         symb_ptr = symb_ptr->next;
 897                 }
 898         }
 899
 900 }
 901
 902
 903 #if LL_ANSI_C
 904 static int join(struct stacks *stack, struct stack_elt *top, int l_ahead)
 905 #else
 906 static int join(stack, top, l_ahead)
 907 struct stacks *stack;
 908 struct stack_elt *top;
 909 int l_ahead;
 910 #endif
 911
 912 /* This function tries to connect a NT on top of a stack with another stack,
 913  * which has already substituted this NT
 914  */
 915 {
 916         struct stack_elt *se;
 917         int size;
 918
 919         if (    (se = stack->join_array[top->nr - LLFIRST_NT]) ==
 920                         (struct stack_elt *)0
 921         ) {
 922                 stack->join_array[top->nr - LLFIRST_NT] = top;
 923                 return 0;               /* Join not possible */
 924         }
 925         else {
 926                 se->nr_nexts++;         /* Increase number of descendants */
 927
 928 #ifdef DEBUG
 929                 edge_allocates++;
 930                 if (edge_allocates - edge_deallocates > edge_max_in_use) {
 931                         edge_max_in_use = edge_allocates - edge_deallocates;
 932                 }
 933 #endif
 934
 935                 /* Allocate one more pointer to descendants */
 936                 size = se->nr_nexts * sizeof(struct edge);
 937                 se->edges = (struct edge *)Realloc((char *) se->edges,
 938                                                         (unsigned) size);
 939
 940                 /* Link it */
 941                 (se->edges + se->nr_nexts - 1)->ptr = top->edges->ptr;
 942                 (se->edges + se->nr_nexts - 1)->flags = 0;
 943
 944                 /* The successor of 'top' gets an extra predecessor.
 945                  * 'top' has always only one successor because the stacks are
 946                  * constructed in 'depth first' order
 947                  */
 948                 top->edges->ptr->ref_count++;
 949
 950
 951 #ifndef NOLOOPS
 952                 /* If we have made a new loop find all stack elements of this
 953                  * loop and mark them
 954                  */
 955                 if (path(top->edges->ptr, se)) {
 956                         (se->edges + se->nr_nexts - 1)->flags |= LLLOOP;
 957                         (se->edges + se->nr_nexts - 1)->flags |= LLYES;
 958                 }
 959                 clear_flags(top->edges->ptr, (LLNO | LLYES));
 960 #endif
 961
 962
 963                 /* Check if joined NT produces empty */
 964                 if ((nonterminals + se->nr - LLFIRST_NT)->rule->empty) {
 965                         generate_heads(stack, top, l_ahead);
 966                 }
 967
 968                 /* Deallocate top symbol */
 969                 if (top->ref_count == 0) {
 970                         to_delete(stack, top);
 971                 }
 972
 973                 return 1;
 974         }
 975 }
 976
 977
 978 #ifndef NOLOOPS
 979
 980 #if LL_ANSI_C
 981 static int path(struct stack_elt *se1, struct stack_elt *se2)
 982 #else
 983 static int path(se1, se2)
 984 struct stack_elt *se1, *se2;
 985 #endif /* LL_ANSI_C */
 986
 987 /* If there is a path from se1 to se2 it returns 1 and marks all the paths
 988  * betweeen these two points, otherwise it returns 0. The flags LLYES and
 989  * LLNO are used for optimization. */
 990 {
 991         int i, result = 0;
 992
 993         if (se1 == se2) return 1;
 994
 995         for (i = 0; i < se1->nr_nexts; i++) {
 996                 if (    (!((se1->edges + i)->flags & LLNO))
 997                 &&      (!((se1->edges + i)->flags & LLLOOP_SEARCH))
 998                 ) {
 999                         (se1->edges + i)->flags |= LLLOOP_SEARCH;
1000
1001                         if (path((se1->edges + i)->ptr, se2)) {
1002                                 (se1->edges + i)->flags |= LLLOOP;
1003                                 result = 1;
1004                         }
1005                         else {
1006                                 (se1->edges + i)->flags |= LLNO;
1007                         }
1008
1009                         (se1->edges + i)->flags &= ~LLLOOP_SEARCH;
1010                 }
1011                 (se1->edges + i)->flags |= LLYES;
1012         }
1013         return result;
1014 }
1015
1016
1017 #if LL_ANSI_C
1018 static int part_of_loop(struct stack_elt *se)
1019 #else
1020 static int part_of_loop(se)
1021 struct stack_elt *se;
1022 #endif /* LL_ANSI_C */
1023
1024 /* Checks if 'se' belongs to a loop */
1025 {
1026         int i;
1027
1028         for (i = 0; i < se->nr_nexts; i++) {
1029                 if ((se->edges + i)->flags & LLLOOP) return 1;
1030         }
1031         return 0;
1032 }
1033
1034 #endif /* NOLOOPS */
1035
1036
1037 #if LL_ANSI_C
1038 static void generate_heads(struct stacks *stack, struct stack_elt *se,
1039                                 int l_ahead)
1040 #else
1041 static generate_heads(stack, se, l_ahead)
1042 struct stacks *stack;
1043 struct stack_elt *se;
1044 int l_ahead;
1045 #endif
1046
1047 /* This funcion finds all heads starting at 'se'. */
1048 {
1049         int i;
1050         struct stack_elt *next_se;
1051
1052
1053         for (i = 0; i < se->nr_nexts; i++) {
1054
1055                 if (!((se->edges + i)->ptr->flags & LLGEN_SEARCH)) {
1056
1057                         (se->edges + i)->ptr->flags |= LLGEN_SEARCH;
1058
1059                         next_se = (se->edges + i)->ptr;
1060
1061                         /* Remember a flag has to be cleared later */
1062
1063                         if (stack->visited_buf_size == 0) {
1064                                 stack->visited_buf_size = LL_VIS_INCR;
1065                                 stack->visited_buf = (struct stack_elt **)
1066                                 Malloc(LL_VIS_INCR * sizeof(struct stack_elt *));
1067                         }
1068                         else if (stack->nr_visited == stack->visited_buf_size) {
1069                                 stack->visited_buf_size += LL_VIS_INCR;
1070                                 stack->visited_buf = (struct stack_elt **)
1071                                         Realloc((char *) stack->visited_buf,
1072                                         (unsigned) stack->visited_buf_size *
1073                                         sizeof(struct stack_elt *));
1074                         }
1075                         *(stack->visited_buf + stack->nr_visited) = next_se;
1076                         stack->nr_visited++;
1077
1078                         if (next_se->flags & LLDUMMY) {
1079                                 generate_heads(stack, next_se, l_ahead);
1080                         }
1081                         else if (next_se->nr == LLEOSTACK) {
1082                                 /* We have matched a nt */
1083                                 if (next_se->matched == LLstartsymb) {
1084                                         stack->start_seen = 1;
1085                                 }
1086
1087                                 continuation(stack, next_se->matched, l_ahead);
1088                                 if (next_se->ref_count == 0) {
1089                                         to_delete(stack, next_se);
1090                                 }
1091                         }
1092                         else if (next_se->nr < LLFIRST_NT) {
1093                                 /* terminal */
1094                                 new_head(stack, next_se);
1095                         }
1096                         else {
1097                                 if (next_se->ref_count > 0) {
1098                                         next_se = split(next_se);
1099                                 }
1100                                 substitute(stack, next_se, l_ahead);
1101                         }
1102                 }
1103         }
1104 }
1105
1106
1107 #if LL_ANSI_C
1108 static void delete(struct stacks *stack, struct stack_elt *se)
1109 #else
1110 static delete(stack, se)
1111 struct stacks *stack;
1112 struct stack_elt *se;
1113 #endif
1114
1115 /* This function runs down the stack(s) deleting every element which cannot be
1116  * reached anymore. */
1117 {
1118         int i;
1119
1120 #ifdef NOCLEAN
1121         return;
1122 #endif
1123
1124         if (se->ref_count == 0) {
1125
1126                 /* Decrease reference counts of all successors */
1127                 for (i = 0; i < se->nr_nexts; i++) {
1128                         if ((se->edges + i)->ptr->ref_count != 0) {
1129                                 (se->edges + i)->ptr->ref_count--;
1130
1131                                 /* Try to delete next element */
1132                                 delete(stack, (se->edges + i)->ptr);
1133                         }
1134                 }
1135
1136                 /* If this element is saved in the join_array clear it */
1137                 if (se->nr >= LLFIRST_NT) {
1138                         if (stack->join_array[se->nr - LLFIRST_NT] == se) {
1139                                 stack->join_array[se->nr - LLFIRST_NT] =
1140                                         (struct stack_elt *)0;
1141                         }
1142                 }
1143 #ifdef DEBUG
1144                 deallocates++;
1145                 edge_deallocates += se->nr_nexts;
1146 #endif
1147                 free((char *) se->edges);
1148                 free((char *) se);
1149         }
1150
1151 #ifndef NOLOOPS
1152         /* If this element belongs to a loop try to delete it */
1153         else if (part_of_loop(se)) {
1154
1155                 /* Do a temporary delete */
1156                 hyp_run(se);
1157
1158                 /* Check it */
1159                 stack->check_run_ok = 1;
1160                 check_run(stack, se);
1161
1162                 /* If it can be deleted delete it */
1163                 if (stack->check_run_ok) {
1164                         se->ref_count = 0;
1165                         delete(stack, se);
1166                 }
1167
1168         }
1169 #endif
1170 }
1171
1172
1173 #ifndef NOLOOPS
1174
1175 #if LL_ANSI_C
1176 static void hyp_run(struct stack_elt *se)
1177 #else
1178 static hyp_run(se)
1179 struct stack_elt *se;
1180 #endif /* LL_ANSI_C */
1181
1182 /* This function sets the 'hyp_ref_counts' of all elements of the loop that
1183  * 'se' belongs to to the value that 'ref_count' will get when 'se' is
1184  * deleted
1185  */
1186 {
1187         int i;
1188         struct stack_elt *next_se;
1189
1190         for (i = 0; i < se->nr_nexts; i++) {
1191                 next_se = (se->edges + i)->ptr;
1192
1193                 if (    (!((se->edges + i)->flags & LLHYP_SEARCH))
1194                 &&      ((se->edges + i)->flags & LLLOOP)
1195                 ) {
1196                         (se->edges + i)->flags |= LLHYP_SEARCH;
1197
1198                         /* If this element is not yet visited initialize
1199                          * 'hyp_ref_count' else decrease it by one
1200                          */
1201                         if (next_se->hyp_ref_count == -1) {
1202                                 next_se->hyp_ref_count = next_se->ref_count - 1;
1203                         }
1204                         else {
1205                                 next_se->hyp_ref_count--;
1206                         }
1207
1208                         /* Continue searching */
1209                         hyp_run(next_se);
1210                 }
1211         }
1212 }
1213
1214
1215 #if LL_ANSI_C
1216 static void check_run(struct stacks *stack, struct stack_elt *se)
1217 #else
1218 static check_run(stack, se)
1219 struct stacks *stack;
1220 struct stack_elt *se;
1221 #endif /* LL_ANSI_C */
1222
1223 /* This function checks all 'hyp_ref_counts' that 'hyp_run()' has set.
1224  * If one of them is not 0, 'check_run_ok' will be set to 0 indicating
1225  * that 'se' cannot be deleted. 'check_run()' also resets all 'hyp_ref_counts'
1226  */
1227 {
1228         int i;
1229
1230         if (se->hyp_ref_count > 0) {
1231                 stack->check_run_ok = 0;
1232         }
1233
1234         /* Reset 'hyp_ref_count' */
1235         se->hyp_ref_count = -1;
1236         for (i = 0; i < se->nr_nexts; i++) {
1237                 if ((se->edges + i)->flags & LLHYP_SEARCH) {
1238                         (se->edges + i)->flags &= ~LLHYP_SEARCH;
1239                         check_run(stack, (se->edges + i)->ptr);
1240                 }
1241         }
1242 }
1243
1244 #endif /* NOLOOPS */
1245
1246
1247 #if LL_ANSI_C
1248 static struct stack_elt *split(struct stack_elt *se)
1249 #else
1250 static struct stack_elt *split(se)
1251 struct stack_elt *se;
1252 #endif
1253
1254 /* This function splits of a NT in de stack, and returns a pointer to it */
1255 {
1256         struct stack_elt *new_stack;
1257         int i;
1258
1259 #ifdef DEBUG
1260         allocates++;
1261         if (allocates - deallocates > max_in_use) {
1262                 max_in_use = allocates - deallocates;
1263         }
1264 #endif
1265
1266         new_stack = (struct stack_elt *)Malloc(sizeof(struct stack_elt));
1267         new_stack->flags = 0;           /* Used by 'clear_gen_flags()' */
1268         new_stack->nr = se->nr;
1269         new_stack->ref_count = 0;       /* Copy is new top */
1270         new_stack->hyp_ref_count = -1;
1271         new_stack->matched = -1;
1272         new_stack->nr_nexts = se->nr_nexts;
1273
1274 #ifdef DEBUG
1275         edge_allocates++;
1276         if (edge_allocates - edge_deallocates > edge_max_in_use) {
1277                 edge_max_in_use = edge_allocates - edge_deallocates;
1278         }
1279 #endif
1280
1281         new_stack->edges = (struct edge *)
1282                 Malloc((unsigned)se->nr_nexts * sizeof(struct edge));
1283
1284         /* Copy gets the same successors as the original */
1285         memcpy((char *) new_stack->edges, (char *) se->edges,
1286                                         se->nr_nexts * sizeof(struct edge));
1287
1288         /* Each successor gets a new predecessor */
1289         for (i = 0; i < new_stack->nr_nexts; i++) {
1290                 (new_stack->edges + i)->ptr->ref_count++;
1291                 (new_stack->edges + i)->flags = 0;
1292         }
1293
1294         return new_stack;
1295 }
1296
1297
1298 #ifdef DEBUG
1299 #if LL_ANSI_C
1300 static void test(struct stacks *stack)
1301 #else
1302 static test(stack)
1303 struct stacks *stack;
1304 #endif
1305 {
1306         struct stack_elt *se;
1307         int i;
1308
1309         printf("STACKS:\n");
1310         for (i = 0; i < stack->nr_heads; i++) {
1311                 printf("%2d: ", i + 1);
1312                 if (*(stack->heads_buf + i) == (struct stack_elt *)0) {
1313                         printf("NIL\n");
1314                         continue;
1315                 }
1316                 se = *(stack->heads_buf + i);
1317                 dump_stack(se, 1);
1318                 clear_flags(se, PRINT_SEARCH);
1319         }
1320 }
1321
1322
1323 #if LL_ANSI_C
1324 static void dump_stack(struct stack_elt *se, int level)
1325 #else
1326 static dump_stack(se, level)
1327 struct stack_elt *se;
1328 int level;
1329 #endif
1330 {
1331         int i, j;
1332
1333         while (se->nr != LLEOSTACK) {
1334                 if ((se->flags & LLDUMMY) && (se->nr_nexts > 1)) {
1335                         printf("[%d] <%d,%d,%d>\n",
1336                                 se->nr, se->ref_count,
1337                                 se->hyp_ref_count,
1338                                 se->flags
1339                         );
1340                         for (j = 0; j < se->nr_nexts; j++) {
1341                                 for (i = 1; i <= level; i++) {
1342                                         printf("    ");
1343                                 }
1344                                 printf("%d: ", j + 1);
1345                                 if (!((se->edges + j)->flags & PRINT_SEARCH)) {
1346                                         printf(" (%d) ", (se->edges + j)->flags);
1347                                         (se->edges + j)->flags |= PRINT_SEARCH;
1348                                         dump_stack((se->edges+j)->ptr,level+1);
1349                                         /*clear_flags((se->edges+j)->ptr,PRINT_SEARCH);*/
1350                                 }
1351                                 else {
1352                                         printf("LOOP\n");
1353                                 }
1354                         }
1355                         return;
1356                 }
1357                 else {
1358                         if (se->flags & LLDUMMY) {
1359                                 printf("[%d] <%d,%d,%d> ",
1360                                         se->nr,se->ref_count,
1361                                         se->hyp_ref_count,
1362                                         se->flags
1363                                 );
1364                         }
1365                         else {
1366                                 printf("%d <%d,%d,%d> ",
1367                                         se->nr, se->ref_count,
1368                                         se->hyp_ref_count,
1369                                         se->flags
1370                                 );
1371                         }
1372                         if (!(se->edges->flags & PRINT_SEARCH)) {
1373                                 printf(" (%d) ", se->edges->flags);
1374                                 se->edges->flags |= PRINT_SEARCH;
1375                                 se = se->edges->ptr;
1376                         }
1377                         else {
1378                                 printf("LOOP\n");
1379                                 return;
1380                         }
1381                 }
1382         }
1383         printf("\n");
1384 }
1385 #endif
1386
1387
1388 #if LL_ANSI_C
1389 static void clear_flags(struct stack_elt *se, char flag)
1390 #else
1391 static clear_flags(se, flag)
1392 struct stack_elt *se;
1393 char flag;
1394 #endif
1395
1396 /* Clears edge flag 'flag' */
1397 {
1398         int i;
1399
1400         for (i = 0; i < se->nr_nexts; i++) {
1401                 if ((se->edges + i)->flags & flag) {
1402                         (se->edges + i)->flags &= ~flag; /* clear flag */
1403                         clear_flags((se->edges + i)->ptr, flag);
1404                 }
1405         }
1406 }
1407
1408 #if LL_ANSI_C
1409 static void clear_gen_flags(struct stacks *stack)
1410 #else
1411 static clear_gen_flags(stack)
1412 struct stacks *stack;
1413 #endif
1414
1415 {
1416         int i;
1417
1418         for (i = 0; i < stack->nr_visited; i++) {
1419                 (*(stack->visited_buf + i))->flags &= ~(LLGEN_SEARCH);
1420         }
1421
1422         stack->nr_visited = 0;
1423 }
1424
1425
1426 #if LL_ANSI_C
1427 static void match_heads(struct stacks *stack, int symb)
1428 #else
1429 static match_heads(stack, symb)
1430 struct stacks *stack;
1431 int symb;
1432 #endif
1433
1434 /* Match heads_buf against symb, leaving only matching heads,
1435  * whilst deallocating the non-matching stacks
1436  */
1437 {
1438         int i;
1439
1440         int old_nr_heads;
1441         struct stack_elt **old_heads_buf;
1442
1443
1444         /* Copy the 'old' heads */
1445         old_nr_heads = stack->nr_heads;
1446         old_heads_buf = stack->heads_buf;
1447
1448
1449         /* Set heads in stack to 0 */
1450         stack->nr_heads = 0;
1451         stack->heads_buf_size = 0;
1452         stack->heads_buf = (struct stack_elt **) 0;
1453
1454
1455         for (i = 0; i < old_nr_heads; i++) {
1456                 if ((*(old_heads_buf + i))->nr != symb) {
1457                         /* Does not match? */
1458                         (*(old_heads_buf + i))->ref_count--;
1459                         (*(old_heads_buf + i))->flags &= ~LLHEAD;
1460                         delete(stack, *(old_heads_buf + i));
1461                 }
1462                 else {  /* Matches */
1463                         if (stack->heads_buf_size == 0) {
1464                                 stack->heads_buf_size = LLHEADS_BUF_INCR;
1465                                 stack->heads_buf = (struct stack_elt **)
1466                                         Malloc((unsigned)stack->heads_buf_size *
1467                                                 sizeof(struct stack_elt *));
1468                         }
1469                         else if (stack->nr_heads == stack->heads_buf_size) {
1470                                 stack->heads_buf_size += LLHEADS_BUF_INCR;
1471                                 stack->heads_buf = (struct stack_elt **)
1472                                         Realloc((char *) stack->heads_buf,
1473                                                 (unsigned) stack->heads_buf_size *
1474                                                 sizeof(struct stack_elt *));
1475                         }
1476                         *(stack->heads_buf + stack->nr_heads) =
1477                                 *(old_heads_buf + i);
1478                         stack->nr_heads++;
1479                 }
1480         }
1481         free((char *) old_heads_buf);
1482 }
1483
1484
1485 #if LL_ANSI_C
1486 static void cleanup(struct stacks *stack)
1487 #else
1488 static cleanup(stack)
1489 struct stacks *stack;
1490 #endif
1491
1492 /* Deletes all elements in 'cleanup_buf()' */
1493 {
1494         int i;
1495
1496         for (i = 0; i < stack->nr_cleanups; i++) {
1497                 delete(stack, *(stack->cleanup_buf + i));
1498         }
1499
1500         stack->nr_cleanups = 0;
1501
1502 }
1503
1504
1505 #if LL_ANSI_C
1506 static void initialize(struct stacks *stack)
1507 #else
1508 static initialize(stack)
1509 struct stacks *stack;
1510 #endif
1511
1512 /* Initializes some variables and arrays */
1513 {
1514         int j;
1515
1516         stack->nr_heads = 0;
1517         stack->heads_buf_size = 0;
1518         stack->heads_buf = (struct stack_elt **)0;
1519
1520         stack->nr_cleanups = 0;
1521         stack->cleanup_buf_size = 0;
1522         stack->cleanup_buf = (struct stack_elt **)0;
1523
1524         stack->nr_visited = 0;
1525         stack->visited_buf_size = 0;
1526         stack->visited_buf = (struct stack_elt **)0;
1527
1528         for (j = 0; j < (LLNNONTERMINALS + 7)/8; j++) {
1529                 stack->r_rec[j] = (char) 0;
1530         }
1531
1532         for (j = 0; j < LLNNONTERMINALS; j++) {
1533                 stack->join_array[j] = (struct stack_elt *)0;
1534         }
1535
1536         for (j = 0; j < LLSETSIZE; j++) {
1537                 stack->exp_terminals[j] = 0;
1538         }
1539
1540         stack->start_seen = 0;
1541 }
1542
1543
1544 #if LL_ANSI_C
1545 static void calculate(struct stacks *stack, int l_ahead)
1546 #else
1547 static calculate(stack, l_ahead)
1548 struct stacks *stack;
1549 int l_ahead;
1550 #endif
1551
1552 /* This function finds all new heads and deletes the old heads */
1553 {
1554         int i;
1555         int old_nr_heads;
1556         struct stack_elt **old_heads_buf;
1557
1558         /* Make a copy of the heads */
1559         old_nr_heads = stack->nr_heads;
1560         old_heads_buf = stack->heads_buf;
1561
1562         stack->nr_heads = 0;
1563         stack->heads_buf = (struct stack_elt **) 0;
1564         stack->heads_buf_size = 0;
1565
1566         for (i = 0; i < old_nr_heads; i++) {
1567                 /* Find all new heads */
1568                 generate_heads(stack, *(old_heads_buf + i), l_ahead);
1569                 clear_gen_flags(stack);
1570
1571                 /* Old head can be deleted now */
1572                 (*(old_heads_buf + i))->ref_count--;
1573                 delete(stack, *(old_heads_buf + i));
1574         }
1575
1576
1577         cleanup(stack);
1578         free((char *) old_heads_buf);
1579
1580         /* Reinitialize some things */
1581         for (i = 0; i < (LLNNONTERMINALS + 7)/8; i++) {
1582                 stack->r_rec[i] = (char) 0;
1583         }
1584
1585         for (i = 0; i < LLNNONTERMINALS; i++) {
1586                 stack->join_array[i] = (struct stack_elt *)0;
1587         }
1588
1589         /* Delete all HEAD flags */
1590         for (i = 0; i < stack->nr_heads; i++) {
1591                 (*(stack->heads_buf + i))->flags &= ~LLHEAD;
1592         }
1593 }
1594
1595 #if LL_ANSI_C
1596 static void kill_stack(struct stacks *stack)
1597 #else
1598 static kill_stack(stack)
1599 struct stacks *stack;
1600 #endif
1601 {
1602         int i;
1603
1604         for (i = 0; i < stack->nr_heads; i++) {
1605                 (*(stack->heads_buf + i))->ref_count--;
1606                 delete(stack, *(stack->heads_buf + i));
1607         }
1608 }
1609
1610
1611
1612 #if LL_ANSI_C
1613 void LLnc_recover(void)
1614 #else
1615 LLnc_recover()
1616 #endif
1617
1618 /* This function contains the main loop for non correcting syntax error
1619  * recovery
1620  */
1621 {
1622         int j;
1623         int base_symb;
1624         struct stacks stack;
1625         int max_nr_heads;
1626         int max_nr_good_heads;
1627
1628         initialize(&stack);
1629         max_nr_heads = 0;
1630         max_nr_good_heads = 0;
1631
1632         /* Grammar has to be read only once */
1633         if (!grammar_read) {
1634                 build_grammar();
1635                 grammar_read = 1;
1636         }
1637
1638         /* Read first token */
1639         read_token();
1640         base_symb = LLsymb;
1641
1642         /* Check on end of file */
1643         if ((base_symb <= 0) || (base_symb == EOFILE)) {
1644
1645                 if ((nonterminals + LLstartsymb - LLFIRST_NT)->rule->empty != 1
1646                 ) {
1647                         LLsymb = EOFILE;
1648                         LLmessage(0);
1649                 }
1650
1651                 kill_stack(&stack);
1652                 return;
1653         }
1654
1655         /* Read look ahead token */
1656         read_token();
1657
1658         /* Now search applicable rules and starts the ball rolling */
1659         start_stack(&stack, base_symb, LLsymb);
1660
1661         if (stack.nr_heads > max_nr_heads) {
1662                 max_nr_heads = stack.nr_heads;
1663         }
1664
1665
1666         /* Only matching heads are needed */
1667         match_heads(&stack, LLsymb);
1668
1669         if (stack.nr_heads > max_nr_good_heads) {
1670                 max_nr_good_heads = stack.nr_heads;
1671         }
1672
1673
1674 #ifdef DEBUG
1675         test(&stack);
1676 #endif
1677
1678         /* Loop untill end of inputfile */
1679         while ((LLsymb > 0) && (LLsymb != EOFILE)) {
1680                 /* When entering the loop LLsymb always contains the
1681                  * symbol that was used as look_ahead to construct the stacks,
1682                  * or, if optimization is OFF, it contains the symbol with
1683                  * which the current heads have been matched
1684                  */
1685
1686                 if (stack.nr_heads == 0) {
1687                         /* No more heads left */
1688                         LLmessage(0);
1689
1690                         /* Restart the whole thing */
1691                         initialize(&stack);
1692
1693                         /* The look-ahead caused the empty stack, don't
1694                          * use it to start a new one !
1695                          */
1696
1697                         read_token();
1698                         base_symb = LLsymb;
1699
1700                         /* Check on end of file */
1701                         if ((base_symb <= 0) || (base_symb == EOFILE)) {
1702                                 if ((nonterminals + LLstartsymb - LLFIRST_NT)->rule->empty != 1) {
1703                                         LLsymb = EOFILE;
1704                                         LLmessage(0);
1705                                 }
1706                                 kill_stack(&stack);
1707                                 return;
1708                         }
1709
1710                         read_token();
1711
1712                         start_stack(&stack, base_symb, LLsymb);
1713
1714                         if (stack.nr_heads > max_nr_heads) {
1715                                 max_nr_heads = stack.nr_heads;
1716                         }
1717
1718
1719                         match_heads(&stack, LLsymb);
1720
1721                         if (stack.nr_heads > max_nr_good_heads) {
1722                                 max_nr_good_heads = stack.nr_heads;
1723                         }
1724
1725                         continue;
1726                 }
1727
1728
1729                 /* Normal case starts here */
1730                 stack.start_seen = 0;
1731
1732                 for (j = 0; j < LLSETSIZE; j++) {
1733                         stack.exp_terminals[j] = 0;
1734                 }
1735
1736                 /* Read next symbol */
1737                 read_token();
1738
1739                 /* Generate all new heads and delete old ones */
1740                 calculate(&stack, LLsymb);
1741
1742                 /* Leave out not wanted heads */
1743
1744                 if (stack.nr_heads > max_nr_heads) {
1745                         max_nr_heads = stack.nr_heads;
1746                 }
1747
1748                 match_heads(&stack, LLsymb);
1749
1750                 if (stack.nr_heads > max_nr_good_heads) {
1751                         max_nr_good_heads = stack.nr_heads;
1752                 }
1753
1754
1755
1756 #ifdef DEBUG
1757                 test(&stack);
1758 #endif
1759
1760         }
1761
1762         /* End of file reached, check if we have seen a start symbol */
1763         if (stack.start_seen == 1) return;
1764         else {
1765                 LLsymb = EOFILE;
1766                 LLmessage(0);
1767         }
1768
1769         kill_stack(&stack);
1770
1771 #ifdef DEBUG
1772         printf("Maximum number of heads: %d\n", max_nr_heads);
1773         printf("Maximum number of good heads: %d\n", max_nr_good_heads);
1774         printf("Number of node allocates: %d\n", allocates);
1775         printf("Number of node deallocates: %d\n", deallocates);
1776         printf("Maximum number of nodes in use: %8d\n", max_in_use);
1777         printf("Sizeof(struct stack_elt)              = %8d\n", sizeof(struct stack_elt));
1778         printf("                                        --------x\n");
1779         printf("                                        %8d\n", max_in_use * sizeof(
1780                                         struct stack_elt));
1781         printf("Number of edge allocates: %d\n", edge_allocates);
1782         printf("Number of edge deallocates: %d\n", edge_deallocates);
1783         printf("Maximum number of edges in use: %8d\n", edge_max_in_use);
1784         printf("Sizeof(struct edge)              = %8d\n", sizeof(struct edge));
1785         printf("                                   --------x\n");
1786         printf("                                   %8d\n", edge_max_in_use * sizeof(struct edge));
1787
1788 #endif
1789 }
1790