home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / compiler / miracl / slr.c < prev   
C/C++ Source or Header  |  1993-01-13  |  9KB  |  377 lines
  1. /*    SLR parser generator
  2.  
  3. given slr grammar in file `grammar', generate characteristic fsm for it
  4. `grammar.c' is generated from cfsm to recognize the grammar
  5. `grammar.o' gives description of state machine
  6.  
  7. */
  8.  
  9.  
  10. #include <stdio.h>
  11. #include <ctype.h>
  12. #include <string.h>
  13. #include <system.h>
  14.  
  15. #define gen(p) fputs(p,output)
  16.  
  17. FILE *grammar, *output, *des;
  18.  
  19. int states[100], sprod[1000], sposn[500], togen[500],
  20.     tsnext[500], tsposn[500], trn[500], sttype[100],
  21.     nstates=0, nterms=0, nnonterms=0, ntogen=1, trans=0, trs[1000];
  22.  
  23. char *pptr, *prods[100], terms[50], nonterms[50], exnon[50], trc[1000];
  24.  
  25. void main()
  26. {
  27.    char o, ia[100], out[200], rt[50],
  28.     *in, *tr, *aptr, *optr, *rtptr, nxtchr;
  29.  
  30.    int    check, prct, z, rules=0, rout, flag=0, nxt=0, cflag,
  31.     i, stype, rdstate, reduce, start, tf, tt, ot;
  32.  
  33.    grammar=fopen("grammar","r"); output=fopen("grammar.c","w");
  34.    des=fopen("grammar.o","w");
  35.  
  36.    if(grammar==NULL || output==NULL || des==NULL)
  37.       {
  38.       printf("file open failure\n"), 
  39.       exit(1);
  40.       }
  41.  
  42.    for(i=0; i<100; i++) prods[i]=malloc(10);
  43.  
  44.    *terms='\0'; *nonterms='\0';
  45.  
  46.    /**** get grammar from input file */
  47.  
  48.    for(;;)
  49.       {
  50.       if(fgets(ia,100,grammar)==0) break;
  51.       in=ia;
  52.       while(isspace(*in)) in++;
  53.  
  54.       tr=prods[rules++]; *tr=*in++;
  55.       while(isspace(*in)) in++;
  56.  
  57.       if(!isupper(*tr) || *in++!='-' || *in++!='>')
  58.      printf("bad grammar file\n"),
  59.      fclose(output),
  60.      exit(0);
  61.  
  62.       while(isspace(*in)) in++;
  63.  
  64.       while(*tr++)
  65.      if((*tr=*in++)==' ') --tr;
  66.  
  67.       *(tr-2)='\0';
  68.       }
  69.  
  70.    fclose(grammar);
  71.  
  72.    /**** show grammar */
  73.  
  74.    fprintf(des,"\ninput grammar : found %d productions ...\n\n",rules);
  75.  
  76.    for(i=0; i<rules; i++)
  77.       fprintf(des,"  %c -> .%s. \n",*prods[i],prods[i]+1);
  78.  
  79.    /**** make list `nonterms' of non-terminals for which productions exist */
  80.  
  81.    for(i=0; i<rules; i++)
  82.       {
  83.       for(flag=0, check=0; check<nnonterms; check++)
  84.       if(prods[i][0]==nonterms[check]) flag=1;
  85.  
  86.       if(!flag) nonterms[nnonterms++]=prods[i][0];
  87.       }
  88.  
  89.    nonterms[nnonterms]='\0';
  90.    fprintf(des,"\nnon-terminals are .%s.\n",nonterms);
  91.  
  92.    /**** check that every rhs non-terminal has a production,list non-terminals */
  93.  
  94.    for(i=0; i<rules; i++)
  95.       {
  96.       tr=prods[i];
  97.       while(*++tr)
  98.      {
  99.      flag=0;
  100.      if(isupper(*tr))
  101.         {
  102.         aptr=nonterms;
  103.         while(*aptr) if(*aptr++==*tr) flag=1;
  104.  
  105.         if(!flag)
  106.            printf("can\'t find production for %c in rule %s\n",
  107.                             *tr,prods[rout]),
  108.            exit(1);
  109.         }
  110.      else
  111.         {
  112.         aptr=terms;
  113.         while(*aptr) if(*aptr++==*tr) flag=1;
  114.         if(!flag)
  115.            { nterms++; *aptr++=*tr; *aptr='\0';}
  116.         }
  117.      }
  118.       }
  119.    fprintf(des,"\nterminals are .%s.\n",terms);
  120.  
  121.    /**** find starting S rule ... usually the first, must be unique */
  122.  
  123.    for(start=-1, i=0; i<rules; i++)
  124.       if(prods[i][0]=='S')
  125.      if(start==-1)
  126.         start=i;
  127.      else
  128.         printf("starting rule must be unique\n"),
  129.         exit(1);
  130.  
  131.  
  132.    /**** expand the grammar into a characteristic fsm */
  133.  
  134.    tsnext[0]=0, tsposn[0]=0, tsnext[1]=-1, tsposn[1]=-1, togen[0]=0;
  135.  
  136.    while(ntogen>nstates)  /* while there are states to expand, do nstate'th */
  137.       {
  138.       if(nstates>0)
  139.      {
  140.      nxt=states[nstates-1];
  141.      while(sprod[nxt++]!=-1);
  142.      }
  143.       else
  144.      nxt=0;
  145.  
  146.       states[nstates]=nxt; exnon[0]='\0';
  147.       tf=togen[nstates]; tt=nxt;
  148.       rdstate=0; reduce=0;
  149.  
  150.       /* copy unexpanded state to state table */
  151.       while(((sprod[tt]=tsnext[tf])&(sposn[tt]=tsposn[tf]))+1) tt++, tf++;
  152.  
  153.       while(nxt<tt)  /* expand each following nterm until complete */
  154.      {
  155.      if(isupper(o=prods[sprod[nxt]][sposn[nxt]+1])) /* non-terminal next? */
  156.         {
  157.         aptr=exnon;
  158.  
  159.         while(*aptr)
  160.            if(*aptr==o)
  161.           break;
  162.            else
  163.           aptr++;
  164.  
  165.         if(*aptr=='\0')  /* then we must expand the nterm's productions */
  166.            {
  167.            *aptr++=o; *aptr='\0';
  168.  
  169.            for(i=0; i<rules; i++)  /* insert prods for nterm */
  170.           if(prods[i][0]==o)
  171.              {
  172.              sprod[tt]=i;   sposn[tt++]=0;
  173.              sprod[tt]=-1;  sposn[tt]=-1;
  174.              }
  175.            }
  176.         }
  177.  
  178.      nxt++;
  179.      }
  180.  
  181.       ssort(nstates); nxt=states[nstates++];
  182.       tf=togen[ntogen-1]; while(tsnext[tf++]+1);
  183.  
  184.       /* now copy each branch out of the state into the unexp table and try it */
  185.       while(sprod[nxt]!=-1)
  186.      {
  187.      nxtchr=prods[sprod[nxt]][sposn[nxt]+1];
  188.  
  189.      tf=togen[ntogen-1];
  190.      while(tsnext[tf++]+1);
  191.      ot=tf; togen[ntogen]=tf;
  192.  
  193.      if(nxtchr=='\0')
  194.         {
  195.         trc[trans]=(char)sposn[nxt];
  196.         trs[trans]=nxt++;
  197.         trn[trans++]=-2; reduce=1;
  198.         }
  199.      else
  200.         {
  201.         while((sprod[nxt]!=-1)&& (nxtchr==prods[sprod[nxt]][sposn[nxt]+1]))
  202.            {
  203.            tsnext[ot]=sprod[nxt];
  204.            tsposn[ot++]=sposn[nxt++]+1;
  205.            }
  206.  
  207.         tsnext[ot]=-1; tsposn[ot]=-1;
  208.         trc[trans]=nxtchr; rdstate=1;
  209.  
  210.         if(z=findstate(ntogen))
  211.            trn[trans++]=z;
  212.         else
  213.            trn[trans++]=ntogen++;
  214.         }
  215.      }
  216.  
  217.       trn[trans]=-1;
  218.       trc[trans++]='0'+rdstate+reduce*2;
  219.       }
  220.  
  221.    /**** list cfsm's transitions */
  222.  
  223.    tt=0;
  224.  
  225.    for(i=0; i<nstates; i++)
  226.       {
  227.       fprintf(des,"\nstate  %d    \n",i);
  228.       while(trn[tt++]!=-1)
  229.      if(trn[tt-1]!=-2)
  230.         fprintf(des," %c %d \n",trc[tt-1],trn[tt-1]);
  231.      else
  232.         fprintf(des," $\n");
  233.  
  234.       stype=trc[tt-1]-'0'; sttype[i]=stype;
  235.       if(stype==1) fprintf(des,"read\n");
  236.       if(stype==2) fprintf(des,"reduce\n");
  237.       if(stype==3) fprintf(des,"inadequate\n");
  238.       }
  239.  
  240.    /**** generate the parser */
  241.  
  242.    tt=0;
  243.  
  244.    fputs("#include <stdio.h>\n#include <system.h>\n\n",output);
  245.    fputs("#define push(a)\t*++sp=a;\n#define pop()",output);
  246.    fputs("\t(sp==stack?(exit(0),*sp):*sp--)\n\n",output);
  247.    fputs("char stack[1000],*sp,res[5000],ia[100],*in;\n\n",output);
  248.    fputs("main()\n{\n\tint state,item,resn=0,finish=0;\n\n",output);
  249.    fputs("\tsp=stack; gets(in=ia); push(0);",output);
  250.    fputs("\n\n\tfor(;;)\n\t{\n\t\tstate=pop(); push(state);\n",output);
  251.    fputs("\t\tif(finish) break;\n\n\t\tswitch(state)\n\t\t{\n",output);
  252.  
  253.    for(i=0; i<nstates; i++)    /* generate the cfsm's case statement */
  254.       switch(sttype[i])
  255.      {
  256.      case 1: /* read state */
  257.         fprintf(output,"\t\tcase %2d : push(item=*in++);\n",i);
  258.         fprintf(output,"\n\t\t\tswitch(item){\n");
  259.  
  260.         while(trn[tt++]!=-1)
  261.            fprintf(output,"\t\t\t\tcase \'%c\':push(%d); break;\n",
  262.                 trc[tt-1],trn[tt-1]);
  263.  
  264.         fprintf(output,"\t\t\t\tdefault :");
  265.         fprintf(output,"printf(\"parse failed\");exit(0);\n");
  266.         fprintf(output,"\t\t\t} break;\n\n");
  267.         break;
  268.  
  269.      case 2: /* reduce state */
  270.         fprintf(output,"\t\tcase %2d : ",i);
  271.  
  272.         for(ot=0; ot<trc[tt]; ot++)
  273.            fprintf(output,"pop();pop();");
  274.  
  275.         fprintf(output," *--in=\'%c\';\n",prods[sprod[states[i]]][0]);
  276.  
  277.         fprintf(output,"\t\t\tres[resn++]=%d;",sprod[states[i]]);
  278.  
  279.         if(prods[sprod[states[i]]][0]=='S')
  280.            fprintf(output," if(*in==\'S\') finish=1;");
  281.  
  282.         fprintf(output," break;\n\n");
  283.         tt++;tt++;
  284.         break;
  285.  
  286.      case 3: /* inadequate state */
  287.         tf=tt; rtptr=rt;
  288.         while(trn[tf]!=-1)
  289.            if(trn[tf++]!=-2)
  290.               *rtptr++=trc[tf-1];
  291.            else
  292.               o=prods[z=sprod[trs[tf-1]]][0];
  293.  
  294.         *rtptr='\0'; rtptr=rt;
  295.         fprintf(output,"\t\tcase %2d : if(*in==\'%c\'",i,*rtptr++);
  296.  
  297.         while(*rtptr)
  298.            fprintf(output,"||*in==\'%c\'",*rtptr++);
  299.  
  300.         fprintf(output,"){\n\t\t\t\tpush(item=*in++);");
  301.         fprintf(output,"\n\n\t\t\t\tswitch(item){\n"); tf=tt;
  302.  
  303.         while(trn[tt++]!=-1)
  304.            if(trn[tt-1]!=-2)
  305.               fprintf(output,"\t\t\t\t\tcase \'%c\':push(%d); break;\n",
  306.             trc[tt-1],trn[tt-1]);
  307.  
  308.         fprintf(output,"\t\t\t\tdefault :");
  309.         fprintf(output,"printf(\"parse failed\");exit(0);}\n");
  310.         fprintf(output,"\t\t\t\t} else {\n\t\t\t");
  311.  
  312.         while(trn[tf++]!=-2);
  313.  
  314.         for(ot=0; ot<trc[tf-1]; ot++)
  315.            fprintf(output,"pop();pop();");
  316.  
  317.         fprintf(output," *--in=\'%c\';\n",o);
  318.         fprintf(output,"\t\t\t\tres[resn++]=%d; ",z);
  319.         fprintf(output,"\n\t\t\t} break;\n");
  320.         break;
  321.      }
  322.  
  323.    fprintf(output,"\n\t\t}\n\t}\n\n\tprintf(\"parsed: \");\n\tfor(item=0;");
  324.    fprintf(output,"item<resn;item++)\n\t\tprintf(\" %%2d\",res[item]);\n}\n");
  325.  
  326.    fclose(des);
  327.    fclose(output);
  328. }
  329.  
  330.  
  331. /**** sort the configuration set for a given state */
  332.  
  333. ssort(int st)
  334. {
  335.    int pstart,nstat,t,la,lb;
  336.  
  337.    for(nstat=0, pstart=states[st]; sprod[pstart++]!=-1; nstat++) ;
  338.  
  339.    if(nstat<2) return;
  340.    pstart=states[st];
  341.  
  342.    for(la=0; la<nstat; la++)
  343.       for(lb=pstart; lb<(pstart+nstat-1); lb++)
  344.  
  345.      if(1000*(int)prods[sprod[lb]][sposn[lb]+1]+50*(int)sprod[lb]+sposn[lb]>
  346.         1000*(int)prods[sprod[lb+1]][sposn[lb+1]+1]+50*(int)sprod[lb+1]+sposn[lb+1])
  347.            {
  348.            t=sprod[lb]; sprod[lb]=sprod[lb+1]; sprod[lb+1]=t;
  349.            t=sposn[lb]; sposn[lb]=sposn[lb+1]; sposn[lb+1]=t;
  350.            }
  351. }
  352.  
  353. /**** compare two unexpanded state sets */
  354.  
  355. int compare(int f1, int f2)
  356. {
  357.    if(f1==f2) return 0;
  358.    f1=togen[f1]; f2=togen[f2];
  359.  
  360.    while(tsnext[f1]==tsnext[f2] && tsposn[f1++]==tsposn[f2++])
  361.       if(tsnext[f1-1]==-1) return 1;
  362.  
  363.    return 0;
  364. }
  365.  
  366. /**** find if state already exists */
  367.  
  368. int findstate(int state)
  369. {
  370.    int i;
  371.  
  372.    for(i=0; i<ntogen; i++)
  373.       if(compare(state,i)) return i;
  374.  
  375.    return 0;
  376. }
  377.