8 enum { PARSER_SHIFT, PARSER_REDUCE, PARSER_ACCEPT };
32 transition_t* transition_shift_new (gint state)
34 transition_t* transition;
35 transition = g_malloc (sizeof (transition_t));
36 transition->action = PARSER_SHIFT;
37 transition->state = state;
38 transition->left = NULL;
39 transition->right = NULL;
43 transition_t* transition_reduce_new (symbol_t* left, rule_t* right)
45 transition_t* transition;
46 transition = g_malloc (sizeof (transition_t));
47 transition->action = PARSER_REDUCE;
48 transition->state = 0;
49 transition->left = left;
50 transition->right = right;
54 transition_t* transition_accept_new ()
56 transition_t* transition;
57 transition = g_malloc (sizeof (transition_t));
58 transition->action = PARSER_ACCEPT;
59 transition->state = 0;
60 transition->left = NULL;
61 transition->right = NULL;
65 void transition_delete (transition_t* transition)
67 if (transition->left != NULL)
68 g_free (transition->left);
69 if (transition->right != NULL)
70 rule_delete (transition->right);
74 void lr1_push (lr1_t* parser, gint st, gpointer attrib)
77 state = g_malloc (sizeof (state_t));
79 state->attrib = attrib;
80 parser->stack = g_list_prepend (parser->stack, state);
83 static gboolean lr1_pop (lr1_t* parser, gpointer* attrib)
88 if ((l = g_list_first (parser->stack)) == NULL)
90 parser->stack = g_list_remove_link (l, l);
91 state = (state_t*) l->data;
93 *attrib = state->attrib;
100 lr1_t* lr1_new (nextcb cb, gpointer data)
105 parser = g_malloc (sizeof (lr1_t));
109 parser->stack = NULL;
110 parser->table = g_hash_table_new_full (g_direct_hash, g_direct_equal,
111 NULL, g_hash_table_destroy);
117 void lr1_delete (lr1_t* parser)
122 for (l = g_list_first (parser->stack); l != NULL; l = g_list_next (l))
127 g_list_free (parser->stack);
129 g_hash_table_destroy (parser->table);
135 gboolean lr1_add (lr1_t* parser, gint state, symbol_t* symbol,
136 transition_t* transition)
141 if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
142 NULL, (gpointer*) &table))
144 table = g_hash_table_new_full (symbol_hash, symbol_equal,
145 g_free, transition_delete);
146 g_hash_table_insert (parser->table, GINT_TO_POINTER(state), table);
149 if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
154 g_hash_table_insert (table, symbol, transition);
159 gboolean lr1_lookup (lr1_t* parser, gint state, symbol_t* symbol,
160 transition_t** transition)
166 if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
167 NULL, (gpointer*) &table))
172 if (!g_hash_table_lookup_extended (table, symbol,
173 NULL, (gpointer*) &trans))
185 static gpointer leaf_new (gpointer data)
187 return g_node_new (data);
190 static gpointer tree_new (rule_t* rule)
192 return g_node_new (rule);
195 static gpointer tree_add (gpointer tree, gpointer data)
197 return g_node_prepend (tree, data);
200 gpointer lr1_build (lr1_t* parser)
205 transition_t* transition;
209 symbol = g_malloc (sizeof (symbol_t));
211 symbol->value = parser->cb (parser->data, &attrib);
212 symbol->terminal = TRUE;
217 l = g_list_first (parser->stack);
218 state = (state_t*) l->data;
219 if (!lr1_lookup (parser, state->state, symbol, &transition))
223 printf ("State: %x, Symbol: %s\n", state->state,
224 g_quark_to_string (symbol->value));
227 if (transition->action == PARSER_SHIFT)
231 printf ("SHIFT: %x\n", transition->state);
233 lr1_push (parser, transition->state, leaf_new (attrib));
234 symbol->value = parser->cb (parser->data, &attrib);
235 symbol->terminal = TRUE;
238 else if (transition->action == PARSER_REDUCE)
246 attrib = tree_new (symbol_copy (transition->left));
248 for (l = grammar_get_rule (transition->right);
253 if (!lr1_pop (parser, &attr))
255 tree_add (attrib, attr);
258 l = g_list_first (parser->stack);
259 state = (state_t*) l->data;
262 printf ("REDUCE: back to %x, ", state->state);
265 lr1_lookup (parser, state->state, transition->left, &trans);
268 printf ("%x\n", trans->state);
271 lr1_push (parser, trans->state, attrib);
275 else if (transition->action == PARSER_ACCEPT)
280 l = g_list_first (parser->stack);
281 state = (state_t*) l->data;
282 return state->attrib;