Transcript Grammars for a Natural Language

Grammars for a Natural Language
•
•
•
•
•
•
5.1 – Auxiliary Verbs and Verb Phrases
5.2 – Movement Phenomena in Language
5.3 – Handling Questions in CFGs
5.4 – Relative Clauses
5.5 – The Hold Mechanism in ATNs
5.6 – Gap Threading
5.1 – Auxiliary Verbs
• Additional “pre-verb” completing sentence
– can, have, shall, may, do, will, must, need, dare, ought
to, used to, be going to
– I will watch the movie.
– My friend should see it for himself.
– Henry might want to take a vacation.
– Next week, they will have been missing for fifteen days.
• Very ordered structure in grammar (not random)
– Auxiliary verbs determine main verb structure
Testing for Auxiliary Verbs
• Can be placed before “not”
– He can not say those things.
– *I eat not a bite more.
• Can precede the subject NP in a question
– Would we run the entire race?
– *Enjoys she her job?
• May not appear as the only verb **
– *John shall the weekend.
– Mary loves the weekend.
Modal & COMPFORM
• Modal auxiliaries exclude “be”, “have”
– Appear only in finite tense (present and past)
– Can only be auxiliary verbs
• Non-modal auxiliaries include “be”, “have”
– Can appear in variety of tenses
– Can be main verbs as well as auxiliary
• COMPFORM
– Feature used to specify form of main verb
COMPFORM Chart
• Chart reproduced from Fig. 5.1 on p. 124 of text
•
•
•
•
Auxiliary
COMPFORM
Construction
modal
“have”
“be”
“be”
base
pastprt
ing
pastprt
modal
perfect
progressive
passive
I can see the house.
I have seen the house.
I am lifting the box.
I was seen by the crowd.
COMPFORM = base
COMPFORM = pastprt
COMPFORM = ing
COMPFORM = pastprt
Grammars with Auxiliaries
•
Grammar rule for VP
VP  (AUX COMPFORM ?s)(VP VFORM ?s)
– I must complete this work.
– I have known that answer for a while.
– I am crying.
•
Restriction 1
Modal + have + be (progressive) + be (passive)
The song might have been being played as we
left.
More Auxiliary Restrictions
• #1: Modal + have + be (prog.) + be (pass.)
– Exception: I regret having been chosen to go.
• #2: Auxiliary sequences can appear as VP
complements for certain verbs
– Exception: *I must be having been singing.
• #3: Add a MAIN feature to signal a main
verb, and a PASS feature to signal passive
VP  AUX[be] VP[ing, +main]
VP[+pass]  AUX[be] VP[passprt, +main]
Features: main, pass
VP  AUX[be] VP[ing, +main]
VP[+pass]  AUX[be] VP[passprt, +main]
VP  V[..]..
• Examples
–
–
–
–
I was helping the boy.
I was seen by the boy.
I was being good.
Parse trees at Fig. 5.4 on page 128 of text
Passive Sentences
• Passive sentences reverse order of NPs:
– I will hide my hat.
– The hat will be hidden by me.
• Object may be removed from passive:
– The hat will be hidden.
• Feature signals missing object – passgap
VP[+passgap]  VP[np]
VP[-passgap]  VP[np] NP
5.2 – Movement Phenomena
• Movement Phenomena – moving parts of a
sentence around, such as in questioning
• Subject-aux inversion
– Rearranging the subject and auxiliary verb to
ask a question
– John is going to the store.
– Is John going to the store?
– Henry found four dollars.
– Did Henry find four dollars?
Local & Unbounded Movement
• Local Movement
– Movement of constituents within limited rules
– Subject-aux inversion
• Unbounded Movement
– Arbitrary movement of constituents in sentence
– Wh-questions
• Wh-questions
– Forming a question by using a wh- word (e.g.,
what, who, why, when)
Wh-questions
• Joe had written a letter to the congressman last night.
– Who ^ had written a letter to the congressman last
night?
– What had Joe written ^ to the congressman last night?
– To whom had Joe written a letter ^ last night?
– When had Joe written a letter to the congressman ^?
• Inverts auxiliary and subject
– Allows inversion rules to apply
• Questions begin with a wh-word
• A gap appears in each sentence at ^
Handling Gaps
• Gap – space where word has been removed
• Filler – moved constituent
• Transformational Grammar
– Maps a regular CFG (deep structure) to an
altered CFG (surface structure)
– Box 5.1 on page 131 of text
• Hold List on CFGs
– Allows constituents to be “saved until later”
Handling Gaps
• Slash categories
– Nonterminals of form X/Y, where X is the real
constituent and Y is the missing constituent
– Increases grammar size
• Feature GAP
– Same format as slash category
– Grammar size not increased
Other Movement Types
• Box 5.2 on p. 132 of text
• Topicalization
– Movement for emphasis
– This picture, I had never liked.
• Adverb preposing
– Adverb moved to beginning of sentence
– Tomorrow, I will see you.
• Extraposition
– NP moved to sentence close
– A book was written discussing evolution
5.3 – Handling Questions in CFGs
• Goal – Extend CFG minimally for questions
• Yes/No questions
S[+inv]  (AUX COMPFORM ?s) (NP) (VP VFORM
?s)
• Gap Rule
(NP GAP ((CAT NP)(AGR ?a)) AGR ?a)  
• Nonlexical subconstituent
(S GAP ?g)  (NP GAP -)(VP GAP ?g)
• Lexical subconstituent
(VP GAP ?g)  V[_np_vp:inf](NP GAP ?g)(PP GAP-)
(VP GAP ?g)  V[_np_vp:inf](NP GAP -)(PP GAP ?g)
Analyzing Fillers
• Filler – moved subconstituent
• Word types
–
–
–
–
–
Pronouns – who, whom, what
Determiners – what, which
Prepositions – where, when
Adverbial modifier – how
Possessive Pronoun – whose
• Feature – WH
– Value = Q: wh-question
– Value = R: relative clause
New Syntactic Categories
• WH (feature, not syntactic category)
– Signals question
– Propagates up through rules (i.e., WH – PP – S)
• QDET
– Determiners introducing WH-terms
• PP-WRD
– Words that act as prepositional phrases
• CNP
– Common noun phrase
Grammar Rules for Wh-words
• Grammar 5.7 on p. 135 of the text
2. (NP WH ?w)  (DET WH ?w AGR ?a)(CNP AGR ?a)
3. CNP  N
5. DET  ART
7. (DET WH ?w)  (QDET WH ?w)
8. (PP WH ?w)  P (NP WH ?w)
9. (PP WH ?w)  (PP-WRD WH ?w)
• Examples
– Which book did you read?
– Where did you find the file?
– In what context did you mean that?
2, 7, 3
9
8, 2, 7, 3
Grammar Rules for Wh-questions
• Grammar 5.9 on p. 137 of text
11. (S[+inv] WH ?w GAP ?g)  (AUX COMPFORM ?s AGR
?a)(NP WH ?w AGR ?a GAP-)(VP VFORM ?s GAP ?g)
12. S  (NP[Q,-gap] AGR ?a)(S[+inv] GAP (NP AGR
?a))
16. (VP GAP ?g)  V[_np] (NP GAP ?g)
• Example: I will purchase the new book.
– What book will I purchase?
• 12: NP = “What book”; S = “will I purchase”
• 2, 7, 3: QDET = “What”; CNP = “book”
• 11: AUX = “will”; NP = “I”; VP = “purchase”
Parsing With Gaps
• Top-down parsing
– Not problematic: gaps are predictable
• Bottom-up parsing
– Problematic: gaps may exist at any position
• Strategy for charting
– Automatically insert gap wherever it is legal
– Works for both top-down and bottom-up,
although top-down creates fewer combinations
of constituents with gaps
Parsing Example With Gaps
• Which dogs did he see?
–
–
–
–
–
Rule 7: “Which”; Rule 3: “dogs”;
Rule 12: “Which dogs”
Rule 11: “did” + “he see”
Rule 1: “he”
Rule 16: “see”; Add EMPTY NP
• No unnecessary EMPTY constituents added
here
5.4 – Relative Clauses
• Embedded sentence missing a noun, connected by
a special relative pronoun (who, whom, which,
when, where, whose)
• New syntactic category: REL
CNP  CNP REL
REL  (NP WH R AGR ?a)(S[-inv, fin] GAP (NP AGR ?a))
REL  (PP WH R PFORM ?p)(S[-inv, fin] GAP (PP PFORM ?p))
The man who we saw at the store was the culprit.
The exam in which you found the error was corrected.
The man whose book you stole is going to the police.
Gaps in Relative Clause
• Gaps are not allowed inside subject
• Subject of relative clause becomes relative
pronoun
REL  NP[R] VP[fin]
– The firefighter who rescued the people…
– The newspaper which ran the story…
– The man who watched the baby…
Relative Pronoun “That”
• Added to wh-words already listed
• WH feature set to value “R” only
• Can use all rules applied to “R” wh-words
– The book that I lent you…
– The search that began four days ago…
• Sometimes the relative pronoun is missing
altogether (implied)
– The investigation (that) Mary has undertaken…
– The programmers (who) I recommended…
Reduced Relative Clauses
• Relative clauses without an explicit pronoun
(implied) AND that implied pronoun is the
missing subject
– The damage ^ caused by the storm was awful.
– The issue ^ creating the argument is age-old.
• Additional rules
REL  (VP VFORM {ing pastprt})
REL  (S[fin] GAP (NP AGR ?a))
• Although multiple gaps now can appear in a
sentence, they do not conflict
5.5 – Hold Mechanism in ATNs
• Hold list
– Alternative method for handling movement (to
gap features)
– Functions by “holding” special constituents to
be used instead at other places
• Hold list stores constituents until later
• Gaps process constituents as they exist, but
plan for where they are missing
Holding
• Hold action
– Adds a constituent to a hold list
– Occurs on an arc transfer in an ATN
– HOLD *
• Emptying list
– VIR arc removes held word of specified type
– Cannot pop from ATN until list is completely
emptied
Holding Examples
• Grammar 5.14 on p. 145 of the text
• Example sentences:
–
–
–
–
–
The dog bit the cat.
Can you find the car?
Who ate the pizza?
The man who ate the pizza spent fifteen dollars.
Who do I see?
Comparing GAPs & Hold Lists
• Three considerations
– Coverage: Can it handle all examples?
– Selectivity: Does it reject ill-formed examples?
– Conciseness: How easily are the rules specified?
• Coverage is equal among the two methods
• Selectivity and conciseness need to be
analyzed and considered
Selectivity & Conciseness
• GAPs require an NP with an NP gap be empty
• ATNs allow held constituents to be used in ways
that violate this rule
– *Who did the man who saw hit the boy?
– Relative clause = “who saw”
– Main sentence = “Who did the man hit the boy”
• To make ATN as selective as GAPs, add
complexity, reduce conciseness
• Fine line between formalism as enabler and
restrictor
5.6 – Gap Threading
• Third method for handling rearrangement of
constituents
• Used in logic grammars
• Predicates defined containing:
– Position-in and position-out, which define the
range of the input
– A list of fillers that exist before the rule is
applied
– A list of fillers existing after the rule is applied
Filler Lists
• Subconstituents can be removed from the
input filler list if they are used as part of the
constituent’s construction
• Subconstituents can be added to the output
filler list if they are parsed but not used as
part of the constituent
• Flexible, but constraints are explicitly
enforced, not part of the formalism (similar
to hold lists)