1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#ifndef GLL_H
#define GLL_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. */
BOOL closure(item_set *is, Grammar *g);
/* first symbols */
/* follow symbols */
/* construct table */
/* lookup table */
/* destroy table */
/* generate table */
#endif
|
