home *** CD-ROM | disk | FTP | other *** search
/ Microsoft Programmer's Library 1.3 / Microsoft-Programers-Library-v1.3.iso / sampcode / alde_c / misc / util / lex / lex.c < prev    next >
Encoding:
C/C++ Source or Header  |  1983-12-25  |  18.1 KB  |  621 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. #ifdef  DOCUMENTATION
  39.  
  40. title   lex     A Lexical Analyser Generator
  41. index           A Lexical Analyser Generator
  42.  
  43. synopsis
  44.  
  45.         lex [-options] [-i grammar] [-o outfile] [-t table]
  46.  
  47. description
  48.  
  49.         Lex compiles a lexical analyser from a grammar and description of
  50.         actions.  It is described more fully in lex.doc: only usage is
  51.         described.  The following options are available:
  52.         .lm +16
  53.         .s.i-16;-a              Disable recognition of non-ASCII characters
  54.         (codes > 177 octal) for exception character classes (form [^ ...]).
  55.         .s.i-16;-d              Enable debugging code within lex.  Normally
  56.         needed only for debugging lex.
  57.         .s.i-16;-e              "Easy" command line. Saying "lex#-e#name" is the
  58.         same as saying:
  59.         .s.i 4;"lex -i name.lxi -o name.c -t name"
  60.         .s
  61.         Do not include devices or an extension on "name" or make it longer
  62.         than 8 characters, or you'll get several error messages.
  63.         .s.i-16;-i file         Read the grammar from the file.  If "-i" is not
  64.         specified, input will be read from the standard input.
  65.         .s.i-16;-m              Enable state minimization. Currently not
  66.         implemented, switch is a no-op.
  67.         .s.i-16;-o file         Write the output to the file.  If "-o" is not
  68.         specified, output will be written to file "lextab.c".
  69.         .s.i-16;-s              "Stand-alone" switch.  Supresses the line
  70.         "#include <stdio.h>" normally generated in the lex output.  Use this
  71.         if LEX is generating a module to be used in a program which does not
  72.         use the "standard I/O" package.
  73.         .s.i-16;-t table        Name the recognizer "table" instead of the
  74.         default "lextab".  If -o is not given, output will be written to file
  75.         "table.c".
  76.         .s.i-16;-v [file]       Verify -- write internal tables to the
  77.         indicated file.  If "-v" is given without a file name argument,
  78.         tables will be written to "lex.out".
  79.         .lm -16
  80.  
  81. diagnostics
  82.  
  83.         The following error messages may occur on invocation.  See lex
  84.         documentation for information on compilation errors.
  85.         .lm +8
  86.         .s.i -8;Can't create ...
  87.         .s.i -8;Cannot open ...
  88.         .s.i -8;Illegal option.
  89.         .s.i -8;Illegal switch combination.
  90.         .s
  91.         "-i", "-o" or "-t" given with "-e" or vice-versa
  92.         .s.i -8;Table name too long.
  93.         .s
  94.         The table name (argument to "-t") must not be longer than 8 bytes.
  95.         .s.i -8;Missing table name.
  96.         .s.i -8;Missing input file.
  97.         .s.i -8;Missing output file.
  98.         .s.i -8;Missing name.
  99.         .lm -8
  100.  
  101. author
  102.         Charles Forsyth
  103.         Modified by Martin Minnow, Bob Denny & Scott Guthery
  104.  
  105. bugs
  106.  
  107. #endif
  108.  
  109. #include <stdio.h>
  110. #include "system.h"        /* includes system configuration constants */
  111.  
  112. extern char *lalloc();
  113. extern char tolower();
  114.  
  115. struct  nfa     nfa[MAXNFA];
  116. struct  nfa     *nfap = &nfa[1];
  117.  
  118. struct  xset    sets[NCHARS];
  119. char    insets[NCHARS];
  120.  
  121. struct  trans   trans[NTRANS];
  122. struct  trans   *transp = &trans[0];
  123.  
  124. char    ccls[NCCLS][(NCHARS+1)/NBPC];
  125. int     nccls;
  126.  
  127. int     ndfa;
  128. struct  dfa     dfa[MAXDFA];
  129. struct  move    move[NNEXT];
  130.  
  131. char    *tabname = "lextab";
  132. char    tabfile[15];
  133. char    *infile         = NULL;
  134. char    *outfile        = NULL;
  135.  
  136. #ifdef DEBUG
  137. char    *dumpfile       = "lex.out";
  138. int     lldebug = 0;
  139. #endif
  140.  
  141. int  llnxtmax = 0;
  142.  
  143. FILE llout;
  144. FILE lexin;
  145. FILE lexlog;
  146.  
  147. /*
  148.  * Flags.  Allow globals only for those requiring same. Some only
  149.  * used for checking for bad combos.
  150.  */
  151.         int     aflag = 0;      /* Ignore non-ASCII in [^ ...] */
  152. static  int     eflag = 0;      /* Easy command line */
  153. static  int     iflag = 0;      /* "-i" given */
  154.         int     mflag = 0;      /* Enable state minimization (not imp.) */
  155. static  int     oflag = 0;      /* "-o" given */
  156.         int     sflag = 0;      /* Supress "#include <stdio.h>" in output */
  157. static  int     tflag = 0;      /* "-t" given */
  158.  
  159. struct  set     *setlist = 0;
  160.  
  161. main(argc, argv)
  162. int argc;
  163. char *argv[];
  164. {
  165.         register char *cp, *cp2;
  166.  
  167. #ifdef DEBUG
  168.         int vflag;
  169.         vflag = 0;
  170. #endif
  171.  
  172.         for (; argc>1 && *argv[1]=='-'; argv++, argc--)
  173.         switch (tolower(argv[1][1])) {
  174.  
  175. #ifdef DEBUG
  176.         /*
  177.          * Create "verification" file, describing the scanner.
  178.          */
  179.         case 'v':                               /* -v => lex.out        */
  180.                 vflag++;                        /* -v x.out => x.out    */
  181.                 if (argc > 2 && argv[2][1] != '1') {
  182.                         --argc;
  183.                         dumpfile = (++argv)[1];
  184.                 }
  185.                 break;
  186.         /*
  187.          * Enable debug displays
  188.          */
  189.         case 'd':
  190.                 lldebug++;
  191.                 break;
  192. #endif
  193.         /*
  194.          * Enable state minimization. Currently not implemented.
  195.          */
  196.         case 'm':
  197.                 mflag++;
  198.                 break;
  199.  
  200.         /*
  201.          * Disable matching of non-ASCII characters (codes > 177(8))
  202.          * for exception character classes (form "[^ ...]").
  203.          */
  204.         case 'a':
  205.                 aflag++;
  206.                 break;
  207.  
  208.         /*
  209.          * Supress "#include <stdio.h>" in generated
  210.          * code for programs not using standard I/O.
  211.          */
  212.         case 's':
  213.                 sflag++;
  214.                 break;
  215.  
  216.         /*
  217.          * "Easy" command line
  218.          */
  219.         case 'e':
  220.                 if(iflag || oflag || tflag) {
  221.                         error("Illegal switch combination\n");
  222.                         exit(1);
  223.                 }
  224.                 if (--argc <= 1) {
  225.                         error("Missing name\n");
  226.                         exit(1);
  227.                 }
  228.                 if (strlen(tabname = (++argv)[1]) > 8) {
  229.                         error("Name too long\n");
  230.                         exit(1);
  231.                 }
  232.                 infile = malloc(14);
  233.                 outfile = malloc(12);
  234.                 strcpy(infile, tabname); strcat(infile, ".lxi");
  235.                 printf("Input read from %s\n", infile);
  236.                 if ((lexin = fopen(infile, "r")) == NULL) {
  237.                         error("Cannot open input \"%s\"\n", infile);
  238.                         exit(1);
  239.                 }
  240.                 strcpy(outfile, tabname); strcat(outfile, ".c");
  241.                 break;
  242.  
  243.         /*
  244.          * Specify input file name.
  245.          */
  246.         case 'i':
  247.                 if (eflag) {
  248.                         error("Illegal switch combination\n");
  249.                         exit(1);
  250.                 }
  251.                 iflag++;
  252.                 if (--argc <= 1) {
  253.                         error("Missing input file\n");
  254.                         exit(1);
  255.                 }
  256.                 infile = (++argv)[1];
  257.                 printf("Input read from %s\n", infile);
  258.                 if ((lexin = fopen(infile, "r")) == NULL) {
  259.                         error("Cannot open input \"%s\"\n", infile);
  260.                         exit(1);
  261.                 }
  262.                 break;
  263.  
  264.         /*
  265.          * Specify output file name. Default = "lextab.c"
  266.          */
  267.         case 'o':
  268.                 if (eflag) {
  269.                         error("Illegal switch combination\n");
  270.                         exit(1);
  271.                 }
  272.                 oflag++;
  273.                 if (--argc <= 1) {
  274.                         error("Missing output file");
  275.                         exit(1);
  276.                 }
  277.                 outfile = (++argv)[1];
  278.                 break;
  279.  
  280.         /*
  281.          * Specify table name.  Default = "lextab.c".  If "-o"
  282.          * not given, output will go to "tabname.c".
  283.          */
  284.         case 't':
  285.                 if (eflag) {
  286.                         error("Illegal switch combination\n");
  287.                         exit(1);
  288.                 }
  289.                 tflag++;
  290.                 if (--argc <= 1) {
  291.                         error("Missing table name");
  292.                         exit(1);
  293.                 }
  294.                 if (strlen(tabname = (++argv)[1]) > 8) {
  295.                         error("Table name too long\n");
  296.                         exit(1);
  297.                 }
  298.                 break;
  299.  
  300.         default:
  301.                 error("Illegal option: %s\n", argv[1]);
  302.                 exit(1);
  303.         }
  304.  
  305. #ifdef DEBUG
  306.  
  307.         cp = (vflag) ? dumpfile : "NUL";
  308.         printf("Log written to %s\n", cp);
  309.         if ((lexlog = fopen(cp, "w")) == NULL) {
  310.                 error("Cannot open \"%s\"", cp);
  311.                 exit(1);
  312.         }
  313. #endif
  314.         if (infile == NULL) {
  315.                 infile = malloc(31);
  316.                 strcpy(infile, "lex.lxi");
  317.         }
  318.         cp = infile;                    /* Fold infile to lower case */
  319. /*
  320.  * The following 2 loops cannot use the form "*cp++ = tolower(*cp)" 
  321.  * due to a bug in VAX-11 C V1.0-09 where the pointer increment
  322.  * is done too soon (!).
  323.  */
  324.         while(*cp)
  325.                 {
  326.                 *cp = tolower(*cp);
  327.                 cp++;
  328.                 }
  329.         cp = tabname;                   /* Fold tabname to lower case */
  330.         while(*cp)
  331.                 {
  332.                 *cp = tolower(*cp);
  333.                 cp++;
  334.                 }
  335.         if (outfile == NULL) {
  336.                 /*
  337.                  * Typical hacker's idiom!
  338.                  */
  339.                 for (cp = tabname, cp2 = tabfile; *cp2 = *cp++;)
  340.                         cp2++;
  341.                 for (cp = ".c"; *cp2++ = *cp++;)
  342.                         ;
  343.                 outfile = tabfile;
  344.         }
  345.         printf("Analyzer written to %s\n", outfile);
  346.         if ((llout = fopen(outfile, "w"))==NULL) {
  347.                 error("Can't create %s\n", outfile);
  348.                 exit(1);
  349.         }
  350.  
  351.         heading();
  352.         fprintf(stderr, "Parse LEX source ...\n");
  353.         if (yyparse())
  354.                 error("Parse failed\n");
  355.         fprintf(stderr, "Build NFA then DFA ...\n");
  356.         dfabuild();                                             /* 01+ */
  357.         fprintf(stderr, "Minimize DFA ...\n");
  358.         dfamin();
  359.         fprintf(stderr, "Create C source ...\n");
  360.         dfaprint();
  361.         dfawrite();
  362. #ifdef DEBUG
  363.         stats();
  364.         fclose(lexlog);
  365. #endif                                                          /* 01- */
  366.         fprintf(stderr, "\07LEX done.\n");
  367.         fclose(llout);
  368. } /** END OF MAIN **/
  369.  
  370. /*
  371.  * This module was moved here from out.c so it could be called from
  372.  * ytab.c residing in same overlay region as out.c.
  373.  * 02-Dec-80  Bob Denny.
  374.  */
  375.                                                                 /* 01+ */
  376. ending()
  377. {
  378.         static int ended;
  379.  
  380.         if (ended++)
  381.                 return;
  382.         fprintf(llout, "\t}\n\treturn(LEXSKIP);\n}\n");
  383.         setline();
  384. }
  385.  
  386. #ifdef DEBUG
  387. stats()
  388. {
  389.         fprintf(lexlog, "\n");
  390.         fprintf(lexlog, "%d/%d NFA states, %d/%d DFA states\n",
  391.                 nfap-nfa, MAXNFA, ndfa, MAXDFA);
  392.         fprintf(lexlog, "%d/%d entries in move vectors\n", llnxtmax, NNEXT);
  393. }
  394.  
  395. /*
  396.  * Print a state set on { ... } form on lexlog.
  397.  */
  398. pset(t, nf)
  399. register struct set *t;
  400. {
  401.         register i;
  402.  
  403.         fprintf(lexlog, "{");
  404.         for (i = 0; i < t->s_len; i++)
  405.                 if (nf)
  406.                         fprintf(lexlog, " %d", t->s_els[i]-nfa); else
  407.                         fprintf(lexlog, " %d", t->s_els[i]);
  408.         fprintf(lexlog, "}");
  409. }
  410.  
  411. /*
  412.  * Print a character to lexlog in readable form.
  413.  * Returns the number of characters generated.
  414.  */
  415. chprint(ch)
  416. {
  417.         register char *s;
  418.  
  419.         ch &= 0377;
  420.         switch (ch) {
  421.         case '\t':
  422.                 s = "\\t";
  423.                 break;
  424.         case '\n':
  425.                 s = "\\n";
  426.                 break;
  427.         case '\b':
  428.                 s = "\\b";
  429.                 break;
  430.         case '\r':
  431.                 s = "\\r";
  432.                 break;
  433.         default:
  434.                 if(ch<040 || ch>=0177)
  435.                         {
  436.                         fprintf(lexlog, "\\%03o", ch);
  437.                         return(4);
  438.                         }
  439.                 else
  440.                         {
  441.                         putc(ch, lexlog);
  442.                         return(1);
  443.                         }
  444.         }
  445.         fprintf(lexlog, s);
  446.         return(2);
  447. }
  448. #endif
  449.  
  450. /*
  451.  * The following functions simply
  452.  * allocate various kinds of
  453.  * structures.
  454.  */
  455. struct nfa *
  456. newnfa(ch, nf1, nf2)
  457. struct nfa *nf1, *nf2;
  458. {
  459.         register struct nfa *nf;
  460.  
  461.         if ((nf = nfap++) >= &nfa[MAXNFA]) {
  462.                 error("Too many NFA states");
  463.                 exit(1);
  464.         }
  465.         nf->n_char = ch;
  466.         nf->n_succ[0] = nf1;
  467.         nf->n_succ[1] = nf2;
  468.         nf->n_trans = 0;
  469.         nf->n_flag = 0;
  470.         nf->n_look = 0;
  471.         return(nf);
  472. }
  473.  
  474. newdfa()
  475. {
  476.         register struct dfa *df;
  477.  
  478.         if ((df = &dfa[ndfa++]) >= &dfa[MAXDFA]) {
  479.                 error("Out of dfa states");
  480.                 exit(1);
  481.         }
  482.         return(df);
  483. }
  484.  
  485. char *
  486. newccl(ccl)
  487. char *ccl;
  488. {
  489.         register char *p, *q;
  490.         register i;
  491.         int j;
  492.  
  493.         for (j = 0; j < nccls; j++) {
  494.                 p = ccl;
  495.                 q = ccls[j];
  496.                 for (i = sizeof(ccls[j]); i--;)
  497.                         if (*p++ != *q++)
  498.                                 goto cont;
  499.                 return(ccls[j]);
  500.         cont:;
  501.         }
  502.         if (nccls >= NCCLS) {
  503.                 error("Too many character classes");
  504.                 exit(1);
  505.         }
  506.         p = ccl;
  507.         q = ccls[j = nccls++];
  508.         for (i = sizeof(ccls[j]); i--;)
  509.                 *q++ = *p++;
  510.         return(ccls[j]);
  511. }
  512.  
  513. struct trans *
  514. newtrans(st, en)
  515. struct nfa *st, *en;
  516. {
  517.         register struct trans *tp;
  518.  
  519.         if ((tp = transp++) >= &trans[NTRANS]) {
  520.                 error("Too many translations");
  521.                 exit(1);
  522.         }
  523.         tp->t_start = st;
  524.         tp->t_final = en;
  525.         en->n_trans = tp;
  526.         return(tp);
  527. }
  528.  
  529. /*
  530.  * Create a new set. `sf', if set, indicates that the elements of the
  531.  * set are states of an NFA). If `sf' is not set, the elements are state
  532.  * numbers of a DFA.
  533.  */
  534. struct set *
  535. newset(v, i, sf)
  536. register struct nfa **v;
  537. register i;
  538. {
  539.         register struct set *t;
  540.         register k;
  541.         int setcomp();
  542.  
  543.         qsort(v, i, sizeof(*v), setcomp);
  544.         for (t = setlist; t; t = t->s_next)
  545.                 if (t->s_len==i && eqvec(t->s_els, v, i))
  546.                         return(t);
  547.         t = lalloc(1, sizeof(*t)+i*sizeof(t->s_els[0]), "set nodes");
  548.         t->s_next = setlist;
  549.         setlist = t;
  550.         t->s_final = 0;
  551.         t->s_state =  0;
  552.         t->s_flag = 0;
  553.         t->s_len = i;
  554.         t->s_group = 0;
  555.         t->s_look = 0;
  556.         for (v += i; i;) {
  557.                 --v;
  558.                 if (sf) {
  559.                         if ((*v)->n_char==FIN)
  560.                                 t->s_final =  (*v)-nfa;
  561.                         if ((*v)->n_flag&LOOK)
  562.                                 t->s_look |= 1<<(*v)->n_look;
  563.                 } else {
  564.                         k = *v;
  565.                         dfa[k].df_name->s_group = t;
  566.                 }
  567.                 t->s_els[--i] = *v;
  568.         }
  569.         return(t);
  570. }
  571.  
  572. setcomp(n1p, n2p)
  573. struct nfa **n1p, **n2p;
  574. {
  575.         register struct nfa *n1, *n2;
  576.  
  577.         n1 = *n1p;
  578.         n2 = *n2p;
  579.         if (n1 > n2)
  580.                 return(1);
  581.         if (n1==n2)
  582.                 return(0);
  583.         return(-1);
  584. }
  585.  
  586. eqvec(a, b, i)
  587. register *a, *b, i;
  588. {
  589.         if (i)
  590.                 do {
  591.                         if (*a++ != *b++)
  592.                                 return(0);
  593.                 } while (--i);
  594.         return(1);
  595. }
  596.  
  597. /*
  598.  * Ask for core, and complain if there is no more.
  599.  */
  600. char *
  601. lalloc(n, s, w)
  602. char *w;
  603. {
  604.         register char *cp;
  605.  
  606.         if ((cp = calloc(n, s)) == NULL) {
  607.                 fprintf(stderr, "No space for %s", w);
  608. #ifdef DEBUG
  609.                 if (lldebug)
  610.                         dfaprint();
  611. #endif
  612.                 exit(1);
  613.         }
  614.         return(cp);
  615. }
  616.  
  617. error(format, argument)
  618. char *format, *argument;
  619. {
  620.     fprintf(stderr, format, argument);
  621. }