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