save point: representation of grammar might be too rough.

The current representation of the grammar is the most primitive BNF.
This is the simplest to implement, but is difficult to cope with user
requirements.  Moreover, I find another paper describing the GLR
algorithm, so I need to think about the representation of the grammar
more.  In particular, I would like the generation of the grammar to be
incremental, so per chance its data type should be adapted
accordingly.

9 files changed, 252 insertions, 30 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index d38ef1b..ffb9a5c 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -1,8 +1,8 @@
 AM_CFLAGS = -Wall -Wextra
 
 noinst_LIBRARIES = libeps.a
-libeps_a_SOURCES = grammar.c list.c input.c \
-grammar.h list.h util.h input.h
+libeps_a_SOURCES = grammar.c list.c reader.c \
+grammar.h list.h util.h reader.h
 
 libeps_a_CFLAGS = $(AM_CFLAGS) --pedantic
 
@@ -19,12 +19,14 @@ CLEANFILES = TAGS
 
 # tests
 
-check_PROGRAMS = check_list check_grammar
+check_PROGRAMS = check_list check_grammar check_reader
 
 check_list_SOURCES = test/check_list.c list.c
 
 check_grammar_SOURCES = test/check_grammar.c list.c grammar.c
 
+check_reader_SOURCES = test/check_reader.c list.c grammar.c reader.c
+
 TESTS = $(check_PROGRAMS)
 
 AM_COLOR_TESTS = always
diff --git a/src/grammar.c b/src/grammar.c
index 9265ef5..fd38ac8 100644
--- a/src/grammar.c
+++ b/src/grammar.c
@@ -10,7 +10,14 @@ struct Rule_s {
   List *right;
 };
 
-TNT *new_tnt(int type, ...)
+struct Grammar_s {
+  List *rules;
+  /* a list of names of non-terminals */
+  List *names;
+};
+
+TNT *
+new_tnt(int type, ...)
 {
   va_list args;
   va_start(args, type);
@@ -26,10 +33,11 @@ TNT *new_tnt(int type, ...)
   return result;
 }
 
-Rule *new_rule(NT left, List *right)
+Rule *
+new_rule(NT left, List *right)
 {
   if (!right) return NULL;
-  
+
   Rule *rule = MYALLOC(Rule, 1);
 
   rule->left = left;
@@ -38,7 +46,22 @@ Rule *new_rule(NT left, List *right)
   return rule;
 }
 
-void print_tnt(void *element)
+Grammar *
+new_grammar()
+{
+  Grammar *g = MYALLOC(Grammar, 1);
+  return g;
+}
+
+void
+build_grammar(Grammar *g, List *rules, List *names)
+{
+  g->rules = rules;
+  g->names = names;
+}
+
+void
+print_tnt(void *element)
 {
   TNT *tnt = (TNT*) element;
 
@@ -48,35 +71,55 @@ void print_tnt(void *element)
     printf("T %lu, ", tnt->data.t);
 }
 
-void print_rule(void *r)
+void
+print_rule(void *r)
 {
-  Rule *rule = (Rule *)r;
-  printf("Rule: NT %u => ", rule->left);
-  
+  Rule *rule = (Rule *) r;
+  printf("Rule: %u => ", rule->left);
+
   map_list(rule->right, print_tnt);
 
   printf("\n");
 }
 
-void print_grammar(Grammar g)
+/* a local function pointer */
+void
+print_name(void *element)
+{
+  char *str = (char *) element;
+  printf("%s", str);
+}
+
+/* a local function pointer */
+void
+print_sep()
+{
+  printf(", ");
+}
+
+void
+print_grammar(Grammar *g)
 {
   printf("Printing a grammar:\n");
-  map_list(g, print_rule);
+  map_list_between(g->names, print_name, print_sep);
+  printf("\n");
+  map_list(g->rules, print_rule);
   printf("\n");
 }
 
-List *new_tnt_string(char *format, int format_len, ...)
+List *
+new_tnt_string(char *format, int format_len, ...)
 {
   /* FORMAT_LEN does not include the terminating null byte, so it
      should be > 0. */
-  
+
   if (format_len <= 0) return NULL;
-  
+
   List *result = new_list();
-  
+
   va_list args;
   va_start(args, format_len);
-  
+
   for (int point = 0; point < format_len; point++) {
     switch (*(format+point)) {
     case 'n':
@@ -99,8 +142,49 @@ List *new_tnt_string(char *format, int format_len, ...)
   return result;
 }
 
-void destroy_rule(Rule *rule)
+void
+destroy_rule(void *rule, int flag)
 {
-  destroy_list(rule->right, 1);
+  Rule * r = (Rule *) rule;
+  destroy_list(r->right, flag);
   free(rule);
 }
+
+void
+destroy_rule_and_free_all(void *rule)
+{
+  destroy_rule(rule, 1);
+}
+
+void
+destroy_rule_and_free_first(void *rule)
+{
+  destroy_rule(rule, 2);
+}
+
+void
+destroy_rule_no_free(void *rule)
+{
+  destroy_rule(rule, 0);
+}
+
+void
+destroy_grammar(void *grammar, int flag)
+{
+  Grammar *g = (Grammar *) grammar;
+
+  switch (flag) {
+  case 0:
+    map_list(g->rules, destroy_rule_no_free);
+    break;
+  case 1:
+    map_list(g->rules, destroy_rule_and_free_all);
+    break;
+  default:
+    map_list(g->rules, destroy_rule_and_free_first);
+    break;    
+  }
+
+  destroy_list(g->rules, 0);
+  destroy_list(g->names, flag);
+}
diff --git a/src/grammar.h b/src/grammar.h
index 2baec68..8353dd5 100644
--- a/src/grammar.h
+++ b/src/grammar.h
@@ -22,8 +22,14 @@ typedef unsigned NT;
 typedef struct TNT_s TNT;
 typedef struct Rule_s Rule;
 
-/* A grammar is a list of rules. */
-typedef List *Grammar;
+/* A grammar is more than a list of rules: it should include a
+   correspondance to associate the names of non-terminals with
+   unsigned integers.  Basically, this means it should hold a list of
+   strings as well. */
+typedef struct Grammar_s Grammar;
+
+/* G is expected to be allocated before this function. */
+void build_grammar(Grammar *g, List *rules, List *names);
 
 /* This accepts one and only one optional argument, which is of type
    either T or NT, depending on TYPE being 0 or not. */
@@ -32,12 +38,14 @@ TNT *new_tnt(int type, ...);
 /* For debugging purposes, we need to print out rules to examine their
    values. */
 
+void print_name(void *element);
+
 void print_tnt(void *element);
 
 void print_rule(void *r);
 
 /* This will generate errors if G is not a list of rules. */
-void print_grammar(Grammar g);
+void print_grammar(Grammar *g);
 
 /* constructors */
 
@@ -53,7 +61,13 @@ List *new_tnt_string(char *format, int format_len, ...);
    If RIGHT is NULL, NULL is returned. */
 Rule *new_rule(NT left, List *right);
 
+Grammar *new_grammar();
+
 /* destructors */
-void destroy_rule(Rule *rule);
+void destroy_rule(void *rule, int flag);
+void destroy_rule_and_free_all(void *rule);
+void destroy_rule_and_free_first(void *rule);
+void destroy_rule_no_free(void *rule);
+void destroy_grammar(void *grammar, int flag);
 
 #endif
diff --git a/src/list.c b/src/list.c
index 8c67a09..d823100 100644
--- a/src/list.c
+++ b/src/list.c
@@ -108,6 +108,16 @@ map_list(List *ls, acter f)
     f(*(ls->array+i));
 }
 
+H_ATTR
+void
+map_list_between(List *ls, acter f, doer d)
+{
+  for (NUM i = 0; i < ls->len; i++) {
+    f(*(ls->array+i));
+    if (i + 1 < ls->len) d();
+  }
+}
+
 void
 print_list(List *ls, printer prt)
 {
diff --git a/src/list.h b/src/list.h
index d774f96..b710aa2 100644
--- a/src/list.h
+++ b/src/list.h
@@ -28,8 +28,12 @@ typedef void (*printer)(void *);
 typedef printer acter;          /* a type that can act on list
                                    elements */
 
+typedef void (*doer)(void);
+
 void map_list(List *ls, acter f);
 
+void map_list_between(List *ls, acter f, doer d);
+
 void print_list(List *ls, printer prt);
 
 /* COPYER is expected to return NULL when it fails to copy. */
diff --git a/src/reader.c b/src/reader.c
index 018d9c7..4bbcf5a 100644
--- a/src/reader.c
+++ b/src/reader.c
@@ -1 +1,20 @@
-#include "input.h"
+#include "reader.h"
+
+struct Reader_s {
+  reader_func_t func;
+  List *args;                   /* the list of arguments; could be
+                                   NULL. */
+};
+
+void build_reader(Reader *reader, reader_func_t func, List *args)
+{
+  reader->func = func;
+  reader->args = args;
+}
+
+void destroy_reader(Reader *reader, int flag)
+{
+  destroy_list(reader->args, flag);
+  reader->args = NULL;
+  reader->func = NULL;
+}
diff --git a/src/reader.h b/src/reader.h
index 16a4ca6..77e7b84 100644
--- a/src/reader.h
+++ b/src/reader.h
@@ -3,6 +3,32 @@
 
 #include "grammar.h"
 
+/* The class of a general reader, which can read a grammar, either
+   from a file, or elsewhere, such as from an Emacs buffer, the
+   standard input, or even from some other places.
+
+   The only expectation, or requirement, of such a reader is to
+   provide a function with a variable number and type of arguments
+   which returns a grammar.  Then the package provides a function to
+   properly read a grammar, according to the specifications of the
+   reader. */
+
+typedef Grammar *(*reader_func_t)(List *args);
+
+typedef struct Reader_s Reader;
+
+/* contructor */
+
+/* Build a reader and assign to *reader.  It is expected to be
+   allocated before this function. */
+void build_reader(Reader *reader, reader_func_t func, List *args);
+
+/* destructor */
+
+/* Does not free READER.
+
+   FLAG is passed to destroy_list, which see. */
+void destroy_reader(Reader *reader, int flag);
 
 
 #endif
diff --git a/src/test/check_grammar.c b/src/test/check_grammar.c
index 1fe27dd..39f66ee 100644
--- a/src/test/check_grammar.c
+++ b/src/test/check_grammar.c
@@ -2,7 +2,8 @@
 #include <stdlib.h>
 #include "../grammar.h"
 
-int main(U_ATTR int argc, U_ATTR char **argv)
+int
+main(U_ATTR int argc, U_ATTR char **argv)
 {
   /* check new_tnt and print it */
   TNT *tnt = new_tnt(1, 12);
@@ -24,12 +25,52 @@ int main(U_ATTR int argc, U_ATTR char **argv)
   }
 
   /* check new_rule, print_rule, and destroy_rule. */
-  
+
   Rule *rule = new_rule(1, tnt_string);
-  
+
   print_rule(rule);
-    
-  destroy_rule(rule);
+
+  destroy_rule(rule, 1);
+
+  /* check build_grammar, print_grammar, and destroy_grammar */
+
+  List *rules = new_list();
+  List *names = new_list();
+
+
+  for (int i = 0; i < 3; i++) {
+    tnt_string = new_tnt_string("ntn", 3,
+                                (NT) 3*(i+1),
+                                (T) 3*(i+1)*(i+1),
+                                (NT) 3*(i+1)*(i+1)-2);
+
+    if (!tnt_string) {
+      eprintf("i = %d, cannot create tnt string\n", i);
+
+      map_list(rules, destroy_rule_and_free_all);
+
+      destroy_list(rules, 0);
+      destroy_list(names, 1);
+      return 1;
+    }
+
+    rule = new_rule(i, tnt_string);
+    add_to_list(rules, rule);
+
+    char *name = MYALLOC(char, 7);
+    snprintf(name, 7, "Rule %d", i);
+    add_to_list(names, name);
+  }
+
+  Grammar *g = new_grammar();
+
+  build_grammar(g, rules, names);
+
+  print_grammar(g);
+
+  destroy_grammar(g, 1);
+
+  free(g);
 
   return 0;
 }
diff --git a/src/test/check_reader.c b/src/test/check_reader.c
new file mode 100644
index 0000000..1d73b3f
--- /dev/null
+++ b/src/test/check_reader.c
@@ -0,0 +1,22 @@
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "../util.h"
+#include "../list.h"
+#include "../grammar.h"
+#include "../reader.h"
+
+/* The test of reading grammars should be postponed till later. */
+
+/* Grammar *
+ * read_grammar(List *args)
+ * {
+ * 
+ * } */
+
+
+int
+main(U_ATTR int argc, U_ATTR char **argv)
+{
+  return 77;
+}