lr0.c

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