lr0.c

   1 /*
   2  *  Copyright (C) 2005  Thadeu Lima de Souza Cascardo <cascardo@holoscopio.com>
   3  *
   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.
   8  *
   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.
  13  *
  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.
  17  */
  18
  19
  20
  21 #include "lr0.h"
  22 #include <stdlib.h>
  23
  24 transition_t* transition_new (gint action, gint state)
  25 {
  26   transition_t* transition;
  27   transition = g_malloc (sizeof (transition_t));
  28   transition->action = action;
  29   transition->state = state;
  30   return transition;
  31 }
  32
  33 static void lr0_push (lr0_t* parser, gint st, gpointer attrib)
  34 {
  35   state_t* state;
  36   state = g_malloc (sizeof (state_t));
  37   state->state = st;
  38   state->attrib = attrib;
  39   parser->stack = g_list_prepend (parser->stack, state);
  40 }
  41
  42 static gboolean lr0_pop (lr0_t* parser, gpointer* attrib)
  43 {
  44
  45   GList* l;
  46   state_t* state;
  47   if ((l = g_list_first (parser->stack)) == NULL)
  48     return FALSE;
  49   parser->stack = g_list_remove_link (l, l);
  50   state = (state_t*) l->data;
  51   if (attrib)
  52     *attrib = state->attrib;
  53   g_free (state);
  54   g_list_free (l);
  55   return TRUE;
  56
  57 }
  58
  59 lr0_t* lr0_new (nextcb cb, gpointer data)
  60 {
  61
  62   lr0_t* parser;
  63
  64   parser = g_malloc (sizeof (lr0_t));
  65   parser->cb = cb;
  66   parser->data = data;
  67
  68   parser->stack = NULL;
  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);
  72   parser->rules = NULL;
  73
  74   return parser;
  75
  76 }
  77
  78 void lr0_delete (lr0_t* parser)
  79 {
  80
  81   GList* l;
  82
  83   for (l = g_list_first (parser->stack); l != NULL; l = g_list_next (l))
  84     {
  85       g_free (l->data);
  86     }
  87
  88   g_list_free (parser->stack);
  89
  90   g_hash_table_destroy (parser->table);
  91
  92   g_free (parser);
  93
  94 }
  95
  96 void lr0_add (lr0_t* parser, gint state, symbol_t* symbol,
  97                  transition_t* transition)
  98 {
  99
 100   GHashTable* table;
 101
 102   if (!g_hash_table_lookup_extended (parser->table, state,
 103                                      NULL, (gpointer*) &table))
 104     {
 105       table = g_hash_table_new_full (symbol_hash, symbol_equal,
 106                                      g_free, g_free);
 107       g_hash_table_insert (parser->table, state, table);
 108     }
 109
 110   g_hash_table_insert (table, symbol, transition);
 111
 112 }
 113
 114 gboolean lr0_lookup (lr0_t* parser, gint state, symbol_t* symbol,
 115                         transition_t** transition)
 116 {
 117
 118   GHashTable* table;
 119   transition_t* trans;
 120
 121   if (!g_hash_table_lookup_extended (parser->table, state,
 122                                      NULL, (gpointer*) &table))
 123     {
 124       return FALSE;
 125     }
 126
 127   if (!g_hash_table_lookup_extended (table, symbol,
 128                                      NULL, (gpointer*) &trans))
 129     {
 130       return FALSE;
 131     }
 132
 133   if (transition)
 134     *transition = trans;
 135
 136   return TRUE;
 137
 138 }
 139
 140 gpointer leaf_new (gpointer data)
 141 {
 142   return g_node_new (data);
 143 }
 144
 145 gpointer tree_new (rule_t* rule)
 146 {
 147   return g_node_new (rule);
 148 }
 149
 150 gpointer tree_add (gpointer tree, gpointer data)
 151 {
 152   return g_node_prepend (tree, data);
 153 }
 154
 155 gpointer lr0_build (lr0_t* parser)
 156 {
 157
 158   state_t* state;
 159   symbol_t* symbol;
 160   transition_t* transition;
 161   gpointer attrib;
 162   GList* l;
 163
 164   symbol = g_malloc (sizeof (symbol_t));
 165
 166   symbol->value = parser->cb (parser->data, &attrib);
 167   symbol->terminal = FALSE;
 168
 169   while (1)
 170     {
 171
 172       l = g_list_first (parser->stack);
 173       state = (state_t*) l->data;
 174       if (!lr0_lookup (parser, state->state, symbol, &transition))
 175         return NULL;
 176
 177       if (transition->action == PARSER_SHIFT)
 178         {
 179           lr0_push (parser, transition->state, leaf_new (attrib));
 180           symbol->value = parser->cb (parser->data, &attrib);
 181           symbol->terminal = FALSE;
 182         }
 183
 184       else if (transition->action == PARSER_REDUCE)
 185         {
 186
 187           rule_t* rule;
 188           state_t* state;
 189           transition_t* trans;
 190           GList* l;
 191           gpointer attrib;
 192
 193           rule = g_list_nth_data (parser->rules, transition->state);
 194           attrib = tree_new (rule);
 195
 196           for (l = g_list_last (rule->right);
 197                l != NULL;
 198                l = g_list_previous (l))
 199             {
 200               gpointer attr;
 201               if (!lr0_pop (parser, &attr))
 202                 return NULL;
 203               tree_add (attrib, attr);
 204             }
 205
 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);
 210
 211         }
 212
 213       else if (transition->action == PARSER_ACCEPT)
 214         {
 215           l = g_list_first (parser->stack);
 216           state = (state_t*) l->data;
 217           return state->attrib;
 218         }
 219
 220     }
 221
 222   return NULL;
 223
 224 }