Linking Syntax and Semantics
To describe an interpretation algorithm that uses the syntactic
analysis of a sentence together with grammar rules augmented by
feature information describing how the semantic analysis of a phrase
is derived from the semantic analyses of its constituents. We shall
show how this works for a simple grammar and then investigate a
few more complicated examples, including the handling of auxiliary
verbs, and prepositional phrases.|
The concepts of lambda-expression and lambda-reduction are central
to the handling of certain grammar rules.
|Reference: Chapter 9 of Allen, J.: Natural Language
Understanding, 2nd ed., Benjamin Cummings, 1995.|
common noun phrase,
- Every constituent must have an interpretation - lambda-expressions, lambda-reduction
- Example: grammar rules with semantic interpretation via features
- The var feature
- Lexicon entries with sem features
- Handling PPs and VPs with lambda-expressions
- Handling different types of PPs
who wrote the textbook we follow in the NLP section of this course, is a
professor in Computer Science at the University of Rochester in the USA.
Allen is a distinguished researcher in the NLP field, and a former editor-in-chief
of the important NLP journal Computational Linguistics. The picture is
from his home page, which is linked above.
- The interpretation algorithm is compositional.
- So we must be able to write down a meaning expression
for each phrase in a sentence: S, NP, VP, PP, N, V, ...
- What is the meaning of a VP like kissed Sue
in Jack kissed Sue ?
- The logical form for Jack kissed Sue would be:
kiss1(k1, name(j1, 'Jack'), name(s1, 'Sue'))
- Clearly there is something "missing" in
___ kissed Sue and we
need to signal this in the logical form.
- The lambda calculus provides a formalism to express such
logical forms with missing components.
- lambda(X, kiss1(k1, X, name(s1, 'Sue')))
is a predicate that takes one argument.
- The argument symbol X marks the "gap" in the VP.
- Since it is a predicate, you can apply it to an argument (such as
name(j1, 'Jack') ) as follows:
lambda(X, kiss1(k1, X, name(s1, 'Sue'))) (name(j1, 'Jack')) *
Lambda Expressions 2
- lambda(X, kiss1(k1, X, name(s1, 'Sue'))) (name(j1, 'Jack')) *
- We can use a step called lambda reduction (λ-reduction)
to simplify *.
- Let p(X) be a proposition about the variable X.
Read lambda(X, p(X))(a) as "lambda(X, p(X)) applied to a".
Lambda reduction says that
lambda(X, p(X))(a) = p(X | a)
- i.e. that to apply lambda(X, p(X))
to a you replace every occurrence† of
X in p(X) by a. (The "lambda(X, " and ")"
are also dropped.)
- Thus the expression marked * above reduces to:
kiss1(k1, name(j1, 'Jack'), name(s1, 'Sue'))
† technically, you replace every free occurrence of X in
p(X) by a. So when would an occurrence not be free?
Answer: If it was within the scope of a quantifier or another lambda
Example: λ(X, knows1(X, λ(X, likes1(X, pizza1)))) = [someone] knows [someone else] likes pizza
The X in the inner λ
is bound by its λ, and so would not be replaced if
λ-reducing the outer λ-expression.
Obviously it would be
clearer to write λ(X, knows1(X, λ(Y, likes1(Y, pizza1))))
Lambda Expressions 3
- PP modifiers can be handled similarly:
- in the store as in The man in the store or
The man is in the store has as meaning
lambda(X, at_loc(X, the<s1, store1>)).
- This can be applied to the<m1, man1> to produce
at_loc(the<m1, man1>, the<s1, store1>).
9.2 Grammar / Lexicon with Semantic Interpretation
Parse Tree with Logical Form (SEM) Features
The whole of the parse/semantic tree for this sentence (Mary sees Jack)
is shown below (equivalent to Fig. 9.1 of Allen):
Grammatical Rules with sem Features
Like Table 9.3 in Allen
|1||S(sem(?semvp(?semnp))) → NP(sem(?semnp)) VP(sem(?semvp))|
|2||VP(var(?v), sem(lambda(a2, ?semv(?v, a2)))) → V[_none](sem(?semv))|
|3||VP(var(?v), sem(lambda(a3, ?semv(?v, a3, ?semnp)))) →|
|4||NP(wh(-), var(?v), sem(pro(?v, ?sempro))) → PRO(sem(?sempro))|
|5||NP(var(?v), sem(name(?v, ?semname))) → NAME(sem(?semname))|
|6||NP(var(?v), sem(?semdet(?v, ?semcnp(?v)))) →|
|7||CNP(sem(?semn)) → N(sem(?semn))|
Head_feature(s, vp, np, cnp) = var
The var feature
- The var feature is new and stores the "discourse variable" that
corresponds to the constituent.
- var features will be useful for handling certain forms of modifiers in
the development that follows.
- They are automatically generated by the parser when
a lexical constituent is constructed for a word.
- They are passed up the tree by treating var as a
Implementing Features in Prolog
- There are several choices for implementing features in Prolog. Let's
consider a noun (N) with agr(3s). Here are three possibilities:
n(agr/3s) works - remember that Prolog doesn't try to
(or an arithmetic comparison operator) is used.
- Positional coding: with this you decide that, say, the third argument
in a term with a particular functor will always be the agr feature:
n(…, …, 3s, …)
Implementing Features in Prolog 2
- We will illustrate using the grammar rule VP → V (intransitive verb):
vp(P1, P2, vp(Verb), lambda(X, SemBody), VarV) :-
v(P1, P2, Verb, SemV, VarV),
SemBody =.. [SemV, VarV, X].
- Note 1: The built-in infix predicate
=.. (pronounced "univ") converts a list into a term,
and works like this:
?- Term =.. [likes, mary, pizza].
Term = likes(mary, pizza)
- Note 2: We are using positional coding for features in the
- the third argument is the syn feature, which is used to record
the syntactic analysis of the phrase;
- the fourth argument is the sem feature, which is used to record
the semantic analysis of the feature;
- the fifth argument is the var feature;
- (and the first two arguments,
are the start and finish positions of the phrase in the sentence,
as with the Prolog syntax rules that we met earlier.)
- the λ-expression for the semantic interpretation is
constructed just by writing it in the sem slot in
the head of the rule.
- however the SemBody has to be constructed using univ, because
it involves a term whose functor is only available as a variable
- The var slot for the
vp is filled by noting
that the var of the
vp is the same as the
var of the
v (var is a head feature
vp) so we just put
VarV in the
var slot in the head of the rule.
Implementing Features in Prolog 3
Lexical Entries with Semantic Information
Like Table 9.2 of Allen
|cry||v(sem(cry1), vform(base), subcat(none))|
|decide||v(sem(decides1), vform(base), subcat(none))|
|decide||v(sem(decides_on1), vform(base), subcat(pp:on))|
Lexical Entries with Semantic Information 2
Like Table 9.2 of Allen (continued)
|has||aux(vform(pres), agr(3s), subcat(vp:pastprt), sem(perf))|
|in||p(pform([loc, mot]), sem(at_loc1))|
Lexical Entries with Semantic Information 3
Like Table 9.2 of Allen (continued)
|on||p(pform([loc, on]), sem(on_loc1))|
|saw||v(sem(sees1), vform(past), subcat(np))|
|see||v(sem(sees1), vform(base), subcat(np), irreg_past(+), en_pastprt(+))|
|the||det(sem(the), agr([3s, 3p]))|
Handling Semantic Interpretation
The chart parser can be modified so that it handles semantic interpretation as
- When a lexical rule is instantiated for use, the var feature is set to a new
- whenever a constituent is built, the sem is simplified by performing any
lambda reductions that are possible.
Interpreting an example sentence: Jill saw the dog
- The word Jill is parsed as a name. A new discourse variable, j1, is
generated, and set as the var feature of the name.
- This constituent is used with rule 5 to build an NP. Since var is a head
feature, var j1 is passed up to the NP, and the sem is built using rule 5 to
give sem name(j1, 'Jill')
- The lexical entry for the word saw generates a V constituent with
the sem past(sees1) and a new var ev1.
- The lexical entry for the produces sem the.
Interpreting an example sentence 2
- The lexical entry for dog produces a N constituent with
sem dog1 and var d1. This in turn gives rise to a CNP constituent with
the same sem and var, via rule 7 .
- Rule 6 combines the sems the and dog1 with the var d1 to produce an NP
with the sem the(d1, dog1(d1)) and var d1.
- the(d1, dog1(d1)) is combined with the sem of the verb and its var by
rule 3 to form a VP with var ev1 and sem
lambda(X, past(sees1)(ev1, X, the(d1, dog1(d1))))
Interpreting an example sentence 3
- This is then combined with the subject NP name(j1, 'Jill') to form the
past(sees1)(ev1, name(j1, 'Jill'), the(d1, dog1(d1)))
and var ev1 (after lambda-reduction).
Completed Parse Tree for Jill saw the dog (Fig. 9.5 Allen)
9.3 Prepositional Phrases and Verb Phrases
- Auxiliary verbs use the grammar rule:
VP(sem(lambda(A1, ?semaux(?semvp(A1))))) →
AUX(subcat(?v), sem(?semaux)) VP(vform(?v), sem(?semvp))
- If the ?semaux is a modal operator like can1, and ?semvp is a
λ-expression such as
lambda(X, laughs1(e3, X)),
then according to the rule
above, the sem of the VP can laugh is
lambda(X, laughs1(e3, X)) (A1)))
Prepositional Phrases and Verb Phrases 2
- This simplifies to
lambda(A1, can1(laughs1(e3, A1)))
since lambda(X, laughs1(e3, X)) (A1) λ-reduces to laughs1(e3, A1)
- In effect the variable for the subject is lifted through the
- If there is more than one auxiliary, the other auxiliary(ies) are handled
by the same rule, recursively.
- PPs can modify an NP or a VP, or may be
subcategorized for by a head word, in which case the preposition acts more as a
flag for an argument than as an independent predicate.
|The man|| in the corner ate lunch.|
| ||PP modifies NP the man|
|The dog barked||in the alley.|
| ||PP modifies VP barked|
|She is ready to take||up the challenge.|
| ||up flags object of "take-up"|
PP Modifying an NP
- With a PP modifying an NP, the sem of the PP is a unary
predicate to be applied to the sem of the NP:
PP(sem(lambda(Y, ?semp(Y, ?semnp))) →
- Given in the corner if the sem of the in is at_loc1,
and the sem of the NP is the<c1, corner1>, then the
sem of the PP would be the unary predicate
lambda(Y, at_loc1(Y, the<c1, corner1>))
PP Modifying an NP 2
- In the context the man in the corner, we need a rule to attach
the PP to the CNP (common noun phrase) man:
CNP(sem(lambda(N1, &(?semcnp(N1), ?sempp(N1))))) →
[Here & means "and". It is used here as a prefix operator. Thus
&(happy(fido), dog(fido)) would mean "Fido is happy and Fido is a dog".
&(man1(X), in_loc1(X, the<c1, corner1>))
means "X is a man and (&) X is in the corner".
PP Modifying an NP 3
- In Prolog, this rule would be:
cnp(P1, P3, cnp(SynCNP, SynPP),
lambda(N1, &(SemCNPN1, LR_Result)),
SemCNPN1 =.. [SemCNP, N1],
cnp(P1, P2, SynCNP, SemCNP, VarCNP),
pP(P2, P3, SynPP, SemPP, VarPP),
lambda_reduce is defined by:
lambda_reduce(lambda(X, Predicate), Argument, Predicate) :-
X = Argument.
lambda_reduce(Expression, _, Expression) :-
Expression \= lambda(_, _).
PP Modifying an NP 4
- The sem of man is the unary predicate Man1, so the new
sem of man in the corner is
lambda(N1, &(man1(N1), (lambda(Y, at_loc1(Y, the<c1, corner1>)) N1)))
- As (lambda(Y, at_loc1(Y, the<c1, corner1>)) N1) simplifies to
at_loc1(N1, the<c1, corner1>) , the whole expression becomes
lambda(N1, &(man1(N1), at_loc1(N1, the<c1, corner1>)))
PP Modifying an NP 5
- Combining this with the using rule 6, we get the sem
the(m2, (lambda(N1, &(man1(N1), at_loc1(N1, the<c1, corner1>))) m2))
which simplifies to
the(m2, &(man1(m2), at_loc1(m2, the<c1, corner1>)))
PP Modifying a VP
- Consider a PP modifying a VP: e.g. cry in the corner,
as in Jill can cry in the corner.
- The relevant syntactic rule would be VP → VP PP.
- cry has logical form, i.e. sem, lambda(X, cries1(e1, X)) and
The desired sem and var for cry in the corner are
lambda(A, &(cries1(e1, A), at_loc1(e1, the<c1, corner1>))) and e1
PP Modifying a VP 2
- The appropriate semantically augmented rule is:
VP(var(?v), sem(lambda(X, &(?semvp(X), ?sempp(?v))))) →
VP(var(?v), sem(?semvp)) PP(sem(?sempp))
[NB: This VP rule will be superseded by two more specific ones soon.]
You are now in a position to do all of the exercises at
PP Modifying a VP 3
Parse tree for cry in the corner using this rule: (like Allen Fig. 9.6, corrected):
PP as a subcategorized constituent in a VP
- Consider the phrase decide on a couch
meaning, say, (a) decide to buy a couch.
- There is an ambiguity here -
this phrase could also mean (b) to make a decision while sitting on a
couch. The appropriate syntactic rule for sense (a) is
VP → V[_pp:on] PP[on]
- The desired final logical form for the VP is
lambda(S, decides_on1(d1, S, a<c1, couch1>))
with a<c1, couch1> appearing as an argument.
PP as a subcategorized constituent in a VP 2
- Subcategorized PPs can be handled by distinguishing between
"predicate" PPs and "argument" PPs using a binary feature pred
(+ for predicate, – for argument).
- A PP is a predicate in cases like "in the corner" in the previous example,
where the preposition is interpreted using the predicate at_loc1.
- A PP is an argument when its interpretation, or rather the interpretation
of its NP, appears as one of the arguments of the verb,
as a<c1, couch1> does in the λ-expression above.
|predicate: decide (while sitting) on a couch|| = pred +|
|argument: decide on (e.g. to buy) a couch|| = pred –|
Using the pred Feature in Grammar Rules
- With the pred feature available, we can have two
rules for PPs, one for each case:
PP(pred(+), sem(lambda(X, ?semp(X, ?semnp)))) → P(sem(?semp)) NP(sem(?semnp))
- interprets preposition as predicate
PP(pred(–), pform(?pf), sem(?semnp)) → P(root(?pf)) NP(sem(?semnp))
- interprets the NP in the PP as an argument of the verb
- Head feature for PP: pform
Logical Forms of pred(+) and pred(–) PPs
- The two analyses are shown below (cf. Figure 9.8 of Allen).
- The analyses use VP rules found in Grammar 9.7 in Allen -
these rules supersede the VP rule that we used previously:
VP(var(?v), sem(lambda(X1, &(?semvp(X1), ?sempp(?v))))) →
VP(sem(?semvp)) PP(pred(+), sem(?sempp))
VP(var(?v), sem(lambda(X2, ?semv(?v, X2, ?sempp))) →
V[pp:on](sem(?semvp)) PP(pred(–), pform(on), sem(?sempp))
Parse Trees for pred(+) and pred(–)
- The upper tree is
for sense (a) in which couch is an argument (pred(–)), and the lower tree
is for sense (b) in which couch is the location modifier for
|Summary: Semantic Interpretation|
The semantic interpretation algorithm is feature-driven: reading the
augmented grammar rules right to left provides a description of how
to build the SEM feature of the phrase described by the grammar
rule. When the semantic description has a gap (as with VP), the SEM
feature is a lambda-expression.
CRICOS Provider Code No. 00098G
Copyright (C) Bill Wilson, 2012, except where another source is acknowledged.