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. auxiliary_section:
  136.         auxiliaries '%' '%'
  137. |       '%' '%'
  138. ;
  139.  
  140. auxiliaries:
  141.         auxiliaries auxiliary
  142. |       auxiliary
  143. ;
  144.  
  145. auxiliary:
  146.         namedef '=' regexp ';' ={
  147.                 dp = $3;
  148.                 nl = $1;
  149.                 np = nl->nl_base;
  150.                 nl->nl_start = dp->d_start;
  151.                 nl->nl_final = dp->d_final;
  152.                 nl->nl_end = nfap;
  153.                 printf("NFA for %s\n", nl->nl_name);
  154.                 nfaprint(dp->d_start, nl->nl_base);
  155.                 nbase = lalloc(i = nl->nl_end-nl->nl_base, sizeof(*nbase),
  156.                         "nfa storage");
  157.                 copynfa(nl, nbase, dp);
  158.                 nl->nl_start = dp->d_start;
  159.                 nl->nl_final = dp->d_final;
  160.                 nl->nl_end = nbase+i;
  161.                 nl->nl_base = nbase;
  162.                 nfap = np;
  163.                 ignore = spccl(nl->nl_name, "ignore", dp);
  164.                 breakc = spccl(nl->nl_name, "break", dp);
  165.                 illeg = spccl(nl->nl_name, "illegal", dp);
  166.         }
  167. |       '%' '{'         ={ copycode(); }
  168. ;
  169.  
  170. namedef:
  171.         NAME    ={
  172.                 $$ = lookup($1);
  173.                 $$->nl_base = nfap;
  174.                 if ($$->nl_start)
  175.                         error("%s redefined", $$->nl_name);
  176.         }
  177. ;
  178.  
  179. name:
  180.         NAME    ={ $$ = lookup($1); }
  181. ;
  182.  
  183. regexp:
  184.         CCLASS ={
  185.                 np = elem(CCL, $1);
  186.                 $$ = newdp(np, np->n_succ[0] = elem(FIN));
  187.         }
  188. |       STRING ={
  189.                 cp = $1;
  190.                 if (strlen == 0) {
  191.                         np = elem(EPSILON);
  192.                         $$ = newdp(np, np->n_succ[0] = elem(FIN));
  193.                         return;
  194.                 }
  195.  
  196.  
  197.  
  198.  
  199.                 $$ = np = elem(*cp++);
  200.                 while (--strlen > 0)
  201.                         np = np->n_succ[0] = elem(*cp++);
  202.                 $$ = newdp($$, np->n_succ[0] = elem(FIN));
  203.         }
  204. |       name    ={
  205.                 if ((nl = $1)->nl_end == 0) {
  206.                         error("%s not defined", nl->nl_name);
  207.                         nl->nl_base = nl->nl_end = elem(FIN);
  208.                         nl->nl_start = nl->nl_final = nl->nl_base;
  209.                 }
  210.                 $$ = dp = lalloc(1, sizeof(*dp), "dfa input");
  211.                 nbase = nfap;
  212.                 i = nl->nl_end-nl->nl_base;
  213.                 if ((nfap += i) >= &nfa[MAXNFA]) {
  214.                         error("Out of NFA nodes");
  215.                         exit(1);
  216.                 }
  217.                 copynfa(nl, nbase, dp);
  218.         }
  219. |       regexp '*' ={
  220.                 $$ = dp = $1;
  221.                 dp->d_start = newnfa(EPSILON, np = dp->d_start, 0);
  222.                 dp->d_final->n_char = EPSILON;
  223.                 dp->d_final->n_succ[0] = np;
  224.                 dp->d_final->n_succ[1] = np = elem(FIN);
  225.                 dp->d_start->n_succ[1] = np;
  226.                 dp->d_final = np;
  227.         }
  228. |       regexp '|' regexp ={
  229.                 $$ = dp = $1;
  230.                 dp->d_start = newnfa(EPSILON, dp->d_start, $3->d_start);
  231.                 dp->d_final->n_char = EPSILON;
  232.                 dp->d_final = dp->d_final->n_succ[0] = np = elem(FIN);
  233.                 dp = $3;
  234.                 dp->d_final->n_char = EPSILON;
  235.                 dp->d_final->n_succ[0] = np;
  236.                 cfree($3);
  237.         }
  238. |       regexp regexp %prec CONCAT ={
  239.                 $$ = $1;
  240.                 dp = $2;
  241.                 np = $$->d_final;
  242.                 $$->d_final = dp->d_final;
  243.                 np->n_char = dp->d_start->n_char;
  244.                 np->n_ccl = dp->d_start->n_ccl;
  245.                 np->n_succ[0] = dp->d_start->n_succ[0];
  246.                 np->n_succ[1] = dp->d_start->n_succ[1];
  247.                 cfree($2);
  248.         }
  249. |       '(' regexp ')' ={ $$ = $2; }
  250. ;
  251.  
  252. translation_section:
  253.         translations ={
  254.                 ending();
  255.         trans1:
  256.                 printf("\nNFA for complete syntax\n");
  257.                 printf("state 0\n");
  258.                 for (tp = trans; tp < transp; tp++)
  259.                         printf("\tepsilon\t%d\n", tp->t_start-nfa);
  260.                 for (tp = trans; tp < transp; tp++)
  261.  
  262.  
  263.  
  264.  
  265.                         nfaprint(tp->t_start, nfa);
  266.                 dfabuild();
  267.                 dfamin();
  268.                 dfaprint();
  269.                 dfawrite();
  270.                 stats();
  271.         }
  272. |       ={ goto trans1; }
  273. ;
  274.  
  275. translations:
  276.         translations translation
  277. |       llactr translation
  278. ;
  279.  
  280. llactr:
  281.         ={
  282.                 llactr();
  283.         }
  284. ;
  285.  
  286. translation:
  287.         pattern action ={ dp = $1;  newtrans(dp->d_start, dp->d_final); }
  288. |       '%' '{'         ={ copycode(); }
  289. |       '%' '%'         ={
  290.                 ending();
  291.                 while ((c = get()) != EOF)
  292.                         putc(c, llout);
  293.         }
  294. ;
  295.  
  296. action:
  297.         '{'     ={ action(); }
  298. ;
  299.  
  300. pattern:
  301.         regexp '/' regexp ={
  302.                 if (nlook >= NBPW)
  303.                         error("More than %d translations with lookahead",NBPW);
  304.                 $$ = dp = $1;
  305.                 np = dp->d_final;
  306.                 np->n_char = EPSILON;
  307.                 np->n_flag |= LOOK;
  308.                 np->n_succ[0] = $3->d_start;
  309.                 dp->d_final = $3->d_final;
  310.                 np->n_look = nlook;
  311.                 dp->d_final->n_look = nlook++;
  312.                 dp->d_final->n_flag |= FLOOK;
  313.                 cfree($3);
  314.         }
  315. |       regexp
  316. ;
  317.  
  318. %%
  319. /*
  320.  * Lexical analyser
  321.  * (it isn't done with lex...)
  322.  */
  323. char    buffer[150];
  324.  
  325. yylex()
  326. {
  327.  
  328.  
  329.  
  330.  
  331.         register c;
  332.         register char *cp;
  333.         int lno;
  334.  
  335.         if (yyline == 0)
  336.                 yyline++;
  337. loop:
  338.         c = get();
  339.         if (isupper(c)) {
  340.                 name(c);
  341.                 for (cp = yylval; c = *cp; cp++)
  342.                         if (isupper(c))
  343.                                 *cp = tolower(c);
  344.                 return(STRING);
  345.         } else if (islower(c) || c == '_') {
  346.                 name(c);
  347.                 return(NAME);
  348.         }
  349.         switch (c) {
  350.         case EOF:
  351.                 return(0);
  352.  
  353.         case '[':
  354.                 return(cclass());
  355.  
  356.         case '(':
  357.         case ')':
  358.         case '{':
  359.         case '}':
  360.         case '*':
  361.         case '|':
  362.         case '=':
  363.         case ';':
  364.         case '%':
  365.                 return(c);
  366.  
  367.         case '/':
  368.                 if ((c = get()) != '*') {
  369.                         unget(c);
  370.                         return('/');
  371.                 }
  372.                 lno = yyline;
  373.                 for (; c != EOF; c = get())
  374.                         if (c == '*')
  375.                                 if ((c = get()) == '/')
  376.                                         goto loop; else
  377.                                         unget(c);
  378.                 yyline = lno;
  379.                 error("End of file in comment");
  380.  
  381.         case '\'':
  382.         case '"':
  383.                 yylval = buffer;
  384.                 string(c);
  385.                 return(STRING);
  386.  
  387.         case '\n':
  388.         case ' ':
  389.         case '\t':
  390.                 goto loop;
  391.  
  392.         default:
  393.  
  394.  
  395.  
  396.  
  397.                 yylval = buffer;
  398.                 if (c == '\\') {
  399.                         unget(c);
  400.                         c = mapch(EOF);
  401.                 }
  402.                 buffer[0] = c;
  403.                 buffer[1] = 0;
  404.                 strlen = 1;
  405.                 return(STRING);
  406.         }
  407. }
  408.  
  409. char    ccl[(NCHARS+1)/NBPC];
  410.  
  411. cclass()
  412. {
  413.         register c, i, lc;
  414.         int compl;
  415.  
  416.         compl = 0;
  417.         for (i = 0; i < sizeof ccl; i++)
  418.                 ccl[i] = 0;
  419.         if ((c = get()) == '^')
  420.                 compl++; else
  421.                 unget(c);
  422.         lc = -1;
  423.         while ((c = mapc(']')) != EOF) {
  424.                 if (c == '-' && lc >= 0) {
  425.                         if ((c = mapc(']')) == EOF)
  426.                                 break;
  427.                         for (i = lc; i <= c; i++)
  428.                                 ccl[i/NBPC] |= 1<<(i%NBPC);
  429.                         lc = -1;
  430.                         continue;
  431.                 }
  432.                 ccl[c/NBPC] |= 1<<(c%NBPC);
  433.                 lc = c;
  434.         }
  435.         if (compl) {
  436.                 for (i = 0; i < sizeof ccl; i++)
  437.                         ccl[i] ^= -1;
  438.                 if (aflag == 0)
  439.                         for (i = 0200; i < (1<<NBPC); i++)
  440.                                 ccl[i/NBPC] &= ~(1 << (i%NBPC));
  441.         }
  442.         yylval = newccl(ccl);
  443.         return(CCLASS);
  444. }
  445.  
  446. string(ec)
  447. {
  448.         register char *cp;
  449.         register c;
  450.  
  451.         for (cp = buffer; (c = mapc(ec)) != EOF;)
  452.                 *cp++ = c;
  453.         *cp = 0;
  454.         strlen = cp-buffer;
  455. }
  456.  
  457. mapc(ec)
  458. {
  459.  
  460.  
  461.  
  462.  
  463.         register c, v, i;
  464.  
  465.         if ((c = get()) == ec)
  466.                 return(EOF);
  467.         switch(c) {
  468.         case EOF:
  469.                 error("End of file in string");
  470.                 return(c);
  471.  
  472.         case '\\':
  473.                 if ((c = get()) >= '0' && c <= '7') {
  474.                         i = 0;
  475.                         for (v = 0; c>='0' && c<='7' && i++<3; c = get())
  476.                                 v = v*010 + c-'0';
  477.                         unget(c);
  478.                         return(v&0377);
  479.                 }
  480.                 switch (c) {
  481.                 case 'n':
  482.                         return('\n');
  483.  
  484.                 case 't':
  485.                         return('\t');
  486.  
  487.                 case 'b':
  488.                         return('\b');
  489.  
  490.                 case 'r':
  491.                         return('\r');
  492.  
  493.                 case '\n':
  494.                         yyline++;
  495.                         return(mapc(ec));
  496.                 }
  497.  
  498.         default:
  499.                 return(c);
  500.         }
  501. }
  502.  
  503. name(c)
  504. register c;
  505. {
  506.         register char *cp;
  507.  
  508.         for (yylval=cp=buffer; isalpha(c) || isdigit(c) || c=='_'; c=get())
  509.                 *cp++ = c;
  510.         *cp = 0;
  511.         strlen = cp-buffer;
  512.         unget(c);
  513. }
  514.  
  515. /*
  516.  * Miscellaneous functions
  517.  * used only by lex.y
  518.  */
  519. struct nfa *
  520. elem(k, v)
  521. {
  522.         struct nfa *fp;
  523.  
  524.         fp = newnfa(k, 0, 0);
  525.  
  526.  
  527.  
  528.  
  529.         if (k == CCL)
  530.                 fp->n_ccl = v;
  531.         return(fp);
  532. }
  533.  
  534. struct des *
  535. newdp(st, fi)
  536. struct nfa *st, *fi;
  537. {
  538.         register struct des *dp;
  539.  
  540.         dp = lalloc(1, sizeof(*dp), "dfa input");
  541.         dp->d_start = st;
  542.         dp->d_final = fi;
  543.         return(dp);
  544. }
  545.  
  546. action()
  547. {
  548.         register c;
  549.         int lno, lev;
  550.  
  551.         newcase(transp-trans);
  552.         lno = yyline;
  553.         lev = 0;
  554.         for (; (c = get()) != EOF && (c != '}' || lev); putc(c, llout))
  555.                 if (c == '{')
  556.                         lev++;
  557.                 else if (c == '}')
  558.                         lev--;
  559.                 else if (c == '\'' || c == '"') {
  560.                         putc(c, llout);
  561.                         skipstr(c);
  562.                 }
  563.         fprintf(llout, "\n\tbreak;\n");
  564.         if (c == EOF) {
  565.                 yyline = lno;
  566.                 error("End of file in action");
  567.         }
  568. }
  569.  
  570. skipstr(ec)
  571. register ec;
  572. {
  573.         register c;
  574.  
  575.         while ((c = get()) != ec && c != EOF) {
  576.                 putc(c, llout);
  577.                 if (c == '\\' && (c = get()) != EOF)
  578.                         putc(c, llout);
  579.         }
  580. }
  581.  
  582.  
  583. copycode()
  584. {
  585.         int lno;
  586.         register c;
  587.  
  588.         setline();
  589.         lno = yyline;
  590.         for (; (c = get()) != EOF; putc(c, llout))
  591.  
  592.  
  593.  
  594.  
  595.                 if (c == '%') {
  596.                         if ((c = get()) == '}')
  597.                                 return;
  598.                         unget(c);
  599.                         c = '%';
  600.                 }
  601.         yyline = lno;
  602.         error("Incomplete %{ declaration");
  603.         exit(1);
  604. }
  605.  
  606. struct nlist *
  607. lookup(s)
  608. register char *s;
  609. {
  610.         register struct nlist *nl;
  611.         register char *cp;
  612.         int i;
  613.  
  614.         for (nl = nlist; nl; nl = nl->nl_next)
  615.                 if (streq(s, nl->nl_name))
  616.                         return(nl);
  617.         nl = lalloc(1, sizeof(*nl), "namelist");
  618.         nl->nl_start = nl->nl_end = nl->nl_base = nl->nl_end = 0;
  619.         nl->nl_next = nlist;
  620.         nlist = nl;
  621.         i = 0;
  622.         for (cp = s; *cp++;)
  623.                 i++;
  624.         nl->nl_name = cp = lalloc(i+1, sizeof(*cp), "namelist");
  625.         while (*cp++ = *s++)
  626.                 ;
  627.         return(nl);
  628. }
  629.  
  630. copynfa(nl, nbase, dp)
  631. struct nlist *nl;
  632. struct des *dp;
  633. struct nfa *nbase;
  634. {
  635.         register struct nfa *np, *ob;
  636.         register j;
  637.         int i, ix;
  638.  
  639.         ob = nl->nl_base;
  640.         i = nl->nl_end-ob;
  641.         copy(ob, sizeof(*np), i, nbase);
  642.         for (np = nbase; i-- > 0; np++) {
  643.                 np->n_flag &= ~NPRT;
  644.                 for (j = 0; j < 2; j++)
  645.                         if (np->n_succ[j])
  646.                                 np->n_succ[j] = (np->n_succ[j]-ob)+nbase;
  647.         }
  648.         dp->d_start = (nl->nl_start-ob)+nbase;
  649.         dp->d_final = (nl->nl_final-ob)+nbase;
  650. }
  651.  
  652. char *
  653. spccl(nm, isit, dp)
  654. char *nm, *isit;
  655. register struct des *dp;
  656. {
  657.  
  658.  
  659.  
  660.  
  661.         if (!streq(nm, isit))
  662.                 return(0);
  663.         if (dp->d_start->n_char == CCL &&
  664.             dp->d_start->n_succ[0] == dp->d_final)
  665.                 return(dp->d_start->n_ccl);
  666.         error("Illegal %s class", isit);
  667.         return(0);
  668. }
  669.  
  670. get()
  671. {
  672.         register c;
  673.  
  674.         if ((c = getc(stdin)) == '\n')
  675.                 yyline++;
  676.         return(c);
  677. }
  678.  
  679. unget(c)
  680. register c;
  681. {
  682.         if (c == '\n')
  683.                 yyline--;
  684.         ungetc(c, stdin);
  685. }
  686.  
  687. error(s)
  688. char *s;
  689. {
  690.         if (yyline)
  691.                 fprintf(stderr, "%d: ", yyline);
  692.         fprintf(stderr, "%r", &s);
  693.         if (yychar > 256)
  694.                 fprintf(stderr, " near `%s'", yysterm[yychar-256]);
  695.         else if (yychar < 256 && yychar > 0)
  696.                 fprintf(stderr, " near `%c'", yychar);
  697.         fprintf(stderr, "\n");
  698. }
  699. se if (yychar < 256 && yychar > 0)
  700.                 fprintf(stderr, " near `%c'", yych