Linking Syntax and Semantics

Aim:

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.

Keywords: CNP, common noun phrase, lambda reduction, VAR feature

Plan:

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

Interpretation Algorithm

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.

Lambda Expressions

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

We can use a step called lambda reduction to simplify *.
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"))

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

We add a SEM (semantic) feature to each lexical entry and grammatical rule to hold logical forms. E.g.

(S SEM (?semvp ?semnp)) → (NP SEM ?semnp) (VP SEM ?semvp)
Example: apply this rule to an NP with SEM (NAME m1 "Mary") and a VP with SEM (λ a (SEES1 e8 a (NAME j1 "Jack")))
The SEM feature of the S, (?semvp ?semnp), becomes
(λ a (SEES1 e8 a (NAME j1 "Jack"))) (NAME m1 "Mary")
which simplifies to
(SEES1 e8 (NAME m1 "Mary") (NAME j1 "Jack"))

Parse Tree with Logical Form (SEM) Features

The whole of the parse/semantic tree for this sentence (Mary sees Jack) is shown below (= 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))) → (V[_np] SEM ?semv) (NP SEM ?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)) → (DET SEM ?semdet) (CNP SEM ?semcnp))
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 "head feature".

Lexical Entries with Semantic Information

Table 9.2 of Allen
a (det AGR 3s SEM A)

can (det SUBCAT base SEM CAN1)

car (n SEM CAR1 AGR 3s)

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)

dog (n SEM DOG1 AGR 3s)

Table 9.2 of Allen
a	(det AGR 3s SEM A)
can	(det SUBCAT base SEM CAN1)
car	(n SEM CAR1 AGR 3s)
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)
dog	(n SEM DOG1 AGR 3s)

Lexical Entries with Semantic Information 2

fish	(n SEM FISH1 AGR 3s)
fish	(n SEM (PLUR FISH1) AGR 3p)
house	(n SEM HOUSE1 AGR 3s)
has	(aux VFORM pres AGR 3s SUBCAT pastprt SEM perf)
he	(pro SEM HE1 AGR 3s)
in	(p PFORM { LOC MOT} SEM AT-LOC1)
Jill	(name AGR 3s SEM "Jill")

Lexical Entries with Semantic Information 3

man	(n SEM MAN1 AGR 3s)
men	(n SEM (PLUR MAN1) AGR 3p)
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 +)
she	(pro SEM SHE1 AGR 3s)
the	(DET SEM THE AGR { 3s 3p} )
to	<(to AGR - VFORM inf)

Handling Semantic Interpretation

The chart parser can be modified so that it handles semantic interpretation as follows:

When a lexical rule is instantiated for use, the VAR feature is set to a new discourse variable;
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 SEM

(<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

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 lambda expression such as (lambda x (LAUGHS1 e3 x)), then according to the rule above, the SEM of the VP can laugh is

(lambda a1 (CAN1 ( (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 CAN1 operator.
If there is more than one auxiliary, a similar process analyses the other auxiliary(ies).

Prepositional Phrases

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.

Examples:

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))) → (P SEM ?semp) (NP SEM ?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)))) →
(CNP SEM ?semcnp) (PP SEM ?sempp)

[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)),
            VarCNP) :-
    SemCNPN1 =.. [SemCNP, N1],
    cnp(P1, P2, SynCNP, SemCNP, VarCNP),
    pP(P2, P3, SynPP, SemPP, VarPP),
    lambda_reduce(SemPP,N1,LR_Result).

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>), so 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 VAR e1. 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 http://www.cse.unsw.edu.au/~cs9414/Exercises/semantics.html

PP Modifying a VP 3

Parse tree for cry in the corner using this rule: (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 decides.

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, 2006, except where another source is acknowledged.

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"

predicate: decide (while sitting) on a couch	= PRED +
argument: decide on (e.g. to buy) a couch	= PRED –