lr1.c

   1 #include <grammar.h>
   2 #include <stdlib.h>
   3
   4 enum { PARSER_SHIFT, PARSER_REDUCE, PARSER_ACCEPT };
   5
   6 struct _transition_t
   7 {
   8   gint action;
   9   gint state;
  10   symbol_t* left;
  11   rule_t* right;
  12 };
  13
  14 struct _lr1_t
  15 {
  16   nextcb cb;
  17   gpointer data;
  18   GHashTable* table;
  19   GList* stack;
  20 };
  21
  22 typedef struct
  23 {
  24   gint state;
  25   gpointer attrib;
  26 } state_t;
  27
  28 transition_t* transition_shift_new (gint state)
  29 {
  30   transition_t* transition;
  31   transition = g_malloc (sizeof (transition_t));
  32   transition->action = PARSER_SHIFT;
  33   transition->state = state;
  34   transition->left = NULL;
  35   transition->right = NULL;
  36   return transition;
  37 }
  38
  39 transition_t* transition_reduce_new (symbol_t* left, rule_t* right)
  40 {
  41   transition_t* transition;
  42   transition = g_malloc (sizeof (transition_t));
  43   transition->action = PARSER_REDUCE;
  44   transition->state = 0;
  45   transition->left = left;
  46   transition->right = right;
  47   return transition;
  48 }
  49
  50 transition_t* transition_accept_new ()
  51 {
  52   transition_t* transition;
  53   transition = g_malloc (sizeof (transition_t));
  54   transition->action = PARSER_ACCEPT;
  55   transition->state = 0;
  56   transition->left = NULL;
  57   transition->right = NULL;
  58   return transition;
  59 }
  60
  61 void transition_delete (transition_t* transition)
  62 {
  63   if (transition->left != NULL)
  64     g_free (transition->left);
  65   if (transition->right != NULL)
  66     rule_delete (transition->right);
  67   g_free (transition);
  68 }
  69
  70 static void lr1_push (lr1_t* parser, gint st, gpointer attrib)
  71 {
  72   state_t* state;
  73   state = g_malloc (sizeof (state_t));
  74   state->state = st;
  75   state->attrib = attrib;
  76   parser->stack = g_list_prepend (parser->stack, state);
  77 }
  78
  79 static gboolean lr1_pop (lr1_t* parser, gpointer* attrib)
  80 {
  81
  82   GList* l;
  83   state_t* state;
  84   if ((l = g_list_first (parser->stack)) == NULL)
  85     return FALSE;
  86   parser->stack = g_list_remove_link (l, l);
  87   state = (state_t*) l->data;
  88   if (attrib)
  89     *attrib = state->attrib;
  90   g_free (state);
  91   g_list_free (l);
  92   return TRUE;
  93
  94 }
  95
  96 lr1_t* lr1_new (nextcb cb, gpointer data)
  97 {
  98
  99   lr1_t* parser;
 100
 101   parser = g_malloc (sizeof (lr1_t));
 102   parser->cb = cb;
 103   parser->data = data;
 104
 105   parser->stack = NULL;
 106   lr1_push (parser, 0, 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_previous (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 }