treeANL {xegaDerivationTrees}

Builds an Attributed Node List (ANL) of a derivation tree.

Description

treeANL() recursively traverses a derivation tree and collects information about the derivation tree in an attributed node list (ANL).

Usage

treeANL(
  tree,
  ST,
  maxdepth = 5,
  ANL = list(),
  IL = list(),
  count = 1,
  depth = 1
)

Arguments

tree

A derivation tree.

ST

A symbol table.

maxdepth

Limit on the depth of a derivation tree.

ANL

Attributed node list (empty on invocation).

IL

Index function list (empty on invocation).

count

Trail count (1 on invocation).

depth

Derivation tree depth (1 on invocation).

Details

An attributed node has the following elements:

• $ID: Id in the symbol table ST.

• $NT: Is the symbol a non-terminal?

• $Pos: Position in the trail.

• $Depth: Depth of node.

• $RDepth: Residual depth for expansion.

• $subtreedepth: Depth of subtree starting here.

• $Index: R index of the node in the derivation tree. Allows fast tree extraction and insertion.

These elements can be used e.g.

• for inserting and extracting subtrees (Pos or node$Index),

• for checking the feasibility of subtree substitution (ID),

• for checking depth bounds (Depth, RDepth, and subtreedepth), ...

Value

A list with three elements:

1. r$count: The trail length (not needed).

2. r$depth: The derivation tree depth (not needed).

3. r$ANL: The attributed node list is a list of nodes. Each node is represented as a list of the following attributes:

   • Node$ID: Id in the symbol table ST.

   • Node$NT: Is the symbol a non-terminal?

   • Node$Pos: Position in the trail.

   • Node$Depth: Depth of node.

   • Node$RDepth: Residual depth for expansion.

   • Node$subtreedepth: Depth of subtree starting here.

   • Node$Index: R index of the node in the derivation tree. Allows fast tree extraction and insertion.

See Also

Other Access Tree Parts: filterANLid(), filterANL(), treeChildren(), treeRoot()

Examples

g<-compileBNF(booleanGrammar())
a<-randomDerivationTree(g$Start, g)
b<-treeANL(a, g$ST)
c<-treeANL(a, g$ST, 10)
d<-treeANL(a, g$ST, maxdepth=10)