20-trees-grammars.pptx
Ling131A
IntroductiontoNLPwithPython
Trees,GrammarsandParsers
MarcVerhagen,Fall2018
Today
Gradesforassignment3areposted
Quiz2
Virtualenvironments
ConstituentsandTrees
PennTreebank
GrammarsandParsing
Quiz2
AllclassnotesstartingwithWordNet
NLTKCh3:3.43.7
NLTKCh5:5.1-5.2,5.4-5.7
NLTKCh6:6.1.1-6.1.5,6.3-6.5
NLTKCh8:8.1-8.5
Questions:
Pythonclass,regularexpressions,WordNet,decision
treesorbayes,taggers,classifiers,vectors,evaluation,
trees,grammars,parsers
VirtualEnvironments
Dependencyhell
Thirdpartypackagesinstalledatafewspots
Butyoucanonlyhaveoneversionofapackage
Whatiftwoprogramsrequiredifferentversions?
>>> import site
>>> site.getsitepackages()
[/usr/local/Cellar/python/3.6.5/Frameworks
/Python.framework/Versions/3.6/lib/python3.6
/site-packages,
/Library/Python/3.6/site-packages]
>>>
VirtualEnvironments
CreateanisolatedenvironmentforPython
projects
eachprojecthasitsowndependencies,regardless
ofwhatdependenciesotherprojectshave
https://docs.python.org/3/library/venv.html
$ python3 -m venv /virtual-environments/nltk
$ source /virtual-environments/nltk/bin/activate
$ which python
/virtual-environments/nltk/bin/python
BeyondBigrams
Bigramsworkwellformodelingpartofspeech
tags
Butnotsomuchforsentences
Theworstpartandclumsylookingforwhoever
heardlight.
Perfectlyokaywhenseenasasequenceoftags
withinanbigrammodel
Usingagrammarasamodelisbetterhere
GrammarModel
Hereisonerulefromagrammar
IfX1andX2arebothphrasesofgrammatical
categoryC,thenthephrase[X1 and X2]
isalsoofcategoryC
Thisisviolatedby
[The worst part]NP and [clumsy looking]AP
Constituents
Agroupofwordsthatformasingleunitina
hierarchicalstructure
Substitution
Aconstituentofonetypecantypicallybereplaced
byanotheroneofthesametype
[Thelittlebear][sleeps]
[Thebear][sleeps]
[She][sleeps]
Themeaningchanges,butthesentenceis
syntacticallyverysimilar
Constituentstructure
Syntacticcategories
Symbol Meaning Example
S sentence themanwalked
NP nounphrase adog
VP verbphrase sawapark
PP prepositionalphrase withatelescope
Det determiner the
N noun dog
V verb walked
P preposition in
Constituentstructure
Constituentstructuretree
PennTreebank
Phrasestructureannotationinthegenerative
tradition
ThemostinfluentialtreebankinNLP.
Googlescholarcitation:6019(Marcusetal1993)
PTBI(Marcusetal1993)
Context-freebackbone
Skeletalstructures
Limitedemptyelements
Noargument/adjunctdistinction
PennTreebank
PTBII(Marcusetal1994)
Addedfunctiontagstomarkupgrammaticalroles
(thusargument/adjunctdistinction,thoughnot
structurally)
Enrichedthesetofemptyelements
Onemillionwordsof1989WallStreetJournal
materialannotatedinTreebank-2style.
ToolsforprocessingTreebankdata,includingtgrep,
atree-searchingandmanipulationpackage
usabilityoftgrepislimited,youmayfindthesoftwaretobe
difficultorimpossibletoport
PennTreebank
PTBIII
AddedtheBrowncorpus
PennTreebankinNLTK
AfragmentofPennTreebankII
Youcanexpandthisyourself
Addedfunctionalityinthenltk.Treeclass
Ambiguity
Ambiguity
Ambiguity
Ambiguity
Treeasamathematicalobject
Atreeisasetofconnectedlabelednodes,
eachreachablebyauniquepathfroma
distinguishedrootnode.
Parent,child,siblings
Gettingthetrees
Treeclasswithinitializationmethods
Treereader
turnaparsefromastringrepresentationintoa
treerepresentation
Shiftreduceparsing
Aformofautomaticparsing
turnalistoftokensintoatreerepresentation
ConstructingatreewithNLTK
nltk.Tree()
Canbeusedtobuildsmalltrees
>>> t = nltk.Tree(S,
[nltk.Tree(NP, [Fido]),
nltk.Tree(VP, [barks])])
>>> t
(S (NP Fido) (VP barks))
>>> t.draw()
ConstructingatreewithNLTK
nltk.Tree.fromstring()
Toparsestringsintotrees
Canbeusedtoreadinmanuallyconstructed
treebanksandturnthetreesintoannltk.Tree
object
Amorepracticalwayforgettingtrees
nltk.Tree.fromstring()
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
Q:Howdoesthisworkunderthehood?
A:Byusingastack
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
Grammars
Withregularexpressionswehadaregular
grammar
Nowwearelookingatthenextlevel:the
contextfreegrammar
Onecategoryontheleft-hand-sideoftherule
Oneormorecategoriesontheright-hand-side
Notallowed
S>
NPVP>DetNVP
Epsilonstandsfortheemptystring
Context-freegrammar
S->NPVP
VP->VNP|VNPPP
PP->PNP
V->saw|ate|walked
NP->John|Mary|Bob|DetN|DetNPP
Det->a|an|the|my
N->man|dog|cat|telescope|park
P->in|on|by|with
Recursioninsyntacticstructure
S->NPVP
NP->DetNom|PropN
Nom->AdjNom|N
VP->VAdj|VNP|VS|VNPPP
PP->PNP
PropN->Buster|Chatterer|Joe
Det->the|a
N->bear|squirrel|tree|fish|logAdj->angry|frightened|little|tall
V->chased|saw|said|thought|was|putP->on
ParsingwithCFG
Aparserprocessesinputsentencesaccording
totheproductionsofagrammar
Itproducesoneormoreconstituent
structuresthatconformtothegrammar
Grammar
adeclarativespecificationofwell-formedness
Parser
aproceduralinterpretationofthegrammarthat
searchesthespaceoftreeslicensedbyagrammar
ParsingwithCFG
Top-downparsing
Predicts/generatessentencesbystartingatthe
topwiththegoalofcreatingacategoryoftypeS
Drivenbythegrammar
Bottom-upparsing
Buildaparsetreefromthegroundup
Drivenbytheinputsentence
Recursivedescentparsing
Top-downparsing
Recursivelybreaksahigh-levelgoalinto
severallower-levelsubgoals
Expand,andmatch
Maintainsalistofnodesinahypothetictree
thatneedstobeexpanded(calledfrontier)
Useback-trackingifyougetintoadeadend
Thedogseesthecat
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Westartoffwiththestartsymbol
ofthegrammar.Thefrontierof
thetreeisthesetofsymbolsthat
youcanstillexpand,nodesinthe
frontierhavealightgreen
background
Andwehaveourinput
S
the dog thesees cat
S ! NP VP Det ! the
NP ! Det N N ! cat
VP ! V N ! dog
VP ! V NP V ! sees
S
NP VP
NDet
the cat
the dog thesees cat
ApplyS!NPVP
ApplyNP!DetN
ApplyDet!the
Confirmtheisininput
ApplyN!cat
Wrong:catisnotininput
S ! NP VP Det ! the
NP ! Det N N ! cat
VP ! V N ! dog
VP ! V NP V ! sees
Nowwebacktrack.Thatis,weundo
thelaststepandseewhetherthere
wasanalternative,ifnot,wekeep
undoingstepsuntilwedofindan
alternative.Ifwebacktrackallthe
waytoSwithoutfindingalternatives
thentheparserfails.
Weundidstep5fromthelast
slideandthefrontierisnowN
andVP.
Andwehaveanalternativewhich
istouseN!doginsteadofN
!cat
S
NP VP
NDet
the
the dog thesees cat
S ! NP VP Det ! the
NP ! Det N N ! cat
VP ! V N ! dog
VP ! V NP V ! sees
Notethatthisbacktrackingwouldnot
havebeenneedediftheparserhad
justbeenaweelittlebitsmarter,for
examplebygroupingtherulesfor
pre-terminals(N,VandDet)and
peekingaheadattheinput.
S
NP VP
NDet
the dog
the dog thesees cat
V
sees
ApplyN!dog
Confirmthatdogisintheinput
ApplyVP!V
ApplyV!sees
Confirmthatseesisintheinput
S ! NP VP Det ! the
NP ! Det N N ! cat
VP ! V N ! dog
VP ! V NP V ! sees
Butnowwearestuck.Thereareno
nodesonthefrontieranymore,but
wehavenotcoveredallinput.Sowe
backtrackagain.
S
NP VP
NDet
the dog
the dog thesees cat
Weundidstep3fromthe
previousslideandthefrontieris
nowtheVP.
Andwehaveanalternativewhich
istouseVP!VNPinsteadofVP
V.
S ! NP VP Det ! the
NP ! Det N N ! cat
VP ! V N ! dog
VP ! V NP V ! sees
S
NP VP
NDet
the
the
NP
dog
the dog thesees cat
NDet
V
cat
sees
ApplyVP!VNP
ApplyV>Sees
Checkforseesintheinput
ApplyNP!DetN
ApplyDet!the
Checkfortheintheinput
ApplyN!cat
Checkforcatintheinput
S ! NP VP Det ! the
NP ! Det N N ! cat
VP ! V N ! dog
VP ! V NP V ! sees
Andtheparsewassuccessful.
RecursiveDescentParserDemo
import nltk
nltk.app.rdparser_app.app()
Weaknessofrecursivedescentparsing
Left-recursiveproductionslikeNP!NPPP
leadstoaninfiniteloop
Theparserwastesalotoftimeconsidering
structuresorwordsthatdonotcorrespondto
theinputstructure
Backtrackingmaydiscardreusablestructures
Sonobodyusesthis
Bottom-upparsing
Familyofparsingmethodwheretheprocessis
drivenbytheinputtext
Generallymoreefficient
Bottom-upparsing
53
S ! NP VP
NP ! det noun
VP ! verb NP
det ! the
noun ! mouse
noun ! cheese
verb ! ate
Input:
Themouseatethecheese
Bottom-upparsing
54
S!NPVP
NP!detnoun
VP!verbNP
det!the
noun!mouse
noun!cheese
verb!ate
ShiftReduceParser
Asimplebottom-upparsingstrategy
Startwiththeinputsentence(alistofwords)
andanemptystack
Repeatedlypushthenextwordontothestack
Butifthetopnitemsonthestackmatchthe
righthand-sideofaCFGrule,thentheyare
poppedoffthestack,andreplacedwiththe
singleitemontheleft-handsideoftherule
ShiftReduceParser
Shift:pushingtothestack
Reduce:movingmelementsfromthestack
andreplacethemwithnelements(nm)
Reduceisguidedbyagrammarandcanonlybe
appliedtothetopitemsofthestack(alimitation
ofthestackdatastructure)
ShiftReduceParser
Theparserfinisheswhenalltheinputis
consumed
successifthereisasingleSnodeonthestack
failureifthereismorethanoneitemonthestack
Shift-reduceexample
Grammar:
S !NP VP
NP !Det N
VP !V
VP !V NP
Det !the
N !cat
N !dog
V !sees
Input:
Thedogseesthecat
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Westartwithanemptystackandthefullinput
sentence.Ouronlyoptionatthestartistoshift,that
is,weaddanelementfromtheremainingtexttothe
stack.Elementsinvolvedinthenextaction(words,
rulesandstackelements)areprintedinblue.
Stack
thedogseesthecat
Remainingtext
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
dogseesthecat
Remainingtext
the
Shiftedtheontothestack.
Therulewastoshiftunlessyoucouldreduce.Wecan
nowreducebecausetheonthestackmatchesthe
right-handside(rhs)ofarulesowewilldothat.
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
dogseesthecat
Remainingtext
Reducedbyremovingthefromthestackandadding
theminitreeusingtheruleDet!the.
Nextup:shift
Det
the
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
seesthecat
Remainingtext
Addeddogtothestack.
Nextup:reducebecausedogisontherhsofarule.
Det
the
dog
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
seesthecat
Remainingtext
Removeddogfromthestackandaddedanother
minitree.
Nextup:DetandNaretherhsofarule,sowecando
anotherreduce
NDet
the dog
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
seesthecat
Remainingtext
Twotopelementsofthestackwereremoved,and
onewasadded,drivenbytheruleNP!DetN.
Nextup:shift
NP
NDet
the dog
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
thecat
Remainingtext
Shiftedseesontothestack.
Nextup:wecandoanotherreduceandsincewestill
preferthoseovershiftswewillgoahead.
NP
NDet
the dog
sees
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
thecat
Remainingtext
Replacedseesonthestackwithaminitree.
Nextup:wecandoanotherreduce.
NP
NDet
the dog
V
sees
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
thecat
Remainingtext
RemovedV(sees)fromthestackandreplacedit
withVP(V(sees).
Nextup:yetanotherreducethistimedrivenbythe
ruleS!NPVP.
NP
NDet
the dog
V
sees
VP
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
thecat
Remainingtext
Wetooktwoelementsfromthestackandreplacedit
byone.
Nextup:ashift
NP
NDet
the dog
V
sees
VP
S
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
cat
Remainingtext
Weshiftedtheontothestack.
Nextup:areduce
NP
NDet
the dog
V
sees
VP
S the
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
cat
Remainingtext
Wetookthefromthestackandreplaceditbya
minitree.
Nextup:ashift
NP
NDet
the dog
V
sees
VP
S
the
Det
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
cat
Remainingtext
Weaddedcattothestack.
Nextup:areduce
NP
NDet
the dog
V
sees
VP
S
the
Det
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
cat
Remainingtext
Weremovedcatfromthestackandaddedamini
tree.
Nextup:areduce
NP
NDet
the dog
V
sees
VP
S
the
Det N
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
cat
Remainingtext
Wereplacedtwoelementsfromthestackand
replacedthemwithoneNP.
Nowthereisnothingthatwecando,andeven
thoughweconsumedallinput,theparsefailed
becauseweshouldhaveonlyoneelementonthe
stackattheend.
NP
NDet
the dog
V
sees
VP
S
the
Det N
NP
Shiftorreduce,thatisthequestion
Whenitispossibletoeithershiftorreduce,
whatshouldtheparserdo?
Whichreducetouseiftherearemorereduce
options?
Theanswertothesequestionscanmean
successorfailurefortheparser
74
Shiftorreduce,thatisthequestion
Possibleanswers:
Useheuristics
Reducehaspriorityovershift;
Usethereducethatcoversthemostitems
Assigningaprobabilitytoeachaction,andthe
actionwiththehighestprobabilitywins
Usebacktrackingtotryoutallchoicesifneeded
75
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
thecat
Remainingtext
Hereiswherewetookthewrongturnthelasttime.
Weweregoingtodoareducesincethosewere
favoredovershifts,butwhatifwechangeourrules.
(NotethatthereisasleightofhandheresinceIam
nowchangingtherulesinthemiddleofaparse,bad,
butitisforexplanatorypurposes).
NP
NDet
the dog
V
sees
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
thecat
Remainingtext
Letssaywenowusethefollowingheuristics.First,if
available,useareducewithaterminalrule.Second,if
noterminalrulesisavailableuseashift.Third,ifthere
isnoshiftusethereducewiththerulewiththe
longestright-handside.
Sohereweshift.
NP
NDet
the dog
V
sees
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
cat
Remainingtext
Nowwecanuseareducewithaterminalrule.
NP
NDet
the dog
V
sees
the
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack
cat
Remainingtext
Hereweshiftagain.
NP
NDet
the dog
V
sees
Det
the
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack Remainingtext
Andherewereducewithaterminalrule.
NP
NDet
the dog
V
sees
Det
the
cat
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack Remainingtext
Wenowdoareducewiththelongestavailablerule,
whichisNP!DetN.
NP
NDet
the dog
V
sees
Det
the cat
N
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack Remainingtext
Andagain
NP
NDet
the dog
V
sees Det
the cat
N
NP
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack Remainingtext
Andagain
NP
NDet
the dog
V
sees Det
the cat
N
NP
VP
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! the
N ! cat
N ! dog
V ! sees
Stack Remainingtext
Andnowwesucceeded.
NP
NDet
the dog
V
sees Det
the cat
N
NP
VP
S
ShiftReduce:prosandcons
Ashift-reduceparseronlybuildsstructurethat
correspondstothewordsintheinput
Generallymoreefficientthantop-down
Problem:
Iftheparsertakesthewrongturn,itmaynotfind
aparseevenifthereisone(incompleteness),and
itishardtocomeupwithgoodheuristics.
Sobacktrackingisneededandexcessiveambiguity
maycausetrouble.
85
Shift-Reduceparserdemo
import nltk
nltk.app.srparser_app.app()
Shiftreduceparsing
ChartParser
Efficientandcomplete
AnexampleofDynamicProgrammingas
appliedtoparsing
DynamicProgramming
Solveaproblembybreakingitintosmallersub
problems
Tworequirements:
Optimalsubstructure:optimalsolutioncanbe
createdfromoptionalsolutionsofsubproblems
Overlappingsubproblems:samesubproblemis
solvedoverandoveragain
RelatedtoDivideandConquerandRecursion
DynamicProgramming
Avoidcomputingasubproblemrepeatedlyby
storingtheminalookuptable,thusreducing
waste
ItisatechniquethatiswidelyusedinNLPto
solveproblemsofthiskind
ChartParsing
Dynamicprogrammingappliedtosyntactic
parsing
Aconstituentlikethemousewillbebuiltonly
onceandstoredinatable
AWell-FormedSubstringTable(WFST)canbe
usedtostoretheintermediateresults
Thefollowingisanoverlysimpleexampleof
usinganWFST
WFSTExample
Grammar:
S ! NP VP
NP ! Det Nom
Nom ! Adj N
VP ! V NP
Det ! the
Adj ! hungry | little
N ! bear | fish
V ! scared
Input:
thehungrybearscaredthelittlefish
WFST
wfst 1 2 3 4 5 6 7
0 Det
1 Adj
2 N
3 V
4 Det
5 Adj
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Initialization
Det Adj N V Det Adj N
start
end
wfst 1 2 3 4 5 6 7
0 Det
1 Adj Nom
2 N
3 V
4 Det
5 Adj Nom
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Span=2
Det Adj N V Det Adj N
Nom -> Adj N
Nom
Nom
wfst 1 2 3 4 5 6 7
0 Det NP
1 Adj Nom
2 N
3 V
4 Det NP
5 Adj Nom
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Span=3
Det Adj N V Det Adj N
Nom -> Adj N
NP -> Det Nom
Nom
Nom
NP NP
wfst 1 2 3 4 5 6 7
0 Det NP
1 Adj Nom
2 N
3 V VP
4 Det NP
5 Adj Nom
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Span=4
Det Adj N V Det Adj N
Nom -> Adj N
NP -> Det Nom
VP -> V NP
Nom
Nom
NP NP
VP
wfst 1 2 3 4 5 6 7
0 Det NP
1 Adj Nom
2 N
3 V VP
4 Det NP
5 Adj Nom
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Span=5
Det Adj N V Det Adj N
Nom -> Adj N
NP -> Det Nom
VP -> V NP
Nom
Nom
NP NP
VP
wfst 1 2 3 4 5 6 7
0 Det NP
1 Adj Nom
2 N
3 V VP
4 Det NP
5 Adj Nom
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Span=6
Det Adj N V Det Adj N
Nom -> Adj N
NP -> Det Nom
VP -> V NP
Nom
Nom
NP NP
VP
wfst 1 2 3 4 5 6 7
0 Det NP S
1 Adj Nom
2 N
3 V VP
4 Det NP
5 Adj Nom
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Span=7
Det Adj N V Det Adj N
Nom -> Adj N
NP -> Det Nom
VP -> V NP
S -> NP VP
Nom
Nom
NP NP
VP
S
StrengthsandweaknessesofWFST
Strength:
Muchmoreefficientthantherecursivedescentparser
Doesnotgetstuckinthesamewayastheshift-reduce
parser
Weaknesses
Checksconstituentsthatarenotlicensedbygrammar,
potentiallywasteful
Doesnotstorealternativeparseswhenthereis
ambiguity(onlyonecategorypercell)
100
Charts
Graphstructure
MoreversatilethanWFSTs
VP!VNP3
Alternativeparses
0 Sheseestheelephantwiththetelescope0 000000
V N
PP
NP
NP2
NP1
NDet
NP3!NPPP
Det
VP!VNP1PP
ChartParsers
CYKparser
Cocke-Younger-Kasamialgorithm
Bottom-up
Earleyparser
Top-down
Earleyparser
Fillthechartinasingleleft-to-rightpassoverthe
input.
ThechartwillbesizeN+1,whereNisthe
numberofwordsintheinput.
Chartentriesareassociatedwiththegaps
betweenthewords
likesliceindexinginPython.
Foreachpositioninthesentence,thechart
containsasetofedgesrepresentingthepartial
parsetreesgeneratedsofar.
Earleyparser
Candealwithallcontextfreegrammars
OperatesinO(n3)
Operations
Predict
Scan
Complete
0Mary1feeds2the3otter4eos5
Reviews
There are no reviews yet.