1 files changed, 73 insertions, 0 deletions
diff --git a/src/slr_table.h b/src/slr_table.h
new file mode 100644
index 0000000..b1684f0
--- /dev/null
+++ b/src/slr_table.h
@@ -0,0 +1,73 @@
+#ifndef SLR_TABLE_H
+#define SLR_TABLE_H
+#include "grammar.h"
+#include "util.h"
+
+/* rule type */
+/* In general a rule is just an index into the list of rules.  But for
+   us the rules are grouped under non-terminals.  So a rule is
+   referred to by two numbers: one indexing the non-terminal and
+   another indexing the rule in the group corresponding to that
+   non-terminal. */
+typedef struct rule_s rule;
+
+/* item type */
+/* An item is a pair of a rule and a position in its right-hand side.
+   The position is the index in the list of terminals or
+   non-terminals, except when the length of the right-hand side is 0,
+   in which case the position is meaningless. */
+typedef struct item_s item;
+
+/* item set type */
+typedef struct item_set_s item_set;
+
+/* action type */
+typedef struct action_s action;
+
+/* action set type: it is just a normal list of actions */
+typedef List * action_set;
+
+/* slr table type */
+typedef struct slr_table_s slr_table;
+
+/* I decide to use hash tables to store SLR tables.  The reason is
+   that the input is represented as a long integer.  So if we use an
+   array to represent the input, the size would definitely be too
+   large.  As a consequence, I think a hash table would be a better
+   option.  Besides, this is also an opportunity to learn how to
+   implement hash tables.
+
+   I have considered some possibilities for the hashing function and
+   the collision resolving method.
+
+   The simplest hashing function is of course the identity function
+   composed with a omdulo operatoin, since our keys are simple
+   integers.
+
+   As to the collision resolution, I have considered to use the cuckoo
+   method, but I do not understand its mechanisms well enough to be
+   sure that it won't fail.  In addition, it seems that to use this
+   method one would need a k-independent hashing function, which is
+   too probabilistic to my taste.  Therefore, I chose to go with the
+   linear probing in the beginning to test if it works.  If ilnear
+   probing turns out to be insufficient for this use-case, I shall
+   then consider using another method. */
+
+/* TODO: the transitive closure to generate the list of states */
+BOOL closure(item_set *is, Grammar *g);
+
+/* first symbols */
+
+/* follow symbols */
+
+/* construct table */
+
+/* lookup table */
+
+/* destroy table */
+
+/* generate table */
+
+int space_holder(int a);
+
+#endif