parser.g 9.6 KB

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