home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / C / LEX.ZIP / LEX.Y < prev    next >
Encoding:
Text File  |  1983-11-19  |  15.3 KB  |  700 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  
  31.  
  32.  
  33.  
  34.  
  35.  
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67. /*
  68.  * Copyright (c) 1978 Charles H. Forsyth
  69.  */
  70.  
  71. /*
  72.  *              W A R N I N G
  73.  *
  74.  * This file is NOT identical with ytab.c.  Several changes which were
  75.  * made directly to ytab.c have not been made to lex.y
  76.  *
  77.  * If you have access to yacc and rebuild ytab.c from lex.y, it is
  78.  * essential that you compare the current ytab.c with the new version,
  79.  * incorporating the necessary changes.
  80.  */
  81.  
  82. /*
  83.  * lex -- grammar/lexical analyser
  84.  */
  85.  
  86. %{
  87. #include <stdio.h>
  88. #include "lexlex.h"
  89. char    copr[]  "Copyright (c) 1978 Charles H. Forsyth";
  90. struct des {
  91.         struct nfa *d_start;
  92.         struct nfa *d_final;
  93. };
  94. struct nlist {
  95.         struct  nlist   *nl_next;
  96.         struct  nfa     *nl_base;
  97.         struct  nfa     *nl_end;
  98.         struct  nfa     *nl_start;
  99.         struct  nfa     *nl_final;
  100.         char    *nl_name;
  101. } *nlist;
  102. int     strlen;
  103. extern  struct  nfa     *elem();
  104. extern  struct  des     *newdp();
  105. extern  struct  nlist   *lookup();
  106. extern  char            *spccl();
  107. %}
  108. %term NAME CCLASS STRING CONCAT
  109.  
  110. %left ';'
  111. %left '='
  112. %left '/'
  113. %left '|'
  114. %left '(' NAME STRING CCLASS
  115. %left CONCAT
  116. %left '*'
  117. %%
  118. %{
  119.         struct nfa *np, *nbase;
  120.         char *cp;
  121.         struct des *dp;
  122.         struct trans *tp;
  123.         struct nlist *nl;
  124.         int i, c;
  125. %}
  126. lexfile:
  127.         auxiliary_section translation_section
  128. |
  129.  
  130.  
  131.  
  132.  
  133.  
  134. ;
  135.  
  136. auxiliary_section:
  137.         auxiliaries '%' '%'
  138. |       '%' '%'
  139. ;
  140.  
  141. auxiliaries:
  142.         auxiliaries auxiliary
  143. |       auxiliary
  144. ;
  145.  
  146. auxiliary:
  147.         namedef '=' regexp ';' ={
  148.                 dp = $3;
  149.                 nl = $1;
  150.                 np = nl->nl_base;
  151.                 nl->nl_start = dp->d_start;
  152.                 nl->nl_final = dp->d_final;
  153.                 nl->nl_end = nfap;
  154.                 printf("NFA for %s\n", nl->nl_name);
  155.                 nfaprint(dp->d_start, nl->nl_base);
  156.                 nbase = lalloc(i = nl->nl_end-nl->nl_base, sizeof(*nbase),
  157.                         "nfa storage");
  158.                 copynfa(nl, nbase, dp);
  159.                 nl->nl_start = dp->d_start;
  160.                 nl->nl_final = dp->d_final;
  161.                 nl->nl_end = nbase+i;
  162.                 nl->nl_base = nbase;
  163.                 nfap = np;
  164.                 ignore = spccl(nl->nl_name, "ignore", dp);
  165.                 breakc = spccl(nl->nl_name, "break", dp);
  166.                 illeg = spccl(nl->nl_name, "illegal", dp);
  167.         }
  168. |       '%' '{'         ={ copycode(); }
  169. ;
  170.  
  171. namedef:
  172.         NAME    ={
  173.                 $$ = lookup($1);
  174.                 $$->nl_base = nfap;
  175.                 if ($$->nl_start)
  176.                         error("%s redefined", $$->nl_name);
  177.         }
  178. ;
  179.  
  180. name:
  181.         NAME    ={ $$ = lookup($1); }
  182. ;
  183.  
  184. regexp:
  185.         CCLASS ={
  186.                 np = elem(CCL, $1);
  187.                 $$ = newdp(np, np->n_succ[0] = elem(FIN));
  188.         }
  189. |       STRING ={
  190.                 cp = $1;
  191.                 if (strlen == 0) {
  192.                         np = elem(EPSILON);
  193.                         $$ = newdp(np, np->n_succ[0] = elem(FIN));
  194.                         return;
  195.                 }
  196.  
  197.  
  198.  
  199.  
  200.  
  201.                 $$ = np = elem(*cp++);
  202.                 while (--strlen > 0)
  203.                         np = np->n_succ[0] = elem(*cp++);
  204.                 $$ = newdp($$, np->n_succ[0] = elem(FIN));
  205.         }
  206. |       name    ={
  207.                 if ((nl = $1)->nl_end == 0) {
  208.                         error("%s not defined", nl->nl_name);
  209.                         nl->nl_base = nl->nl_end = elem(FIN);
  210.                         nl->nl_start = nl->nl_final = nl->nl_base;
  211.                 }
  212.                 $$ = dp = lalloc(1, sizeof(*dp), "dfa input");
  213.                 nbase = nfap;
  214.                 i = nl->nl_end-nl->nl_base;
  215.                 if ((nfap += i) >= &nfa[MAXNFA]) {
  216.                         error("Out of NFA nodes");
  217.                         exit(1);
  218.                 }
  219.                 copynfa(nl, nbase, dp);
  220.         }
  221. |       regexp '*' ={
  222.                 $$ = dp = $1;
  223.                 dp->d_start = newnfa(EPSILON, np = dp->d_start, 0);
  224.                 dp->d_final->n_char = EPSILON;
  225.                 dp->d_final->n_succ[0] = np;
  226.                 dp->d_final->n_succ[1] = np = elem(FIN);
  227.                 dp->d_start->n_succ[1] = np;
  228.                 dp->d_final = np;
  229.         }
  230. |       regexp '|' regexp ={
  231.                 $$ = dp = $1;
  232.                 dp->d_start = newnfa(EPSILON, dp->d_start, $3->d_start);
  233.                 dp->d_final->n_char = EPSILON;
  234.                 dp->d_final = dp->d_final->n_succ[0] = np = elem(FIN);
  235.                 dp = $3;
  236.                 dp->d_final->n_char = EPSILON;
  237.                 dp->d_final->n_succ[0] = np;
  238.                 cfree($3);
  239.         }
  240. |       regexp regexp %prec CONCAT ={
  241.                 $$ = $1;
  242.                 dp = $2;
  243.                 np = $$->d_final;
  244.                 $$->d_final = dp->d_final;
  245.                 np->n_char = dp->d_start->n_char;
  246.                 np->n_ccl = dp->d_start->n_ccl;
  247.                 np->n_succ[0] = dp->d_start->n_succ[0];
  248.                 np->n_succ[1] = dp->d_start->n_succ[1];
  249.                 cfree($2);
  250.         }
  251. |       '(' regexp ')' ={ $$ = $2; }
  252. ;
  253.  
  254. translation_section:
  255.         translations ={
  256.                 ending();
  257.         trans1:
  258.                 printf("\nNFA for complete syntax\n");
  259.                 printf("state 0\n");
  260.                 for (tp = trans; tp < transp; tp++)
  261.                         printf("\tepsilon\t%d\n", tp->t_start-nfa);
  262.                 for (tp = trans; tp < transp; tp++)
  263.  
  264.  
  265.  
  266.  
  267.  
  268.                         nfaprint(tp->t_start, nfa);
  269.                 dfabuild();
  270.                 dfamin();
  271.                 dfaprint();
  272.                 dfawrite();
  273.                 stats();
  274.         }
  275. |       ={ goto trans1; }
  276. ;
  277.  
  278. translations:
  279.         translations translation
  280. |       llactr translation
  281. ;
  282.  
  283. llactr:
  284.         ={
  285.                 llactr();
  286.         }
  287. ;
  288.  
  289. translation:
  290.         pattern action ={ dp = $1;  newtrans(dp->d_start, dp->d_final); }
  291. |       '%' '{'         ={ copycode(); }
  292. |       '%' '%'         ={
  293.                 ending();
  294.                 while ((c = get()) != EOF)
  295.                         putc(c, llout);
  296.         }
  297. ;
  298.  
  299. action:
  300.         '{'     ={ action(); }
  301. ;
  302.  
  303. pattern:
  304.         regexp '/' regexp ={
  305.                 if (nlook >= NBPW)
  306.                         error("More than %d translations with lookahead",NBPW);
  307.                 $$ = dp = $1;
  308.                 np = dp->d_final;
  309.                 np->n_char = EPSILON;
  310.                 np->n_flag |= LOOK;
  311.                 np->n_succ[0] = $3->d_start;
  312.                 dp->d_final = $3->d_final;
  313.                 np->n_look = nlook;
  314.                 dp->d_final->n_look = nlook++;
  315.                 dp->d_final->n_flag |= FLOOK;
  316.                 cfree($3);
  317.         }
  318. |       regexp
  319. ;
  320.  
  321. %%
  322. /*
  323.  * Lexical analyser
  324.  * (it isn't done with lex...)
  325.  */
  326. char    buffer[150];
  327.  
  328. yylex()
  329. {
  330.  
  331.  
  332.  
  333.  
  334.  
  335.         register c;
  336.         register char *cp;
  337.         int lno;
  338.  
  339.         if (yyline == 0)
  340.                 yyline++;
  341. loop:
  342.         c = get();
  343.         if (isupper(c)) {
  344.                 name(c);
  345.                 for (cp = yylval; c = *cp; cp++)
  346.                         if (isupper(c))
  347.                                 *cp = tolower(c);
  348.                 return(STRING);
  349.         } else if (islower(c) || c == '_') {
  350.                 name(c);
  351.                 return(NAME);
  352.         }
  353.         switch (c) {
  354.         case EOF:
  355.                 return(0);
  356.  
  357.         case '[':
  358.                 return(cclass());
  359.  
  360.         case '(':
  361.         case ')':
  362.         case '{':
  363.         case '}':
  364.         case '*':
  365.         case '|':
  366.         case '=':
  367.         case ';':
  368.         case '%':
  369.                 return(c);
  370.  
  371.         case '/':
  372.                 if ((c = get()) != '*') {
  373.                         unget(c);
  374.                         return('/');
  375.                 }
  376.                 lno = yyline;
  377.                 for (; c != EOF; c = get())
  378.                         if (c == '*')
  379.                                 if ((c = get()) == '/')
  380.                                         goto loop; else
  381.                                         unget(c);
  382.                 yyline = lno;
  383.                 error("End of file in comment");
  384.  
  385.         case '\'':
  386.         case '"':
  387.                 yylval = buffer;
  388.                 string(c);
  389.                 return(STRING);
  390.  
  391.         case '\n':
  392.         case ' ':
  393.         case '\t':
  394.                 goto loop;
  395.  
  396.         default:
  397.  
  398.  
  399.  
  400.  
  401.  
  402.                 yylval = buffer;
  403.                 if (c == '\\') {
  404.                         unget(c);
  405.                         c = mapch(EOF);
  406.                 }
  407.                 buffer[0] = c;
  408.                 buffer[1] = 0;
  409.                 strlen = 1;
  410.                 return(STRING);
  411.         }
  412. }
  413.  
  414. char    ccl[(NCHARS+1)/NBPC];
  415.  
  416. cclass()
  417. {
  418.         register c, i, lc;
  419.         int compl;
  420.  
  421.         compl = 0;
  422.         for (i = 0; i < sizeof ccl; i++)
  423.                 ccl[i] = 0;
  424.         if ((c = get()) == '^')
  425.                 compl++; else
  426.                 unget(c);
  427.         lc = -1;
  428.         while ((c = mapc(']')) != EOF) {
  429.                 if (c == '-' && lc >= 0) {
  430.                         if ((c = mapc(']')) == EOF)
  431.                                 break;
  432.                         for (i = lc; i <= c; i++)
  433.                                 ccl[i/NBPC] |= 1<<(i%NBPC);
  434.                         lc = -1;
  435.                         continue;
  436.                 }
  437.                 ccl[c/NBPC] |= 1<<(c%NBPC);
  438.                 lc = c;
  439.         }
  440.         if (compl) {
  441.                 for (i = 0; i < sizeof ccl; i++)
  442.                         ccl[i] ^= -1;
  443.                 if (aflag == 0)
  444.                         for (i = 0200; i < (1<<NBPC); i++)
  445.                                 ccl[i/NBPC] &= ~(1 << (i%NBPC));
  446.         }
  447.         yylval = newccl(ccl);
  448.         return(CCLASS);
  449. }
  450.  
  451. string(ec)
  452. {
  453.         register char *cp;
  454.         register c;
  455.  
  456.         for (cp = buffer; (c = mapc(ec)) != EOF;)
  457.                 *cp++ = c;
  458.         *cp = 0;
  459.         strlen = cp-buffer;
  460. }
  461.  
  462. mapc(ec)
  463. {
  464.  
  465.  
  466.  
  467.  
  468.  
  469.         register c, v, i;
  470.  
  471.         if ((c = get()) == ec)
  472.                 return(EOF);
  473.         switch(c) {
  474.         case EOF:
  475.                 error("End of file in string");
  476.                 return(c);
  477.  
  478.         case '\\':
  479.                 if ((c = get()) >= '0' && c <= '7') {
  480.                         i = 0;
  481.                         for (v = 0; c>='0' && c<='7' && i++<3; c = get())
  482.                                 v = v*010 + c-'0';
  483.                         unget(c);
  484.                         return(v&0377);
  485.                 }
  486.                 switch (c) {
  487.                 case 'n':
  488.                         return('\n');
  489.  
  490.                 case 't':
  491.                         return('\t');
  492.  
  493.                 case 'b':
  494.                         return('\b');
  495.  
  496.                 case 'r':
  497.                         return('\r');
  498.  
  499.                 case '\n':
  500.                         yyline++;
  501.                         return(mapc(ec));
  502.                 }
  503.  
  504.         default:
  505.                 return(c);
  506.         }
  507. }
  508.  
  509. name(c)
  510. register c;
  511. {
  512.         register char *cp;
  513.  
  514.         for (yylval=cp=buffer; isalpha(c) || isdigit(c) || c=='_'; c=get())
  515.                 *cp++ = c;
  516.         *cp = 0;
  517.         strlen = cp-buffer;
  518.         unget(c);
  519. }
  520.  
  521. /*
  522.  * Miscellaneous functions
  523.  * used only by lex.y
  524.  */
  525. struct nfa *
  526. elem(k, v)
  527. {
  528.         struct nfa *fp;
  529.  
  530.         fp = newnfa(k, 0, 0);
  531.  
  532.  
  533.  
  534.  
  535.  
  536.         if (k == CCL)
  537.                 fp->n_ccl = v;
  538.         return(fp);
  539. }
  540.  
  541. struct des *
  542. newdp(st, fi)
  543. struct nfa *st, *fi;
  544. {
  545.         register struct des *dp;
  546.  
  547.         dp = lalloc(1, sizeof(*dp), "dfa input");
  548.         dp->d_start = st;
  549.         dp->d_final = fi;
  550.         return(dp);
  551. }
  552.  
  553. action()
  554. {
  555.         register c;
  556.         int lno, lev;
  557.  
  558.         newcase(transp-trans);
  559.         lno = yyline;
  560.         lev = 0;
  561.         for (; (c = get()) != EOF && (c != '}' || lev); putc(c, llout))
  562.                 if (c == '{')
  563.                         lev++;
  564.                 else if (c == '}')
  565.                         lev--;
  566.                 else if (c == '\'' || c == '"') {
  567.                         putc(c, llout);
  568.                         skipstr(c);
  569.                 }
  570.         fprintf(llout, "\n\tbreak;\n");
  571.         if (c == EOF) {
  572.                 yyline = lno;
  573.                 error("End of file in action");
  574.         }
  575. }
  576.  
  577. skipstr(ec)
  578. register ec;
  579. {
  580.         register c;
  581.  
  582.         while ((c = get()) != ec && c != EOF) {
  583.                 putc(c, llout);
  584.                 if (c == '\\' && (c = get()) != EOF)
  585.                         putc(c, llout);
  586.         }
  587. }
  588.  
  589.  
  590. copycode()
  591. {
  592.         int lno;
  593.         register c;
  594.  
  595.         setline();
  596.         lno = yyline;
  597.         for (; (c = get()) != EOF; putc(c, llout))
  598.  
  599.  
  600.  
  601.  
  602.  
  603.                 if (c == '%') {
  604.                         if ((c = get()) == '}')
  605.                                 return;
  606.                         unget(c);
  607.                         c = '%';
  608.                 }
  609.         yyline = lno;
  610.         error("Incomplete %{ declaration");
  611.         exit(1);
  612. }
  613.  
  614. struct nlist *
  615. lookup(s)
  616. register char *s;
  617. {
  618.         register struct nlist *nl;
  619.         register char *cp;
  620.         int i;
  621.  
  622.         for (nl = nlist; nl; nl = nl->nl_next)
  623.                 if (streq(s, nl->nl_name))
  624.                         return(nl);
  625.         nl = lalloc(1, sizeof(*nl), "namelist");
  626.         nl->nl_start = nl->nl_end = nl->nl_base = nl->nl_end = 0;
  627.         nl->nl_next = nlist;
  628.         nlist = nl;
  629.         i = 0;
  630.         for (cp = s; *cp++;)
  631.                 i++;
  632.         nl->nl_name = cp = lalloc(i+1, sizeof(*cp), "namelist");
  633.         while (*cp++ = *s++)
  634.                 ;
  635.         return(nl);
  636. }
  637.  
  638. copynfa(nl, nbase, dp)
  639. struct nlist *nl;
  640. struct des *dp;
  641. struct nfa *nbase;
  642. {
  643.         register struct nfa *np, *ob;
  644.         register j;
  645.         int i, ix;
  646.  
  647.         ob = nl->nl_base;
  648.         i = nl->nl_end-ob;
  649.         copy(ob, sizeof(*np), i, nbase);
  650.         for (np = nbase; i-- > 0; np++) {
  651.                 np->n_flag &= ~NPRT;
  652.                 for (j = 0; j < 2; j++)
  653.                         if (np->n_succ[j])
  654.                                 np->n_succ[j] = (np->n_succ[j]-ob)+nbase;
  655.         }
  656.         dp->d_start = (nl->nl_start-ob)+nbase;
  657.         dp->d_final = (nl->nl_final-ob)+nbase;
  658. }
  659.  
  660. char *
  661. spccl(nm, isit, dp)
  662. char *nm, *isit;
  663. register struct des *dp;
  664. {
  665.  
  666.  
  667.  
  668.  
  669.  
  670.         if (!streq(nm, isit))
  671.                 return(0);
  672.         if (dp->d_start->n_char == CCL &&
  673.             dp->d_start->n_succ[0] == dp->d_final)
  674.                 return(dp->d_start->n_ccl);
  675.         error("Illegal %s class", isit);
  676.         return(0);
  677. }
  678.  
  679. get()
  680. {
  681.         register c;
  682.  
  683.         if ((c = getc(stdin)) == '\n')
  684.                 yyline++;
  685.         return(c);
  686. }
  687.  
  688. unget(c)
  689. register c;
  690. {
  691.         if (c == '\n')
  692.                 yyline--;
  693.         ungetc(c, stdin);
  694. }
  695.  
  696. error(s)
  697. char *s;
  698. {
  699.         if (yyline)
  700.                 fprintf(stderr, "%d: ", yyline);
  701.         fprintf(stderr, "%r", &s);
  702.         if (yychar > 256)
  703.                 fprintf(stderr, " near `%s'", yysterm[yychar-256]);
  704.         else if (yychar < 256 && yychar > 0)
  705.                 fprintf(stderr, " near `%c'", yychar);
  706.         fprintf(stderr, "\n");
  707. }
  708. se if (yychar < 256 && yychar > 0)
  709.                 fprintf(stderr, " near `%c'", yych