lr1.c

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