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.
24 transition_t* transition_new (gint action, gint state)
26 transition_t* transition;
27 transition = g_malloc (sizeof (transition_t));
28 transition->action = action;
29 transition->state = state;
33 static void lr0_push (lr0_t* parser, gint st, gpointer attrib)
36 state = g_malloc (sizeof (state_t));
38 state->attrib = attrib;
39 parser->stack = g_list_prepend (parser->stack, state);
42 static gboolean lr0_pop (lr0_t* parser, gpointer* attrib)
47 if ((l = g_list_first (parser->stack)) == NULL)
49 parser->stack = g_list_remove_link (l, l);
50 state = (state_t*) l->data;
52 *attrib = state->attrib;
59 lr0_t* lr0_new (nextcb cb, gpointer data)
64 parser = g_malloc (sizeof (lr0_t));
69 parser_push (parser, 0, NULL);
70 parser->table = g_hash_table_new_full (g_direct_hash, g_direct_equal,
71 NULL, g_hash_table_destroy);
78 void lr0_delete (lr0_t* parser)
83 for (l = g_list_first (parser->stack); l != NULL; l = g_list_next (l))
88 g_list_free (parser->stack);
90 g_hash_table_destroy (parser->table);
96 void lr0_add (lr0_t* parser, gint state, symbol_t* symbol,
97 transition_t* transition)
102 if (!g_hash_table_lookup_extended (parser->table, state,
103 NULL, (gpointer*) &table))
105 table = g_hash_table_new_full (symbol_hash, symbol_equal,
107 g_hash_table_insert (parser->table, state, table);
110 g_hash_table_insert (table, symbol, transition);
114 gboolean lr0_lookup (lr0_t* parser, gint state, symbol_t* symbol,
115 transition_t** transition)
121 if (!g_hash_table_lookup_extended (parser->table, state,
122 NULL, (gpointer*) &table))
127 if (!g_hash_table_lookup_extended (table, symbol,
128 NULL, (gpointer*) &trans))
140 gpointer leaf_new (gpointer data)
142 return g_node_new (data);
145 gpointer tree_new (rule_t* rule)
147 return g_node_new (rule);
150 gpointer tree_add (gpointer tree, gpointer data)
152 return g_node_prepend (tree, data);
155 gpointer lr0_build (lr0_t* parser)
160 transition_t* transition;
164 symbol = g_malloc (sizeof (symbol_t));
166 symbol->value = parser->cb (parser->data, &attrib);
167 symbol->terminal = FALSE;
172 l = g_list_first (parser->stack);
173 state = (state_t*) l->data;
174 if (!lr0_lookup (parser, state->state, symbol, &transition))
177 if (transition->action == PARSER_SHIFT)
179 lr0_push (parser, transition->state, leaf_new (attrib));
180 symbol->value = parser->cb (parser->data, &attrib);
181 symbol->terminal = FALSE;
184 else if (transition->action == PARSER_REDUCE)
193 rule = g_list_nth_data (parser->rules, transition->state);
194 attrib = tree_new (rule);
196 for (l = g_list_last (rule->right);
198 l = g_list_previous (l))
201 if (!lr0_pop (parser, &attr))
203 tree_add (attrib, attr);
206 l = g_list_first (parser->stack);
207 state = (state_t*) l->data;
208 lr0_lookup (parser, state->state, rule->left, &trans);
209 lr0_push (parser, trans->state, attrib);
213 else if (transition->action == PARSER_ACCEPT)
215 l = g_list_first (parser->stack);
216 state = (state_t*) l->data;
217 return state->attrib;