home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / unix / dgrep.arc / DFATREE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-01-15  |  19.2 KB  |  863 lines
  1. /**********************************************************************\
  2.  *
  3.  *    DFATREE.C
  4.  *
  5.  * Creates a syntax tree from the regular expression.
  6.  *
  7.  * Before parsing the regular expression is changed from the character
  8.  * array to an integer array and also changed to a simpler syntax. Same 
  9.  * process does also lexical analyzing so that special symbols are in 
  10.  * the higher byte and normal characters in the lower byte.
  11.  *
  12.  * Parser is a recursive descent parser that builds the syntax tree.
  13.  *
  14.  * Parser syntax:
  15.  *
  16.  * primary-expression:
  17.  *    constant
  18.  *    character-class
  19.  *    empty
  20.  *    ( expression )
  21.  *
  22.  * closure-expression:
  23.  *    primary-expression
  24.  *    closure-expression primary-expression
  25.  *
  26.  * cat-expression:
  27.  *    closure-expression
  28.  *    cat-expression closure-expression
  29.  *
  30.  * or-expression:
  31.  *    cat-expression
  32.  *    or-expression cat-expression
  33.  *
  34.  * expression: 
  35.  *    or-expression
  36.  *
  37.  * Author: Jarmo Ruuth 15-Mar-1988
  38.  *
  39.  * Copyright (C) 1988-90 by Jarmo Ruuth
  40.  * May be freely copied for any non-commercial usage.
  41. \**********************************************************************/
  42.  
  43. #include "system.h"
  44. #include "dfa.h"
  45.  
  46. #define NCLASSITEMS    NLANG
  47. #define REGBLOCK    10
  48. #define NEGATE_CLASS    '^'
  49.  
  50. #define EMPTY        ( '@' << CHARBITS )    /* epsilon */
  51. #define CLASS        ( '[' << CHARBITS )
  52. #define    L_PAR        ( '(' << CHARBITS )
  53. #define    R_PAR        ( ')' << CHARBITS )
  54. #define    CLOSURE_OP    ( '*' << CHARBITS )
  55. #define    OR_OP        ( '|' << CHARBITS )
  56. #define BOL_OP        ( '^' << CHARBITS )
  57. #define EOL_OP        ( '$' << CHARBITS )
  58. #define    EOS        0
  59.  
  60. static node_t*    treeptr;    /* current syntax tree pointer */
  61. static node_t*    treestart;    /* pointer to start of the syntax tree */
  62. static int*    regexp;    /* modified regular expression */
  63. static int*    regptr;    /* current pointer to regexp */
  64. static int    memerr;        /* flag for out of memory error */
  65. static int    current;    /* current regexp token type */
  66. static int    next;        /* next regexp token type */
  67. static int    pos;        /* position in syntax tree */
  68. static int    regsize;    /* allocated size for regexp */
  69. static int    regpos;        /* index to regexp */
  70. static int    last_class;    /* last character class in classes */
  71. static set_t**    classes;    /* array of character classes for regexp */
  72. static uchar*    language;    /* boolean array of characters in language */
  73.  
  74. static int expression (void);
  75.  
  76. /**********************************************************************
  77.  *
  78.  *    CLEAR_LANGUAGE
  79.  */
  80. #ifdef BSD
  81. #define CLEAR_LANGUAGE(l)    bzero(l, NLANG)
  82. #else
  83. #define CLEAR_LANGUAGE(l)    memset(l, FALSE, NLANG)
  84. #endif
  85.  
  86. /**********************************************************************
  87.  *
  88.  *    tree_error
  89.  */
  90. static int tree_error(char* msg)
  91. {
  92.     current = next = pos = ERROR;    /* stop parsing */
  93.     rbuf.reg_error = msg;
  94.     return ERROR;
  95. }
  96.  
  97. /**********************************************************************
  98.  *
  99.  *    new_pos
  100.  *
  101.  * Gets new tree node and sets pos to point to it.
  102.  */
  103. static int new_pos(void)    
  104. {
  105.     ++pos;
  106.     if (pos == 0) {
  107.         if ((treestart = malloc(sizeof(node_t))) == NULL)
  108.             return tree_error("Out of memory");
  109.         treeptr = treestart;
  110.     } else {
  111.         if ((treestart=realloc(treestart,(pos+1)*sizeof(node_t)))==NULL)
  112.             return tree_error("Out of memory");
  113.         treeptr = treestart + pos;
  114.     }
  115.     return TRUE;
  116. }
  117.  
  118. /**********************************************************************
  119.  *
  120.  *    add_language
  121.  *
  122.  * Adds a new character to the recognized language.
  123.  */
  124. static void add_language(int ch)
  125. {
  126.     language[ch] = TRUE;
  127.     if (rbuf.ignorecase && isalpha(ch))
  128.         language[CHCASE(ch)] = TRUE;
  129. }
  130.  
  131. /**********************************************************************
  132.  *
  133.  *    add_item
  134.  *
  135.  * Adds a new leaf item to the syntax tree and returns tree position.
  136.  */
  137. static int add_item(node_type_t type, unsigned value)
  138. {
  139.     if (new_pos() == ERROR)
  140.         return ERROR;
  141.     treeptr->type = type;
  142.     treeptr->val.item = value;
  143.     if (type != EMPTY_ID)
  144.         add_language(value);
  145.     return pos;
  146. }
  147.  
  148. /**********************************************************************
  149.  *
  150.  *    add_node
  151.  *
  152.  * Adds a new node to the syntax tree and returns tree position.
  153.  */
  154. static int add_node(node_type_t type, int left, int right)
  155. {
  156.     if (new_pos() == ERROR)
  157.         return ERROR;
  158.     treeptr->type = type;
  159.     treeptr->val.next.left = left;
  160.     treeptr->val.next.right = right;
  161.     return pos;
  162. }
  163.  
  164. /**********************************************************************
  165.  *
  166.  *    add_regexp
  167.  *
  168.  * Adds a new item to the modified regular expression.
  169.  */
  170. static void add_regexp(int item)
  171. {
  172.     if (regexp == NULL) {
  173.         regpos = -1;
  174.         regsize = REGBLOCK;
  175.         if ((regexp = malloc(regsize*sizeof(int))) == NULL)
  176.             memerr = TRUE;
  177.     }
  178.     if (regpos == regsize-1) {
  179.         regsize += REGBLOCK;
  180.         if ((regexp = realloc(regexp, regsize*sizeof(int))) == NULL)
  181.             memerr = TRUE;
  182.     }
  183.     ++regpos;
  184.     if  (!(item & ~MAXCHAR) && rbuf.ignorecase && islower(item))
  185.         regexp[regpos] = toupper(item);
  186.     else
  187.         regexp[regpos] = item;
  188. }
  189.  
  190. /**********************************************************************
  191.  *
  192.  *    block_beg
  193.  *
  194.  * Finds the beginning of a possible block that starts from regpos.
  195.  */
  196. static int block_beg(int regpos)
  197. {
  198.     REG1 int    i, cnt;
  199.     
  200.     if (regexp[regpos] != R_PAR)
  201.         return regpos;
  202.     for (cnt = 1, i = regpos-1; i >= 0 && cnt; i--) {
  203.         if (regexp[i] == L_PAR)
  204.             --cnt;
  205.         if (regexp[i] == R_PAR)
  206.             ++cnt;
  207.     }
  208.     return i+1;
  209. }
  210.  
  211. /**********************************************************************
  212.  *
  213.  *    copy_class
  214.  *
  215.  * Copies class to the classes array. We can't use the same class twice, 
  216.  * because each class is released by calling free().
  217.  */
  218. static int copy_class(set_t *class)
  219. {
  220.     REG1 int    bsize;
  221.     REG2 set_t    *tmpclass;
  222.     
  223.     bsize = set_bytesize(NCLASSITEMS);
  224.     if ((tmpclass = malloc(bsize)) == NULL) {
  225.         memerr = TRUE;
  226.         return 0;
  227.     }
  228.     set_copy(tmpclass, class, bsize);
  229.     if ((classes=realloc(classes,(++last_class+1)*sizeof(set_t *)))==NULL) {
  230.         memerr = TRUE;
  231.         return 0;
  232.     }
  233.     classes[last_class] = tmpclass;
  234.     return last_class;
  235. }
  236.     
  237. /**********************************************************************
  238.  *
  239.  *    add_one_or_more
  240.  *
  241.  * Changes r+ to rr*.
  242.  */
  243. static void add_one_or_more(void)
  244. {
  245.     REG1 int    i, pos;
  246.  
  247.     for (i = block_beg(regpos), pos = regpos; i <= pos; i++)
  248.         add_regexp(regexp[i]);
  249.     for (i = pos+1, pos = regpos; i <= pos; i++)
  250.         if (regexp[i] == CLASS)
  251.                 regexp[i+1] = copy_class(classes[regexp[i+1]]);
  252.     add_regexp(CLOSURE_OP);
  253. }
  254.  
  255. /**********************************************************************
  256.  *
  257.  *    add_left_paren
  258.  *
  259.  * Finds previous block in regexp and adds left parethesis before it.
  260.  */
  261. static void add_left_paren(int regpos)
  262. {
  263.     REG1 int    i, pos, save;
  264.  
  265.     save = regexp[regpos];
  266.     pos = block_beg(regpos);
  267.     for (i = regpos; i > pos; i--)
  268.         regexp[i] = regexp[i-1];
  269.     regexp[pos] = L_PAR;
  270.     add_regexp(save);
  271. }
  272.  
  273. /**********************************************************************
  274.  *
  275.  *    add_zero_or_one
  276.  *
  277.  * Changes r? to (r|ε).
  278.  */
  279. static void add_zero_or_one(void)
  280. {
  281.     add_left_paren(regpos);
  282.     add_regexp(OR_OP);
  283.     add_regexp(EMPTY);
  284.     add_regexp(R_PAR);
  285. }
  286.  
  287. /**********************************************************************
  288.  *
  289.  *    add_class
  290.  *
  291.  * Adds character class to regexp. Classes are added to regexp so that
  292.  * it is surrounded by parenthesis and it contains CLASS marker followed
  293.  * by an integer that is class index to the classes array.
  294.  */
  295. static void add_class(REG1 uchar* class)
  296. {
  297.     REG2 int    i;
  298.     
  299.     class[rbuf.eol] = class[EOL] = class[REM] = FALSE;
  300.     if (classes == NULL) {
  301.         if ((classes = malloc(sizeof(set_t *))) == NULL) {
  302.             memerr = TRUE;
  303.             return;
  304.         }
  305.         last_class = 0;
  306.     } else {
  307.         if ((classes=realloc(classes,(++last_class+1)*sizeof(set_t *)))
  308.              == NULL) {
  309.             memerr = TRUE;
  310.             return;
  311.         }
  312.     }
  313.     if ((classes[last_class] = malloc(set_bytesize(NCLASSITEMS))) == NULL) {
  314.         memerr = TRUE;
  315.         return;
  316.     }
  317.     set_clear(classes[last_class], set_bytesize(NCLASSITEMS));
  318.     for (i = 0; i < NCLASSITEMS; i++)
  319.         if (class[i]) {
  320.             if (!language[i])
  321.                 add_language(i);
  322.             add_set(classes[last_class], i);
  323.         }
  324.     if (set_empty(classes[last_class], set_bytesize(NCLASSITEMS)))
  325.         add_regexp(EMPTY);
  326.     else {
  327.         add_regexp(L_PAR);
  328.         add_regexp(CLASS);
  329.         add_regexp(last_class);
  330.         add_regexp(R_PAR);
  331.     }
  332. }
  333.  
  334. /**********************************************************************
  335.  *
  336.  *    init_class
  337.  */
  338. #define init_class(c, v)    memset(c, v, NCLASSITEMS);
  339.  
  340. /**********************************************************************
  341.  *
  342.  *    get_class
  343.  *
  344.  * Collects class characters to boolean array indexed by characters
  345.  * and adds it to regexp.
  346.  */
  347. static uchar* get_class(REG3 uchar* str)
  348. {
  349.     REG1 int    i, end_range;
  350.     REG4 int    neg = FALSE;
  351.     uchar        class[NCLASSITEMS];
  352.  
  353.     init_class(class, FALSE);
  354.     ++str;    /* skip starting '[' */
  355.     if (*str == NEGATE_CLASS) {
  356.         ++str;
  357.         neg = TRUE;
  358.     }
  359.     if (*str == ']') {
  360.         ++str;
  361.         class[']'] = TRUE;
  362.     }
  363.     for (; *str && *str != ']'; str++) {
  364.         if (*str == '\\' && !*(++str))
  365.             return NULL;
  366.         if (*(str+1) == '-' && *(str+2) != ']') {
  367.             i = *str;
  368.             str +=  *(str+2) == '\\' ? 3 : 2;
  369.             if ((end_range = *str) == '\0')
  370.                 return NULL;
  371.             if (end_range < i) {
  372.                 int tmp = i;
  373.                 i = end_range;
  374.                 end_range = tmp;
  375.             }
  376.             for (; i <= end_range; i++)
  377.                 class[i] = TRUE;
  378.             continue;
  379.         }
  380.         class[*str] = TRUE;
  381.     }
  382.     if (rbuf.ignorecase) {
  383.         for (i = 1; i < NCHARS; i++)
  384.             if (isalpha(i))
  385.                 class[i] |= class[CHCASE(i)];
  386.     }
  387.     if (neg)
  388.         for (i = 1; i < NCLASSITEMS; i++)
  389.             class[i] = !class[i];
  390.     return *str == ']' ? add_class(class),str : NULL;
  391. }
  392.  
  393. /**********************************************************************
  394.  *
  395.  *    add_any
  396.  *
  397.  * Adds a character class to the regexp that matches any character except
  398.  * end of line.
  399.  */
  400. static void add_any(void)
  401. {
  402.     uchar    class[NCLASSITEMS];
  403.  
  404.     init_class(class, TRUE);
  405.     class[BOL] = class[rbuf.eol] = class[EOL] = FALSE;
  406.     add_class(class);
  407. }
  408.  
  409. /**********************************************************************
  410.  *
  411.  *    add_search_init
  412.  *
  413.  * Adds [0-MAXCHAR]*( to the beginning of the regexp if we are building
  414.  * a substring searcher. Note, that no characters from here are added 
  415.  * to the language.
  416.  */
  417. static void add_search_init(void)
  418. {
  419.     uchar    class[NCLASSITEMS];
  420.     
  421.     init_class(class, TRUE);
  422.     add_class(class);
  423.     add_regexp(CLOSURE_OP);
  424.     add_regexp(L_PAR);
  425. }
  426.  
  427. /**********************************************************************
  428.  *
  429.  *    make_regexp
  430.  *
  431.  * Changes regular expression to simpler syntax (uses only '(', ')', '|',
  432.  * '*' and 'ε'). Integer array is used, so full eight bit character set
  433.  * except '\0' can be used.
  434.  */
  435. static char* make_regexp(REG1 uchar* str)
  436. {
  437.     REG2 uchar*    strbeg = str;
  438.     REG3 int    paren_cnt = 0;
  439.     
  440.     regexp = NULL;
  441.     /* Check special cases and make sure, that they match to every line. */
  442.     /* Is this really necessary and correct ? */
  443.     if (((*str == '$' || *str == '^') && *(str+1) == '\0')
  444.         || *str == '\0')
  445.         str = "a*";
  446.     /* If we are building a substring searcher, change regexp r to form
  447.        [0-MAXCHAR]*(r). It guarantees, that substring is found in 
  448.        O(n+m)-time.
  449.     */
  450.     memerr = FALSE;
  451.     if (rbuf.search)
  452.         add_search_init();
  453.     CLEAR_LANGUAGE(language);
  454.     rbuf.begline = rbuf.endline = FALSE;
  455.     for (; *str && !memerr; str++) {
  456.         switch (*str) {
  457.             case '\\':
  458.                 if (*(str+1) != '\0')
  459.                     add_regexp(*(++str));
  460.                 else
  461.                     add_regexp(*str);
  462.                 break;
  463.             case '(':
  464.                 if (*(str+1) == ')')
  465.                     ++str;
  466.                 else if (*(str+1) == '\0')
  467.                     add_regexp(*str);
  468.                 else {
  469.                     add_regexp(L_PAR);
  470.                     ++paren_cnt;
  471.                 }
  472.                 break;
  473.             case ')':
  474.                 --paren_cnt;
  475.                 add_regexp(R_PAR);
  476.                 break;
  477.             case '[':
  478.                 str = get_class(str);
  479.                 if (str == NULL)
  480.                     return "Unterminated character class";
  481.                 break;
  482.             case ']':
  483.                 add_regexp(*str);
  484.                 break;
  485.             case '*':
  486.                 if (str != strbeg)
  487.                     add_regexp(CLOSURE_OP);
  488.                 else
  489.                     add_regexp(*str);
  490.                 break;
  491.             case '?':
  492.                 if (str != strbeg)
  493.                     add_zero_or_one();
  494.                 else
  495.                     add_regexp(*str);
  496.                 continue;
  497.             case '+':
  498.                 if (str != strbeg)
  499.                     add_one_or_more();
  500.                 else
  501.                     add_regexp(*str);
  502.                 break;
  503.             case '.':
  504.                 add_any();
  505.                 break;
  506.             case '|':
  507.                 if (str == strbeg || *(str+1) == '\0')
  508.                     add_regexp(*str);
  509.                 else if (*(str-1) == '(') {
  510.                     add_regexp(EMPTY);
  511.                     add_regexp(OR_OP);
  512.                 } else if (*(str+1) == ')') {
  513.                     add_regexp(OR_OP);
  514.                     add_regexp(EMPTY);
  515.                 } else
  516.                     add_regexp(OR_OP);
  517.                 break;
  518.             case '^':
  519.                 rbuf.begline = TRUE;
  520.                 add_regexp(BOL_OP);
  521.                 break;
  522.             case '$':
  523.                 rbuf.endline = TRUE;
  524.                 add_regexp(EOL_OP);
  525.                 break;
  526.             default:
  527.                 if (*str == rbuf.eol || *str == rbuf.eol2)
  528.                     return  "End of line character "
  529.                         "in regular expression";
  530.                 add_regexp(*str);
  531.                 break;
  532.         }
  533.     }
  534.     /* Finish L_PAR started at add_search_init() */
  535.     if (rbuf.search)
  536.         add_regexp(R_PAR);
  537.     add_regexp(EOS);
  538.     if (memerr)
  539.         return "Out of memory";
  540.     return paren_cnt ? "Unbalanced parenthesis" : NULL;
  541. }
  542.  
  543. /**********************************************************************
  544.  *
  545.  *    fetch_next
  546.  */
  547. #define fetch_next() \
  548. { \
  549.     current = next; \
  550.     next = *(++regptr); \
  551. }
  552.  
  553. /**********************************************************************
  554.  *
  555.  *    fetch_new
  556.  */
  557. #define fetch_new() \
  558. { \
  559.     current = *(++regptr); \
  560.     next = *(++regptr); \
  561. }
  562.  
  563. /**********************************************************************
  564.  *
  565.  *    primary_exp
  566.  */
  567. static int primary_exp(void)
  568. {
  569.     REG1 int    last_pos;
  570.     
  571.     switch (current) {
  572.         case L_PAR:
  573.             fetch_next();        /* skip L_PAR */
  574.             last_pos = expression();
  575.             if (next != R_PAR)
  576.                 return tree_error("Error in expression");
  577.             fetch_next();        /* skip R_PAR */
  578.             return last_pos;
  579.         case R_PAR:
  580.         case CLOSURE_OP:
  581.         case OR_OP:
  582.             return tree_error("Error in expression");
  583.         case EOS:
  584.             return tree_error("Premature end of expression");
  585.         case CLASS:
  586.             fetch_next();
  587.             if (new_pos() == ERROR)
  588.                 return ERROR;
  589.             treeptr->type = CLASS_ID;
  590.             treeptr->val.class = classes[current];
  591.             return pos;
  592.         case EMPTY:
  593.             return add_item(EMPTY_ID, 0);
  594.         case EOL_OP:
  595.             add_language(EOL);
  596.             return add_item(ID, rbuf.eol);
  597.         case BOL_OP:
  598.             return add_item(ID, BOL);
  599.         case ERROR:
  600.             return ERROR;
  601.         default:
  602.             return add_item(ID, current);
  603.     }
  604. }
  605.  
  606. /**********************************************************************
  607.  *
  608.  *    closure_exp
  609.  */
  610. static int closure_exp(void)
  611. {
  612.     REG1 int    left;
  613.  
  614.     left = primary_exp();
  615.     switch (next) {
  616.         case CLOSURE_OP:
  617.             fetch_next();
  618.             return add_node(CLOSURE, left, 0);
  619.         default:
  620.             return left;
  621.     }
  622. }
  623.  
  624. /**********************************************************************
  625.  *
  626.  *    cat_exp
  627.  */
  628. static int cat_exp(void)
  629. {
  630.     REG1 int    left, right;
  631.     
  632.     left = closure_exp();
  633.     for (;;) {
  634.         switch (next) {
  635.             case R_PAR:
  636.             case CLOSURE_OP:
  637.             case OR_OP:
  638.             case EOS:
  639.             case ERROR:
  640.                 return left;
  641.             case L_PAR:
  642.             default:
  643.                 fetch_next();
  644.                 right = closure_exp();
  645.                 if (right == ERROR)
  646.                     return ERROR;
  647.                 if (add_node(CAT, left, right) == ERROR)
  648.                     return ERROR;
  649.                 left = pos;
  650.                 continue;
  651.         }
  652.     }
  653. }
  654.  
  655. /**********************************************************************
  656.  *
  657.  *    expression
  658.  */
  659. static int expression(void)
  660. {
  661.     REG1 int    left, right;
  662.  
  663.     left = cat_exp();
  664.     for (;;) {
  665.         switch (next) {
  666.             case OR_OP:
  667.                 fetch_new();
  668.                 right = cat_exp();
  669.                 if (right == ERROR)
  670.                     return ERROR;
  671.                 if (add_node(OR, left, right) == ERROR)
  672.                     return ERROR;
  673.                 left = pos;
  674.                 continue;
  675.             default:
  676.                 return left;
  677.         }
  678.     }
  679. }
  680.  
  681. /**********************************************************************
  682.  *
  683.  *    add_endmarker
  684.  *
  685.  * Adds unique right-end marker to the regular expression.
  686.  */
  687. static int add_endmarker(REG1 int left)
  688. {
  689.     REG2 int    right;
  690.  
  691.     if (add_item(ID, REM) == ERROR)
  692.         return ERROR;
  693.     /* catenate original expression and right-end marker */
  694.     right = pos;
  695.     if (add_node(CAT, left, right) == ERROR)
  696.         return ERROR;
  697.     return TRUE;
  698. }
  699.  
  700. /**********************************************************************
  701.  *
  702.  *    convert_language
  703.  *
  704.  * Converts language from boolean array to a list of those characters 
  705.  * that belong to the language. Rbuf.language[0] is number of characters
  706.  * in language.
  707.  */
  708. static bool convert_language(void)
  709. {
  710.     REG1 unsigned    i, j;
  711.     
  712.     /* calculate number of items in language */
  713.     for (i = j = 0; i < NLANG; i++)
  714.         if (language[i])
  715.             j++;
  716.     /* allocate buffer for language items */
  717.     if ((rbuf.language = malloc((j+1)*sizeof(rbuf.language[0]))) == NULL)
  718.         return FALSE;
  719.     /* Copy language elements to the rbuf. Note that the zeroth element
  720.        contains the number of characters in language. */
  721.     rbuf.language[0] = j;
  722.     for (i = 0, j = 1; i < NLANG; i++)
  723.         if (language[i])
  724.             rbuf.language[j++] = i;
  725.     return TRUE;
  726. }
  727.     
  728. #ifdef TEST
  729.  
  730. #if defined(__TURBOC__) || defined(MSDOS)
  731. #define EMPTYCH    0xee
  732. #else
  733. #define EMPTYCH    '@'
  734. #endif
  735.  
  736. extern int debug;
  737.  
  738. /**********************************************************************
  739.  *
  740.  *    print_regexp
  741.  */
  742. static void print_regexp(void)
  743. {
  744.     int* ptr;
  745.     
  746.     for (ptr = regexp; *ptr; ptr++) {
  747.         switch (*ptr) {
  748.             case L_PAR:
  749.                 putchar('(');
  750.                 break;
  751.             case R_PAR:
  752.                 putchar(')');
  753.                 break;
  754.             case CLOSURE_OP:
  755.                 putchar('*');
  756.                 break;
  757.             case OR_OP:
  758.                 putchar('|');
  759.                 break;
  760.             case EMPTY:
  761.                 putchar(EMPTYCH);
  762.                 break;
  763.             case BOL_OP:
  764.                 putchar('^');
  765.                 break;
  766.             case EOL_OP:
  767.                 putchar('$');
  768.                 break;
  769.             case CLASS:
  770.                 putchar('[');
  771.                 ++ptr;
  772.                 printf("%d", *ptr);
  773.                 putchar(']');
  774.                 break;
  775.             default:
  776.                 putchar(*ptr);
  777.                 break;
  778.         }
  779.     }
  780.     putchar('\n');
  781. }        
  782. #endif /* TEST */
  783.  
  784. /**********************************************************************
  785.  *
  786.  *    free_treemem
  787.  *
  788.  * Releases all unnecessary memory.
  789.  */
  790. static void free_treemem(void)
  791. {
  792.     d_free(&language);
  793.     d_free(&classes);
  794.     d_free(®exp);
  795. }    
  796.  
  797. /**********************************************************************
  798.  *
  799.  *    error_return
  800.  */
  801. static int error_return(REG1 char* msg)
  802. {
  803.     d_free(&treestart);
  804.     free_treemem();
  805.     if (msg)
  806.         rbuf.reg_error = msg;
  807.     else if (!rbuf.reg_error)
  808.         rbuf.reg_error = "Error in expression";
  809.     return ERROR;
  810. }
  811.  
  812. /**********************************************************************
  813.  *
  814.  *    init_tree
  815.  */
  816. static char* init_tree(void)
  817. {
  818.     classes = NULL;
  819.     treestart = treeptr = rbuf.tree = NULL;
  820.     rbuf.root = -1;
  821.     regexp = NULL;
  822.     if ((language = malloc(NLANG)) == NULL)
  823.         return "Out of memory";
  824.     return NULL;
  825. }
  826.  
  827. /**********************************************************************
  828.  *
  829.  *    create_tree
  830.  *
  831.  * Creates syntax tree from given regular expression. Returns root
  832.  * of the tree or -1, if there was errors.
  833.  */
  834. int create_tree(REG2 uchar* str)
  835. {
  836.     REG1 int    left;
  837.     REG3 char*    msg;
  838.     
  839.     if ((msg = init_tree()) != NULL)
  840.         return error_return(msg);
  841.     if ((msg = make_regexp(str)) != NULL)
  842.         return error_return(msg);
  843. #ifdef TEST
  844.     if (debug)
  845.         print_regexp();
  846. #endif
  847.     regptr = regexp;
  848.     current = *regptr;
  849.     next = *(++regptr);
  850.     pos = -1;
  851.     left = expression();
  852.     if (left == ERROR || next != EOS)
  853.         return error_return(NULL);
  854.     if (add_endmarker(left) == ERROR)
  855.         return error_return(NULL);
  856.     if (!convert_language())
  857.         return error_return("Out of memory");
  858.     free_treemem();
  859.     rbuf.tree = treestart;
  860.     rbuf.root = pos;
  861.     return pos;
  862. }
  863.