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