5 enum { PARSER_SHIFT, PARSER_REDUCE, PARSER_ACCEPT };
29 transition_t* transition_shift_new (gint state)
31 transition_t* transition;
32 transition = g_malloc (sizeof (transition_t));
33 transition->action = PARSER_SHIFT;
34 transition->state = state;
35 transition->left = NULL;
36 transition->right = NULL;
40 transition_t* transition_reduce_new (symbol_t* left, rule_t* right)
42 transition_t* transition;
43 transition = g_malloc (sizeof (transition_t));
44 transition->action = PARSER_REDUCE;
45 transition->state = 0;
46 transition->left = left;
47 transition->right = right;
51 transition_t* transition_accept_new ()
53 transition_t* transition;
54 transition = g_malloc (sizeof (transition_t));
55 transition->action = PARSER_ACCEPT;
56 transition->state = 0;
57 transition->left = NULL;
58 transition->right = NULL;
62 void transition_delete (transition_t* transition)
64 if (transition->left != NULL)
65 g_free (transition->left);
66 if (transition->right != NULL)
67 rule_delete (transition->right);
71 static void lr1_push (lr1_t* parser, gint st, gpointer attrib)
74 state = g_malloc (sizeof (state_t));
76 state->attrib = attrib;
77 parser->stack = g_list_prepend (parser->stack, state);
80 static gboolean lr1_pop (lr1_t* parser, gpointer* attrib)
85 if ((l = g_list_first (parser->stack)) == NULL)
87 parser->stack = g_list_remove_link (l, l);
88 state = (state_t*) l->data;
90 *attrib = state->attrib;
97 lr1_t* lr1_new (nextcb cb, gpointer data)
102 parser = g_malloc (sizeof (lr1_t));
106 parser->stack = NULL;
107 lr1_push (parser, 0, NULL);
108 parser->table = g_hash_table_new_full (g_direct_hash, g_direct_equal,
109 NULL, g_hash_table_destroy);
115 void lr1_delete (lr1_t* parser)
120 for (l = g_list_first (parser->stack); l != NULL; l = g_list_next (l))
125 g_list_free (parser->stack);
127 g_hash_table_destroy (parser->table);
133 gboolean lr1_add (lr1_t* parser, gint state, symbol_t* symbol,
134 transition_t* transition)
139 if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
140 NULL, (gpointer*) &table))
142 table = g_hash_table_new_full (symbol_hash, symbol_equal,
143 g_free, transition_delete);
144 g_hash_table_insert (parser->table, GINT_TO_POINTER(state), table);
147 if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
152 g_hash_table_insert (table, symbol, transition);
157 gboolean lr1_lookup (lr1_t* parser, gint state, symbol_t* symbol,
158 transition_t** transition)
164 if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
165 NULL, (gpointer*) &table))
170 if (!g_hash_table_lookup_extended (table, symbol,
171 NULL, (gpointer*) &trans))
183 static gpointer leaf_new (gpointer data)
185 return g_node_new (data);
188 static gpointer tree_new (rule_t* rule)
190 return g_node_new (rule);
193 static gpointer tree_add (gpointer tree, gpointer data)
195 return g_node_prepend (tree, data);
198 gpointer lr1_build (lr1_t* parser)
203 transition_t* transition;
207 symbol = g_malloc (sizeof (symbol_t));
209 symbol->value = parser->cb (parser->data, &attrib);
210 symbol->terminal = TRUE;
215 l = g_list_first (parser->stack);
216 state = (state_t*) l->data;
217 if (!lr1_lookup (parser, state->state, symbol, &transition))
220 if (transition->action == PARSER_SHIFT)
223 lr1_push (parser, transition->state, leaf_new (attrib));
224 symbol->value = parser->cb (parser->data, &attrib);
225 symbol->terminal = TRUE;
228 else if (transition->action == PARSER_REDUCE)
236 attrib = tree_new (symbol_copy (transition->left));
238 for (l = grammar_get_rule (transition->right);
243 if (!lr1_pop (parser, &attr))
245 tree_add (attrib, attr);
248 l = g_list_first (parser->stack);
249 state = (state_t*) l->data;
250 lr1_lookup (parser, state->state, transition->left, &trans);
251 lr1_push (parser, trans->state, attrib);
255 else if (transition->action == PARSER_ACCEPT)
257 l = g_list_first (parser->stack);
258 state = (state_t*) l->data;
259 return state->attrib;