first.c

   1 #include <grammar.h>
   2 #include <stdio.h>
   3 #include <assert.h>
   4
   5 typedef struct
   6 {
   7   gboolean has_empty;
   8   GHashTable* terminals;
   9   GList* rules;
  10   GList* recursive;
  11 } first_set_t;
  12
  13 first_set_t* first_set_new ()
  14 {
  15   first_set_t* first_set;
  16   first_set = g_malloc (sizeof (first_set_t));
  17   first_set->has_empty = FALSE;
  18   first_set->terminals = g_hash_table_new_full (symbol_hash, symbol_equal,
  19                                                 g_free, NULL);
  20   first_set->rules = NULL;
  21   first_set->recursive = NULL;
  22   return first_set;
  23 }
  24
  25 void first_set_delete (first_set_t* first_set)
  26 {
  27   GList* l;
  28   g_hash_table_destroy (first_set->terminals);
  29   l = first_set->rules;
  30   while (l != NULL)
  31     {
  32       rule_delete (l->data);
  33       l = g_list_next (l);
  34     }
  35   g_list_free (first_set->rules);
  36   l = first_set->recursive;
  37   while (l != NULL)
  38     {
  39       rule_delete (l->data);
  40       l = g_list_next (l);
  41     }
  42   g_list_free (first_set->recursive);
  43   g_free (first_set);
  44 }
  45
  46 void first_set_insert_terminal (first_set_t* first_set, symbol_t* symbol)
  47 {
  48   g_hash_table_insert (first_set->terminals, symbol, NULL);
  49 }
  50
  51 void first_set_insert (gpointer key, gpointer val, gpointer data)
  52 {
  53   g_hash_table_insert (data, symbol_copy (key), NULL);
  54 }
  55
  56 GHashTable* first_set_union (GHashTable* a, GHashTable* b)
  57 {
  58   g_hash_table_foreach (b, first_set_insert, a);
  59   return a;
  60 }
  61
  62 void first_advance_recursive (first_set_t* first_set, symbol_t* symbol)
  63 {
  64
  65   GList* rules;
  66   rules = first_set->recursive;
  67
  68   /*
  69    * For each recursive rule, remove recursiveness and insert any new
  70    * rule to list of non-recursive rules.
  71    */
  72
  73   while (rules != NULL)
  74     {
  75
  76       rule_t* rule;
  77       GList* symbols;
  78       symbol_t* first_symbol;
  79
  80       rule = rules->data;
  81       symbols = grammar_get_rule (rule);
  82
  83       assert (symbols != NULL);
  84
  85       first_symbol = symbols->data;
  86
  87       assert (first_symbol->value == symbol->value);
  88
  89       /* Remove any leading symbols equal to the recursive nonterminal */
  90       while (first_symbol->value == symbol->value)
  91         {
  92           first_symbol = rule_pop (rule);
  93
  94           /* If no symbol remains after removing leading recursive
  95            * nonterminal, it may produce the empty string */
  96           if (first_symbol == NULL)
  97             {
  98               first_set->has_empty = TRUE;
  99               rule_delete (rule);
 100               break;
 101             }
 102           /* If after removing leading recursive nonterminal, there
 103            * is a terminal, it is in the first set of the nonterminal */
 104           else if (first_symbol->terminal)
 105             {
 106               first_set_insert_terminal (first_set,
 107                                          symbol_copy (first_symbol));
 108               rule_delete (rule);
 109               break;
 110             }
 111           /*
 112            * If after removing leading recursive nonterminal, there
 113            * is a nonterminal, the first of the remaining sequence
 114            * of symbols is in the first set of the recursive
 115            * nonterminal
 116            */
 117           else if (first_symbol->value != symbol->value)
 118             {
 119               first_set->rules = g_list_append (first_set->rules, rule);
 120               break;
 121             }
 122         }
 123
 124       rules = g_list_next (rules);
 125
 126     }
 127
 128   g_list_free (first_set->recursive);
 129   first_set->recursive = NULL;
 130
 131 }
 132
 133 void first_prepare (gpointer key, gpointer val, gpointer data)
 134 {
 135
 136   symbol_t* symbol;
 137   GList* rules;
 138   GHashTable* first;
 139
 140   first_set_t* first_set;
 141
 142   symbol = (symbol_t*) key;
 143   rules = *(GList**) val;
 144   first = (GHashTable*) data;
 145
 146   assert (symbol->terminal == FALSE);
 147
 148   /* For each nonterminal in the grammar, there is a first set */
 149   first_set = first_set_new ();
 150   g_hash_table_insert (first, symbol_copy (symbol), first_set);
 151
 152   /*
 153    * For each rule for the nonterminal in the grammar, it will either
 154    * produce the empty string directly, start with a terminal that will
 155    * be included in the first set, start with a different nonterminal or
 156    * be a recursive rule.
 157    */
 158   while (rules != NULL)
 159     {
 160
 161       rule_t* rule;
 162       GList* symbols;
 163       symbol_t* first_symbol;
 164
 165       rule = rules->data;
 166       symbols = grammar_get_rule (rule);
 167
 168       if (symbols == NULL)
 169         {
 170           first_set->has_empty = TRUE;
 171         }
 172       else
 173         {
 174           first_symbol = symbols->data;
 175           if (first_symbol->terminal)
 176             {
 177               first_set_insert_terminal (first_set,
 178                                          symbol_copy (first_symbol));
 179             }
 180           else if (first_symbol->value == symbol->value)
 181             {
 182               first_set->recursive = g_list_prepend (first_set->recursive,
 183                                                      rule_copy (rule));
 184             }
 185           else
 186             {
 187               first_set->rules = g_list_prepend (first_set->rules,
 188                                                  rule_copy (rule));
 189             }
 190         }
 191
 192       rules = g_list_next (rules);
 193
 194     }
 195
 196   /*
 197    * If there any no non-recursive rules starting with a nonterminal
 198    * recursiveness may be easily eliminated.
 199    */
 200   if (first_set->rules == NULL && first_set->recursive != NULL)
 201     {
 202       /*
 203        * If the nonterminal may produce the empty string, each recursive
 204        * rule will lead to a new rule with the leading recursive nonterminal
 205        * removed.
 206        */
 207       if (first_set->has_empty)
 208         {
 209           first_advance_recursive (first_set, symbol);
 210         }
 211       /* If it does not produce the empty string, every recursive rule
 212        * may be simply removed. All terminals in first set are known at
 213        * this point.
 214        */
 215       else
 216         {
 217           GList* l;
 218           l = first_set->recursive;
 219           while (l != NULL)
 220             {
 221               rule_delete (l->data);
 222               l = g_list_next (l);
 223             }
 224           g_list_free (first_set->recursive);
 225           first_set->recursive = NULL;
 226         }
 227       assert (first_set->recursive == NULL);
 228     }
 229
 230 }
 231
 232 void first_iterate (gpointer key, gpointer val, gpointer data)
 233 {
 234
 235   symbol_t* symbol;
 236   first_set_t* first_set;
 237   GHashTable* first;
 238
 239   GList* rules;
 240   GList* new_rules;
 241
 242   symbol = (symbol_t*) key;
 243   first_set = (first_set_t*) val;
 244   first = (GHashTable*) data;
 245
 246   assert (symbol->terminal == FALSE);
 247
 248   /* If there are no non-recursive rules starting with a
 249    * nonterminal, there's not much to do. Only remove all
 250    * the recursive rules or advance them as described in
 251    * the first_prepare.
 252    */
 253   if (first_set->rules == NULL)
 254     {
 255       if (first_set->recursive != NULL)
 256         {
 257           if (first_set->has_empty)
 258             {
 259               first_advance_recursive (first_set, symbol);
 260             }
 261           else
 262             {
 263               GList* l;
 264               l = first_set->recursive;
 265               while (l != NULL)
 266                 {
 267                   rule_delete (l->data);
 268                   l = g_list_next (l);
 269                 }
 270               g_list_free (first_set->recursive);
 271               first_set->recursive = NULL;
 272             }
 273           assert (first_set->recursive == NULL);
 274         }
 275       return;
 276     }
 277   else
 278     {
 279
 280       rules = first_set->rules;
 281       new_rules = NULL;
 282
 283       /*
 284        * For each rule, try to eliminate it by checking the first set of
 285        * the nonterminal with starts it. Rules may have been added by
 286        * previous iterations or the advancement of recursive rules.
 287        * So, trivial checks like empty rules and rules starting with
 288        * terminals should be checked too.
 289        */
 290       while (rules != NULL)
 291         {
 292
 293           rule_t* rule;
 294           GList* symbols;
 295           symbol_t* first_symbol;
 296
 297           rule = rules->data;
 298           symbols = grammar_get_rule (rule);
 299
 300           /* If it is an empty rule, nonterminal may produce the empty
 301            * string */
 302           if (symbols == NULL)
 303             {
 304               first_set->has_empty = TRUE;
 305               rule_delete (rule);
 306             }
 307           else
 308             {
 309
 310               first_set_t* next_set;
 311
 312               first_symbol = symbols->data;
 313
 314               /* If it starts with a terminal, include it in the first
 315                * set and remove the rule. */
 316               if (first_symbol->terminal)
 317                 {
 318                   first_set_insert_terminal (first_set,
 319                                              symbol_copy (first_symbol));
 320                   rule_delete (rule);
 321                 }
 322               /* Get the first set of the nonterminal which starts the rule */
 323               else if (g_hash_table_lookup_extended (first, first_symbol, NULL,
 324                                                      (gpointer*) &next_set))
 325                 {
 326                   /*
 327                    * If nonterminal produces the empty string, the first set
 328                    * of the sequence of symbols next to it is in the first
 329                    * set of the nonterminal we are treating. Add a new rule
 330                    * corresponding to this sequence of symbols. This is the
 331                    * rule which says: if there is a production A -> y1 y2 yk
 332                    * and the empty string is in the first of y1, then first
 333                    * of y2 yk is in first of A.
 334                    */
 335                   if (next_set->has_empty)
 336                     {
 337                       rule_t* new_rule;
 338                       new_rule = rule_copy (rule);
 339                       rule_pop (new_rule);
 340                       new_rules = g_list_prepend (new_rules, new_rule);
 341                     }
 342                   /* The terminals in the first of the leading nonterminal in
 343                    * the rule are in the first of our current nonterminal */
 344                   first_set_union (first_set->terminals,
 345                                    next_set->terminals);
 346                   /*
 347                    * If there are other rules starting with a nonterminal
 348                    * for this nonterminal, they should be copied to the
 349                    * current nonterminal, so we can detect and treat indirect
 350                    * recursiveness properly.
 351                    */
 352                   if (next_set->rules != NULL)
 353                     {
 354                       /* FIXME: not much of an advance here, watch for
 355                        * this in a possible unstopabble loop */
 356                       /* FIXME: copy recursive rules too, with care */
 357                       GList* next_rules;
 358                       next_rules = next_set->rules;
 359                       while (next_rules != NULL)
 360                         {
 361                           rule_t* next_rule = rule_copy (next_rules->data);
 362                           GList* next_symbols;
 363                           next_symbols = grammar_get_rule (next_rule);
 364                           /*
 365                            * If the rule is empty, both terminals produce the
 366                            * empty set. This will be detected for the other
 367                            * nonterminal later. Optimization could be done
 368                            * here. TODO
 369                            */
 370                           if (next_symbols == NULL)
 371                             {
 372                               first_set->has_empty = TRUE;
 373                               rule_delete (next_rule);
 374                             }
 375                           else
 376                             {
 377                               symbol_t* next_symbol;
 378                               next_symbol = next_symbols->data;
 379                               /* TODO: Check this assertion is correct. */
 380                               assert (next_symbol->terminal == FALSE);
 381                               /* This is an indirect recursive rule. */
 382                               if (next_symbol->value == symbol->value)
 383                                 {
 384                                   first_set->recursive =
 385                                     g_list_prepend (first_set->recursive,
 386                                                     next_rule);
 387                                 }
 388                               /* Next time we treat current nonterminal,
 389                                * we will check this rule directly. */
 390                               else
 391                                 {
 392                                   new_rules = g_list_prepend (new_rules, next_rule);
 393                                 }
 394                             }
 395                           next_rules = g_list_next (next_rules);
 396                         }
 397                     }
 398                   /*
 399                    * If nonterminal has recursive rules, we should expect
 400                    * more rules to add here and so we will check it again
 401                    * in the next iteration. Keep the rule. If there is only
 402                    * indirect recursiveness, we will detect it through the
 403                    * rules we have added before. We should remove it in this
 404                    * case so we make advance.
 405                    */
 406                   if (next_set->recursive != NULL)
 407                     {
 408                       new_rules = g_list_prepend (new_rules, rule);
 409                     }
 410                   else
 411                     {
 412                       rule_delete (rule);
 413                     }
 414                 }
 415               else
 416                 {
 417                   assert (TRUE);
 418                 }
 419
 420             }
 421
 422           rules = g_list_next (rules);
 423
 424         }
 425
 426       g_list_free (first_set->rules);
 427       first_set->rules = new_rules;
 428
 429     }
 430
 431 }
 432
 433 void first_check (gpointer key, gpointer val, gpointer data)
 434 {
 435
 436   symbol_t* symbol;
 437   first_set_t* first_set;
 438   gboolean* stop;
 439
 440   symbol = (symbol_t*) key;
 441   first_set = (first_set_t*) val;
 442   stop = (gboolean*) data;
 443
 444   assert (symbol->terminal == FALSE);
 445
 446   /* If there is anything besides terminals in the first set,
 447    * we must iterate more and remove all of them. */
 448   if (first_set->rules != NULL || first_set->recursive != NULL)
 449     {
 450       *stop = FALSE;
 451     }
 452
 453 }
 454
 455 /*
 456  * Calculate the first set for every nonterminal symbol in the grammar.
 457  * We should iterate through the rules for each nonterminal until only
 458  * terminals are known to be in the first set of it.
 459  */
 460 GHashTable* grammar_first (Grammar* grammar)
 461 {
 462   GHashTable* first;
 463   gboolean stop;
 464   first = g_hash_table_new_full (symbol_hash, symbol_equal,
 465                                  g_free,
 466                                  first_set_delete);
 467   g_hash_table_foreach (grammar->grammar, first_prepare, first);
 468   do
 469     {
 470       g_hash_table_foreach (first, first_iterate, first);
 471       stop = TRUE;
 472       g_hash_table_foreach (first, first_check, &stop);
 473     } while (stop == FALSE);
 474   return first;
 475 }
 476
 477 static void put_key_on_list (gpointer key, gpointer val, gpointer data)
 478 {
 479   GList** l;
 480   l = (GList**) data;
 481   *l = g_list_prepend (*l, symbol_copy (key));
 482 }
 483
 484 GList* first_get (GHashTable* first, symbol_t* symbol)
 485 {
 486
 487   first_set_t* first_set;
 488   GList* l;
 489   l = NULL;
 490   if (g_hash_table_lookup_extended (first, symbol, NULL,
 491                                     (gpointer*) &first_set))
 492     {
 493       if (first_set->has_empty)
 494         l = g_list_prepend (l, symbol_new (TRUE, 0));
 495       g_hash_table_foreach (first_set->terminals, put_key_on_list, &l);
 496     }
 497   return l;
 498
 499 }
 500
 501 GList* first_rule (GHashTable* first, rule_t* rule)
 502 {
 503
 504   GHashTable* terminals;
 505   GList* symbols;
 506   GList* l;
 507
 508   l = NULL;
 509
 510   symbols = grammar_get_rule (rule);
 511
 512   terminals = g_hash_table_new_full (symbol_hash, symbol_equal, g_free, NULL);
 513
 514   while (symbols != NULL)
 515     {
 516       first_set_t* first_set;
 517       symbol_t* symbol;
 518       symbol = (symbol_t*) symbols->data;
 519       if (symbol->terminal)
 520         {
 521           g_hash_table_insert (terminals, symbol_copy (symbol), NULL);
 522           break;
 523         }
 524       if (!g_hash_table_lookup_extended (first, symbol, NULL,
 525                                          (gpointer*) &first_set))
 526         {
 527           g_hash_table_destroy (terminals);
 528           return NULL;
 529         }
 530       first_set_union (terminals, first_set->terminals);
 531       if (first_set->has_empty == FALSE)
 532         break;
 533       symbols = g_list_next (symbols);
 534     }
 535
 536   if (symbols == NULL)
 537     l = g_list_prepend (l, symbol_new (TRUE, 0));
 538   g_hash_table_foreach (terminals, put_key_on_list, &l);
 539
 540   g_hash_table_destroy (terminals);
 541
 542   return l;
 543
 544 }