lr1.c

   1 #include <grammar.h>
   2 #include <stdlib.h>
   3 #include <lr1.h>
   4
   5 enum { PARSER_SHIFT, PARSER_REDUCE, PARSER_ACCEPT };
   6
   7 struct _transition_t
   8 {
   9   gint action;
  10   gint state;
  11   symbol_t* left;
  12   rule_t* right;
  13 };
  14
  15 struct _lr1_t
  16 {
  17   nextcb cb;
  18   gpointer data;
  19   GHashTable* table;
  20   GList* stack;
  21 };
  22
  23 typedef struct
  24 {
  25   gint state;
  26   gpointer attrib;
  27 } state_t;
  28
  29 transition_t* transition_shift_new (gint state)
  30 {
  31   transition_t* transition;
  32   transition = g_malloc (sizeof (transition_t));
  33   transition->action = PARSER_SHIFT;
  34   transition->state = state;
  35   transition->left = NULL;
  36   transition->right = NULL;
  37   return transition;
  38 }
  39
  40 transition_t* transition_reduce_new (symbol_t* left, rule_t* right)
  41 {
  42   transition_t* transition;
  43   transition = g_malloc (sizeof (transition_t));
  44   transition->action = PARSER_REDUCE;
  45   transition->state = 0;
  46   transition->left = left;
  47   transition->right = right;
  48   return transition;
  49 }
  50
  51 transition_t* transition_accept_new ()
  52 {
  53   transition_t* transition;
  54   transition = g_malloc (sizeof (transition_t));
  55   transition->action = PARSER_ACCEPT;
  56   transition->state = 0;
  57   transition->left = NULL;
  58   transition->right = NULL;
  59   return transition;
  60 }
  61
  62 void transition_delete (transition_t* transition)
  63 {
  64   if (transition->left != NULL)
  65     g_free (transition->left);
  66   if (transition->right != NULL)
  67     rule_delete (transition->right);
  68   g_free (transition);
  69 }
  70
  71 void lr1_push (lr1_t* parser, gint st, gpointer attrib)
  72 {
  73   state_t* state;
  74   state = g_malloc (sizeof (state_t));
  75   state->state = st;
  76   state->attrib = attrib;
  77   parser->stack = g_list_prepend (parser->stack, state);
  78 }
  79
  80 static gboolean lr1_pop (lr1_t* parser, gpointer* attrib)
  81 {
  82
  83   GList* l;
  84   state_t* state;
  85   if ((l = g_list_first (parser->stack)) == NULL)
  86     return FALSE;
  87   parser->stack = g_list_remove_link (l, l);
  88   state = (state_t*) l->data;
  89   if (attrib)
  90     *attrib = state->attrib;
  91   g_free (state);
  92   g_list_free (l);
  93   return TRUE;
  94
  95 }
  96
  97 lr1_t* lr1_new (nextcb cb, gpointer data)
  98 {
  99
 100   lr1_t* parser;
 101
 102   parser = g_malloc (sizeof (lr1_t));
 103   parser->cb = cb;
 104   parser->data = data;
 105
 106   parser->stack = NULL;
 107   parser->table = g_hash_table_new_full (g_direct_hash, g_direct_equal,
 108                                          NULL, g_hash_table_destroy);
 109
 110   return parser;
 111
 112 }
 113
 114 void lr1_delete (lr1_t* parser)
 115 {
 116
 117   GList* l;
 118
 119   for (l = g_list_first (parser->stack); l != NULL; l = g_list_next (l))
 120     {
 121       g_free (l->data);
 122     }
 123
 124   g_list_free (parser->stack);
 125
 126   g_hash_table_destroy (parser->table);
 127
 128   g_free (parser);
 129
 130 }
 131
 132 gboolean lr1_add (lr1_t* parser, gint state, symbol_t* symbol,
 133                   transition_t* transition)
 134 {
 135
 136   GHashTable* table;
 137
 138   if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
 139                                      NULL, (gpointer*) &table))
 140     {
 141       table = g_hash_table_new_full (symbol_hash, symbol_equal,
 142                                      g_free, transition_delete);
 143       g_hash_table_insert (parser->table, GINT_TO_POINTER(state), table);
 144     }
 145
 146   if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
 147     {
 148       return FALSE;
 149     }
 150
 151   g_hash_table_insert (table, symbol, transition);
 152   return TRUE;
 153
 154 }
 155
 156 gboolean lr1_lookup (lr1_t* parser, gint state, symbol_t* symbol,
 157                      transition_t** transition)
 158 {
 159
 160   GHashTable* table;
 161   transition_t* trans;
 162
 163   if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
 164                                      NULL, (gpointer*) &table))
 165     {
 166       return FALSE;
 167     }
 168
 169   if (!g_hash_table_lookup_extended (table, symbol,
 170                                      NULL, (gpointer*) &trans))
 171     {
 172       return FALSE;
 173     }
 174
 175   if (transition)
 176     *transition = trans;
 177
 178   return TRUE;
 179
 180 }
 181
 182 static gpointer leaf_new (gpointer data)
 183 {
 184   return g_node_new (data);
 185 }
 186
 187 static gpointer tree_new (rule_t* rule)
 188 {
 189   return g_node_new (rule);
 190 }
 191
 192 static gpointer tree_add (gpointer tree, gpointer data)
 193 {
 194   return g_node_prepend (tree, data);
 195 }
 196
 197 gpointer lr1_build (lr1_t* parser)
 198 {
 199
 200   state_t* state;
 201   symbol_t* symbol;
 202   transition_t* transition;
 203   gpointer attrib;
 204   GList* l;
 205
 206   symbol = g_malloc (sizeof (symbol_t));
 207
 208   symbol->value = parser->cb (parser->data, &attrib);
 209   symbol->terminal = TRUE;
 210
 211   while (1)
 212     {
 213
 214       l = g_list_first (parser->stack);
 215       state = (state_t*) l->data;
 216       if (!lr1_lookup (parser, state->state, symbol, &transition))
 217         return NULL;
 218
 219       if (transition->action == PARSER_SHIFT)
 220         {
 221           gint st;
 222           lr1_push (parser, transition->state, leaf_new (attrib));
 223           symbol->value = parser->cb (parser->data, &attrib);
 224           symbol->terminal = TRUE;
 225         }
 226
 227       else if (transition->action == PARSER_REDUCE)
 228         {
 229
 230           state_t* state;
 231           transition_t* trans;
 232           GList* l;
 233           gpointer attrib;
 234
 235           attrib = tree_new (symbol_copy (transition->left));
 236
 237           for (l = grammar_get_rule (transition->right);
 238                l != NULL;
 239                l = g_list_next (l))
 240             {
 241               gpointer attr;
 242               if (!lr1_pop (parser, &attr))
 243                 return NULL;
 244               tree_add (attrib, attr);
 245             }
 246
 247           l = g_list_first (parser->stack);
 248           state = (state_t*) l->data;
 249           lr1_lookup (parser, state->state, transition->left, &trans);
 250           lr1_push (parser, trans->state, attrib);
 251
 252         }
 253
 254       else if (transition->action == PARSER_ACCEPT)
 255         {
 256           l = g_list_first (parser->stack);
 257           state = (state_t*) l->data;
 258           return state->attrib;
 259         }
 260
 261     }
 262
 263   return NULL;
 264
 265 }