12.4.3 Searching Treebanks
It is often important to search through a treebank to find examples of particular grammatical phenomena, either for linguistic research or for answering analytic questions about a computational application. But neither the regular expressions used for text search nor the boolean expressions over words used for web search are a sufficient search tool. What is needed is a language that can specify constraints about nodes and links in a parse tree, so as to search for specific patterns.
Various such tree-searching languages exist in different tools. Tgrep (Pito, 1993) and TGrep2 (Rohde, 2005) are publicly-available tools for searching treebanks that use a similar language for expressing tree constraints. We’ll describe the more recent language used by TGrep2, drawing from the online manual (Rohde, 2005).
A pattern in $ \text{tgrep} $ or $ \text{TGrep2} $ consists of a specification of a node, possibly followed by links to other nodes. A node specification can then be used to return the subtree rooted at that node. For example, the pattern
NP
returns all subtrees in a corpus whose root is NP. Nodes can be specified by a name, a regular expression inside slashes, or a disjunction of these. For example, we can specify a singular or plural noun (NN or NNS) using Penn Treebank notation as either of the following:
$$ /NNS?/卍 \quad NN\mid NNS $$
A node which either is the word bush or else ends in the string tree can be expressed as:
$$ /tree/|bush $$
The power of tgrep/TGrep2 patterns is the ability to specify information about links. The operator < means immediately dominates; the following pattern thus matches an NP immediately dominating a PP
$$ \mathrm{N P}\quad<\quad\mathrm{P P} $$
The relation << is used to specify dominance; this pattern matches an NP dominating a PP:
$$ \mathrm{N P}\quad<<\mathrm{~P P} $$
This previous pattern would thus match either of the following trees:
(NP (NP (NN reinvestment))
(PP (IN of)
(NP (NNS dividends)))
NP (NP (DT the) (JJ austere) (NN company) (NN dormitory))
(VP (VBN run)
(PP (IN by) (NP (DT a) (JJ prying) (NN caretaker))))
The relation . is used to mark linear precedence. The following pattern matches an NP that immediately dominates a JJ and is immediately followed by a PP, for example matching the NP dominating the austere company dormitory in (12.11) above: $ ^{2} $
$$ \mathrm{N P}~<~\mathrm{J J}~\mathrm{~.~}\mathrm{V P} $$
Each of the relations in a tgrep/TGrep2 expression is interpreted as referring to the first or root node. Thus for example the following expression means an NP which both precedes a PP and dominates an S:
$$ \mathrm{~N P~}\quad.\quad\mathrm{P P~}<\mathrm{~S~} $$
If we wanted instead to specify that the PP dominated the S, we could use parentheses as follows:
NP . (PP < S)
Fig. 12.11 gives the major link operations for TGrep2.
| A < B | A is the parent of (immediately dominates) B. |
| --- | --- |
| A > B | A is the child of B. |
| A < N B | B is the Nth child of A (the first child is <1). |
| A > N B | A is the Nth child of B (the first child is >1). |
| A < , B | Synonymous with A <1 B. |
| A > , B | Synonymous with A >1 B. |
| A < -N B | B is the Nth-to-last child of A (the last child is <-1). |
| A > -N B | A is the Nth-to-last child of B (the last child is >-1). |
| A < - B | B is the last child of A (synonymous with A <-1 B). |
| A > - B | A is the last child of B (synonymous with A >-1 B). |
| A < ' B | B is the last child of A (also synonymous with A <-1 B). |
| A > ' B | A is the last child of B (also synonymous with A >-1 B). |
| A < : B | B is the only child of A |
| A > : B | A is the only child of B |
| A < < B | A dominates B (A is an ancestor of B). |
| A > > B | A is dominated by B (A is a descendant of B). |
| A < < , B | B is a left-most descendant of A. |
| A > > , B | A is a left-most descendant of B. |
| A < < ' B | B is a right-most descendant of A. |
| A > > ' B | A is a right-most descendant of B. |
| A < < : B | There is a single path of descent from A and B is on it. |
| A > > : B | There is a single path of descent from B and A is on it. |
| A . B | A immediately precedes B. |
| A , B | A immediately follows B. |
| A . B | A precedes B. |
| A , , B | A follows B. |
| A $ B | A is a sister of B (and A ≠ B). |
| A $ . B | A is a sister of and immediately precedes B. |
| A $ , B | A is a sister of and immediately follows B. |
| A $ . . B | A is a sister of and precedes B. |
| A $ , , B | A is a sister of and follows B. |
| Figure 12.11 Links in TGrep2, summarized from Rohde (2005). | |