ROLEINVS.Cpp
上传用户:tenhai
上传日期:2021-02-19
资源大小:492k
文件大小:6k
源码类别:

组合框控件

开发平台:

Visual C++

  1. #include "stdafx.h"
  2. #include "error.h"
  3. #include "symbol.h"
  4. #include "grmrgrph.h"
  5. #include "rrtbl.h"
  6. #include "roleinvs.h"
  7. #define FMARK 0x01
  8. #define LMARK 0x10
  9. #define MAXRENTRY 30031
  10. typedef struct rolentry_t{
  11. unsigned int rul;
  12. unsigned int rol;
  13. struct rolentry_t *nxt;
  14. }rolentry_t;
  15. rolentry_t **rolhashtbl;
  16. addrolinvr(symbol_node_t *psrcs, symbol_arc_t *parc, int term, 
  17.            char mode){
  18.   rulrol_struct *pnewrr;
  19. //  rulrol_struct *ptrrr, *qtrrr;
  20.   int index;
  21.   
  22.   EGEN((pnewrr=(rulrol_struct *)malloc(sizeof (rulrol_struct)))==NULL,
  23.        MEMFUL, return -1;)
  24.   pnewrr->rule=parc->rule;
  25.   pnewrr->role=parc->role;
  26.   pnewrr->expsymb=psrcs->sid;
  27.   /*debug use*/
  28.   /*printf("%s as %d.%dn", parc->aim->literal, parc->rule, parc->role);*/
  29.   if (mode=='l')
  30.      pnewrr->expmode='r';
  31.   else
  32.      pnewrr->expmode='s';
  33.   index=term*(tntcount-1)+parc->aim->sid-1;
  34.   if (mode=='f'){
  35.      pnewrr->nxt=rr_tbl[index].lrr;
  36.      rr_tbl[index].lrr=pnewrr;
  37.   }
  38.   else{
  39.   pnewrr->nxt=rr_tbl[index].rrr;
  40.   rr_tbl[index].rrr=pnewrr;
  41.   /*
  42.   ptrrr=rr_tbl[index].rrr;
  43.   qtrrr=NULL;
  44.   while ((ptrrr!=NULL)&&
  45.   RGT(pnewrr->rule, pnewrr->role, ptrrr->rule, ptrrr->role)){
  46.   qtrrr=ptrrr;
  47.   ptrrr=ptrrr->nxt;
  48.   }
  49.   if (!qtrrr)
  50.  rr_tbl[index].rrr=pnewrr;
  51.   else
  52.  qtrrr->nxt=pnewrr;
  53.   pnewrr->nxt=ptrrr;
  54.   */
  55.   }
  56.   return 0;
  57. }
  58. roleinvr(void){
  59.   char *mark;
  60.   symbol_node_t **symstack;
  61.   char *tagstack;
  62.   int stackp;
  63.   int stacksz;
  64.   unsigned int term;
  65.   stacksz=2*ntcount;
  66.   EGEN((mark=(char *)calloc(ntcount, sizeof (char)))==NULL,
  67.        MEMFUL, return -1;)
  68.   EGEN((symstack=(symbol_node_t **)
  69.        calloc(stacksz, sizeof(symbol_node_t *)))==NULL,
  70.        MEMFUL, {free(mark); return -1;})
  71.   EGEN((tagstack=(char *)calloc(stacksz, sizeof(char)))==NULL,
  72.        MEMFUL, {free(mark);free(symstack);return -1;})
  73.   ECHK(rrini();, {free(mark);free(symstack);free(tagstack);return -1;})
  74.   for (term=0;term<tcount;term++){
  75.       unsigned int ntidx;
  76.       /*debug use*/
  77.       /*printf("======n");*/
  78.       /*printf("终结符:%5sn", code2tnode(term)->literal);*/
  79.       /*clear all marks*/
  80.       for (ntidx=0; ntidx<ntcount; mark[ntidx++]=0)
  81.           ;
  82.       /*push in the stub*/
  83.       stackp=0;
  84.       symstack[0]=code2tnode(term);
  85.       tagstack[0]='F';
  86.       while (stackp>=0){
  87.             symbol_node_t *psrcs=symstack[stackp], *paims;      
  88.             symbol_arc_t *parc;
  89.             char mode=tagstack[stackp];
  90.             int aimsidx;
  91.             /*pop up a symbol to be processed*/
  92.             stackp--;
  93.             switch (mode){
  94.               case 'F':
  95.                /*propgate upward*/
  96.                for (parc=psrcs->fstlst;parc!=NULL;parc=parc->nxt){
  97.                    ECHK(addrolinvr(psrcs, parc, term, 'f');,
  98.                         {free(symstack);free(tagstack);free(mark);
  99.                          return -1;}) 
  100.                    paims=parc->aim;
  101.                    aimsidx=paims->sid-tcount;
  102.                    if (!(mark[aimsidx] & FMARK)){
  103.                       mark[aimsidx]|=FMARK;
  104.                       symstack[++stackp]=paims;
  105.                       tagstack[stackp]='F';
  106.                    }
  107.                }
  108.                /*propgate leftward*/
  109.                for(parc=psrcs->adjlst;parc!=NULL;parc=parc->nxt){
  110.                   ECHK(addrolinvr(psrcs, parc, term, 'a');,
  111.                        {free(symstack);free(tagstack);free(mark);
  112.                         return -1;})
  113.                   paims=parc->aim;
  114.                   aimsidx=paims->sid-tcount;
  115.                   if (aimsidx>=0 && !(mark[aimsidx] & LMARK)){
  116.                      mark[aimsidx]|=LMARK;
  117.                      symstack[++stackp]=paims;
  118.                      tagstack[stackp]='D';
  119.                   }
  120.                }
  121.                break;
  122.               case 'D':
  123.                /*propgate downward*/
  124.                for (parc=psrcs->lstlst;parc!=NULL;parc=parc->nxt){
  125.                    ECHK(addrolinvr(psrcs, parc, term, 'l');,
  126.                        {free(symstack);free(tagstack);free(mark);
  127.                         return -1;})
  128.                    paims=parc->aim;
  129.                    aimsidx=paims->sid-tcount;
  130.                    if (aimsidx>=0 && !(mark[aimsidx] & LMARK)){
  131.                       mark[aimsidx]|=LMARK;
  132.                       symstack[++stackp]=paims;
  133.                       tagstack[stackp]='D';
  134.                    }
  135.                }
  136.                break;
  137.             }
  138.       }
  139.   }
  140.   free(symstack);
  141.   free(tagstack);
  142.   free(mark);
  143.   rrready=1;
  144.   return 0;
  145. }
  146. genexpec(void){
  147.   unsigned int i, j;
  148.   expecini();
  149.   EXP(0, 0)=ssym->sid;
  150.   EXP(0, 1)=tntcount;
  151.   for (i=1; i<=rulcount; i++){
  152.       j=EXP(i, rightlenof(i))=leftof(i);
  153.       for (j=0; j<rightlenof(i); j++){
  154.           EXP(i, j)=rightof(i, j+1);
  155.   }
  156.   }
  157.   return 0;
  158. }
  159. rolentry_t *rlsearch(int hashval, unsigned int rul, unsigned int rol){
  160.   rolentry_t *currentry;
  161.   unsigned int i,j;
  162.   int flag;
  163.   for (currentry=rolhashtbl[hashval];currentry!=NULL;currentry=currentry->nxt){
  164.       if ((rightlenof(currentry->rul)-currentry->rol)==(rightlenof(rul)-rol)){
  165.   flag=1;
  166.   for (i=currentry->rol+1, j=rol+1; j<=rightlenof(rul); i++, j++){
  167.   if (rightof(currentry->rul, i)!=rightof(rul, j)){
  168.   flag=0;
  169.   break;
  170.   }
  171.   }
  172.   if (flag)
  173.   break;
  174.   
  175.   }
  176.   }
  177.   return currentry;
  178. }
  179. int rlrelease(int hashval){
  180.   rolentry_t *prentry, *qrentry;
  181.   for (prentry=rolhashtbl[hashval];prentry!=NULL;prentry=qrentry){
  182.       qrentry=prentry->nxt;
  183.       free(prentry);
  184.   }
  185.   return 0;
  186. }
  187. unsigned int hashr(unsigned int i, unsigned int j){
  188.   unsigned hashval, iter;
  189.   rolentry_t *newrentry;
  190.   for (hashval=0, iter=j; iter<rightlenof(i); iter++)
  191.       hashval=rightof(i, iter+1)+31*hashval;
  192.   hashval=hashval % MAXRENTRY;
  193.   newrentry=rlsearch(hashval, i, j);
  194.   if (newrentry==NULL){
  195.      newrentry=(rolentry_t *)malloc(sizeof(rolentry_t));
  196.  newrentry->rul=i;
  197.  newrentry->rol=j;
  198.      newrentry->nxt=rolhashtbl[hashval];
  199.      rolhashtbl[hashval]=newrentry;
  200.  
  201.   } 
  202.   return (unsigned int)(newrentry);
  203. }
  204. genpostfix(){
  205. int i;
  206. unsigned int j, k;
  207. rolhashtbl=(rolentry_t **)malloc(sizeof(rolentry_t *)*MAXRENTRY);
  208. for (i=0; i<MAXRENTRY; i++)
  209. rolhashtbl[i]=NULL;
  210. PST(0,0)=0;
  211. for (j=1; j<=rulcount; j++){
  212. for (k=0; k<rightlenof(j); k++){
  213. PST(j,k)=hashr(j, k);
  214. }
  215. }
  216. for (i=0; i<MAXRENTRY; i++){
  217. rlrelease(i);
  218. }
  219. free(rolhashtbl);
  220. return 0;
  221. }