home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 September / Simtel20_Sept92.cdr / msdos / c / lex.arc / LEX.C < prev    next >
Text File  |  1986-03-13  |  16KB  |  551 lines
  1. /*
  2.  * Copyright (c) 1978 Charles H. Forsyth
  3.  */
  4.  
  5. /*
  6.  * lex -- initialisation, allocation, set creation
  7.  *
  8.  *     Revised for PDP-11 (Decus) C by Martin Minow
  9.  */
  10.  
  11. /* Modified 02-Dec-80 Bob Denny -- Conditionalized debug code for smaller size
  12.  *                           01 -- Moved calls to dfa build, min, print, write
  13.  *                                  and to stat, and code for ending() into
  14.  *                                  this module so that 'ytab' could be put
  15.  *                                  into overlay region.
  16.  *          29-May-81 Bob Denny -- More extern hacking for RSX overlaying.
  17.  * More     19-Mar-82 Bob Denny -- New C library & compiler
  18.  * More     03-May-82 Bob Denny -- Final touches, remove unreferenced autos
  19.  *          28-Aug-82 Bob Denny -- Add "-s" switch to supress references to
  20.  *                                  "stdio.h" in generated code.  Add switch
  21.  *                                  comments in code. Add -e for "easy" com-
  22.  *                                  mand line. "lex -e file" is the short way
  23.  *                                  of saying:
  24.  *                                      "lex -i file.lxi -o file.c -t file"
  25.  * More(!)  30-Oct-82 Bob Denny -- Fix RSX ODL to put lots of FCS junk into
  26.  *                                  overlay, pick up (badly needed) 3KW for
  27.  *                                  NFA nodes, etc.  Change static allocations
  28.  *                                  in LEXLEX.H for RSX so can do non-trivial
  29.  *                                  things.  Task is now big on RSX and grows
  30.  *                                  from big to huge as it runs.
  31.  *                                 Fix "-s" support so it is again possible
  32.  *                                  to do a lexswitch() (dumb!).
  33.  *          14-Apr-83 Bob Denny    VAX-11 C workarounds.
  34.  *                                 Fix definition of toupper().
  35.  *            20-Nov-83 Scott Guthery  Adapt for IBM PC & DeSmet C
  36.  */
  37.  
  38. #include <stdio.h>
  39. #include "system.h"        /* includes system configuration constants */
  40.  
  41. extern char *lalloc();
  42. extern char tolower();
  43.  
  44. struct  nfa     nfa[MAXNFA];
  45. struct  nfa     *nfap = &nfa[1];
  46.  
  47. struct  xset    sets[NCHARS];
  48. char    insets[NCHARS];
  49.  
  50. struct  trans   trans[NTRANS];
  51. struct  trans   *transp = &trans[0];
  52.  
  53. char    ccls[NCCLS][(NCHARS+1)/NBPC];
  54. int     nccls;
  55.  
  56. int     ndfa;
  57. struct  dfa     dfa[MAXDFA];
  58. struct  move    move[NNEXT];
  59.  
  60. char    *tabname = "lextab";
  61. char    tabfile[15];
  62. char    *infile         = NULL;
  63. char    *outfile        = NULL;
  64.  
  65. #ifdef DEBUG
  66. char    *dumpfile       = "lex.out";
  67. int     lldebug = 0;
  68. #endif
  69.  
  70. int  llnxtmax = 0;
  71.  
  72. FILE *llout;
  73. FILE *lexin;
  74. FILE *lexlog;
  75.  
  76. /*
  77.  * Flags.  Allow globals only for those requiring same. Some only
  78.  * used for checking for bad combos.
  79.  */
  80.         int     aflag = 0;      /* Ignore non-ASCII in [^ ...] */
  81. static  int     eflag = 0;      /* Easy command line */
  82. static  int     iflag = 0;      /* "-i" given */
  83.         int     mflag = 0;      /* Enable state minimization (not imp.) */
  84. static  int     oflag = 0;      /* "-o" given */
  85.         int     sflag = 0;      /* Supress "#include <stdio.h>" in output */
  86. static  int     tflag = 0;      /* "-t" given */
  87.  
  88. struct  set     *setlist = 0;
  89.  
  90. main(argc, argv)
  91. int argc;
  92. char *argv[];
  93. {
  94.         register char *cp, *cp2;
  95.  
  96. #ifdef DEBUG
  97.         int vflag;
  98.         vflag = 0;
  99. #endif
  100.  
  101.         for (; argc>1 && *argv[1]=='-'; argv++, argc--)
  102.         switch (tolower(argv[1][1])) {
  103.  
  104. #ifdef DEBUG
  105.         /*
  106.          * Create "verification" file, describing the scanner.
  107.          */
  108.         case 'v':                               /* -v => lex.out        */
  109.                 vflag++;                        /* -v x.out => x.out    */
  110.                 if (argc > 2 && argv[2][1] != '1') {
  111.                         --argc;
  112.                         dumpfile = (++argv)[1];
  113.                 }
  114.                 break;
  115.         /*
  116.          * Enable debug displays
  117.          */
  118.         case 'd':
  119.                 lldebug++;
  120.                 break;
  121. #endif
  122.         /*
  123.          * Enable state minimization. Currently not implemented.
  124.          */
  125.         case 'm':
  126.                 mflag++;
  127.                 break;
  128.  
  129.         /*
  130.          * Disable matching of non-ASCII characters (codes > 177(8))
  131.          * for exception character classes (form "[^ ...]").
  132.          */
  133.         case 'a':
  134.                 aflag++;
  135.                 break;
  136.  
  137.         /*
  138.          * Supress "#include <stdio.h>" in generated
  139.          * code for programs not using standard I/O.
  140.          */
  141.         case 's':
  142.                 sflag++;
  143.                 break;
  144.  
  145.         /*
  146.          * "Easy" command line
  147.          */
  148.         case 'e':
  149.                 if(iflag || oflag || tflag) {
  150.                         error("Illegal switch combination\n");
  151.                         exit(1);
  152.                 }
  153.                 if (--argc <= 1) {
  154.                         error("Missing name\n");
  155.                         exit(1);
  156.                 }
  157.                 if (strlen(tabname = (++argv)[1]) > 8) {
  158.                         error("Name too long\n");
  159.                         exit(1);
  160.                 }
  161.                 infile = malloc(14);
  162.                 outfile = malloc(12);
  163.                 strcpy(infile, tabname); strcat(infile, ".lxi");
  164.                 printf("Input read from %s\n", infile);
  165.                 if ((lexin = fopen(infile, "r")) == NULL) {
  166.                         error("Cannot open input \"%s\"\n", infile);
  167.                         exit(1);
  168.                 }
  169.                 strcpy(outfile, tabname); strcat(outfile, ".c");
  170.                 break;
  171.  
  172.         /*
  173.          * Specify input file name.
  174.          */
  175.         case 'i':
  176.                 if (eflag) {
  177.                         error("Illegal switch combination\n");
  178.                         exit(1);
  179.                 }
  180.                 iflag++;
  181.                 if (--argc <= 1) {
  182.                         error("Missing input file\n");
  183.                         exit(1);
  184.                 }
  185.                 infile = (++argv)[1];
  186.                 printf("Input read from %s\n", infile);
  187.                 if ((lexin = fopen(infile, "r")) == NULL) {
  188.                         error("Cannot open input \"%s\"\n", infile);
  189.                         exit(1);
  190.                 }
  191.                 break;
  192.  
  193.         /*
  194.          * Specify output file name. Default = "lextab.c"
  195.          */
  196.         case 'o':
  197.                 if (eflag) {
  198.                         error("Illegal switch combination\n");
  199.                         exit(1);
  200.                 }
  201.                 oflag++;
  202.                 if (--argc <= 1) {
  203.                         error("Missing output file");
  204.                         exit(1);
  205.                 }
  206.                 outfile = (++argv)[1];
  207.                 break;
  208.  
  209.         /*
  210.          * Specify table name.  Default = "lextab.c".  If "-o"
  211.          * not given, output will go to "tabname.c".
  212.          */
  213.         case 't':
  214.                 if (eflag) {
  215.                         error("Illegal switch combination\n");
  216.                         exit(1);
  217.                 }
  218.                 tflag++;
  219.                 if (--argc <= 1) {
  220.                         error("Missing table name");
  221.                         exit(1);
  222.                 }
  223.                 if (strlen(tabname = (++argv)[1]) > 8) {
  224.                         error("Table name too long\n");
  225.                         exit(1);
  226.                 }
  227.                 break;
  228.  
  229.         default:
  230.                 error("Illegal option: %s\n", argv[1]);
  231.                 exit(1);
  232.         }
  233.  
  234. #ifdef DEBUG
  235.  
  236.         cp = (vflag) ? dumpfile : "NUL";
  237.         printf("Log written to %s\n", cp);
  238.         if ((lexlog = fopen(cp, "w")) == NULL) {
  239.                 error("Cannot open \"%s\"", cp);
  240.                 exit(1);
  241.         }
  242. #endif
  243.         if (infile == NULL) {
  244.                 infile = malloc(31);
  245.                 strcpy(infile, "lex.lxi");
  246.         }
  247.         cp = infile;                    /* Fold infile to lower case */
  248. /*
  249.  * The following 2 loops cannot use the form "*cp++ = tolower(*cp)" 
  250.  * due to a bug in VAX-11 C V1.0-09 where the pointer increment
  251.  * is done too soon (!).
  252.  */
  253.         while(*cp)
  254.                 {
  255.                 *cp = tolower(*cp);
  256.                 cp++;
  257.                 }
  258.         cp = tabname;                   /* Fold tabname to lower case */
  259.         while(*cp)
  260.                 {
  261.                 *cp = tolower(*cp);
  262.                 cp++;
  263.                 }
  264.         if (outfile == NULL) {
  265.                 /*
  266.                  * Typical hacker's idiom!
  267.                  */
  268.                 for (cp = tabname, cp2 = tabfile; *cp2 = *cp++;)
  269.                         cp2++;
  270.                 for (cp = ".c"; *cp2++ = *cp++;)
  271.                         ;
  272.                 outfile = tabfile;
  273.         }
  274.         printf("Analyzer written to %s\n", outfile);
  275.         if ((llout = fopen(outfile, "w"))==NULL) {
  276.                 error("Can't create %s\n", outfile);
  277.                 exit(1);
  278.         }
  279.  
  280.         heading();
  281.         fprintf(stderr, "Parse LEX source ...\n");
  282.         if (yyparse())
  283.                 error("Parse failed\n");
  284.         fprintf(stderr, "Build NFA then DFA ...\n");
  285.         dfabuild();                                             /* 01+ */
  286.         fprintf(stderr, "Minimize DFA ...\n");
  287.         dfamin();
  288.         fprintf(stderr, "Create C source ...\n");
  289.         dfaprint();
  290.         dfawrite();
  291. #ifdef DEBUG
  292.         stats();
  293.         fclose(lexlog);
  294. #endif                                                          /* 01- */
  295.         fprintf(stderr, "\07LEX done.\n");
  296.         fclose(llout);
  297. } /** END OF MAIN **/
  298.  
  299. /*
  300.  * This module was moved here from out.c so it could be called from
  301.  * ytab.c residing in same overlay region as out.c.
  302.  * 02-Dec-80  Bob Denny.
  303.  */
  304.                                                                 /* 01+ */
  305. ending()
  306. {
  307.         static int ended;
  308.  
  309.         if (ended++)
  310.                 return;
  311.         fprintf(llout, "\t}\n\treturn(LEXSKIP);\n}\n");
  312.         setline();
  313. }
  314.  
  315. #ifdef DEBUG
  316. stats()
  317. {
  318.         fprintf(lexlog, "\n");
  319.         fprintf(lexlog, "%d/%d NFA states, %d/%d DFA states\n",
  320.                 nfap-nfa, MAXNFA, ndfa, MAXDFA);
  321.         fprintf(lexlog, "%d/%d entries in move vectors\n", llnxtmax, NNEXT);
  322. }
  323.  
  324. /*
  325.  * Print a state set on { ... } form on lexlog.
  326.  */
  327. pset(t, nf)
  328. register struct set *t;
  329. {
  330.         register int i;
  331.  
  332.         fprintf(lexlog, "{");
  333.         for (i = 0; i < t->s_len; i++)
  334.                 if (nf)
  335.                         fprintf(lexlog, " %d", t->s_els[i]-nfa); else
  336.                         fprintf(lexlog, " %d", t->s_els[i]);
  337.         fprintf(lexlog, "}");
  338. }
  339.  
  340. /*
  341.  * Print a character to lexlog in readable form.
  342.  * Returns the number of characters generated.
  343.  */
  344. chprint(ch)
  345. {
  346.         register char *s;
  347.  
  348.         ch &= 0377;
  349.         switch (ch) {
  350.         case '\t':
  351.                 s = "\\t";
  352.                 break;
  353.         case '\n':
  354.                 s = "\\n";
  355.                 break;
  356.         case '\b':
  357.                 s = "\\b";
  358.                 break;
  359.         case '\r':
  360.                 s = "\\r";
  361.                 break;
  362.         default:
  363.                 if(ch<040 || ch>=0177)
  364.                         {
  365.                         fprintf(lexlog, "\\%03o", ch);
  366.                         return(4);
  367.                         }
  368.                 else
  369.                         {
  370.                         putc(ch, lexlog);
  371.                         return(1);
  372.                         }
  373.         }
  374.         fprintf(lexlog, s);
  375.         return(2);
  376. }
  377. #endif
  378.  
  379. /*
  380.  * The following functions simply
  381.  * allocate various kinds of
  382.  * structures.
  383.  */
  384. struct nfa *
  385. newnfa(ch, nf1, nf2)
  386. struct nfa *nf1, *nf2;
  387. {
  388.         register struct nfa *nf;
  389.  
  390.         if ((nf = nfap++) >= &nfa[MAXNFA]) {
  391.                 error("Too many NFA states");
  392.                 exit(1);
  393.         }
  394.         nf->n_char = ch;
  395.         nf->n_succ[0] = nf1;
  396.         nf->n_succ[1] = nf2;
  397.         nf->n_trans = 0;
  398.         nf->n_flag = 0;
  399.         nf->n_look = 0;
  400.         return(nf);
  401. }
  402.  
  403. newdfa()
  404. {
  405.         register struct dfa *df;
  406.  
  407.         if ((df = &dfa[ndfa++]) >= &dfa[MAXDFA]) {
  408.                 error("Out of dfa states");
  409.                 exit(1);
  410.         }
  411.         return(df);
  412. }
  413.  
  414. char *
  415. newccl(ccl)
  416. char *ccl;
  417. {
  418.         register char *p, *q;
  419.         register int i;
  420.         int j;
  421.  
  422.         for (j = 0; j < nccls; j++) {
  423.                 p = ccl;
  424.                 q = ccls[j];
  425.                 for (i = sizeof(ccls[j]); i--;)
  426.                         if (*p++ != *q++)
  427.                                 goto cont;
  428.                 return(ccls[j]);
  429.         cont:;
  430.         }
  431.         if (nccls >= NCCLS) {
  432.                 error("Too many character classes");
  433.                 exit(1);
  434.         }
  435.         p = ccl;
  436.         q = ccls[j = nccls++];
  437.         for (i = sizeof(ccls[j]); i--;)
  438.                 *q++ = *p++;
  439.         return(ccls[j]);
  440. }
  441.  
  442. struct trans *
  443. newtrans(st, en)
  444. struct nfa *st, *en;
  445. {
  446.         register struct trans *tp;
  447.  
  448.         if ((tp = transp++) >= &trans[NTRANS]) {
  449.                 error("Too many translations");
  450.                 exit(1);
  451.         }
  452.         tp->t_start = st;
  453.         tp->t_final = en;
  454.         en->n_trans = tp;
  455.         return(tp);
  456. }
  457.  
  458. /*
  459.  * Create a new set. `sf', if set, indicates that the elements of the
  460.  * set are states of an NFA). If `sf' is not set, the elements are state
  461.  * numbers of a DFA.
  462.  */
  463. struct set *
  464. newset(v, i, sf)
  465. register struct nfa **v;
  466. register int i;
  467. {
  468.         register struct set *t;
  469.         register int k;
  470.         int setcomp();
  471.  
  472.         qsort(v, i, sizeof(*v), setcomp);
  473.         for (t = setlist; t; t = t->s_next)
  474.                 if (t->s_len==i && eqvec(t->s_els, v, i))
  475.                         return(t);
  476.         t = lalloc(1, sizeof(*t)+i*sizeof(t->s_els[0]), "set nodes");
  477.         t->s_next = setlist;
  478.         setlist = t;
  479.         t->s_final = 0;
  480.         t->s_state =  0;
  481.         t->s_flag = 0;
  482.         t->s_len = i;
  483.         t->s_group = 0;
  484.         t->s_look = 0;
  485.         for (v += i; i;) {
  486.                 --v;
  487.                 if (sf) {
  488.                         if ((*v)->n_char==FIN)
  489.                                 t->s_final =  (*v)-nfa;
  490.                         if ((*v)->n_flag&LOOK)
  491.                                 t->s_look |= 1<<(*v)->n_look;
  492.                 } else {
  493.                         k = *v;
  494.                         dfa[k].df_name->s_group = t;
  495.                 }
  496.                 t->s_els[--i] = *v;
  497.         }
  498.         return(t);
  499. }
  500.  
  501. setcomp(n1p, n2p)
  502. struct nfa **n1p, **n2p;
  503. {
  504.         register struct nfa *n1, *n2;
  505.  
  506.         n1 = *n1p;
  507.         n2 = *n2p;
  508.         if (n1 > n2)
  509.                 return(1);
  510.         if (n1==n2)
  511.                 return(0);
  512.         return(-1);
  513. }
  514.  
  515. eqvec(a, b, i)
  516. register int *a, *b, i;
  517. {
  518.         if (i)
  519.                 do {
  520.                         if (*a++ != *b++)
  521.                                 return(0);
  522.                 } while (--i);
  523.         return(1);
  524. }
  525.  
  526. /*
  527.  * Ask for core, and complain if there is no more.
  528.  */
  529. char *
  530. lalloc(n, s, w)
  531. char *w;
  532. {
  533.         register char *cp;
  534.  
  535.         if ((cp = calloc(n, s)) == NULL) {
  536.                 fprintf(stderr, "No space for %s", w);
  537. #ifdef DEBUG
  538.                 if (lldebug)
  539.                         dfaprint();
  540. #endif
  541.                 exit(1);
  542.         }
  543.         return(cp);
  544. }
  545.  
  546. error(format, argument)
  547. char *format, *argument;
  548. {
  549.     fprintf(stderr, format, argument);
  550. }
  551.