home *** CD-ROM | disk | FTP | other *** search
/ cs.rhul.ac.uk / www.cs.rhul.ac.uk.zip / www.cs.rhul.ac.uk / pub / rdp / rdp_cs3470.tar / rdp_gram.c < prev    next >
C/C++ Source or Header  |  1998-05-07  |  16KB  |  529 lines
  1. /****************************************************************************
  2. *
  3. * RDP release 1.50 by Adrian Johnstone (A.Johnstone@rhbnc.ac.uk) 20 December 1997
  4. *
  5. * rdp_gram.c - rdp grammar checking routines
  6. *
  7. * This file may be freely distributed. Please mail improvements to the author.
  8. *
  9. ****************************************************************************/
  10. #include <string.h>
  11. #include <ctype.h>
  12. #include "memalloc.h"
  13. #include "scan.h"
  14. #include "set.h"
  15. #include "symbol.h"
  16. #include "textio.h"
  17. #include "rdp_aux.h"
  18. #include "rdp_gram.h"
  19. #include "rdp_prnt.h"
  20. #include "rdp.h"
  21.  
  22. static int rdp_follow_changed;  /* repeat until done flag for follow sets */
  23.  
  24. void rdp_check_eoln(char * id)
  25. {
  26.   if (strcmp(id, "EOLN")== 0)
  27.     rdp_dir_newline_visible = 1;  /* Grammar contains an explicit EOLN */
  28. }
  29.  
  30. void rdp_check_token_valid(char * id)
  31. {
  32.   if (id == NULL)
  33.     return; 
  34.   
  35.   if (* id == 0)
  36.     text_message(TEXT_ERROR_ECHO, "empty tokens are not allowed: use [ ... ] instead\n"); 
  37.   /* Test for embedded spaces in token */
  38.   {
  39.     int bad = 0; 
  40.     
  41.     while (* id != 0)
  42.     {
  43.       bad |= !isgraph(* id); 
  44.       id++; 
  45.     }
  46.     
  47.     if (bad)
  48.       text_message(TEXT_ERROR_ECHO, "tokens must not contain spaces or control characters\n"); 
  49.   }
  50. }
  51.  
  52. void rdp_check_string_token_valid(char * id)
  53. {
  54.   rdp_check_token_valid(id);  /* make sure it's not empty or contains spaces */
  55.   if (*(id + 2)!= 0)
  56.     text_message(TEXT_ERROR_ECHO, "string delimiter tokens must be exactly one character long\n"); 
  57. }
  58.  
  59. void rdp_check_comment_token_valid(char * id)
  60. {
  61.   rdp_check_token_valid(id);  /* make sure it's not empty or contains spaces */
  62.   if (!(*(id + 2)== 0 || *(id + 3)== 0))
  63.     text_message(TEXT_ERROR_ECHO, "comment delimiter tokens must be less than three characters long\n"); 
  64. }
  65.  
  66. void rdp_check_prod_name_valid(char * id)
  67. {
  68.   if ((strncmp("rdp_", id, 4)== 0)||
  69.     (strncmp("RDP_", id, 4)== 0)||
  70.   (strncmp("args_", id, 5)== 0)||
  71.   (strncmp("mem_", id, 4)== 0)||
  72.   (strncmp("set_", id, 4)== 0)||
  73.   (strncmp("scan_", id, 5)== 0)||
  74.   (strncmp("SCAN_", id, 5)== 0)||
  75.   (strncmp("sym_", id, 4)== 0)||
  76.   (strncmp("text_", id, 5)== 0))
  77.   text_message(TEXT_ERROR_ECHO, "identifier \'%s\' begins with a reserved name\n", id); 
  78. }
  79.  
  80. static void rdp_count_productions(void * base)
  81. {
  82.   unsigned primaries = 0, 
  83.   internals = 0, 
  84.   codes = 0; 
  85.   
  86.   rdp_data * temp =(rdp_data *) symbol_next_symbol_in_scope(base); 
  87.   
  88.   while (temp != NULL)
  89.   {
  90.     if (temp->kind == K_PRIMARY)
  91.       primaries++; 
  92.     else if (temp->kind == K_CODE)
  93.       codes++; 
  94.     else
  95.       internals++; 
  96.     
  97.     temp =(rdp_data *) symbol_next_symbol_in_scope(temp); 
  98.   }
  99.   
  100.   if (rdp_verbose)
  101.     text_message(TEXT_INFO, "%u rules, %u tokens, %u actions, %u subrules\n", 
  102.   primaries, rdp_token_count - SCAN_P_TOP + 1, codes, internals); 
  103. }
  104.  
  105. static void rdp_first(rdp_data * prod)
  106. {
  107.   if (prod->in_use)           /* something has gone wrong */
  108.   {
  109.     text_message(TEXT_ERROR, "LL(1) violation - rule \'%s\' is left recursive\n", prod->id);  /* and return */
  110.     prod->ll1_violation = 1; 
  111.     return; 
  112.   }
  113.   
  114.   if (!prod->first_done)      /* something to do */
  115.   {
  116.     rdp_list * list = prod->list;  /* set up alternates pointer */
  117.     
  118.     prod->in_use = 1;         /* mark this production as being processed */
  119.     
  120.     if (prod->kind == K_SEQUENCE) /* sequences are treated differently */
  121.     {
  122.       prod->contains_null = 1;  /* set up list flag */
  123.       while (list != NULL && prod->contains_null) /* scan until non-empty alternate is found */
  124.       {
  125.         if (!list->production->first_done) /* do first */
  126.           rdp_first(list->production); 
  127.         
  128.         set_unite_set(& prod->first, & list->production->first);  /* add alternate first set to production first set */
  129.         prod->contains_null = list->production->contains_null;  /* set contains_null flag */
  130.         
  131.         list = list->next; 
  132.       }
  133.     }
  134.     else
  135.       while (list != NULL)    /* scan all alternates */
  136.     {
  137.       if (!list->production->first_done) /* do first */
  138.         rdp_first(list->production); 
  139.       
  140.       set_unite_set(& prod->first, & list->production->first);  /* add alternate first set to production first set */
  141.       prod->contains_null |= list->production->contains_null;  /* OR in contains_null flag */
  142.       list = list->next; 
  143.     }
  144.     prod->in_use = 0;         /* production is no longer in use */
  145.     prod->first_done = 1;     /* first set is now complete */
  146.     /* and set cardinality */
  147.     prod->first_cardinality = set_cardinality(& prod->first); 
  148.   }
  149. }
  150.  
  151. /* scan a sequence production for follow set changes */
  152. static void rdp_follow_sequence(rdp_data * prod)
  153. {
  154.   rdp_list * check = prod->list;  /* pointer to sequence list */
  155.   
  156.   while (check != NULL)       /* scan entire sequence and add to follow sets */
  157.   {
  158.     rdp_list * following = check;  /* temporary to look at followers */
  159.     unsigned old_cardinality = check->production->follow_cardinality; 
  160.     
  161.     do                        /* scan up list adding first sets of trailing productions */
  162.     {
  163.       following = following->next; 
  164.       if (following == NULL)  /* We hit end of sequence */
  165.         set_unite_set(& check->production->follow, & prod->follow); 
  166.       else
  167.         set_unite_set(& check->production->follow, & following->production->first); 
  168.     }
  169.     while (following != NULL && following->production->contains_null); 
  170.       
  171.     /* Update cardinality changed flag */
  172.     rdp_follow_changed |=((check->production->follow_cardinality =
  173.     set_cardinality(& check->production->follow)
  174.     )!= old_cardinality); 
  175.     
  176.     check = check->next;      /* step to next item in sequence */
  177.   }
  178. }
  179.  
  180. /* scan an alternate for follow set changes */
  181. static void rdp_follow_alternate(rdp_data * prod)
  182. {
  183.   rdp_list * check = prod->list;  /* pointer to alternate list */
  184.   
  185.   while (check != NULL)
  186.   {
  187.     unsigned old_cardinality = check->production->follow_cardinality; 
  188.     
  189.     set_unite_set(& check->production->follow, & prod->follow); 
  190.     
  191.     rdp_follow_changed |=((check->production->follow_cardinality =
  192.     set_cardinality(& check->production->follow)
  193.     )!= old_cardinality); 
  194.     check = check->next; 
  195.   }
  196. }
  197.  
  198. static void rdp_find_follow(void * base)
  199. {
  200.   rdp_data * temp; 
  201.   unsigned follow_pass = 0; 
  202.   
  203.   do
  204.   {
  205.     follow_pass++; 
  206.     rdp_follow_changed = 0; 
  207.     temp =(rdp_data *) symbol_next_symbol_in_scope(base); 
  208.     while (temp != NULL)
  209.     {
  210.       if (temp->kind == K_SEQUENCE) /* only need to scan sequences */
  211.         rdp_follow_sequence(temp); 
  212.       else
  213.         rdp_follow_alternate(temp); 
  214.       temp =(rdp_data *) symbol_next_symbol_in_scope(temp); 
  215.     }
  216.   }
  217.   while (rdp_follow_changed); 
  218.     
  219.   if (rdp_verbose)
  220.     text_message(TEXT_INFO, "Follow sets stabilised after %u pass%s\n", follow_pass, follow_pass == 1 ? "": "es"); 
  221.   
  222. }
  223.  
  224. static int rdp_check_identifier(char * id)
  225. {
  226.   rdp_data * s =(rdp_data *) symbol_lookup_key(rdp, & id, NULL); 
  227.   
  228.   if (s != NULL)
  229.   {
  230.     if (s->kind == K_PRIMARY)
  231.     {
  232.       text_message(TEXT_ERROR, "identifier \'%s\' is a C++ reserved word or library identifier\n", id); 
  233.       return 1; 
  234.     }
  235.   }
  236.   return 0; 
  237. }
  238.  
  239. static int rdp_check_reserved_words(void)
  240. {
  241.   int bad = 0, 
  242.   temp = 0; 
  243.   char * rdp_reserved_words[]= {RDP_RESERVED_WORDS, NULL}; 
  244.   
  245.   while (rdp_reserved_words[temp]!= NULL)
  246.     bad |= rdp_check_identifier(rdp_reserved_words[temp++]); 
  247.   
  248.   return bad; 
  249. }
  250.  
  251. /* check for empty alternates. mark up code sequences while we're at it */
  252. static int rdp_check_empties(void * base)
  253. {
  254.   int bad = 0; 
  255.   rdp_data * temp =(rdp_data *) symbol_next_symbol_in_scope(base); 
  256.   
  257.   while (temp != NULL)
  258.   {
  259.     rdp_list * list = temp->list; 
  260.     int k = temp->kind, 
  261.     bad_alternate = 1; 
  262.     
  263.     if (k == K_PRIMARY && temp->call_count == 0 && !temp->comment_only)
  264.       text_message(TEXT_WARNING, "rule \'%s\' never called so deleted\n", temp->id); 
  265.     
  266.     if (list == NULL && k == K_PRIMARY)
  267.     {
  268.       text_message(TEXT_ERROR, "rule \'%s\' is empty\n", temp->id); 
  269.       bad = 1; 
  270.     }
  271.     
  272.     if (k == K_SEQUENCE)      /* check for empty alternates and mark up code */
  273.     {
  274.       while (list != NULL)
  275.       {
  276.         if (list->production->kind == K_CODE) /* check code position */
  277.           if (list->next == NULL) /* last in list? */
  278.           list->production->code_terminator = 1; 
  279.         else if (list->next->production->kind == K_CODE) /* is the next one code? */
  280.           list->next->production->code_successor = 1;  /* next one is code successor */
  281.         else
  282.           list->production->code_terminator = 1;  /* this one is code terminator */
  283.         
  284.         if (list->production->kind != K_CODE)
  285.           bad_alternate = 0; 
  286.         list = list->next; 
  287.       }
  288.     }
  289.     else
  290.       bad_alternate = 0; 
  291.     
  292.     if (bad_alternate)
  293.     {
  294.       if (temp->list == NULL)
  295.       {
  296.         text_message(TEXT_ERROR, "LL(1) violation - alternate \'%s\' is empty\n", temp->id); 
  297.         temp->ll1_violation = 1; 
  298.       }
  299.       else
  300.       {
  301.         temp->code_only = 1; 
  302.       }
  303.       bad = 1; 
  304.     }
  305.     temp =(rdp_data *) symbol_next_symbol_in_scope(temp); 
  306.   }
  307.   
  308.   /* Now go over again updating primaries to mark code only productions */
  309.   temp =(rdp_data *) symbol_next_symbol_in_scope(base); 
  310.   
  311.   while (temp != NULL)
  312.   {
  313.     if (temp->kind == K_PRIMARY && temp->list != NULL)
  314.       if (temp->list->next == NULL && temp->list->production->code_only)
  315.       temp->code_only = 1; 
  316.     temp =(rdp_data *) symbol_next_symbol_in_scope(temp); 
  317.   }
  318.   return bad; 
  319. }
  320.  
  321. static void rdp_find_first(void * base)
  322. {
  323.   rdp_data * temp =(rdp_data *) symbol_next_symbol_in_scope(base); 
  324.   
  325.   while (temp != NULL)
  326.   {
  327.     rdp_first(temp); 
  328.     temp =(rdp_data *) symbol_next_symbol_in_scope(temp); 
  329.   }
  330. }
  331.  
  332. /* Check if we have a nullable alternate inside a nullable iterator */
  333. static int rdp_check_nested_nullable(void * base)
  334. {
  335.   int bad = 0; 
  336.   rdp_data * temp =(rdp_data *) symbol_next_symbol_in_scope(base); 
  337.   
  338.   while (temp != NULL)
  339.   {
  340.     if (set_includes_element(& rdp_production_set, temp->kind)&& temp->kind != K_SEQUENCE)
  341.     {
  342.       rdp_list * inner = temp->list; 
  343.       
  344.       while (inner != NULL)
  345.       {
  346.         
  347.         if (temp->lo == 0 && inner->production->contains_null)
  348.         {
  349.           text_message(TEXT_ERROR, "LL(1) violation - rule \'%s\'\n is nullable but contains the nullable subrule\n", temp->id); 
  350.           text_printf(" %s ::= ", inner->production->id); 
  351.           rdp_print_sub_item(inner->production, 1); 
  352.           text_printf(".\n"); 
  353.           bad = 1; 
  354.           temp->ll1_violation = 1; 
  355.           inner->production->ll1_violation = 1; 
  356.         }
  357.         inner = inner->next; 
  358.       }
  359.     }
  360.     temp =(rdp_data *) symbol_next_symbol_in_scope(temp); 
  361.   }
  362.   return bad; 
  363. }
  364. static int rdp_check_disjoint(void * base)
  365. {
  366.   int bad = 0; 
  367.   set_ work = SET_NULL; 
  368.   
  369.   rdp_data * temp =(rdp_data *) symbol_next_symbol_in_scope(base); 
  370.   
  371.   while (temp != NULL)
  372.   {
  373.     if (set_includes_element(& rdp_production_set, temp->kind)&& temp->kind != K_SEQUENCE)
  374.     {
  375.       rdp_list * left = temp->list; 
  376.       
  377.       while (left != NULL)
  378.       {
  379.         rdp_list * right = left->next; 
  380.         
  381.         while (right != NULL)
  382.         {
  383.           /* First check for disjoint on epsilon */
  384.           if (left->production->contains_null && right->production->contains_null)
  385.           {
  386.             text_message(TEXT_ERROR, "LL(1) violation - rule \'%s\'\n", temp->id); 
  387.             text_printf(" productions %s ::= ", left->production->id); 
  388.             rdp_print_sub_item(left->production, 1); 
  389.             text_printf(".\n and %s ::= ", right->production->id); 
  390.             rdp_print_sub_item(right->production, 1); 
  391.             text_printf(".\n are both nullable \n"); 
  392.             left->production->ll1_violation = 1; 
  393.             right->production->ll1_violation = 1; 
  394.             bad = 1; 
  395.           }
  396.           
  397.           set_assign_set(& work, & left->production->first); 
  398.           set_intersect_set(& work, & right->production->first); 
  399.           
  400.           if (set_cardinality(& work)!= 0)
  401.           {
  402.             text_message(TEXT_ERROR, "LL(1) violation - rule \'%s\'\n", temp->id); 
  403.             text_printf(" productions %s ::= ", left->production->id); 
  404.             rdp_print_sub_item(left->production, 1); 
  405.             text_printf(".\n and %s ::= ", right->production->id); 
  406.             rdp_print_sub_item(right->production, 1); 
  407.             text_printf(".\n share these start tokens: "); 
  408.             set_print_set(& work, rdp_token_string, 78); 
  409.             text_printf("\n"); 
  410.             left->production->ll1_violation = 1; 
  411.             right->production->ll1_violation = 1; 
  412.             bad = 1; 
  413.           }
  414.           right = right->next; 
  415.         }
  416.         left = left->next; 
  417.       }
  418.     }
  419.     temp =(rdp_data *) symbol_next_symbol_in_scope(temp); 
  420.   }
  421.   return bad; 
  422. }
  423.  
  424. static int rdp_check_nullable(void * base)
  425. {
  426.   int bad = 0; 
  427.   rdp_data * temp =(rdp_data *) symbol_next_symbol_in_scope(base); 
  428.   set_ work = SET_NULL; 
  429.   
  430.   while (temp != NULL)
  431.   {
  432.     if (temp->contains_null &&(temp->kind != K_CODE))
  433.     {
  434.       set_assign_set(& work, & temp->first); 
  435.       set_intersect_set(& work, & temp->follow); 
  436.       
  437.       if (set_cardinality(& work)!= 0)
  438.       {
  439.         text_message(TEXT_ERROR, "LL(1) violation - rule\n %s ::= ", temp->id); 
  440.         rdp_print_sub_item(temp, 1); 
  441.         text_printf(".\n contains null but first and follow sets both include: "); 
  442.         
  443.         set_print_set(& work, rdp_token_string, 78); 
  444.         text_printf("\n"); 
  445.         temp->ll1_violation = 1; 
  446.         bad = 1; 
  447.       }
  448.     }
  449.     temp =(rdp_data *) symbol_next_symbol_in_scope(temp); 
  450.   }
  451.   return bad; 
  452. }
  453.  
  454. static void rdp_update_follow_sets(void * base)
  455. {
  456.   rdp_data * temp =(rdp_data *) symbol_next_symbol_in_scope(base); 
  457.   
  458.   while (temp != NULL)
  459.   {
  460.     if (temp->kind == K_LIST && temp->hi != 1 && temp->supplementary_token == NULL)
  461.     {
  462.       set_unite_set(& temp->follow, & temp->first); 
  463.       temp->follow_cardinality = set_cardinality(& temp->follow); 
  464.     }
  465.     temp =(rdp_data *) symbol_next_symbol_in_scope(temp); 
  466.   }
  467. }
  468.  
  469. int rdp_bad_grammar(void * base)
  470. {
  471.   int bad = 0; 
  472.   
  473.   /* Check for empties */
  474.   if (rdp_verbose)
  475.     text_message(TEXT_INFO, "Checking for empty alternates\n"); 
  476.   bad |= rdp_check_empties(base); 
  477.   
  478.   /* Count productions and produce statistics */
  479.   rdp_count_productions(base); 
  480.   
  481.   /* Check promotion operators on start production */
  482.   if (rdp_start_prod->promote_default != PROMOTE_DONT)
  483.     text_message(TEXT_WARNING, "default promotion operator \'%s\' on start production \'%s\' will not be applied at top level\n", 
  484.   rdp_start_prod->promote_default == PROMOTE ? "^": 
  485.   rdp_start_prod->promote_default == PROMOTE_AND_COPY ? "^^": "??", 
  486.   rdp_start_prod->id); 
  487.   
  488.   /* find first sets */
  489.   if (rdp_verbose)
  490.     text_message(TEXT_INFO, "Generating first sets\n"); 
  491.   rdp_find_first(base); 
  492.   
  493.   /* find follow sets */
  494.   if (rdp_verbose)
  495.     text_message(TEXT_INFO, "Generating follow sets\n"); 
  496.   rdp_find_follow(base); 
  497.   
  498.   /* check for C reserved words */
  499.   if (rdp_verbose)
  500.     text_message(TEXT_INFO, "Checking for clashes with reserved words\n"); 
  501.   bad |= rdp_check_reserved_words(); 
  502.   
  503.   /* check that for each production, all alternates have unique start tokens */
  504.   if (rdp_verbose)
  505.     text_message(TEXT_INFO, "Checking for disjoint first sets\n"); 
  506.   bad |= rdp_check_disjoint(base); 
  507.   
  508.   /* check nullable brackets don't contain nullable productions */
  509.   if (rdp_verbose)
  510.     text_message(TEXT_INFO, "Checking for nested nullable subrules\n"); 
  511.   bad |= rdp_check_nested_nullable(base); 
  512.   
  513.   /* check that first(a) - follow (a) is empty for nullable a */
  514.   if (rdp_verbose)
  515.     text_message(TEXT_INFO, "Checking nullable rules\n"); 
  516.   bad |= rdp_check_nullable(base); 
  517.   
  518.   /* add first() to follow() for iterations so that error handling doesn't just eat entire file! */
  519.   if (rdp_verbose)
  520.     text_message(TEXT_INFO, "Updating follow sets\n"); 
  521.   rdp_update_follow_sets(base); 
  522.   /* re-close follow sets */
  523.   rdp_find_follow(base); 
  524.   
  525.   return bad; 
  526. }
  527.  
  528. /* End of rdp_gram.c */
  529.