public class TreeWithAritiesAlgebra extends TreeAlgebra
f(f(a), b). Note that f occurs twice in the tree: once with arity
2 and once with arity 1. Such a tree would not be allowed as a term over
an algebra, which must be consistent with the ranked signature over the algebra,
so f can only have arity 1 or 2, but not both. Thus an ordinary TreeAlgebra
cannot represent this tree.
The TreeWithAritiesAlgebra circumvents this problem by annotating every
operation symbol in the algebra with its arity, thus separating the
one-place and the two-place f into two different symbols. The (unique)
term in this algebra that evaluates to f(f(a),b) is f_2(f_1(a_0), b_0).
Observe that each symbol has a suffix "_k", where k is the number of children
in the tree. These symbols disappear when then term is evaluated
to a tree.
Many trees that arise in practice should be represented as values of this
algebra and not the TreeAlgebra. For instance, the parse trees in the
Penn Treebank have NP nodes with one children, two children, and so on.
Thus when you write a grammar that generates PTB-style parse trees,
you'll want to use a TreeWithAritiesAlgebra instead of a
TreeAlgebra.
By default, this algebra is in permissive mode or not. In non-permissive mode,
when you try to evaluate a term like f_2(a_0), evaluation will fail
with an IllegalArgumentException, because f_2 should have
two children, but only got one. In permissive mode, such mismatches are ignored.
By default, the algebra is in permissive mode; this simplifies PTB parsing,
but has the theoretical problem that now not every term that evaluates to some
tree t is in the language of the decomposition automaton (because the latter only
accepts trees with the correct arities in the labels).
| Constructor and Description |
|---|
TreeWithAritiesAlgebra() |
| Modifier and Type | Method and Description |
|---|---|
static Tree<String> |
addArities(Tree<String> tree)
Annotates each label in the given tree with its arity.
|
TreeAutomaton |
decompose(Tree<String> value)
Computes a decomposition automaton for the given value.
|
Tree<String> |
evaluate(Tree<String> t)
Evaluates a term over the algebra's signature into an algebra object.
|
Tree<String> |
parseString(String representation)
Resolves the string representation of some element of the algebra's
domain to this element.
|
static Tree<String> |
stripArities(Tree<String> tree)
Removes arity annotations from the labels of the given tree.
|
countBrackets, getClassOfValues, precision, recall, visualizegetAllAlgebraClasses, getSignature, hasOptions, readOptions, representAsString, setOptions, writeOptionspublic Tree<String> evaluate(Tree<String> t)
Algebraevaluate in class TreeAlgebrat - a term (= tree whose nodes are labeled with algebra operation
symbols)public TreeAutomaton decompose(Tree<String> value)
Algebradecompose in class TreeAlgebrapublic Tree<String> parseString(String representation) throws ParserException
AlgebraTreeAlgebra.parseString(java.lang.String)
resolves the string "f(a,b)" into a tree with three nodes.It is the job of an algebra class to keep track of the signature of the algebra. Many algebras have a potentially infinite domain (e.g. the string algebra can be used with arbitrary alphabets), so the algebra class should keep track of the symbols that were actually used in the current run of the program. The best practice is to update the signature each time the parseString method is called. The rest of the IRTG tool code takes care to call parseString of the respective algebra to obtain objects of type E, so this ensures that the signature is always up-to-date.
parseString in class TreeAlgebraParserExceptionpublic static Tree<String> addArities(Tree<String> tree)
tree - public static Tree<String> stripArities(Tree<String> tree)
addArities(de.up.ling.tree.Tree).tree - Copyright © 2017. All rights reserved.