first.c

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