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_cs3460.tar / rdp_aux.c < prev    next >
C/C++ Source or Header  |  1998-05-07  |  12KB  |  346 lines
  1. /****************************************************************************
  2. *
  3. * RDP release 1.50 by Adrian Johnstone (A.Johnstone@rhbnc.ac.uk) 20 December 1997
  4. *
  5. * rdp_aux.c - rdp semantic 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 <stdio.h>
  13. #include "graph.h"
  14. #include "memalloc.h"
  15. #include "scan.h"
  16. #include "set.h"
  17. #include "symbol.h"
  18. #include "textio.h"
  19. #include "rdp_aux.h"
  20. #include "rdp_gram.h"
  21. #include "rdp_prnt.h"
  22. #include "rdp.h"
  23.  
  24. extern void * codes, * rdp, * tokens; 
  25.  
  26. void * rdp_base;              /* symbol table for the parser */
  27. extern char * rdp_sourcefilename;  /* source file name loaded by main line */
  28.  
  29. int
  30. rdp_comment_only = 0,         /* Flag to track productions that contain only comments */
  31. rdp_rule_count = 0,           /* Number of rules declared * 2 */
  32. rdp_force = 0,                /* force output files flag */
  33. rdp_error_production_name = 0,  /* flag to force writing of production name into error messages */
  34. rdp_expanded = 0,             /* flag to generate expanded bnf listing */
  35. rdp_undeclared_symbols_are_tokens,  /* convert symbols flag */
  36. rdp_parser_only = 0,          /* omit semantic actions flag */
  37. rdp_trace = 0;                /* add trace messages flag */
  38.  
  39. char
  40. * rdp_primary_id;             /* identifier for parent production */
  41.  
  42. unsigned rdp_component;       /* sub-production component number */
  43. unsigned rdp_token_count = SCAN_P_TOP;  /* number of tokens + extendeds */
  44.  
  45. rdp_data * rdp_start_prod; 
  46.  
  47. char
  48. * rdp_dir_title = "rdparser",  /* string from TITLE directive */
  49. * rdp_dir_suffix = "",        /* string from SUFFIX directive */
  50. * rdp_dir_pre_parse = NULL,   /* string from PRE_PARSE directive */
  51. * rdp_dir_post_parse = NULL,  /* string from POST_PARSE directive */
  52. * rdp_dir_output_file = NULL,  /* string from OUTPUT_FILE directive */
  53. * rdp_dir_tree_fields = "";   /* fild names for tree node from TREE directive */
  54.  
  55. unsigned
  56. rdp_dir_tree = 0,             /* TREE flag */
  57. rdp_dir_epsilon_tree = 0,     /* EPSILON_TRTEE tree flag */
  58. rdp_dir_annotated_epsilon_tree = 0,  /* ANNOTATED_EPSILON_TRTEE tree flag */
  59. rdp_dir_case_insensitive = 0,  /* CASE_INSENSITIVE flag */
  60. rdp_dir_show_skips = 0,       /* SHOW_SKIPS flag */
  61. rdp_dir_newline_visible = 0,  /* NEWLINE_VISIBLE flag */
  62. rdp_dir_passes = 1,           /* PASSES directive */
  63. rdp_dir_hash_size = 101,      /* HASH_SIZE directive */
  64. rdp_dir_hash_prime = 31,      /* HASH_PRIME dirctive */
  65. rdp_dir_max_errors = 25,      /* MAX_ERRORS directive */
  66. rdp_dir_max_warnings = 100;   /* MAX_WARNINGS directive */
  67.  
  68. unsigned long rdp_dir_text_size = 35000l;  /* TEXT_SIZE directive */
  69. unsigned long rdp_dir_tab_width = 8;  /* TAB_WIDTH directive */
  70.  
  71. rdp_string_list
  72. * rdp_dir_include = NULL;     /* strings from INCLUDE directives */
  73.  
  74. rdp_arg_list
  75. * rdp_dir_args = NULL;        /* data from ARG_* directives */
  76.  
  77. rdp_table_list
  78. * rdp_dir_symbol_table = NULL;  /* data from SYMBOL_TABLE directives */
  79.  
  80. rdp_index_table_list
  81. * rdp_dir_index_table = NULL;  /* data from SYMBOL_TABLE directives */
  82.  
  83. set_
  84. rdp_production_set; 
  85.  
  86. void rdp_add_arg(enum arg_kind_type kind, char * key, char * var, char * desc)
  87. {
  88.   rdp_arg_list * temp =(rdp_arg_list *) mem_malloc(sizeof(rdp_arg_list)); 
  89.   
  90.   temp->kind = kind; 
  91.   temp->key = key; 
  92.   temp->var = var; 
  93.   temp->desc = desc; 
  94.   temp->next = rdp_dir_args; 
  95.   rdp_dir_args = temp; 
  96. }
  97.  
  98. rdp_data * rdp_find(char * id, kind_type kind, symbol_type symbol)
  99. {
  100.   rdp_data * temp; 
  101.   void * table; 
  102.   
  103.   /* Figure out which table to use */
  104.   if (kind == K_CODE)
  105.     table = codes; 
  106.   else if (kind == K_TOKEN || kind == K_EXTENDED)
  107.     table = tokens; 
  108.   else table = rdp; 
  109.     
  110.   if ((temp =(rdp_data *) symbol_lookup_key(table, & id, NULL))== NULL)
  111.   {
  112.     if (symbol == RDP_OLD && rdp_undeclared_symbols_are_tokens)
  113.     {
  114.       text_message(TEXT_WARNING_ECHO, "Undeclared symbol \'%s\' converted to token\n", id); 
  115.       rdp_process_token(id); 
  116.     }
  117.     else
  118.     {
  119.       if (symbol == RDP_OLD)
  120.         text_message(TEXT_ERROR_ECHO, "Undeclared symbol \'%s\'\n", id); 
  121.       temp =(rdp_data *) symbol_new_symbol(sizeof(rdp_data)); 
  122.       temp->id = id; 
  123.       symbol_insert_symbol(table, temp); 
  124.       temp->token = SCAN_P_ID; 
  125.       temp->kind = kind; 
  126.       temp->hi = temp->lo = 1;  /* set instance numbers to one */
  127.       temp->first_cardinality = 0; 
  128.       set_assign_element(& temp->follow, SCAN_P_EOF); 
  129.       temp->follow_cardinality = 1; 
  130.       temp->return_type_stars = 0; 
  131.       switch (kind)
  132.       {
  133.         case K_INTEGER: 
  134.         temp->return_type = "long int"; 
  135.         break; 
  136.         case K_TOKEN: 
  137.         temp->return_type = "int"; 
  138.         break; 
  139.         case K_REAL: 
  140.         temp->return_type = "double"; 
  141.         break; 
  142.         case K_STRING: 
  143.         temp->return_type = "char"; 
  144.         temp->return_type_stars = 1; 
  145.         break; 
  146.         default: 
  147.         temp->return_type = "void"; 
  148.         break; 
  149.       }
  150.     }
  151.   }
  152.   else
  153.     if (symbol == RDP_NEW)
  154.     text_message(TEXT_ERROR_ECHO, "Doubly declared symbol \'%s\'\n", id); 
  155.   
  156.   return temp; 
  157. }
  158.  
  159. rdp_data * rdp_find_extended(char * open, char * close, int token)
  160. {
  161.   rdp_data * result; 
  162.   
  163.   rdp_check_token_valid(open); 
  164.   rdp_check_token_valid(close); 
  165.   result = rdp_find(open, K_EXTENDED, RDP_ANY); 
  166.   result->token_value = token; 
  167.   result->close = close; 
  168.   result->return_type = "char"; 
  169.   result->return_type_stars = 1; 
  170.   return result; 
  171. }
  172.  
  173.  
  174. void rdp_pre_parse(void)
  175. {
  176.   rdp_dir_output_file = text_force_filetype(rdp_sourcefilename, "out"); 
  177.   rdp_base = symbol_new_scope(rdp, "parser"); 
  178.   set_assign_list(& rdp_production_set, K_PRIMARY, K_SEQUENCE, K_LIST, SET_END); 
  179.   
  180.   rdp_add_arg(ARG_BLANK, NULL, NULL, ""); 
  181.   rdp_add_arg(ARG_BOOLEAN, "f", "rdp_filter", "Filter mode (read from stdin and write to stdout)"); 
  182.   rdp_add_arg(ARG_BOOLEAN, "l", "rdp_line_echo", "Make a listing"); 
  183.   rdp_add_arg(ARG_STRING, "o", "rdp_outputfilename", "Write output to filename"); 
  184.   rdp_add_arg(ARG_BOOLEAN, "s", "rdp_symbol_echo", "Echo each scanner symbol as it is read"); 
  185.   rdp_add_arg(ARG_BOOLEAN, "S", "rdp_symbol_statistics", "Print summary symbol table statistics"); 
  186.   rdp_add_arg(ARG_NUMERIC, "t", "rdp_tabwidth", "Tab expansion width (default 8)"); 
  187.   rdp_add_arg(ARG_NUMERIC, "T", "rdp_textsize", "Text buffer size in bytes for scanner (default 20000)"); 
  188.   rdp_add_arg(ARG_BOOLEAN, "v", "rdp_verbose", "Set verbose mode"); 
  189.   rdp_add_arg(ARG_STRING, "V", "rdp_vcg_filename", "Write derivation tree to filename in VCG format"); 
  190.   
  191.   rdp_find("ID", K_STRING, RDP_ANY)->token_value = SCAN_P_ID;  /* add predefined primitive productions */
  192.   rdp_find("INTEGER", K_INTEGER, RDP_ANY)->token_value = SCAN_P_INTEGER; 
  193.   rdp_find("REAL", K_REAL, RDP_ANY)->token_value = SCAN_P_REAL; 
  194.   rdp_find("EOLN", K_STRING, RDP_ANY)->token_value = SCAN_P_EOLN; 
  195. }
  196.  
  197. static void rdp_order_tokens(void * base)
  198. {
  199.   rdp_data * temp =(rdp_data *) symbol_next_symbol_in_scope(base); 
  200.   
  201.   while (temp != NULL)
  202.   {
  203.     if (temp->kind == K_TOKEN || temp->kind == K_EXTENDED)
  204.     {
  205.       temp->extended_value = temp->token_value; 
  206.       temp->token_value = rdp_token_count++; 
  207.     }
  208.     temp =(rdp_data *) symbol_next_symbol_in_scope(temp); 
  209.   }
  210.   
  211.   /* now set up start sets for tokens, code and primitives */
  212.   temp =(rdp_data *) symbol_next_symbol_in_scope(base); 
  213.   while (temp != NULL)
  214.   {
  215.     if (temp->kind == K_TOKEN || temp->kind == K_INTEGER ||
  216.       temp->kind == K_REAL || temp->kind == K_STRING ||
  217.     temp->kind == K_EXTENDED)
  218.     {
  219.       set_unite_element(& temp->first, temp->token_value); 
  220.       temp->first_cardinality = set_cardinality(& temp->first); 
  221.       set_unite_element(& temp->follow, SCAN_P_EOF); 
  222.       temp->follow_cardinality = set_cardinality(& temp->follow); 
  223.       
  224.       temp->first_done = 1; 
  225.     }
  226.     else if (temp->kind == K_LIST && temp->supplementary_token != NULL)
  227.     {
  228.       set_unite_element(& temp->follow, temp->supplementary_token->token_value); 
  229.       temp->follow_cardinality = set_cardinality(& temp->follow); 
  230.     }
  231.     temp =(rdp_data *) symbol_next_symbol_in_scope(temp); 
  232.   }
  233. }
  234.  
  235. static void rdp_add_continuations(void * base)
  236. {
  237.   rdp_data * temp =(rdp_data *) symbol_next_symbol_in_scope(base); 
  238.   char * last_token = "";     /* remember most recent token name */
  239.   int tokens_added = 0; 
  240.   
  241.   if (rdp_verbose)
  242.     text_message(TEXT_INFO, "Checking for continuation tokens\n"); 
  243.   
  244.   while (temp != NULL)        /* scan over all productions */
  245.   {
  246.     if (temp->kind == K_TOKEN || temp->kind == K_EXTENDED)
  247.     {
  248.       char * lo = last_token, 
  249.       * hi = temp->id; 
  250.       
  251.       if (!text_is_valid_C_id(hi)) /* ignore identifiers */
  252.       {
  253.         /* rdp_find common prefix */
  254.         while (* lo == * hi && * hi != 0) /* bump while they are identical */
  255.         {
  256.           lo++; 
  257.           hi++; 
  258.         }
  259.         
  260.         hi++;                 /* we can't have two identical tokens, so at worst this will move to a null */
  261.         
  262.         /* now add continuations */
  263.         /* is the first non-identical character the one before the terminating null ? */
  264.         while (*(hi)!= 0)     /* add a continuation */
  265.         {
  266.           /* insert the sub-string */
  267.           char * c = temp->id, 
  268.           * continuation_name = text_top;  /* remember start position */
  269.           
  270.           while (c != hi)
  271.             text_insert_char(* c++);  /* copy identifier */
  272.           text_insert_char(0);  /* add a terminating null */
  273.           
  274.           if (rdp_verbose)
  275.             text_message(TEXT_INFO, "Adding continuation token \'%s\'\n", continuation_name); 
  276.           
  277.           tokens_added = 1; 
  278.           
  279.           rdp_find(continuation_name, K_TOKEN, RDP_ANY); 
  280.           
  281.           hi++; 
  282.         }
  283.       }
  284.       
  285.       last_token = temp->id; 
  286.     }
  287.     temp =(rdp_data *) symbol_next_symbol_in_scope(temp); 
  288.   }
  289.   if (rdp_verbose && !tokens_added)
  290.     text_message(TEXT_INFO, "No continuation tokens needed\n"); 
  291.   
  292. }
  293.  
  294. void rdp_post_parse(char * outputfilename, int force)
  295. {
  296.   void
  297.   * tokens_base = symbol_get_scope(tokens), 
  298.   * rdp_base = symbol_get_scope(rdp); 
  299.   
  300.   locals_data * local =(locals_data *) symbol_new_symbol(sizeof(locals_data)); 
  301.   
  302.   local->id = "result"; 
  303.   symbol_insert_symbol(locals, local); 
  304.   
  305.   symbol_sort_scope(tokens, tokens_base);  /* sort productions into alphabetical order */
  306.   rdp_add_continuations(tokens_base);  /* scan through tokens and add any necessry continuations */
  307.   symbol_sort_scope(tokens, tokens_base);  /* re-sort productions into alphabetical order */
  308.   rdp_order_tokens(tokens_base);  /* apply token numbers to token productions */
  309.   rdp_order_tokens(rdp_base);  /* apply token numbers to token productions */
  310.   rdp_make_token_string(tokens_base);  /* make a string with all token names in it */
  311.   
  312.   symbol_sort_scope(rdp, rdp_base);  /* sort productions into alphabetical order */
  313.   rdp_bad_grammar(rdp_base);  /* find the non-LL(1)-isms */
  314.   
  315.   if (rdp_expanded)           /* print out expanded BNF */
  316.     rdp_dump_extended(rdp_base); 
  317.   
  318.   if (text_total_errors()> 0)
  319.   {
  320.     if (force)
  321.       text_message(TEXT_WARNING, "Grammar is not LL(1) but -F set: writing files\n"); 
  322.     else
  323.       text_message(TEXT_FATAL, "Run aborted without creating output files - rerun with -F to override\n"); 
  324.   }
  325.   
  326.   rdp_print_header(text_force_filetype(outputfilename, "h"));  /* dump header file */
  327.   
  328.   rdp_print_parser(text_force_filetype(outputfilename, "c"), rdp_base);  /* dump main file */
  329.   
  330.   if (rdp_verbose)            /* see how much text buffer space we used */
  331.     text_print_statistics(); 
  332. }
  333.  
  334. void * rdp_process_token(char * name)
  335. {
  336.   rdp_data * result; 
  337.   
  338.   rdp_check_token_valid(name); 
  339.   result = rdp_find(name, K_TOKEN, RDP_ANY); 
  340.   result->call_count++;       /* increment call count */
  341.   
  342.   return result; 
  343. }
  344.  
  345. /* End of rdp_aux.c */
  346.