资源描述：
《Graph-structured_Stack_and_Natural_Language_Parsing_Abstract》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Graph-structuredStackandNaturalLanguageParsingMasaruTomltaCenterforMachineTranslationandComputerScienceDepartmentCamegie-MeUonUniversityPittsburgh,PA15213Abstractruninpolynomialtime.Thisistrueforalloftheparsingsystemsmentionedabove;ATN,shift-reduceAgeneraldeviceforhandlingnondet
2、erminisminstackparsing,principle-basedparsing,andperhapsanyoperationsisdescribed.Thedevice,calledaotherparsingsystemswhichemployastack.Graph-structuredStack,caneliminateduplicationofoperationsthroughoutthenondeterministicprocesses.Thenextsectiondescribesthegraph-structureThispap
3、erthenappliesthegraph-structuredstacktovariousnaturallanguageparsingmethods,includingstackitself.Sections3,4,5and6thendescribetheATN,LRparsing,categodalgrammarandprinciple-useofthegraph-structuredstackinshift-reduceLRbasedparsing.Therelationshipbetweenthegraph-parsing,ATN,Catego
4、rlalGrammars,andprinciple-structuredstackandachartinchartparsingisalsobasedparsing,respectively.Section7discussesthediscussed.relationshipbetweenthegraph-structuredstackandchart[5],demonstratingthatchartparsingmaybe1.Introductionviewedasaspecialcaseofshift-reduceparsingwithAstac
5、kplaysanimportantroleinnaturallanguageagraph-structuredstack.parsing.Itisthestackwhichgivesaparsercontext-free(ratherthanregular)powerbypermitting2.TheGraph-structuredStackrecursions.MostparsingsystemsmakeexplicituseInthissection,wedescribethreekeynotionsoftheofthestack.Augmente
6、dTransitionNetwork(ATN)graph-structuredstack:splitting,combiningandlocal[10]employsastackforkeepingtrackofretumambiguitypacking.addresseswhenitvisitsasub-network.Shift-reduceparsingusesastackasapdmarydevice;sentencesareparsedonlybypushinganelementontothestack2.1.SpUttlngorbyredu
7、cingthestackinaccordancewithWhenastackmustbereduced(orpopped)inmoregrammaticalrules.Implementationofpdnciple-basedthanoneway,thetopofthestackissplit.Supposeparsing[9,1,4]andcategodalgrammar[2]alsooftenthatthestackisinthefollowingstate.Theleft-mostrequiresastackforstodngpartialpa
8、rsesalreadybuilLelement,A,isthebottomofthestack
