ROLEINVS.Cpp
资源名称:ictprop.rar [点击查看]
上传用户:tenhai
上传日期:2021-02-19
资源大小:492k
文件大小:6k
源码类别:
组合框控件
开发平台:
Visual C++
- #include "stdafx.h"
- #include "error.h"
- #include "symbol.h"
- #include "grmrgrph.h"
- #include "rrtbl.h"
- #include "roleinvs.h"
- #define FMARK 0x01
- #define LMARK 0x10
- #define MAXRENTRY 30031
- typedef struct rolentry_t{
- unsigned int rul;
- unsigned int rol;
- struct rolentry_t *nxt;
- }rolentry_t;
- rolentry_t **rolhashtbl;
- addrolinvr(symbol_node_t *psrcs, symbol_arc_t *parc, int term,
- char mode){
- rulrol_struct *pnewrr;
- // rulrol_struct *ptrrr, *qtrrr;
- int index;
- EGEN((pnewrr=(rulrol_struct *)malloc(sizeof (rulrol_struct)))==NULL,
- MEMFUL, return -1;)
- pnewrr->rule=parc->rule;
- pnewrr->role=parc->role;
- pnewrr->expsymb=psrcs->sid;
- /*debug use*/
- /*printf("%s as %d.%dn", parc->aim->literal, parc->rule, parc->role);*/
- if (mode=='l')
- pnewrr->expmode='r';
- else
- pnewrr->expmode='s';
- index=term*(tntcount-1)+parc->aim->sid-1;
- if (mode=='f'){
- pnewrr->nxt=rr_tbl[index].lrr;
- rr_tbl[index].lrr=pnewrr;
- }
- else{
- pnewrr->nxt=rr_tbl[index].rrr;
- rr_tbl[index].rrr=pnewrr;
- /*
- ptrrr=rr_tbl[index].rrr;
- qtrrr=NULL;
- while ((ptrrr!=NULL)&&
- RGT(pnewrr->rule, pnewrr->role, ptrrr->rule, ptrrr->role)){
- qtrrr=ptrrr;
- ptrrr=ptrrr->nxt;
- }
- if (!qtrrr)
- rr_tbl[index].rrr=pnewrr;
- else
- qtrrr->nxt=pnewrr;
- pnewrr->nxt=ptrrr;
- */
- }
- return 0;
- }
- roleinvr(void){
- char *mark;
- symbol_node_t **symstack;
- char *tagstack;
- int stackp;
- int stacksz;
- unsigned int term;
- stacksz=2*ntcount;
- EGEN((mark=(char *)calloc(ntcount, sizeof (char)))==NULL,
- MEMFUL, return -1;)
- EGEN((symstack=(symbol_node_t **)
- calloc(stacksz, sizeof(symbol_node_t *)))==NULL,
- MEMFUL, {free(mark); return -1;})
- EGEN((tagstack=(char *)calloc(stacksz, sizeof(char)))==NULL,
- MEMFUL, {free(mark);free(symstack);return -1;})
- ECHK(rrini();, {free(mark);free(symstack);free(tagstack);return -1;})
- for (term=0;term<tcount;term++){
- unsigned int ntidx;
- /*debug use*/
- /*printf("======n");*/
- /*printf("终结符:%5sn", code2tnode(term)->literal);*/
- /*clear all marks*/
- for (ntidx=0; ntidx<ntcount; mark[ntidx++]=0)
- ;
- /*push in the stub*/
- stackp=0;
- symstack[0]=code2tnode(term);
- tagstack[0]='F';
- while (stackp>=0){
- symbol_node_t *psrcs=symstack[stackp], *paims;
- symbol_arc_t *parc;
- char mode=tagstack[stackp];
- int aimsidx;
- /*pop up a symbol to be processed*/
- stackp--;
- switch (mode){
- case 'F':
- /*propgate upward*/
- for (parc=psrcs->fstlst;parc!=NULL;parc=parc->nxt){
- ECHK(addrolinvr(psrcs, parc, term, 'f');,
- {free(symstack);free(tagstack);free(mark);
- return -1;})
- paims=parc->aim;
- aimsidx=paims->sid-tcount;
- if (!(mark[aimsidx] & FMARK)){
- mark[aimsidx]|=FMARK;
- symstack[++stackp]=paims;
- tagstack[stackp]='F';
- }
- }
- /*propgate leftward*/
- for(parc=psrcs->adjlst;parc!=NULL;parc=parc->nxt){
- ECHK(addrolinvr(psrcs, parc, term, 'a');,
- {free(symstack);free(tagstack);free(mark);
- return -1;})
- paims=parc->aim;
- aimsidx=paims->sid-tcount;
- if (aimsidx>=0 && !(mark[aimsidx] & LMARK)){
- mark[aimsidx]|=LMARK;
- symstack[++stackp]=paims;
- tagstack[stackp]='D';
- }
- }
- break;
- case 'D':
- /*propgate downward*/
- for (parc=psrcs->lstlst;parc!=NULL;parc=parc->nxt){
- ECHK(addrolinvr(psrcs, parc, term, 'l');,
- {free(symstack);free(tagstack);free(mark);
- return -1;})
- paims=parc->aim;
- aimsidx=paims->sid-tcount;
- if (aimsidx>=0 && !(mark[aimsidx] & LMARK)){
- mark[aimsidx]|=LMARK;
- symstack[++stackp]=paims;
- tagstack[stackp]='D';
- }
- }
- break;
- }
- }
- }
- free(symstack);
- free(tagstack);
- free(mark);
- rrready=1;
- return 0;
- }
- genexpec(void){
- unsigned int i, j;
- expecini();
- EXP(0, 0)=ssym->sid;
- EXP(0, 1)=tntcount;
- for (i=1; i<=rulcount; i++){
- j=EXP(i, rightlenof(i))=leftof(i);
- for (j=0; j<rightlenof(i); j++){
- EXP(i, j)=rightof(i, j+1);
- }
- }
- return 0;
- }
- rolentry_t *rlsearch(int hashval, unsigned int rul, unsigned int rol){
- rolentry_t *currentry;
- unsigned int i,j;
- int flag;
- for (currentry=rolhashtbl[hashval];currentry!=NULL;currentry=currentry->nxt){
- if ((rightlenof(currentry->rul)-currentry->rol)==(rightlenof(rul)-rol)){
- flag=1;
- for (i=currentry->rol+1, j=rol+1; j<=rightlenof(rul); i++, j++){
- if (rightof(currentry->rul, i)!=rightof(rul, j)){
- flag=0;
- break;
- }
- }
- if (flag)
- break;
- }
- }
- return currentry;
- }
- int rlrelease(int hashval){
- rolentry_t *prentry, *qrentry;
- for (prentry=rolhashtbl[hashval];prentry!=NULL;prentry=qrentry){
- qrentry=prentry->nxt;
- free(prentry);
- }
- return 0;
- }
- unsigned int hashr(unsigned int i, unsigned int j){
- unsigned hashval, iter;
- rolentry_t *newrentry;
- for (hashval=0, iter=j; iter<rightlenof(i); iter++)
- hashval=rightof(i, iter+1)+31*hashval;
- hashval=hashval % MAXRENTRY;
- newrentry=rlsearch(hashval, i, j);
- if (newrentry==NULL){
- newrentry=(rolentry_t *)malloc(sizeof(rolentry_t));
- newrentry->rul=i;
- newrentry->rol=j;
- newrentry->nxt=rolhashtbl[hashval];
- rolhashtbl[hashval]=newrentry;
- }
- return (unsigned int)(newrentry);
- }
- genpostfix(){
- int i;
- unsigned int j, k;
- rolhashtbl=(rolentry_t **)malloc(sizeof(rolentry_t *)*MAXRENTRY);
- for (i=0; i<MAXRENTRY; i++)
- rolhashtbl[i]=NULL;
- PST(0,0)=0;
- for (j=1; j<=rulcount; j++){
- for (k=0; k<rightlenof(j); k++){
- PST(j,k)=hashr(j, k);
- }
- }
- for (i=0; i<MAXRENTRY; i++){
- rlrelease(i);
- }
- free(rolhashtbl);
- return 0;
- }