Proceedings of EACL '99 
Generating referring expressions with a unification grammar 
Richard Power 
Information Technology Research Institute 
University of Brighton 
Lewes Road 
Brighton BN2 4AT, UK 
Richard.Power@itri.bton.ac.uk 
Abstract 
A simple formalism is proposed to repre- 
sent the contexts in which pronouns, def- 
inite/indefinite descriptions, and ordinal 
descriptions (e.g. 'the second book') can 
be used, and the way in which these ex- 
pressions change the context. It is shown 
that referring expressions can be gener- 
ated by a unification grammar provided 
that some phrase-structure rules are spe- 
cially tailored to express entities in the 
current knowledge base. 
1 Introduction 
Nominal referring expressions are exceptionally 
sensitive to linguistic context. If a discourse men- 
tions a book, potential referring expressions in- 
clude 'it', 'a book', 'the book', 'another book', 
'the second book', along with an unlimited num- 
ber of more complex descriptions (e.g. 'the red 
book') that mention the book's properties. The 
choice among these alternatives depends on fea- 
tures of the preceding text: whether the referent 
has been mentioned before; whether it is currently 
a focus of attention; whether different referents of 
the same type (e.g. other books) have been in- 
troduced as well. Taking account of such factors 
poses a tricky problem for Natural Language Gen- 
eration (NLG), especially in applications in which 
efficiency (i.e. fast generation of texts) is a prior- 
ity. 
This paper proposes a method that allows effi- 
cient generation of referring expressions, through 
a unification grammar, at the cost of some ini- 
tial effort in tailoring the phrase-structure rules 
to the current knowledge base. The method was 
invented to meet the needs of applications us- 
ing 'WYSIWYM editing' (Power and Scott, 1998), 
which allow an author to control the content of an 
automatically generated text without prior train- 
ing in knowledge engineering. WYSIWYM is based 
\[ 1  oAL j 1 _f \] procedure j r ~ put-on j -\[, patch 
METHOD ~I 
REST I 
Figure 1: Network representation of an instruction 
on the idea of a 'feedback text', i.e. a text, gener- 
ated by the system, that presents the current con- 
tent of the knowledge base (however incomplete) 
along with the set of permitted operations for ex- 
tending or otherwise editing the knowledge; these 
operations are provided through pop-up menus 
which open on spans of the feedback text. Two re- 
quirements of WYSIWYM editing are that feedback 
texts should be generated fast (even a delay of a 
few seconds is irritating), and that they should ex- 
press coreference relations clearly through appro- 
priate referring expressions; reconciling these two 
requirements has motivated the work described 
here. 
The semantic network in figure 1 shows a knowl- 
edge base that might be produced using the ICON- 
OCLAST 1 system, which generates patient infor- 
mation leaflets. At present this knowledge base 
defines only the goal and first step of a procedure; 
before generating a useful output text the author 
would have to add further steps. To facilitate the 
author's task, the program generates the following 
feedback text, including the 'anchor' Further steps 
which provides options for extending the proce- 
dure. 
IICONOCLAST is supported by the Engineering and 
Physical Sciences Research Council (EPSRC) Grant 
L77102. 
Proceedings of EACL '99 
To put on a patch: 
1. Remove the patch from the box. 
Further steps. 
The program can also produce an 'output text' 
in which optional unspecified material is omitted. 
Whereas the feedback text is viewed only by the 
author during editing, the output text constitutes 
the final product which will be incorporated into 
the patient information leaflet. At the stage de- 
picted by figure 1, with only one step specified, 
an output text could be generated if desired, but 
owing to the incomplete content it would read 
strangely: 
Put on a patch by removing it from the box. 
These simple texts already illustrate several ways 
in which the choice of referring expression depends 
upon context. 
• To introduce a referent into the discourse, an 
indefinite description (e.g. 'a patch') is usu- 
ally used, although a definite description may 
be preferred if the referent will already be fa- 
miliar to the reader ('the box'). 
• Subsequent mentions of the referent are made 
through a pronoun or a definite description. 
In this way~ the text distinguishes references 
to the same token from references to two to- 
kens of the same type. If the patch removed 
from the box were different from the patch 
to be put on, the second line of the feedback 
text should contain another indefinite nom- 
inal (e.g. 'Remove a second patch from the 
box'). 
• Roughly, a pronoun can be used instead of 
a definite description if there is no danger of 
ambiguity, and if no major structural bound- 
ary has been passed since the referent was 
last mentioned. We are not concerned here 
with the details of this issue (Hofmann, 1989; 
Walker et al., 1998); in the examples, we have 
treated the colon in the feedback text as a ma- 
jor structural boundary, so preferring a def- 
inite description in the feedback text and a 
pronoun in the output text. 
We concentrate here on two contextual features, 
focus and prior mentions. The problem of find- 
ing suitable identifying properties (Dale and Re- 
iter, 1995; Horacek, 1997) will not be addressed 
here, although as will be shown our approach 
could incorporate this work. 
2 Representing linguistic context 
For any referring expression (e.g. 'a patch') one 
can define two relevant contextual states: first, the 
context in which the expression may be used; sec- 
ondly, the context that results from its use. These 
will be called the 'initial' and 'final' contexts. In 
the case of 'a patch', they can be informally de- 
fined as follows. 
Initial context: The patch is not in focus, it 
has not been mentioned before, and no other 
patch has been mentioned. 
Final context: The patch is in focus, it has been 
mentioned, and no other patch has been men- 
tioned. 
The aim of this section is to model the initial 
and final contexts formally, considering not just 
indefinite descriptions but the full range of nom- 
inals mentioned earlier (including pronouns, def- 
inite descriptions and ordinal descriptions). For 
this purpose we will discuss an example that in- 
cludes at least one nominal of each kind. 
To put on a patch: 
1. Take a sachet. 
2. Remove the patch from a second sachet. 
3. Position the patch and press it firmly. 
The strange second step suggests that the author 
has made a mistake during knowledge editing, in- 
troducing a second sachet instead of re-using the 
sachet entity introduced in step 1. An important 
objective of the WYSIWYM feedback text is to ex- 
pose such errors clearly. Because of this editing 
mistake, the passage mentions three objects: one 
patch, and two sachets. The patch is unique, the 
only object in the discourse satisfying the descrip- 
tion 'patch'. The sachets, instead, are distractors 
-- i.e., distinct objects answering to the same de- 
scription. 
As a first approximation, the contextual state 
can be formalized by two vectors which will be 
called the 'focus vector' and the 'mention vector'. 
Each vector should contain one element for each 
discourse referent that might be expressed by a 
nominal referring expression, so that in the exam- 
ple the vectors will be three elements long. The 
order of elements in the vector is irrelevant pro- 
vided that it is observed consistently: it will be 
assumed arbitrarily that it is SA, SB, p, where SA 
and sB denote the two sachets and p denotes the 
patch. Note in particular that the order of SA and 
sB in the vector is independent from their order 
of introduction in the text. 
The values in the focus vector are boolean: 1 if 
the referent is in focus, 0 if it is not. We simplify 
10 
Proceedings of EACL '99 
3 Incorporating context into the 
grammar 
A requirement on all WYSIWYM systems has been 
fast response. Every time that the author selects 
an editing operation on the feedback text, the 
knowledge base is updated and a new feedback 
text is generated. Any tangible delay in present- 
ing the updated feedback text is irritating. 
In pursuit of efficiency, ICONOCLAST employs 
a top-down generator coupled with a unification 
grammar. The grammar adheres strictly to Oc- 
cain's razor: features or rules are admitted only 
if they contribute to generating the desired texts. 
ICONOCLAST is implemented in ProFIT (Erbach, 
1995), so that feature structures are represented 
by Prolog terms and can be unified efficiently 
through Prolog term unification. 
How can linguistic context be fitted into such a 
scheme? Ideally we would like to incorporate con- 
text into the phrase-structure rules, so that for 
example a rule introducing a pronoun would be 
applied only if the referent to be expressed had 
a value of 1 in the focus vector. Unfortunately 
such a rule could not be formulated in general 
terms: both its semantic features and its focus 
and mention vectors would depend on particular 
properties of the current knowledge base. How- 
ever, nothing prevents us from constructing 'be- 
spoke' rules, tailored to the current state of the 
knowledge base, every time that it is updated. At 
first sight this might seem a ridiculous waste of 
time -- one would have to envisage beforehand 
all the ways in which every referent might be ex- 
pressed -- but in compensation the search phase 
of generation can proceed much faster, since all 
calculations relating to linguistic context have al- 
ready been performed, and there is no danger that 
they might be duplicated. 
Returning to the example in the previous sec- 
tion, let us work out the bespoke phrase-structure 
rules that should be added to the grammar so that 
it can refer to SA, SB and p. At this stage we do 
not know the exact contexts in which these ref- 
erents will be introduced; these will depend on 
text-planning decisions during generation. Never- 
theless, some valid generalizations can be made in 
advance by examining the content to be expressed: 
• p will be mentioned several times, so we might 
need pronouns, definite descriptions, and in- 
definite descriptions. However, since p has no 
distractors, no rule introducing ordinals will 
be necessary. 
• SA and SB are mentioned only once each, so 
definite descriptions and pronouns are unnec- 
essary. However, since they are distractors, 
indefinite descriptions with ordinals should 
be provided. 
Here is a phrase-structure rule generating indef- 
inite descriptions for SA (either 'a sachet' or 'a 
second sachet'). The rule is presented in sim- 
plified ProFIT notation, where F!V means that 
V is the value of feature F; as usual in Prolog, 
symbols starting with a lower-case letter are con- 
stants, while symbols starting with an upper-case 
letter are variables. Focus and mention vectors 
are represented by lists, while the phrase-structure 
constituents are listed under the cset feature. It 
will be seen that the rule does not rely entirely 
on unification, because it includes a statement ex- 
pressing Df as a function of Di, but it will shown 
later how this blemish can be removed. 
rule (referent ! sA & 
properties ! \[type :patch\] & 
syntax !np & 
initial! (focus! \[0 .... \] & 
mention! \[O/Di, N/Di, M\]) & 
final! (focus! \[i, O, O\] & 
mention! \[Dr/Dr, N/Dr, M\]) 
cset ! \[properties ! \[type : indef\] & 
syntax ! det, 
properties ! \[order: (Dr/Dr), 
type :patch\] 
syntax ! nbar\] ) : - 
Df is Di + I. 
The syntactic form of this rule is NP --+ DET + 
NBAR, where the NBAR can be expanded by 
NBAR --+ NOUN to yield 'a sachet', and by 
NBAR --+ ORDINAL + NBAR to yield 'a sec- 
ond sachet'. Which of these rules is applied will 
depend on the order property, which reproduces 
the final mention ratio -- a ratio of 1/1 activates 
the former rule, while any other ratio activates the 
latter. 
The above statement of the rule simplifies by 
specifying contextual features only on the parent. 
In this particular case the omission is harmless: 
since the sachets have no properties (apart from 
type), the NBAR of the indefinite description 
cannot include any expression referring to other 
objects (e.g. 'a sachet containing a patch'). In 
general, however, subordinated nominals might 
modify the context, so the final context of the 
parent should depend partly on the final context 
of its last constituent. This requires two things: 
first, the context must be 'threaded' through the 
constituents; secondly, the relationship between 
the final contexts of the parent and the last con- 
stituent must be defined. 
11 
Proceedings of EACL '99 
by assuming (a) that focus is all-or-none rather 
than a matter of degree, and (b) that at most one 
referent can be in focus at any time. Actually the 
ICONOCLAST system refines the second limitation 
by grouping the referents according to whether 
they are competitors for the same pronoun: peo- 
ple compete for 'he/she' (or 'him/her' etc.), and 
physical objects for 'it'. With this refinement, the 
relevant constraint is that at most one referent in 
each group can be in focus at any time. However, 
in the example, the three referents are all physical 
objects -- competitors for 'it' -- so this compli- 
cation can be ignored. 
The behaviour of the focus vector is straight- 
forward. At the beginning of the text no referent 
has been mentioned, so all focus values are zero: 
8A 8B p 
FOCUS 0 0 0 
Whenever an object is mentioned, it comes into 
focus and its rivals go out of focus. As a result, 
the phrase 'the patch' in the final step switches 
the focus vector to the foUowing: 
8A 8B p 
FOCUS 0 0 1 
With p now in focus, the pronoun 'it' can be em- 
ployed to refer to p in the final clause. 
The mention vector is more complex. Each 
value is a ratio N/D, where N is the order of intro- 
duction of the referent relative to its distractors, 
and D is the number of members of the distractor 
group introduced so far. If the referent has not 
yet been mentioned, N = 0; if no members of the 
distractor group have yet been mentioned, D = 0. 
Initially all mention ratios are set to 0/0; at the 
end of step 1 in the example the state of the men- 
tion vector will be as follows (assuming that the 
first-mentioned sachet is SA): 
SA SB p 
MENTION 1/1 0/1 1/1 
Consequently, when SB is introduced during the 
second step, its initial mention ratio is 0/1, mean- 
ing that while sB has not yet been mentioned, one 
of its distractors has got in first: On the basis of 
this information the generator should produce an 
indefinite description including the ordinal 'sec- 
ond' (or perhaps the determiner 'another'). By 
the end of step 2 all three objects have been in- 
troduced, so the mention vector reaches its final 
state: 
SA SB p 
MENTION 1/2 2/2 1/1 
Note that the two mentions of the patch in step 
3 have no effect on the mention vector: its pur- 
pose is to record the order of introduction of a 
referent in relation to its distractors, not the num- 
ber of times that a referent has been mentioned. 
When choosing a referring expression it is rele- 
vant whether a referent has been mentioned (as 
signalled by its N value in the mention ratio), but 
the precise number of mentions is of no signifi- 
cance. 
It has been shown that the focus and mention 
vectors allow us to represent the initial and final 
contexts of the referring expressions in the exam- 
ple. (Of course we have oversimplified, especially 
in our treatment of focus.) We now show that 
by abstracting from the particular contexts in the 
example, it is possible to describe the initial and 
final contexts of these referring expressions in all 
texts expressing the same content. This is done 
by using variables to represent the values of any 
contextual features that do not interact with the 
referring expression under consideration. For in- 
stance, the generalized initial and final contexts of 
'a patch' are 
Initial context Final context 
p 'a patch' SA SB p SA SB p 
FOCUS FA FB 0 0 0 1 
MENTION MA Ms 0/0 MA MB 1/1 
where FA, MA, etc. are variables. Among other 
things this rule implies that 'a patch' may be used 
whatever the current focus values for SA and SB, 
but that after "a patch' these objects must be out 
of focus. Here are the corresponding rules for the 
other referring expressions in the example. 
p 'the patch' 
FOCUS 
MENTION 
p 'it' 
FOCUS 
MENTION 
SA ~a sachet' 
FOCUS 
MENTION 
SB 'a second 
sachet' 
FOCUS 
MENTION 
Initial context Final context 
8A 8B p 8A 8B p 
FA FB O 0 0 1 
MA MB 1/1 MA MB 1/1 
Initial context Final context 
SA SB p SA SB p 
0 0 1 0 0 1 
MA MB M MA MB M 
Initial context Final context 
SA SB p 8A SB p 
0 0 F 1 0 0 
0/0 0/0 M 1/1 0/1 M 
Initial context Final context 
8A 8B p SA SB p 
FA 0 F 0 1 0 
1/1 0/1 M 1/2 2/2 M 
Note that each rule is specific to a referent. For 
instance, the rule given for 'a sachet' is specific 
to SA; a slightly different rule would be needed to 
describe the contexts in which 'a sachet' can be 
employed to refer to SB. 
12 
Proceedings of EACL '99 
The procedure for threading contextual features 
is straightforward. Suppose the rule has the form 
u0 -+ ui + u2... + uN, and that the initial and final 
contexts of any unit u are I(u) and F(u). In all 
cases, the initial context of the parent should be 
unified with the initial context of the first daugh- 
ter, so that I(uo) = I(ui). The relationship be- 
tween I(ui) and F(ut) will depend upon the rule 
that expands the first daughter, but the final con- 
text of any daughter should always be unified with 
the initial context of the next daughter, so that for 
example F(ut) = I(u2). Moreover, for any rule 
that does not generate a referring expression, the 
final context of the last daughter can be unified 
with that of the parent, so that F(ug) = f(uo). 
For referring expressions, instead, F(uo) usually 
differs from F(ug), because the end of a referring 
expression is the point where the linguistic context 
may be changed. 
Thus to take account of subordinated referring 
expressions, a rule must specify the relationship 
between three contexts: I(uo), F(uiv), and F(uo). 
A rule capable of expressing SA by 'a sachet con- 
talning a patch' should represent these contexts 
as follows: 
I(uo) sa sB p 
FOCUS 0 ...... 
MENTION O/Di N/Di ... 
F(uN) sA sB p 
FOCUS ...... F 
MENTION O/Di N/Di M 
F(Uo) SA SB p 
FOCUS 1 0 0 
MENTION Dr~Dr N/Df M 
where D/= Di + 1. 
Finally we return, as promised, to the problem 
of updating mention ratios by unification, without 
resorting to statements like Df is Di + 1. This 
can be done by replacing numbers with lists of the 
appropriate length, so that for example the ratio 
0/2 is represented by the term 
\[\] / \[_, _\] 
With this convention, the relationship between 
the mention ratios of F(UN) and F(uo) can be 
stated without an accompanying numerical con- 
straint: 
8A 8S P 
F(uN) \[\]/D N/D M 
F(uo) \[-I D\]/\[_ I D\] N/I_ I D\] M 
4 Conclusion 
Two ideas have been suggested: 
The linguistic context relevant to choosing 
nominal referring expressions can be formal- 
ized, in part, by vectors giving focus values 
and mention ratios for all potential referents. 
These features can be threaded through the 
text structure during generation by assigning 
initial and final contexts to each textual unit. 
• Since generation requires search through a 
space of possible structures, there is a dan- 
ger that expensive computations of linguis- 
tic context will be repeated many times. 
This can be avoided by composing 'bespoke' 
phrase-structure rules, tailored to the entities 
currently in the knowledge base, before em- 
barking on the search phase. 
Note that the first proposal can be employed in- 
dependently from the second, which is more spec- 
ulative. However, we think that the idea of using 
specially tailored phrase-structure rules deserves 
consideration. Its applications are not limited to 
the generation of referring expressions. One aim 
of the ICONOCLAST project is to generate texts 
in a variety of house styles, where a 'style' em- 
braces preferences regarding textual organization, 
wording, punctuation and layout. To cover a large 
range of styles, many patterns must be made avail- 
able to the generator, even though only a fraction 
are relevant for a particular company and a partic- 
ular knowledge base. Before commencing a search 
through this space of patterns, it is worth devoting 
some effort to refining the search space by filter- 
ing out irrelevant rules and perhaps merging rules 
that separately constrain linguistic and presenta- 
tional features. 
The efficiency of the approach suggested here 
is difficult to evaluate in general terms: it will 
depend on the nature of the alternative meth- 
ods, and also on the size of the generated text. 
For larger texts, in which entities may be men- 
tioned many times, the initial investment of effort 
in creating bespoke phrase-structure rules will ob- 
viously pay more dividends. However, before try- 
ing to evaluate this difficult trade-off, we feel the 
next step should be to ensure that the approach 
can be applied to a wider range of referring ex- 
pressions (e.g. demonstratives, plurals), and that 
it can be extended to cover a more complex treat- 
ment of focus such as centering theory (Walker et 
al., 1998). 
Although we have not addressed here the prob- 
lem of selecting appropriate properties for use in 
13 
Proceedings of EACL '99 
referential descriptions (Dale and Reiter, 1995), it 
is worth noting that since this selection depends 
on the current state of the knowledge base, it can 
also be performed before the search phase of gen- 
eration, the results of the selection algorithm be- 
ing saved in the form of additional bespoke rules. 
References 
R. Dale and E. Reiter. 1995. Computational in- 
terpretations of the gricean maxims in the gen- 
eration of referring expressions. Cognitive Sci- 
ence, 19:233-263. 
G. Erbach. 1995. Profit: Prolog with features, 
inheritance and templates. In Seventh Confer- 
ence of the European Chapter of the Association 
for Computational Linguistics, pages 180-187, 
Dublin. 
T. Hofmann. 1989. Paragraphs and anaphora. 
Journal of Pragmatics, 13:239--250. 
H. Horacek. 1997. An algorithm for generat- 
ing referential descriptions with flexible inter- 
faces. In 35th Annual Meeting of the Associa- 
tion for Computational Linguistics, pages 206- 
213, Madrid. 
R. Power and D. Scott. 1998. Multilingual au- 
thoring using feedback texts. In Proceedings of 
the 17th International Conference on Computa- 
tional Linguistics and 36th Annual Meeting of 
the Association for Computational Linguistics, 
pages 1053-1059, Montreal, Canada. 
M. Walker, A. Joshi, and E. Prince. 1998. Center- 
ing theory in discourse. Clarendon Press, Ox- 
ford. 
14 
