Lines Matching refs:tree
795 /* Parse the regular expression, and build a structure tree. */
801 /* Analyze the tree and create the nfa. */
1149 /* Analyze the structure tree, and calculate "first", "next", "edest",
1213 implement parse tree visits. Instead, we use parent pointers and
1223 /* Descend down the tree, preferably to the left (or to the right
1338 bin_tree_t *op, *cls, *tree1, *tree;
1356 tree = create_tree (dfa, op, tree1, CONCAT);
1357 if (BE (tree == NULL || tree1 == NULL || op == NULL || cls == NULL, 0))
1365 return tree;
1391 /* Pass 2: compute NEXT on the tree. Preorder visit. */
2101 Parse the regular expression REGEXP and return the structure tree.
2103 This function build the following tree, from regular expression <reg_exp>:
2117 bin_tree_t *tree, *eor, *root;
2121 tree = parse_reg_exp (regexp, preg, ¤t_token, syntax, 0, err);
2122 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2125 if (tree != NULL)
2126 root = create_tree (dfa, tree, eor, CONCAT);
2137 /* This function build the following tree, from regular expression
2151 bin_tree_t *tree, *branch = NULL;
2152 tree = parse_branch (regexp, preg, token, syntax, nest, err);
2153 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2168 tree = create_tree (dfa, tree, branch, OP_ALT);
2169 if (BE (tree == NULL, 0))
2175 return tree;
2178 /* This function build the following tree, from regular expression
2191 bin_tree_t *tree, *exp;
2193 tree = parse_expression (regexp, preg, token, syntax, nest, err);
2194 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2203 if (tree != NULL)
2204 postorder (tree, free_tree, NULL);
2207 if (tree != NULL && exp != NULL)
2209 bin_tree_t *newtree = create_tree (dfa, tree, exp, CONCAT);
2213 postorder (tree, free_tree, NULL);
2217 tree = newtree;
2219 else if (tree == NULL)
2220 tree = exp;
2221 /* Otherwise exp == NULL, we don't need to create new tree. */
2223 return tree;
2226 /* This function build the following tree, from regular expression a*:
2237 bin_tree_t *tree;
2241 tree = create_token_tree (dfa, NULL, NULL, token);
2242 if (BE (tree == NULL, 0))
2256 tree = create_tree (dfa, tree, mbc_remain, CONCAT);
2257 if (BE (mbc_remain == NULL || tree == NULL, 0))
2267 tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err);
2268 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2272 tree = parse_bracket_exp (regexp, dfa, token, syntax, err);
2273 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2283 tree = create_token_tree (dfa, NULL, NULL, token);
2284 if (BE (tree == NULL, 0))
2328 tree = create_token_tree (dfa, NULL, NULL, token);
2329 if (BE (tree == NULL, 0))
2357 tree = create_tree (dfa, tree_first, tree_last, OP_ALT);
2358 if (BE (tree_first == NULL || tree_last == NULL || tree == NULL, 0))
2366 tree = create_token_tree (dfa, NULL, NULL, token);
2367 if (BE (tree == NULL, 0))
2378 return tree;
2380 tree = create_token_tree (dfa, NULL, NULL, token);
2381 if (BE (tree == NULL, 0))
2391 tree = build_charclass_op (dfa, regexp->trans,
2395 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2400 tree = build_charclass_op (dfa, regexp->trans,
2404 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2425 tree = parse_dup_op (tree, regexp, dfa, token, syntax, err);
2426 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2438 return tree;
2441 /* This function build the following tree, from regular expression
2453 bin_tree_t *tree;
2461 tree = NULL;
2464 tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
2467 if (tree != NULL)
2468 postorder (tree, free_tree, NULL);
2478 tree = create_tree (dfa, tree, NULL, SUBEXP);
2479 if (BE (tree == NULL, 0))
2484 tree->token.opr.idx = cur_nsub;
2485 return tree;
2494 bin_tree_t *tree = NULL, *old_tree = NULL;
2567 tree = elem;
2571 tree = create_tree (dfa, tree, elem, CONCAT);
2572 if (BE (elem == NULL || tree == NULL, 0))
2577 return tree;
2581 old_tree = tree;
2589 tree = create_tree (dfa, elem, NULL, (end == -1 ? OP_DUP_ASTERISK : OP_ALT));
2590 if (BE (tree == NULL, 0))
2599 tree = create_tree (dfa, tree, elem, CONCAT);
2600 if (BE (elem == NULL || tree == NULL, 0))
2603 tree = create_tree (dfa, tree, NULL, OP_ALT);
2604 if (BE (tree == NULL, 0))
2609 tree = create_tree (dfa, old_tree, tree, CONCAT);
2611 return tree;
3259 /* Build a tree for complex bracket. */
3273 /* Build a tree for simple bracket. */
3297 /* Build a tree for simple bracket. */
3596 bin_tree_t *tree;
3650 /* Build a tree for simple bracket. */
3653 tree = create_token_tree (dfa, NULL, NULL, &br_token);
3654 if (BE (tree == NULL, 0))
3661 /* Build a tree for complex bracket. */
3669 tree = create_tree (dfa, tree, mbc_tree, OP_ALT);
3671 return tree;
3676 return tree;
3679 return tree;
3734 /* Functions for binary tree operation. */
3736 /* Create a tree node. */
3751 bin_tree_t *tree;
3762 tree = &dfa->str_tree_storage->data[dfa->str_tree_storage_idx++];
3764 tree->parent = NULL;
3765 tree->left = left;
3766 tree->right = right;
3767 tree->token = *token;
3768 tree->token.duplicated = 0;
3769 tree->token.opt_subexp = 0;
3770 tree->first = NULL;
3771 tree->next = NULL;
3772 tree->node_idx = -1;
3775 left->parent = tree;
3777 right->parent = tree;
3778 return tree;
3781 /* Mark the tree SRC as an optional subexpression.
3808 /* Worker function for tree walking. Free the allocated memory inside NODE
3833 /* Create a new tree and link it back to the current parent. */