art.c

編譯器的accent語法分析器

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

PRIVATE table_full()
/*
 * item table full
 */
{
#if DYNAMICITEMS
   ITEMLIMIT += ITEMINCR;

   dot = (long *) realloc(dot, ITEMLIMIT* sizeof(long));
   if (! dot) yymallocerror();
   back = (long *) realloc(back, ITEMLIMIT* sizeof(long));
   if (! back) yymallocerror();
   left = (long *) realloc(left, ITEMLIMIT* sizeof(long));
   if (! left) yymallocerror();
   sub = (long *) realloc(sub, ITEMLIMIT* sizeof(long));
   if (! sub) yymallocerror();
#else
   Abort("fatal error: item table overflow [increase ITEMLIMIT in art.c]\n");
#endif
}

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

PUBLIC yymallocerror()
{
   printf("running out of memory\n");
   exit(1);
}

/*============================================================================*/
/* SEARCH OPTIMISATION                                                        */
/*============================================================================*/

#if BIGHASH
PRIVATE init_DHITS()
/*
 * Initialise DHITS
 * (value must be different from possible values of 'thislist')
 */
{ 
   int i;

   for (i=1; i<=c_length; i++) {
      DHITS[i] = 0;
   }
}
#endif

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

#define HSIZE 1024

#define HASHCODE (b%8+d)%HSIZE

#if HASHING

int hash[HSIZE];
/*
 * hash table to speed up lookup-function
 * if an item with back pointer b and dot d is entered
 * into the current item list
 * an entry with a corresponding hash code is set
 */

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

#ifdef HASHING
PRIVATE int clearhash ()
/*
 * clear hash table
 */
{
   int i;

   for (i = 0; i<HSIZE; i++) hash[i] = 0;
}
#endif

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

PRIVATE int hashed(d, b)
   int d, b;
/*
 * true if there is an entry entry for item with dot d and backpointer b
 */
{
   return hash[HASHCODE];
}

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

PRIVATE sethash(d, b)
   int d, b;
/*
 * set entry for item with dot d and backpointer b
 */
{
   hash[HASHCODE] = 1;
}
#endif


/*============================================================================*/
/* TOKENS                                                                     */
/*============================================================================*/

PRIVATE readsym ()
/*
 * read next token
 * current token: 'sym'
 * following token: 'lookaheadsym'
 * extend the list of lexical values by calling
 * next_lexval() provided by 'yyactions.c'
 */
{
   long truepos;

   sym = lookaheadsym;
   truepos = lookaheadpos;

   yypos = truepos;
   if (lookaheadsym != 50000 /*EOF*/) {
      /* xxx
      printf("calling yylex()\n");
      */
      lookaheadsym = yylex()+term_base;
      /* xxx
      printf("back from yylex()\n");
      */
      lookaheadpos = yypos;
   }
   else /* printf("was already EOF\n") */ ;
   next_lexval();
   yypos = truepos;
   /* xxxxx */
   /*
   printf("readsym: sym = %d, lookaheadsym = %d\n", sym, lookaheadsym);
   */
}

/*============================================================================*/
/* GRAMMAR                                                                    */
/*============================================================================*/

PRIVATE int getprio(subptr)
   int subptr;

   /* subptr points to an item */
   /* return the prio of corresponding rule */
{
   int i;

   /* find end of rule */
   i = dot[subptr];
   while (yygrammar[i] > 0) i++;
   /* i points to the negative lhs encoding */
   i++;
   /* i now points to the rule number, this is also the index of the prio */

   return yyannotation[i];
}

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

PRIVATE int getmemberannotation(i)
   int i;

   /* i is the index of a member */
   /* return the annotation of the member before the dot */
{
   int grammarindex, annotation;

   grammarindex = dot[i]-1;
   annotation = yyannotation[grammarindex];
   return annotation;
}

/*============================================================================*/
/* AMBIGUITY RESOLUTION                                                       */
/*============================================================================*/

PRIVATE int test_for_cycle(subtree, container)
   int subtree;
   int container;
/*
 * return true if
 * the tree to which 'container' (a "subpointer" of an item) points
 * contains the tree to which 'subtree' (also a "subpointer") points
 */
{
   if (container < subtree) {
      /* an earlier item cannot refer a later one */ 
      return 0;
   }
   if (container == subtree) {
      return 1;
   }
   if (sub[container]) {
      if (test_for_cycle(subtree, sub[container]))
         return 1;
   }
   if (left[container]) {
      if (test_for_cycle(subtree, left[container]))
         return 1;
   }
   return 0;
}

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

PRIVATE combi_ambiguity(i, d, l, s)
   int i, d, l, s;
/*
 * The item with index i
 * and an item with dot d, leftpointer l, and subpointer s
 * introduce a combi ambiguity
 */
{
   if (left[i] != l) {

      /* Combi Ambiguity */

      int left1, left2, sub1, sub2, annotation,
	 selected_left, selected_sub;

#if TRACE
      printf("Combi Ambiguity left[%d] = %d, l = %d\n", i, left[i], l);
#endif

      left1 = left[i];
      sub1 = sub[i];

      left2 = l;
      sub2 = s;

      annotation = getmemberannotation(i);

      if (annotation == 1) {
	 /* %short */

	 if (left1 > left2) {
	    selected_left = left1;
	    selected_sub = sub1;
	 }
	 else {
	    selected_left = left2;
	    selected_sub = sub2;
	 }
      }
      else if (annotation == 2) {
	 /* %long */

	 if (left2 > left1) {
	    selected_left = left1;
	    selected_sub = sub1;
	 }
	 else {
	    selected_left = left2;
	    selected_sub = sub2;
	 }
      }
      else {
	 /* annotation == undef */


	 int old_sub, old_left;

	 printf("\n");
	 printf("GRAMMAR DEBUG INFORMATION\n");
	 printf("\n");
	 printf("Grammar ambiguity detected.\n");

	 {
	    int k;
	    k = dot[i];
	    while (yygrammar[k] > 0) k++;
	    printf("There are two different parses\n");
	    printf("for the beginning of ``%s'', alternative at ",
	       yyprintname(-yygrammar[k]));
	    print_coordinate(k+1);
	    printf(",\n");
	 }
	 printf("upto and containing ``%s'' at ", yyprintname(yygrammar[d-1]));
	 print_coordinate(d-1);
	 printf(".\n");

	 printf("\n");
	 printf("PARSE 1\n");
	 printf("-------\n");
	 printf("\n");
	 print_tree(i);

	 /* xxx
	 old_sub = sub[i];
	 old_left = left[i];
	 sub[i] = s;
	 left[i] = l;
	 */
	 printf("\n");
	 printf("PARSE 2\n");
	 printf("-------\n");
	 printf("\n");
	 /* xxx
	 print_tree(i);
	 */
	 print_tree(last_item+1);

	 printf("\n");
	 printf("For ``%s'' at ", yyprintname(yygrammar[d-1]));
	 print_coordinate(d-1);
	 printf(",\n");
	 if (left1 > left2) {
	    printf("use %%short annotation to select first parse,\n");
	    printf("use %%long annotation to select second parse.\n");
	 }
	 else {
	    printf("use %%long annotation to select first parse,\n");
	    printf("use %%short annotation to select second parse.\n");
	 }

	 /* xxx
	 sub[i] = old_sub;
	 left[i] = old_left;
	 */

	 printf("\nEND OF GRAMMAR DEBUG INFORMATION\n\n");

	 yyerror("source text uncovers unhandled grammar ambiguity");
	 exit(1);

	 selected_left = l;
	 selected_sub = s;
      }

      left[i] = selected_left;
      sub[i] = selected_sub;
   }
}

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

PRIVATE simple_ambiguity(i, d, l, s)
   int i, d, l, s;
/*
 * The item with index i
 * and an item with dot d, leftpointer l, and subpointer s
 * introduce a simple ambiguity
 */
{
   /* Simple Ambiguity */

   int sub1, sub2, rule1, rule2, prio1, prio2;

#if TRACE
   printf("simple amiguity\n");
   printf("i = %d\n", i);
   printf("last_item+1 = %d\n", last_item+1);
#endif
   sub1 = sub[i];
   sub2 = s;

   prio1 = getprio(sub1);
   prio2 = getprio(sub2);

   if (prio1 == -1 || prio2 == -1) {
      /* undefined prio */

      printf("\n");
      printf("GRAMMAR DEBUG INFORMATION\n");
      printf("\n");
      printf("Grammar ambiguity detected.\n");
      printf
	 ("Two different ``%s'' derivation trees for the same phrase.\n",
	 yyprintname(yygrammar[d-1]));

      printf("\n");
      printf("TREE 1\n");
      printf("------\n");
      printf("\n");
      print_tree(sub[i]);
      printf("\n");
      printf("TREE 2\n");
      printf("------\n");
      printf("\n");
      print_tree(s);
      printf("\n");

      if (test_for_cycle(s, sub[i])) {
	 /* not possible */
	 printf("Tree 1 contains tree 2 as subtree.\n");
	 printf
	    ("Use %%prio annotation to select the second tree.\n");
	 printf("An annotation selecting the first tree\n");
	 printf("would not resolve the ambiguity.\n");
      }
      else if (test_for_cycle(sub[i], s)) {
	 printf("Tree 2 contains tree 1 as subtree.\n");
	 printf
	    ("Use %%prio annotation to select the first tree.\n");
	 printf("An annotation selecting the second tree\n");
	 printf("would not resolve the ambiguity.\n");
      }
      else {
	 printf("Use %%prio annotation to select an alternative.\n");
      }

      printf("\nEND OF GRAMMAR DEBUG INFORMATION\n\n");

      yyerror("source text uncovers unhandled grammar ambiguity");
      exit(1);

   }

   else if (prio1 > prio2) {
#if TRACE
      printf("old value wins\n");
#endif
   }
   else {
#if TRACE
      printf("new value wins\n");
      printf("sub[%d] was %d\n", i, sub[i]);
      printf("sub[%d] becomes %d\n", i, s);
#endif

#if DYNAMICCYCLECHECK
      if (s >= i) {
	 if (test_for_cycle(i, s)) {
	    printf("\n");
	    printf("GRAMMAR DEBUG INFORMATION\n");
	    printf("\n");
	    printf("Annotation for ``%s'' allows cyclic derivation.\n",
	       yyprintname(yygrammar[d-1]));
	    printf("\nEND OF GRAMMAR DEBUG INFORMATION\n\n");
	    yyerror("source text uncovers unhandled grammar ambiguity");
	    exit(1);
	 }
      }
#endif
      sub[i] = s;
   }
}

/*============================================================================*/
/* EARLEY                                                                     */
/*============================================================================*/

PRIVATE SEARCH(d, b, l, s)
   long d, b, l, s;
/*
 * An item with dot d, backpointer b, leftpointer l, subpointer s
 * has been prliminary added to the current list at position
 * last_item+1 (sentinel)
 * if there is no other item with dot d and backpointer b
 * make this item permanent
 * otherwise, if the old item has a different backpointer/subpointer
 * then an ambiguity is detected
 * if the backpointer/subpointer is the same
 * the new item is already present
 */
{
   register long i;

   i = thislist;

   while ((dot[i]!=d)||(back[i]!=b)) i++;

   if (i==last_item+1) {
      last_item++;
      if (last_item==(ITEMLIMIT-2)) table_full();
#if HASHING
      sethash(d, b);
#endif
#if STATISTICS
      foundnew++;
#endif
   }
   else {
#if STATISTICS
      foundsame++;
#endif

#if DETECTAMBIGUITY
      if (left[i] != l)
	 combi_ambiguity(i, d, l, s);
      else if (sub[i] != s)
	 simple_ambiguity(i, d, l, s);

#endif

   }
}

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

PRIVATE additem ( d, b, l, s)
   long d, b, l, s;
/*
 * add an item with dot d, backpointer b, leftpointer l, and subpointer s
 * to the current item list
 * if there is already an item with dot d and backpointer b
 * then the grammar is ambigous (see 'SEARCH', which actually adds the item)
 *
 * hash optimization:
 * if there is no item with the same hash code for d and b
 * it is not neccessary to invoke SEARCH because the item is unique in the
 * current list
 */
{
#if STATISTICS || TRACE
   int old = last_item;
#endif

#if STATISTICS
   calls_additem++;
#endif

   /* sentinel */
   dot [ last_item+1 ] = d;
   back[ last_item+1 ] = b;
   left[ last_item+1 ] = l;