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                               /*
 380                                * This rule starts with a terminal. Ignore it.
 381                                * We could add it as an optimization. TODO
 382                                */
 383                               if (next_symbol->terminal)
 384                                 {
 385                                   rule_delete (next_rule);
 386                                 }
 387                               /* This is an indirect recursive rule. */
 388                               else if (next_symbol->value == symbol->value)
 389                                 {
 390                                   first_set->recursive =
 391                                     g_list_prepend (first_set->recursive,
 392                                                     next_rule);
 393                                 }
 394                               /* Next time we treat current nonterminal,
 395                                * we will check this rule directly. */
 396                               else
 397                                 {
 398                                   new_rules = g_list_prepend (new_rules, next_rule);
 399                                 }
 400                             }
 401                           next_rules = g_list_next (next_rules);
 402                         }
 403                     }
 404                   /*
 405                    * If nonterminal has recursive rules, we should expect
 406                    * more rules to add here and so we will check it again
 407                    * in the next iteration. Keep the rule. If there is only
 408                    * indirect recursiveness, we will detect it through the
 409                    * rules we have added before. We should remove it in this
 410                    * case so we make advance.
 411                    */
 412                   if (next_set->recursive != NULL)
 413                     {
 414                       new_rules = g_list_prepend (new_rules, rule);
 415                     }
 416                   else
 417                     {
 418                       rule_delete (rule);
 419                     }
 420                 }
 421               else
 422                 {
 423                   assert (TRUE);
 424                 }
 425
 426             }
 427
 428           rules = g_list_next (rules);
 429
 430         }
 431
 432       g_list_free (first_set->rules);
 433       first_set->rules = new_rules;
 434
 435     }
 436
 437 }
 438
 439 void first_check (gpointer key, gpointer val, gpointer data)
 440 {
 441
 442   symbol_t* symbol;
 443   first_set_t* first_set;
 444   gboolean* stop;
 445
 446   symbol = (symbol_t*) key;
 447   first_set = (first_set_t*) val;
 448   stop = (gboolean*) data;
 449
 450   assert (symbol->terminal == FALSE);
 451
 452   /* If there is anything besides terminals in the first set,
 453    * we must iterate more and remove all of them. */
 454   if (first_set->rules != NULL || first_set->recursive != NULL)
 455     {
 456       *stop = FALSE;
 457     }
 458
 459 }
 460
 461 /*
 462  * Calculate the first set for every nonterminal symbol in the grammar.
 463  * We should iterate through the rules for each nonterminal until only
 464  * terminals are known to be in the first set of it.
 465  */
 466 GHashTable* grammar_first (grammar_t* grammar)
 467 {
 468   GHashTable* first;
 469   gboolean stop;
 470   first = g_hash_table_new_full (symbol_hash, symbol_equal,
 471                                  g_free,
 472                                  first_set_delete);
 473   g_hash_table_foreach (grammar->grammar, first_prepare, first);
 474   do
 475     {
 476       g_hash_table_foreach (first, first_iterate, first);
 477       stop = TRUE;
 478       g_hash_table_foreach (first, first_check, &stop);
 479     } while (stop == FALSE);
 480   return first;
 481 }
 482
 483 static void put_key_on_list (gpointer key, gpointer val, gpointer data)
 484 {
 485   GList** l;
 486   l = (GList**) data;
 487   *l = g_list_prepend (*l, symbol_copy (key));
 488 }
 489
 490 GList* first_get (GHashTable* first, symbol_t* symbol)
 491 {
 492
 493   first_set_t* first_set;
 494   GList* l;
 495   l = NULL;
 496   if (g_hash_table_lookup_extended (first, symbol, NULL,
 497                                     (gpointer*) &first_set))
 498     {
 499       if (first_set->has_empty)
 500         l = g_list_prepend (l, symbol_new (TRUE, 0));
 501       g_hash_table_foreach (first_set->terminals, put_key_on_list, &l);
 502     }
 503   return l;
 504
 505 }
 506
 507 GList* first_rule (GHashTable* first, rule_t* rule)
 508 {
 509
 510   GHashTable* terminals;
 511   GList* symbols;
 512   GList* l;
 513
 514   l = NULL;
 515
 516   symbols = grammar_get_rule (rule);
 517
 518   terminals = g_hash_table_new_full (symbol_hash, symbol_equal, g_free, NULL);
 519
 520   while (symbols != NULL)
 521     {
 522       first_set_t* first_set;
 523       symbol_t* symbol;
 524       symbol = (symbol_t*) symbols->data;
 525       if (symbol->terminal)
 526         {
 527           g_hash_table_insert (terminals, symbol_copy (symbol), NULL);
 528           break;
 529         }
 530       if (!g_hash_table_lookup_extended (first, symbol, NULL,
 531                                          (gpointer*) &first_set))
 532         {
 533           g_hash_table_destroy (terminals);
 534           return NULL;
 535         }
 536       first_set_union (terminals, first_set->terminals);
 537       if (first_set->has_empty == FALSE)
 538         break;
 539       symbols = g_list_next (symbols);
 540     }
 541
 542   if (symbols == NULL)
 543     l = g_list_prepend (l, symbol_new (TRUE, 0));
 544   g_hash_table_foreach (terminals, put_key_on_list, &l);
 545
 546   g_hash_table_destroy (terminals);
 547
 548   return l;
 549
 550 }
 551
 552 void first_print_symbol (gpointer key, gpointer val, gpointer data)
 553 {
 554   symbol_t* symbol;
 555   symbol = (symbol_t*) key;
 556   fprintf (stdout, "%s\n", g_quark_to_string (symbol->value));
 557 }
 558
 559 void first_print_set (gpointer key, gpointer val, gpointer data)
 560 {
 561   symbol_t* symbol;
 562   first_set_t* first_set;
 563   symbol = (symbol_t*) key;
 564   first_set = (first_set_t*) val;
 565   fprintf (stdout, "FIRST of %s:\n", g_quark_to_string (symbol->value));
 566   if (first_set->has_empty)
 567     fprintf (stdout, "empty symbol\n");
 568   g_hash_table_foreach (first_set->terminals, first_print_symbol, NULL);
 569 }
 570
 571 void first_print (GHashTable* first)
 572 {
 573   g_hash_table_foreach (first, first_print_set, NULL);
 574 }