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