程序代写代做代考 Context Free Languages Lambda Calculus Computational

Computational
Linguistics
CSC 485 Summer 2020
8
8. Mildly Context-Sensitive Grammar Formalisms
Gerald Penn
Department of Computer Science, University of Toronto
Based on slides by David Smith, Dan Klein, Stephen Clark and Eva Banik
Copyright © 2017 Gerald Penn. All rights reserved.

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; prosody and information structure; automatic parsers; generation
16

Combinatory Categorial Grammar (CCG)




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
17

CCG Lexical Categories
• •
• • •
transitive verb: (S \NP )/NP respected
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

intransitive verb: S \NP walked
Complex categories encode subcategorisation information
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

ccg Grammar Simple CCG Derivation
A Simple ccg Derivation
interleukin − 10 NP
inhibits production
(S \NP )/NP
S \NP S
NP
> < > forward application < backward application 19 ccg Gram Function Application Schemata unction Application Rule Schemata • Forward (>) and backward (<) application: X/Y Y ⇒ X (>) Y X\Y ⇒ X (<) 20 F Classical Categorial Grammar Classical Categorial Grammar ccg Grammar • • ‘Classical’ Categorial Grammar only has application rules Classical Categorial Grammar is context free S NP (S\NP)/NP NP interleukin-10 inhibits production S\NP Stephen Clark Practical Linguistically Motivated Parsing JHU, J une 2 21 2 0 Classical Categorial Grammar ccg Grammar Classical Categorial Grammar • • ‘Classical’ Categorial Grammar only has application rules Classical Categorial Grammar is context free S NP V NP interleukin-10 inhibits production VP Stephen Clark Practical Linguistically Motivated Parsing JHU, June 2 22 Extraction out of a Relative Clause The company which (NP\NP)/(S/NP) NP Microsoft bought NP (S\NP)/NP S /(S \NP )S /NP NP \NP NP/N NP N > T type-raising
> B forward composition
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
23

Extraction out of a Relative Clause
The company
which Microsoft bought
(NP\NP)/(S/NP) NP
S /(S \NP )S /NP
NP/N
NP
N
(S\NP)/NP
>T
> T type-raising
NP
NP \NP
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
24

Extraction out of a Relative Clause
The
NP/N
company
N
which Microsoft bought
NP
>T
S /NP
(NP\NP)/(S/NP) NP S/(S\NP)
(S\NP)/NP
>B
> T > B
type-raising
forward composition
NP
NP \NP
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
25

Extraction out of a Relative Clause
The company
NP/N N
which Microsoft bought
(NP\NP)/(S/NP) NP S/(S\NP)
(S\NP)/NP
>B >
>T
S /NP
NP
NP \NP
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
26

Extraction out of a Relative Clause
The
NP/N
company which Microsoft bought
N
(NP\NP)/(S/NP) NP (S\NP)/NP > >T
NP
S/(S\NP)
S /NP
NP \NP
< >B >
NP
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
27

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) (T
S/(S\NP) S/NP S/NP
(S \NP )/NP S/NP
conj NP (S \NP )/NP NP >T
> T type-raising
S
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
29

“Non-constituents” in ccg – Right Node Raising
Google
sells
but
conj
S /NP S
Microsoft buys shares
NP S/(S\NP)
> T type-raising
> B forward composition
>T
S/(S\NP)
S/NP >B
(S \NP )/NP S/NP >B
NP (S \NP )/NP NP >T
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
30

“Non-constituents” in ccg – Right Node Raising
Google
sells
but
conj
Microsoft buys shares
NP S/(S\NP)
>T
S/(S\NP)
(S \NP )/NP S/NP >B
NP (S \NP )/NP NP >T
S /NP S
S/NP >B <Φ>
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
31

“Non-constituents” in ccg – Right Node Raising
Google
sells
but
conj
Microsoft buys shares
NP S/(S\NP)
>T
S/(S\NP)
S/NP >B
(S \NP )/NP S/NP >B
NP (S \NP )/NP NP >T
S /NP S
<Φ>
>
Stephen Clark
Practical Linguistically Motivated Parsing JHU, June 2009
32

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

9(‘(:/(-+.&0:$)()*?+)$/+O<:/+3.$909('(:/(-+ + 91+:1;9$'(-+.&0:$)()*6 PP2+E0.:()* 2+E0.:()* CCG Semantics ! P$;9()0/$.1+ P0/&*$.(0'+ 2.0;;0. • ! Q<''1+R;$)$ST+ Categories encode argument sequences '&L(-0'(U&%+ • and lambda calculus semantic operations *.0;;0. Parallel syntactic combinator operations ! P0/&*$.(&:+&)-$%&+ 0.*<;&)/+ :&V<&)-&: ! W&.1+-'$:&'1+ .&'0/&%+/$+/4&+ '0;9%0+-0'-<'<: ! P0)+40I&+:3<.($<:+ 0;9(*<(/(&:+R541MT 34 P CCG Semantics Left arg. Right arg. Operation Result X/Y : f Y :a Forward application X : f(a) Y :a X\Y : f Backward application X : f(a) X/Y : f Y/Z : g Forward composition X/Z : λx.f(g(x)) X :a Type raising T/(T\X) : λf.f(a) etc. 35 Tree Adjoining Grammar 36 TAG Building Blocks • Elementary trees (of many depths) • Harry likes peanuts passionately. •αα Tree Substitution Grammar equivalent to TAG Building Blocks Substitution at ↓ 1 NP 2 S Harry 􏱅H 􏱅􏱅􏱅􏱅 HHHH NP↓ VP 􏱅􏱅􏱅􏱅HHH CFG 􏱅􏱅􏱅 HHH NP↓ VP 􏱅􏱅􏱅􏱅HHH V NP↓ likes V TAG Building Blocks NP↓ Harry likes peanuts passionately. NP S α3 βα1 α2􏱅􏱅HH NP peanuts VP likes 􏱅􏱅􏱅􏱅􏱅HHHH 􏱅H VP* Adv passionately Harry α3 NP β VP 􏱅􏱅H 3 􏱅􏱅􏱅 HHH 37 peanuts 􏱅H TAG Building Blocks TAG Building Blocks • Auxiliary trees for adjunction α1 NP α2 S • Adds extra power beyond CFG 􏱅􏱅􏱅􏱅􏱅HHHHH NP↓ VP 􏱅􏱅H TAG Building Blocks 􏱅􏱅 HH Harry likes peanuts passionately. α1NPα2S NPVP Harry likes peanuts passionately. likes 􏱅􏱅􏱅􏱅HHHH α3 β 􏱅􏱅H Harry V NP↓ Harry 􏱅H 􏱅􏱅HH NP↓ VP 􏱅􏱅􏱅HH V NP↓ peanuts 􏱅􏱅 HH 􏱅H VP* Adv passionately likes α3 NP β VP peanuts 􏱅􏱅􏱅􏱅􏱅􏱅HHHHH VP* Adv passionately 38 TAG Building Blocks Harry likes peanuts passionately. α1 NP α2 S Harry 􏱅􏱅􏱅􏱅􏱅HHHHH NP↓ VP Derivation Tree􏱅􏱅􏱅􏱅HHH Derived Tree S α1 likes 􏱅􏱅􏱅􏱅􏱅􏱅􏱅􏱅􏱅HHHHHHHH V NP↓ 􏱅􏱅􏱅􏱅􏱅􏱅􏱅􏱅HHHHHHH αNP􏱅 VPH 􏱅 H 3 β H 􏱅H 􏱅 􏱅􏱅 􏱅􏱅􏱅HH HH NP VP1 􏱅H α2 􏱅􏱅β HH α3 Harry passionately peanuts 􏱅􏱅􏱅HH peanuts VP* Adv passionately Semantics 􏱅 H 􏱅H Harry 􏱅􏱅􏱅􏱅 VP2 􏱅􏱅􏱅􏱅􏱅HHHH V 3 NP likes peanuts HHHH Adv passionately Harry(x) ∧ likes(e, x, y) ∧ peanuts(y) ∧ passionately(e) 4 39