temporary save point

Just to save some work.

1 files changed, 426 insertions, 22 deletions

diff --git a/src/grammar.c b/src/grammar.c
index 692e858..a24f9cb 100644
--- a/src/grammar.c
+++ b/src/grammar.c
@@ -1,3 +1,5 @@
+#include <string.h>
+#include "ht.h"
 #include "grammar.h"
 
 struct Rule_s {
@@ -5,12 +7,51 @@ struct Rule_s {
   List *right;                  /* a list of TNT's */
 };
 
-typedef struct {
+struct Rule_group_s {
   /* this group holds rules for this non-terminal */
   NT left;
   /* a list of lists of TNT's */
   List *rights;
-} Rule_group;
+};
+
+NT
+rg_left(CCR_MOD(Rule_group *) rg)
+{
+  return rg->left;
+}
+
+NUM
+rg_len(CCR_MOD(Rule_group *) rg)
+{
+  return list_length(rg->rights);
+}
+
+List *
+rg_right(CCR_MOD(Rule_group *) rg)
+{
+  return rg->rights;
+}
+
+List *
+rg_nth(CCR_MOD(Rule_group *) rg, NUM n)
+{
+  if (n < 0 || n >= list_length(rg->rights)) {
+    fleprintf("Out of bounds: %ld with len = %ld\n",
+              n, list_length(rg->rights));
+    return NULL;
+  }
+
+  return (List *) list_nth(rg->rights, n);
+}
+
+/* TODO: Add some statistic counts to assist the hash tables.  For
+   example, store the total number of terminals as an integer; then
+   the hash table can be hinted at initialization to contain that many
+   elements, which can reduce the number of time a hash table needs to
+   expand and re-insert all its keys, which then helps the
+   performance.  But this is not the top priority thing to do, and
+   might be postponed until a proto-type of the parser generator is
+   usable already. */
 
 /* rule_grps and names should have the same length */
 struct Grammar_s {
@@ -22,6 +63,7 @@ struct Grammar_s {
 
      To print them, first encode them into normal strings. */
   List *names;
+  /* TODO: Add an array of predicates. */
 };
 
 static void
@@ -80,14 +122,14 @@ print_rule_group(void *rule_grp)
 
   for (int i = 0; i < list_length(rg->rights); i++) {
     List *str = (List *) list_nth(rg->rights, i);
-    printf("Rule %u => ", rg->left);
+    printf("Rule %lu => ", rg->left);
     map_list_between(str, print_tnt, print_sep);
     printf("\n");
   }
 }
 
 TNT *
-new_tnt(int type, ...)
+new_tnt(TNT_TYPE type, ...)
 {
   va_list args;
   va_start(args, type);
@@ -95,8 +137,17 @@ new_tnt(int type, ...)
   TNT *result = MYALLOC(TNT, 1);
   result->type = type;
 
-  if (type) result->data.nt = va_arg(args, NT);
-  else result->data.t = va_arg(args, T);
+  switch (type) {
+  case TERMINAL:
+    result->data.t = va_arg(args, T);
+    break;
+  case NONTERMINAL:
+    result->data.nt = va_arg(args, NT);
+    break;
+  default:
+    result->data.pt = va_arg(args, PT);
+    break;
+  }
 
   va_end(args);
 
@@ -104,7 +155,7 @@ new_tnt(int type, ...)
 }
 
 Rule *
-new_rule(NT left, const List * const right)
+new_rule(NT left, CC_MOD(List *) right)
 {
   if (!right) return NULL;
 
@@ -125,7 +176,7 @@ new_grammar()
 
 /* We classify the rules into different rule groups. */
 BOOL
-build_grammar(Grammar *g, const List *rules, const List * const names)
+build_grammar(Grammar *g, const List *rules, CC_MOD(List *) names)
 {
   g->names = (List *) names;
 
@@ -135,7 +186,7 @@ build_grammar(Grammar *g, const List *rules, const List * const names)
   /* If a rule corresponds to a non-terminal not on the list, signal
      an error. */
   for (int i = 0; i < rule_len; i++) {
-    if (((Rule *) list_nth(rules, i))->left >= len) {
+    if ((NUM) (((Rule *) list_nth(rules, i))->left) >= len) {
       fleprintf("%d, Rule contains weird non-terminal\n", i);
       return 1;
     }
@@ -228,17 +279,25 @@ print_tnt(void *element)
 {
   TNT *tnt = (TNT*) element;
 
-  if (tnt->type)
-    printf("NT %u", tnt->data.nt);
-  else
-    printf("T %lu", tnt->data.t);
+  switch (tnt->type) {
+  case TERMINAL:
+    if (tnt->data.t == END_OF_INPUT) printf("T $");
+    else printf("T %lu", tnt->data.t);
+    break;
+  case NONTERMINAL:
+    printf("NT %lu", tnt->data.nt);
+    break;
+  default:
+    printf("PT %lu", tnt->data.pt);
+    break;
+  }
 }
 
 void
 print_rule(void *r)
 {
   Rule *rule = (Rule *) r;
-  printf("Rule: %u => ", rule->left);
+  printf("Rule: %lu => ", rule->left);
 
   map_list(rule->right, print_tnt);
 
@@ -246,8 +305,8 @@ print_rule(void *r)
 }
 
 NUM
-find_in_cpa_list(const NUM * const restrict string, NUM size,
-                 const List * const restrict list)
+find_in_cpa_list(CCR_MOD(NUM *) string, NUM size,
+                 CCR_MOD(List *) list)
 {
   NUM len = list_length(list), index = 0;
 
@@ -305,7 +364,7 @@ print_name(void *element)
 /* REVIEW: Print the names of non-terminals out, instead of printing
    the numbers? */
 void
-print_grammar(const Grammar * const g)
+print_grammar(CC_MOD(Grammar *) g)
 {
   printf("Printing a grammar:\n");
   map_list_between(g->names, print_name, print_sep);
@@ -335,13 +394,16 @@ new_tnt_string(char *format, int format_len, ...)
   for (int point = 0; point < format_len; point++) {
     switch (*(format+point)) {
     case 'n':
-      add_to_list(result, new_tnt(1, va_arg(args, NT)));
+      add_to_list(result, new_tnt(NONTERMINAL, va_arg(args, NT)));
       break;
     case 't':
-      add_to_list(result, new_tnt(0, va_arg(args, T)));
+      add_to_list(result, new_tnt(TERMINAL, va_arg(args, T)));
+      break;
+    case 'p':
+      add_to_list(result, new_tnt(PREDICATE, va_arg(args, PT)));
       break;
     default:
-      eprintf("Wront character: %c\n", *(format+point));
+      eprintf("Wrong character: %c\n", *(format+point));
       destroy_list(result, 1);
       va_end(args);
       return NULL;
@@ -403,9 +465,9 @@ destroy_grammar(void *grammar, int flag)
     map_list(g->rule_grps, destroy_rule_group_free_all);
   else if (flag == 2)
     map_list(g->rule_grps, destroy_rule_group_free_first);
-  
+
   destroy_list(g->rule_grps, 0);
-  
+
   /* CPA structure has no concept of freeing first.  So if flag is
      non-zero, we just free everything, and hope no disaster
      ensues. */
@@ -415,3 +477,345 @@ destroy_grammar(void *grammar, int flag)
 
   free(grammar);
 }
+
+Rule_group *
+grammar_rule(CCR_MOD(Grammar *) g, NT nt)
+{
+  if ((NUM) nt >= list_length(g->rule_grps)) {
+    fleprintf("Invalid nonterminal: %lu\n", nt);
+    return NULL;
+  }
+
+  return (Rule_group *) list_nth(g->rule_grps, nt);
+}
+
+NUM
+grammar_left_len(CCR_MOD(Grammar *)g)
+{
+  return list_length(g->names);
+}
+
+/* A transitive closure algorithm */
+void
+epsilon_nts(CC_MOD(Grammar *) g, BOOL * const restrict nts)
+{
+  NUM left_len = grammar_left_len(g);
+
+  memset(nts, 0, sizeof(BOOL) * left_len);
+
+  BOOL changed = 0, first_time = 1;
+
+  do {
+    changed = 0;
+
+    for (NUM i = 0; i < left_len; i++) {
+      /* If this non-terminal is already known to produce the empty
+         string, then we don't need to check it again. */
+      if (*(nts+i)) continue;
+
+      Rule_group *rg = grammar_rule(g, (NT) i);
+      NUM rg_length = rg_len(rg);
+
+      for (NUM j = 0; j < rg_length; j++) {
+        List *string = rg_nth(rg, j);
+        if (first_time && list_length(string) == 0) {
+          changed = 1;
+          *(nts+i) = 1;
+          break;
+        }
+
+        NUM string_len = list_length(string);
+
+        BOOL non_epsilon = 0;
+
+        for (NUM k = 0; k < string_len;) {
+          TNT *tnte = (TNT *) list_nth(string, k++);
+          if (tnte->type == NONTERMINAL && *(nts+tnte->data.nt))
+            continue;
+
+          non_epsilon = 1;
+          break;
+        }
+
+        if (!non_epsilon && !(*(nts+i))) {
+          changed = 1;
+          *(nts+i) = 1;
+        }
+      }
+    }
+
+    first_time = 0;
+  } while (changed);
+}
+
+BOOL
+nt_first(CC_MOD(Grammar *) g, CCR_MOD(BOOL *) nts,
+         ht *terminal_hts, ht *predicate_hts)
+{
+  NUM left_len = grammar_left_len(g);
+
+  BOOL changed = 0, first = 1;
+
+  ht *terminal_ht = NULL, *pred_ht = NULL;
+
+  /* lazy macro */
+
+#define BREAKOUT k = string_len
+
+  do {
+    changed = 0;
+
+    for (NUM i = 0; i < left_len; i++) {
+      Rule_group *rg = grammar_rule(g, (NT) i);
+      NUM rg_length = rg_len(rg);
+
+      for (NUM j = 0; j < rg_length;) {
+        List *string = rg_nth(rg, j++);
+        NUM string_len = list_length(string);
+        TNT *top = NULL;
+
+        for (NUM k = 0; k < string_len;) {
+          top = (TNT *) list_nth(string, k++);
+
+          switch (top->type) {
+          case TERMINAL:
+            if (first &&
+                ht_find(terminal_hts+i, top->data.t) == NULL) {
+              changed = 1;
+              ht_insert(terminal_hts+i, top->data.t, (void*)1);
+              BREAKOUT;
+            }
+            break;
+          case PREDICATE:
+            if (first &&
+                ht_find(predicate_hts+i, top->data.pt) == NULL) {
+              changed = 1;
+              ht_insert(predicate_hts+i, top->data.pt, (void*)1);
+              BREAKOUT;
+            }
+            break;
+          default:
+            terminal_ht = terminal_hts+top->data.nt;
+            pred_ht = predicate_hts+top->data.nt;
+            /* Add all entries to the corresponding hash table for the
+               nonterminal I.  Also record if new entries have been
+               found. */
+
+            NUM len = ht_size(terminal_ht);
+            NUM *keys = ht_keys(terminal_ht);
+
+            for (NUM ell = 0; ell < len;) {
+              NUM key = *(keys+ell++);
+              if (ht_find(terminal_hts+i, key) == NULL) {
+                changed = 1;
+                ht_insert(terminal_hts+i, key, (void*)1);
+              }
+            }
+
+            len = ht_size(pred_ht);
+            keys = ht_keys(pred_ht);
+
+            for (NUM ell = 0; ell < len;) {
+              NUM key = *(keys+ell++);
+              if (ht_find(predicate_hts+i, key) == NULL) {
+                changed = 1;
+                ht_insert(predicate_hts+i, key, (void*)1);
+              }
+            }
+
+            if (!(*(nts+(top->data.nt)))) BREAKOUT;
+            break;
+          }
+        }
+      }
+    }
+    first = 0;
+  } while (changed);
+
+#undef BREAKOUT
+
+  return 0;
+}
+
+BOOL
+tnt_first(CC_MOD(ht *) terminal_hts, CC_MOD(ht *) predicate_hts,
+          CCR_MOD(BOOL *) nts, NUM len, List *tnts,
+          ht * const restrict result_terminals,
+          ht * const restrict result_predicates)
+{
+  if (tnts == NULL) return 0;
+
+  NUM tnt_len = list_length(tnts);
+
+  if (!tnt_len) return 0;
+
+  NUM temp_len = 0, *keys = NULL;
+
+  TNT *top = NULL;
+
+  NT current = 0;
+
+  for (NUM i = 0; i < tnt_len; i++) {
+    top = (TNT *) list_nth(tnts, i);
+
+    switch (top->type) {
+    case TERMINAL:
+      ht_insert(result_terminals, top->data.t, (void *)1);
+      return 0;
+      break;
+    case PREDICATE:
+      ht_insert(result_predicates, top->data.pt, (void *)1);
+      return 0;
+      break;
+    default:
+      current = top->data.nt;
+
+      if (current >= (NT) len || current < 0) {
+        fleprintf("Wrong non-terminal: %ld>%ld\n", current, len);
+        return 1;
+      }
+
+      temp_len = ht_size(terminal_hts+current);
+      keys = ht_keys(terminal_hts+current);
+
+      for (NUM j = 0; j < temp_len;)
+        ht_insert(result_terminals, *(keys+j++), (void *)1);
+
+      temp_len = ht_size(predicate_hts+current);
+      keys = ht_keys(predicate_hts+current);
+
+      for (NUM j = 0; j < temp_len;)
+        ht_insert(result_predicates, *(keys+j++), (void *)1);
+
+      if (!(*(nts+current))) i = tnt_len;
+
+      break;
+    }
+  }
+
+  return 0;
+}
+
+BOOL
+nt_follow(CC_MOD(Grammar *) g, CCR_MOD(BOOL *) nts,
+          CC_MOD(ht *)terminal_hts, CC_MOD(ht *)predicate_hts,
+          ht * const restrict result_terminals,
+          ht * const restrict result_predicates)
+{
+  ht_insert(result_terminals, END_OF_INPUT, (void*)1);
+
+  NUM left_len = grammar_left_len(g);
+
+  BOOL changed = 0, first = 1;
+
+  NUM ht_len = 0, *keys = NULL;
+
+  List *temp = NULL;
+
+  do {
+    changed = 0;
+
+    for (NUM i = 0; i < left_len; i++) {
+      Rule_group *rg = grammar_rule(g, (NT) i);
+      NUM rg_length = rg_len(rg);
+
+      for (NUM j = 0; j < rg_length;) {
+        List *string = rg_nth(rg, j++);
+        NUM string_len = list_length(string);
+        TNT *top = NULL;
+
+        NUM rest_produce_epsilon = -1;
+
+        for (NUM ell = 0; ell < string_len; ell++) {
+          top = (TNT *) list_nth(string, ell);
+
+          switch (top->type) {
+          case NONTERMINAL:
+            if (!(*(nts+top->data.nt)))
+              rest_produce_epsilon = -1;
+            else if (rest_produce_epsilon < 0)
+              rest_produce_epsilon = ell;
+            break;
+          default:
+            rest_produce_epsilon = -1;
+            break;
+          }
+        }
+
+        for (NUM k = 0; k < string_len; k++) {
+          top = (TNT *) list_nth(string, k);
+
+          switch (top->type) {
+          case NONTERMINAL:
+            if (first && k+1<string_len) {
+              changed = 1;
+              temp = array_to_list
+                (list_array(string)+k+1, string_len-k-1);
+
+              if (temp == NULL) return 1;
+
+              if (tnt_first
+                  (terminal_hts, predicate_hts, nts, left_len,
+                   temp,
+                   result_terminals+top->data.nt,
+                   result_predicates+top->data.nt)) {
+                fleprintf("Error in generating the first set for %ld:"
+                          " i = %ld, j = %ld, k = %ld, len = %ld\n",
+                          top->data.nt, i, j, k, string_len);
+                free(temp);
+                return 1;
+              }
+
+              free(temp);
+            }
+
+            /* Test if the remaining thing produces the emtpy
+               string. */
+
+            if (k+1 == string_len ||
+                (rest_produce_epsilon >= 0 &&
+                 rest_produce_epsilon <= k))
+              goto add_to_follow;
+
+            break;
+
+          add_to_follow:
+
+            ht_len = ht_size(result_terminals+i);
+            keys = ht_keys(result_terminals+i);
+
+            for (NUM ell = 0; ell < ht_len;) {
+              NUM key = *(keys+ell++);
+              if (ht_find(result_terminals+top->data.nt,
+                          key) == NULL) {
+                changed = 1;
+                ht_insert(result_terminals+top->data.nt,
+                          key, (void*)1);
+              }
+            }
+
+            ht_len = ht_size(result_predicates+i);
+            keys = ht_keys(result_predicates+i);
+
+            for (NUM ell = 0; ell < ht_len;) {
+              NUM key = *(keys+ell++);
+              if (ht_find(result_predicates+top->data.nt,
+                          key) == NULL) {
+                changed = 1;
+                ht_insert(result_predicates+top->data.nt,
+                          key, (void*)1);
+              }
+            }
+
+            break;
+          default:
+            break;
+          }
+        }
+      }
+    }
+    first = 0;
+  } while (changed);
+
+  return 0;
+}