Lines Matching refs:tree
797 /* Parse the regular expression, and build a structure tree. */
803 /* Analyze the tree and create the nfa. */
1115 /* Analyze the structure tree, and calculate "first", "next", "edest",
1179 implement parse tree visits. Instead, we use parent pointers and
1189 /* Descend down the tree, preferably to the left (or to the right
1304 bin_tree_t *op, *cls, *tree1, *tree;
1322 tree = create_tree (dfa, op, tree1, CONCAT);
1323 if (BE (tree == NULL || tree1 == NULL || op == NULL || cls == NULL, 0))
1331 return tree;
1357 /* Pass 2: compute NEXT on the tree. Preorder visit. */
2062 Parse the regular expression REGEXP and return the structure tree.
2064 This function build the following tree, from regular expression <reg_exp>:
2078 bin_tree_t *tree, *eor, *root;
2082 tree = parse_reg_exp (regexp, preg, ¤t_token, syntax, 0, err);
2083 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2086 if (tree != NULL)
2087 root = create_tree (dfa, tree, eor, CONCAT);
2098 /* This function build the following tree, from regular expression
2112 bin_tree_t *tree, *branch = NULL;
2113 tree = parse_branch (regexp, preg, token, syntax, nest, err);
2114 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2129 tree = create_tree (dfa, tree, branch, OP_ALT);
2130 if (BE (tree == NULL, 0))
2136 return tree;
2139 /* This function build the following tree, from regular expression
2152 bin_tree_t *tree, *exp;
2154 tree = parse_expression (regexp, preg, token, syntax, nest, err);
2155 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2166 if (tree != NULL && exp != NULL)
2168 tree = create_tree (dfa, tree, exp, CONCAT);
2169 if (tree == NULL)
2175 else if (tree == NULL)
2176 tree = exp;
2177 /* Otherwise exp == NULL, we don't need to create new tree. */
2179 return tree;
2182 /* This function build the following tree, from regular expression a*:
2193 bin_tree_t *tree;
2197 tree = create_token_tree (dfa, NULL, NULL, token);
2198 if (BE (tree == NULL, 0))
2212 tree = create_tree (dfa, tree, mbc_remain, CONCAT);
2213 if (BE (mbc_remain == NULL || tree == NULL, 0))
2223 tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err);
2224 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2228 tree = parse_bracket_exp (regexp, dfa, token, syntax, err);
2229 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2239 tree = create_token_tree (dfa, NULL, NULL, token);
2240 if (BE (tree == NULL, 0))
2284 tree = create_token_tree (dfa, NULL, NULL, token);
2285 if (BE (tree == NULL, 0))
2313 tree = create_tree (dfa, tree_first, tree_last, OP_ALT);
2314 if (BE (tree_first == NULL || tree_last == NULL || tree == NULL, 0))
2322 tree = create_token_tree (dfa, NULL, NULL, token);
2323 if (BE (tree == NULL, 0))
2334 return tree;
2336 tree = create_token_tree (dfa, NULL, NULL, token);
2337 if (BE (tree == NULL, 0))
2347 tree = build_charclass_op (dfa, regexp->trans,
2351 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2356 tree = build_charclass_op (dfa, regexp->trans,
2360 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2381 tree = parse_dup_op (tree, regexp, dfa, token, syntax, err);
2382 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2394 return tree;
2397 /* This function build the following tree, from regular expression
2409 bin_tree_t *tree;
2417 tree = NULL;
2420 tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
2430 tree = create_tree (dfa, tree, NULL, SUBEXP);
2431 if (BE (tree == NULL, 0))
2436 tree->token.opr.idx = cur_nsub;
2437 return tree;
2446 bin_tree_t *tree = NULL, *old_tree = NULL;
2519 tree = elem;
2523 tree = create_tree (dfa, tree, elem, CONCAT);
2524 if (BE (elem == NULL || tree == NULL, 0))
2529 return tree;
2533 old_tree = tree;
2541 tree = create_tree (dfa, elem, NULL, (end == -1 ? OP_DUP_ASTERISK : OP_ALT));
2542 if (BE (tree == NULL, 0))
2551 tree = create_tree (dfa, tree, elem, CONCAT);
2552 if (BE (elem == NULL || tree == NULL, 0))
2555 tree = create_tree (dfa, tree, NULL, OP_ALT);
2556 if (BE (tree == NULL, 0))
2561 tree = create_tree (dfa, old_tree, tree, CONCAT);
2563 return tree;
3225 /* Build a tree for complex bracket. */
3239 /* Build a tree for simple bracket. */
3263 /* Build a tree for simple bracket. */
3563 bin_tree_t *tree;
3617 /* Build a tree for simple bracket. */
3620 tree = create_token_tree (dfa, NULL, NULL, &br_token);
3621 if (BE (tree == NULL, 0))
3628 /* Build a tree for complex bracket. */
3636 tree = create_tree (dfa, tree, mbc_tree, OP_ALT);
3638 return tree;
3643 return tree;
3646 return tree;
3701 /* Functions for binary tree operation. */
3703 /* Create a tree node. */
3718 bin_tree_t *tree;
3729 tree = &dfa->str_tree_storage->data[dfa->str_tree_storage_idx++];
3731 tree->parent = NULL;
3732 tree->left = left;
3733 tree->right = right;
3734 tree->token = *token;
3735 tree->token.duplicated = 0;
3736 tree->token.opt_subexp = 0;
3737 tree->first = NULL;
3738 tree->next = NULL;
3739 tree->node_idx = -1;
3742 left->parent = tree;
3744 right->parent = tree;
3745 return tree;
3748 /* Mark the tree SRC as an optional subexpression.
3775 /* Worker function for tree walking. Free the allocated memory inside NODE
3800 /* Create a new tree and link it back to the current parent. */