[SOLVED] python algorithm 20-trees-grammars.pptx

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