#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