fix errorsHEADmaster

There are multiple subtle errors in the previous version, both in the
codes and in the description of the BNF format.  This version should
fix some problems now.

This version can successfully parse the grammar of its own grammar
format, which is quite nice.  See test/check_reader.c for parsing this
format.

1 files changed, 105 insertions, 26 deletions

diff --git a/src/cnp.c b/src/cnp.c
index 3c76f52..b28f967 100644
--- a/src/cnp.c
+++ b/src/cnp.c
@@ -1,6 +1,21 @@
+#include <time.h>
 #include <string.h>
 #include "cnp.h"
 
+#define TITO struct timespec tic, toc
+
+#define TIC do {                                \
+    clock_gettime(CLOCK_MONOTONIC_RAW, &tic);   \
+  } while (0)
+
+#define TOC do {                                \
+    clock_gettime(CLOCK_MONOTONIC_RAW, &toc);   \
+    printf("\nTotal time = %f seconds\n",       \
+           (toc.tv_nsec - tic.tv_nsec) /        \
+           1000000000.0 +                       \
+           toc.tv_sec - tic.tv_sec);            \
+  } while (0)
+
 struct Environment_s {
   grammar_info *gi;
   /* RESULT_TS and RESULT_PS are temporary arrays used in the
@@ -32,7 +47,6 @@ nt_add(Environment *env, NUM X, NUM j)
   for (NUM i = 0; i < rg_len(RG); i++) {
     BOOL result =
       test_select(env, *(env->string+j), X, rg_nth(RG, i));
-    /* fleprintf("i = %ld, after test select\n", i); */
 
     for (NUM k = 0; k < grammar_left_len(GI->g); k++) {
       ht_reset(env->result_ts+k, DELETE_KEY);
@@ -42,12 +56,10 @@ nt_add(Environment *env, NUM X, NUM j)
     if (env->error) break;
 
     if (result) {
-      /* fleprintf("i = %ld, j = %ld\n", i, j); */
       env->error =
         desc_add(env->pr, env->pu, j,
                  (pair4) { .x = X, .y = i, .z = 0, .u = j });
 
-      /* fleprintf("env->error = %d\n", env->error); */
       /* print_procr(env->pr); */
       /* fleprintf("pr len = %ld\n", env->pr->len);
        * fleprintf("pr ini = %d\n", (env->pr->array)->initialized); */
@@ -73,22 +85,40 @@ test_select(Environment *env, NUM b, NUM X, CCR_MOD(List *) tnts)
   ht *result_ts = env->result_ts;
   ht *result_ps = env->result_ps;
 
+  ht_reset(result_ts, DELETE_KEY);
+  ht_reset(result_ps, DELETE_KEY);
+  
   if (tnt_first(gi->pts, gi->pps, gi->nts, grammar_left_len(gi->g),
                 tnts, result_ts, result_ps)) {
     fleprintf0("Fail to find the first set of the TNT string.\n");
     goto cleanup;
   }
+  /* if (X == 3) {
+   *   fleprintf0("for empty the first has ");
+   *   for (NUM i = 0; i < ht_size(result_ts); i++) {
+   *     eprintf("%ld", **((NUM **)ht_keys(result_ts)+i));
+   *     if (i+1<ht_size(result_ts)) eprintf(", ");
+   *     else eprintf("\n");
+   *   }
+   *   if (list_length(tnts) && ((TNT *)list_nth(tnts, 0))->data.nt == 1)
+   *     fleprintf("first of tnts is %ld\n",
+   *               ((TNT *)list_nth(tnts, 0))->data.nt);
+   * } */
 
   if (ht_find(result_ts, &b) != NULL) {
     result = 1;
+
+#ifdef DEBUG
+    fleprintf("test succeeds against %ld\n", b);
+#endif
+
     goto success;
   }
-
+  /* fleprintf("hi, size = %ld\n", ht_size(result_ps)); */
   for (NUM i = 0; i < ht_size(result_ps); i++) {
-    PTD *ptdp = grammar_ptd(gi->g, **((PT **) ht_keys(result_ps+i)));
+    PTD *ptdp = grammar_ptd(gi->g, **((PT **) ht_keys(result_ps)+i));
 
     if (ptd_run(ptdp, b)) {
-      /* fleprintf("i = %ld\n", i); */
       result = 1;
       goto success;
     }
@@ -104,24 +134,27 @@ test_select(Environment *env, NUM b, NUM X, CCR_MOD(List *) tnts)
       goto success;
       break;
     default:
-      if (!(gi->nts+TOP->data.nt)) goto success;
+      if (!(*(gi->nts+(TOP->data.nt)))) goto success;
       break;
     }
 
 #undef TOP
 
   }
-
+  /* fleprintf("hi %ld\n", X); */
   if (ht_find(gi->sts+X, &b) != NULL) {
     result = 1;
+
+#ifdef DEBUG
+    fleprintf("followed by %ld\n", b);
+#endif
+
     goto success;
   }
 
   for (NUM i = 0; i < ht_size(gi->sps+X); i++) {
-    PTD *ptdp = grammar_ptd(gi->g, **((PT **) ht_keys(gi->sps+X)));
-    /* fleprintf("i = %ld\n", i); */
+    PTD *ptdp = grammar_ptd(gi->g, **((PT **) ht_keys(gi->sps+X)+i));
     if (ptd_run(ptdp, b)) {
-      /* fleprintf("i = %ld\n", i); */
       result = 1;
       goto success;
     }
@@ -154,9 +187,11 @@ rtn_internal(pair6 label)
                   label.v, label.w
                 }))) return;
 
-  /* fleprintf("added descriptor (%ld, %ld, %ld, %ld, %ld)\n",
-   *           label.z, label.u, label.v, label.w,
-   *           rtn_internal_num); */
+#ifdef DEBUG
+    fleprintf("added descriptor (%ld, %ld, %ld, %ld, %ld)\n",
+              label.z, label.u, label.v, label.w,
+              rtn_internal_num);
+#endif
 
   if ((rtn_internal_env->error =
        bsr_add(rtn_internal_env->gi->g,
@@ -175,9 +210,11 @@ rtn(Environment *env, NUM X, NUM k, NUM j)
   pair3 label = (pair3) { .x = X, .y = k, .z = j };
   pair2 label2 = (pair2) { .x = X, .y = k };
 
-  if (spa_belong(env->spap, label)) return;
+#ifdef DEBUG
+  fleprintf("encounter %ld, %ld, %ld\n", X, k, j);
+#endif
 
-  /* fleprintf0("new spa\n"); */
+  if (spa_belong(env->spap, label)) return;
 
   if ((env->error = spa_insert(env->spap, label))) return;
 
@@ -267,7 +304,12 @@ cnp_call(Environment *env, pair3 label, NUM i, NUM j)
   }
 
   NUM X = (NUM) xtnt->data.nt;
-  /* fleprintf("X = %ld, j = %ld\n", X, j); */
+
+#ifdef DEBUG
+  fleprintf0("X = ");
+  eprint_name(list_nth(grammar_names(env->gi->g), X));
+  eprintf(", j = %ld\n", j);
+#endif
 
   pair2 node = (pair2) { .x = X, .y = j };
   pair4 u = (pair4)
@@ -279,11 +321,21 @@ cnp_call(Environment *env, pair3 label, NUM i, NUM j)
     };
 
   if (!(crf_find_node(env->crfp, node))) {
+
+#ifdef DEBUG
+    fleprintf("adding node (%ld, %ld)\n", X, j);
+#endif
+
     if (crf_add_node(env->crfp, node)) {
       fleprintf0("fail to add node to crf\n");
       goto cleanup;
     }
 
+#ifdef DEBUG
+    fleprintf("adding edge to (%ld, %ld, %ld, %ld)\n",
+              u.x, u.y, u.z, u.u);
+#endif
+
     if (crf_add_edge(env->crfp, node, u)) {
       fleprintf0("fail to add edge to crf\n");
       goto cleanup;
@@ -292,11 +344,14 @@ cnp_call(Environment *env, pair3 label, NUM i, NUM j)
     /* errors will be stored in ENV, so we simply return */
     nt_add(env, X, j);
 
-    /* fleprintf("X = %ld, j = %ld\n", X, j); */
-
     return;
   }
 
+#ifdef DEBUG
+    fleprintf("adding edge to (%ld, %ld, %ld, %ld)\n",
+              u.x, u.y, u.z, u.u);
+#endif
+
   if (!(crf_find_edge(env->crfp, node, u))) {
     if (crf_add_edge(env->crfp, node, u)) {
       fleprintf0("fail to add edge to crf\n");
@@ -378,11 +433,13 @@ env_follow_p(CCR_MOD(Environment *) env, NUM X, NUM t)
 
   for (NUM i = 0; i < ht_size(env->gi->sps+X); i++) {
     PTD *ptdp = grammar_ptd(env->gi->g,
-                            **((PT **) ht_keys(env->gi->sps+X)));
+                            **((PT **) ht_keys(env->gi->sps+X)+i));
     if (ptd_run(ptdp, t)) return 1;
   }
 
-  /* fleprintf("X = %ld, t = %ld\n", X, t); */
+#ifdef DEBUG
+  fleprintf("X = %ld, t = %ld\n", X, t);
+#endif
 
   return 0;
 }
@@ -679,6 +736,9 @@ cnp_parse(Grammar *g, str *string)
 
       if (env_follow_p(env, current_prodecor->x,
                        *(num_string+current_grade))) {
+#ifdef DEBUG
+        fleprintf0("returning from an empty rule\n");
+#endif
         rtn(env, current_prodecor->x,
             current_prodecor->u, current_grade);
       }
@@ -693,6 +753,9 @@ cnp_parse(Grammar *g, str *string)
     if (current_prodecor->z == list_length(right)) {
       if (env_follow_p(env, current_prodecor->x,
                        *(num_string+current_grade))) {
+#ifdef DEBUG
+        fleprintf0("returning from the end\n");
+#endif
         rtn(env, current_prodecor->x,
             current_prodecor->u, current_grade);
       }
@@ -744,7 +807,17 @@ cnp_parse(Grammar *g, str *string)
            ((TNT *) list_nth(right, current_prodecor->z-1))->type ==
            PREDICATE) {
 #ifdef DEBUG
-      fleprintf0("found terminal\n");
+      if (((TNT *) list_nth(right, current_prodecor->z-1))->type ==
+          TERMINAL)
+        fleprintf("found terminal %ld\n",
+                  ((TNT *)
+                   list_nth
+                   (right, current_prodecor->z-1))->data.t);
+      else
+        fleprintf("found predicate terminal %ld\n",
+                  ((TNT *)
+                   list_nth
+                   (right, current_prodecor->z-1))->data.pt);
 #endif
       /* add to BSR set */
       errorp =
@@ -771,8 +844,12 @@ cnp_parse(Grammar *g, str *string)
 
         goto continue_label;
       }
+
 #ifdef DEBUG
       fleprintf0("terminal not at the end\n");
+      fleprintf("testing X = %ld, z = %ld, input = %ld\n",
+                current_prodecor->x, current_prodecor->z,
+                *(num_string+current_grade));
 #endif
       /* else test select */
       tnts =
@@ -818,10 +895,12 @@ cnp_parse(Grammar *g, str *string)
         .z = current_prodecor->z
       }, current_prodecor->u, current_grade);
 
-    /* fleprintf("after call { %ld, %ld, %ld, %ld, %ld }\n",
-     *           current_prodecor->x, current_prodecor->y,
-     *           current_prodecor->z, current_prodecor->u,
-     *           current_grade); */
+#ifdef DEBUG
+    fleprintf("after call { %ld, %ld, %ld, %ld, %ld }\n",
+              current_prodecor->x, current_prodecor->y,
+              current_prodecor->z, current_prodecor->u,
+              current_grade);
+#endif
 
   continue_label: