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 static 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   lr1_push (parser, 0, NULL);
 108   parser->table = g_hash_table_new_full (g_direct_hash, g_direct_equal,
 109                                          NULL, g_hash_table_destroy);
 110
 111   return parser;
 112
 113 }
 114
 115 void lr1_delete (lr1_t* parser)
 116 {
 117
 118   GList* l;
 119
 120   for (l = g_list_first (parser->stack); l != NULL; l = g_list_next (l))
 121     {
 122       g_free (l->data);
 123     }
 124
 125   g_list_free (parser->stack);
 126
 127   g_hash_table_destroy (parser->table);
 128
 129   g_free (parser);
 130
 131 }
 132
 133 gboolean lr1_add (lr1_t* parser, gint state, symbol_t* symbol,
 134                   transition_t* transition)
 135 {
 136
 137   GHashTable* table;
 138
 139   if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
 140                                      NULL, (gpointer*) &table))
 141     {
 142       table = g_hash_table_new_full (symbol_hash, symbol_equal,
 143                                      g_free, transition_delete);
 144       g_hash_table_insert (parser->table, GINT_TO_POINTER(state), table);
 145     }
 146
 147   if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
 148     {
 149       return FALSE;
 150     }
 151
 152   g_hash_table_insert (table, symbol, transition);
 153   return TRUE;
 154
 155 }
 156
 157 gboolean lr1_lookup (lr1_t* parser, gint state, symbol_t* symbol,
 158                      transition_t** transition)
 159 {
 160
 161   GHashTable* table;
 162   transition_t* trans;
 163
 164   if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
 165                                      NULL, (gpointer*) &table))
 166     {
 167       return FALSE;
 168     }
 169
 170   if (!g_hash_table_lookup_extended (table, symbol,
 171                                      NULL, (gpointer*) &trans))
 172     {
 173       return FALSE;
 174     }
 175
 176   if (transition)
 177     *transition = trans;
 178
 179   return TRUE;
 180
 181 }
 182
 183 static gpointer leaf_new (gpointer data)
 184 {
 185   return g_node_new (data);
 186 }
 187
 188 static gpointer tree_new (rule_t* rule)
 189 {
 190   return g_node_new (rule);
 191 }
 192
 193 static gpointer tree_add (gpointer tree, gpointer data)
 194 {
 195   return g_node_prepend (tree, data);
 196 }
 197
 198 gpointer lr1_build (lr1_t* parser)
 199 {
 200
 201   state_t* state;
 202   symbol_t* symbol;
 203   transition_t* transition;
 204   gpointer attrib;
 205   GList* l;
 206
 207   symbol = g_malloc (sizeof (symbol_t));
 208
 209   symbol->value = parser->cb (parser->data, &attrib);
 210   symbol->terminal = TRUE;
 211
 212   while (1)
 213     {
 214
 215       l = g_list_first (parser->stack);
 216       state = (state_t*) l->data;
 217       if (!lr1_lookup (parser, state->state, symbol, &transition))
 218         return NULL;
 219
 220       if (transition->action == PARSER_SHIFT)
 221         {
 222           gint st;
 223           lr1_push (parser, transition->state, leaf_new (attrib));
 224           symbol->value = parser->cb (parser->data, &attrib);
 225           symbol->terminal = TRUE;
 226         }
 227
 228       else if (transition->action == PARSER_REDUCE)
 229         {
 230
 231           state_t* state;
 232           transition_t* trans;
 233           GList* l;
 234           gpointer attrib;
 235
 236           attrib = tree_new (symbol_copy (transition->left));
 237
 238           for (l = grammar_get_rule (transition->right);
 239                l != NULL;
 240                l = g_list_next (l))
 241             {
 242               gpointer attr;
 243               if (!lr1_pop (parser, &attr))
 244                 return NULL;
 245               tree_add (attrib, attr);
 246             }
 247
 248           l = g_list_first (parser->stack);
 249           state = (state_t*) l->data;
 250           lr1_lookup (parser, state->state, transition->left, &trans);
 251           lr1_push (parser, trans->state, attrib);
 252
 253         }
 254
 255       else if (transition->action == PARSER_ACCEPT)
 256         {
 257           l = g_list_first (parser->stack);
 258           state = (state_t*) l->data;
 259           return state->attrib;
 260         }
 261
 262     }
 263
 264   return NULL;
 265
 266 }