Computational
Linguistics
Copyright © 2017 Gerald
Penn. All rights reserved.
9A
9A. Mildly Context-Sensitive
Grammar Formalisms
Gerald Penn
Department of Computer Science, University of Toronto
CSC 2501 / 485
Fall 2018
Based on slides by David Smith, Dan Klein, Stephen Clark
and Eva Banik
Combinatory
Categorial Grammar
15
Combinatory Categorial Grammar (CCG)
• Categorial grammar (CG) is one of the
oldest grammar formalisms
• Combinatory Categorial Grammar now well
established and computationally well
founded (Steedman, 1996, 2000)
• Account of syntax; semantics; prodody
and information structure; automatic
parsers; generation
16
• CCG is a lexicalized grammar
• An elementary syntactic structure – for CCG a lexical
category – is assigned to each word in a sentence
walked: S\NP “give me an NP to my left and I return a
sentence”
• A small number of rules define how categories can
combine
• Rules based on the combinators from Combinatory
Logic
Combinatory Categorial Grammar (CCG)
17
CCG Lexical Categories
• Atomic categories: S , N , NP , PP , . . . (not many more)
• Complex categories are built recursively from atomic categories
and slashes, which indicate the directions of arguments
• Complex categories encode subcategorisation information
• intransitive verb: S \NP walked
• transitive verb: (S \NP )/NP respected
• ditransitive verb: ((S \NP )/NP )/NP gave
• Complex categories can encode modification
• PP nominal: (NP \NP )/NP
• PP verbal: ((S \NP )\(S \NP ))/NP
18
Simple CCG Derivationccg Grammar 21
A Simple ccg Derivation
interleukin ! 10 inhibits production
NP (S\NP)/NP NP
>
S\NP
<
S
> forward application
< backward application
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
19
Function Application Schemata
ccg Grammar 22
Function Application Rule Schemata
• Forward (>) and backward (<) application:
X /Y Y ! X (>)
Y X \Y ! X (<)
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
20
Classical Categorial Grammar
ccg Grammar 23
Classical Categorial Grammar
• ‘Classical’ Categorial Grammar only has application rules
• Classical Categorial Grammar is context free
interleukin-10 inhibits production
NP (S\NP)/NP NP
S\NP
S
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
21
Classical Categorial Grammar
ccg Grammar 24
Classical Categorial Grammar
• ‘Classical’ Categorial Grammar only has application rules
• Classical Categorial Grammar is context free
interleukin-10 inhibits production
NP V NP
VP
S
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 200922
ccg Grammar 25
Extraction out of a Relative Clause
The company which Microsoft bought
NP/N N (NP\NP)/(S/NP) NP (S\NP)/NP
NP S/(S\NP)
S/NP
NP\NP
NP
> T type-raising
> B forward composition
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
23
ccg Grammar 26
Extraction out of a Relative Clause
The company which Microsoft bought
NP/N N (NP\NP)/(S/NP) NP (S\NP)/NP
>T
NP S/(S\NP)
S/NP
NP\NP
NP
> T type-raising
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
24
ccg Grammar 27
Extraction out of a Relative Clause
The company which Microsoft bought
NP/N N (NP\NP)/(S/NP) NP (S\NP)/NP
>T
NP S/(S\NP)
>B
S/NP
NP\NP
NP
> T type-raising
> B forward composition
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
25
ccg Grammar 28
Extraction out of a Relative Clause
The company which Microsoft bought
NP/N N (NP\NP)/(S/NP) NP (S\NP)/NP
>T
S/(S\NP)
>B
S/NP
>
NP\NP
NP
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
26
ccg Grammar 29
Extraction out of a Relative Clause
The company which Microsoft bought
NP/N N (NP\NP)/(S/NP) NP (S\NP)/NP
> >T
NP S/(S\NP)
>B
S/NP
>
NP\NP
<
NP
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
27
ccg Grammar 30
Forward Composition and Type-Raising
• Forward composition (>B):
X /Y Y /Z ! X /Z (>B)
• Type-raising (T):
X ! T/(T\X ) (>T)
X ! T\(T/X ) (
S/(S\NP) S/(S\NP)
S/NP S/NP
S/NP
S
> T type-raising
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
29
ccg Grammar 32
“Non-constituents” in ccg – Right Node Raising
Google sells but Microsoft buys shares
NP (S\NP)/NP conj NP (S\NP)/NP NP
>T >T
S/(S\NP) S/(S\NP)
>B >B
S/NP S/NP
S/NP
S
> T type-raising
> B forward composition
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
30
ccg Grammar 33
“Non-constituents” in ccg – Right Node Raising
Google sells but Microsoft buys shares
NP (S\NP)/NP conj NP (S\NP)/NP NP
>T >T
S/(S\NP) S/(S\NP)
>B >B
S/NP S/NP
S/NP
S
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
31
ccg Grammar 34
“Non-constituents” in ccg – Right Node Raising
Google sells but Microsoft buys shares
NP (S\NP)/NP conj NP (S\NP)/NP NP
>T >T
S/(S\NP) S/(S\NP)
>B >B
S/NP S/NP
S/NP
>
S
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
32
ccg Grammar 35
Combinatory Categorial Grammar
• ccg is mildly context sensitive
• Natural language is provably non-context free
• Constructions in Dutch and Swiss German (Shieber, 1985) require
more than context free power for their analysis
• these have crossing dependencies (which ccg can handle)
Type 0 languages
Context sensitive languages
Context free languages
Regular languages
Mildly context sensitive languages =
natural languages (?)
Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2009
33
CCG Semantics
• Categories encode argument sequences
• Parallel syntactic combinator operations
and lambda calculus semantic operations
!”
#$%&'()*+,)-&./0()/1
! 203()*+4$’&+50.)()*6
! 7(*+%(88&.&)-&+9&/5&&)+:/0/(:/(-0’+%(:0;9(*<0/($)+0)%+:/0/(:/(-0'+
.&0:$)()*=
! >(/4+3.$909(‘(:/(-+30.:&.:?+-0)+:01+/4()*:+'(@&+ABCD+9&'(&8+/40/+/4&+EE+
0//0-4&:+/$+/4&+FE=G
! H40/+;&0):+/40/+!”#$%$&’ /4&+&)&;1+40:+)(*4/+I(:($)+*$**’&:=
! J$5&I&.?+1$<+-0)K/+/4.$5+0+'$*(-0'+0::&./($)+()/$+0+/4&$.&;+3.$I&.+
5(/4+BCD+-$)8(%&)-&=
! F$/+-'&0.+4<;0):+.&0''1+&L/.0-/+0)%+3.$-&::+'$*(-0'+:/0/&;&)/:+
:1;9$'(-0''1+0)1501=
! ,:&+/4(:+/$+%&-(%&+/4&+&L3&-/&%+(/4+3.$909(‘(:/(-+30.:&.:?+-0)+:01+/4()*:+'(@&+ABCD+9&'(&8+/40/+/4&+EE+
0//0-4&:+/$+/4&+FE=G
! H40/+;&0):+/40/+!”#$%$&’ /4&+&)&;1+40:+)(*4/+I(:($)+*$**’&:=
! J$5&I&.?+1$<+-0)K/+/4.$5+0+'$*(-0'+0::&./($)+()/$+0+/4&$.&;+3.$I&.+ 5(/4+BCD+-$)8(%&)-&= ! F$/+-'&0.+4<;0):+.&0''1+&L/.0-/+0)%+3.$-&::+'$*(-0'+:/0/&;&)/:+ :1;9$'(-0''1+0)1501= ! ,:&+/4(:+/$+%&-(%&+/4&+&L3&-/&%+