3
$\begingroup$

Trees are usually drawn as a set of objects connected by edges.

But sometimes one sees a non-graphical, parentheses-based notation, like on the example below. What does the indentation mean in such context? How does this correspond to vertex-edge representation of a tree?

(ROOT
  (S
    (NP (NNP John))
    (VP (VBD hit)
      (NP (DT the) (NN ball)))
    (. .)))
$\endgroup$
8
$\begingroup$

In this parenthesis notation for trees, $(P\;D_1\;D_2\;D_3)$ means that $P,D_1,D_2$, and $D_3$ are nodes, and $D_1,D_2$, and $D_3$ are daughters of the parent node $P$. This is an ordered tree, so when you draw the tree, the daughter nodes $D_1,D_2,D_3$ should appear in that order from left to right.

Now suppose that $D_1$ has daughters $A_1$ and $A_2$; then the subtree with $D_1$ as root is written $(D_1\;A_1\;A_2)$ and replaces $D_1$ in the description of the subtree with root $P$: $$(P\;(D_1\;A_1\;A_2)\;D_2\;D_3)\;.$$ The subtree itself looks like this:

$$\begin{array}{ccc} &&&&P\\ &&&\diagup&\mid&\diagdown\\ &&D_1&&D_2&&D_3\\ &\diagup&\mid\\ A_1&&A_2 \end{array}$$

Your tree could be written

$$\text{(ROOT (S (NP (NNP John)) (VP (VBD hit) (NP (DT the) (NN ball))) (. .)))}\;,$$

without any indentation; the indentation is there to make it easier to see which nodes are on which level. ROOT and S are the only nodes on their respective levels, and S is one level below ROOT; NP and VP are one level below S and NNP, VBD, and NP are one level deeper yet. The indenting is not entirely consistent deeper in the tree; if it were, you’d have something like this:

(ROOT  
  (S  
    (NP  
      (NNP John))  
    (VP  
      (VBD hit)  
      (NP  
        (DT the)  
        (NN ball)))  
    (. .)))

(In all versions the $(.\;.)$ represents possible other daughters of $S$ besides $NP$ and $VP$.)

Expanding it into the usual graphical representation of a tree gives you something like this:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.