home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 290_01 / main.c < prev    next >
C/C++ Source or Header  |  1990-05-14  |  17KB  |  600 lines
  1. /*
  2. **    file:        main.c
  3. **    purpose:    Tool to generate fast lexical analyzers
  4. **    mods:        1989.12.30 - Roberto Artigas Jr
  5. **            Added usage() routine
  6.  *
  7.  *
  8.  * Copyright (c) 1987, the University of California
  9.  * 
  10.  * The United States Government has rights in this work pursuant to
  11.  * contract no. DE-AC03-76SF00098 between the United States Department of
  12.  * Energy and the University of California.
  13.  * 
  14.  * This program may be redistributed.  Enhancements and derivative works
  15.  * may be created provided the new works, if made available to the general
  16.  * public, are made available for use by anyone.
  17.  *
  18.  *
  19.  * ver   date  who    remarks
  20.  * ---   ----  ------ -------------------------------------------------------
  21.  * 04b 30sep87 kg, vp .implemented (part of) Van Jacobson's fast scanner design
  22.  * 04a 27jun86 vp     .translated from Ratfor into C
  23.  * 01a 22aug83 vp     .written.  Original version by Jef Poskanzer.
  24.  */
  25. #define MSC
  26.  
  27. #ifdef TURBOC
  28. #include <io.h>  /* for mktemp() prototype */
  29. #include <dir.h>
  30. #endif
  31.  
  32. #ifdef MSC
  33. #include <io.h>  /* for mktemp() prototype */
  34. #endif
  35.  
  36. #include "flexdef.h"
  37.  
  38. #include "main.h"
  39. #include "misc.h"
  40. #include "nfa.h"
  41. #include "tblcmp.h"
  42. #include "ecs.h"
  43.  
  44. /* these globals are all defined and commented in flexdef.h */
  45. int printstats, syntaxerror, eofseen, ddebug, trace, spprdflt;
  46. int interactive, caseins, useecs, fulltbl, usemecs, reject;
  47. int fullspd, gen_line_dirs;
  48. int datapos, dataline, linenum;
  49. FILE *skelfile = NULL;
  50. char *infilename = NULL;
  51. int onestate[ONE_STACK_SIZE], onesym[ONE_STACK_SIZE];
  52. int onenext[ONE_STACK_SIZE], onedef[ONE_STACK_SIZE], onesp;
  53. int current_mns;
  54. int accnum, *firstst, *lastst, *finalst, *transchar;
  55. int *trans1, *trans2, *accptnum, lastnfa;
  56. int numtemps, numprots, protprev[MSP], protnext[MSP], prottbl[MSP];
  57. int protcomst[MSP], firstprot, lastprot, protsave[PROT_SAVE_SIZE];
  58. int numecs, nextecm[CSIZE + 1], ecgroup[CSIZE + 1], nummecs, tecfwd[CSIZE + 1];
  59. int tecbck[CSIZE + 1];
  60. int lastsc, current_max_scs, *scset, *scbol, *scxclu, *actvsc;
  61. int current_max_dfa_size, current_max_xpairs;
  62. int current_max_template_xpairs, current_max_dfas;
  63. int lastdfa, *nxt, *chk, *tnxt;
  64. int *base, *def, tblend, firstfree, numtemps, **dss, *dfasiz;
  65. union dfaacc_union *dfaacc;
  66. int *accsiz, *dhash, *todo, todo_head, todo_next, numas;
  67. int numsnpairs, jambase, jamstate;
  68. int lastccl, current_maxccls, *cclmap, *ccllen, *cclng, cclreuse;
  69. int current_max_ccl_tbl_size;
  70. char *ccltbl;
  71. char *starttime, *endtime, nmstr[MAXLINE];
  72. int sectnum, nummt, hshcol, dfaeql, numeps, eps2, num_reallocs;
  73. int tmpuses, totnst, peakpairs, numuniq, numdup, hshsave;
  74. FILE *temp_action_file;
  75. int end_of_buffer_state;
  76. char *action_file_name = "" ;
  77.  
  78. /*
  79. **    function:    usage
  80. **    purpose:    Show syntax of message
  81. */
  82. void
  83. usage(void)
  84. {
  85. fprintf(stderr,"FLEX (Version 1.04b)\t\t\t\t12/30/1989\n");
  86. fprintf(stderr,
  87. "Usage: flex [ -dfirstvFILT -c[efmF] -Sskeleton_file ] <filename.L>\n");
  88. fprintf(stderr,"\t-d = Scanner runs in DEBUG mode.\n");
  89. fprintf(stderr,"\t-f = Do not compress scanner tables.\n");
  90. fprintf(stderr,"\t-i = Generate case-insensitive scanner.\n");
  91. fprintf(stderr,"\t-r = Use the REJECT action.\n");
  92. fprintf(stderr,"\t-s = Suppress default rule.\n");
  93. fprintf(stderr,"\t-t = Identical to LEX's option.\n");
  94. fprintf(stderr,"\t-v = Verbose. Print summary statistics.\n");
  95. fprintf(stderr,"\t-F = Fast scanner table representation.\n");
  96. fprintf(stderr,"\t-I = Generate an interactive scanner.\n");
  97. fprintf(stderr,"\t-L = Do not generate #line directives.\n");
  98. fprintf(stderr,"\t-T = Run FLEX in trace mode.\n");
  99. fprintf(stderr,"\t-c[efmF] = Controls degree of table compresion.\n");
  100. fprintf(stderr,"\t-Sskeleton_file = Overrides default skeleton.\n");
  101. fprintf(stderr,"\t<filename.L> = The FLEX grammar file to process.\n");
  102.     return;
  103. };                    /* usage */
  104.  
  105.  
  106.  
  107. /* flex - main program
  108.  *
  109.  * synopsis (from the shell)
  110.  *    flex [-v] [file ...]
  111.  */
  112.  
  113. int main( argc, argv )
  114. int argc;
  115. char **argv;
  116. {
  117.     if (argc == 1)            /* Only name inputed? */
  118.     {                    /* Yes, */
  119.         usage();            /* Give me syntax */
  120.         exit(1);            /* Good bye! */
  121.     };                    /* endif */
  122.     
  123.     flexinit( argc, argv );
  124.  
  125.     readin();
  126.  
  127.     if ( ! syntaxerror )
  128.     {
  129.         /* convert the ndfa to a dfa */
  130.         ntod();
  131.  
  132.         /* generate the C state transition tables from the DFA */
  133.         make_tables();
  134.     }
  135.  
  136.     /* note, flexend does not return.  It exits with its argument as status. */
  137.  
  138.     flexend( 0 );
  139.  
  140.     return 0 ; /* for the lint-minded */
  141. }
  142.  
  143.  
  144. /* flexend - terminate flex
  145.  *
  146.  * synopsis
  147.  *    int status;
  148.  *    flexend( status );
  149.  *
  150.  *    status is exit status.
  151.  *
  152.  * note
  153.  *    This routine does not return.
  154.  */
  155.  
  156. void flexend( status )
  157. int status;
  158.  
  159. {
  160.     int tblsiz;
  161.  
  162.     if ( skelfile != NULL )
  163.         (void) fclose( skelfile );
  164.  
  165.     if ( temp_action_file )
  166.     {
  167.         (void) fclose( temp_action_file );
  168.         (void) unlink( action_file_name );
  169.     }
  170.  
  171.     if ( printstats )
  172.     {
  173.         endtime = gettimestr();
  174.  
  175.         fprintf( stderr, "flex usage statistics:\n" );
  176.         fprintf( stderr, "  started at %s, finished at %s\n",
  177.           starttime, endtime );
  178.  
  179.         fprintf( stderr, "  %d/%d NFA states\n", lastnfa, current_mns );
  180.         fprintf( stderr, "  %d/%d DFA states (%d words)\n", lastdfa,
  181.           current_max_dfas, totnst );
  182.         fprintf( stderr, "  %d rules\n", accnum );
  183.         fprintf( stderr, "  %d/%d start conditions\n", lastsc,
  184.           current_max_scs );
  185.         fprintf( stderr, "  %d epsilon states, %d double epsilon states\n",
  186.           numeps, eps2 );
  187.  
  188.         if ( lastccl == 0 )
  189.             fprintf( stderr, "  no character classes\n" );
  190.         else
  191.             fprintf( stderr,
  192.               "  %d/%d character classes needed %d/%d words of storage, %d reused\n",
  193.               lastccl, current_maxccls,
  194.               cclmap[lastccl] + ccllen[lastccl] - 1,
  195.               current_max_ccl_tbl_size, cclreuse );
  196.  
  197.         fprintf( stderr, "  %d state/nextstate pairs created\n", numsnpairs );
  198.         fprintf( stderr, "  %d/%d unique/duplicate transitions\n",
  199.           numuniq, numdup );
  200.  
  201.         if ( fulltbl )
  202.         {
  203.             tblsiz = lastdfa * numecs;
  204.             fprintf( stderr, "  %d table entries\n", tblsiz );
  205.         }
  206.  
  207.         else
  208.         {
  209.             tblsiz = 2 * (lastdfa + numtemps) + 2 * tblend;
  210.  
  211.             fprintf( stderr, "  %d/%d base/def entries created\n",
  212.               lastdfa + numtemps, current_max_dfas );
  213.             fprintf( stderr, "  %d/%d (peak %d) nxt/chk entries created\n",
  214.               tblend, current_max_xpairs, peakpairs );
  215.             fprintf( stderr,
  216.               "  %d/%d (peak %d) template nxt/chk entries created\n",
  217.               numtemps * nummecs, current_max_template_xpairs,
  218.               numtemps * numecs );
  219.             fprintf( stderr, "  %d empty table entries\n", nummt );
  220.             fprintf( stderr, "  %d protos created\n", numprots );
  221.             fprintf( stderr, "  %d templates created, %d uses\n",
  222.               numtemps, tmpuses );
  223.         }
  224.  
  225.         if ( useecs )
  226.         {
  227.             tblsiz = tblsiz + CSIZE;
  228.             fprintf( stderr, "  %d/%d equivalence classes created\n",
  229.               numecs, CSIZE );
  230.         }
  231.  
  232.         if ( usemecs )
  233.         {
  234.             tblsiz = tblsiz + numecs;
  235.             fprintf( stderr, "  %d/%d meta-equivalence classes created\n",
  236.               nummecs, CSIZE );
  237.         }
  238.  
  239.         fprintf( stderr, "  %d (%d saved) hash collisions, %d DFAs equal\n",
  240.           hshcol, hshsave, dfaeql );
  241.         fprintf( stderr, "  %d sets of reallocations needed\n", num_reallocs );
  242.         fprintf( stderr, "  %d total table entries needed\n", tblsiz );
  243.     }
  244.  
  245.     exit( status );
  246. }
  247.  
  248.  
  249. /* flexinit - initialize flex
  250.  *
  251.  * synopsis
  252.  *    int argc;
  253.  *    char **argv;
  254.  *    flexinit( argc, argv );
  255.  */
  256.  
  257. void flexinit( argc, argv )
  258. int argc;
  259. char **argv;
  260.  
  261. {
  262.     int i, sawcmpflag, use_stdout;
  263.     char *arg, *skelname = NULL ;
  264.     char *flexenv = "" ;
  265.     char *skelpath = "" ;
  266.     /*    char *gettime(), clower(), *mktemp(); */
  267.  
  268.     printstats = syntaxerror = trace = spprdflt = interactive = caseins = false;
  269.     ddebug = fulltbl = reject = fullspd = false;
  270.     gen_line_dirs = usemecs = useecs = true;
  271.  
  272.     sawcmpflag = false;
  273.     use_stdout = false;
  274.  
  275.     /* read flags */
  276.     for ( --argc, ++argv; argc ; --argc, ++argv )
  277.     {
  278.         if ( argv[0][0] != '-' || argv[0][1] == '\0' )
  279.             break;
  280.  
  281.         arg = argv[0];
  282.  
  283.         for ( i = 1; arg[i] != '\0'; ++i )
  284.             switch ( arg[i] )
  285.             {
  286.             case 'c':
  287.                 if ( i != 1 )
  288.                     flexerror( "-c flag must be given separately" );
  289.  
  290.                 if ( ! sawcmpflag )
  291.                 {
  292.                     useecs = false;
  293.                     usemecs = false;
  294.                     fulltbl = false;
  295.                     sawcmpflag = true;
  296.                 }
  297.  
  298.                 for ( ++i; arg[i] != '\0'; ++i )
  299.                     switch ( clower( arg[i] ) )
  300.                     {
  301.                     case 'e':
  302.                         useecs = true;
  303.                         break;
  304.  
  305.                     case 'F':
  306.                         fullspd = true;
  307.                         break;
  308.  
  309.                     case 'f':
  310.                         fulltbl = true;
  311.                         break;
  312.  
  313.                     case 'm':
  314.                         usemecs = true;
  315.                         break;
  316.  
  317.                     default:
  318.                         lerrif( "unknown -c option %c",
  319.                           (int) arg[i] );
  320.                         break;
  321.                     }
  322.  
  323.                 goto get_next_arg;
  324.  
  325.             case 'd':
  326.                 ddebug = true;
  327.                 break;
  328.  
  329.             case 'f':
  330.                 useecs = usemecs = false;
  331.                 fulltbl = true;
  332.                 break;
  333.  
  334.             case 'I':
  335.                 interactive = true;
  336.                 break;
  337.  
  338.             case 'i':
  339.                 caseins = true;
  340.                 break;
  341.  
  342.             case 'L':
  343.                 gen_line_dirs = false;
  344.                 break;
  345.  
  346.             case 'r':
  347.                 reject = true;
  348.                 break;
  349.  
  350.             case 'F':
  351.                 useecs = usemecs = false;
  352.                 fullspd = true;
  353.                 break;
  354.  
  355.             case 'S':
  356.                 if ( i != 1 )
  357.                     flexerror( "-S flag must be given separately" );
  358.  
  359.                 skelname = arg + i + 1;
  360.                 goto get_next_arg;
  361.  
  362.             case 's':
  363.                 spprdflt = true;
  364.                 break;
  365.  
  366.             case 't':
  367.                 use_stdout = true;
  368.                 break;
  369.  
  370.             case 'T':
  371.                 trace = true;
  372.                 break;
  373.  
  374.             case 'v':
  375.                 printstats = true;
  376.                 break;
  377.  
  378.             default:
  379.                 lerrif( "unknown flag %c", (int) arg[i] );
  380.                 break;
  381.             }
  382.  
  383. get_next_arg: /* used by -c and -S flags in lieu of a "continue 2" control */
  384.         ;
  385.     }
  386.  
  387.     if ( (fulltbl || fullspd) && usemecs )
  388.         flexerror( "full table and -cm don't make sense together" );
  389.  
  390.     if ( (fulltbl || fullspd) && interactive )
  391.         flexerror( "full table and -I are (currently) incompatible" );
  392.  
  393.     if ( (fulltbl || fullspd) && reject )
  394.         flexerror( "reject (-r) cannot be used with -f or -F" );
  395.  
  396.     if ( fulltbl && fullspd )
  397.         flexerror( "full table and -F are mutually exclusive" );
  398.  
  399.     if ( ! skelname )
  400.     {
  401.         static char skeleton_name_storage[400];
  402.  
  403.         skelname = skeleton_name_storage;
  404.  
  405.         if ( fullspd || fulltbl )
  406.             (void) strcpy( skelname, FAST_SKELETON_FILE );
  407.         else
  408.             (void) strcpy( skelname, DEFAULT_SKELETON_FILE );
  409.     }
  410.  
  411.     if ( ! use_stdout )
  412.     {
  413.         FILE *prev_stdout = freopen( "lexyy.c", "w", stdout );
  414.  
  415.         if ( prev_stdout == NULL )
  416.             flexerror( "could not create lexyy.c" );
  417.     }
  418.  
  419.     if ( argc )
  420.     {
  421.         if ( argc > 1 )
  422.             flexerror( "extraneous argument(s) given" );
  423.  
  424.         yyin = fopen( infilename = argv[0], "r" );
  425.  
  426.         if ( yyin == NULL )
  427.             lerrsf( "can't open %s", argv[0] );
  428.     }
  429.  
  430.     else
  431.         yyin = stdin;
  432.  
  433.     lastccl = 0;
  434.     lastsc = 0;
  435.  
  436.     /* initialize the statistics */
  437.     starttime = gettimestr();
  438.  
  439.     if ((skelfile = fopen( skelname, "r" )) == NULL )
  440.     {
  441.         if (!(flexenv = getenv("FLEXENV")))
  442.             lerrsf( "can't open skeleton file %s", skelname );
  443.         else
  444.            if (!(skelpath = malloc( strlen(skelname) + strlen(flexenv) + 2)))
  445.                lerrsf("%s: out of memory.", "flexinit()") ;
  446.  
  447.         sprintf( skelpath,"%s\\%s", flexenv, skelname) ;
  448.  
  449.         if ( (skelfile = fopen( skelpath, "r" )) == NULL )
  450.            lerrsf( "can't open skeleton file %s", skelpath ); 
  451.         else
  452.            free( skelpath) ;
  453.     }
  454.  
  455.     action_file_name = mktemp( "flXXXXXX" ) ;
  456.  
  457.     if ( (temp_action_file = fopen( action_file_name, "w" )) == NULL )
  458.         lerrsf( "can't open temporary action file %s", action_file_name );
  459.  
  460.     lastdfa = lastnfa = accnum = numas = numsnpairs = tmpuses = 0;
  461.     numecs = numeps = eps2 = num_reallocs = hshcol = dfaeql = totnst = 0;
  462.     numuniq = numdup = hshsave = eofseen = datapos = dataline = 0;
  463.     onesp = numprots = 0;
  464.  
  465.     linenum = sectnum = 1;
  466.     firstprot = NIL;
  467.  
  468.     /* used in mkprot() so that the first proto goes in slot 1
  469.      * of the proto queue
  470.      */
  471.     lastprot = 1;
  472.  
  473.     if ( useecs )
  474.     {
  475.         /* set up doubly-linked equivalence classes */
  476.         ecgroup[1] = NIL;
  477.  
  478.         for ( i = 2; i <= CSIZE; ++i )
  479.         {
  480.             ecgroup[i] = i - 1;
  481.             nextecm[i - 1] = i;
  482.         }
  483.  
  484.         nextecm[CSIZE] = NIL;
  485.     }
  486.  
  487.     else
  488.     { /* put everything in its own equivalence class */
  489.         for ( i = 1; i <= CSIZE; ++i )
  490.         {
  491.             ecgroup[i] = i;
  492.             nextecm[i] = BAD_SUBSCRIPT; /* to catch errors */
  493.         }
  494.     }
  495.  
  496.     set_up_initial_allocations();
  497. }
  498.  
  499.  
  500. /* readin - read in the rules section of the input file(s)
  501.  *
  502.  * synopsis
  503.  *    readin();
  504.  */
  505.  
  506. void readin()
  507. {
  508.     fputs( "#define YY_DEFAULT_ACTION ", stdout );
  509.  
  510.     if ( spprdflt )
  511.         fputs( "YY_FATAL_ERROR( \"flex scanner jammed\" )", stdout );
  512.     else
  513.         fputs( "ECHO", stdout );
  514.  
  515.     fputs( ";\n", stdout );
  516.  
  517.     if ( ddebug )
  518.         puts( "#define FLEX_DEBUG" );
  519.     if ( useecs )
  520.         puts( "#define FLEX_USE_ECS" );
  521.     if ( usemecs )
  522.         puts( "#define FLEX_USE_MECS" );
  523.     if ( interactive )
  524.         puts( "#define FLEX_INTERACTIVE_SCANNER" );
  525.     if ( reject )
  526.         puts( "#define FLEX_REJECT_ENABLED" );
  527.     if ( fulltbl )
  528.         puts( "#define FLEX_FULL_TABLE" );
  529.  
  530.     skelout();
  531.  
  532.     line_directive_out( stdout );
  533.  
  534.     if ( yyparse() )
  535.         lerrif( "fatal parse error at line %d", linenum );
  536.  
  537.     if ( useecs )
  538.     {
  539.         numecs = cre8ecs( nextecm, ecgroup, CSIZE );
  540.         ccl2ecl();
  541.     }
  542.  
  543.     else
  544.         numecs = CSIZE;
  545.  
  546. }
  547.  
  548.  
  549.  
  550. /* set_up_initial_allocations - allocate memory for internal tables */
  551.  
  552. void set_up_initial_allocations()
  553.  
  554. {
  555.     current_mns = INITIAL_MNS;
  556.     firstst = allocate_integer_array( current_mns );
  557.     lastst = allocate_integer_array( current_mns );
  558.     finalst = allocate_integer_array( current_mns );
  559.     transchar = allocate_integer_array( current_mns );
  560.     trans1 = allocate_integer_array( current_mns );
  561.     trans2 = allocate_integer_array( current_mns );
  562.     accptnum = allocate_integer_array( current_mns );
  563.  
  564.     current_max_scs = INITIAL_MAX_SCS;
  565.     scset = allocate_integer_array( current_max_scs );
  566.     scbol = allocate_integer_array( current_max_scs );
  567.     scxclu = allocate_integer_array( current_max_scs );
  568.     actvsc = allocate_integer_array( current_max_scs );
  569.  
  570.     current_maxccls = INITIAL_MAXCCLS;
  571.     cclmap = allocate_integer_array( current_maxccls );
  572.     ccllen = allocate_integer_array( current_maxccls );
  573.     cclng = allocate_integer_array( current_maxccls );
  574.  
  575.     current_max_ccl_tbl_size = INITIAL_MAX_CCL_TBL_SIZE;
  576.     ccltbl = allocate_character_array( current_max_ccl_tbl_size );
  577.  
  578.     current_max_dfa_size = INITIAL_MAX_DFA_SIZE;
  579.  
  580.     current_max_xpairs = INITIAL_MAX_XPAIRS;
  581.     nxt = allocate_integer_array( current_max_xpairs );
  582.     chk = allocate_integer_array( current_max_xpairs );
  583.  
  584.     current_max_template_xpairs = INITIAL_MAX_TEMPLATE_XPAIRS;
  585.     tnxt = allocate_integer_array( current_max_template_xpairs );
  586.  
  587.     current_max_dfas = INITIAL_MAX_DFAS;
  588.     base = allocate_integer_array( current_max_dfas );
  589.     def = allocate_integer_array( current_max_dfas );
  590.     dfasiz = allocate_integer_array( current_max_dfas );
  591.     accsiz = allocate_integer_array( current_max_dfas );
  592.     dhash = allocate_integer_array( current_max_dfas );
  593.     todo = allocate_integer_array( current_max_dfas );
  594.     dss = allocate_intptr_array( current_max_dfas );
  595.     dfaacc = allocate_dfaacc_union( current_max_dfas );
  596. }
  597.  
  598.  
  599.  
  600.