MinimalistParsing
Editedby ROBERTC.BERWICK AND EDWARDP.STABLER
GreatClarendonStreet,Oxford,OX26DP, UnitedKingdom
OxfordUniversityPressisadepartmentoftheUniversityofOxford. ItfurtherstheUniversity’sobjectiveofexcellenceinresearch,scholarship, andeducationbypublishingworldwide.Oxfordisaregisteredtrademarkof OxfordUniversityPressintheUKandincertainothercountries
©editorialmatterandorganizationRobertC.BerwickandEdwardP.Stabler2019 ©thechapterstheirseveralauthors2019
Themoralrightsoftheauthorshavebeenasserted FirstEditionpublishedin2019
Impression:1
Allrightsreserved.Nopartofthispublicationmaybereproduced,storedin aretrievalsystem,ortransmitted,inanyformorbyanymeans,withoutthe priorpermissioninwritingofOxfordUniversityPress,orasexpresslypermitted bylaw,bylicenceorundertermsagreedwiththeappropriatereprographics rightsorganization.Enquiriesconcerningreproductionoutsidethescopeofthe aboveshouldbesenttotheRightsDepartment,OxfordUniversityPress,atthe addressabove
Youmustnotcirculatethisworkinanyotherform andyoumustimposethissameconditiononanyacquirer
PublishedintheUnitedStatesofAmericabyOxfordUniversityPress 198MadisonAvenue,NewYork,NY10016,UnitedStatesofAmerica
BritishLibraryCataloguinginPublicationData Dataavailable
LibraryofCongressControlNumber:2019939273
ISBN978–0–19–879508–7(hbk.) ISBN978–0–19–879509–4(pbk.)
Printedandboundby CPIGroup(UK)Ltd,Croydon,CR04YY
LinkstothirdpartywebsitesareprovidedbyOxfordingoodfaithand forinformationonly.Oxforddisclaimsanyresponsibilityforthematerials containedinanythirdpartywebsitereferencedinthiswork.
4.ParsingwithMinimalistGrammars
4.2.2Samoanprosodicconstituency
4.2.3TheSamoansyntax–prosodyinterface
4.3Samoansyntax,spellout,prosody,andinterfaces:implementation
4.3.1Generationofcandidateprosodicparseswithan xfst transducer97
4.3.2Syntactic/post-syntacticgrammarfragment:MGlexiconandderivation99
4.3.3Simultaneous(post-)syntacticparsingandMatchPhrasecomputation102
4.3.4FinalphonologicaltransductionafterMGparse:StrongStart
4.4Discussionandconclusion
5.Parsingellipsisefficiently
GregoryM.Kobele
5.1Introduction
5.2Ellipsisinminimalistgrammars
5.2.1Minimalistgrammars
5.2.2Derivationalstructure
5.2.3Ellipsis
5.2.4Hypotheticalderivations
5.2.5Ellipsisoperations
5.2.6Interpretingellipsis
5.2.7Anexample
5.3Thecomplexityofellipsisresolution
5.3.1Parsinginthepresenceofellipsis
5.3.2Resolvingellipsis
5.3.3Updatingthediscoursecontext
5.3.4Elidingmaximalprojections
5.3.5Boundingellipsis
5.3.6Stoppingsilence
5.4Conclusion
6.Left-cornerparsingofminimalistgrammars
6.1Humanprocessingoflong-distancedependencies
6.1.1Empiricalbackground
6.1.2Retrievaldecisionsasambiguityresolution
6.2Thetop-downMGparser
6.3Towardsaleft-cornerMGparser
6.3.1CFGleft-cornerparsing
6.3.2Basiccases
6.3.3Multiplemovements
6.4Dealingwithremnantmovement
6.4.1Anoutlineofthechallenge
6.4.2Outlineofacandidatesolution
6.5Empiricalconnectionsbasedonwhatwehavesofar
6.5.1Activegap-filling
6.5.2Islandsensitivity
6.6Conclusion
7.GrammaticalpredictorsforfMRItime-courses
JixingLiandJohnHale
7.1Introduction
7.2Parametersinneuro-computationalmodels ofsentenceprocessing
7.2.1Grammar
7.2.2Parsingstrategy
7.2.3Complexitymetrics
7.2.4Summary
7.3Otherfactorsinfluencingsentenceprocessing
7.3.1Word-to-wordassociations
7.3.2Lexical-semanticcoherence
7.4CorrelatingfMRItime-courseswithvariousmetricsduring naturalstorylistening
7.4.1Complexitymetrics
7.4.2Dataacquisition
7.4.3Dataanalysis
7.4.4Results
7.5Towardsafunctionalanatomyofsentencecomprehension
Preface
ThechaptersinthisvolumegrewoutofaworkshoponMinimalistParsingheldatMIT onOctober10–11,2015.Sofarasweknow,theyrepresentthefirstworkshopdevoted solelytothistopic.TheydrawonongoingworkoriginatingfromNoamChomskyin theearly1990sthroughthepresentday,leadingtoperhapsthedominantapproach incontemporarygenerativegrammar,theMinimalistProgram(MP).Thisapproach leftopenacentralquestion:howcanwebuildcomputerprogramsthatmapfrom external sentencesbackto internal representationsthatfollowMPlinguistictheories, comprisingpartofthebroaderprogramofviewinglinguistictheoryasfullyintegrated intohumancomputationalcognitive(andbiological)science?Theaimofthisbookis toanswerthisquestion.
AcentraltenetoftheMPisthataccountsofhumanlanguageoughttobegrounded onthesimplestpossiblelogicallynecessarysetofassumptions.Forexample,hierarchicalsyntacticstructureneedonlybebinary-branching,ratherthanternary-branching, sinceempirically,binary-branchingseemstosuffice;further,thispropertyitselfcan beseentofollowfrommorebasicprinciples,asacorollaryofthebasiccombinatory operationsofMinimalistGrammars.However,despitethisapparentsimplicity,buildingparsersforsuchsystemsturnsoutnotbenotsosimple.Infact,itisoneofthe greatsurprisesofthemodernstudyofhumanlanguagethat,astheIntroductionthat followsexplains,thestandardcomputationaltoolkitforparsingthestructureof,say, programminglanguages fails outrightwhenappliedtothe“simpler”caseofhuman languages.
Mostofthechaptersthatfollowdescribethewaysinwhichwemustextendour computationaltoolkittocoverhumanlanguage.Therestextendtheseinsightstoother staplesofcomputationalcognitivescience,suchasintegratingsuchparsersintomodels ofhumansentenceprocessingbehavior,evendowntothelevelofbrainactivity.
InthisregarditisimportanttostressthattheMPisindeeda program,aparticular methodologicalapproachtogenerativegrammarandhumanlanguage,nota theory. Moreover,itisastill-developingprogram.Inpracticethismeansthattherecanbe severaldistinctstrandsorchoicesinhowtorealizethebasic“simplicity”tenets oftheMP.Thereaderwillseethisreflectedinthedistinctwaystheauthorshave approachedimplementation—someformal,somenot,butallwithinthegeneralspirit ofminimalism.Wehopethattheresultingdiversityandthesuccessintacklingthe thornycomputationalissuesinspireanewgenerationofresearcherstocontinueto explorehowlinguisticsandcomputationcanbemadetofittogether.
RobertC.Berwick
EdwardP.Stabler October,2018
Minimalistparsing
RobertC.BerwickandEdwardP.Stabler
TheMinimalistProgramhasinspireddiversestudiesofparsingwithdiversegoals: toclarifythecommitmentsofparticularinformallypresentedlinguistictheories;to explorehowdifferenttheoriesfittogether;tomakeexplicitthefundamentalmechanismsofminimalisttheories;andtoidentifyarangeperformancemechanismsthat couldberelevantforpsycholinguisticmodels.Allofthesegoalsarerepresentedinthe contributionstothisvolume.
Thisdiversityofgoalsisnotsurprising.TheMinimalistProgramisaloosecollection oflinguistictheoriesinspiredbytheworkofNoamChomskyandmanyothers beginninginthemid-1990s.While“parsing”inthiscontextreferstotheassignmentof linguisticstructuretosentences,itisimportanttodistinguishwhat,exactly,thismeans. Aninterestinparsingcouldaddressdiversequestions:howlinguistictheoriesdefine structure;howalgorithmscanassignstructuretoacousticorperceivedrepresentations ofwhathasbeenheard;orhowstructurecanbeassignedinmodelsofhuman linguisticabilities.Andwhenwerefertolinguisticstructure,wecouldmeanall analysescompatiblewiththegrammar,orwecouldmeanjustthoseanalysesthat wouldbe(orwouldprobablybe)assignedbyacompetentspeakerinaparticular discoursecontext.Sowhenthetitleofthisvolumeisunpackedevenslightly,we seethatitcoversawiderangeofresearchprojects,someofwhicharerepresented here.Nevertheless,allthedifferentgoalsmentionedaboveoverlap.Inthesediverse proposalsthereareoverarchingthemes,withanintelligiblehistoryandapromising future.Itiseasytoforgetthatcommongroundinourdailyskirmishes,soaperspective unitingmanyoftheseprojectsissketchedhere.
Afoundational,unifyingperspectiveisprovidedinthenextsection.Thisvolume extendsthatperspectiveinvariousways,brieflyoverviewedinthesection1.2.And section1.3providessomeadditionalformaldetails,withattentiontotranslating betweensomeofthevariousnotationsused.
1.1Aperspectiveonlanguageandparsing
Thissectionpresentsasketchofhowsomesomefamilarlinguisticresultsrelateto parsing.Focusingonwhatismostrelevantforsituatingthecontributionsofthis volumeinaroughandreadyway,verymanyimportantaspectsofcurrentlinguistic theoryareputtooneside,andwecanbequitebrief.
MinimalistParsing.Firstedition.RobertC.BerwickandEdwardP.Stabler(eds.)Thischapter©RobertC. BerwickandEdwardP.Stabler2019.Firstpublished2019byOxfordUniversityPress.
Hierarchy. Thearithmeticterm2 + 3 ∗ 4isconventionallyassumedtodenote thesamethingas (2 +(3 ∗ 4)),andparsersforcalculatorsandothersystemsusing arithmeticaretypicallyexpectedtofindtheparenthesizedstructure.Notethatthe structureishierarchical,withonearithmeticterminsideofanother,and,inthis case,thestructurebranchestotheright,withthemorecomplexsubconstituenton therightside.1Asubstantialmathematicaltheoryincomputerscienceaddressesthe questionofhowthiskindofparsingproblemcanbesolved,mappingthesymbol sequencesofcontext-freelanguagestoappropriatehierarchicalstructures.2Tosaythat theinfinitelanguageofarithmetichasacontext-freegrammar(CFG)meansthatthe categorizationofexpressionsneededforarithmeticisfinite;therulesofcombination needtoknowonlywhichoffinitelymanycategoriesanexpressionfallsinto.Theset ofwell-formedhierarchicalCFGderivationsforsentencesofarithmeticis“regular” (moduloasimplerenamingofcategories)inthesensethatitcanberecognizedby asimplefinite-statetreeautomaton(Thatcher1967;Comonetal.2007).Fromthis sortofglobalperspective,aperspectivethatisprobablymorefamiliartothecomputer scientistthanthelinguist,itisnothardtoshowthatthecontext-freelanguagesthat aretheyieldsoftheseregulartreelanguagesareclosedwithrespecttoregularstring transductions.3Thatis,whenthestringsofacontext-freelanguagearealteredbya finitestatetransducer,theresultinglanguagecanalsobedefineddirectlybyaCFG. Turningtohumanlanguage,foracompetentEnglishspeaker,thesentenceBopraises Cal isusuallyassumedtohaveahierarchicalstructure (Bo(praisesCal)).Asinthe arithmeticcase,thisstructurehasaphrasewithinaphrase,andagainithappensthat themorecomplexsubtermisontheright.Onemightthinkthatthealgorithmsfor parsingcontext-freelanguageswouldcarryoverimmediatelytodeliverthestructures forhumanlanguages,butinaperhapssurprisingdiscovery,thisdoesnotwork,as notedinChomsky(1957;1955)andverymanyotherstudies.Humanlanguagepresents manyessentialfeaturesnotfoundinsimpleartificiallanguageslikearithmeticoreven programminglanguages.
Movement. Oneprominent,evenbasic,featureofhumanlanguagenotreflected inartificiallanguagesisthatphraseswithparticulargrammaticalrolescanappearin variousstructuralpositions.Forexample,inthetopicalizedsentence Cal,Bopraises, manyofthegrammaticalrelationsarethesameasinthepreviousexample,sothelatter
1Tobesure,thisisnotnecessary.Obviouslywecoulddefineahigherorderfunction f suchthat,forany x,y, thevalue f(x,y) isafunctionthatmapsanotherargument z to x+(y∗z).Sincethisisexactlytheresultobtained bythetraditionalcalculation,whynotfindthestructure f(x,y)(z),whichhasthemorecomplexsubtermonthe left?Certainly,bydefinition,thelatterapproachisfineifthegoalissimplytodenotetheintendedvalue,but thereisareasonthatmathteachersinstructchildrentodoacalculationthatcorrespondstotheright-branching calculation.Notonlyis f inahighertypethan + and ∗,butalso,althoughbothapproachesinvolvetwofunction applications,unpackingthedefinitionof f involvesmorefunctionapplicationsinvolving + and ∗.Soitiseasyto identifyvarioussensesinwhichtheformerstructureis simpler.Thisinturninvitesalongerdiscussionofhow thenotion simplicity mightbecashedoutincognitiveterms—perhaps“simpler”meanseasiertoparse,produce, orlearn.Andifwearemodelingwhathumansdo,thereisanempiricalquestionaboutwhichaccountbetterfits thefacts.Wewill,however,leavethisimportantdiscussionforanotheroccasion.
2Seee.g.AhoandUllman(1972);Valiant(1975);Nijholt(1980);SippuandSoisalon-Soininen(1988;1990); Leermakers(1993).
3Theyieldofanorderedtreeisthesequenceofitsleaves(itsterminalelements),inorder.
1.1 aperspectiveonlanguageandparsing3
structuremaybesomethinglike(Cal(Bo(praisesCal))),usingthestrike-outtoindicate thattheconstituent Cal ispronouncedonlyinitsfirstappearance,nowattherootand pronouncedontheleft,butstilltheobjectoftheverb.OnecoreideaofMinimalism, aimingforthesimplestaccountpossible(Chomsky1995a),isthattheoperationthat buildsthislatterstructuremaybejustliketheoperationsbuilding (Bo(praisesCal)), exceptthatanadditionalstepselectssomethingalreadyinthestructure(namely, Cal), mergingitagainontheleft,attheroot.
Isthereasimplewaytoextendformalgrammarsandparserstoallowoperations likethat?Theminimalistgrammars(MGs)ofStabler(1997)startwithacategorybasedmergeoperation—similartoacontext-freerulebutappliedbottom-up—and extendittoallowaconstituentalreadyinthederivationtomovefromitsoriginalsite tomergeattheroot.⁴ThesegrammarspreservesomefundamentalpropertiesofCFGs: parsingwithMGsisformallytractableevenintheworstcase(FowlieandKoller2017; Harkema2000);thecategorizationofexpressionsneededforanyMGisfinite;andthe setofderivationtreesforanyMGisregular(Kobeleetal.2007).TheMGderivation treelanguagesalsohavethemoresurprisingpropertythattheyare(moduloasimple categoryrenaming)closednotonlywithrespecttoregulartransductionsontheir yieldsbutalsowithrespecttointersectionwithotherregularsetsoftrees(Kobele2011; Graf2011).Ofcourse,MGsareaverysimpleapproximationtowhatweareaiming for,buttheyprovideausefulstartingpoint,allowingelegantmodulardescriptionsof phenomena.Itisconceivablethatatleastsomeoftheirfundamentalpropertieswill continuetoholdaswemoveclosertohumanlanguage.⁵
Biolinguistics. Theideathatthetheoryoflinguisticstructureandparsingprovides thebasisforacognitivescience,asacomponentofhumanpsychologyandbiology, isaanotherdistinctivestrandoftheMinimalisttradition(Chomsky1965;1995b; 2015a;BerwickandChomsky2011;2017).ThereisevidencethatacompetentEnglish speaker’sunderstandingofasentenceinvolvesrecognizinghierarchicalrelationssimilartothosethatourgrammarsdefine.Time-coursestudiesandmemoryinterference effectsconfirm,asonewouldexpect,thatthecontinuousanddynamicalmechanisms forstorageandcomputationinhumancognitionareratherdifferentfromthediscrete tapes,stacks,queues,andmatricesthatcomputerscientistsusuallyassumeintheir parsingalgorithms,buttheneuralarchitecturemustrealizesomethingsimilartoour
⁴Detailsareprovidedinsection1.3,orseee.g.Stabler(2011)foramorethoroughoverview.
⁵Sincedependencyparsingiscurrentlysopopularinnaturallanguageprocessing,itisworthnotingthatif by“dependencygrammar”wemeanagrammarthatspecifiesforanytwopronouncedheadswhetheronecan dependontheother,thendependencygrammarsareexpressivelyequivalenttoCFGs(Gaifman1965).Those grammarscanbeextendedtoaformthatisequivalenttoLCFRSsandhencetoMGs(KuhlmannandMöhl 2007).Andif“dependencygrammar”isusedinaloosersensetorefertoanygrammarwhosederivationscan beexactlyrepresentedbydependenciesbetweenheads,thenMGsaredependencygrammarstoo(Stabler1999; Salvati2011a;Bostonetal.2010).ThedependencyrepresentationofMGissometimesuseful.Butthereisalso “data-driven”dependencygrammar,alinguistictraditionwhichtypicallyusesveryfewtypesofdependenciesand leavesparsingtoastatisticalmodelthattypicallyusesaverylargesetoffeatures—seee.g.deMarneffeetal.(2014) andreferencescitedthere.Theseprojectsmainlyaimtofindusefulstatisticalmodelsthataresimpleenoughtobe easilytrainablewithavailabletechnologiesandavailabledata,deliberatelyignoringperformanceofthemodelon datathatisnotrelevanttoapplicationgoals.Theengineeringsuccessofthislasttraditionisreallywhathasbrought dependencygrammarintothelimelight,whileseeminglyputtingasidethetraditionalconcernsofexplanatory adequacyintermsoffixingtheproperstructuralrelationshipsofsentencesoraccountingforlanguageacquisition.
parsingstrategies.Weknowratherlittleabouttheneededneuralmechanisms,but therearesomespeculativeproposals.⁶
Efficiency,determinism,andlocality. Forpreciselydefinedformalgrammarsand parsingproblems,thereareempiricalquestionsaboutwheretheyfailasaccounts ofhumanlanguages.Buttheydefinepreciseparsingandacquisitionproblems.For example,evidenceseemstosuggestthat,atleastinawiderangeofcasesoffluent languageunderstanding,eachwordisintegratedintoasinglestructureassoonasit isheard.Sowecanaskwhether,givenourcurrentapproximatebutformalgrammars forhumanlanguage,whethertheparsingproblempresentedbyapreciselydefined grammarmakesthatkindofhumanabilityexpected—orisitsurprising?Thatis,is theparsingproblemforourapproximationsimpleenoughthatitshouldbesolvable inthelineartimeallowedforeachword,orisitmoredifficultthanthat?Thequestion isstillvague,especiallybecauseitisnotquiteclearwhichaspectsofhumanlanguage understandingcountaspartoftheparsingproblem.Wecanmakesomepreliminary observationsabouttheissue,basedonthesimpleformalmodelsalreadymentioned. First,itiswellknownthatforanyCFGwecancalculateallpossibleparses(representing themcompactlyina“chart”or“matrix”)injustlessthancubictimeintheworstcase. Thatis,wecancalculatethechartforan n-wordsentenceusingnomorethan O(n2 37) basiccomputationalsteps.MGlanguagescanbeparsedinatworst O(n2k+3),where k isthenumberoflicensorfeatures.⁷Thesecomplexityresultsmayseemdiscouraging. If,whenweuseanadequategrammarofthelanguage,thenumberofstepsrequiredto parseexamplesthatarereadilycomprehensibleevenwhentheexamplesarefairlylong growscubicallyorworsewiththelengthofthesentence,thatcouldbehardtofitwith ourapparentabilitytoidentifysyntacticrelationsonaroughlyword-by-wordbasis. Butforunambiguouscontext-freelanguageslikearithmetic(eitherwithparenthesesor withrulesaboutoperatorpriority),parsingrequiresonlylineartime,andsimilarlyfor MGlanguages.Iftheparsingstepsaredeterministic(ornearlyso),lineartimesuffices.⁸ Someattentionhasbeengiventotheideathathumanparsing,inadisambiguating context,isalsodeterministic,buildingasinglesyntacticstructurewithasequenceof stepsthatneverdeletesanyearlierassignedstructure.Marcus(1980)andBerwick andWeinberg(1984)proposethatdeterministicparsingforhumanlanguagesis possibleifacertainkindoflookaheadisallowed,alookaheadthatisnotfinitely boundedinthestringbutthatisneverthelessfinitelyboundedintermsofthenumber ofstructuralelementsitneedstoconsideratanypoint.Furthermore,theyexplore thepossibilitythatthatthisboundedlookaheadprovidesafunctionalexplanation oflocalityrestrictionsondisplacementoperations.Theseproposalsfaceempirical
⁶E.g.beimGrabenandGerth(2012);GerthandbeimGraben(2009);Cho,Goldrick,andSmolensky(2017); HaleandSmolensky(2006).
⁷ThedifferentkindsoffeaturesusedbyMGsaredefinedandrelatedtovariousnotationsinsection1.3.
⁸NotethatMGparsingdoesnotspecifybindingrelationsandotheraspectsoflanguagethatareknowntobe significantlymorecomplex—seee.g.Ristad(1993);Bartonetal.(1987).GrafandAbner(2012)pointoutthat althoughproblemsincorporatingthefullrangeofbindingphenomemamaybecomplex,acertainsubsetofthem remaintractableandenforceableinanMGframework.
problems,asallcurrentaccountsoflocalitydo,⁹butsomebasicarchitecturalfeatures ofthesesystemsfindtheirwayintoalmostallmoderntheories.
Itisnoaccidentthattheassumptionofafinitelyboundeddomainformovement operationsinthoseearlierworkshasacloseanaloginMGs.TheproposalinStabler (1997)isthatatmostonelicensorofeachtypecanbethefirstfeatureoftheheads inanMGderivation.Thisiscalledthe shortestmoveconstraint (SMC)becauseit means,forexample,thatawh-phrasemustmovetothenearest+whlandingsite, predictingcertainkindsofwh-islands.Sincethetotalnumberoflicensortypesis finitelyboundedinanygrammar,theSMCimmediatelyentailsthatonlyfinitely manypossiblemovementoperationsarepossibleatanypointinaderivation.The consequencesofthisassumptionfordeterministicparsingwithlookaheadhavenot beenfullyexplored,1⁰butaswithearlierproposalsaboutboundsonmovement,we canseeimmediatelythattheSMCfacesempiricalproblems.Forexample,howcanthe SMCallowattestedcasesofmultiplewh-movement?Therearepossibleresponsesto thatparticularchallenge(GärtnerandMichaelis2010;2007),butthecorrectanalysisis stillunclear,andforalllinguistictheories,manypuzzlesaboutlocalityrestrictionson movementremain.11Salvati(2011a)hasestablished,though,thatiftheSMCissimply removed,theparsingproblemforMGlanguagesbecomessubstantiallyharder—as difficultasprovabilityinmultiplicativeexponentiallinearlogic,whichisintractable (LazićandSchmitz2014).
1.2Thisvolume
FongandGinsberg describenotaparserbutanimplementedsystemthatcomputes derivationsaccordingtoablendofproposalsfromChomsky(2001),Pesetskyand Torrego(2001),Gallego(2006),Kayne(2002),andSobin(2014),asystemwhichisable toprovidesophisticatedtreatmentsofawiderangeofexamplesfromtheliterature. ComparedtothesparebasicsofMGs,theirsystemmayseemcomplex,atleastat first.Internalandexternalmergeareassumedtoformsetswithtwoelementsinstead oftreeswithtwodaughters,andathirdcaseofmergeisusedtoformnotsimple setswithtwoelementsbutanorderedpair.Agreeandprobe-goaloperationsthat valuefeatures,alabelingoperation,theta-markingandfeatureinheritancecanapply.12 Lettingtheseoperationsapplyfreelytoasetoflexicalitemswouldproducemany resultsthatshouldbefilteredout,sotheoperationsaretightlyrestrictedinamachine thatactsonaonatriplecomprisingasyntacticobject(SO),astack(!FStack)of unvaluedfeatures,andalist(LIs)oflexicalitemsandotherLIs,whereembeddedLIs containthepartsofsubconstituentstobederived,puttingtheresultsbackintothe
⁹Seee.g.Fodor(1985)foracriticalreviewofthoseproposals. 1⁰KallmeyerandMaier(2015)exploreLRparsingforLCFRSs,anexpressivelyequivalentgrammarformalism thatispreciselyrelatedtoMGsbyMichaelis(1998).
11Overviewsarepresentedine.g.Szabolcsi(2006),Boeckx(2012),denDikkenandLahne(2013). 12Featuresarevaluedbyunification.Seee.g.AdgerandSvenonius(2011).
containinglist.Finally,anoracle(thelinguist)initiallyputstheelementsintoanorder thatallowseachderivedSOtocombinewiththefirstelementofLIs,andadecision procedurePdecideswhichgroupsofoperationsshouldapplyateachpoint.Fong andGinsbergdispensewiththefeaturecheckingideaofearlyminimalisminfavorof constraint-drivenandfreedisplacement,tobefilteredbypossiblyexternalconditions downstreamfromthemergesteps,includingforexamplerequirementsofa“Labeling algorithmatTransfer”whichisnotfullydescribedhere.Themechanismsintroduced by FongandGinsberg aredeployedinlinguisticanalysesdescribedby Ginsberg andFong,withparticularattentiontoexpletives,that-traceeffects,andrelativeclause constructionswithpropertiesthatareexplainedinpartbyeconomyconditions.
OfalltheconstraintsproposedintheMinimalistProgram,thetrans-derivational economyconditions–thosethatruleoutoneanalysisbasedonthepossibilityof anotherone–seemmostcomputationallydifficult,andmostunlikeanythinginthe MGformalism.Nevertheless,Graf(2013)showsthat,inspiteofappearances,most economyconditionsproposedbylinguistsareinfacttractableandconsistentwith MGassumptions.Manytrans-derivationalconstraintscanbereformulatedsothatthey achieveexactlythesameeffectwithoutcomparingderivations.Quiteafewconstraints ofthiskindareanalyzedbyGraf(2013),butnottheparticularsetadoptedbyFongand Ginsberg,sothecomplexityoftheseremainsanopenquestion.
ThisclarificationoftheoreticalproposalsinworklikeFongandGinsberg’sisan essentialprerequisitetoassemblingarigorousformalmodelofthetheory,aformal modelthatwouldallowconclusionsaboutwhichkindsoflanguagesaredefinable,and onethatwouldposedefiniteparsingproblemswhosecomplexityandimplementation wecanstudy.Soforthe(possiblyrare)readerwhostudiesthisvolumefrombeginning toend,itisgoodtobeginwiththesetwostudiesthatstartclosetothelinguistictheory; theyremindusofthedistanceweneedtogofromsimplerformalmodelstocomplete linguisticdescriptions.
Yu observesthatrecentworkcontinuestoconfirmtheobservationfromChomsky andHalle(1968)thatprosodicdomainsdonotcoincidewithsyntacticconstituency, andsosheproposesaworkingmodelofthesyntax/prosodyinterface,basedonMGs forthesyntaxandusingtheoptimality-theoreticMatchconstraintofSelkirkand othersforthemismatchedprosody.Thismightseemlikeadifficultmarriage,butYu showshowitmightwork.Sheobservesthat,iftheprosodicandMatchconstraints canbeenforcedwithonlyfinitecounting(asitseemstheycanbe),thentheeffect oftheOTinterfacecanberepresentedwithafinite-statestringtransduction.That transductioncanbeintegratedintostandardbottom-upMGparsinginsuchaway thatsyntactic/prosodicmismatchesarepenalizedbutallowedwhennobetteranalysis survives.
Kobeleobservesthatellipsisseemstoinvolvethedeletionofunboundedamountsof material,andsoitcouldseemthataddinganysuchoperationtoMGsoranyotherformalismwouldmakeparsingintractable.Butusingapro-formtheory,wheretheproformsat“deletion”sitestakeMGderivationantecedents,thesyntacticandsemantic effectsofantecedentmaterialcanbepredicted,whileefficientparsingispreserved.To setthestage,hepresentsakindofsequentcalculusforhypotheticalreasoningabout
MGexpressions.Ahypothesisintroducesakindofholeinaderivation.Whenthe derivationcontainingtheholeissilenced—allphoneticcontentsdeleted—wedefine amappingfromassumptionswithcertainfeaturestoanexpressionwithcertain, usuallydifferent,features.Thesemappingsarethepossibleellipsisoperations.Headds finitelymanyoftheseoperationstoMGs.AsKobelesaysofthesepro-formoperations, “Buildingupanexpression,andsilencingallofitexceptforsomemovingpieces,is reconceptualizedasbuildinganexpressionwhichismissingsomeparts,andsilencing allofit.”Whenthenewoperationsareinterpretedbyantecedentderivationswiththe rightfeatures,thenweobtainanappropriateinterpretationoftheellipsisconstruction, aswasproposedmoreinformallyinKobele(2015).Withthisapproach,theparsing problemistodeterminewhetheragivensequenceoflexicalitemshasaparse(i.e. anypositivenumberofparsesofthespecified“start”category)usingthebasicMG operationssupplementedwiththefinitelymanyellipsisoperationsthatthegrammar allows.Withthisapproach,itiseasytoseehowparsingstaysefficient.
Hunter beginswithareviewofpsycholinguisticstudiessupportingtheintuitive ideathatwhenapossibletraceorgapsiteisencountered—theoriginalpositionsof internallymerged(“moved”)elements—thelistenerengagesinagap-fillingprocess thattakessomeeffort.Afterconsideringatop-downparserforMGsthatdoesnot predictthateffort,Hunterproposestoformulatealeft-cornerparsingstrategyforMGs. Thebasicleft-cornerideaisthatthefirstconstituentofaphraseisprocessedbottomup,butthenitssisters,ifany,arepredictedtop-down.Thismaysoundsimple,butitis trickytodefineleft-cornerparsingoperationsthataresoundandcompleteforMGs— “sound”inthesensethatanyderivationfoundis,infact,aderivationallowedbythe grammar,and“complete”inthesensethat,ifthegrammarallowsaderivation,thereis asequenceofparseroperationsthatwillfindit.Huntertakessomefirststepstowards suchaparserhere,andshowshowithasthepotentialtomodelthe“activegap-filling” strategythatpsycholinguistshaveproposed.
LiandHale describeamoreabstractperspectiveontheeffortofhumanparsing, askingwhichlinguisticstructuresandparsingstrategiespredicttheeffortindicatedby fMRIstudies.Theydefineawidevarietyofparsertime-coursecomplexitymetrics,and thenuseastepwiseregressiontofitamodeltofMRItimecourseresultsfromBrennan etal.(2016).ExaminingthecoefficientsforthelinguisticpredictorsoffMRIactivity, theyfindanumberofconnections,includinganeffectofwhattheycall“bottom-up nodecounts”inMGs,overandabovethenodecountsofsimilarCFGformulations— wherethebottom-upnodecountisthenumberofparsingstepsbetweensuccessive wordsinbottom-upparsing.Theactiveregionssupportamodelinwhichtemporal lobeprocessingisinvolvedinbothphrasestructuresyntaxandintherecognitionof distributionalsemantics.
1.3Minimalist-inspiredformalisms
Forreaderswhowanttounderstandthecontributionsofthisvolumeincomplete detail,thissectionprovidesalittlebackgroundandkeystotranslationsbetweenthe
variousnotations.WeuseStabler(2011)asastartingpointbecausethenotationthere isamongthesimplest,andthatnotationisadoptedbyseveralofthechaptershere. Somereadersmaywanttoskipthissection,possiblyreturningtoitasneededfor clarifications.
MGfeatures inStabler(2011).AnMGisgivenbyafinitelexicon,whichassociates eachphoneticformwithasequenceoffeatures.Thebasicfeaturescomeinfourtypes: categories={D,N,V,A,P,...}
selectors={=D,=N,=V,=A,=P,...} licensees={-wh,-topic,-focus,-case,...} licensors={+wh,+topic,+focus,+case,...}
ForeachcategoryXwehavethecorrepondingselectorfeature=X,andforeachlicensee feature–xwehavethecorrespondinglicensorfeature+x.Andtospecifyalanguage, asetofstrings,aparticular“startcategory”ischosen;thelanguageisthewholesetof sequencesofphoneticformsthathavecompletedderivationsthatincludethatcategory feature.
ExampleMG1. Considerthefollowingminimalistgrammar,alexiconwithtwelve elements,wherecomplementizerCisthestartcategory.Weindicateeachpairingof phoneticformwithafeaturessequencewithtwocolons::forreadability:
(MG1)Cal::Dpraises::=D=DV ε ::=VC Bo::Dknows::=C=DV ε ::=V+whC student::Nthe::=ND ε ::=V+focC teacher::Nwhich::=ND–wh ε ::=DD–foc
Wewillrefertoeachlexicalitembyitsphoneticform.Intherightcolumn,the ε indicatesphoneticallyemptyelements,sowewillcallthemC,C+wh,C+foc,andD foc, respectively.
Inthisgrammar,thelexicalitem praises hasthreefeatures.Thatsequenceofthree featuresindicatesthat praises willmergewithtwophrasesofcategoryD(whichwecan thinkofasitsobjectandsubject,respectively)tocompleteaphraseofcategoryV.And, againreadingthefeaturesfromlefttoright,thelexicalitem which selectsanNtoform aphraseofcategoryD,andtheadditionalfeature–whindicatesthatitcanbelicensed ina+whposition.Finally, ε istheemptysequence,usedtoindicatethesilentelements intherightcolumn.13Anexamplederivation,justbelow,willillustratehowallthese featuresworktogethertodefineasetofstructureswhoseleavesformasetofsequences ofheads,alanguage.
MGmerge inStabler(2011).Ratherthanimposinglinearorderonaderived structurewithseparateprinciples(thoughthatcaneasilybedone),let’sspecifyit asaside-effectofthesinglebasiccombinatorialoperation,merge.Afirst-merged elementisalwaysattachedtotherightoftheselectinghead(asthe“complement”), andsubsequentmergedelementsareattachedtotheleft(as“specifiers”).Intheformal
13EmptycategoriesarefamiliarinChomskyansyntaxbutareoftenmisunderstoodbyothertraditions,even thoughotherlinguistictraditionsoftenhavesomeformoftype-changingruleswithsimilareffects.
specificationofthemergerule,itisconvenienttoseparatethecasesofexternalmerge andinternalmerge,whereinternalmerge(“movement”)isdistinguishedbythefact thatitselectssomethingalreadymerged.Thestagehasbeensetforthisbydividingthe categoryfeaturesfromthelicensees.Twoelementscanmergeonlyiftheheadfeatures ofthefirstbeginwithaselector=Xorlicensor+x,andtheheadfeaturesofthesecond beginwiththecorrespondingcategoryXorlicensee–x.Whentwoelementsmerge, insteadofputtingthetwotogetherinaset,wewillputthemintoatreewithanarrowat therootthatpointstotheselectingelement,andwewilldeletethefeaturesinvolvedin themergestep.(Forreasonsthatwillbeirrelevanthere,inderivedstructures,Stabler (2011)changesthedoublecolon::pairingnotationtoasinglecolon.)Toimposea kindofeconomy,theSMC,mentionedabove,restrictsinternalmergetojustthose structuresinwhichnotwofeaturesequencesbeginwiththesamelicensee.Finally,a derivationofcategoryXis complete ifXistheonlyfeatureleftinthestructure.The languagedefinedbythegrammaristhesetofyieldsofthecompletedderivationsofa specifiedcategory(the“startcategory”).Thatcompletesthespecificationofminimalist grammars.
Notethatwhileexternalmergehasadifferenteffectdependingonwhetheritisa firstmergeornon-firstmerge,internalmergehasnofirst-mergecase,becauseit requiresastructureinwhichthingshavealreadybeenmerged.Andwhileexternalmergeisbinary,internalmergeisaunaryfunction.Thestructuraleffectof internalmergeisidenticaltonon-firstexternalmerge,butthesingleargumentof internalmergealreadycontainsthephrasetobemerged.
ExamplederivationfromMG1. Noticethatsince Cal onlyhasonefeature,itis alreadyacompletedderivationofaD.Butlet’sconstructacompletederivationofa structureofcategoryCtoillustratehowmergeworks.Sincethefeaturesofwhichbegin withthefeature=N,andsincethefeaturesofstudentbeginwithN,wecanmergethem, deletingthefeatures=NandN:
(1) m(which, student) = < student which:D wh
Herewewritemformerge.Notethattheheadofstructure(1)—indicatedbythearrow attheroot—hasasequenceoftwofeaturesleft,namely:D–wh.Sincestructure(1)has firstfeatureD,itcannowbeselectedby praises,deletingthe=DandD.Notethatthis isagaina“first-merge”fortheselectinghead praises:
(2) m(praises, 1) = < praises: = D V < which: wh student
Ournextstepisanon-firstmerge,sothemergedelementisplacedontheleftofthe selector:
