2.1 FTAG

A tree adjoining grammar is a tuple 〈Σ, N, I, A, S〉 with Σ a set of terminals, N a set of nonterminals, I a finite set of initial trees, A a finite set of auxiliary trees and S a distinguished nonterminal (S ∈ N). Initial trees are trees whose leaves are labelled with substitution nodes (marked with a downarrow) or terminal categories. Auxiliary trees are distinguished by a foot node (marked with a star) whose category must be the same as that of the root node.

Two tree-composition operations are used to combine trees: substitution and adjunction. Substitution inserts a tree onto a substitution node of some other tree while adjunction inserts an auxiliary tree into a tree. In an FTAG, of which an example is given in Figure 1, the tree nodes are furthermore decorated with two feature structures (called top and bottom) which are unified during derivation as follows. On substitution, the top of the substitution node is unified with the top of the root node of the tree being substituted in. On adjunction, the top of the root of the auxiliary tree is unified with the top of the node where adjunction takes place; and the bottom features of the foot node are unified with the bottom features of this node. At the end of a derivation, the top and bottom of all nodes in the derived tree are unified. FTAG feature structures are nonrecursive and consist of sets of feature/value pairs where the value is either a constant or a unification variable. Unification variables can furthermore be coreferenced with any other value occurring in the same elementary tree.

Fig. 1.

Example feature-based tree adjoining grammar (N is a unification variable, sg is a constant, and [f : v] is a feature structure with feature f and feature value v).

In an FTAG, each sentence derivation is associated with both a derived tree representing the phrase structure of the sentence and a derivation tree recording how the corresponding elementary trees were combined to form the derived tree (Figure 2). Nodes in a derivation tree are labelled with the name of a TAG elementary tree. Edges are labelled with a description of the operation used to combine the TAG trees whose names label the edge vertices.

Fig. 2.

Parse trees for ‘The man often runs’ using the grammar of Figure 1. In the derivation tree, plain lines indicate adjunction and dotted ones substitution. For simplicity, tree names are replaced with the lemmas anchoring each elementary tree. The number on the upper right of each tree name gives the Gorn address of the node onto which the tree was inserted.

2.2 FTAG with semantics

To associate semantic representations with natural language expressions, the FTAG is modified as proposed by Gardent and Kallmeyer (Reference Gardent and Kallmeyer2003). Each elementary tree is associated with a flat semantic representation. For instance, in Figure 3, the trees for mary and run are associated with the semantics l ₆ : mary(x ₆) and l ₇ : run(e ₇,x ₇), respectively. Importantly, the arguments of a semantic functor are represented by unification variables which occur both in the semantic representation of this functor and on some nodes of the associated syntactic tree. For instance, in Figure 3, the semantic index x ₇ occurring in the semantic representation of run also occurs on the subject substitution node of the associated elementary tree. The value of semantic arguments is determined by the unifications resulting from adjunction and substitution. For instance, the semantic index x ₇ in the tree for run is unified during substitution with the semantic index labelling the root node of the tree for mary. As a result, the semantics of Mary run is {l ₆ : mary(x ₆),l ₇ : run(e ₇,x ₆)}.

Fig. 3.

An FTAG augmented with a unification-based semantics. For the sake of clarity, feature structures are abbreviated, feature percolation has been simplified precluding the possibility that adjunction modifies feature values and only the semantic feature values relevant for semantic construction are indicated. C^x,l/C_x,l abbreviate a node with category C and a top/bottom feature structure including the feature-value pairs {index:x, label:l}.

The semantic representation language used (L_U) is a unification-based language which describes first-order formulae in the sense that the model of a given (L_U) formula is a set of first order formulae (Gardent and Kallmeyer Reference Gardent and Kallmeyer2003). For instance, the formula in Figure 4 describes the first-order formula

Fig. 4.

Derived tree and semantics for ‘A man often sees Mary run’.

More generally, (L_U) formulae are flat, underspecified FOL formulae. They are flat in that the recursive tree structure of a FOL formula is transformed into a conjunction of nonrecursive labelled formulae where the label of each formula is used to indicate its position in the initial tree structure. They are underspecified in that the scope of scope-bearing operators (quantifiers, modals and negation) is specified by underconstrained scoping constraints between so-called holes (written h, h_i) and labels (written l, l_i). Thus, the formulae of L_U are labelled elementary predications (l : Rⁿ(i ₁, . . ., i_n) with l a label constant, Rⁿ an n-ary relation, and i_j variables over individuals and/or labels/hole constants), scoping constraints (h ≥ l with h a hole constant and l a label constant), and conjunctions (φ, ψ with ψ and φ formulae of L_U). The models described by L_U formulae are defined by the set of possible ‘pluggings’, i.e. injections from the holes of a formula to the labels of this formula. The following example illustrates this. Suppose the sentence in (1) is assigned the L_U formula (2).

1. (1) Every dog chases a cat.

2. (2) l ₀ : ∀(x,h ₁,h ₂),h ₁ ≥ l ₁, l ₁ : D(x),h ₂ ≥ l ₂,l ₂ : Ch(x,y),l ₃ : ∃(x,h ₃,h ₄),h ₃ ≥ l ₄, l ₄ : C(y), h ₄ ≥ l ₂.

Only two pluggings are possible for this formula in (2) namely {h ₁ → l ₁, h ₂ → l ₃, h ₃ → l ₄, h ₄ → l ₂} and {h ₁ → l ₁, h ₂ → l ₂, h ₃ → l ₄, h ₄ → l ₀}. They yield the following meaning representations for (1):

1. (3)

   1. a. l ₀ : ∀(x,l ₁,l ₃),l ₁ : D(x),l ₂ : Ch(x,y),l ₃ : ∃(x,l ₄,l ₂),l ₄ : C(y)

   2. b. l ₀ : ∀(x,l ₁,l ₂),l ₁ : D(x),l ₂ : Ch(x,y),l ₃ : ∃(x,l ₄,l ₀), l ₄:C(y).

For more details on the interpretation of (L_U) and on the semantic representations it permits associating with a grammar of natural language, refer to Gardent and Kallmeyer (Reference Gardent and Kallmeyer2003). The proposal described in this paper is, however, largely independent of the specific semantics used and only requires a tree adjoining grammar that is equipped with a unification-based semantics, such as SemXTag.

2.3 SemXTAG

SemXTag is an FTAG for English whose syntactic coverage approaches that of XTAG, the FTAG developed for English by the XTAG group (The XTAG Research Group 2001). Like XTAG, it contains around 1300 elementary trees and covers auxiliaries, copula, raising and small clause constructions, topicalisation, relative clauses, infinitives, gerunds, passives, adjuncts, ditransitives and datives, ergatives, it-clefts, wh-clefts, PRO constructions, noun-noun modification, extraposition, sentential adjuncts, imperatives and resultatives. Unlike XTAG, SemXTag is augmented with a unification-based compositional semantics of the type described above, with which all of its syntactic constructs are associated.

2.4 Converting SemXTAG to FRTG

In this section, we summarise the FTAG to FRTG transformation of Schmitz and Le Roux (Reference Schmitz, Le, Gardent and Sarkar2008). We start by presenting the TAG to RTG conversion, that is, the conversion for a grammar without feature structures. We then go on to indicate how feature structures are converted. For a more precise description of this FTAG to FRTG conversion, we refer the reader to Schmitz and Le Roux (Reference Schmitz, Le, Gardent and Sarkar2008).

A regular tree grammar (Comon et al. Reference Comon, Dauchet, Gilleron, Löding, Jacquemard, Lugiez, Tison and Tommasi2007) is a grammar whose rules rewrite a nonterminal symbol as a tree whose internal nodes are each labelled with a terminal symbol and whose leaf nodes are each labelled with a terminal or nonterminal symbol.

Formally, an RTG is a 4-tuple G = (S, 𝒩, 𝒡, 𝒭) consisting of an axiom S, a finite set 𝒩 of zero-arity nonterminal symbols with S ∈ 𝒩, a set 𝒡 (disjoint with 𝒩) of terminal symbols each having a fixed arity, and a finite set 𝒭 of production rules of the form A → β, with A a nonterminal of 𝒩 and β a term over 𝒡 ∪ 𝒩. A term over some set of fixed-arity symbols M is defined recursively as a symbol of M applied to n arguments with n equal to the arity of the symbol and each of the arguments being a term over M. A set of fixed-arity symbols is also called a ranked alphabet, and the set of terms over the ranked alphabet M is written T(M).

The language described by an RTG is a regular tree language. A given RTG G = (S, 𝒩, 𝒡, 𝒭) describes the language consisting of all terms t over 𝒡 such that the axiom S can be rewritten as t via a series of rewrites licensed by the rules in 𝒭. In other words, to derive a term of the language, we start from the axiom and apply rules until we have a term containing no nonterminal symbols.

More formally, the derivation relation →_G associated to G is a relation on pairs of terms of T(𝒡 ∪ 𝒩) such that s →_G t if and only if there is a rule A → α ∈ 𝒭 such that substituting α for an instance of A in s gives t; and the language generated by G, denoted by L(G), is {s ∈ T(𝒡) | S →⁺_G s} with →⁺_G the transitive closure of →_G. The subscript G on the symbols →_G and →⁺_G can be omitted if the grammar is clear from the context.

As is well known (Vijay-Shanker, Weir and Joshi Reference Vijay-Shanker, Weir and Joshi1987; Shieber Reference Shieber2006), RTG can be used to generate the derivation trees licensed by a TAG grammar. Intuitively, the RTG representation of a TAG elementary tree is a rule that rewrites the requirement satisfied by that tree as a local tree whose root is the tree name and whose leaves are the introduced requirements. A substitution/adjunction requirement for a tree of root category X is written as X_S and X_A, respectively.

Figure 5 shows the rules of an example RTG that describes the derivation trees of the toy TAG grammar depicted in the left part of the figure. The RTG terminals ({john, runs, often, ε}) refer to the elementary trees of the TAG grammar while its nonterminals ({NP_S, S_S, NP_A, VP_A, V_A, S_A}) describe the adjunction and substitution requirements that can be introduced by an elementary tree. Further, each elementary tree t in the input TAG gives rise to an RTG rule whose left-hand side (lhs) expresses the syntactic requirement that t can satisfy and whose right-hand side (rhs) expresses the syntactic requirements it introduces. If the tree is an auxiliary tree, it can satisfy an adjunction requirement and the category labelling the lhs of the RTG rule is subscripted with A. If it is an initial tree, the lhs category of the RTG rule is subscripted with S to indicate that it can satisfy a substitution requirement. Further, each node in the elementary tree that either requires a substitution or allows for an adjunction introduces a daughter node in the rhs RTG term whose category reflects the allowed/required adjunction/substitution. To capture the fact that adjunction is optional, there are additional rules allowing any adjunction requirement to be rewritten as the symbol ε, a terminal symbol of the RTG.

Fig. 5.

Example RTG describing the derivation trees of a toy TAG.

We just saw how to map a TAG to an RTG of TAG derivations. Schmitz and Le Roux (Reference Schmitz, Le, Gardent and Sarkar2008) further extend this mapping to FTAG as follows. In the resulting FRTG, each nonterminal symbol on the left- and right-hand side of a rule is marked up with a feature structure with top and bottom attributes. For a symbol on the right-hand side, the values of those attributes are equal to the top and bottom feature structures of the corresponding TAG tree node (substitution node or adjunction site). For the symbol on the left, they are the interface of the tree to any node into which the tree is inserted. When an initial tree is inserted into a substitution node of another tree, its root node's top unifies with the substitution node's top. Thus, the interface of the initial tree is its root node's top, and this appears as the top attribute of the symbol on the left-hand side of the corresponding RTG rule. For an auxiliary tree, the interface is the top of the root node and the bottom of the foot node (cf. Section 2.1), so these appear as the top and bottom, respectively, of the left-hand side of the corresponding rule.

There will generally be co-indexed feature values in a rule. In a substitution rule such as (4), which is a translation of the ‘Mary’ tree from Figure 3, the top value of the left-hand side symbol is equal to the top feature structure of the root node of the tree, and therefore is co-indexed with the top value of the right-hand side symbol that embodies that node. In an epsilon rule such as (5), the top and bottom values on the left-hand side are co-indexed with each other to enforce the requirement that the top and bottom feature structures of each node in the derived tree must unify.

1. (4)

2. (5)

3.1 Converting SemXTAG to a DCG

In the DCG formalism, a grammar is represented as a set of Prolog definite clauses, and Prolog's query mechanism provides built-in grammar traversal. We take advantage of this by deriving a DCG from SemXTag and then using Prolog queries to generate semantic representations that are licensed by SemXTag.

Our algorithm for converting SemXTag to a DCG proceeds in two steps. We first derive an FRTG of SemXTag's derivations as described in the previous section, then convert this FRTG to a DCG. We will show that there exists a mapping from our FRTG to a DCG such that the trees in the language described by the FRTG are in a one-to-one relationship with, and can easily be reconstructed from, the derivations of the DCG. As before, we start by explaining the mapping between featureless versions of the grammars, then explain how feature structures are handled.

Any RTG can be converted to a CFG (Gécseg and Steinby Reference Gécseg, Steinby, Rosenberg and Salomaa1997), which is what motivates our use of RTG as an intermediate representation. In the case of an RTG of TAG derivations, each of whose rules has a local tree on the right-hand side, this can be done simply by flattening each right-hand side tree into a list consisting of its root node followed by its leaves. If we apply this operation, for example, to the rules of the RTG of derivations from Figure 5, the result, shown in Figure 6, forms the rule set of a CFG.

Fig. 6.

Rules of a CFG derived from an RTG of TAG derivations.

Figure 7 illustrates the mapping between the trees generated by the RTG and those generated by the CFG. Reconstructing the former from the latter is trivial. It suffices to relabel each internal node in the derivation tree with the label of the unique leaf node among its daughters, and then prune the leaf nodes. This effectively reverses the flattening of the rules' right-hand sides.

Fig. 7.

An RTGns-generated tree and corresponding CFG derivation.

Extending the RTG to CFG mapping with feature structures is straightforward. In fact, the procedure for mapping an FRTG rule to a CFG rule is exactly the same except that the CFG nonterminals are now complex nonterminal categories including a feature structure.

Now, as DCGs are essentially a superclass of feature-augmented CFGs, formulating an instance of the latter as the former is straightforward. It is primarily a matter of writing down the rules in the particular Prolog syntax of DCGs. For details on the DCG implementation we refer the reader to Gottesman (Reference Gottesman2009).

Each FRTG rule other than the epsilon rules is additionally associated with a semantic formula containing unification variables. These were carried over as is from the TAG trees to the FRTG rules, and we carry them over to the DCG rules as well.

Figures 8–10 illustrate the TAG to DCG conversion process we just sketched. Figure 8 shows a toy FTAG. For each tree, the anchor family and semantics are shown underneath it. The anchor nodeFootnote ¹ is indicated with a diamond (◇). This grammar fragment includes only two features, namely the semantic label and the index. Figure 9 shows the result of translating this fragment to an FRTG and Figure 10 shows the result of converting this FRTG to a DCG, with a minimal lexicon added. Note that all nonterminals are represented using the rule predicate. The (nonhidden) arguments of the basic rule predicateFootnote ² are rule(Category, Subscript, Top, Bottom, Semantics). Its first two arguments encode the base name and subscript (init = initial/substitution = subscript S, aux = auxiliary/adjunction = subscript A) of the nonterminal symbol. The top and bottom features are represented by the third and fourth arguments, respectively. The fifth argument is the semantics slot.

Fig. 8.

TAG fragment.

Fig. 9.

FRTG translation of TAG fragment.

Fig. 10.

DCG translation of FRTG fragment.

3.2 Querying the DCG

We now show how to run a query that will cause Prolog to traverse the DCG encoding of the SemXTag grammar so as to find a valid derivation tree and produce a semantic formula as output.

We define a Prolog predicate for querying against the DCG, as follows. Its one input argument, Cat, is the label of the root node of the derivation tree (typically s), and its one output argument, Sem, is the semantic representation associated with that tree.Footnote ³

To give the users some control over the sorts of semantic representations that they get back from a query against the DCG, we augment the DCG in such a way as to allow control over the TAG familyFootnote ⁴ of the root tree in the derivation tree, over the number and type of adjunctions in the derivation, and over the depth of substitutions. To implement control over the family is quite simple: we need merely to index the DCG rules by family and modify the gensem call accordingly. For instance, the s DCG rule from Figure 10 becomes:

We permit restrictions on adjunctions by adding an additional argument to the grammar symbols, namely a vector of nonnegative integers representing the number of nonnull adjunctions of each type that are in the derivation subtree dominated by the symbol. By ‘type’ of adjunction, we mean the category of the adjunction site. In DCG terms, a nonnull adjunction of a category X is represented as the expansion of an x/aux symbol other than as ε. So, for example, a DCG symbol associated with the vector [1,0,0,0,0], where the five dimensions of the vector correspond to the n, np, v, vp, and s categories, respectively, dominates a subtree containing exactly one n/aux symbol expanded by a nonepsilon rule, and no other aux symbol expanded by a nonepsilon rule.

To implement the functionality of the vector, we define a special predicate to handle the divvying up of a mother node's vector among the daughters. We link the vector associated with the root of the derivation to the query predicate.

Finally, we add an additional argument to the DCG rule and to the gensem call to control the traversal depth with respect to the number of substitutions applied. The overall depth of each derivation is therefore constrained both by the user-defined adjunction and substitution-depth constraints.

Our query predicate now has four input arguments and one output argument:

4.1 RTGen's base algorithm

In essence, RTGen implements a chart-based Earley algorithm for the FRTG encoding of SemXTag. Table 1 sketches the algorithm. The standard item representation is the pair [(A,d) → T_a((B ₁,d ₁), . . ., •(B_i,d _i), . . ., (B_n,d _n)), ψ]. In the first component, the dot in the production marks the point reached in the generation of the derivation tree. The nonterminal symbols (B_i,d _i) in the dotted rule are complex nonterminals from the FRTG rules (i.e. a nonterminal symbol, syntactic category and operation type, B_i and a feature structure d_i). T_a is the ranked terminal of the FRTG rule (i.e. is the elementary tree family). The second component of the item, ψ, is a flat semantic formula. In the items, we do not keep track of input string positions, as is usually done when parsing a string, but rather we keep the associated input semantic information. The algorithm starts from the initial fact, the axiom, [S′ → • S_S, ∅]. Note that in this item the nonterminal symbol S_S is the axiom in the FRTG grammar while the second component represents the empty semantics. As we are generating from an input semantics (i.e. the semantic input to the realiser), the subset of the input semantics analysed so far is empty. On the other hand, in the goal item [S′ → S_S •, φ] the dot at the end of the item production means that the whole derivation tree with root S_S has been traversed. At this point the semantics φ should be exactly the input semantics. This RTGen algorithm includes mechanisms such as sharing and packing (Gardent and Perez-Beltrachini Reference Gardent and Perez-Beltrachini2010).

Table 1.

RTGen derivation tree generation algorithm

4.2 Three ways to implement RTGen

Depending on how much linguistic information (in the form of feature constraints from the feature structures) is preserved in the FRTG rules, several RTGen configurations can be tried out, each reflecting a different division of labour between constraint solving and structure building.

• RTGen-all: all the feature structure information present in the SemXTag elementary trees is carried over to the FRTG rules.

• RTGen-level0: only the syntactic category and the semantic features are preserved by the conversion.

• RTGen-selective: uses exactly the subset of features that induce feature structure unification failures during generation. We identify this subset while running RTGen-all by (automatically) observing which features effectively block item combination.

5.1 Preserving the syntax/semantics interface

Given some input semantics, surface realisation involves building a syntactic tree whose compositional semantics is the input semantics. When generating from the derivation tree, it is therefore necessary that derivations can be coupled with the appropriate compositional semantics. For standard FTAG derivation trees, however, this is known not to be the case (Frank and Genabith Reference Frank, Genabith, Butt and King2001). Indeed, there are known cases of linguistic constructs (quantifiers, wh-questions, and raising verbs) where the standard FTAG derivation tree cannot be associated with the appropriate compositional semantics, in essence because two elementary trees that stand in a semantic relation are not in a mother–daughter relationship.Footnote ⁵ As shown by Gardent and Kallmeyer (Reference Gardent and Kallmeyer2003). and sketched in Section 2, a simple solution to this quandary is to associate a compositional semantics with FTAG derived trees using features and feature structure unification. Since furthermore, the FTAG-to-RTG conversion preserves both the semantics and the feature structure information contained in the initial FTAG, it follows that the derivation trees built by RTGen also support the appropriate semantics. This contrasts, in particular, with the approach described by Koller and Striegnitz (Reference Koller and Striegnitz2002). In that approach, similarly to the RTGen approach, surface realisation relies on an FTAG which is converted to a dependency grammar that models the contribution of each FTAG elementary tree to the derivation tree. However, since, in that approach, feature structures are not taken into account, it is unclear how the derivation trees of the known problematic cases can be assigned an appropriate semantics and, consequently, how the corresponding sentences could be generated.

5.2 Efficiency and overgeneration

Real world grammars such as XTAG or SemXTag typically make heavy use of feature structures and feature unification to restrict the number of elementary trees and appropriately model linguistic phenomena such as, for instance, verb/subject agreement or, as mentioned in the preceding section, to appropriately model the syntax/semantic interface.

Importantly, the FRTG encoding provided by Schmitz and Le Roux (Reference Schmitz, Le, Gardent and Sarkar2008) preserves the feature structure information contained in SemXTag, thereby ensuring that only sentences generated by SemXTag are produced. Moreover, as mentioned in Section 4, RTGen permits experimenting with three levels of feature information (RTGen-all, RTGen-level0 and RTGen-selective). To explore the impact of features on efficiency and overgeneration and to compare the FRTG approach with those of Koller and Striegnitz (Reference Koller and Striegnitz2002) and Gardent and Kow (Reference Gardent, Kow and Busemann2007), we ran RTGen in each of the three modes on a benchmark generated using the gensem benchmark generator described in Section 3. Table 2 presents an analysis of cases involving three modifiers. The results show that running RTGen with no feature information (other than semantic features) leads to an increased chart size; to runtimes that are higher on average than for full sentence generation, that is, realisation using the full grammar with all constraints; and to massive overgeneration (on average, 1108.06 sentence trees produced when using no features against 15.05 when using all features). This suggests that using a filtering step based only on semantic indices is a poor strategy. Using gensem, we compared RTGen with the GenI (Gardent and Kow Reference Gardent, Kow and Busemann2007) surface realiser, which uses such a filter. And indeed, we found that in terms of space, RTGen consistently outperformed GenI (cf. Gardent and Perez-Beltrachini Reference Gardent and Perez-Beltrachini2010). Similarly, the approach of Koller and Striegnitz (Reference Koller and Striegnitz2002) builds derivation trees without taking feature structures into account, thus raising the question of how the resulting massive overgeneration will impact efficiency once the postprocessing step needed to check feature information is taken into account.

Table 2.

RTGen average chart sizes and processing times on 618 test cases from a gensem -generated benchmark. Each test case has 3 modifications, distributed in various ways between adjectival and adverbial modifications and combined (in some cases) with lexical ambiguity, 10 trees for each modifier. The second column, Generation Forest (GF), is the number of derivation trees present in the generated parse forest. The third and fourth columns show the chart and unpacked chart sizes, respectively. The last column shows the runtime in seconds

5.3 Versatility

A third advantage of using FRTG as a means to describe the derivation trees of an FTAG is that, by maintaining a grammar-based approach, it permits benefiting from the tools and techniques developed for computational grammars. This contrasts with the planning-based approach of Koller and Stone (Reference Koller and Stone2007) in two ways.

First, sophisticated search strategies that were developed to handle the exponential complexity of the surface realisation problem can be drawn upon. As shown by Koller and Hoffmann (Reference Koller, Hoffmann, Brafman, Geffner, Hoffmann and Kautz2010), the planning approach fails to scale to conjunctions of five basic clauses such as The man greets the man and the man greets the man and the man greets the man and the man greets the man and the man greets the man. For such cases, all planners and planner strategies tested by Koller and Hoffmann (Reference Koller, Hoffmann, Brafman, Geffner, Hoffmann and Kautz2010) time out. The Earley-based search strategy used by RTGen, in contrast, yields the expected sentence in 2.03 seconds of CPU time. More generally, while the planning approach is an interesting way of dealing with the interactions between surface realisation and the generation of referring expressions, the grammar-based approach seems better suited to handle ‘real world’ surface realisation, i.e. the production of well-formed sentences of arbitrary length and complexity.

Second, the FRTG encoding of SemXTag can be put to work in different ways. In particular, we showed that it could be used either to produce the sentences verbalising a given meaning (surface realisation) or – by translating it to a DCG – to generate the semantic representations licensed by SemXTag and obeying a set of user defined constraints (benchmark generation). Furthermore, as Schmitz and Le Roux (Reference Schmitz, Le, Gardent and Sarkar2008) mentioned, the FRTG can also be used for parsing (going from string to meaning) provided it is extended with topological information as proposed by Kuhlmann (Reference Kuhlmann2010). In short, the FRTG approach provides a uniform resource which supports various types of processing. While the planning operators of Koller and Stone (Reference Koller and Stone2007) could in principle also be used in different ways, it remains to be seen exactly how one might adapt planning operators and planning strategies to effectively model parsing, surface realisation, and/or the construction of benchmarks.