Syntax with Context-Free Grammars
ANLP: Week 5, Unit 2
Shay Cohen
Based on slides from ANLP 2019
1/17
Desirable Properties of a Grammar
Chomsky specified two properties that make a grammar “interesting and satisfying”:
It should be a finite specification of the strings of the language, rather than a list of its sentences.
It should be revealing, in allowing strings to be associated with meaning (semantics) in a systematic way.
We can add another desirable property:
It should capture structural and distributional properties of the language. (E.g. where heads of phrases are located; how a sentence transforms into a question; which phrases can float around the sentence.)
A Tiny Fragment of English
Let’s say we want to capture in a distributional properties that give
A duck walked in the park.
The man walked with a duck. You made a duck.
You made her duck.
A man with a telescope saw you. A man saw you with a telescope. You saw a man with a telescope.
grammar the structural and rise to sentences like:
NP,V,PP
NP,V,PP Pro,V,NP ? Pro,V,NP NP,PP,V,Pro NP,V,Pro,PP Pro,V,NP,PP
We want to write grammatical rules that generate these phrase structures, and lexical rules that generate the words appearing in them.
2/17
4/17
Desirable Properties of a Grammar
Context-free grammars (CFGs) provide a pretty good approximation.
Some features of NLs are more easily captured using mildly context-sensitive grammars, as well see later in the course.
There are also more modern grammar formalisms that better capture structural and distributional properties of human languages. (E.g. combinatory categorial grammar.)
Programming language grammars (such as the ones used with compilers, like LL(1)) aren’t enough for NLs.
3/17
A Tiny Fragment of English
Let’s say we want to capture in a distributional properties that give
A duck walked in the park.
The man walked with a duck. You made a duck.
You made her duck.
A man with a telescope saw you. A man saw you with a telescope. You saw a man with a telescope.
grammar the structural and rise to sentences like:
NP,V,PP
NP,V,PP Pro,V,NP ? Pro,V,NP NP,PP,V,Pro NP,V,Pro,PP Pro,V,NP,PP
We want to write grammatical rules that generate these phrase structures, and lexical rules that generate the words appearing in them.
4/17
A Tiny Fragment of English
Let’s say we want to capture in a distributional properties that give
A duck walked in the park.
The man walked with a duck. You made a duck.
You made her duck.
A man with a telescope saw you. A man saw you with a telescope. You saw a man with a telescope.
grammar the structural and rise to sentences like:
NP,V,PP
NP,V,PP Pro,V,NP ? Pro,V,NP NP,PP,V,Pro NP,V,Pro,PP Pro,V,NP,PP
We want to write grammatical rules that generate these phrase structures, and lexical rules that generate the words appearing in them.
A Tiny Fragment of English
Let’s say we want to capture in a distributional properties that give
A duck walked in the park.
The man walked with a duck. You made a duck.
You made her duck.
A man with a telescope saw you. A man saw you with a telescope. You saw a man with a telescope.
grammar the structural and rise to sentences like:
NP,V,PP
NP,V,PP Pro,V,NP ? Pro,V,NP NP,PP,V,Pro NP,V,Pro,PP Pro,V,NP,PP
We want to write grammatical rules that generate these phrase structures, and lexical rules that generate the words appearing in them.
4/17
4/17
A Tiny Fragment of English
Let’s say we want to capture in a distributional properties that give
A duck walked in the park.
The man walked with a duck. You made a duck.
You made her duck.
A man with a telescope saw you. A man saw you with a telescope. You saw a man with a telescope.
grammar the structural and rise to sentences like:
NP,V,PP
NP,V,PP Pro,V,NP ? Pro,V,NP NP,PP,V,Pro NP,V,Pro,PP Pro,V,NP,PP
We want to write grammatical rules that generate these phrase structures, and lexical rules that generate the words appearing in them.
4/17
Grammar for the Tiny Fragment of English
Grammar G1 generates the sentences on the previous slide:
Grammatical rules
S → NP VP
NP → Det N NP → Det N PP NP → Pro
VP → V NP PP VP → V NP
VP → V
PP → Prep NP
Lexical rules
Det → a | the | her (determiners)
N → man | park | duck | telescope (nouns) Pro → you (pronoun)
V → saw | walked | made (verbs)
Prep → in | with | for (prepositions)
5/17
Context-free grammars: formal definition
A context-free grammar (CFG) G consists of
a finite set N of non-terminals,
a finite set Σ of terminals, disjoint from N,
a finite set P of productions of the form X → α, where X ∈ N, α ∈ (N ∪ Σ)∗,
a choice of start symbol S ∈ N.
A sentential form is any sequence of terminals and nonterminals that can appear in a derivation starting from the start symbol.
Formal definition: The set of sentential forms derivable from G is the smallest set S(G) ⊆ (N ∪ Σ)∗ such that
S ∈ S(G)
ifαXβ∈S(G)andX →γ ∈P,thenαγβ∈S(G).
The language associated with grammar is the set of sentential forms that contain only terminals.
Formal definition: The language associated with G is defined by L(G) = S(G)∩Σ∗
A language L ⊆ Σ∗ is defined to be context-free if there exists some CFG G such that L = L(G).
6/17
7/17
A sentential form is any sequence of terminals and nonterminals that can appear in a derivation starting from the start symbol.
Formal definition: The set of sentential forms derivable from G is the smallest set S(G) ⊆ (N ∪ Σ)∗ such that
S ∈ S(G)
ifαXβ∈S(G)andX →γ ∈P,thenαγβ∈S(G).
The language associated with grammar is the set of sentential forms that contain only terminals.
Formal definition: The language associated with G is defined by L(G) = S(G)∩Σ∗
7/17
Assorted remarks
X →α1 | α2 | ··· | αn issimplyanabbreviationfora bunch of productions X → α1, X → α2, …, X → αn.
These grammars are called context-free because a rule X → α says that an X can always be expanded to α, no matter where the X occurs.
This contrasts with context-sensitive rules, which might allow us to expand X only in certain contexts, e.g. bXc → bαc.
Broad intuition: context-free languages allow nesting of structures to arbitrary depth. E.g. brackets, begin-end blocks, if-then-else statements, subordinate clauses in English, . . .
8/17
Grammar for the Tiny Fragment of English
Grammar G1 generates the sentences on the previous slide:
Grammatical rules
S → NP VP
NP → Det N NP → Det N PP NP → Pro
VP → V NP PP VP → V NP
VP → V
PP → Prep NP
Lexical rules
Det → a | the | her (determiners)
N → man | park | duck | telescope (nouns) Pro → you (pronoun)
V → saw | walked | made (verbs)
Prep → in | with | for (prepositions)
Does G1 produce a finite or an infinite number of sentences?
Structural Ambiguity
You saw a man with a telescope. S
NP VP Pro
9/17
You
saw
V NP PP
Det N a man
Prep NP
with
Det N
a telescope
11/17
Recursion
Recursion in a grammar makes it possible to generate an infinite number of sentences.
In direct recursion, a non-terminal on the LHS of a rule also appears on its RHS. The following rules add direct recursion to G1:
VP → VP Conj VP Conj → and | or
In indirect recursion, some non-terminal can be expanded (via several steps) to a sequence of symbols containing that non-terminal:
NP → Det N PP PP → Prep NP
10/17
Structural Ambiguity
You saw a man with a telescope. S
NP VP
Pro
V NP
You
saw
Det N PP
a man
Prep NP
with Det N
a telescope
12/17
Structural Ambiguity
You saw a man with a telescope.
S
NP VP Pro
You
V NP PP
saw Det N Prep
NP Pro You
N telescope
VP
S
V NP saw
Det N PP
NP
a
man Prep NP
a man
with Det a
with
Det N
a telescope
This illustrates attachment ambiguity: the PP can be a part of the VP or of the NP. Note that there’s no POS ambiguity here.
Structural Ambiguity
You saw a man with a telescope.
S
NP VP Pro
You
V NP PP
saw Det N Prep
NP Pro You
N telescope
VP
S
13/17
V NP saw
Det N PP
NP
a
man Prep NP
a man
with Det a
with
Det N
a telescope
This illustrates attachment ambiguity: the PP can be a part of the VP or of the NP. Note that there’s no POS ambiguity here.
13/17
Structural Ambiguity
You saw a man with a telescope.
S
NP VP Pro
You
V NP PP
saw Det N Prep
NP Pro You
N telescope
VP
S
V NP saw
Det N PP
NP
a
man Prep NP
a man
with Det a
with
Det N
a telescope
This illustrates attachment ambiguity: the PP can be a part of the VP or of the NP. Note that there’s no POS ambiguity here.
13/17
Structural Ambiguity
Grammar G1 only gives us one analysis of you made her duck. S
NP VP
Pro
You made Det N
her duck
There is another, ditransitive (i.e., two-object) analysis of this sentence – one that underlies the pair:
What did you make for her? You made her duck.
V NP
14/17
Structural Ambiguity
For this alternative, G1 also needs rules like:
NP → N
VP → V NP NP Pro → her
S
NP VP
Pro
You made Det N her duck
V NP
S
NP VP
Pro You
V NP NP made Pro N
her duck In this case, the structural ambiguity is rooted in POS ambiguity.
Structural Ambiguity
There is a third analysis as well, one that underlies the pair: What did you make her do?
You made her duck. (move head or body quickly downwards) Here, the small clause (her duck) is the direct object of a verb.
Similar small clauses are possible with verbs like see, hear and notice, but not ask, want, persuade, etc.
G1 needs a rule that requires accusative case-marking on the subject of a small clause and no tense on its verb.:
VP → V S1
S1 → NP(acc) VP(untensed) NP(acc) → her | him | them
15/17
16/17
Structural Ambiguity
There is a third analysis as well, one that underlies the pair:
What did you make her do? You made her duck.
Here, the small clause (her duck) is the direct object of a verb. Similar small clauses are possible with verbs like see, hear and
notice, but not ask, want, persuade, etc.
G1 needs a rule that requires accusative case-marking on the
subject of a small clause and no tense on its verb.:
VP → V S1
S1 → NP(acc) VP(untensed) NP(acc) → her | him | them
16/17
Summary
Phrases are the building block of sentence structure; a phrase has a head, it’s most important element (e.g., verb in VP).
Recursion in grammar makes it possible to generate an infinite number of sentences; direct vs. indirect recursion.
Structural ambiguity can be caused by POS ambiguity or by attachment ambiguity.
Recursive-decent is a top-down, depth-first parsing algorithm with backtracking.
Shift-reduce is a bottom-up, depth-first parsing algorithm, with optional backtracking.
With global ambiguity, the whole string is ambiguous. With local ambiguity, only a substring is ambiguous.
18/17
Structural Ambiguity
Now we have three analyses for you made her duck:
SSS
NP VP
Pro V NP
Det N
You made her duck
NP VP NP VP Pro V NP NP Pro V S
Pro N
NP(acc) VP V
You made her duck You made her duck
How can we compute these analyses automatically?
17/17