modules/src/em_opt/parser.g

   1 /* Parser to read optimization patterns of the form:
   2                 op1 op2 ... test : action
   3         or
   4                 op1 op2 ... : action
   5    and build a program to recognize then */
   6
   7 %token  SFIT, UFIT, ROTATE, PSIZE, WSIZE, DWSIZE,  DEFINED, UNDEFINED, SAMESIGN;
   8 %token  SAMEEXT, SAMENAM, OFFSET, LOGAND, LOGOR, BITAND, BITOR, XOR;
   9 %token  MINUS, PLUS, TIMES, DIV, MOD, EQ, NE, LT, LE, GT, GE, NOT, COMP;
  10 %token  LSHIFT, RSHIFT, COMMA, OPCODE, INT, UPLUS, UMINUS, PATARG;
  11
  12 %start  parser, input;
  13
  14 {
  15 #ifndef NORCSID
  16 static char rcsidp1[] = "$Id: parser.g,v 1.7 1994/06/24 11:14:30 ceriel Exp $";
  17 #endif
  18
  19 #include "parser.h"
  20
  21 #define MAXPRIO 11
  22
  23 struct state    *states[MAXSTATES];
  24 struct action   *actions[MAXSTATES];
  25 struct mnems    patterns[MAXSTATES];
  26 int             numpatterns = 0;        /* Number of patterns */
  27 int             higheststate = 0;       /* Highest state yet allocated */
  28 struct idf      *ops;                   /* Chained list of all ops */
  29 int             maxpattern = 0;
  30 int             maxreplacement = 0;
  31 int             nerrors = 0;
  32
  33 static int      lencurrpatt;
  34 static int      lenthisrepl;
  35 static int      currentstate;           /* Current state of dfa */
  36 }
  37
  38 input   : /* empty */
  39         | optimization input
  40         ;
  41
  42 optimization
  43                         {
  44                         int startline;
  45                         struct exp_node *restrictions;
  46                         struct exp_node *finaltest;
  47                         struct mnem_list *repllist;
  48                         }
  49         :
  50                         {
  51                         startline=linenum; currentstate=0;
  52                         lencurrpatt=0; lenthisrepl=0;
  53                         }
  54         patterns(&restrictions)
  55                         { finaltest = (struct exp_node *)NULL; }
  56         [
  57                 '?'
  58                 exp(1,&finaltest)
  59         ]?
  60         ':'
  61         action(&repllist)
  62                         {
  63                         numpatterns++;
  64                         addaction(startline,currentstate,restrictions,
  65                                 finaltest,repllist);
  66                         }
  67         '\n'
  68         ;
  69
  70 patterns(struct exp_node **tests;)
  71                         {
  72                         struct mnem_list *list;
  73                         struct exp_node *onetest;
  74                         }
  75         :
  76                         {
  77                         list = (struct mnem_list *)NULL;
  78                         *tests = (struct exp_node *)NULL;
  79                         }
  80         [
  81         OPCODE
  82                         {
  83                         if(++lencurrpatt>maxpattern)
  84                                 maxpattern=lencurrpatt;
  85                         list = addelem(list,opval, (struct exp_node *)NULL);
  86                         opval->id_used=1;
  87                         if(lencurrpatt==1)
  88                                 opval->id_startpatt=1;
  89                         currentstate=dotransition(currentstate,opval,list,lencurrpatt);
  90                         }
  91         [
  92                 restriction(opval->id_argfmt,&onetest)
  93                         {
  94                         *tests = combinetests(*tests,onetest);
  95                         }
  96         ]?
  97         ]+
  98         ;
  99
 100 restriction(int argtype; struct exp_node **test;)
 101                         {
 102                         struct exp_node *test1,*test2;
 103                         int relop;
 104                         int offsetop;
 105                         }
 106         :
 107         [ %if(argtype==CSTOPT)
 108                 [ optrelop(&relop) exp(1,test)
 109                         {
 110                         *test = mknode(relop,mkleaf(PATARG,lencurrpatt),*test);
 111                         }
 112                 | DEFINED
 113                         {
 114                         *test = mkleaf(DEFINED,lencurrpatt);
 115                         }
 116                 | UNDEFINED
 117                         {
 118                         *test = mkleaf(UNDEFINED,lencurrpatt);
 119                         }
 120                 ]
 121         | %if(argtype==EXT)
 122                 patarg(&test1)
 123                         {
 124                         *test=mknode(SAMEEXT,
 125                                 mkleaf(PATARG,lencurrpatt),
 126                                 test1);
 127                         }
 128                 [
 129                         [ PLUS
 130                                 { offsetop = PLUS; }
 131                         | MINUS
 132                                 { offsetop = MINUS; }
 133                         ]
 134                         exp(1,&test2)
 135                                 {
 136                                 test2 = mknode(offsetop, test1, test2);
 137                                 test2 = mknode(EQ, mkleaf(PATARG,lencurrpatt), test2);
 138                                 *test = combinetests(
 139                                         mknode(SAMENAM,
 140                                                 mkleaf(PATARG,lencurrpatt),
 141                                                 test1),
 142                                         test2);
 143                                 }
 144                 ]?
 145         |
 146                 optrelop(&relop) exp(1,test)
 147                         {
 148                         *test = mknode(relop,mkleaf(PATARG,lencurrpatt),*test);
 149                         }
 150         ]
 151         ;
 152
 153 optrelop(int *op;)
 154         :
 155                 {*op = EQ;}
 156         [ EQ    {*op = EQ;}
 157         | NE    {*op = NE;}
 158         | LT    {*op = LT;}
 159         | LE    {*op = LE;}
 160         | GT    {*op = GT;}
 161         | GE    {*op = GE;}
 162         ]?
 163         ;
 164 action(struct mnem_list **list;)
 165                         {
 166                         struct exp_node *test, *test2;
 167                         struct idf *keepopval;
 168                         int offsetop;
 169                         }
 170         :
 171                         { *list = (struct mnem_list *)NULL; }
 172         [
 173         OPCODE
 174                         {
 175                         if(++lenthisrepl>maxreplacement)
 176                                 maxreplacement = lenthisrepl;
 177                         test= (struct exp_node *)NULL;
 178                         keepopval = opval;
 179                         }
 180                 [ %if(keepopval->id_argfmt==EXT)
 181                 patarg(&test)
 182                                 {
 183                                 test2 = test;
 184                                 }
 185                         [
 186                                 [ PLUS
 187                                         { offsetop = PLUS; }
 188                                 | MINUS
 189                                         { offsetop = MINUS; }
 190                                 ]
 191                                 exp(1,&test2)
 192                                         {
 193                                         test2 = mknode(offsetop,test,test2);
 194                                         }
 195
 196                         ]?
 197                                 {
 198                                 test = mknode(COMMA,test,test2);
 199                                 }
 200                 | exp(1,&test)
 201                 ]?
 202                                 {
 203                                 *list = addelem(*list,keepopval,test);
 204                                 }
 205         ]*
 206         ;
 207
 208 exp(int level; struct exp_node **result;)
 209                         { struct exp_node *res1, *res2;
 210                           int operator; }
 211                 :
 212                 %if(level <= MAXPRIO)
 213                 exp(MAXPRIO+1,&res1)
 214                         [ %while (priority(LLsymb) >= level)
 215                           binop
 216                                 {
 217                                 operator=LLsymb;
 218                                 }
 219                           exp(priority(operator)+1,&res2)
 220                                 {
 221                                 res1 = mknode(operator,res1,res2);
 222                                 }
 223                         ]*
 224                                 {
 225                                 *result = res1;
 226                                 }
 227                 | '(' exp(1,result) ')'
 228                 | unaryop(&operator) exp(priority(operator)+1,&res1)
 229                         {
 230                         *result = mknode(operator,res1,(struct exp_node *)NULL);
 231                         }
 232                 | SAMESIGN '(' exp(1,&res1) COMMA exp(1,&res2) ')'
 233                         {
 234                         *result = mknode(SAMESIGN,res1,res2);
 235                         }
 236                 | SFIT '(' exp(1,&res1) COMMA exp(1,&res2) ')'
 237                         {
 238                         *result = mknode(SFIT,res1,res2);
 239                         }
 240                 | UFIT '(' exp(1,&res1) COMMA exp(1,&res2) ')'
 241                         {
 242                         *result = mknode(UFIT,res1,res2);
 243                         }
 244                 | ROTATE '(' exp(1,&res1) COMMA exp(1,&res2) ')'
 245                         {
 246                         *result = mknode(ROTATE,res1,res2);
 247                         }
 248                 | SAMEEXT '(' patarg(&res1) COMMA patarg(&res2) ')'
 249                         {
 250                         *result = mknode(SAMEEXT,res1,res2);
 251                         }
 252                 | SAMENAM '(' patarg(&res1) COMMA patarg(&res2) ')'
 253                         {
 254                         *result = mknode(SAMENAM,res1,res2);
 255                         }
 256                 | OFFSET '(' patarg(&res1) ')'
 257                         {
 258                         *result = res1;
 259                         }
 260                 | patarg(result)
 261                 | PSIZE
 262                         {
 263                         *result = mkleaf(PSIZE,0);
 264                         }
 265                 | WSIZE
 266                         {
 267                         *result = mkleaf(WSIZE,0);
 268                         }
 269                 | DWSIZE
 270                         {
 271                         *result = mkleaf(DWSIZE,0);
 272                         }
 273                 | INT
 274                         {
 275                         *result = mkleaf(INT,lastintval);
 276                         }
 277                 ;
 278
 279 patarg(struct exp_node **result;)
 280                 { int intval; }
 281         :  PATARG argno(&intval)
 282                 {
 283                 *result = mkleaf(PATARG,intval);
 284                 }
 285         ;
 286
 287 argno(int *val;)
 288         : INT
 289                 {
 290                 *val = lastintval;
 291                 if(lastintval<0 || (lastintval>lencurrpatt)) {
 292                         fprintf(stderr ,"Illegal $%d on line %d\n",
 293                                         lastintval,linenum);
 294                         nerrors++;
 295                 }
 296                 }
 297         ;
 298
 299 unaryop(int *operator;)
 300         : PLUS  { *operator = UPLUS; }
 301         | MINUS { *operator = UMINUS; }
 302         | NOT   { *operator = NOT; }
 303         | COMP  { *operator = COMP; }
 304         ;
 305
 306 binop   : LOGAND
 307         | LOGOR
 308         | BITAND
 309         | BITOR
 310         | XOR
 311         | MINUS
 312         | PLUS
 313         | TIMES
 314         | DIV
 315         | MOD
 316         | EQ
 317         | NE
 318         | LT
 319         | LE
 320         | GT
 321         | GE
 322         | LSHIFT
 323         | RSHIFT
 324         ;
 325
 326 %lexical yylex;
 327
 328 {
 329 addaction(startline, state, restrictions, finaltest, repllist)
 330         int startline;
 331         int state;
 332         struct exp_node *restrictions, *finaltest;
 333         struct mnem_list *repllist;
 334 {
 335         struct action *p, *q;
 336         p=(struct action *)Malloc(sizeof(struct action));
 337         p->next = (struct action *)NULL;
 338         p->linenum = startline;
 339         p->test = combinetests(restrictions,finaltest);
 340         p->replacement.m_len = lenthisrepl;
 341         p->replacement.m_elems = constructlist(repllist,lenthisrepl);
 342         /* chain new action to END of action chain */
 343         if((q = actions[state])==(struct action *)NULL)
 344                 actions[state] = p;
 345         else {
 346                 while(q->next != (struct action *)NULL)
 347                         q = q->next;
 348                 q->next = p;
 349         }
 350 }
 351
 352 struct mnem_elem **
 353 constructlist(list,len)
 354         struct mnem_list *list;
 355         int len;
 356 {
 357         struct mnem_elem **p;
 358         p = (struct mnem_elem **)
 359                 Malloc((unsigned)(len*sizeof(struct mnem_elem *)));
 360         while(len--) {
 361                 p[len] = list->elem;
 362                 list = list->next;
 363         }
 364         return(p);
 365 }
 366
 367 struct mnem_list *
 368 addelem(oldlist, mnem, test)
 369         struct mnem_list *oldlist;
 370         struct idf *mnem;
 371         struct exp_node *test;
 372 {
 373         struct mnem_list *reslist;
 374         struct mnem_elem *element;
 375         element = (struct mnem_elem *)Malloc(sizeof(struct mnem_elem));
 376         element->op_code = mnem;
 377         element->arg = test;
 378         reslist = (struct mnem_list *)Malloc(sizeof(struct mnem_list));
 379         reslist->elem = element;
 380         reslist->next = oldlist;
 381         return(reslist);
 382 }
 383
 384 int
 385 dotransition(state, mnem, mnem_list, lenlist)
 386         int state;
 387         struct idf *mnem;
 388         struct mnem_list *mnem_list;
 389         int lenlist;
 390 {
 391         struct state *p;
 392         /* look for existing transition */
 393         for(p=states[state];
 394             (p!=((struct state *)NULL)) && ((p->op)!=mnem);
 395             p = p->next
 396            );
 397         if(p==(struct state *)NULL) {
 398                 /* none found so add a new state to dfa */
 399                 p=(struct state *)Malloc(sizeof(struct state));
 400                 p->op=mnem;
 401                 if(++higheststate>MAXSTATES) {
 402                         fprintf(stderr,"Parser: More than %s states\n",MAXSTATES);
 403                         sys_stop(S_EXIT);
 404                 }
 405                 p->goto_state= higheststate;
 406                 p->next=states[currentstate];
 407                 states[currentstate]=p;
 408                 states[higheststate] = (struct state *)NULL;
 409                 actions[higheststate] = (struct action *)NULL;
 410                 patterns[higheststate].m_len = lencurrpatt;
 411                 patterns[higheststate].m_elems =
 412                         constructlist(mnem_list,lenlist);
 413                 return(higheststate);
 414         }
 415         else return(p->goto_state); /* already exists */
 416 }
 417
 418 struct exp_node *
 419 combinetests(test1, test2)
 420         struct exp_node *test1, *test2;
 421 {
 422         if(test1==(struct exp_node *)NULL)
 423                 return(test2);
 424         else if(test2==(struct exp_node *)NULL)
 425                 return(test1);
 426         else
 427                 return(mknode(LOGAND,test1,test2));
 428 }
 429
 430 priority(op) int op; {
 431         switch (op) {
 432         case LOGOR:     return(1);
 433         case LOGAND:    return(2);
 434         case BITOR:     return(3);
 435         case XOR:       return(4);
 436         case BITAND:    return(5);
 437         case EQ:
 438         case NE:        return(6);
 439         case LT:
 440         case LE:
 441         case GT:
 442         case GE:        return(7);
 443         case LSHIFT:
 444         case RSHIFT:    return(8);
 445         case MINUS:
 446         case PLUS:      return(9);
 447         case TIMES:
 448         case DIV:
 449         case MOD:       return(10);
 450         case NOT:
 451         case COMP:
 452         case UPLUS:
 453         case UMINUS:    return(11);
 454         }
 455         fprintf(stderr,"Internal error: priority: - unrecognized operator\n");
 456         return(0);
 457 }
 458
 459 struct exp_node *
 460 mknode(op,left,right)
 461         int op;
 462         struct exp_node *left,*right;
 463 {
 464         struct exp_node *p;
 465         p = (struct exp_node *)Malloc(sizeof(struct exp_node));
 466         p->node_type = op;
 467         p->exp_left = left;
 468         p->exp_right = right;
 469         return(p);
 470 }
 471
 472 struct exp_node *
 473 mkleaf(op,val)
 474         int op,val;
 475 {
 476         struct exp_node *p;
 477         p = (struct exp_node *)Malloc(sizeof(struct exp_node));
 478         p->node_type = op;
 479         p->leaf_val = val;
 480         return(p);
 481 }
 482
 483 LLmessage(insertedtok)
 484         int insertedtok;
 485 {
 486         nerrors++;
 487         fprintf(stderr,"parser: syntax error on line %d: ",linenum);
 488         if(insertedtok) {
 489                 fprintf(stderr,"Inserted token %d\n",insertedtok);
 490                 back_token();
 491         }
 492         else fprintf(stderr,"Deleted token %d\n",LLsymb);
 493 }
 494
 495 main() {
 496         initlex();
 497         states[0] = (struct state *)NULL;
 498         patterns[0].m_len = 0;
 499         parser();
 500         if(nerrors) {
 501                 fprintf(stderr,"%d errors detected\n",nerrors);
 502                 sys_stop(S_EXIT);
 503         }
 504         outputnopt();
 505         sys_stop(S_END);
 506 }
 507 }