lr1.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 <grammar.h>
  22 #include <stdlib.h>
  23 #include <lr1.h>
  24 #ifdef DEBUG
  25 #include <stdio.h>
  26 #endif
  27
  28 enum { PARSER_SHIFT, PARSER_REDUCE, PARSER_ACCEPT };
  29
  30 struct _transition_t
  31 {
  32   gint action;
  33   gint state;
  34   symbol_t* left;
  35   rule_t* right;
  36 };
  37
  38 struct _lr1_t
  39 {
  40   nextcb cb;
  41   gpointer data;
  42   GHashTable* table;
  43   GList* stack;
  44 };
  45
  46 typedef struct
  47 {
  48   gint state;
  49   gpointer attrib;
  50 } state_t;
  51
  52 transition_t* transition_shift_new (gint state)
  53 {
  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;
  60   return transition;
  61 }
  62
  63 transition_t* transition_reduce_new (symbol_t* left, rule_t* right)
  64 {
  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;
  71   return transition;
  72 }
  73
  74 transition_t* transition_accept_new ()
  75 {
  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;
  82   return transition;
  83 }
  84
  85 void transition_delete (transition_t* transition)
  86 {
  87   if (transition->left != NULL)
  88     g_free (transition->left);
  89   if (transition->right != NULL)
  90     rule_delete (transition->right);
  91   g_free (transition);
  92 }
  93
  94 void lr1_push (lr1_t* parser, gint st, gpointer attrib)
  95 {
  96   state_t* state;
  97   state = g_malloc (sizeof (state_t));
  98   state->state = st;
  99   state->attrib = attrib;
 100   parser->stack = g_list_prepend (parser->stack, state);
 101 }
 102
 103 static gboolean lr1_pop (lr1_t* parser, gpointer* attrib)
 104 {
 105
 106   GList* l;
 107   state_t* state;
 108   if ((l = g_list_first (parser->stack)) == NULL)
 109     return FALSE;
 110   parser->stack = g_list_remove_link (l, l);
 111   state = (state_t*) l->data;
 112   if (attrib)
 113     *attrib = state->attrib;
 114   g_free (state);
 115   g_list_free (l);
 116   return TRUE;
 117
 118 }
 119
 120 lr1_t* lr1_new (nextcb cb, gpointer data)
 121 {
 122
 123   lr1_t* parser;
 124
 125   parser = g_malloc (sizeof (lr1_t));
 126   parser->cb = cb;
 127   parser->data = data;
 128
 129   parser->stack = NULL;
 130   parser->table = g_hash_table_new_full (g_direct_hash, g_direct_equal,
 131                                          NULL, g_hash_table_destroy);
 132
 133   return parser;
 134
 135 }
 136
 137 void lr1_delete (lr1_t* parser)
 138 {
 139
 140   GList* l;
 141
 142   for (l = g_list_first (parser->stack); l != NULL; l = g_list_next (l))
 143     {
 144       g_free (l->data);
 145     }
 146
 147   g_list_free (parser->stack);
 148
 149   g_hash_table_destroy (parser->table);
 150
 151   g_free (parser);
 152
 153 }
 154
 155 gboolean lr1_add (lr1_t* parser, gint state, symbol_t* symbol,
 156                   transition_t* transition)
 157 {
 158
 159   GHashTable* table;
 160
 161   if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
 162                                      NULL, (gpointer*) &table))
 163     {
 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);
 167     }
 168
 169   if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
 170     {
 171       return FALSE;
 172     }
 173
 174   g_hash_table_insert (table, symbol, transition);
 175   return TRUE;
 176
 177 }
 178
 179 gboolean lr1_lookup (lr1_t* parser, gint state, symbol_t* symbol,
 180                      transition_t** transition)
 181 {
 182
 183   GHashTable* table;
 184   transition_t* trans;
 185
 186   if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
 187                                      NULL, (gpointer*) &table))
 188     {
 189       return FALSE;
 190     }
 191
 192   if (!g_hash_table_lookup_extended (table, symbol,
 193                                      NULL, (gpointer*) &trans))
 194     {
 195       return FALSE;
 196     }
 197
 198   if (transition)
 199     *transition = trans;
 200
 201   return TRUE;
 202
 203 }
 204
 205 static gpointer leaf_new (gpointer data)
 206 {
 207   return g_node_new (data);
 208 }
 209
 210 static gpointer tree_new (rule_t* rule)
 211 {
 212   return g_node_new (rule);
 213 }
 214
 215 static gpointer tree_add (gpointer tree, gpointer data)
 216 {
 217   return g_node_prepend (tree, data);
 218 }
 219
 220 gpointer lr1_build (lr1_t* parser)
 221 {
 222
 223   state_t* state;
 224   symbol_t* symbol;
 225   transition_t* transition;
 226   gpointer attrib;
 227   GList* l;
 228
 229   symbol = g_malloc (sizeof (symbol_t));
 230
 231   symbol->value = parser->cb (parser->data, &attrib);
 232   symbol->terminal = TRUE;
 233
 234   while (1)
 235     {
 236
 237       l = g_list_first (parser->stack);
 238       state = (state_t*) l->data;
 239       if (!lr1_lookup (parser, state->state, symbol, &transition))
 240         return NULL;
 241
 242 #ifdef DEBUG
 243           printf ("State: %x, Symbol: %s\n", state->state,
 244                   g_quark_to_string (symbol->value));
 245 #endif
 246
 247       if (transition->action == PARSER_SHIFT)
 248         {
 249           gint st;
 250 #ifdef DEBUG
 251           printf ("SHIFT: %x\n", transition->state);
 252 #endif
 253           lr1_push (parser, transition->state, leaf_new (attrib));
 254           symbol->value = parser->cb (parser->data, &attrib);
 255           symbol->terminal = TRUE;
 256         }
 257
 258       else if (transition->action == PARSER_REDUCE)
 259         {
 260
 261           state_t* state;
 262           transition_t* trans;
 263           GList* l;
 264           gpointer attrib;
 265
 266           attrib = tree_new (symbol_copy (transition->left));
 267
 268           for (l = grammar_get_rule (transition->right);
 269                l != NULL;
 270                l = g_list_next (l))
 271             {
 272               gpointer attr;
 273               if (!lr1_pop (parser, &attr))
 274                 return NULL;
 275               tree_add (attrib, attr);
 276             }
 277
 278           l = g_list_first (parser->stack);
 279           state = (state_t*) l->data;
 280
 281 #ifdef DEBUG
 282           printf ("REDUCE: back to %x, ", state->state);
 283 #endif
 284
 285           lr1_lookup (parser, state->state, transition->left, &trans);
 286
 287 #ifdef DEBUG
 288           printf ("%x\n", trans->state);
 289 #endif
 290
 291           lr1_push (parser, trans->state, attrib);
 292
 293         }
 294
 295       else if (transition->action == PARSER_ACCEPT)
 296         {
 297 #ifdef DEBUG
 298           printf ("ACCEPT\n");
 299 #endif
 300           l = g_list_first (parser->stack);
 301           state = (state_t*) l->data;
 302           return state->attrib;
 303         }
 304
 305     }
 306
 307   return NULL;
 308
 309 }