alogos.systems._shared.init_tree

Shared functions for generating derivation trees.

Functions

uniform(grammar, max_expansions=10000)

Generate a derivation tree by choosing uniformly random rules.

weighted(grammar, max_expansions=10000, reduction_factor=0.96)

Generate a derivation tree by choosing weighted random rules.

ptc2(grammar, max_expansions=100)

Create a derivation tree with Nicolau's PTC2 variant.

grow_one_branch_to_max_depth(grammar, max_depth=20)

Randomly grow a tree and try to reach a maximum depth in at least one branch.

grow_all_branches_within_max_depth(grammar, max_depth=20)

Randomly grow a tree and try to stay below a maximum depth in all branches.

grow_all_branches_to_max_depth(grammar, max_depth=20)

Randomly grow a tree and try to reach a maximum depth in all branches.

Detailed object descriptions

alogos.systems._shared.init_tree.uniform(grammar, max_expansions=10000)[source]

Generate a derivation tree by choosing uniformly random rules.

Parameters:

  • grammar (Grammar)

  • max_expansions (int) – Maximum number of expansions of nonterminal symbols. This is a limit value. Reaching it leads to raising an error.

Returns:

derivation_tree (DerivationTree)

Raises:

MappingError – If the maximum number of expansions is reached.

Notes

Each possible rule has the same probability of being selected throughout the entire derivation [1].

This is a problem if there are recursive rules that tend to introduce more symbols than they remove. It is unlikely to generate a finished derivation tree in this case.

References

alogos.systems._shared.init_tree.weighted(grammar, max_expansions=10000, reduction_factor=0.96)[source]

Generate a derivation tree by choosing weighted random rules.

Parameters:

  • grammar (Grammar)

  • max_expansions (int, optional) – Maximum number of expansions of nonterminal symbols. This is a limit value. Reaching it leads to raising an error.

  • reduction_factor (float, optional) – Factor by which the weight of a rule is multiplied to reduce its probability of being selected again within the same branch. Its value should be between 0.0 and 1.0.

Returns:

derivation_tree (DerivationTree)

Raises:

MappingError – If the maximum number of expansions is reached.

Notes

Each rule gets an initial weight of 1.0 that influences its chance of being selected in the next expansion of a nonterminal. Every time a rule is chosen within a branch of the tree, its weight gets reduced (only in that branch) by multiplying it with a provided factor [2].

This limits the chance of a single rule being chosen over and over again in the same branch, which leads to a better chance of generating a finished derivation tree within a given maximum number of expansions, especially in the presence of recursive rules.

References

alogos.systems._shared.init_tree.ptc2(grammar, max_expansions=100)[source]

Create a derivation tree with Nicolau’s PTC2 variant.

Parameters:

  • grammar (Grammar)

  • max_expansions (int, optional) – Desired maximum number of nonterminal expansions. This is a target value. Missing it slightly below or above does not raise an error.

Returns:

derivation_tree (DerivationTree)

alogos.systems._shared.init_tree.grow_one_branch_to_max_depth(grammar, max_depth=20)[source]

Randomly grow a tree and try to reach a maximum depth in at least one branch.

Parameters:

  • grammar (Grammar)

  • max_depth (int, optional) – Desired maximum depth of the tree. This is a target value. Missing it slightly below or above does not raise an error.

Returns:

derivation_tree (DerivationTree)

alogos.systems._shared.init_tree.grow_all_branches_within_max_depth(grammar, max_depth=20)[source]

Randomly grow a tree and try to stay below a maximum depth in all branches.

Parameters:

  • grammar (Grammar)

  • max_depth (int, optional) – Desired maximum depth of the tree. This is a target value. Missing it slightly below or above does not raise an error.

Returns:

derivation_tree (DerivationTree)

alogos.systems._shared.init_tree.grow_all_branches_to_max_depth(grammar, max_depth=20)[source]

Randomly grow a tree and try to reach a maximum depth in all branches.

Parameters:

  • grammar (Grammar)

  • max_depth (int, optional) – Desired maximum depth of the tree. This is a target value. Missing it slightly below or above does not raise an error.

Returns:

derivation_tree (DerivationTree)