close

Вход

Забыли?

вход по аккаунту

?

CONTEXT-FREE GRAMMARS

код для вставкиСкачать
CONTEXT-FREE GRAMMARS
1
Syntactic analysis (Parsing)
S
NP
AT
the
VP
NNS
VBD
children
ate
NP
AT
the
2
NLE
NN
cake
Beyond regular languages:
Context-Free Grammars
S пѓ NP VP
NP пѓ Det Nominal
Nominal пѓ Noun
VP пѓ V
4
Det пѓ the
Det пѓ a
Noun пѓ flight
V пѓ left
NLE
Derivations
пЃ¬
A DERIVATION of a string is a sequence of rule
applications
–
E.g., the string “a flight” can be derived from the grammar
above and symbol NP by the (leftmost first) derivation
пЃ¬
пЃ¬
пЃ¬
5
NP => Det Nominal => a Nominal => a Noun => a flight
Derivations can be visualized as PARSE TREES
The LANGUAGE defined by a CFG is the set of strings
derivable from the start symbol S (for Sentence)
NLE
Derivations and parse trees
6
NLE
A more formal definition
пЃ¬
7
A CFG is a 4-tuple
<N,пЃ“,P, S> consisting of
NLE
What `context free’ means
8
NLE
Derivations and languages
пЃ¬
The language LG GENERATED by a CFG
grammar G is the set of strings of TERMINAL
symbols that can be derived from the start
symbol S using the production rules in G
–
пЃ¬
пЃ¬
9
LG = {w | w is in пЃ“* and S derives w}
The strings in LG are called GRAMMATICAL
The strings not in LG are called
UNGRAMMATICAL
NLE
Grammar development
пЃ¬
пЃ¬
10
One of the most basic skills in NLE is the ability
to write a CFG for some fragment of a
language (e.g., the dates)
We’ll briefly cover some of the issues to be
addressed when writing small CFG grammars
NLE
An example lexicon
11
NLE
An example grammar
12
NLE
A simple parse tree
13
NLE
Basic types of phrases
пЃ¬
пЃ¬
пЃ¬
пЃ¬
14
Sentences
Noun Phrases
Verb phrases
Prepositional phrases
NLE
Basic types of sentences
15
NLE
Noun phases: premodifiers
пЃ¬
пЃ¬
NP пѓ (Det) (Card) (Ord) (Quant) (AP) Nominal
Det: Determiners
–
–
пЃ¬
пЃ¬
пЃ¬
пЃ¬
16
a flight
Optional: I’m looking for flights to Denver
Card: Cardinal numbers (one stop)
Ord: Ordinal numbers (the first flight)
Quantifiers: most flights to Denver leave in the morning
AP (Adjectives): three very expensive seats
NLE
Noun phases: postmodifiers
пЃ¬
пЃ¬
пЃ¬
пЃ¬
17
Nominal пѓ Noun
Nominal пѓ Nominal PP (PP) (PP)
Nominal пѓ Nominal GerundVP
Nominal пѓ Nominal RelClause
NLE
Types of postnominal modifiers
18
NLE
Recursion
пЃ¬
Nominal пѓ Nominal PP (PP) (PP)
–
пЃ¬
Other examples:
–
–
пЃ¬
19
Is an example of RECURSIVE rule
NP пѓ NP PP
VP пѓ VP PP
Recursion a powerful device, but could have
bad consequences (see lectures on parsing)
NLE
Recursion and VP attachment
20
NLE
Coordination
пЃ¬
NP пѓ NP and NP
–
пЃ¬
VP пѓ VP and VP
–
пЃ¬
John talks softly and carries a big stick
S пѓ S and / but / S
–
пЃ¬
John and Mary left
Kim is a lawyer but Sandy is reading medicine.
In fact, probably English has a
XP пѓ XP and XP
rule
–
21
NLE
Agreement
пЃ¬
пЃ¬
пЃ¬
пЃ¬
пЃ¬
пЃ¬
пЃ¬
22
This dog
Those dogs
*This dogs
*Those dogs
This dog is smart
*This dog are smart
*Those dogs is smart
NLE
CFGs vs Regular languages
пЃ¬
пЃ¬
For many applications, finite state languages
(the languages defined by FA) are appropriate
Limitation of FAs: cannot count
–
пЃ¬
Example of construction showing that English
is CF: long-distance dependencies
–
24
I.e., cannot check A n B n
Which film did Kim say the director who we just met
_ recommended _?
NLE
The Chomsky Hierarchy
пЃ¬
Finite-state languages (type 3)
–
пЃ¬
Context-free languages (type 2)
–
пЃ¬
CAC пѓ BB
Recursively enumerable languages
–
25
A пѓ BB
Context-sensitive languages (type 1)
–
пЃ¬
A пѓ bC | Cb (a single NT on the right)
Every language that can be specified by a finite algorithm
NLE
Readings
пЃ¬
пЃ¬
Jurafsky and Martin, chapter 9
The chapters on context-free languages in
–
–
26
The Free Dictionary:
http://encyclopedia.thefreedictionary.com/Contextfree%20language
Wikipedia:
http://en.wikipedia.org/wiki/Context-free_grammar
NLE
Документ
Категория
Презентации
Просмотров
3
Размер файла
268 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа