#!/usr/bin/env python
#
# Natural Language Toolkit: TGrep search
#
# Copyright (C) 2001-2023 NLTK Project
# Author: Will Roberts <wildwilhelm@gmail.com>
# URL: <https://www.nltk.org/>
# For license information, see LICENSE.TXT
"""
============================================
TGrep search implementation for NLTK trees
============================================
This module supports TGrep2 syntax for matching parts of NLTK Trees.
Note that many tgrep operators require the tree passed to be a
``ParentedTree``.
External links:
- `Tgrep tutorial <https://www.stanford.edu/dept/linguistics/corpora/cas-tut-tgrep.html>`_
- `Tgrep2 manual <http://tedlab.mit.edu/~dr/Tgrep2/tgrep2.pdf>`_
- `Tgrep2 source <http://tedlab.mit.edu/~dr/Tgrep2/>`_
Usage
=====
>>> from nltk.tree import ParentedTree
>>> from nltk.tgrep import tgrep_nodes, tgrep_positions
>>> tree = ParentedTree.fromstring('(S (NP (DT the) (JJ big) (NN dog)) (VP bit) (NP (DT a) (NN cat)))')
>>> list(tgrep_nodes('NN', [tree]))
[[ParentedTree('NN', ['dog']), ParentedTree('NN', ['cat'])]]
>>> list(tgrep_positions('NN', [tree]))
[[(0, 2), (2, 1)]]
>>> list(tgrep_nodes('DT', [tree]))
[[ParentedTree('DT', ['the']), ParentedTree('DT', ['a'])]]
>>> list(tgrep_nodes('DT $ JJ', [tree]))
[[ParentedTree('DT', ['the'])]]
This implementation adds syntax to select nodes based on their NLTK
tree position. This syntax is ``N`` plus a Python tuple representing
the tree position. For instance, ``N()``, ``N(0,)``, ``N(0,0)`` are
valid node selectors. Example:
>>> tree = ParentedTree.fromstring('(S (NP (DT the) (JJ big) (NN dog)) (VP bit) (NP (DT a) (NN cat)))')
>>> tree[0,0]
ParentedTree('DT', ['the'])
>>> tree[0,0].treeposition()
(0, 0)
>>> list(tgrep_nodes('N(0,0)', [tree]))
[[ParentedTree('DT', ['the'])]]
Caveats:
========
- Link modifiers: "?" and "=" are not implemented.
- Tgrep compatibility: Using "@" for "!", "{" for "<", "}" for ">" are
not implemented.
- The "=" and "~" links are not implemented.
Known Issues:
=============
- There are some issues with link relations involving leaf nodes
(which are represented as bare strings in NLTK trees). For
instance, consider the tree::
(S (A x))
The search string ``* !>> S`` should select all nodes which are not
dominated in some way by an ``S`` node (i.e., all nodes which are
not descendants of an ``S``). Clearly, in this tree, the only node
which fulfills this criterion is the top node (since it is not
dominated by anything). However, the code here will find both the
top node and the leaf node ``x``. This is because we cannot recover
the parent of the leaf, since it is stored as a bare string.
A possible workaround, when performing this kind of search, would be
to filter out all leaf nodes.
Implementation notes
====================
This implementation is (somewhat awkwardly) based on lambda functions
which are predicates on a node. A predicate is a function which is
either True or False; using a predicate function, we can identify sets
of nodes with particular properties. A predicate function, could, for
instance, return True only if a particular node has a label matching a
particular regular expression, and has a daughter node which has no
sisters. Because tgrep2 search strings can do things statefully (such
as substituting in macros, and binding nodes with node labels), the
actual predicate function is declared with three arguments::
pred = lambda n, m, l: return True # some logic here
``n``
is a node in a tree; this argument must always be given
``m``
contains a dictionary, mapping macro names onto predicate functions
``l``
is a dictionary to map node labels onto nodes in the tree
``m`` and ``l`` are declared to default to ``None``, and so need not be
specified in a call to a predicate. Predicates which call other
predicates must always pass the value of these arguments on. The
top-level predicate (constructed by ``_tgrep_exprs_action``) binds the
macro definitions to ``m`` and initialises ``l`` to an empty dictionary.
"""
import functools
import re
try:
import pyparsing
except ImportError:
print("Warning: nltk.tgrep will not work without the `pyparsing` package")
print("installed.")
import nltk.tree
[docs]class TgrepException(Exception):
"""Tgrep exception type."""
pass
[docs]def ancestors(node):
"""
Returns the list of all nodes dominating the given tree node.
This method will not work with leaf nodes, since there is no way
to recover the parent.
"""
results = []
try:
current = node.parent()
except AttributeError:
# if node is a leaf, we cannot retrieve its parent
return results
while current:
results.append(current)
current = current.parent()
return results
[docs]def unique_ancestors(node):
"""
Returns the list of all nodes dominating the given node, where
there is only a single path of descent.
"""
results = []
try:
current = node.parent()
except AttributeError:
# if node is a leaf, we cannot retrieve its parent
return results
while current and len(current) == 1:
results.append(current)
current = current.parent()
return results
def _descendants(node):
"""
Returns the list of all nodes which are descended from the given
tree node in some way.
"""
try:
treepos = node.treepositions()
except AttributeError:
return []
return [node[x] for x in treepos[1:]]
def _leftmost_descendants(node):
"""
Returns the set of all nodes descended in some way through
left branches from this node.
"""
try:
treepos = node.treepositions()
except AttributeError:
return []
return [node[x] for x in treepos[1:] if all(y == 0 for y in x)]
def _rightmost_descendants(node):
"""
Returns the set of all nodes descended in some way through
right branches from this node.
"""
try:
rightmost_leaf = max(node.treepositions())
except AttributeError:
return []
return [node[rightmost_leaf[:i]] for i in range(1, len(rightmost_leaf) + 1)]
def _istree(obj):
"""Predicate to check whether `obj` is a nltk.tree.Tree."""
return isinstance(obj, nltk.tree.Tree)
def _unique_descendants(node):
"""
Returns the list of all nodes descended from the given node, where
there is only a single path of descent.
"""
results = []
current = node
while current and _istree(current) and len(current) == 1:
current = current[0]
results.append(current)
return results
def _before(node):
"""
Returns the set of all nodes that are before the given node.
"""
try:
pos = node.treeposition()
tree = node.root()
except AttributeError:
return []
return [tree[x] for x in tree.treepositions() if x[: len(pos)] < pos[: len(x)]]
def _immediately_before(node):
"""
Returns the set of all nodes that are immediately before the given
node.
Tree node A immediately precedes node B if the last terminal
symbol (word) produced by A immediately precedes the first
terminal symbol produced by B.
"""
try:
pos = node.treeposition()
tree = node.root()
except AttributeError:
return []
# go "upwards" from pos until there is a place we can go to the left
idx = len(pos) - 1
while 0 <= idx and pos[idx] == 0:
idx -= 1
if idx < 0:
return []
pos = list(pos[: idx + 1])
pos[-1] -= 1
before = tree[pos]
return [before] + _rightmost_descendants(before)
def _after(node):
"""
Returns the set of all nodes that are after the given node.
"""
try:
pos = node.treeposition()
tree = node.root()
except AttributeError:
return []
return [tree[x] for x in tree.treepositions() if x[: len(pos)] > pos[: len(x)]]
def _immediately_after(node):
"""
Returns the set of all nodes that are immediately after the given
node.
Tree node A immediately follows node B if the first terminal
symbol (word) produced by A immediately follows the last
terminal symbol produced by B.
"""
try:
pos = node.treeposition()
tree = node.root()
current = node.parent()
except AttributeError:
return []
# go "upwards" from pos until there is a place we can go to the
# right
idx = len(pos) - 1
while 0 <= idx and pos[idx] == len(current) - 1:
idx -= 1
current = current.parent()
if idx < 0:
return []
pos = list(pos[: idx + 1])
pos[-1] += 1
after = tree[pos]
return [after] + _leftmost_descendants(after)
def _tgrep_node_literal_value(node):
"""
Gets the string value of a given parse tree node, for comparison
using the tgrep node literal predicates.
"""
return node.label() if _istree(node) else str(node)
def _tgrep_macro_use_action(_s, _l, tokens):
"""
Builds a lambda function which looks up the macro name used.
"""
assert len(tokens) == 1
assert tokens[0][0] == "@"
macro_name = tokens[0][1:]
def macro_use(n, m=None, l=None):
if m is None or macro_name not in m:
raise TgrepException(f"macro {macro_name} not defined")
return m[macro_name](n, m, l)
return macro_use
def _tgrep_node_action(_s, _l, tokens):
"""
Builds a lambda function representing a predicate on a tree node
depending on the name of its node.
"""
if tokens[0] == "'":
# strip initial apostrophe (tgrep2 print command)
tokens = tokens[1:]
if len(tokens) > 1:
# disjunctive definition of a node name
assert list(set(tokens[1::2])) == ["|"]
# recursively call self to interpret each node name definition
tokens = [_tgrep_node_action(None, None, [node]) for node in tokens[::2]]
# capture tokens and return the disjunction
return (lambda t: lambda n, m=None, l=None: any(f(n, m, l) for f in t))(tokens)
else:
if hasattr(tokens[0], "__call__"):
# this is a previously interpreted parenthetical node
# definition (lambda function)
return tokens[0]
elif tokens[0] == "*" or tokens[0] == "__":
return lambda n, m=None, l=None: True
elif tokens[0].startswith('"'):
assert tokens[0].endswith('"')
node_lit = tokens[0][1:-1].replace('\\"', '"').replace("\\\\", "\\")
return (
lambda s: lambda n, m=None, l=None: _tgrep_node_literal_value(n) == s
)(node_lit)
elif tokens[0].startswith("/"):
assert tokens[0].endswith("/")
node_lit = tokens[0][1:-1]
return (
lambda r: lambda n, m=None, l=None: r.search(
_tgrep_node_literal_value(n)
)
)(re.compile(node_lit))
elif tokens[0].startswith("i@"):
node_func = _tgrep_node_action(_s, _l, [tokens[0][2:].lower()])
return (
lambda f: lambda n, m=None, l=None: f(
_tgrep_node_literal_value(n).lower()
)
)(node_func)
else:
return (
lambda s: lambda n, m=None, l=None: _tgrep_node_literal_value(n) == s
)(tokens[0])
def _tgrep_parens_action(_s, _l, tokens):
"""
Builds a lambda function representing a predicate on a tree node
from a parenthetical notation.
"""
assert len(tokens) == 3
assert tokens[0] == "("
assert tokens[2] == ")"
return tokens[1]
def _tgrep_nltk_tree_pos_action(_s, _l, tokens):
"""
Builds a lambda function representing a predicate on a tree node
which returns true if the node is located at a specific tree
position.
"""
# recover the tuple from the parsed string
node_tree_position = tuple(int(x) for x in tokens if x.isdigit())
# capture the node's tree position
return (
lambda i: lambda n, m=None, l=None: (
hasattr(n, "treeposition") and n.treeposition() == i
)
)(node_tree_position)
def _tgrep_relation_action(_s, _l, tokens):
"""
Builds a lambda function representing a predicate on a tree node
depending on its relation to other nodes in the tree.
"""
# process negation first if needed
negated = False
if tokens[0] == "!":
negated = True
tokens = tokens[1:]
if tokens[0] == "[":
# process square-bracketed relation expressions
assert len(tokens) == 3
assert tokens[2] == "]"
retval = tokens[1]
else:
# process operator-node relation expressions
assert len(tokens) == 2
operator, predicate = tokens
# A < B A is the parent of (immediately dominates) B.
if operator == "<":
retval = lambda n, m=None, l=None: (
_istree(n) and any(predicate(x, m, l) for x in n)
)
# A > B A is the child of B.
elif operator == ">":
retval = lambda n, m=None, l=None: (
hasattr(n, "parent")
and bool(n.parent())
and predicate(n.parent(), m, l)
)
# A <, B Synonymous with A <1 B.
elif operator == "<," or operator == "<1":
retval = lambda n, m=None, l=None: (
_istree(n) and bool(list(n)) and predicate(n[0], m, l)
)
# A >, B Synonymous with A >1 B.
elif operator == ">," or operator == ">1":
retval = lambda n, m=None, l=None: (
hasattr(n, "parent")
and bool(n.parent())
and (n is n.parent()[0])
and predicate(n.parent(), m, l)
)
# A <N B B is the Nth child of A (the first child is <1).
elif operator[0] == "<" and operator[1:].isdigit():
idx = int(operator[1:])
# capture the index parameter
retval = (
lambda i: lambda n, m=None, l=None: (
_istree(n)
and bool(list(n))
and 0 <= i < len(n)
and predicate(n[i], m, l)
)
)(idx - 1)
# A >N B A is the Nth child of B (the first child is >1).
elif operator[0] == ">" and operator[1:].isdigit():
idx = int(operator[1:])
# capture the index parameter
retval = (
lambda i: lambda n, m=None, l=None: (
hasattr(n, "parent")
and bool(n.parent())
and 0 <= i < len(n.parent())
and (n is n.parent()[i])
and predicate(n.parent(), m, l)
)
)(idx - 1)
# A <' B B is the last child of A (also synonymous with A <-1 B).
# A <- B B is the last child of A (synonymous with A <-1 B).
elif operator == "<'" or operator == "<-" or operator == "<-1":
retval = lambda n, m=None, l=None: (
_istree(n) and bool(list(n)) and predicate(n[-1], m, l)
)
# A >' B A is the last child of B (also synonymous with A >-1 B).
# A >- B A is the last child of B (synonymous with A >-1 B).
elif operator == ">'" or operator == ">-" or operator == ">-1":
retval = lambda n, m=None, l=None: (
hasattr(n, "parent")
and bool(n.parent())
and (n is n.parent()[-1])
and predicate(n.parent(), m, l)
)
# A <-N B B is the N th-to-last child of A (the last child is <-1).
elif operator[:2] == "<-" and operator[2:].isdigit():
idx = -int(operator[2:])
# capture the index parameter
retval = (
lambda i: lambda n, m=None, l=None: (
_istree(n)
and bool(list(n))
and 0 <= (i + len(n)) < len(n)
and predicate(n[i + len(n)], m, l)
)
)(idx)
# A >-N B A is the N th-to-last child of B (the last child is >-1).
elif operator[:2] == ">-" and operator[2:].isdigit():
idx = -int(operator[2:])
# capture the index parameter
retval = (
lambda i: lambda n, m=None, l=None: (
hasattr(n, "parent")
and bool(n.parent())
and 0 <= (i + len(n.parent())) < len(n.parent())
and (n is n.parent()[i + len(n.parent())])
and predicate(n.parent(), m, l)
)
)(idx)
# A <: B B is the only child of A
elif operator == "<:":
retval = lambda n, m=None, l=None: (
_istree(n) and len(n) == 1 and predicate(n[0], m, l)
)
# A >: B A is the only child of B.
elif operator == ">:":
retval = lambda n, m=None, l=None: (
hasattr(n, "parent")
and bool(n.parent())
and len(n.parent()) == 1
and predicate(n.parent(), m, l)
)
# A << B A dominates B (A is an ancestor of B).
elif operator == "<<":
retval = lambda n, m=None, l=None: (
_istree(n) and any(predicate(x, m, l) for x in _descendants(n))
)
# A >> B A is dominated by B (A is a descendant of B).
elif operator == ">>":
retval = lambda n, m=None, l=None: any(
predicate(x, m, l) for x in ancestors(n)
)
# A <<, B B is a left-most descendant of A.
elif operator == "<<," or operator == "<<1":
retval = lambda n, m=None, l=None: (
_istree(n) and any(predicate(x, m, l) for x in _leftmost_descendants(n))
)
# A >>, B A is a left-most descendant of B.
elif operator == ">>,":
retval = lambda n, m=None, l=None: any(
(predicate(x, m, l) and n in _leftmost_descendants(x))
for x in ancestors(n)
)
# A <<' B B is a right-most descendant of A.
elif operator == "<<'":
retval = lambda n, m=None, l=None: (
_istree(n)
and any(predicate(x, m, l) for x in _rightmost_descendants(n))
)
# A >>' B A is a right-most descendant of B.
elif operator == ">>'":
retval = lambda n, m=None, l=None: any(
(predicate(x, m, l) and n in _rightmost_descendants(x))
for x in ancestors(n)
)
# A <<: B There is a single path of descent from A and B is on it.
elif operator == "<<:":
retval = lambda n, m=None, l=None: (
_istree(n) and any(predicate(x, m, l) for x in _unique_descendants(n))
)
# A >>: B There is a single path of descent from B and A is on it.
elif operator == ">>:":
retval = lambda n, m=None, l=None: any(
predicate(x, m, l) for x in unique_ancestors(n)
)
# A . B A immediately precedes B.
elif operator == ".":
retval = lambda n, m=None, l=None: any(
predicate(x, m, l) for x in _immediately_after(n)
)
# A , B A immediately follows B.
elif operator == ",":
retval = lambda n, m=None, l=None: any(
predicate(x, m, l) for x in _immediately_before(n)
)
# A .. B A precedes B.
elif operator == "..":
retval = lambda n, m=None, l=None: any(
predicate(x, m, l) for x in _after(n)
)
# A ,, B A follows B.
elif operator == ",,":
retval = lambda n, m=None, l=None: any(
predicate(x, m, l) for x in _before(n)
)
# A $ B A is a sister of B (and A != B).
elif operator == "$" or operator == "%":
retval = lambda n, m=None, l=None: (
hasattr(n, "parent")
and bool(n.parent())
and any(predicate(x, m, l) for x in n.parent() if x is not n)
)
# A $. B A is a sister of and immediately precedes B.
elif operator == "$." or operator == "%.":
retval = lambda n, m=None, l=None: (
hasattr(n, "right_sibling")
and bool(n.right_sibling())
and predicate(n.right_sibling(), m, l)
)
# A $, B A is a sister of and immediately follows B.
elif operator == "$," or operator == "%,":
retval = lambda n, m=None, l=None: (
hasattr(n, "left_sibling")
and bool(n.left_sibling())
and predicate(n.left_sibling(), m, l)
)
# A $.. B A is a sister of and precedes B.
elif operator == "$.." or operator == "%..":
retval = lambda n, m=None, l=None: (
hasattr(n, "parent")
and hasattr(n, "parent_index")
and bool(n.parent())
and any(predicate(x, m, l) for x in n.parent()[n.parent_index() + 1 :])
)
# A $,, B A is a sister of and follows B.
elif operator == "$,," or operator == "%,,":
retval = lambda n, m=None, l=None: (
hasattr(n, "parent")
and hasattr(n, "parent_index")
and bool(n.parent())
and any(predicate(x, m, l) for x in n.parent()[: n.parent_index()])
)
else:
raise TgrepException(f'cannot interpret tgrep operator "{operator}"')
# now return the built function
if negated:
return (lambda r: (lambda n, m=None, l=None: not r(n, m, l)))(retval)
else:
return retval
def _tgrep_conjunction_action(_s, _l, tokens, join_char="&"):
"""
Builds a lambda function representing a predicate on a tree node
from the conjunction of several other such lambda functions.
This is prototypically called for expressions like
(`tgrep_rel_conjunction`)::
< NP & < AP < VP
where tokens is a list of predicates representing the relations
(`< NP`, `< AP`, and `< VP`), possibly with the character `&`
included (as in the example here).
This is also called for expressions like (`tgrep_node_expr2`)::
NP < NN
S=s < /NP/=n : s < /VP/=v : n .. v
tokens[0] is a tgrep_expr predicate; tokens[1:] are an (optional)
list of segmented patterns (`tgrep_expr_labeled`, processed by
`_tgrep_segmented_pattern_action`).
"""
# filter out the ampersand
tokens = [x for x in tokens if x != join_char]
if len(tokens) == 1:
return tokens[0]
else:
return (
lambda ts: lambda n, m=None, l=None: all(
predicate(n, m, l) for predicate in ts
)
)(tokens)
def _tgrep_segmented_pattern_action(_s, _l, tokens):
"""
Builds a lambda function representing a segmented pattern.
Called for expressions like (`tgrep_expr_labeled`)::
=s .. =v < =n
This is a segmented pattern, a tgrep2 expression which begins with
a node label.
The problem is that for segemented_pattern_action (': =v < =s'),
the first element (in this case, =v) is specifically selected by
virtue of matching a particular node in the tree; to retrieve
the node, we need the label, not a lambda function. For node
labels inside a tgrep_node_expr, we need a lambda function which
returns true if the node visited is the same as =v.
We solve this by creating two copies of a node_label_use in the
grammar; the label use inside a tgrep_expr_labeled has a separate
parse action to the pred use inside a node_expr. See
`_tgrep_node_label_use_action` and
`_tgrep_node_label_pred_use_action`.
"""
# tokens[0] is a string containing the node label
node_label = tokens[0]
# tokens[1:] is an (optional) list of predicates which must all
# hold of the bound node
reln_preds = tokens[1:]
def pattern_segment_pred(n, m=None, l=None):
"""This predicate function ignores its node argument."""
# look up the bound node using its label
if l is None or node_label not in l:
raise TgrepException(f"node_label ={node_label} not bound in pattern")
node = l[node_label]
# match the relation predicates against the node
return all(pred(node, m, l) for pred in reln_preds)
return pattern_segment_pred
def _tgrep_node_label_use_action(_s, _l, tokens):
"""
Returns the node label used to begin a tgrep_expr_labeled. See
`_tgrep_segmented_pattern_action`.
Called for expressions like (`tgrep_node_label_use`)::
=s
when they appear as the first element of a `tgrep_expr_labeled`
expression (see `_tgrep_segmented_pattern_action`).
It returns the node label.
"""
assert len(tokens) == 1
assert tokens[0].startswith("=")
return tokens[0][1:]
def _tgrep_node_label_pred_use_action(_s, _l, tokens):
"""
Builds a lambda function representing a predicate on a tree node
which describes the use of a previously bound node label.
Called for expressions like (`tgrep_node_label_use_pred`)::
=s
when they appear inside a tgrep_node_expr (for example, inside a
relation). The predicate returns true if and only if its node
argument is identical the the node looked up in the node label
dictionary using the node's label.
"""
assert len(tokens) == 1
assert tokens[0].startswith("=")
node_label = tokens[0][1:]
def node_label_use_pred(n, m=None, l=None):
# look up the bound node using its label
if l is None or node_label not in l:
raise TgrepException(f"node_label ={node_label} not bound in pattern")
node = l[node_label]
# truth means the given node is this node
return n is node
return node_label_use_pred
def _tgrep_bind_node_label_action(_s, _l, tokens):
"""
Builds a lambda function representing a predicate on a tree node
which can optionally bind a matching node into the tgrep2 string's
label_dict.
Called for expressions like (`tgrep_node_expr2`)::
/NP/
@NP=n
"""
# tokens[0] is a tgrep_node_expr
if len(tokens) == 1:
return tokens[0]
else:
# if present, tokens[1] is the character '=', and tokens[2] is
# a tgrep_node_label, a string value containing the node label
assert len(tokens) == 3
assert tokens[1] == "="
node_pred = tokens[0]
node_label = tokens[2]
def node_label_bind_pred(n, m=None, l=None):
if node_pred(n, m, l):
# bind `n` into the dictionary `l`
if l is None:
raise TgrepException(
"cannot bind node_label {}: label_dict is None".format(
node_label
)
)
l[node_label] = n
return True
else:
return False
return node_label_bind_pred
def _tgrep_rel_disjunction_action(_s, _l, tokens):
"""
Builds a lambda function representing a predicate on a tree node
from the disjunction of several other such lambda functions.
"""
# filter out the pipe
tokens = [x for x in tokens if x != "|"]
if len(tokens) == 1:
return tokens[0]
elif len(tokens) == 2:
return (lambda a, b: lambda n, m=None, l=None: a(n, m, l) or b(n, m, l))(
tokens[0], tokens[1]
)
def _macro_defn_action(_s, _l, tokens):
"""
Builds a dictionary structure which defines the given macro.
"""
assert len(tokens) == 3
assert tokens[0] == "@"
return {tokens[1]: tokens[2]}
def _tgrep_exprs_action(_s, _l, tokens):
"""
This is the top-lebel node in a tgrep2 search string; the
predicate function it returns binds together all the state of a
tgrep2 search string.
Builds a lambda function representing a predicate on a tree node
from the disjunction of several tgrep expressions. Also handles
macro definitions and macro name binding, and node label
definitions and node label binding.
"""
if len(tokens) == 1:
return lambda n, m=None, l=None: tokens[0](n, None, {})
# filter out all the semicolons
tokens = [x for x in tokens if x != ";"]
# collect all macro definitions
macro_dict = {}
macro_defs = [tok for tok in tokens if isinstance(tok, dict)]
for macro_def in macro_defs:
macro_dict.update(macro_def)
# collect all tgrep expressions
tgrep_exprs = [tok for tok in tokens if not isinstance(tok, dict)]
# create a new scope for the node label dictionary
def top_level_pred(n, m=macro_dict, l=None):
label_dict = {}
# bind macro definitions and OR together all tgrep_exprs
return any(predicate(n, m, label_dict) for predicate in tgrep_exprs)
return top_level_pred
def _build_tgrep_parser(set_parse_actions=True):
"""
Builds a pyparsing-based parser object for tokenizing and
interpreting tgrep search strings.
"""
tgrep_op = pyparsing.Optional("!") + pyparsing.Regex("[$%,.<>][%,.<>0-9-':]*")
tgrep_qstring = pyparsing.QuotedString(
quoteChar='"', escChar="\\", unquoteResults=False
)
tgrep_node_regex = pyparsing.QuotedString(
quoteChar="/", escChar="\\", unquoteResults=False
)
tgrep_qstring_icase = pyparsing.Regex('i@\\"(?:[^"\\n\\r\\\\]|(?:\\\\.))*\\"')
tgrep_node_regex_icase = pyparsing.Regex("i@\\/(?:[^/\\n\\r\\\\]|(?:\\\\.))*\\/")
tgrep_node_literal = pyparsing.Regex("[^][ \r\t\n;:.,&|<>()$!@%'^=]+")
tgrep_expr = pyparsing.Forward()
tgrep_relations = pyparsing.Forward()
tgrep_parens = pyparsing.Literal("(") + tgrep_expr + ")"
tgrep_nltk_tree_pos = (
pyparsing.Literal("N(")
+ pyparsing.Optional(
pyparsing.Word(pyparsing.nums)
+ ","
+ pyparsing.Optional(
pyparsing.delimitedList(pyparsing.Word(pyparsing.nums), delim=",")
+ pyparsing.Optional(",")
)
)
+ ")"
)
tgrep_node_label = pyparsing.Regex("[A-Za-z0-9]+")
tgrep_node_label_use = pyparsing.Combine("=" + tgrep_node_label)
# see _tgrep_segmented_pattern_action
tgrep_node_label_use_pred = tgrep_node_label_use.copy()
macro_name = pyparsing.Regex("[^];:.,&|<>()[$!@%'^=\r\t\n ]+")
macro_name.setWhitespaceChars("")
macro_use = pyparsing.Combine("@" + macro_name)
tgrep_node_expr = (
tgrep_node_label_use_pred
| macro_use
| tgrep_nltk_tree_pos
| tgrep_qstring_icase
| tgrep_node_regex_icase
| tgrep_qstring
| tgrep_node_regex
| "*"
| tgrep_node_literal
)
tgrep_node_expr2 = (
tgrep_node_expr
+ pyparsing.Literal("=").setWhitespaceChars("")
+ tgrep_node_label.copy().setWhitespaceChars("")
) | tgrep_node_expr
tgrep_node = tgrep_parens | (
pyparsing.Optional("'")
+ tgrep_node_expr2
+ pyparsing.ZeroOrMore("|" + tgrep_node_expr)
)
tgrep_brackets = pyparsing.Optional("!") + "[" + tgrep_relations + "]"
tgrep_relation = tgrep_brackets | (tgrep_op + tgrep_node)
tgrep_rel_conjunction = pyparsing.Forward()
tgrep_rel_conjunction << (
tgrep_relation
+ pyparsing.ZeroOrMore(pyparsing.Optional("&") + tgrep_rel_conjunction)
)
tgrep_relations << tgrep_rel_conjunction + pyparsing.ZeroOrMore(
"|" + tgrep_relations
)
tgrep_expr << tgrep_node + pyparsing.Optional(tgrep_relations)
tgrep_expr_labeled = tgrep_node_label_use + pyparsing.Optional(tgrep_relations)
tgrep_expr2 = tgrep_expr + pyparsing.ZeroOrMore(":" + tgrep_expr_labeled)
macro_defn = (
pyparsing.Literal("@") + pyparsing.White().suppress() + macro_name + tgrep_expr2
)
tgrep_exprs = (
pyparsing.Optional(macro_defn + pyparsing.ZeroOrMore(";" + macro_defn) + ";")
+ tgrep_expr2
+ pyparsing.ZeroOrMore(";" + (macro_defn | tgrep_expr2))
+ pyparsing.ZeroOrMore(";").suppress()
)
if set_parse_actions:
tgrep_node_label_use.setParseAction(_tgrep_node_label_use_action)
tgrep_node_label_use_pred.setParseAction(_tgrep_node_label_pred_use_action)
macro_use.setParseAction(_tgrep_macro_use_action)
tgrep_node.setParseAction(_tgrep_node_action)
tgrep_node_expr2.setParseAction(_tgrep_bind_node_label_action)
tgrep_parens.setParseAction(_tgrep_parens_action)
tgrep_nltk_tree_pos.setParseAction(_tgrep_nltk_tree_pos_action)
tgrep_relation.setParseAction(_tgrep_relation_action)
tgrep_rel_conjunction.setParseAction(_tgrep_conjunction_action)
tgrep_relations.setParseAction(_tgrep_rel_disjunction_action)
macro_defn.setParseAction(_macro_defn_action)
# the whole expression is also the conjunction of two
# predicates: the first node predicate, and the remaining
# relation predicates
tgrep_expr.setParseAction(_tgrep_conjunction_action)
tgrep_expr_labeled.setParseAction(_tgrep_segmented_pattern_action)
tgrep_expr2.setParseAction(
functools.partial(_tgrep_conjunction_action, join_char=":")
)
tgrep_exprs.setParseAction(_tgrep_exprs_action)
return tgrep_exprs.ignore("#" + pyparsing.restOfLine)
[docs]def tgrep_tokenize(tgrep_string):
"""
Tokenizes a TGrep search string into separate tokens.
"""
parser = _build_tgrep_parser(False)
if isinstance(tgrep_string, bytes):
tgrep_string = tgrep_string.decode()
return list(parser.parseString(tgrep_string))
[docs]def tgrep_compile(tgrep_string):
"""
Parses (and tokenizes, if necessary) a TGrep search string into a
lambda function.
"""
parser = _build_tgrep_parser(True)
if isinstance(tgrep_string, bytes):
tgrep_string = tgrep_string.decode()
return list(parser.parseString(tgrep_string, parseAll=True))[0]
[docs]def treepositions_no_leaves(tree):
"""
Returns all the tree positions in the given tree which are not
leaf nodes.
"""
treepositions = tree.treepositions()
# leaves are treeposition tuples that are not prefixes of any
# other treeposition
prefixes = set()
for pos in treepositions:
for length in range(len(pos)):
prefixes.add(pos[:length])
return [pos for pos in treepositions if pos in prefixes]
[docs]def tgrep_positions(pattern, trees, search_leaves=True):
"""
Return the tree positions in the trees which match the given pattern.
:param pattern: a tgrep search pattern
:type pattern: str or output of tgrep_compile()
:param trees: a sequence of NLTK trees (usually ParentedTrees)
:type trees: iter(ParentedTree) or iter(Tree)
:param search_leaves: whether to return matching leaf nodes
:type search_leaves: bool
:rtype: iter(tree positions)
"""
if isinstance(pattern, (bytes, str)):
pattern = tgrep_compile(pattern)
for tree in trees:
try:
if search_leaves:
positions = tree.treepositions()
else:
positions = treepositions_no_leaves(tree)
yield [position for position in positions if pattern(tree[position])]
except AttributeError:
yield []
[docs]def tgrep_nodes(pattern, trees, search_leaves=True):
"""
Return the tree nodes in the trees which match the given pattern.
:param pattern: a tgrep search pattern
:type pattern: str or output of tgrep_compile()
:param trees: a sequence of NLTK trees (usually ParentedTrees)
:type trees: iter(ParentedTree) or iter(Tree)
:param search_leaves: whether to return matching leaf nodes
:type search_leaves: bool
:rtype: iter(tree nodes)
"""
if isinstance(pattern, (bytes, str)):
pattern = tgrep_compile(pattern)
for tree in trees:
try:
if search_leaves:
positions = tree.treepositions()
else:
positions = treepositions_no_leaves(tree)
yield [tree[position] for position in positions if pattern(tree[position])]
except AttributeError:
yield []