home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / glimpse-2.1 / agrep / parse.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-16  |  10.5 KB  |  445 lines
  1. /* Copyright (c) 1994 Sun Wu, Udi Manber, Burra Gopal.  All Rights Reserved. */
  2. /* the functions in this file parse a string that represents
  3.    a regular expression, and return a pointer to a syntax
  4.    tree for that regular expression.                */
  5.  
  6. #include <stdio.h>
  7. #include "re.h"
  8.  
  9. #define FALSE    0
  10. #define TRUE    1
  11.  
  12. #define NextChar(s)     *(*s)++
  13. #define Unexpected(s, c) (**s == NUL || **s == c)
  14. #define Invalid_range(x, y)    (x == NUL || x == '-' || x == ']' || x < y)
  15.  
  16. extern Stack Push();
  17. extern Re_node Pop();
  18. extern Re_node Top();
  19. extern int Size();
  20. extern Pset pset_union();
  21. extern Pset create_pos();
  22. extern void free_re();
  23.  
  24. int final_pos, pos_cnt = 0;
  25.  
  26. /* retract_token() moves the string pointer back, effectively "unseeing"
  27.    the last character seen.  It is used only to retract a right paren --
  28.    the idea is that the incarnation of parse_re() that saw the corresponding
  29.    left paren is supposed to take care of matching the right paren.  This
  30.    is necessary to prevent recursive calls from mistakenly eating up someone
  31.    else's right parens.                            */
  32.  
  33. #define retract_token(s)    --(*s)
  34.  
  35. /* mk_leaf() creates a leaf node that is (usually) a literal node.    */
  36.  
  37. Re_node mk_leaf(opval, type, ch, cset)
  38. short opval, type;
  39. char ch;
  40. Ch_Set cset;
  41. {
  42.     Re_node node; 
  43.     Re_Lit l;
  44.  
  45.     new_node(Re_Lit, l, l);
  46.     new_node(Re_node, node, node);
  47.     if (l == NULL || node == NULL) {
  48.         if (l != NULL) free(l);
  49.         if (node != NULL) free(node);
  50.         return NULL;
  51.     }
  52.     lit_type(l) = type;
  53.     lit_pos(l)  = pos_cnt++;
  54.     if (type == C_SET) lit_cset(l) = cset;
  55.     else lit_char(l) = ch;            /* type == C_LIT */
  56.     Op(node) = opval;
  57.     Lit(node) = l;
  58.     Nullable(node) = FALSE;
  59.     Firstpos(node) = create_pos(lit_pos(l));
  60.     Lastpos(node) = Firstpos(node);
  61.     return node;
  62. }
  63.  
  64. /* parse_cset() takes a pointer to a pointer to a string and parses
  65.    a prefix of it denoting a character set literal.  It returns a pointer
  66.    to a Re_node node, NULL if there is an error.            */
  67.  
  68. Re_node parse_cset(s)
  69. char **s;
  70. {
  71.     Ch_Set cs_ptr, curr_ptr, prev_ptr;
  72.     char ch;
  73.     Ch_Range range = NULL;
  74.  
  75.     if (Unexpected(s, ']')) return NULL;
  76.     new_node(Ch_Set, curr_ptr, curr_ptr); 
  77.     cs_ptr = curr_ptr;
  78.     while (!Unexpected(s, ']')) {
  79.         new_node(Ch_Range, range, range);
  80.         curr_ptr->elt = range;
  81.         ch = NextChar(s);
  82.         if (ch == '-') {
  83.             free(range);
  84.             free(curr_ptr);
  85.             return NULL;    /* invalid range */
  86.         }
  87.         range->low_bd = ch;
  88.         if (**s == NUL) {
  89.             free(range);
  90.             free(curr_ptr);
  91.             return NULL;
  92.         }
  93.         else if (**s == '-') {        /* character range */
  94.             (*s)++;
  95.             if (Invalid_range(**s, ch)) {
  96.                 free(range);
  97.                 free(curr_ptr);
  98.                 return NULL;
  99.             }
  100.             else range->hi_bd = NextChar(s);
  101.         }
  102.         else range->hi_bd = ch;
  103.         prev_ptr = curr_ptr;
  104.         new_node(Ch_Set, curr_ptr, curr_ptr);
  105.         prev_ptr->rest = curr_ptr;
  106.     };
  107.     if (**s == ']') {
  108.         prev_ptr->rest = NULL;
  109.         return mk_leaf(LITERAL, C_SET, NUL, cs_ptr);
  110.     }
  111.     else {
  112.         if (range != NULL) free(range);
  113.         free(curr_ptr);
  114.         return NULL;
  115.     }
  116. } /* parse_cset */
  117.  
  118.  
  119. /* parse_wildcard() "parses" a wildcard -- a wildcard is treated as a
  120.    character range whose values span all ASCII values.  parse_wildcard()
  121.    creates a node representing such a range.                */
  122.  
  123. Re_node parse_wildcard()
  124. {
  125.     Ch_Set s; 
  126.     Ch_Range r;
  127.  
  128.     new_node(Ch_Range, r, r);
  129.     r->low_bd = ASCII_MIN;    /* smallest ASCII value */
  130.     r->hi_bd  = ASCII_MAX;    /* greatest ASCII value */
  131.     new_node(Ch_Set, s, s);
  132.     s->elt = r;
  133.     s->rest = NULL;
  134.     return mk_leaf(LITERAL, C_SET, NUL, s);
  135. }
  136.  
  137. /* parse_chlit() parses a character literal.  It is assumed that the
  138.    character in question does not have any special meaning.  It returns
  139.    a pointer to a node for that literal.                */
  140.  
  141. Re_node parse_chlit(ch)
  142. char ch;
  143. {
  144.     if (ch == NUL) return NULL;
  145.     else return mk_leaf(LITERAL, C_LIT, ch, NULL);
  146. }
  147.  
  148. /* routine to free the malloced token */
  149. void free_tok(next_token)
  150. Tok_node next_token;
  151. {
  152.     if (next_token == NULL) return;
  153.     switch (tok_type(next_token)) {
  154.     case LITERAL:
  155.         free_re(tok_val(next_token));
  156.     case EOS:
  157.     case RPAREN:
  158.     case LPAREN:
  159.     case OPSTAR:
  160.     case OPALT:
  161.     case OPOPT:
  162.     default:
  163.         free(next_token);
  164.         break;
  165.     }
  166. }
  167.  
  168. /* get_token() returns the next token -- this may be a character
  169.    literal, a character set, an escaped character, a punctuation (i.e.
  170.    parenthesis), or an operator.  It traverses the character string
  171.    representing the RE, given by a pointer s; leaves s positioned
  172.    immediately after the unit it parsed, and returns a pointer to
  173.    a token node for that unit.  */
  174.  
  175. Tok_node get_token(s)
  176. char **s;
  177. {
  178.     Tok_node rn = NULL;
  179.  
  180.     if (s == NULL || *s == NULL) return NULL;    /* error */
  181.     new_node(Tok_node, rn, rn);
  182.     if (**s == NUL) tok_type(rn) = EOS; /* end of string */
  183.     else {
  184.         switch (**s) {
  185.         case '.':            /* wildcard */
  186.             tok_type(rn) = LITERAL;
  187.             tok_val(rn) =  parse_wildcard();
  188.             if (tok_val(rn) == NULL) {
  189.                 free_tok(rn);
  190.                 return NULL;
  191.             }
  192.             break;
  193.         case '[':            /* character set literal */
  194.             (*s)++;
  195.             tok_type(rn) = LITERAL;
  196.             tok_val(rn) = parse_cset(s);
  197.             if (tok_val(rn) == NULL) {
  198.                 free_tok(rn);
  199.                 return NULL;
  200.             }
  201.             break;
  202.         case '(':
  203.             tok_type(rn) = LPAREN;
  204.             break;
  205.         case ')' : 
  206.             tok_type(rn) = RPAREN;
  207.             break;
  208.         case '*' :
  209.             tok_type(rn) = OPSTAR;
  210.             break;
  211.         case '|' :
  212.             tok_type(rn) = OPALT;
  213.             break;
  214.         case '?' : 
  215.             tok_type(rn) = OPOPT;
  216.             break;
  217.         case '\\':            /* escaped character */
  218.             (*s)++;
  219.         default :            /* must be ordinary character */
  220.             tok_type(rn) = LITERAL;
  221.             tok_val(rn) = parse_chlit(**s);
  222.             if (tok_val(rn) == NULL) {
  223.                 free_tok(rn);
  224.                 return NULL;
  225.             }
  226.             break;
  227.         } /* switch (**s) */
  228.         (*s)++;
  229.     } /* else */
  230.     return rn;
  231. }
  232.  
  233. /* cat2() takes a stack of RE-nodes and, if the stack contains
  234.    more than one node, returns the stack obtained by condensing
  235.    the top two nodes of the stack into a single CAT-node.  If there
  236.    is only one node on the stack,  nothing is done.            */
  237.  
  238. Stack cat2(stk)
  239. Stack *stk;
  240. {
  241.     Re_node r;
  242.  
  243.     if (stk == NULL) return NULL;
  244.     if (*stk == NULL || (*stk)->next == NULL) return *stk;
  245.     new_node(Re_node, r, r);
  246.     if (r == NULL) return NULL;        /* can't allocate memory */
  247.     Op(r) = OPCAT;
  248.     Rchild(r) = Pop(stk);
  249.     Lchild(r) = Pop(stk);
  250.     if (Push(stk, r) == NULL) {
  251.         free_re(Rchild(r));
  252.         free_re(Lchild(r));
  253.         free(r);
  254.         return NULL;
  255.     }
  256.     Nullable(r) = Nullable(Lchild(r)) && Nullable(Rchild(r));
  257.     if (Nullable(Lchild(r)))
  258.         Firstpos(r) = pset_union(Firstpos(Lchild(r)), Firstpos(Rchild(r)));
  259.     else Firstpos(r) = Firstpos(Lchild(r));
  260.     if (Nullable(Rchild(r)))
  261.         Lastpos(r) = pset_union(Lastpos(Lchild(r)), Lastpos(Rchild(r)));
  262.     else Lastpos(r) = Lastpos(Rchild(r));
  263.     return *stk;
  264. }
  265.  
  266. /* wrap() takes a stack and an operator, takes the top element of the
  267.    stack and "wraps" that operator around it, then puts this back on the
  268.    stack and returns the resulting stack.                */
  269.  
  270. Stack wrap(s, opv)
  271. Stack *s;
  272. short opv;
  273. {
  274.     Re_node r;
  275.  
  276.     if (s == NULL || *s == NULL) return NULL;
  277.     new_node(Re_node, r, r);
  278.     if (r == NULL) return NULL;
  279.     Op(r) = opv;
  280.     Child(r) = Pop(s);
  281.     if (Push(s, r) == NULL) {
  282.         free_re(Child(r));
  283.         free(r);
  284.         return NULL;
  285.     }
  286.     Nullable(r) = TRUE;
  287.     Firstpos(r) = Firstpos(Child(r));
  288.     Lastpos(r)  = Lastpos(Child(r));
  289.     return *s;
  290. }
  291.  
  292. /* mk_alt() takes a stack and a regular expression, creates an ALT-node
  293.    from the top of the stack and the given RE, and replaces the top-of-stack
  294.    by the resulting ALT-node.                        */   
  295.  
  296. Stack mk_alt(s, r)
  297. Stack *s;
  298. Re_node r;
  299. {
  300.     Re_node node;
  301.  
  302.     if (s == NULL || *s == NULL || r == NULL) return NULL;
  303.     new_node(Re_node, node, node);
  304.     if (node == NULL) return NULL;
  305.     Op(node) = OPALT;
  306.     Lchild(node) = Pop(s);
  307.     Rchild(node) = r;
  308.     if (Push(s, node) == NULL) return NULL;
  309.     Nullable(node) = Nullable(Lchild(node)) || Nullable(Rchild(node));
  310.     Firstpos(node) = pset_union(Firstpos(Lchild(node)), Firstpos(Rchild(node)));
  311.     Lastpos(node) = pset_union(Lastpos(Lchild(node)), Lastpos(Rchild(node)));
  312.     return *s;
  313. }
  314.  
  315. /* parse_re() takes a pointer to a string and traverses that string,
  316.    returning a pointer to a syntax tree for the regular expression
  317.    represented by that string, NULL if there is an error.        */
  318.  
  319. Re_node parse_re(s, end)
  320. char **s;
  321. short end;
  322. {
  323.     Stack stk = NULL, ret = NULL, top, temp;
  324.     Tok_node next_token, t1;
  325.     Re_node re = NULL, val;
  326.  
  327.     if (s == NULL || *s == NULL) return NULL;
  328.     while (TRUE) {
  329.         ret = NULL;
  330.         if ((next_token = get_token(s)) == NULL) return NULL;
  331.         switch (tok_type(next_token)) {
  332.         case RPAREN:
  333.             retract_token(s);
  334.         case EOS:
  335.             if (end == tok_type(next_token)) {
  336.                 free_tok(next_token);
  337.                 top = cat2(&stk);
  338.                 val = Top(top);
  339.                 free(top);
  340.                 return val;
  341.             }
  342.             else {
  343.                 free_tok(next_token);
  344.                 return NULL;
  345.             }
  346.         case LPAREN:
  347.             free_tok(next_token);
  348.             re = parse_re(s, RPAREN);
  349.             if ((ret = Push(&stk, re)) == NULL) return NULL;
  350.             if ((t1 = get_token(s)) == NULL) {
  351.                 free(ret);
  352.                 return NULL;
  353.             }
  354.             if ((tok_type(t1) != RPAREN) || (re == NULL)) {
  355.                 free(ret);
  356.                 free_tok(t1);
  357.                 return NULL;
  358.             }
  359.             free_tok(t1);
  360.             if (Size(stk) > 2) {
  361.                 temp = stk->next;
  362.                 stk->next = cat2(&temp);    /* condense CAT nodes */
  363.                 if (stk->next == NULL) {
  364.                     free(ret);
  365.                     return NULL;
  366.                 }
  367.                 else stk->size = stk->next->size + 1;
  368.             }
  369.             break;
  370.         case OPSTAR:
  371.             if ((ret = wrap(&stk, OPSTAR)) == NULL) {
  372.                 free_tok(next_token);
  373.                 return NULL;
  374.             }
  375.             break;
  376.         case OPOPT:
  377.             if ((ret = wrap(&stk, OPOPT)) == NULL) {
  378.                 free_tok(next_token);
  379.                 return NULL;
  380.             }
  381.             break;
  382.         case OPALT:
  383.             if ((ret = cat2(&stk)) == NULL) {
  384.                 free_tok(next_token);
  385.                 return NULL;
  386.             }
  387.             re = parse_re(s, end);
  388.             if (re == NULL) {
  389.                 free(ret);
  390.                 free_tok(next_token);
  391.                 return NULL;
  392.             }
  393.             if (mk_alt(&stk, re) == NULL) {
  394.                 free(ret);
  395.                 free_tok(next_token);
  396.                 return NULL;
  397.             }
  398.             break;
  399.         case LITERAL:
  400.             if ((ret = Push(&stk, tok_val(next_token))) == NULL) {
  401.                 free_tok(next_token);
  402.                 return NULL;
  403.             }
  404.             free(next_token);
  405.             if (Size(stk) > 2) {
  406.                 temp = stk->next;
  407.                 stk->next = cat2(&temp);    /* condense CAT nodes */
  408.                 if (stk->next == NULL) {
  409.                     free(ret);
  410.                     return NULL;
  411.                 }
  412.                 else stk->size = stk->next->size + 1;
  413.             }
  414.             break;
  415.         default:
  416.             printf("parse_re: unknown token type %d\n", tok_type(next_token));
  417.             break;
  418.         }
  419.         /* free_tok(next_token); */
  420.     }
  421. }
  422.  
  423. /* parse() essentially just calls parse_re().  Its purpose is to stick an
  424.    end-of-string token at the end of the syntax tree returned by parse_re().
  425.    It should really be done in parse_re, but the recursion there makes it
  426.    more desirable to have it here.                    */
  427.  
  428. Re_node parse(s)
  429. char *s;
  430. {
  431.     Re_node val, tree, temp;
  432.     Stack top, stk = NULL;
  433.  
  434.     if ((tree = parse_re(&s, NUL)) == NULL) return NULL;
  435.     if (Push(&stk, tree) == NULL) return NULL;
  436.     temp = mk_leaf(EOS, C_LIT, NUL, NULL);
  437.     if (temp == NULL || Push(&stk, temp) == NULL) return NULL;
  438.     final_pos = --pos_cnt;
  439.     top = cat2(&stk);
  440.     val = Top(top);
  441.     free(top);
  442.     return val;
  443. }
  444.  
  445.