2 * Copyright (C) 2005 Thadeu Lima de Souza Cascardo <cascardo@holoscopio.com>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License along
15 * with this program; if not, write to the Free Software Foundation, Inc.,
16 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
28 enum { PARSER_SHIFT, PARSER_REDUCE, PARSER_ACCEPT };
52 transition_t* transition_shift_new (gint state)
54 transition_t* transition;
55 transition = g_malloc (sizeof (transition_t));
56 transition->action = PARSER_SHIFT;
57 transition->state = state;
58 transition->left = NULL;
59 transition->right = NULL;
63 transition_t* transition_reduce_new (symbol_t* left, rule_t* right)
65 transition_t* transition;
66 transition = g_malloc (sizeof (transition_t));
67 transition->action = PARSER_REDUCE;
68 transition->state = 0;
69 transition->left = left;
70 transition->right = right;
74 transition_t* transition_accept_new ()
76 transition_t* transition;
77 transition = g_malloc (sizeof (transition_t));
78 transition->action = PARSER_ACCEPT;
79 transition->state = 0;
80 transition->left = NULL;
81 transition->right = NULL;
85 void transition_delete (transition_t* transition)
87 if (transition->left != NULL)
88 g_free (transition->left);
89 if (transition->right != NULL)
90 rule_delete (transition->right);
94 void lr1_push (lr1_t* parser, gint st, gpointer attrib)
97 state = g_malloc (sizeof (state_t));
99 state->attrib = attrib;
100 parser->stack = g_list_prepend (parser->stack, state);
103 static gboolean lr1_pop (lr1_t* parser, gpointer* attrib)
108 if ((l = g_list_first (parser->stack)) == NULL)
110 parser->stack = g_list_remove_link (l, l);
111 state = (state_t*) l->data;
113 *attrib = state->attrib;
120 lr1_t* lr1_new (nextcb cb, gpointer data)
125 parser = g_malloc (sizeof (lr1_t));
129 parser->stack = NULL;
130 parser->table = g_hash_table_new_full (g_direct_hash, g_direct_equal,
131 NULL, g_hash_table_destroy);
137 void lr1_delete (lr1_t* parser)
142 for (l = g_list_first (parser->stack); l != NULL; l = g_list_next (l))
147 g_list_free (parser->stack);
149 g_hash_table_destroy (parser->table);
155 gboolean lr1_add (lr1_t* parser, gint state, symbol_t* symbol,
156 transition_t* transition)
161 if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
162 NULL, (gpointer*) &table))
164 table = g_hash_table_new_full (symbol_hash, symbol_equal,
165 g_free, transition_delete);
166 g_hash_table_insert (parser->table, GINT_TO_POINTER(state), table);
169 if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
174 g_hash_table_insert (table, symbol, transition);
179 gboolean lr1_lookup (lr1_t* parser, gint state, symbol_t* symbol,
180 transition_t** transition)
186 if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
187 NULL, (gpointer*) &table))
192 if (!g_hash_table_lookup_extended (table, symbol,
193 NULL, (gpointer*) &trans))
205 static gpointer leaf_new (gpointer data)
207 return g_node_new (data);
210 static gpointer tree_new (rule_t* rule)
212 return g_node_new (rule);
215 static gpointer tree_add (gpointer tree, gpointer data)
217 return g_node_prepend (tree, data);
220 gpointer lr1_build (lr1_t* parser)
225 transition_t* transition;
229 symbol = g_malloc (sizeof (symbol_t));
231 symbol->value = parser->cb (parser->data, &attrib);
232 symbol->terminal = TRUE;
237 l = g_list_first (parser->stack);
238 state = (state_t*) l->data;
239 if (!lr1_lookup (parser, state->state, symbol, &transition))
243 printf ("State: %x, Symbol: %s\n", state->state,
244 g_quark_to_string (symbol->value));
247 if (transition->action == PARSER_SHIFT)
251 printf ("SHIFT: %x\n", transition->state);
253 lr1_push (parser, transition->state, leaf_new (attrib));
254 symbol->value = parser->cb (parser->data, &attrib);
255 symbol->terminal = TRUE;
258 else if (transition->action == PARSER_REDUCE)
266 attrib = tree_new (symbol_copy (transition->left));
268 for (l = grammar_get_rule (transition->right);
273 if (!lr1_pop (parser, &attr))
275 tree_add (attrib, attr);
278 l = g_list_first (parser->stack);
279 state = (state_t*) l->data;
282 printf ("REDUCE: back to %x, ", state->state);
285 lr1_lookup (parser, state->state, transition->left, &trans);
288 printf ("%x\n", trans->state);
291 lr1_push (parser, trans->state, attrib);
295 else if (transition->action == PARSER_ACCEPT)
300 l = g_list_first (parser->stack);
301 state = (state_t*) l->data;
302 return state->attrib;