P5: 전자 텍스트 부호화 및 교환에 대한 지침

Broadly speaking, graphs can be divided into two types: undirected and directed. An undirected graph is a set of nodes (or vertices) together with a set of pairs of those vertices, called arcs or edges. Each node in an arc of an undirected graph is said to be incident with that arc, and the two vertices (nodes) which make up an arc are said to be adjacent. An directed graph is like an undirected graph except that the arcs are ordered pairs of nodes. In the case of directed graphs, the term edge is not used; moreover, each arc in a directed graph is said to be adjacent from the node from which the arc emanates, and adjacent to the node to which the arc is directed. We use the element graph to encode graphs as a whole, node to encode nodes or vertices, and arc to encode arcs or edges; arcs can also be encoded by attributes on the node element. These elements have the following descriptions and attributes:

• graph 노드와 이 노드를 연결하는 호로 구성된 그래프를 부호화한다.
• node 그래프에서 (표지가 붙는 지점일 수도 있는) 노드를 부호화한다.
• arc 그래프에서 노드 사이를 연결하는 호를 부호화한다.

Before proceeding, some additional terminology may be helpful. We define a path in a graph as a sequence of nodes n1, ..., nk such that there is an arc from each ni to ni+1 in the sequence. A cyclic path, or cycle is a path leading from a particular node back to itself. A graph that contains at least one cycle is said to be cyclic; otherwise it is acyclic. We say, finally, that a graph is connected if there is a path from some node to every other node in the graph; any graph that is not connected is said to be disconnected.

Here is an example of an undirected, cyclic disconnected graph, in which the nodes are annotated with three-letter codes for airports, and the arcs connecting the nodes are represented by horizontal and vertical lines, with 90 degree bends used simply to avoid having to draw diagonal lines.

The first child element of graph may be a label to record a label for the graph; similarly, the label child of each node element records the labels of that node. The order and size attributes on the graph element record the number of nodes and number of arcs in the graph respectively; these values are optional (since they can be computed from the rest of the graph), but if they are supplied, they must be consistent with the rest of the encoding. They can thus be used to help check that the graph has been encoded and transmitted correctly. The degree attribute on the node elements record the number of arcs that are incident with that node. It is optional (because redundant), but can be used to help in validity checking: if a value is given, it must be consistent with the rest of the information in the graph. Finally, the from and to attributes on the arc elements provide pointers to the nodes connected by those arcs. Since the graph is undirected, no directionality is implied by the use of the from and to attributes; the values of these attributes could be interchanged in each arc without changing the graph.

Although in many cases the arc element is redundant (since arcs can be described using the adjacency attributes of their adjacent nodes), it has nevertheless been included in this module, in order to allow the convenient specification of identifiers, display or rendition information, and labels for each arc (using the attributes xml:id, rend, and a child label element).

Next, let us modify the preceding graph by adding directionality to the arcs. Specifically, we now think of the arcs as specifying selected routes from one airport to another, as indicated by the direction of the arrowheads in the following diagram.

• » 19.1.2 Family Trees
• 가정 | 목차

19.1.1 Transition Networks Transition Networks¶

For encoding transition networks and other kinds of directed graphs in which distinctions among types of nodes must be made, the type attribute is provided for node elements. In the following example, the initial and final nodes (or states) of the network are distinguished. It can be understood as accepting the set of strings obtained by traversing it from its initial node to its final node, and concatenating the labels.

<graph
  type="network-transition"
  xml:id="SS8"
  order="5"
  size="6">
 <label>(8)</label>
 <node
   xml:id="Q0"
   inDegree="0"
   outDegree="1"
   type="initial"/>
 <node xml:id="Q1" inDegree="2" outDegree="3"/>
 <node xml:id="Q2" inDegree="1" outDegree="1"/>
 <node xml:id="Q3" inDegree="1" outDegree="1"/>
 <node
   xml:id="Q4"
   inDegree="2"
   outDegree="0"
   type="final"/>
 <arc from="#Q0" to="#Q1">
  <label>THE</label>
 </arc>
 <arc from="#Q1" to="#Q1">
  <label>OLD</label>
 </arc>
 <arc from="#Q1" to="#Q2">
  <label>MAN</label>
 </arc>
 <arc from="#Q1" to="#Q3">
  <label>MEN</label>
 </arc>
 <arc from="#Q2" to="#Q4">
  <label>COMES</label>
 </arc>
 <arc from="#Q3" to="#Q4">
  <label>COME</label>
 </arc>
</graph>

A finite state transducer has two labels on each arc, and can be thought of as representing a mapping from one sequence of labels to the other. The following example represents a transducer for translating the English strings accepted by the network in the preceding example into French. The nodes have been annotated with numbers, for convenience.

<graph type="transducer" order="7" size="10">
 <node
   xml:id="T0"
   inDegree="0"
   outDegree="3"
   type="initial">
  <label>0</label>
 </node>
 <node xml:id="T1" inDegree="2" outDegree="1">
  <label>1</label>
 </node>
 <node xml:id="T2" inDegree="2" outDegree="2">
  <label>2</label>
 </node>
 <node xml:id="T3" inDegree="2" outDegree="2">
  <label>3</label>
 </node>
 <node xml:id="T4" inDegree="1" outDegree="1">
  <label>4</label>
 </node>
 <node xml:id="T5" inDegree="1" outDegree="1">
  <label>5</label>
 </node>
 <node
   xml:id="T6"
   inDegree="2"
   outDegree="0"
   type="final">
  <label>6</label>
 </node>
 <arc from="#T0" to="#T1">
  <label>THE</label>
  <label>L'</label>
 </arc>
 <arc from="#T0" to="#T2">
  <label>THE</label>
  <label>LE</label>
 </arc>
 <arc from="#T0" to="#T3">
  <label>THE</label>
  <label>LES</label>
 </arc>
 <arc from="#T1" to="#T4">
  <label>MAN</label>
  <label>HOMME</label>
 </arc>
 <arc from="#T2" to="#T1">
  <label>OLD</label>
  <label>VIEIL</label>
 </arc>
 <arc from="#T2" to="#T2">
  <label>OLD</label>
  <label>VIEIL</label>
 </arc>
 <arc from="#T3" to="#T3">
  <label>OLD</label>
  <label>VIEUX</label>
 </arc>
 <arc from="#T3" to="#T5">
  <label>MEN</label>
  <label>HOMMES</label>
 </arc>
 <arc from="#T4" to="#T6">
  <label>COMES</label>
  <label>VIENT</label>
 </arc>
 <arc from="#T5" to="#T6">
  <label>COME</label>
  <label>VIENNENT</label>
 </arc>
</graph>

• « 19.1.1 Transition Networks
• » 19.1.3 Historical Interpretation
• 가정 | 목차

19.1.2 Family Trees Family Trees¶

The next example provides an encoding a portion of a family tree⁷⁶ in which nodes are used to represent individuals and parents of individuals, and arcs are used to represent common parentage and descent links. Let us suppose, further, that information about individuals is contained in feature structures, which are contained in feature-structure libraries elsewhere (see 18.4 Feature Libraries and Feature-Value Libraries). We can use the value attribute on node elements to point to those feature structures. In this particular representation of the graph, nodes representing females are framed by ovals, nodes representing males are framed by boxes, and nodes representing parents are framed by diamonds.

<graph type="family_tree" order="13" size="12">
 <node
   xml:id="KATHR"
   value="http://example.com/russell-fs/tei/kr1"
   inDegree="0"
   outDegree="1">
  <label>Katherine</label>
 </node>
 <node
   xml:id="AMBER"
   value="http://example.com/russell-fs/tei/ar1"
   inDegree="0"
   outDegree="1">
  <label>Amberley</label>
 </node>
 <node xml:id="KAR" inDegree="2" outDegree="3">
  <label>K+A</label>
 </node>
 <node
   xml:id="BERTR"
   value="http://example.com/russell-fs/tei/br1"
   inDegree="1"
   outDegree="2">
  <label>Bertrand</label>
 </node>
 <node
   xml:id="PETER"
   value="http://example.com/russell-fs/tei/pr1"
   inDegree="0"
   outDegree="1">
  <label>Peter</label>
 </node>
 <node
   xml:id="DORAR"
   value="http://example.com/russell-fs/tei/dr1"
   inDegree="0"
   outDegree="1">
  <label>Dora</label>
 </node>
 <node xml:id="PBR" inDegree="2" outDegree="1">
  <label>P+B</label>
 </node>
 <node xml:id="DBR" inDegree="2" outDegree="2">
  <label>D+B</label>
 </node>
 <node
   xml:id="FRANR"
   value="http://example.com/russell-fs/tei/fr1"
   inDegree="1"
   outDegree="0">
  <label>Frank</label>
 </node>
 <node
   xml:id="RACHR"
   value="http://example.com/russell-fs/tei/rr1"
   inDegree="1"
   outDegree="0">
  <label>Rachel</label>
 </node>
 <node
   xml:id="CONRR"
   value="http://example.com/russell-fs/tei/cr1"
   inDegree="1"
   outDegree="0">
  <label>Conrad</label>
 </node>
 <node
   xml:id="KATER"
   value="http://example.com/russell-fs/tei/kr2"
   inDegree="1"
   outDegree="0">
  <label>Kate</label>
 </node>
 <node
   xml:id="JOHNR"
   value="http://example.com/russell-fs/tei/jr1"
   inDegree="1"
   outDegree="0">
  <label>John</label>
 </node>
 <arc from="#KATHR" to="#KAR">
  <label>Mo</label>
 </arc>
 <arc from="#AMBER" to="#KAR">
  <label>Fa</label>
 </arc>
 <arc from="#KAR" to="#BERTR">
  <label>So</label>
 </arc>
 <arc from="#KAR" to="#FRANR">
  <label>So</label>
 </arc>
 <arc from="#KAR" to="#RACHR">
  <label>Da</label>
 </arc>
 <arc from="#PETER" to="#PBR">
  <label>Mo</label>
 </arc>
 <arc from="#BERTR" to="#PBR">
  <label>Fa</label>
 </arc>
 <arc from="#PBR" to="#CONRR">
  <label>So</label>
 </arc>
 <arc from="#DORAR" to="#DBR">
  <label>Mo</label>
 </arc>
 <arc from="#BERTR" to="#DBR">
  <label>Fa</label>
 </arc>
 <arc from="#DBR" to="#KATER">
  <label>Da</label>
 </arc>
 <arc from="#DBR" to="#JOHNR">
  <label>So</label>
 </arc>
</graph>

bibliography 

A tree is a connected acyclic graph. That is, it is possible in a tree graph to follow a path from any vertex to any other vertex, but there are no paths that lead from any vertex to itself. A rooted tree is a directed graph based on a tree; that is, the arcs in the graph correspond to the arcs of a tree such that there is exactly one node, called the root, for which there is a path from that node to all other nodes in the graph. For our purposes, we may ignore all trees except for rooted trees, and hence we shall use the tree element for rooted trees, and the root element for its root. The nodes adjacent to a given node are called its children, and the node adjacent from a given node is called its parent. Nodes with both a parent and children are called internal nodes, for which we use the iNode element. A node with no children is tagged as a leaf. If the children of a node are ordered from left to right, then we say that that node is ordered. If all the nodes of a tree are ordered, then we say that the tree is an ordered tree. If some of the nodes of a tree are ordered and others are not, then the tree is a partially ordered tree. The ordering of nodes and trees may be specified by an attribute; we take the default ordering for trees to be ordered, that roots inherit their ordering from the trees in which they occur, and internal nodes inherit their ordering from their parents. Finally, we permit a node to be specified as following other nodes, which (when its parent is ordered) it would be assumed to precede, giving rise to crossing arcs. The elements used for the encoding of trees have the following descriptions and attributes.

• tree 수형도를 부호화하며, 이 수형도는 뿌리, 내부 노드, 단말노드, 그리고 뿌리로부터 단말 노드에 이르는 호로 구성된다.

  arity	뿌리의 자식 노드 및 수형도의 내부 노드의 최대 수를 제시한다.
  ord	(순서가 있는) 수형도가 순서가 있는지, 또는 수형도가 부분적으로 순서가 있는지를 나타낸다.
  order	수형도의 순서를 제시한다. 즉, 그 노드의 수

• root (뿌리 노드) 수형도의 뿌리 노드를 표시한다.

  value	뿌리의 값을 제시하며, 그 값은 자질 구조 또는 기타 분석적 요소이다.
  children	뿌리 노드의 자식인 요소의 확인소 목록을 제시한다.
  ord	(순서가 있는) 뿌리가 순서가 있는지의 여부를 제시한다.
  outDegree	뿌리의 정도, 즉, 그 자식의 수를 제시한다.

• iNode (중간 (또는 내부) 노드) 수형도의 중간 (또는 내부) 노드를 표시한다.

  value	중간 노드의 값을 제시하며, 그 값은 자질 구조 또는 기타 분석적 요소이다.
  children	중간 노드의 자식인 요소의 확인소 목록을 제시한다.
  parent	이 노드의 부모인 요소의 확인소를 제공한다.
  ord	(순서가 있는) 내부 노드가 순서가 있는지를 표시한다.
  follow	이 노드가 따르는 요소의 확인소를 제공한다.
  outDegree	중간 노드의 정도, 즉, 그 자식의 수를 제시한다.

• leaf 수형도의 단말 노드를 부호화한다.

  value	자질 구조 또는 기타 분석적 요소에 대한 포인터를 제공한다.
  parent	단말 노드의 부모의 확인소를 제공한다.
  follow	이 단말 노드가 따르는 요소의 확인소를 제공한다.

Here is an example of a tree. It represents the order in which the operators of addition (symbolized by +), exponentiation (symbolized by **) and division (symbolized by /) are applied in evaluating the arithmetic formula ((a**2)+(b**2))/((a+b)**2). In drawing the graph, the root is placed on the far right, and directionality is presumed to be to the left.

<tree
  n="ex1"
  arity="2"
  ord="true"
  order="12">
 <root xml:id="G-DIV1" children="#PLU1 #EXP1">
  <label>/</label>
 </root>
 <iNode xml:id="PLU1" parent="#G-DIV1" children="#EXP2 #EXP3">
  <label>+</label>
 </iNode>
 <iNode xml:id="EXP1" parent="#G-DIV1" children="#PLU2 #NUM2.3">
  <label>**</label>
 </iNode>
 <iNode xml:id="EXP2" parent="#PLU1" children="#VARA1 #NUM2.1">
  <label>**</label>
 </iNode>
 <iNode xml:id="EXP3" parent="#PLU1" children="#VARB1 #NUM2.2">
  <label>**</label>
 </iNode>
 <iNode xml:id="PLU2" parent="#EXP1" children="#VARA2 #VARB2">
  <label>+</label>
 </iNode>
 <leaf xml:id="VARA1" parent="#EXP2">
  <label>a</label>
 </leaf>
 <leaf xml:id="NUM2.1" parent="#EXP2">
  <label>2</label>
 </leaf>
 <leaf xml:id="VARB1" parent="#EXP3">
  <label>b</label>
 </leaf>
 <leaf xml:id="NUM2.2" parent="#EXP3">
  <label>2</label>
 </leaf>
 <leaf xml:id="VARA2" parent="#PLU2">
  <label>a</label>
 </leaf>
 <leaf xml:id="VARB2" parent="#PLU2">
  <label>b</label>
 </leaf>
 <leaf xml:id="NUM2.3" parent="#EXP1">
  <label>2</label>
 </leaf>
</tree>

In this encoding, the arity attribute represents the arity of the tree, which is the greatest value of the outDegree attribute for any of the nodes in the tree. If, as in this case, arity is 2, we say that the tree is a binary tree.

This encoding represents all of the following:

• ((a**2)+(b**2))/((a+b)**2)
• ((b**2)+(a**2))/((a+b)**2)
• ((a**2)+(b**2))/((b+a)**2)
• ((b**2)+(a**2))/((a+b)**2)

Linguistic phrase structure is very commonly represented by trees. Here is an example of phrase structure represented by an ordered tree with its root at the top, and a possible encoding.

<tree
  n="ex3"
  ord="true"
  arity="2"
  order="8">
 <root xml:id="GD-PP1" children="#GD-P1 #GD-NP1">
  <label>PP</label>
 </root>
 <iNode xml:id="GD-P1" parent="#GD-PP1" children="#GD-WITH1">
  <label>P</label>
 </iNode>
 <leaf xml:id="GD-WITH1" parent="#GD-P1">
  <label>with</label>
 </leaf>
 <iNode xml:id="GD-NP1" parent="#GD-PP1" children="#GD-THE1 #GD-PERI1">
  <label>NP</label>
 </iNode>
 <iNode xml:id="GD-ART1" parent="#GD-NP1" children="#GD-THE1">
  <label>Art</label>
 </iNode>
 <leaf xml:id="GD-THE1" parent="#GD-ART1">
  <label>the</label>
 </leaf>
 <iNode xml:id="GD-N1" parent="#GD-NP1" children="#GD-PERI1">
  <label>N</label>
 </iNode>
 <leaf xml:id="GD-PERI1" parent="#GD-N1">
  <label>periscope</label>
 </leaf>
</tree>

Finally, here is an example of an ordered tree, in which a particular node which ordinarily would precede another is specified as following it. In the drawing, the xxx symbol indicates that the arc from VB to PT crosses the arc from VP to PN.

<tree
  n="ex4"
  arity="2"
  order="8"
  ord="true">
 <leaf xml:id="GD-LOOK1" parent="#GD-VB2">
  <label>look</label>
 </leaf>
 <leaf xml:id="GD-THEM1" parent="#GD-PN1">
  <label>them</label>
 </leaf>
 <leaf xml:id="GD-UP1" parent="#GD-PT1">
  <label>up</label>
 </leaf>
 <iNode xml:id="GD-VB2" parent="#GD-VB1" children="#GD-LOOK1">
  <label>VB</label>
 </iNode>
 <iNode xml:id="GD-PN1" parent="#GD-VP1" children="#GD-THEM1">
  <label>PN</label>
 </iNode>
 <iNode
   xml:id="GD-PT1"
   parent="#GD-VB1"
   children="#GD-UP1"
   follow="#GD-PN1">
  <label>PT</label>
 </iNode>
 <iNode xml:id="GD-VB1" parent="#GD-VP1" children="#GD-VB2 #GD-PT1">
  <label>VB</label>
 </iNode>
 <root xml:id="GD-VP1" children="#GD-VB1 #GD-PN1">
  <label>VP</label>
 </root>
</tree>

In this section, we present an alternative to the method of representing the structure of ordered rooted trees given in section 19.2 Trees, which is based on the observation that any node of such a tree can be thought of as the root of the subtree that it dominates. Thus subtrees can be thought of as the same type as the trees they are embedded in, hence the designation eTree, for embedding tree. Whereas in a tree the relationship among the parts is indicated by the children attribute, and by the names of the elements root, iNode, and leaf, the relationship among the parts of an eTree is indicated simply by the arrangement of their content. However, we have chosen to enable encoders to distinguish the terminal elements of an eTree by means of the empty eLeaf element, though its use is not required; the eTree element can also be used to identify the terminal nodes of eTree elements. We also provide a triangle element, which can be thought of as an underspecified eTree, i.e. an eTree in which certain information has been left out. In addition, we provide a forest element, which consists of one or more tree, eTree, or triangle elements, and a <listGrp> element, which consists of one or more forest elements. The elements used for the encoding of embedding trees and the units containing them have the following descriptions and attributes.

• eTree (내포 수형도) 순서가 있고 뿌리가 있는 수형 구조를 표시하기 위해 수형도 요소에 대체안을 제시한다.

  value

  내포 수형도의 값을 제시하며, 그 값은 자질 구조 또는 기타 분석적 요소이다.

• triangle (미명시된 내포 수형도, 도출될 때 그 특성적 모양 때문에 그렇게 불린다.) 미명시된 eTree를 제시한다. 즉, 정보가 삭제된 eTree

  value

  삼각형의 값을 제시하며, 그 값은 자질 구조 또는 기타 분석적 요소의 확인소이다.

• eLeaf (내포 수형도의 단말 노드) 내포 수형도의 단말 노드를 명시적으로 제공한다. 내포 수형도는 또한 eTree 요소로 부호화될 수 있다.

  value

  내포 단말 노드의 값을 제시하며, 그 값은 자질 구조 또는 기타 분석적 요소이다.

• forest 뿌리가 있는 수형도군을 제공한다.

  type	수형도 집합의 유형을 식별한다.

• listForest provides for lists of forests.

  type	수형도군의 유형을 식별한다.

Like the root, iNode, and leaf of a tree, the eTree, triangle and eLeaf elements may also have value attributes and label children.

To illustrate the use of the eTree and eLeaf elements, here is an encoding of the second example in section 19.2 Trees, repeated here for convenience.

<eTree n="ex1">
 <label>PP</label>
 <eTree>
  <label>P</label>
  <eLeaf>
   <label>with</label>
  </eLeaf>
 </eTree>
 <eTree>
  <label>NP</label>
  <eTree>
   <label>Art</label>
   <eLeaf>
    <label>the</label>
   </eLeaf>
  </eTree>
  <eTree>
   <label>N</label>
   <eLeaf>
    <label>periscope</label>
   </eLeaf>
  </eTree>
 </eTree>
</eTree>

Next, we provide an encoding, using the triangle element, in which the internal structure of the eTree labeled NP is omitted.

<eTree n="ex2">
 <label>PP</label>
 <eTree>
  <label>P</label>
  <eLeaf>
   <label>with</label>
  </eLeaf>
 </eTree>
 <triangle>
  <label>NP</label>
  <eLeaf>
   <label>the periscope</label>
  </eLeaf>
 </triangle>
</eTree>

Ambiguity involving alternative tree structures associated with the same terminal sequence can be encoded relatively conveniently using a combination of the exclude and copyOf attributes described in sections 16.8 Alternation and 16.6 Identical Elements and Virtual Copies. In the simplest case, an eTree may be part of the content of exactly one of two different eTree elements. To mark it up, the embedded eTree may be fully specified within one of the embedding eTree elements to which it may belong, and a virtual copy, specified by the copyOf attribute, may appear on the other. In addition, each of the embedded elements in question is specified as excluding the other, using the exclude attribute. To illustrate, consider the English phrase see the vessel with the periscope, which may be considered to be structurally ambiguous, depending on whether the phrase with the periscope is a modifier of the phrase the vessel or a modifier of the phrase see the vessel. This ambiguity is indicated in the sketch of the ambiguous tree by means of the dotted-line arcs. The markup using the copyOf and exclude attributes follows the sketch.

<eTree n="ex3">
 <label>VP</label>
 <eTree>
  <label>V</label>
  <eLeaf>
   <label>see</label>
  </eLeaf>
 </eTree>
 <eTree>
  <label>NP</label>
  <eTree>
   <label>Art</label>
   <eLeaf>
    <label>the</label>
   </eLeaf>
  </eTree>
  <eTree>
   <label>N</label>
   <eLeaf>
    <label>vessel</label>
   </eLeaf>
  </eTree>
  <eTree xml:id="GD-PPA" exclude="#GD-PPB">
   <label>PP</label>
   <eTree>
    <label>P</label>
    <eLeaf>
     <label>with</label>
    </eLeaf>
   </eTree>
   <eTree>
    <label>NP</label>
    <eTree>
     <label>Art</label>
     <eLeaf>
      <label>the</label>
     </eLeaf>
    </eTree>
    <eTree>
     <label>N</label>
     <eLeaf>
      <label>periscope</label>
     </eLeaf>
    </eTree>
   </eTree>
  </eTree>
 </eTree>
 <eTree xml:id="GD-PPB" copyOf="#GD-PPA" exclude="#GD-PPA">
  <label>PP</label>
 </eTree>
</eTree>

To indicate that one of the alternatives is selected, one may specify the select attribute on the highest eTree as either #GD-PPA or #GD-PPB; see section 16.8 Alternation.

Depending on the grammar one uses to associate structures with examples like see the man with the periscope, the representations may be more complicated than this. For example, adopting a version of the X-bar theory of phrase structure originated by Jackendoff,⁷⁸ the attachment of a modifier may require the creation of an intermediate node which is not required when the attachment is not made, as shown in the following diagram. A possible encoding of this ambiguous structure immediately follows the diagram.

<eTree n="ex4">
 <label>VP</label>
 <eTree xml:id="VBARA" exclude="#VBARB">
  <label>V'</label>
  <eTree xml:id="VA">
   <label>V</label>
   <eLeaf>
    <label>see</label>
   </eLeaf>
  </eTree>
  <eTree>
   <label>NP</label>
   <eTree xml:id="SPEC1A">
    <label>Spec</label>
    <eLeaf>
     <label>the</label>
    </eLeaf>
   </eTree>
   <eTree>
    <label>N'</label>
    <eTree xml:id="NBAR2A">
     <label>N'</label>
     <eTree>
      <label>N</label>
      <eLeaf>
       <label>vessel</label>
      </eLeaf>
     </eTree>
    </eTree>
    <eTree xml:id="PPA1">
     <label>PP</label>
     <eTree>
      <label>P</label>
      <eLeaf>
       <label>with</label>
      </eLeaf>
     </eTree>
     <eTree>
      <label>NP</label>
      <eTree>
       <label>Spec</label>
       <eLeaf>
        <label>the</label>
       </eLeaf>
      </eTree>
      <eTree>
       <label>N'</label>
       <eTree>
        <label>N</label>
        <eLeaf>
         <label>periscope</label>
        </eLeaf>
       </eTree>
      </eTree>
     </eTree>
    </eTree>
   </eTree>
  </eTree>
 </eTree>
 <eTree xml:id="VBARB" exclude="#VBARA">
  <label>V'</label>
  <eTree>
   <label>V'</label>
   <eTree xml:id="VB" copyOf="#VA">
    <label>V</label>
   </eTree>
   <eTree>
    <label>NP</label>
    <eTree xml:id="SPEC1B" copyOf="#SPEC1A">
     <label>Spec</label>
    </eTree>
    <eTree xml:id="NBAR2B" copyOf="#NBAR2A">
     <label>N'</label>
    </eTree>
   </eTree>
  </eTree>
  <eTree xml:id="PPB" copyOf="#PPA1">
   <label>PP</label>
  </eTree>
 </eTree>
</eTree>

A derivation in a generative grammar is often thought of as a set of trees. To encode such a derivation, one may use the forest element, in which the trees may be marked up using the tree, the eTree, or the triangle element. The type attribute may be used to specify what kind of derivation it is. Here is an example of a two-tree forest, involving application of the ‘wh-movement’ transformation in the derivation of what you do (as in this is what you do) from the underlying you do what.⁷⁹

<forest n="ex5" type="derivation-syntactic">
 <eTree n="Stage 1" xml:id="S1SBAR">
  <label>S'</label>
  <eTree xml:id="S1COMP">
   <label>COMP</label>
   <eLeaf xml:id="S1E">
    <label>e</label>
   </eLeaf>
  </eTree>
  <eTree xml:id="S1S">
   <label>S</label>
   <eTree xml:id="S1NP1">
    <label>NP</label>
    <eLeaf>
     <label>you</label>
    </eLeaf>
   </eTree>
   <eTree xml:id="S1VP">
    <label>VP</label>
    <eTree xml:id="S1V">
     <label>V</label>
     <eLeaf>
      <label>do</label>
     </eLeaf>
    </eTree>
    <eTree xml:id="S1NP2">
     <label>NP</label>
     <eLeaf xml:id="S1WH">
      <label>what</label>
     </eLeaf>
    </eTree>
   </eTree>
  </eTree>
 </eTree>
 <eTree n="Stage 2" xml:id="S2SBAR" corresp="#S1SBAR">
  <label>S'</label>
  <eTree xml:id="S2COMP" corresp="#S1COMP">
   <label>COMP</label>
   <eTree copyOf="#S1NP2" corresp="#S1E">
    <label>NP</label>
   </eTree>
  </eTree>
  <eTree xml:id="S2S" corresp="#S1S">
   <label>S</label>
   <eTree xml:id="S2NP1" copyOf="#S1NP1">
    <label>NP</label>
   </eTree>
   <eTree xml:id="S2VP" corresp="#S1VP">
    <label>VP</label>
    <eTree xml:id="S2V" copyOf="#S1V">
     <label>V</label>
    </eTree>
    <eTree xml:id="S2NP2" corresp="#S1NP2">
     <label>NP</label>
     <eLeaf corresp="#S1WH">
      <label>t</label>
     </eLeaf>
    </eTree>
   </eTree>
  </eTree>
 </eTree>
</forest>

In this markup, we have used copyOf attributes to provide virtual copies of elements in the tree representing the second stage of the derivation that also occur in the first stage, and the corresp attribute (see section 16.4 Correspondence and Alignment) to link those elements in the second stage with corresponding elements in the first stage that are not copies of them.

If a group of forests (e.g. a full grammatical derivation including syntactic, semantic, and phonological subderivations) is to be articulated, the grouping element listForest may be used.