C   24

regexp c

Guest on 24th January 2023 02:05:43 PM


  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define MAX_ENDS 10
  6.  
  7. #define S_SPLIT 256
  8. #define S_MATCH 257
  9.  
  10. /* Operators, ordered by ascending precedence */
  11. typedef enum ops {
  12.         OP_START,       /* Sentinel, implicit */
  13.         OP_END,         /* Implicit */
  14.         OP_CHAR,
  15.         OP_RPAR,
  16.         OP_LPAR,
  17.         OP_OR,
  18.         OP_CONCAT,      /* Implicit */
  19.         OP_STAR,
  20. } optype_t;
  21.  
  22. struct state {
  23.         int c;
  24.         struct state *next;
  25.         struct state *next2;
  26. };
  27.  
  28. struct expr {
  29.         struct state *start;
  30.         struct state **ptrs[MAX_ENDS];
  31.         int nptrs;
  32. };
  33.  
  34. int tokval;
  35. struct expr exprstack[10];
  36. struct expr *exprp = exprstack;
  37. optype_t opstack[10];
  38. optype_t *opp = opstack;
  39. int need_concat;
  40.  
  41. static struct state *
  42. new_state(int c, struct state *next, struct state *next2)
  43. {
  44.         struct state *s;
  45.  
  46.         s = malloc(sizeof(struct state));
  47.         s->c = c;
  48.         s->next = next;
  49.         s->next2 = next2;
  50.  
  51.         return (s);
  52. }
  53.  
  54. void
  55. patch(struct expr *e, struct state *s)
  56. {
  57.         int i;
  58.  
  59.         for (i = 0; i < e->nptrs; i++)
  60.                 *e->ptrs[i] = s;
  61. }
  62.  
  63. optype_t
  64. next_token(char **s)
  65. {
  66.         char c;
  67.  
  68.         c = *(*s)++;
  69.  
  70.         switch (c) {
  71.         case '\0':
  72.                 return (OP_END);
  73.         case '(':
  74.                 return (OP_LPAR);      
  75.         case ')':
  76.                 return (OP_RPAR);
  77.         case '*':
  78.                 return (OP_STAR);
  79.         case '|':
  80.                 return (OP_OR);
  81.         case '\\':
  82.                 tokval = *(*s)++;
  83.                 return (OP_CHAR);
  84.         default:
  85.                 tokval = c;
  86.                 return (OP_CHAR);
  87.         }
  88. }
  89.  
  90. void
  91. push_expr(struct state *start, struct state **ptr)
  92. {
  93.         struct expr *e;
  94.  
  95.         e = exprp++;
  96.         e->start = start;
  97.         *e->ptrs = ptr;
  98.         e->nptrs = 1;
  99. }
  100.  
  101. void
  102. push_expr_arr(struct state *start, struct state **ptrs[], int n)
  103. {
  104.         struct expr *e;
  105.  
  106.         e = exprp++;
  107.         e->start = start;
  108.         e->nptrs = n;
  109.         memcpy(e->ptrs, ptrs, n * sizeof(struct state *));
  110. }
  111.  
  112. struct expr *
  113. pop_expr()
  114. {
  115.         return (--exprp);
  116. }
  117.  
  118. void
  119. push_op(optype_t op)
  120. {
  121.         *opp++ = op;
  122. }
  123.  
  124. optype_t
  125. pop_op()
  126. {
  127.         *opp = OP_START;
  128.         return (*--opp);
  129. }
  130.  
  131. void
  132. evalopsuntil(optype_t op)
  133. {
  134.         struct state *new;
  135.         struct expr *e1, *e2;
  136.         optype_t cur;
  137.         int i;
  138.  
  139.         while (*(opp-1) >= op) {
  140.                 cur = pop_op();
  141.                 if (cur == OP_STAR) {
  142.                         e1 = pop_expr();
  143.                         new = new_state(S_SPLIT, e1->start, NULL);
  144.                         patch(e1, new);
  145.                         push_expr(new, &new->next2);
  146.                 } else if (cur == OP_CONCAT) {
  147.                         e2 = pop_expr();
  148.                         e1 = pop_expr();
  149.                         patch(e1, e2->start);
  150.                         push_expr_arr(e1->start, e2->ptrs, e2->nptrs);
  151.                 } else if (cur == OP_OR) {
  152.                         e2 = pop_expr();
  153.                         e1 = pop_expr();
  154.                         new = new_state(S_SPLIT, e1->start, e2->start);
  155.                         /* XXX overflow */
  156.                         for (i = 0; i < e2->nptrs; i++)
  157.                                 e1->ptrs[e1->nptrs + i] = e2->ptrs[i];
  158.                         push_expr_arr(new, e1->ptrs, e1->nptrs + e2->nptrs);
  159.                 } else if (cur == OP_START)
  160.                         break;
  161.         }
  162. }
  163.  
  164. void
  165. operator(optype_t op)
  166. {
  167.         if (*(opp - 1) >= op) {
  168.                 evalopsuntil(op);
  169.                 if (op != OP_RPAR)
  170.                         push_op(op);
  171.         } else
  172.                 push_op(op);
  173.  
  174.         if (op == OP_RPAR && need_concat)
  175.                 operator(OP_CONCAT);
  176.  
  177.         if (op == OP_STAR || op == OP_RPAR)
  178.                 need_concat = 1;
  179.         else
  180.                 need_concat = 0;
  181. }
  182.  
  183. struct state *
  184. compile(char *s)
  185. {
  186.         struct state *new, *start;
  187.         struct expr *e;
  188.         int op;
  189.  
  190.         need_concat = 0;
  191.         start = NULL;
  192.         opp = opstack;
  193.         exprp = exprstack;
  194.         push_op(OP_START);
  195.  
  196.         while (1) {
  197.                 op = next_token(&s);
  198.                 if (op == OP_END)
  199.                         break;
  200.                 if (op == OP_CHAR) {
  201.                         if (need_concat)
  202.                                 operator(OP_CONCAT);
  203.  
  204.                         new = new_state(tokval, NULL, NULL);
  205.                         push_expr(new, &new->next);
  206.  
  207.                         need_concat = 1;
  208.                 } else
  209.                         operator(op);
  210.         }
  211.  
  212.         evalopsuntil(OP_START);
  213.         e = pop_expr();
  214.         new = new_state(S_MATCH, NULL, NULL);
  215.         patch(e, new);
  216.  
  217.         return (e->start);
  218. }
  219.  
  220. int
  221. main(void)
  222. {
  223.         compile("a(b|c)*d");
  224.         compile("abcd");
  225.         compile("a(b|c)d");
  226.         compile("a(bb)*a");
  227.         compile("a(bc)d");
  228.         compile("ab*cd");
  229.         compile("a(bc)*d");
  230.         compile("a(b|c)d");
  231.         compile("a(bc|de)fg");
  232.  
  233.         return (0);
  234. }

Raw Paste


Login or Register to edit or fork this paste. It's free.

">