findworst.c 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165
  1. #ifndef NORCSID
  2. static char rcsidp3[] = "$Id$";
  3. #endif
  4. #include "parser.h"
  5. #define UPDATEWORST(backups) if(backups>mostbackups) mostbackups = backups;
  6. PRIVATE int leftmatch();
  7. PRIVATE int rightmatch();
  8. findworst(patt,repl)
  9. struct mnems patt,repl;
  10. {
  11. /*
  12. /* Find the pattern that requires the most backup of output queue.
  13. /* Let repl be r1 r2 ... rn. All these are already on the output queue.
  14. /* Possibilities in order of most backup first are:
  15. /* a) pattern of form: p1 .... pb r1 r2 .... rn pc ... pd
  16. /* i.e. <repl> completely in pattern.
  17. /* requires a backup of b+n instructions
  18. /* and a goto to state 0.
  19. /* b) pattern of form: p1 .... pb r1 r2 .... ri
  20. /* i.e. a prefix of <repl> ends a pattern.
  21. /* requires a backup of b+n instructions
  22. /* and a goto to state 0.
  23. /* c) pattern of form: ri ri+1 ... rn pc ... pd
  24. /* i.e. a suffix of <repl> starts a pattern.
  25. /* requires a backup of j-i+1 instructions and a goto to state 0.
  26. /* d) pattern of the form: ri ri+1 ... rj
  27. /* i.e. a substring of <repl> is a complete pattern
  28. /* requires a backup of j-i+1 instructions and a goto to state 0.
  29. */
  30. int n = repl.m_len;
  31. int diff = patt.m_len - repl.m_len;
  32. int first,i,j;
  33. int s;
  34. int mostbackups = 0;
  35. if(n==0) {
  36. fprintf(ofile,"\t\tOO_mkrepl(0,%d,%d);\n",diff,maxpattern-1);
  37. return;
  38. }
  39. for(s=1;s<=higheststate;s++) {
  40. /* only match complete patterns */
  41. if(actions[s]==(struct action *)NULL)
  42. continue;
  43. /* look for case a */
  44. if(first=rightmatch(patterns[s],repl,1,n)) {
  45. UPDATEWORST(first-1+n);
  46. }
  47. /* look for case b */
  48. for(i=n-1;i;i--) {
  49. if((first=rightmatch(patterns[s],repl,1,i)) &&
  50. (first+i-1==patterns[s].m_len)) {
  51. UPDATEWORST(first-1+n);
  52. }
  53. }
  54. /* look for case c */
  55. for(i=2;i<=n;i++) {
  56. if((first=leftmatch(patterns[s],repl,i,n)) &&
  57. (first==1)) {
  58. UPDATEWORST(n-i+1);
  59. }
  60. }
  61. /* look for case d */
  62. for(i=2;i<=n;i++) {
  63. for(j=n-1;j>i;j--) {
  64. if((first=leftmatch(patterns[s],repl,i,j)) &&
  65. (first==1)&&
  66. (j-i+1 == patterns[s].m_len)) {
  67. UPDATEWORST(n-i+1);
  68. }
  69. }
  70. }
  71. }
  72. fprintf(ofile,"\t\tOO_mkrepl(%d,%d,%d);\n",n,diff,mostbackups);
  73. }
  74. findfail(state,resout,rescpy,resgto)
  75. int state;
  76. int *resout, *rescpy, *resgto;
  77. {
  78. /*
  79. /* If pattern matching fails in 'state', how many outputs and how many
  80. /* push backs are requires. If pattern is of the form p1 p2 .... pn
  81. /* look for patterns of the form p2 p3 ... pn; then p3 p4 ... pn; etc.
  82. /* The first such match of the form pi pi+1 ... pn requires an output
  83. /* of p1 p2 ... pi-1 and a push back of pn pn-1 ... pi.
  84. */
  85. int s,i;
  86. struct state *p;
  87. int istrans;
  88. int n = patterns[state].m_len;
  89. for(i=2;i<=n;i++) {
  90. for(s=1;s<=higheststate;s++) {
  91. /* exclude those on transitions from this state */
  92. istrans = 0;
  93. for(p=states[state];p!=(struct state *)NULL;p=p->next)
  94. if(s==p->goto_state)
  95. istrans++;
  96. if(istrans)
  97. continue;
  98. if((leftmatch(patterns[s],patterns[state],i,n)==1)&&
  99. patterns[s].m_len==(n-i+1)) {
  100. *resout = i-1;
  101. *rescpy = n-i+1;
  102. *resgto = s;
  103. return;
  104. }
  105. }
  106. }
  107. *resout = n;
  108. *rescpy = 0;
  109. *resgto = 0;
  110. }
  111. PRIVATE int
  112. leftmatch(patt,repl,i,j)
  113. struct mnems patt,repl;
  114. int i,j;
  115. {
  116. /*
  117. /* Return the first complete match of the mnems <ri,ri+1,..,rj> of
  118. /* 'repl' in the mnems of 'patt'. Find the leftmost match.
  119. /* Return 0 if fails.
  120. */
  121. int lenrij = j-i+1;
  122. int lastpos = patt.m_len - lenrij + 1;
  123. int k,n;
  124. for(k=1;k<=lastpos;k++) {
  125. for(n=1;n<=lenrij;n++) {
  126. if(patt.m_elems[(k+n-1)-1]->op_code != repl.m_elems[(i+n-1)-1]->op_code)
  127. break;
  128. }
  129. if(n>lenrij) {
  130. return(k);
  131. }
  132. }
  133. return(0);
  134. }
  135. PRIVATE int
  136. rightmatch(patt,repl,i,j)
  137. struct mnems patt,repl;
  138. int i,j;
  139. {
  140. /*
  141. /* Return the first complete match of the mnems <ri,ri+1,..,rj> of
  142. /* 'repl' in the mnems of 'patt'. Find the rightmost match.
  143. /* Return 0 if fails.
  144. */
  145. int lenrij = j-i+1;
  146. int lastpos = patt.m_len - lenrij + 1;
  147. int k,n;
  148. for(k=lastpos;k>=1;k--) {
  149. for(n=1;n<=lenrij;n++) {
  150. if(patt.m_elems[(k+n-1)-1]->op_code != repl.m_elems[(i+n-1)-1]->op_code)
  151. break;
  152. }
  153. if(n>lenrij) {
  154. return(k);
  155. }
  156. }
  157. return(0);
  158. }