art.c

編譯器的accent語法分析器

   sub [ last_item+1 ] = s;

#if TRACE
   print_item(last_item+1);
#endif

#if HASHING
   if (! hashed(d, b)) {
#if STATISTICS
      nosearch_h++;
#endif
#if BIGHASH
      DHITS[d] = thislist;
      BHITS[b] = thislist;
#endif
      last_item++; if (last_item==(ITEMLIMIT-2)) table_full();
      sethash(d, b);
   }
   else {
#endif
#if BIGHASH
      if (DHITS[d] == thislist) {
	 /* there may be already an item with code d */
	 if (BHITS[b] == thislist) {
	    /* there may be already an item with code b */
#if STATISTICS
	    search++;
#endif
	    SEARCH(d, b, l, s);
	 }
	 else
	 {
	    /* no search necessary: no item with code b entered til now */

#if STATISTICS
	    nosearch_b++;
#endif
	    BHITS[b] = thislist;
	    last_item++; if (last_item==(ITEMLIMIT-2)) table_full();
#if HASHING
	    sethash(d, b);
#endif
	 }
      }
      else {
	 /* no search necessary: no item with code d entered til now */

#if STATISTICS
	 nosearch++;
#endif
	 DHITS[d] = thislist;
	 BHITS[b] = thislist;
	 last_item++; if (last_item==(ITEMLIMIT-2)) table_full();
#if HASHING
	 sethash(d, b);
#endif
      }
#else
#if STATISTICS
      search++;
#endif
      SEARCH(d, b, l, s);
#endif
#if HASHING
   }
#endif

#if STATISTICS
   if (last_item > old) {
      itemsadded++;
   }
#endif
#if TRACE
   if (last_item <= old) {
      printf(" [already inserted]\n");
   }
#endif
}

/*----------------------------------------------------------------------------*/

PRIVATE kernel (prevlist)
   long prevlist;
/*
 * compute the kernel of the next item list
 * prevlist points to the previous list
 *
 * KERNEL[i] =
 *    {
 *       < N : alpha yygrammar[i] * beta, B,I,0 >
 *    |
 *       < N : alpha * yygrammar[i] beta, B,_,_ > is in IL[i-1] and has index I
 *    }
 */
{
   long i;
#if TRACE
   printf("kernel:\n");
#endif
   i = prevlist;
   while (dot[i]) {
      if (yygrammar[dot[i]] >= term_base ) {
         if (yygrammar[dot[i]] == sym) {
#if CHECKVIABLE
	    if (is_viable(dot[i]+1))
#endif
	    {
	       additem(dot[i]+1,back[i],i,0);
	    }
#if STATISTICS
	    GOOD++;
#endif
         }
	 else {
#if STATISTICS
	    BAD++;
#endif
	 }
      }
      i++;
   }
}

/*----------------------------------------------------------------------------*/

PRIVATE predictor (item)
   long item;
/*
 * predictor step for item 'item'
 *
 * PREDICTOR:
 * The dot is before a nonterm
 * add the rules for that nonterm (with the dot at the beginning)
 *
 * If
 *    < N : alpha * M beta, B,L,S >
 * is in IL
 * then add
 *    < M : * gamma, B',0,0 >
 * if there is not yet an an item with the first two components
 * and there is a rule N : gamma
 * B' is a reference to IL[i]
 */
{
   long ruleptr;
  
   ruleptr = yygrammar[dot[item]];
#if TRACE
   printf("predictor for item %d:\n", item);
#endif
   do {
      int old = last_item;

#if ! LOOKAHEAD
      /* (1) ORIGINAL VERSION */
      additem(ruleptr+1,thislist,0,0);
      if ((back[last_item]==thislist) && (last_item>old)) specialitemadded=1;
#else
      /* (2) IMPROVEMENT
	 add test: is current symbol (lookaheadsym)
	 in director set of that rule ?
      */
         if (lookup_dirset(ruleptr)) {
            additem(ruleptr+1,thislist,0,0);
	    if ((back[last_item]==thislist) && (last_item>old))
	       specialitemadded=1;
	 }
	 else {
#if TRACE
            printf("rejected by lookup_dirset(%d)\n", ruleptr);
#endif
#if STATISTICS
	    rules_rej++;
#endif
	 }
#endif

      ruleptr=yygrammar[ruleptr];

   } while (ruleptr);
}

/*----------------------------------------------------------------------------*/

PRIVATE completer (item)
   long item;
/*
 * completer step for item 'item'
 *
 * COMPLETER
 * The dot is at the end of a rule
 * add the item that triggered this rule to be included
 * where the dot is advanced after the nonterm
 *
 * If
 *    < M : gamma * , B,L,S >
 * is in CL (with index ITEM)
 * and there is an item
 *    < N : alpha * M beta, B',L',S' >
 * in the item list to which the back-pointer B refers (with index I)
 * then add
 *    < N : alpha M * beta, B',I,ITEM >
 * if there is not yet an item with the first two components
 */

{
   long lhs, old;
   register int i;
   int dot_i;
  
#if TRACE
	    printf("completer for item %d:\n", item);
#endif

   lhs=-yygrammar[dot[item]];
   i=back[item];

   /* loop over all items in earlier item list */
   dot[last_item+1] = 0; /* sentinel */
   while (dot_i = dot[i]) {

      if (yygrammar[/*dot[i]*/dot_i]==lhs) {

#if CHECKVIABLE
	 if (is_viable(/*dot[i]*/dot_i+1))
#endif
	 {
            old=last_item;
	    additem(/*dot[i]*/dot_i+1,back[i],i,item);
            dot[last_item+1] = 0; /* sentinel */
	    if ((back[i]==thislist) && (last_item>old)) specialitemadded=1;
	 }
      }

      i++;
   }
}

/*----------------------------------------------------------------------------*/

PRIVATE closure ()
/*
 * compute closure for the kernel of the current item list
 *
 * CLOSURE
 * apply PREDICTOR and COMPLETOR
 * as long as there are changes
 */
{
   long i;
#if TRACE
   printf("closure\n");
#endif
   do {
      specialitemadded=0;
      i=thislist;
      while (i<=last_item) {
         if (yygrammar[dot[i]]<0) completer(i);
         else if (yygrammar[dot[i]]<term_base) predictor(i);
         i++;
      }
#if TRACE
      if (specialitemadded) printf("next closure iteration\n");
#endif
  } while (specialitemadded);
}

/*----------------------------------------------------------------------------*/

PRIVATE initial_itemlist()
/*
 * compute initial item list
 * its kernel is given by the item
 *    YYSTART : * UserRoot EOF
 * for which the closure is computed
 *
 */
{
   
#if DYNAMICITEMS
   ITEMLIMIT = ITEMINCR;

   dot = (long *) malloc(ITEMLIMIT* sizeof(long));
   if (! dot) yymallocerror();
   back = (long *) malloc(ITEMLIMIT* sizeof(long));
   if (! back) yymallocerror();
   left = (long *) malloc(ITEMLIMIT* sizeof(long));
   if (! left) yymallocerror();
   sub = (long *) malloc(ITEMLIMIT* sizeof(long));
   if (! sub) yymallocerror();
#endif

#if STATISTICS
  itemlistcount = 0;
#endif
  thislist=1;
#if HASHING
  clearhash();
#endif
#if TRACE
  printf("initial itemlist:\n");
#endif
  additem(2,1,0,0); /*  YYSTART : * UserRoot EOF  */
  closure();
#if TRACE
  printf("end of initial itemlist\n");
#endif
  additem(0,0,0,0); /* terminator */
}

/*----------------------------------------------------------------------------*/

PRIVATE next_itemlist()
/*
 * compute next item list:
 * kernel and closure
 */
{
   long prevlist;

#if STATISTICS
   itemlistcount++;
#endif

#if HASHING
   clearhash();
#endif

   prevlist=thislist;
   thislist=last_item+1;

#if BIGHASH
   BHITS[thislist] = -1;
#endif

   kernel(prevlist);
   if (last_item<thislist) syntaxerror();
   closure();
#if TRACE
   printf("end of itemlist\n");
#endif
   additem(0,0,0,0);
}

/*----------------------------------------------------------------------------*/

PRIVATE itemlist_sequence()
/*
 * compute the sequence of item lists:
 * initial_itemlist
 * and then next_itemlist for each input token
 */
{
   last_item=0;
   initial_itemlist();
   do {
      readsym();
      next_itemlist();
   } while (sym != eofsym);
}

/*============================================================================*/
/* RETURN LEFTPARSE STEP BY STEP                                              */
/*============================================================================*/

/*
 * when the recognizer has terminated
 * leftpointers and sub pointers represent the parse tree
 * (starting with the item YYSTART : UserRoot EOF * )
 * the function 'yyselect' returns the rule number
 * one after each other in the order of a left derivation
 * as required by the tree walker implemented in yyactions.c
 * it uses a stack to keep track of items that need to be processed later
 */

#define STACKINCR 200
int STACKSIZE;
int *stack;
int stptr = 0;

/*----------------------------------------------------------------------------*/

PRIVATE push(n)
   int n;
/*
 * push item index n onto the stack
 */
{
   if (stptr == STACKSIZE-2) {
      STACKSIZE += STACKINCR;
      stack = (int *) realloc(stack, sizeof(int)*STACKSIZE);
      if (! stack) yymallocerror();
   }
   stack[stptr++] = n;
}

/*----------------------------------------------------------------------------*/

PRIVATE int pop()
/*
 * pop an item index from the stack and return the value
 */
{
   stptr--;
   return stack[stptr];
}

/*----------------------------------------------------------------------------*/

PRIVATE init_stack()
/*
 * push the initial item index on the stack
 * it represents the item
 *    YYSTART : UserRoot EOF *
 * i.e. the root of the derivation tree
 */
{ 
   STACKSIZE = STACKINCR;
   stack = (int *) malloc (sizeof(int) * STACKSIZE);
   if (! stack) yymallocerror();

   push(thislist);
}

/*----------------------------------------------------------------------------*/

PUBLIC int yyselect()
/*
 * return the next rule number (for the left-derivation)
 *
 * this function is called by the generated tree walker
 *
 * the stack always contains pointers to items that still must be processed
 * to produce a left-derivation
 * the top element must be processed first
 * if the dot appears inside a rule
 *    M : alpha N * beta
 * then the items representing the parse for beta are already on the stack
 * and the items representing alpha N must be pushed
 * they are represented by the sub pointer of the item
 * (corresponding to the parse for N)
 * and the leftpointer of the item
 * (corresponding to the parse for alpha)
 * if the item has the form
 *    M : gamma *
 * (i.e. the rule has been completed)
 * first the items representing gamma are pushed
 * then the rule number is returned
 * subsequent calls will process the items
 * representing gamma
 * 
 */
{
   int i;
   while (1) {
      i = pop();
      if (sub[i])  push(sub[i]);
      if (left[i]) push(left[i]);
      if (yygrammar[dot[i]] < 0 ) {
	    return yygrammar[dot[i]+1];
      }
   }
}

/*============================================================================*/
/* MAIN FUNCTION YYPARSE                                                      */
/*============================================================================*/

PUBLIC int yyparse()
/*
 * main function of the parser
 *
 * this function is called by the user's program
 *
 * compute the sequence of item lists
 * which implictely contain the parse tree
 * and then invokes the generated tree walker YYSTART
 * which in turn calls yyselect() to obtain the rule numbers
 * in the order of a left derivation
 */
{
#if BIGHASH
   init_DHITS();
#endif
   init_dirsets();
   lookaheadsym = yylex()+term_base;
   lookaheadpos = yypos;
   first_lexval();
   itemlist_sequence();

#if TRACE
   printf("END OF RECOGNIZER\n");
#endif

#if DYNAMICITEMS
   free(back);
#endif

#if PRINTTREE
   print_tree(left[thislist]);
#endif

#if WALK
   init_stack();
   init_lexelem();
   YYSTART();
#endif

#if DYNAMICITEMS
free(dot);
free(left);
free(sub);
#endif

#if STATISTICS
   print_statistics();
#endif

   return 0;
}

/*================================================================ THE END ===*/