Lines Matching defs:tree
818 /* Parse the regular expression, and build a structure tree. */
824 /* Analyze the tree and create the nfa. */
1150 /* Analyze the structure tree, and calculate "first", "next", "edest",
1214 implement parse tree visits. Instead, we use parent pointers and
1224 /* Descend down the tree, preferably to the left (or to the right
1339 bin_tree_t *op, *cls, *tree1, *tree;
1357 tree = create_tree (dfa, op, tree1, CONCAT);
1358 if (BE (tree == NULL || tree1 == NULL || op == NULL || cls == NULL, 0))
1366 return tree;
1392 /* Pass 2: compute NEXT on the tree. Preorder visit. */
2105 Parse the regular expression REGEXP and return the structure tree.
2107 This function build the following tree, from regular expression <reg_exp>:
2121 bin_tree_t *tree, *eor, *root;
2125 tree = parse_reg_exp (regexp, preg, ¤t_token, syntax, 0, err);
2126 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2129 if (tree != NULL)
2130 root = create_tree (dfa, tree, eor, CONCAT);
2141 /* This function build the following tree, from regular expression
2155 bin_tree_t *tree, *branch = NULL;
2156 tree = parse_branch (regexp, preg, token, syntax, nest, err);
2157 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2172 tree = create_tree (dfa, tree, branch, OP_ALT);
2173 if (BE (tree == NULL, 0))
2179 return tree;
2182 /* This function build the following tree, from regular expression
2195 bin_tree_t *tree, *expr;
2197 tree = parse_expression (regexp, preg, token, syntax, nest, err);
2198 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2209 if (tree != NULL && expr != NULL)
2211 tree = create_tree (dfa, tree, expr, CONCAT);
2212 if (tree == NULL)
2218 else if (tree == NULL)
2219 tree = expr;
2220 /* Otherwise expr == NULL, we don't need to create new tree. */
2222 return tree;
2225 /* This function build the following tree, from regular expression a*:
2236 bin_tree_t *tree;
2240 tree = create_token_tree (dfa, NULL, NULL, token);
2241 if (BE (tree == NULL, 0))
2255 tree = create_tree (dfa, tree, mbc_remain, CONCAT);
2256 if (BE (mbc_remain == NULL || tree == NULL, 0))
2266 tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err);
2267 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2271 tree = parse_bracket_exp (regexp, dfa, token, syntax, err);
2272 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2282 tree = create_token_tree (dfa, NULL, NULL, token);
2283 if (BE (tree == NULL, 0))
2327 tree = create_token_tree (dfa, NULL, NULL, token);
2328 if (BE (tree == NULL, 0))
2356 tree = create_tree (dfa, tree_first, tree_last, OP_ALT);
2357 if (BE (tree_first == NULL || tree_last == NULL || tree == NULL, 0))
2365 tree = create_token_tree (dfa, NULL, NULL, token);
2366 if (BE (tree == NULL, 0))
2377 return tree;
2379 tree = create_token_tree (dfa, NULL, NULL, token);
2380 if (BE (tree == NULL, 0))
2390 tree = build_charclass_op (dfa, regexp->trans,
2394 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2399 tree = build_charclass_op (dfa, regexp->trans,
2403 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2424 tree = parse_dup_op (tree, regexp, dfa, token, syntax, err);
2425 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2437 return tree;
2440 /* This function build the following tree, from regular expression
2452 bin_tree_t *tree;
2460 tree = NULL;
2463 tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
2473 tree = create_tree (dfa, tree, NULL, SUBEXP);
2474 if (BE (tree == NULL, 0))
2479 tree->token.opr.idx = cur_nsub;
2480 return tree;
2489 bin_tree_t *tree = NULL, *old_tree = NULL;
2563 tree = elem;
2567 tree = create_tree (dfa, tree, elem, CONCAT);
2568 if (BE (elem == NULL || tree == NULL, 0))
2573 return tree;
2577 old_tree = tree;
2585 tree = create_tree (dfa, elem, NULL,
2587 if (BE (tree == NULL, 0))
2601 tree = create_tree (dfa, tree, elem, CONCAT);
2602 if (BE (elem == NULL || tree == NULL, 0))
2605 tree = create_tree (dfa, tree, NULL, OP_ALT);
2606 if (BE (tree == NULL, 0))
2611 tree = create_tree (dfa, old_tree, tree, CONCAT);
2613 return tree;
3289 /* Build a tree for complex bracket. */
3303 /* Build a tree for simple bracket. */
3328 /* Build a tree for simple bracket. */
3629 bin_tree_t *tree;
3689 /* Build a tree for simple bracket. */
3692 tree = create_token_tree (dfa, NULL, NULL, &br_token);
3693 if (BE (tree == NULL, 0))
3700 /* Build a tree for complex bracket. */
3708 tree = create_tree (dfa, tree, mbc_tree, OP_ALT);
3710 return tree;
3715 return tree;
3718 return tree;
3775 /* Functions for binary tree operation. */
3777 /* Create a tree node. */
3792 bin_tree_t *tree;
3803 tree = &dfa->str_tree_storage->data[dfa->str_tree_storage_idx++];
3805 tree->parent = NULL;
3806 tree->left = left;
3807 tree->right = right;
3808 tree->token = *token;
3809 tree->token.duplicated = 0;
3810 tree->token.opt_subexp = 0;
3811 tree->first = NULL;
3812 tree->next = NULL;
3813 tree->node_idx = REG_MISSING;
3816 left->parent = tree;
3818 right->parent = tree;
3819 return tree;
3822 /* Mark the tree SRC as an optional subexpression.
3849 /* Worker function for tree walking. Free the allocated memory inside NODE
3874 /* Create a new tree and link it back to the current parent. */