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