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