4 enum { PARSER_SHIFT, PARSER_REDUCE, PARSER_ACCEPT };
28 transition_t* transition_shift_new (gint state)
30 transition_t* transition;
31 transition = g_malloc (sizeof (transition_t));
32 transition->action = PARSER_SHIFT;
33 transition->state = state;
34 transition->left = NULL;
35 transition->right = NULL;
39 transition_t* transition_reduce_new (symbol_t* left, rule_t* right)
41 transition_t* transition;
42 transition = g_malloc (sizeof (transition_t));
43 transition->action = PARSER_REDUCE;
44 transition->state = 0;
45 transition->left = left;
46 transition->right = right;
50 transition_t* transition_accept_new ()
52 transition_t* transition;
53 transition = g_malloc (sizeof (transition_t));
54 transition->action = PARSER_ACCEPT;
55 transition->state = 0;
56 transition->left = NULL;
57 transition->right = NULL;
61 void transition_delete (transition_t* transition)
63 if (transition->left != NULL)
64 g_free (transition->left);
65 if (transition->right != NULL)
66 rule_delete (transition->right);
70 void lr1_push (lr1_t* parser, gint st, gpointer attrib)
73 state = g_malloc (sizeof (state_t));
75 state->attrib = attrib;
76 parser->stack = g_list_prepend (parser->stack, state);
79 static gboolean lr1_pop (lr1_t* parser, gpointer* attrib)
84 if ((l = g_list_first (parser->stack)) == NULL)
86 parser->stack = g_list_remove_link (l, l);
87 state = (state_t*) l->data;
89 *attrib = state->attrib;
96 lr1_t* lr1_new (nextcb cb, gpointer data)
101 parser = g_malloc (sizeof (lr1_t));
105 parser->stack = NULL;
106 parser->table = g_hash_table_new_full (g_direct_hash, g_direct_equal,
107 NULL, g_hash_table_destroy);
113 void lr1_delete (lr1_t* parser)
118 for (l = g_list_first (parser->stack); l != NULL; l = g_list_next (l))
123 g_list_free (parser->stack);
125 g_hash_table_destroy (parser->table);
131 gboolean lr1_add (lr1_t* parser, gint state, symbol_t* symbol,
132 transition_t* transition)
137 if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
138 NULL, (gpointer*) &table))
140 table = g_hash_table_new_full (symbol_hash, symbol_equal,
141 g_free, transition_delete);
142 g_hash_table_insert (parser->table, GINT_TO_POINTER(state), table);
145 if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
150 g_hash_table_insert (table, symbol, transition);
155 gboolean lr1_lookup (lr1_t* parser, gint state, symbol_t* symbol,
156 transition_t** transition)
162 if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
163 NULL, (gpointer*) &table))
168 if (!g_hash_table_lookup_extended (table, symbol,
169 NULL, (gpointer*) &trans))
181 static gpointer leaf_new (gpointer data)
183 return g_node_new (data);
186 static gpointer tree_new (rule_t* rule)
188 return g_node_new (rule);
191 static gpointer tree_add (gpointer tree, gpointer data)
193 return g_node_prepend (tree, data);
196 gpointer lr1_build (lr1_t* parser)
201 transition_t* transition;
205 symbol = g_malloc (sizeof (symbol_t));
207 symbol->value = parser->cb (parser->data, &attrib);
208 symbol->terminal = TRUE;
213 l = g_list_first (parser->stack);
214 state = (state_t*) l->data;
215 if (!lr1_lookup (parser, state->state, symbol, &transition))
218 if (transition->action == PARSER_SHIFT)
221 lr1_push (parser, transition->state, leaf_new (attrib));
222 symbol->value = parser->cb (parser->data, &attrib);
223 symbol->terminal = TRUE;
226 else if (transition->action == PARSER_REDUCE)
234 attrib = tree_new (symbol_copy (transition->left));
236 for (l = grammar_get_rule (transition->right);
238 l = g_list_previous (l))
241 if (!lr1_pop (parser, &attr))
243 tree_add (attrib, attr);
246 l = g_list_first (parser->stack);
247 state = (state_t*) l->data;
248 lr1_lookup (parser, state->state, transition->left, &trans);
249 lr1_push (parser, trans->state, attrib);
253 else if (transition->action == PARSER_ACCEPT)
255 l = g_list_first (parser->stack);
256 state = (state_t*) l->data;
257 return state->attrib;