[PDF] Parser Generation for Interactive Environments Jan Rekers

View - Download Parser Generation for Interactive Environments Jan Rekers

Previous PDF

Next PDF

ParserGenerationforInteractiveEnvironmentsAcademischProefschriftterverkrijgingvandegraadvando ctoraandeUniversiteitvanAmsterdam?opgezagvanRectorMagni?cusProf?dr?P?W?M?deMeijer?inhetop enbaarteverdedigenindeAuladerUniversiteit?OudeLuthersekerk?ingangSingel411?ho ekSpui??op31januari1992?desnamiddagste15?00uur?do or

JoanGerardRekersgeb orenteAmsterdam

NotesPartialsupp ortforthisresearchwasreceivedfromtheEurop eanCommuni?tiesunderESPRITpro ject348?GIPE?GenerationofInteractiveProgram?mingEnvironments?andunderESPRITpro ject2177?GIPEI I?GenerationofInteractiveProgrammingEnvironmentsI I??Partialsupp ortforthisresearchwasalsoreceivedfromtheNetherlandsOrganizationforScienti?cResearch?NWO?pro jectIncrementalProgramGenerators?Partsofchapter1?GeneralizedLRParsing?haveb eenpublishedas?BHK89?chapter8??Thesepartsarereprintedwiththekindp ermissionofAddison?Wesley?Chapter2?IncrementalParserGeneration?isjointworkwithJ?HeeringandP?Klint?Ithasb eenpublishedas?HKR89?andas?HKR90?andisreprintedwiththekindp ermissionofIEEE?Chapter3?RestrictingaParsertoaSubgrammar?isama jorrevisionof?Rek89??Chapter4?SubstringParsing?isjointworkwithWilcoKo orn?Ithasearlierb eenpublishedas?RK91a?andas?RK91b??Chapter6?ImplementationofSDF?has?inanearlierform?app earedaspartofdeliverableD1?3ofthe3

rdreviewrep ortoftheGIPEI Ipro ject?CoverdesignbyOkkieMathijsen?

AcknowledgementsIamverygratefultoPaulKlint?mypromotor?Healwaysstimulatedmeandpushedmeintherightdirection?Becauseofthetrusthehadinmefromthestart?thisdissertationwasbroughttocompletion?IalsowanttothankJanHeeringforhismanycontributionsandhisendlesspatiencewithmyEnglish?WorkingatCWIwasverypleasant?esp eciallyb ecauseofthekindcol?leaguesIhad?Withoutlistingthemall?IwouldliketomentionPaulHen?driks?EmmavanderMeulen?WilcoKo orn?ArievanDeursen?PumWalters?Jasp erKamp erman?andFrankTip?IwouldalsoliketoaddDominiqueCl?em?ent?fromsema?metra?tothislist?CWI?withitsamplemo dernequipmentandtechnicalsupp ort?providedanexcellentresearchenvironment?Ihaveenjoyedtoimplemementmyre?searchonmo dernworkstations?formattingmythesiswaseasy?andcommu?nicatingwithp eopleallovertheworldthroughMailandNewshashadaveryp ositivein?uenceonmywork?Iwould like tothank therefereesfortheirwillingness toreviewthisthesis:Prof?Dr?J?A?Bergstra?Prof?Dr?F?E?J?KrusemanAretz?Prof?Dr?B?Lang?Prof?Dr?A?Nijholt?andProf?Dr?R?J?H?Scha?Ialsowanttothanksomep eopleforthesupp orttheygaveinmyprivatelife?MoniqueMegens?althoughsometimesreluctant?certainlycontributedtomywork?Apartfromher?Iesp eciallywanttothankmyfather?forwhomIstarteddoingresearchinthe?rstplace?mymother?andmysistersClaarandMan?es?Finally?IwanttothankOkkieMathijsen?whogavethisthesisitsnicejacket?Op drachtVo ormijnvader?diemelietzienho eleukwetenschapkanzijn?Vo orMonique?diemegelukkigno oitenig?growingneglectduringtheworkonthisthesis?heeftto egestaan?

OverviewTheworkdescrib edinthisthesishasb eenp erformedinthecontextoftheEspritpro jectsGIPEandGIPEI I?GenerationofInteractiveProgrammingEnvironments??Thegoalofthesepro jectsistodevelopasystemwhichisabletogenerateinteractiveprogrammingenvironmentsfromformallan?guagede?nitions?Oneoftheob jectiveswastodesignap owerfulandeasy?to?useformalismforthede?nitionofsyntax?Theresultingsyntaxde?nitionformalismSDFhasthefollowingprop erties:?lexical?context?freeandabstractsyntaxarede?nedsimultaneously??SDFsupp ortsgeneralcontext?freegrammars??ithasp owerfuldisambiguationconstructs??ithaslistconstructs??itsupp ortsmo dulargrammarde?nitions??itcaneasilyb ecoupledtosemanticformalismsinordertoprovidethemwithuser?de?nablesyntax??itsimplementationisfullyincremental?and?itprovidesallinformationneededbyasyntax?directededitorforthelanguagedescrib ed?Thisthesisdescrib eshowtheproblemsintheimplementationofSDF?relatedtoparsingandparsergeneration?haveb eensolved?AlthoughtheprimemotivationforthisresearchwastoimplementSDF?weattempttoremainasgeneralasp ossibleandwedealinmostcaseswithBNFgrammarsonly?5

6OVERVIEWAllalgorithmsdescrib edinthisthesisarealsoprovidedinpseudoco de?Thisfacilitatestranslationofthealgorithmsintoarealprogramminglan?guage?Inadditiontothis?app endixAcontainsversionsofthealgorithmsinLISPwhichareavailableviaelectronicmail?aswell?Thisallowsexp er?imentstob ep erformedwiththealgorithmswithoutanyimplementatione?ort?TheparsingalgorithmChapter1?GeneralizedLRParsing?dealswithcho osingasuitableparsingalgorithm?Thisparsershouldacceptgeneralcontext?freegrammars?andshouldb ease?cientasanordinaryLRparseronLR?1?grammars?WehaveselectedaGeneralizedLR?GLR?metho dasthebasisforoursyntacticto ols?ThetheoreticalframeworkforGLRparsingwasintro ducedbyLang?Lan74??andworkedoutforLRparsingbyTomita?Tom85??Ourcontributionisthatweextendedittothefullclassofgeneralcontext?freegrammarsandthatweimprovedthesharingintheparseforest?Infact?wehaveb eenquitefortunateinthatourinvestmentsintheGLRalgorithmremainedofvalueinthesequelofthepro ject?inwhichmoreandmoreelab orateparsergenerationschemesweredevelop ed?whichwerenotforeseenatthetimetheGLRmetho dwasselected?ParsergenerationTheGLRparserneedsLRparsetables?Ageneratorfortheseparseta?blesisstraightforward?astheGLRalgorithmworksquitewellwithsimpleLR?0?parsetables?However?wedonotonlywanttogenerateinteractiveprogrammingenvironments?butwealsowishtoprovidefacilitiesforinter?activegrammardevelopment?Asaconsequencetheparsergeneratorshouldb eincremental?Inchapter2?IncrementalParserGeneration?wedescrib ealazyandincrementalparsergeneratorIPG:?Theparserisgeneratedinalazyfashionfromthegrammar?Thereisnoseparateparsergenerationphase?buttheparserisgeneratedbyneedwhileparsinginput?Iftypicalinputsentencesneedonlyasmallpartofthegrammar?afasterresp onseisachievedthaninthegreedycase:theparsergenerationphasedo esnotintro duceanoticeablede?layandparsingcanstartimmediately?Iftheinputsentencesdonot

OVERVIEW7usethewholegrammar?workissavedonthegenerationpro cessasawhole?Itturnsoutthatincomparisonwithconventionaltechniques?theoverheadintro ducedbythislazytechniqueissmall??Theparsergeneratorisincremental?Achangeinthegrammarpro?ducesacorresp ondingchangeinthealreadygeneratedparser?Partsoftheparserthatarenota?ectedbythemo di?cationinthegrammararere?used?Hence?thee?ortsp entingeneratingthemisre?usedaswell??Thee?ciencyoftheparsingpro cessitselfremainsuna?ected?inthesensethatonceallrequiredpartsoftheparserhaveb eengenerated?theparserwillb ease?cientasaconventionallygeneratedone?Asimilartechnique?forthemorelimitedclassofLALR?1?grammars?hasb eenprop osedbyHorsp o ol?Hor89?Hor90??Mo dulargrammarsNotonlythesyntax?butalsothesemanticsofprogramminglanguagesneedtob ede?ned?Tothisend?thealgebraicsp eci?cationformalismASFhasb eendevelop edintheGIPEpro ject?Themainprop ertyofASF?inrelationtotheworkdescrib edinthisthesis?isthatitisamo dularformalism?ThismeansthatbycombiningASFandSDF?resultingintheASF?SDFformal?ism??SDFhastob ecomemo dularaswell?Thisintro ducesthequestionofhowtogenerateparsersformo dulargrammarde?nitions?Amo dulargrammarconsistsofanumb erofgrammarmo duleseachcontainingasetofgrammarrulesandasetofnamesofothermo dulestob eimp orted?Eachmo dulede?nesa?p ossiblyincomplete?grammar?whichhastob ecompletedbytherulesintheimp ortedmo dules?Amo dulargrammarconsistingofnmo dulesthusde?nesnordinarygrammars?Inmostcases?thesegrammarswillhavelargepartsincommon?Iftheparsersde?nedbythesemo dulesareallneeded?nparserswillhavetob egenerated?Itis?ofcourse?p ossibletouseanon?mo dular parsergeneration techniquetogeneratethesenparsers?Thiswould?however?inducemuchduplicategeneratione?ortforthecommonpartsofthegrammars?Furthermore?amo di?cationinamo duleattheb ottomoftheimp orthierarchywouldcausemanyparserstob einvalidated?Theobviousapproachtoparsergenerationformo dulargrammarswouldb etogeneratean incomplete parserfortherulesin eachmo dule and translate

8OVERVIEWtheimp ortrelationb etweenmo dulestoanimp ortrelationb etweenparsers?Thissolution?however?rulesoutall optimizations available intheLRparsingtechniqueofchapter1and2?astheseoptimizationsarebasedonknowledgeofthecompletegrammar?Inchapter3?RestrictingaParsertoaSubgrammar?weintro duceatechniqueforrestrictingaparsertoasubgrammarofthegrammaritwasgeneratedfor?Theresultingparserb ehaveslikeaparsersp eciallygener?atedforthesubgrammar?butmakingtherestrictionismuchcheap erthangeneratingasp eci?cparser?Bymeansofthistechniqueweareabletosolvetheproblemofgeneratingparsersformo dulargrammars?WedothisbyusingIPG?chapter2?togenerateoneparserfortheunionofallgrammarrulesofallmo dules?andrestrictthisparserntimesaccordingtothengrammarsde?nedbythemo dules?Inthisway?noduplicate generation workisdone?mo di?cations arepro cessedincrementally?andthegeneratedparsersarereasonablye?cient?Adrawbackofthisapproachisthatitisnotp ossibletodevelopparsersseparatelyandcombinethemlateron?However?thislimitationisnotto osevereforthegrammardevelopmentsystemenvisaged?Otherapproachestoparsergenerationformo dulargrammarsarere?p ortedin?Voi86?Kos90??Toourknowledgetherestrictedparsingtechniqueitselfhasneverb eenprop osedintheliterature?Klintappliedthesameideatoscannergeneration?Kli91a??SubstringparsingChapter4?SubstringParsing?addressestheproblemwhetherastringcanb easubstringofsomesentenceinalanguage?Theprop osalsforsubstringparsingrep ortedintheliterature?Cor89?Ric85?onlyworkforalimitedclassofgrammarsandwithsp eciallygeneratedparsetables?Oursubstringparserisbasedongeneralcontext?freegrammarsandusesthesameparsetablesastheoriginalparser?Substringparsingcouldb eusedtosupp ortincrementalparsinginasyntax?directededitor?butwe?nallydecidednottodosoforreasonsofe?ciency?Substringparsingcanalsob eusedfornoncorrectingsyntaxerrorrecovery:ifanordinaryparserdetectsasyntaxerroronsomesymb ol?thesubstringparsercanb estartedonthenextsymb oltodiscoveradditionalsyntaxerrors?

OVERVIEW9SDF

Nowthatallbasicproblemshaveb eensolved?wepro ceedwithSDFitself?Chapter5?FromBNFtoSDF?containsanintro ductiontowritingSDFde?nitionsanddescrib esthedevelopmentofanSDFde?nitionforasubsetofPascal?Ourmainp ointsofinterestarethemo dulardecomp ositionofthegrammar?thereadabilityofthede?nitionandtheb ehaviouroftheeditorgeneratedfromit?SDFhasb eenintro ducedin?HHKR89?andseveralSDFde?nitionshaveb eenpublished?butatutorialonhowtodesignanSDFde?nitiondidnotyetexist?Chapter6?AnImplementationofSDF?describ estheimplementationofSDFitself?Thepurp oseofthischapteristodo cumentthecurrentim?plementation?toguideprogrammerswhohavetodealwithit?andtogiveanimpressionofthesoftwareinfrastructurestillneededtoensureprop erop erationoftheunderlyingalgorithms?Atthetimeof?nishingthisthesis?theGIPEgrouphassuccessfullyimplementedasystemforinteractivedevelopmentofsp eci?cationsintheASF?SDFformalism?Whensp ecifyingaprogramminglanguage?thesys?temincrementallygeneratesaprogrammingenvironmentforit?These?manticfeaturesoftheASF?SDFsystemhavenotb eenaddressedinthisthesis?butmanyofthesyntacticfeaturesinASF?SDFaretheresultoftheresearchdescrib edhere?HowtheimplementationofSDF?tsintheASF?SDFsystemisdescrib edin?Kli91b?Hen91??

10OVERVIEW

Chapter1GeneralizedLRParsingWhichmetho dsforparsergenerationandparsingareb estsuitedforaninteractivedevelopmentsystemofsyntaxde?nitions?InthischapterwearguethataGeneralizedLRparsingalgorithmistheb estchoice?WepresentanenhancedversionofTomita?sGLRalgorithm?andcom?pareitse?ciencywithtwocomp etitors?YACCandEarley?salgorithm?1?1Intro ductionWhichmetho dsforparsergenerationandparsingareb estsuitedforaninteractivedevelopmentsystemofsyntaxde?nitions?WeencounteredthisquestioninthecontextoftheEspritpro jectGIPE?GenerationofInteractiveProgrammingEnvironments??thataimsatderivingprogrammingenviron?mentsfromformallanguagede?nitions?WehaveselectedaGeneralizedLR?GLR?metho dasthebasisforoursyntacticto ols?Thisalgorithmwasoriginally develop edbyTomita?Tom85??Weextendedittogeneral context?free grammarsandimproved thesharing intheparseforestitgenerates?Inthispap erwesummarizetheargumentsforcho osingtheGLRmetho d?wedescrib eourextensionstoTomita?sparsingalgorithmandwecomparethee?ciencyoftheGLRalgorithmwithYACCandEarley?salgorithm?Mostofthesub jectsdiscussedareofgeneralrelevance?butdep endenciesonthesp eci?csettinginwhichthesequestionswereraisedisunavoidable?Inparticular?ourultimategoalhasb eentoimplementSDF?SyntaxDe?nitionFormalism??HHKR89???asp eci?cationformalismforlexical?context?freeandabstractsyntax?However?thepap erdo esnotrequireanyknowledge11

12CHAPTER1?GENERALIZEDLRPARSINGofSDF?andallalgorithmspresentedarebasedonconventionalBNFde?ni?tions?1?2Cho osingaparsingmetho dWhichrequirementsdo esSDFimp oseonitsimplementationandhowdothesea?ectthechoiceofaparserandparsergenerator?1?2?1RequirementsTheparserandparsergeneratorshouldacceptgeneralcontext?freegram?mars?CFGs??Thisclassmayseemoverlylarge?asLALR?1?orLR?1?isusuallyalargeenoughclasstode?neprogramminglanguagesin?andam?biguousgrammarsareinmostcasesundesirable?WepreferthelargerclassofCFGshoweverforthefollowingreasons?Manyparsergenerationsystemsdonotallowcertainkindsofruleslikeleft?recursive?right?recursiveorepsilonrules?Thisforcesthewriterofagrammartoavoidthesecases?anditrestrictstheformofparsetreesthatcanb ebuilt?Byallowingallofthese?maximalfreedomisgiventothewriterofasp eci?cation??SDFallowsmo dularcomp ositionofgrammarmo dules?Thismeansthatifonemo duleimp ortsanotherone?theirgrammarsarecombined?Theonlyclassofcontext?freegrammarsthatisclosedundercomp osi?tion?isthatclassitself?HU79?page131??Thisisnotthecaseforanysub classofit?likeLR?k??LALR?1?orLL?k???Itisnotp ossibletoexcludeambiguousgrammars?asitisundecidablewhetheragrammarisambiguous?Har78?page260??Inpractice?onecanonlyensurethatagrammarisnon?ambiguousbyrestrictingittoasmallerclassofgrammars?likeLR?k?orLL?k??Thiswouldatb estmeanthattheparserisonlyallowedtousea?xednumb erofsymb olsoflo ok?ahead?whilewewouldlikeittousearbitrarylo ok?ahead?OnecanincludethefullclassofunambiguousgrammarsonlybyallowinggeneralCFGs??SDFhasaquiteelab orateschemeforpro cessingtheprioritiesb etweengrammarrules?whichispartlyde?nedbycomputingwhichparsetreeisthe?largest?amongthep ossibilities?HHKR89?section6?2??This

1?2?CHOOSINGAPARSINGMETHOD13meansthattheparsermustgenerateallp ossibleparsetreesinorderthattheycanb ecompared?Astheenvisagedsystemisintendedforthede?nitionofprogramminglanguages?largepartsofthegrammarswill?tintheLR?1?class?Inthesecasestheparsershouldb ecomparableinsp eedtotheordinary?e?cient?LRparsingtechniques?Weaimatasystemfortheinteractivedevelopmentofsyntaxde?ni?tions?Parsergenerationshouldthereforeb efast?Itmustb ep ossibletomakeincrementalup datestotheparsergenerated?andparsergenerationfordi?erentmo dulesofamo dularsp eci?cationshouldnotinvolvedupli?categeneratione?ort?Theserequirementsallp ointtoaverysimpleparsergenerationalgorithm?withoutexp ensiveglobalop erationsonthegrammarrules?1?2?2TheparserThep ossiblealgorithmsweexaminedfortheparseranditsgeneratorare:?LR?1?algorithmsThesehaveane?cientparsergeneration?tableconstruction?algo?rithmthatleadstotimee?cientparsers?However?theclassofLR?1?grammarsisto orestricted??LR?k?algorithms?withk?1Thelargerkis?thelargertheclassofacceptedgrammarsb ecomes?However?parsinginaccordancewithallnon?ambiguousgrammarsisstillimp ossible?andparsergeneration?tableconstruction?timein?creasesexp onentiallywithk??Earley?suniversalcontext?freeparsingalgorithm?Ear70?Thisalgorithmcanhandleallcontext?freegrammarsandcanworkwithanegligibleparsergenerationphase?However?anEarleyparserisveryslowonLR?1?grammars??Tomita?suniversalparsingalgorithm?Tom85?Thisalgorithmcanb eplacedb etweenLR?k?algorithmsandEarley?salgorithm?Theclassofacceptedgrammarsisrestrictedtoacyclicgrammarsandthetimecomplexityofthealgorithmdep endsonthe

14CHAPTER1?GENERALIZEDLRPARSINGcomplexityofthegrammarandthesentenceb eingparsed?Tomita?salgorithm canuseanyLRparsetable constructorasaparsergenerator?Sikkelstudiedthedi?erencesb etweenthealgorithmsofEarley?sandTomita?sandconcludedthatb othareremarkablysimilar?Sik90??Tomita?salgorithmisb othmorep owerfulthananyLR?k?algorithmaswellasfasterthanEarley?salgorithmonmostgrammars?butitlo opsoncyclicgrammars?Weconsideredthisasabuginthealgorithmandhaverepairedit?Bydoingso?wehaveconvertedthealgorithmtoaGeneralizedLRparsingalgorithmwhichisasstrongasEarley?salgorithm?TheGLRalgorithmstartsasanordinaryLRparser?butwhenitencoun?tersashift?reduceorreduce?reducecon?ictinitsparsetableduringparsing?itsplitsupinasmanyparsersastherearep ossibilities?Theseparsersthenactinparallel;someofthemmaydieifthecon?ictingentrywascausedbyaneedforalargerlo ok?ahead?someofthemarecombinedagainafterhavingrecognizedanambiguouspartoftheinput?In?Lan74??Langdescrib edthisschemeinageneralmannerforallkindsoftabledrivenparsers?OurGLRalgorithmisasp ecialcaseofhisgeneraltechnique?ThegeneralizedLRparsingalgorithmcanhandlemoredeterministicgrammarsthananyLR?k?algorithm?b ecauseforeachLR?k?parsingalgo?rithmagrammarcanb econstructedwhichneedsalo ok?aheadofk? 1andhencecannotb eparsedbythatalgorithm?ThegeneralizedLRparsingal?gorithmdo esnothavesuchanupp erlimit?b ecauseitadjustsitslo ok?aheaddynamicallybyusingdi?erentparsestacksasalo ok?aheadmechanism?Anotherinterestingapproachtogeneralcontext?freeparsingisrecursiveascentparsing?KA88?Lee91??whichshouldb eatb oththeEarleyandtheTomitaparsingalgorithminsp eed?Wehavenotinvestigatedthistechniqueintoanydepth?however?TheGLRparsingalgorithmiscalledpseudo?parallel?butisclearlyde?signedtorunononepro cessoronly?Aparallelversionofthealgorithmthatsplitsupateachcon?ictintheparsetabledo esnotinducemuchgainduetothelargecommunicationoverhead?TN89?NT90??Amoresuccess?fulattempttoparallelizeTomita?salgorithmhasb eenp erformedbySikkel?Sik91??Heusesaseparatepro cessorforeachwordoftheinputsentenceandeachpro cessorparsesallconstituentsthatstartwiththatparticularword?See?Nij91?forageneraloverviewofparallelparsingalgorithms?

1?2?CHOOSINGAPARSINGMETHOD151?2?3TheparsergeneratorHavingdecidedtousetheGeneralizedLRparsingalgorithm?westillhavetocho osewhichparsetableconstructortouse?astheGLRparsingalgo?rithmcanworkwithLR?0??SLR?1??LALR?1?andLR?1?tables?Unliketheconventionalsituation?thesetablesareallowedtocontainmultipleentries?shift?reduceandreduce?reducecon?icts?whenusedincombinationwiththeGLRalgorithm?AnLR?0?parsetableconstructorgeneratesareduceactionforeachrulethathasb eenrecognizedcompletely?withoutcheckingifthelo ok?aheadisrightforit?LR?1?parsetableconstructors?ontheotherhand?onlygenerateareduceactionifthelo ok?ahead isright?So?theGLRparsingalgorithm willstartmoreparserswhencontrolledbyanLR?0?tablethanwhencontrolledbyanLR?1?tableforthesamegrammar?AdisadvantageoftheLR?1?techniqueisthatanLR?1?parsetablecontainsmorestatesthananLR?0?tableforthesamegrammar?as?intheLR?1?technique?statesareconsidereddi?erentiftheiritemshavedi?erentlo ok?aheadinformation?IftheGLRparseriscontrolledbyanLR?1?tableitwillthereforeb eabletojoinlessparsers?asparsersarejoinedonlyiftheyhavethesamestateontopoftheirstack?Frommeasurementsdescrib edin?Lan91?and?BL89??itturnsoutthatthisdisadvantageoftenoutweighstheadvantageofrunningfewerparsers?SLR?1?andLALR?1?parsetablescontainasmanystatesasLR?0?parsetables?whiletheydoapplylo ok?aheadinformationtolimitthenumb erofreductions?SLR?1?tablesgenerateareduceactionforaruleA::??onlyifthenextinputsymb olisinFOLLOW?A??LALR?1?tablesevengeneratelessreduceactions?byusingaLR?1?constructionschemeinwhichstatesarejoinedasifnolo ok?aheadinformationwaspresent?Ifweorderthedi?erenttablegeneratorsinaccordancewiththenumb erofuselessreduceactionsgenerated?LR?0?isontop?nextcomeSLR?1??LALR?1? and LR?1??Itistob eexp ected?and veri?edby measurements?thattheGLRalgorithmwillb emoste?cientwithLALR?1?tables?However?inthemeasurementsp erformedin?Lan91??SLR?1?andLALR?1?haveab outequale?ect?andtheirgaininsp eedoverLR?0?isonly10??WehavedecidedtouseanLR?0?tablegeneration algorithm?asthisisthesimplestgenerator?andwillb etheeasiestonetoextendb othtoincrementalparsergeneration?Chapter2ofthisthesis?andtoparsergenerationformo dulargrammars?Chapter3ofthisthesis??

16CHAPTER1?GENERALIZEDLRPARSING1?3GeneralizedLRrecognitionAGeneralizedLRparserrunsseveralsimpleLRparsersinparallel?ItstartsasasingleLRparser?but?ifitencountersacon?ictintheparsetable?itsplitsinasmanyparsersastherearecon?ictingp ossibilities?Theseindep endentlyrunningsimpleparsersarefullydeterminedbytheirparsestack?Iftwoparsershavethesamestateontopoftheirstack?theyarejoinedinasingleparserwithaforkedstack?Areduceactionwhicha?ectsapartoftheparsestackcontainingafork?splitsthecorresp ondingparseragainintotwoseparateparsers?Ifaparserencountersanerrorentryintheparsetable?itiskilledbyremovingitfromthesetofactiveparsers?Thealgorithmwedescrib edi?ersslightlyfromtheoriginalTomitaalgo?rithm?mainlytoallowittohandlethefullclassofcontext?freegrammars?1?3?1DescriptionThejoinedstacksmaintainedbythealgorithmhaveagraph?likeformandareimplementedusingstacknodesthatcontainastateandasetoflinkstostackno desonelevelloweronthestack?Ifastatemustb epushedonastackwhichhasstackno dep

?ontop?anewstackno depiscreatedwhichgetsalinkbacktop

??andpb ecomesthetopofthestack?Ap op?actionisnotp erformedphysically?thetopofthestackp ointerisjustmovedonelevelloweronthestack?Ap opactionresultsinasetofnewtopno des?Duringparsing?thevariableactive?parserscontainsallstackno deswhichhaveb eenontopofastackduringthepro cessingofthecurrentinputtoken?Thissetnevercontainstwostackno deswiththesamestate?Whenaparserwithtopno dep

?mustpushastates?whilethereisalreadyastackno depinactive?parserswhichcontainsstates?thenthelinksofpareextendedwithalinktop

??TheGLRrecognizercreatesandmaintainsthesegraph?likestackswhileitpro cessesitsinputsentence?Initially?thesetofactiveparsersjustconsistsofasinglestackno dehavingasstatethestartstateoftheparsetable?Theinputsentenceisextendedwithanend?of?sentencemarker?EOF?Next?routinePARSEWORDiscalledrep eatedlytopro cesseachtokenintheinputsentence?TheBo oleanaccept?sentence?initially?false??indicateswhetherthesentencehasb eenrecognizedornot?Iftheparsetablesprescrib eanacceptactionatthepro cessingofEOF?thisvariableissetto?true??Foreachoftheactiveparsers?PARSEWORDconsultstheparsetableby

1?3?GENERALIZEDLRRECOGNITION17meansofroutineACTION?Thisroutinereturnsasetofactionstop erformwiththestateontopofthestackandthecurrentinputtoken?A??shiftstate

0onthestackandhastomovetothenextinputsymb ol?A??reduceA::?????actionmeansthattheparserhastop opj?jstateso?thestack?hastouseroutineGOTOtoobtainanewstatestate

0?andhastopushstate

0onthestackagain?Shiftactionsarep ostp oneduntilallparsersarereadytoshiftandtheyarep erformedbyroutineSHIFTER?Onareductionof?A::???inaparserwithtopno dep?allstackno desatj?jlinksdistancefromparegiventoREDUCERforfurtherpro cessing?BothSHIFTERandREDUCERhavetopushnewno desonthestack?sohereitmayhapp enthatthelinksofotherstackno desmustb eextendedinordertojointwoparsers?InREDUCERthematterisevenmorecomplicated?Ifthelinksofastackno deareextended?allpreviouslyp erformedreductionsmustb ere?checkedasnewpathsmayhaveb ecomep ossibleoverthelinkjustcreated?Thisre?checkingofthereductionsthathavealreadyb eenp erformedisamo di?cationtotheoriginalTomitaalgorithm?andisduetoNozoho or?Farshi?NF89??Intheoriginalalgorithmonlythosepathswerereconsideredwhichhadthenewlinkas?rststep?However?inordertotake??reductionsseriously?allpathswhichcontainthenewlinkmustb ereconsidered?Themo di?cationofNozoho or?Farshia?ectsthewayinwhich??symb olsb etweenadjacentinputsymb olsaretreated?Intheoriginalalgorithmasmany??symb olsasneededareputb etweenthem?whileinthevariantofNozoho or?Farshi onlyone?isused?whichissharedasmanytimesasneeded?Thissubtledi?erenceavoidslo opingoncyclicgrammars?cf?section1?4?1?and ongrammarsin which thereexistsanon?terminal A?suchthatA

????A?where? ????butnot?

?????Wereferto?NF89?forthefullexplanationofthisextension?whichallowstheGLRrecognizertohandlethefullclassofcontext?freegrammars?1?3?2AlgorithmoftherecognizerTheGLRrecognizerforgeneralcontext?freegrammarsdescrib edab oveisimplementedbythefollowingfunctions?TheLispversionofthisalgorithmcanb efoundin?App endixA?1ofthisthesis??PARSE?Grammar?a1

? ? ?an ?:a n?1 :?EOFglobalaccept?sentence:?falsecreateastackno depwithstateSTART?STATE?Grammar?

18CHAPTER1?GENERALIZEDLRPARSINGglobalactive?parsers:?fpgfori:?1ton? 1doglobalcurrent?token:?aiPARSEWORDreturnaccept?sentencePARSEWORD:globalfor?actor:?active?parsersglobalfor?shifter:??whilefor?actor6??doremoveaparserpfromfor?actorACTOR?p?SHIFTERACTOR?p?:forallaction2ACTION?state?p??current?token?doifaction??shiftstate

0?thenadd?p?state

0forwhichapathoflength???fromptop

0existsdoREDUCER?p

0?GOTO?state?p

0??A??REDUCER?p

?yetthenaddalinklinkfromptop ?forallp

0?rule?link?else

createastackno depwithstatestateaddalinkfromptop

0forwhichapathoflength???fromptop

0throughlinkexistsdoREDUCER?p

0?GOTO?state?p

0??A??SHIFTER:

1?3?GENERALIZEDLRRECOGNITION19active?parsers:??forall? p

??state

0thenaddalinkfromptop

?else createastackno depwithstatestate

0addalinkfromptop

?andletitparsethesententialform?SSS??whichisambiguousaccordingtothegrammar?Itisp ossibletoparsesententialformswiththerecognizer?asthealgorithmmakesnodistinctionb etweenterminalsandnon?terminals?Wecould?ofcourse?alsoaddarule?S::?a?tothegrammarandparsethesentence?aaa??butthatwouldonlyintro duceadditional?andlessinteresting?reduceactions?TheLR?0?parsetableofGss

is transitionsreductions stateEOFS

0shift1

1acceptshift2

2shift2reduceS::?SS

Inthetracewedenotethestackno desbylittleb oxes?whichcontainastatenumb erandcanhavelinkstootherstackno des?Forexample?

1

0representsastackno decontainingstate1?thathasalinktoanotherstackno decontainingstate0?Now?weshowthestepbystepexecutionoftherecognitionalgorithm?Initially

active?parsers:?f 0 g 0 ?ACTION?0?S??fshift1g?sofor?shifter:?f? 0 ?0?gSHIFTER active?parsers:?f 1 0 1 0 ?ACTION?1?S??fshift2g?sofor?shifter:?f? 1 0 ?2?gSHIFTERactive?parsers:?f 2 1 0 g 2 1 0 ?ACTION?2?S??fshift2?reduceS::?SSgtheshiftactionisp erformedbysettingfor?shiftertof? 2 1 0 ?2?g?thereduceactionbyDO?REDUCTIONS? 2 1 0 ?S::?SS?p optwono deso?thestack?andREDUCER? 0 2 1 0 1? g?andadd 1 0 tofor?actorACTOR? 1 0 ?ACTION?1?S??fshift2g 2 1 0

1?2???

?2?gSHIFTERactive?parsers:?f 2 2 1 0 2 2 1 0 2 2 1 0 ?S::?SS?therearetwowaystop optwono deso?thestack?via 2 2 and 2 1 viathe?rstpath:REDUCER? 1 0 1 0 0 2 2 1 0 1? g?andadd 1 0 tofor?actorACTOR? 1 0

22CHAPTER1?GENERALIZEDLRPARSINGFinally

returntrue1?3?4CyclesintheparsestackThegraphofstackno des?asgeneratedbytherecognizerofsection1?3?2mayinsomecasesb ecomecyclic?Toexplainhowandwhythishapp ens?weusethefollowinggrammarS::?ASb?GrammarG1

?S::?xA::??ofthelanguagexb n? n?0?TheLR?0?parsetableofthisgrammaris: transitionsreductions statexbEOFAS

0shift1shift2shift3reduceA::??

1reduceS::?x

2shift1shift2shift4reduceA::??

3accept

4shift5

5reduceS::?ASb

Onparsingasentencexb

ninaccordancewithG1

?theparserneedstointro ducejustasmany??sb eforethex?asthereareb?safterit?TheoriginalTomitaalgorithmlo opsonthisgrammar?asanadditional?canalwaysb einserted?Weavoidthislo opinouralgorithmbysharing?symb ols?butbydoingso?thegraphofparsestacksb ecomescyclic?Thisisnecessary?asforeverynumb erofb?s?enoughA?sshouldb eavailabletoreduceA::?ASbrep eatedly?Justb eforeareductionoftheruleS::?ASb?theparsestackslo okslikeinFig?1?1?a??

1Poppingo?theno desforthesymb olsontheright?handsidecanb edoneovertwopaths;onethatgo esstraightdownandendsinstackno de

0 ?andtheotherthatgo esoverthecycleandends2 ?PushingthestatesGOTO?0?S?andGOTO?2?S?onb othstackno des?leadstothe

1Forclarity?wehaveannotatedthelinksinFig?1?1withsymb ols?whiletheseareactuallynotpresentinthealgorithm?

1?4?GENERALIZEDLRPARSING23

5b 4S 2A 0?a? A 4S 2A 0?b? A 3S

Figure1?1:Theparsestackb eforeandafterreductionofS::?ASbgraphofstackno desasinFig?1?1?b??Itdep endsonthenextinputsymb ol?borEOF?whichofthesetwoparserswillsurvive?Thisexampleshowshowtheparserusesacyclicparsestacktointro ducejustasmany?symb olsastherewillb eneededafterwards?1?4GeneralizedLRparsingIfwegenerateatreefortheinputsentence?weextendtheGLRrecognizeroftheprevioussectioninaGLRparser?IntheordinaryLRcase?aparsergeneratesatreebynotonlypushingstatesonitsparsestack?butalsosubtrees?Onashift?actionitpushesaterminalno deonthestack?andonareduceactionitp opsthesubtreesoftheright?handsideoftheruleo?thestack?takesthesetogetherinanewsubtree?andpushesthissubtreeonthestackagain?Whentheparserencounterstheacceptaction?thestackcontainstheparsetreeforthewholesentence?IntheGLRcasetheinputsentencemayb eambiguousandseveraltreesmustb ebuiltforit?Inordertodoso?webuildaparseforestwhichsplitsatambiguousp ointsandsharescommonsubtrees?Thisparseforestmayb ecomecyclic?andisthus?infact?agraph?asaresultofcyclesinthegrammar?Beforewecontinuethedescriptionoftheparseforest?wehavetosp endafewwordsonthenatureofthesecyclicgrammarsandtheproblemstheyintro duceforaparser?

????A? ????A??Thesegrammarsareproblematicb ecausethederivationA

???Acanb erep eatedin?nitelymanytimesinanyderivationthatcontainsanA?Thismaycauseparserstolo opforeverandgivesrisetoin?nitelymanydi?erentparsetrees?Mostparsingsystemsdonotallowcyclicgrammars?asthesecanalwaysb erewrittenintonon?cycliconesthatrecognizethesamelanguage?Thislimitstheexpressivep owerofcontext?freegrammars?asacyclicgrammarcanb ethemostcompactandnaturalwaytodescrib ealanguage?Therefore?weprefertodealwithcyclicgrammarsintheparseritself?Bydoingso?theparseforestbuiltb ecomescyclic?1?4?2ThestructureoftheparseforestTheparseforestwhichisbuiltbyourGLRparsingalgorithmconsistsofinstancesofthreestructures:symbolnode?termnodeandrulenode??Symbolnodesarelab eledwithanon?terminalofthegrammar?Edgesthatdepartfromasymb olno dearecalledpossibilities?andp ointtoaruleno dewhoserulehasthenon?terminalofthesymb olno deasitsleft?handside?Ifasymb olno dehasmorethanonep ossibility?thereareseveralapplicablepro ductionrules?Thismultiplicityrepresentsanambiguityintheparse??Termnodesarelab eledwithaterminal?Termno desdonothaveoutgoingedgesandareleavesoftheparsegraph??Rulenodesarelab eledwitharuleofthegrammar?Aruleno dehasasmanyoutgoingedgesasithaselementsintheright?handsideoftherule?andtheseedgesareordered?Iftheasso ciatedelementofanedgeisaterminal?theedgego estoatermno delab eledwiththatterminal;ifitisanon?terminal?theedgego estoasymb olno delab eledwiththenon?terminal?Inthecaseofan??ruletheruleno dedo esnothaveanyoutgoingedgeandconstitutesaleafoftheparsegraph?Notethattheparseforestthusorganizedformsabipartitegraph?Har69?p?17??inwhichtheruleno desareinonepartition?andthesymb olno desandtermno desintheother?IntheGLRparser?thelinksb etweentheno desoftheparsestackareextendedwithtermno desandsymb olno des?Onashiftaction?atermno de

1?4?GENERALIZEDLRPARSING25iscreatedwhichisusedinthelinksofallparsersthatarereadytoshift?Onareduceaction?thetermno desandsymb olno desofeachstackpathareassembledinaruleno de?Next?asymb olno deiscreatedwiththenewruleno deasitsonlyp ossibility?Thissymb olno deisthenattachedtothelinkb etweentheasso ciatedno desintheparsestack?Ifsuchalinkalreadyexists?however?italreadyhasasymb olno de?Inthatcase?thep ossibilitiesofthatsymb olno deareextendedwiththeruleno de?andanambiguousp ointintheparseforestisintro duced?1?4?3AlgorithmoftheparserThealgorithmsoftherecognizer?section1?3?2?andtheparserarequitesim?ilar?Theyonlydi?erinthefactthataparseforestisbuilt?Thedi?erencesaremarkedbyabarintherightmargin?PARSE?Grammar?a1

? ? ?an ?:a n?1 :?EOFglobalaccepting?parser:??

createastackno depwithstateSTART?STATE?Grammar?globalactive?parsers:?fpgfori:?1ton? 1doglobalcurrent?token:?aiPARSEWORDifaccepting?parser6??then

returnthetreeno deoftheonlylinkofaccepting?parser else return?

0?thenadd?p?state

DO?REDUCTIONS?p?A::???:forallp

0forwhichapathoflength???fromptop

0existsdokids:?thetreeno desofthelinkswhichformthepathfromptop

0

REDUCER?p

0?GOTO?state?p

0??A??A::???kids?

REDUCER?p

??state?A::???kids?: rulenode:?GET?RULENODE?A::???kids? ?then

ADD?RULENODE?treeno de?link??rulenode?

else n:?GET?SYMBOLNODE?A?rulenode? addalinklinkfromptop ?withtreeno den forallp

0?rule?link?elsecreateastackno depwithstatestaten:?GET?SYMBOLNODE?A?rulenode?

addalinkfromptop ?withtreeno den

0forwhichapathoflength???fromptop

0throughlinkexistsdokids:?thetreeno desofthelinkswhichformthepathfromptop

0

REDUCER?p

0?GOTO?state?p

0??A??A::???kids?

SHIFTER:active?parsers:??createatermno denwithtokencurrent?token forall? p ??state

0thenaddalinkfromptop

?withtreeno den elsecreateastackno depwithstatestate

0addalinkfromptop

?withtreeno den returnaruleno dewithrulerandelementskids

ADD?RULENODE?symbolnode?rulenode?:

1?4?GENERALIZEDLRPARSING27

S

S::?Id:?Exp

Id:?Exp

Exp::?Exp?ExpExp::?Exp?Exp

ExpExp

Exp::?Exp?ExpExp::?Exp?Exp

Exp?Exp?Exp

Exp:?IntExp:?IntExp:?IntIntIntInt

Figure1?2:The?ambiguous?treeof?Id:?Int?Int?Int?addrulenodetothep ossibilitiesofsymbolnode

GET?SYMBOLNODE?s?rulenode?:

returnasymb olno dewithsymb olsandp ossibilitiesfrulenodeg

?TheforestgeneratedbytheparserisgivenifFig?1?2?Ruleno desareinb oxes?symb olno desincirclesandtermno desarejustrepresentedbytheir

28CHAPTER1?GENERALIZEDLRPARSINGtokens?Theparserusestwometho dstocompactifytheforestgenerated?subtreesharingandlocalambiguitypacking?Both metho dsarein facta directconsequenceofthesharingofparsestacksalreadyp erformedingeneralizedLRparsing??subtreesharingIftwoparsersarecombinedandactforawhileasasingleparser?theygeneratetreeno desontheircommonpartoftheparsestack?Atthemomentareductionisp erformedthatgo esb eyondthecommonpart?theparsersplitsagain?Asaresult?thetreeno deswhichwhereonthecommonpartwillb eusedintwodi?erentcontexts?Thisiswhathapp enedtothesubtreesattheb ottomofFig?1?2andiscalledsubtreesharing??lo calambiguitypackingAsentenceissaidtohavealo calambiguityifoneofitsprop ersub?sentencescanb ereducedtothesamenon?terminalintwoormoreways?Ifasentencehasmanylo calambiguities?thetotalnumb erofambiguitieswouldgrowexp onentially?Toavoidthis?thetopno desofthesubtreesthatrepresentlo calambiguitiesaremergedandtheyaretreatedasasingleno debythehigherlevelno des?Lo calambiguitypackingisp erformedbytheroutinesREDUCERandADD?RULENODEintheparsingalgorithm?Iftherealreadyexistsaparserpinthestatetogoto?andpalreadyhasalinkbacktop

??thenewlyfoundruleno decanjustb eaddedtothesymb olno deasso ciatedtothislink?

2Thehighest?Exp?no deinFig?1?2issuchalo callyambiguousp oint?Ourtreescontainmoreno desthanthetreesin?forexample??Tom85??Thisisduetothefactthatweusedistinctno desforsymb olsandrules?Symb olno deswithmultipleoutgoingedgesrepresentambiguity?whiletheoutgoingedgesofaruleno demerelyrepresentthearityoftherule?Weconsideratreerepresentationlessclearifthiskindofinformationmustb eguessedfromtheproximityofedges?asinFig?2?12of?Tom85??And?withourrepresentation?itisp ossibletoobtainb ettersharing?

2Thenewruleno decoversthesamepartoftheinputsentenceastheotherruleno desinthesymb olno de?b ecausealinkb etweentwostackno despandp

?describ eswhathapp enedb etweenthemomentthatp ?wastopofthestack?andthemomentthatpis?Thismeansthat?ifanewlinkb etweenpandp ?isfound?theycoverthesamepartoftheinput? S

A::?ASb

S

A::?ASb

S

A::?ASb

S S::?x x A A::?? b b b S

A::?ASb

S

A::?ASb

S

A::?ASb

S S::?x x A A::?? A A::?? b b b

?a??b?Figure1?3:Twotreesfor?xbbb?1?5ImprovingthesharingintheparseforestIntheGLRparsingalgorithm?thesharingintheparseforestisdirectlyderivedfromthatoftheparsestacks?However?itmightb ethattheparsetablecontainsseveralstatesinwhichthereductionofthesameruleispre?scrib ed?Inthatcase?thesestatesarenotsharedintheparsestack?whiletheno desgeneratedbytheirreductionscouldb esharedintheparseforest?Asanexample?ifwetakegrammarG1

ofSection1?3?4?andusetheparsingalgorithmofSection1?4?3onthesentence?xbbb??thetreeofFig?1?3?a?isgenerated?Onewouldexp ectatreelikethatofFig?1?3?b??however?withonlyasingleno defortheruleA::???The?rsttreeis?fromtheviewp ointofthegrammar?aweirdtree?Whyistheno defor??rulere?usedatonep ointandnotatanotherp oint?Thiscanonlyb eundersto o dwiththeparsetableofG1

inmind?whichcontainstwostateswithareductionoftheruleA::???Improvedsharingintheparsetreewouldremovethisgeneratordep endentinformationandgeneratesamorecompacttree?

30CHAPTER1?GENERALIZEDLRPARSINGThesharingweprop oseis?again?anextensionoftheoriginalTomitaalgorithm?Inthatalgorithmruleno desdonotapp earasseparateenti?ties?andsharingcannotb ep erformedeasily?Furthermore?fromthetreesdrawnin?NF89??itapp earsthatNozoho or?Farshido esnotexploitthiskindofsharingeither?Thesharingintherepresentationweprop oseisnearlyasstrongasthatinthegrammarrepresentationofBillotandLang?BL89??exceptthatwedonotallowsharingofthetailofalistofsonsb etweendif?ferentno des?BillotandLanggenerateno deswithmaximallytwosubno desintheirgrammarrepresentation?andarethusabletoachievecubicspacecomplexity?Weusethefollowingtwometho dstoimprovethesharingofno desintheparsetree:?ruleno desharingCheckatthecreationofaruleno dewhetheraruleno dewiththesameruleandchildrenalreadyexists?Ifso?re?usethisruleno de??symb olno desharingCheckatthecreationofasymb olno deiftherealreadyexistasymb olno dewiththesamesymb olwhichcoversthesamepartoftheinput?Ifso?re?usethissymb olno de?Toillustratethee?ectofthesetwomeasures?wetakethefollowing?cyclic?grammarS::?SSGrammarG3S::?aS::???ofwhichtheLR?0?parsetableis

transitionsreductions stateaEOFS

0shift1shift2reduceS::??

1reduceS::?a

2shift1acceptshift3reduceS::??

3shift1shift3reduceS::??reduceS::?SS

toparseanemptysentenceinfourdi?erentways:?a?withtheGLRparsingalgorithmaspresentedinSection1?4?3??b?withruleno desharingalone??c?withsymb olno desharingalone?and?d?withb othmetho dsofsharingapplied?Fig?1?4showstheparsetreesgenerated?Thetreeof?a?clearlycontainsto omanyno des?In?b?theruleno desof?a?withthesameruleandthesamechildrenhaveb eencombined?whichremoves5sup er?uousruleno des?In?c?allsymb olno desof?a?werejoinedintooneastheyallcontainedthesamesymb olS?andcoveredthesame??symb ol?Ifthetwometho dsareb othapplied?thetreeshownin?d?istheresult?whichisthesmallestandmostnaturalrepresentationofallp ossibleparsetreesof?accordingtogrammarG3

?Inordertorealizethissharing?theparserhastorememb ertheruleno desandsymb olno desgeneratedduringthepro cessingofthecurrentinputsymb ol?Eachno destoresthefrontieritcoversinatuple?s? e??withsthep ositionofthe?rsttokencoveredandethep ositionofthelastone?Thisinformationcaneasilyb epropagatedb ottom?upduringthegenerationoftheparsetree?Termno descreatedforatokenatp ositioniobtain? i? i ?ascover?Ruleno desobtain? s? e ?ascover?withsthestartp ositionofthe?rstchildoftheruleno deandetheendp ositionofitslastchild?Symb olno desinherittheircoverfromtheruleno detheyarecreatedfor?

3??Rulesformaprobleminthisscheme?asruleno desforthemdonothavechildren?Theseruleno desobtainanemptycover?withtheconsequencethatsymb olno desmayalsogetanemptycover?Thismeansagainthatcomput?ingthefrontiercoveredbyruleno deshigherinthetreeb ecomesslightlymorecomplicated?seeroutineCOVERfortheactualimplementation??1?5?1AlgorithmoftheparserwithimprovedsharingThisisanextensionofthealgorithmofSection1?4?3?TheLispversionofthisGLRparsingalgorithmcanb efoundin?App endixA?2ofthisthesis??Themaindi?erencewiththealgorithmofSection1?4?3isinroutinesGET?RULENODEand GET?SYMBOLNODE which trytore?usepreviouslygeneratedno des?Also?allno desintheparsetreecontainareferencetothepartofthefrontiertheycover?Finally?routineADD?RULENODEhastocheckwhethertheruleno detoaddisnotalreadycontainedinthesymb olno de?Thedi?erenceswithSection1?4?3aremarkedbyabarintheright

3Otherruleno desareonlyaddedtoasymb olno deiftheycoverthesamefrontier?

32CHAPTER1?GENERALIZEDLRPARSING

?a?:withoutsharing S

S::?SSS::??

S

S::?SSS::?SSS::??

S

S::?SSS::?SSS::??

?b?:ruleno desharingalone S::?? S

S::?SS

S

S::?SS

S

S::?SS

?c?:symb olno desharingalone S

S::?SS

S::?SS

S::?SS

S::?SS

S::?SS

S::?? S::?? S::?? ?d?:b othsharings S

S::?SSS::??

PARSE?Grammar?a1

? ? ?an ?:a n?1

:?EOFglobalaccepting?parser:??createastackno depwithstateSTART?STATE?Grammar?globalactive?parsers:?fpgfori:?1ton? 1doglobalcurrent?token:?aiglobalposition:?i

PARSEWORDifaccepting?parser6??thenreturnthetreeno deoftheonlylinkofaccepting?parserelsereturn?PARSEWORD:globalfor?actor:?active?parsersglobalfor?shifter:??globalrulenodes:??;globalsymbolnodes:??

0?thenadd?p?state

0forwhichapathoflength???fromptop

0existsdokids:?thetreeno desofthelinkswhichformthepathfromptop

0REDUCER?p

0?GOTO?state?p

0??A??A::???kids?REDUCER?p

?thenADD?RULENODE?treeno de?link??rulenode?else ?withtreeno denforallp

0?rule?link?elsecreateastackno depwithstatestaten:?GET?SYMBOLNODE?A?rulenode?addalinkfromptop

?withtreeno denaddptoactive?parsersaddptofor?actorDO?LIMITED?REDUCTIONS?p?A::???link?:forallp

0forwhichapathoflength???fromptop

0throughlinkexistsdokids:?thetreeno desofthelinkswhichformthepathfromptop

0REDUCER?p

0?GOTO?state?p

0??A??A::???kids?SHIFTER:active?parsers:??createatermno denwithtokentokenandcover?position?position?

forall? p ??state

0thenaddalinkfromptop

?withtreeno denelse createastackno depwithstatestate

0addalinkfromptop

?withtreeno denaddptoactive?parsersGET?RULENODE?r?kids?:if9n2rulenodeswithrule?n??randelements?n??kidsthen

returnn else createaruleno denwithruler?elementskidsandcoverCOVER?kids? addntorulenodes returnn

COVER?kids?:

ifkids??or8kid2kids:cover?kid??emptythen returnempty else begin:?thestartp ositionofthe?rstkidwithanon?emptycover end:?theendp ositionofthelastkidwithanon?emptycover return?begin?end?

ADD?RULENODE?symbolnode?rulenode?:

1?6?MEASUREMENTS35ifrulenode62thep ossibilitiesofsymbolnodethen

addrulenodetothep ossibilitiesofsymbolnode GET?SYMBOLNODE?s?rulenode?:if9n2symbolnodeswithsymb ol?n??sand cover?n??cover?rulenode?then

ADD?RULENODE?n?rulenode?

returnn else createasymb olno denwithsymb ols? p ossibilitiesfrulenodegand covercover?rulenode? addntosymbolnodes returnn

1?6MeasurementsWeusethesyntaxofPascaltocomparethee?ciencyofourGLRparsingalgorithmwiththatofYACCandEarley?sparsingalgorithm?Inordertodoso?weto oktheSDFde?nitionofPascal?HHKR89?ap?p endix2??andextractedtheBNFde?nitiongeneratedbytheimplementa?tionofSDF?ThisBNFde?nitionisintendedtob eusedinasyntax?directededitor;itisabletorecognizeanyPascalconstructseparatelyandallowsholesintheinput?ByremovingtheseextensionsfromtheBNFde?nition?weobtainedthegrammarusedinthemeasurements?Thisgrammarcon?tains178rulesandallowscompletePascalprogramsonly?Thegrammarisambiguous?asprioritydeclarationswereusedintheSDFde?nitiontoexpressthepriorityorderingofthePascalop erators?insteadofco dingthepriorityorderinginthegrammaritself?Usingthisgrammar?wehavecomparedthetimeneededtogenerateparsetreesforPascalprogramsuptothreepagesinlength?Measurementsliketheseareeasilyin?uencedbyfactorsnotrelatedtoactualparsing;wehavetakenthefollowingprecautionstoavoidtheseasmuchasp ossible??Allmeasurementswerep erformedonthesamesunsparcstation1??Asinputfortheparsers?weusedactualPascalprograms?intheformofstreamsoflexicaltokenswhichweregeneratedbyalexicalscannerb eforehand?

36CHAPTER1?GENERALIZEDLRPARSING?Thesestreamswereallloadedintocoreb eforeparsingstartedtoavoidin?uencesofthesp eedofthe?lesystemonthemeasurements??Thetimeneededtoprintparsetreeswasnotmeasured?Wecomparedimplementationsofthefollowingparsingalgorithms:?GLRTheimplementationoftheGLRparsingalgorithmweusedistheonein?App endixA?2ofthisthesis??ThisimplementationiswritteninLeLisp?andtheco dehasb eencompiledwiththeLeLispcompiler?Complice??LeL87??TheparsetablegeneratorusedistheincrementalparsergeneratorIPG?Chapter2ofthisthesis??whichgeneratesLR?0?parsetables?IPGgeneratestheneededpartsoftheparsetablelazily?duringparsing?Toensurethatallneededpartsoftheparsetablewerepresent?wehaveparsedeachinputstreamtwice?anddidonlytimethesecondparse??YACC?Joh86?ThisisthestandardparsergeneratoravailableunderUnix?YACCgeneratesaparseranditsLALR?1?tablesintheformofaCprogram?whichissubsequentlycompiledintomachineco debyaC?compiler?AsYACConlyallowsnon?ambiguousparsetables?wehadtoadddisam?biguationconstructstorepresenttheprioritiesofPascalexpressions?Thiswasnotnecessaryforthetwootherparsingsystems?whichusethefull?ambiguous?Pascalgrammar?Byaddingthesedisambigua?tionconstructs?wehavesolved357shift?reducecon?icts?leavingonlyasinglecon?ictforthewellknownif?then?elseambiguityinPascal?Theactionsasso ciatedwitheachrulebuildatreerepresentationoftheinput??EarleyWehaveusedanimplementationofEarley?sparsingalgorithmwrittenbyMarkFreeleyinScheme?Dyb87??AsSchemeimplementationwehaveusedT?ofwhichWilliamMaddoxremarksthat?theco dequalityoftheTcompilerisamongtheb estforanydialectofLisp??Mad91??CompilingtheEarleyparserresultedinasp eed?upfactorofab out20comparedtointerpretedScheme?Still?wehavenotb eenabletop erformallplanned measurementsforEarley?salgorithm?aslong inputsentencescausedanapparentlyin?nitenumb erofgarbagecollections?

1?6?MEASUREMENTS37

02004006008001000Numb eroftokens

0 0?5 1 1?5

2Parsetime?inseconds?

??Yacc GLR SDF

EarleyFigure1?5:Howdi?erentparsersp erformonPascalprogramsTheresultsofthemeasurementsaredepictedinFig?1?5?TheyshowthattheGLRparserisab outthreetimesasslowastheYACCparser?whichismainlyduetothefollowingfactors:?TheGLRalgorithmisdrivenbyLR?0?parsetables?versusthemoresophisticatedLALR?1?tablesusedbytheYACCparser??TheYACCparsetablesdidnotcontaincon?icts?thankstothedis?ambiguationconstructsthathadtob eaddedtothegrammar?TheGLRalgorithmusedparsetablesthatdidcontaincon?icts?andhadtobuildlargerparsetreesrepresentingtheambiguities??TheYACCparserisimplementedinC?theGLRparserinLISP??TheGLRmetho dallowsalargerclassofgrammarsthanYACCdo es?Thisleadstoadditionalworkduringparsing?Fig?1?5containsanadditionallinemarked?SDF??ThismeasurementservestogiveanideahowtheGLRalgorithmp erformswithintheSDFenvi?ronment?Inthatcase?thejobtop erformisextendedwithlexicalscanning?solvingprioritycon?icts?andthetransformationoftheparsetreeintoanabstractsyntaxtree?ThegrammarusedintheSDFcaseallowsincompleteprogramsto o?Thisadditionalworkab outdoublesthetotalexecutiontime?

38CHAPTER1?GENERALIZEDLRPARSINGFig?1?5alsoshowsthattheEarleyalgorithmp erformsquitebadlyonthelargerinputsentences?andwouldclearlyb eanundesirablechoicetoparsePascalprograms?Itis?however?tob eexp ectedthattheEarleyalgorithmwillb eattheGLRalgorithmonhighlyambiguousinputsentences?asEarleyhasaworstupp erb oundofn

3?whileGLRisexp onential?Toillustratethis?wemeasuredthetimeneededbyb othalgorithmstoparsePascalprogramsofthefollowingform:programA?input??begina??bf?bg

iend?Withithenumb erof??s?AsthePascalgrammarusedcontainsarule?Expression::?Expression?Expression??theseprogramshaveanumb erofambiguousparseswhichgrowsexp onentiallywithi?Thisnumb er?Cn

?iscalledtheCatalannumb er?GKP89?p?343?344??andisequalto:C n n?0?1:1n?1: P n?1k?0 C k

Cn?k?1

2nn 1

n?1Fig?1?6shows?fori?1? ? ? ? ?20?theparsetimetakenbyb othalgo?rithmsandthenumb erofambiguousparses?Ci

?Thismeasurementcon?rmsourexp ectationthattheGLRalgorithmgenerallyp erformsb etterthantheEarleyalgorithm?butlosesonhighlyambiguoussentences?inthisexample:containingmorethan10

7ambiguities??Combiningtheresultsofthetwomeasurements?weconcludethattheGLRalgorithmisago o dchoicefor?near?LR?grammars?Forthesegram?marsitparsesnearlyase?cientlyasYACCdo es?whileitisabletohandleambiguoussentencesreasonablywell?Ifinputsentencesb ecomehighlyam?biguoushowever?theEarleyalgorithmwouldb eab etterchoice?Ifthegrammarsareknowntob eintheLALR?1?class?itwould?obviously?b emoreappropriatetouseYACC?1?7ConclusionsTheGeneralizedLRparsingalgorithmcoversthefullrangefromLRgram?marstogeneralcontext?freegrammarswithacceptablee?ciency?Atb othendsofthisrangeitmighthoweverb eadvisabletousesp ecializedalgo?rithms?like?resp ectively?YACCandEarley?salgorithm?Anotheradvantage

1?7?CONCLUSIONS39

05101520i?ornumb erof??s

1 100
10000
1e?06 1e?08 1e?10

1e?12ambiguities?

0?01 0?1 1

10Parsetime?inseconds????

?:ParsetimeEarley?:ParsetimeGLR?:Ci

?ornumb erofambiguitiesFigure1?6:Howdi?erentparsersp erformonhighlyambiguousprogramsoftheGLRalgorithmisthatitallowsusingtheverysimpleLR?0?parsetablegenerationalgorithm?OurcontributionstotheGLRalgorithmarethefollowing?wepresentthealgorithminclearpseudo?co de?whichshouldb eeasytotranslatetoanyprogramminglanguage??wehaveextendedthealgorithmtothefullclassofcontext?freegram?mars??andwehaveimprovedthesharingintheparseforest?

40CHAPTER1?GENERALIZEDLRPARSING

Chapter2IncrementalParserGenerationAnLR?basedparsergeneratorforarbitrarycontext?freegrammarsisdescrib edthatgeneratesparsersbyneedandhandlesmo di?cationstoitsinputgrammarbyup datingtheparserithasgeneratedsofar?Theneedforthesetechniquesismotivatedinthecontextofinteractivelan?guagede?nitionenvironments?Wepresentallrequiredalgorithms? andgivemeasurementscomparingtheirp erformancewiththatofconven?tionaltechniques?2?1Intro ductionThedesignofparsergeneratorsisusuallybasedontheassumptionthatthegeneratedparsersareusedmanytimes?Ifthisisindeedthecase?asophisticated?p ossiblyine?cient?parsergeneratorcanb eusedtogeneratee?cientparsers?Thereareapplications?however?towhichthisassumptiondo esnotapply:?Whenalanguageisb eingdesigned?itsgrammarisnotyetcompletely?xed?Aftereachchangeofthegrammar?a?completely?newparsermustb egenerated?butthereisnoguaranteethatitwillb eusedsuf??cientlyoften?Threeobservationscanb emadehere:?Thetimeneededtoparsetheinputisdeterminedbythee?ciencyofb oththeparserandtheparsergenerator?

c?1990IEEE?Reprinted?withp ermission?fromIEEETransactionsonSoftwareEn?gineering?16?12?:1344?1351? 1990?41

42CHAPTER2?INCREMENTALPARSERGENERATION?Somepartsofthegrammarmaynotb eneededbyanyofthesentencesactuallygiventotheparser;thee?ortsp entonsuchpartsbytheparsergeneratoriswasted??Ingeneralonlyasmallpartofthegrammarismo di?ed?Onewouldliketoexploitthisfactbymakingacorresp ondinglysmallmo di?cationtotheparser?ratherthangeneratinganentirelynewone??Thereisatrendtowardsprogramming?sp eci?cationlanguagesthatallowgeneraluser?de?nedsyntax?LITHE?San82??OBJ?FGJM85??Cigale?Voi86??ASF?SDF?BHK89???Insuchlanguageseachmo d?ulede?nesitsownsyntax?andeachimp ortofamo duleextendsthesyntaxoftheimp ortingmo dulewiththe?visible?syntaxoftheim?p ortedmo dule?Fore?cientparsingandsyntax?directededitingoftheselanguages?itisofgreatimp ortancetouseaparsergeneratorthatcanhandlealargeclassofcontext?freegrammars?andthatcanincorp oratemo di?cationsofthegrammarintheparserincrementally?Wedescrib ealazyandincrementalparsergeneratorIPG?whichissp eciallytailoredtowardsthehighlydynamicapplicationssketchedab ove:?Theparserisgeneratedinalazyfashionfromthegrammar?Thereisnoseparateparsergenerationphase?buttheparserisgeneratedbyneedwhileparsinginput?Iftypicalinputsentencesneedonlyasmallpartofthegrammar?afasterresp onseisachievedthaninthegreedycase:theparsergenerationphasedo esnotintro duceanoticeablede?layandparsingcanstartimmediately?Iftheinputsentencesdonotusetheentiregrammar?workissavedonthegenerationpro cessasawhole?Itturnsoutthatincomparisonwithconventionaltechniques?theoverheadintro ducedbythislazytechniqueissmall??Theparsergeneratorisincremental?Achangeinthegrammarpro?ducesacorresp ondingchangeinthealreadygeneratedparser?Partsoftheparserthatarenota?ectedbythemo di?cationinthegrammararere?used?Hence?thee?ortsp entingeneratingthemisre?usedaswell?Thishasclearadvantagesforinteractivelanguagede?nitionsystems??Thee?ciencyoftheparsingpro cessitselfremainsuna?ected?inthesensethatonceallrequiredpartsoftheparserhaveb eengenerated?theparserwillb ease?cientasaconventionallygeneratedone?

2?2?CHOOSINGAPARSINGALGORITHM43?Theparsing algorithm iscapable ofhandling general context?free gram?mars?inclusiveambiguousgrammars?Foradescriptionofthegeneralprinciplesunderlyingourmetho d?see?HKR91??In?HKR87?alazy?incrementallexicalscannergeneratorISGisdescrib ed?ThecombinationISG?IPGisusedinaninteractivedevelopmentenvironment fortheASF?SDFsp eci?cation language mentionedab ove?Theuniversalsyntax?directededitorofthisenvironmentisparametrizedwithagrammarwritteninSDF?HHKR89??andusesISG?IPGasitsparsingcomp onent?Theresp onsetimeoftheeditorisacceptable?eventhoughthelexicalscannerandtheparseraregeneratedandmo di?edonthe?yduringediting?InSection2?2wediscussrelatedalgorithmsandexplainhowourtech?niqueevolvedfromthem?InSection2?3wepresentanLRparserandaconventionalLR?0?parsergenerationalgorithm?WeextendthisintoalazyparsergenerationalgorithminSection2?4?InSection2?5weextenditonceagainintoanincrementalparsergenerationalgorithm?Finally?Section2?6givestheresultsofe?ciencymeasurements?andSection2?7containssomeconcludingremarks?2?2Cho osingaparsingalgorithmWecomparesomeexistingparsingalgorithmswithourownalgorithmfromthep ersp ectiveofhighlydynamicapplicationsliketheonesdiscussedintheprevioussection:?LR?k?andLALR?k?algorithms?ASU86?chapter4?7?Thesealgorithmsarecontrolledbyaparsetablethatisconstructedb eforehandbyatablegenerator?Thetableisconstructedtop?down?whereastheparseritselfworksb ottom?up?Theparserworksinlin?eartime?Whenthelo ok?aheadkisincreased?theclassofrecog?nizablelanguagesb ecomeslarger?butwillalwaysb elimitedtonon?ambiguousgrammars??andthetablegenerationtimeincreasesexp o?nentially?WithconventionalLRorLALRtablegenerationalgorithmsitisdi?culttoup dateanalreadygeneratedparsetableincrementallyifthegrammarismo di?ed?seeb elow???RecursivedescentandLL?k?algorithms?ASU86?chapter4?4?

44CHAPTER2?INCREMENTALPARSERGENERATIONArecursivedescentparsergeneratorbuildsaparsingprogram?whereasanLLgeneratorbuildsaparsetablethatisinterpretedbya?xedparser?Inb othalgorithmstheparsersworktop?down?Theclassofacceptedlanguagesdep endsonthelo ok?aheadk?butisalwayslimitedtonon?left?recursive?non?ambiguousgrammars??Earley?sgeneralcontext?freeparsingalgorithm?Ear70?Earley?salgorithmcanhandleallcontext?freegrammars?Itworksbyattachingtoeachsymb olintheinputasetof?dottedrules??Adottedruleconsistsofasyntaxrulewithacursor???initandthep ositionintheinputwheretherecognitionoftherulestarted?Thesetofdottedrulesforsymb oln?1iscomputedatparsetimefromthesetforsymb oln?Earley?salgorithmdo esnothaveaseparategenerationphase?soitadaptseasilytomo di?cationsinthegrammar?Itisthissamelackofagenerationphasethatmakesthealgorithmto oine?cientforinteractivepurp oses??Cigale?Voi86?Cigaleusesaparsingalgorithmthatissp eciallytailoredtoexpressionparsing?Itbuildsatrieforthegrammarinwhichpro ductionruleswiththesamepre?xshareapath?Duringparsingthistrieistra?versedrecursively?Atriecaneasilyb eextendedwithnewsyntaxrulesandtriesfordi?erentgrammarscanb ecombinedjustlikemo dules?TheclassofgrammarsissomewhatlargerthanLR?0?grammars?astheparserdo esnotuselo ok?aheadinageneralmannerandcannotbacktrack??OBJ?FGJM85?OBJusesarecursivedescentparsingtechniquewithbacktracking?OBJitselfdo esnotallowambiguousgrammars?butthebacktrack?parserdo esdetectallambiguousparses?Thismakestheparsingsys?temsuitablefor?nitelyambiguousgrammars?butasmentionedin?FGJM85?page60??parsingcanb eexp ensiveforcomplexexpres?sions??whichmakesthealgorithmlesssuitableforlargeinputsen?tences??Pseudo?parallelLRparsing?Lan74?Tom85?ThisisanextendedLRparsingalgorithmthatrequiresaconventional?butp ossiblymulti?valued? LR?0??LR?1?orLALR?1?parsetable?The

2?2?CHOOSINGAPARSINGALGORITHM45parserstartsasanLRparser?butwhenitencountersamulti?valuedentryintheparsetable?conventionallyknownasatablecon?ict??itsplitsupinseveralLRparsersthatworkinparallel?Thetheoreti?calframeworkforpseudo?parallelLRandLLparsingwasintro ducedbyLang?Lan74??Itwasoptimizedindep endentlybyTomitaforLRparsing?Tom85??Grammarsarerestrictedtotheclassof?nitelyam?biguous?oracyclic?context?freegrammars?WediscussthisalgorithmindetailandextendittogeneralCFgrammarsin?Chapter1ofthisthesis??AsTomita?sparsingtechniqueusesthesametablegenerationphaseasconventionalLRalgorithms?mo difyingthegrammarisanexp ensiveop erationwiththisalgorithm??IncrementalparsergeneratorIPGWedevelop edthismetho donthebasisoftheTomitaparsingalgo?rithm?butprovidedthealgorithmwithanincrementalLR?0?parsetablegenerator?Parsingstartswithanemptyparsetable?whichisexpandedbyneedduringparsing?Achangeinthegrammarishan?dledincrementallybyremovingthosepartsoftheparsetablethatarea?ectedbythechange;thesepartsarerecomputedforthemo di??edgrammarwhentheparserneedsthemagain?Theparsetableisconstructedduringparsing?soafteracertaintime?dep endingontheinputgiventoit?thesystemwillb ecomeasfastasaconventionallygeneratedTomitaparser??IncrementalLALR?1?parsergeneration?Hor89?Hor90?Atthetimewewrotethispap er?averysimilarapproachwasprop osedindep endentlybyHorsp o ol?Hisp ointofdepartureisaconventionalLRparserratherthanaparalleloneandheconsidersincrementalgen?erationofLALR?1?parsetables?Thisismoredi?cultthanincremen?talgenerationofLR?0?tables:lo ok?aheadsetshavetob etakenintoaccountwhoseincrementalgenerationandmo di?cationturnouttob eproblematic?Asaconsequence?hissystemhasalesse?cientincre?mentaltablegenerationphase?butgeneratesmoree?cientLALR?1?parsers?Weoptedforamoree?cientLR?0?tablegenerationphaseattheexp enseofsomelossinparsinge?ciencyfornon?LR?0?languages?butwithoutrestrictingtheclassofacceptablegrammarsinanyway??Fig?2?1assignsarating totheab ove?mentioned algorithms foreachofthefollowingprop erties:capabilityofhandlingarbitrarycontext?freegrammars

46CHAPTER2?INCREMENTALPARSERGENERATION

p owerfulfast?exiblemo dular ???????Earley ???????OBJ ?????Tomita ??????Horsp o ol

?????Figure2?1:Comparisonofvariousparsingalgorithms?p owerful??e?ciencyonlargeinputsentences?fast??p ossibilityforpro cess?ingofmo di?cationsofthegrammar??exible??andp ossibilityformo dularcomp ositionofparsers?mo dular??2?3LRparsingandparsergenerationInthissectionwedescrib eanLRparser?theasso ciatedparsetables?andanLR?0?parsergenerator?Weassumethereadertob ereasonablyfamiliarwiththesub ject?Thissectionjustservestorefreshthereader?smemory?ThebasicreferenceforLRparsingandparsergenerationis?ASU86???GJ90?and?KP90?arealsointerestingasthesecontainanup?to?dateanno?tatedbibliographyofrelatedalgorithms?2?3?1LRparsingWeuseapseudo?parallelparsingalgorithm?develop edbyTomita?Tom85??ItrunsseveralordinaryLRparsersinparallelandcanhandlearbitrarycontext?freegrammars?Togiveanideaofhowourparserworks?wepresentanon?parallelLRparser?Itmaintainsaparsestackwhichinitiallycontainsthestart?state?Thestateontopofthestackisthecurrentstateoftheparser?Theparserrep eatedlyconsultsitsparsetableforactionstob ep erformedinthecurrentstateandwiththecurrentinputsymb ol?ThisisdonebyroutinesACTIONandGOTO?Ifthereareseveralp ossibleactions?itcho osesoneofthem?Pushthestart?stateonthestack

2?3?LRPARSINGANDPARSERGENERATION47whiletruedoThecurrentstateoftheparseristhestateontopofthestackThecurrentinputsymb olisthe?rstsymb olofsentenceCho oseanarbitraryactionfromthosereturnedbyACTIONifthereisnoactionthenRejectthesentenceelseifitisashiftactiontoastatethenPushthecurrentsymb olandthenewstateonthestackRemovethecurrentsymb olfromtheheadofsentenceelseifitisareduceactionofruleA::??thenReplace?onthestackbyACallGOTOforanewstatePushthenewstateonthestackelseifitisanacceptactionthenAcceptthesentenceProvidedwithaparsetablegeneratedbyanLR?0?parsergenerator?thisalgorithmyieldsuniqueparsesforanyLR?0?grammar?butitmayfailforothergrammarsifitcho osesthewrongactionatanyp ointatwhichACTIONreturnsmultipleactions?Thepseudo?parallelversionofthealgo?rithm?Tom85???Chapter1ofthisthesis?exploresallactionsreturnedbyACTIONbysplittinginmultipleparsers?oneforeachp ossibility?Inthiswayityieldsuniqueparsesforanyunambiguousgrammar?andallp ossibleparsesforambiguousgrammars?So?thistechniqueenablesustorecognizethefullclassofcontext?freegrammars?whileusingasimpleLR?0?parsetablegenerator?Wedonotrejectambiguoussentences?butlettheparsingalgorithmreturnal lp ossibleparses?Thisleavesro omforap ostpro cessor?suchasthealgorithmdescrib edin?HHKR89?section6?whichselectsparsetreesonthebasisofprioritydeclarations?2?3?2TheparsetableorgraphofitemsetsThenotionofitemordottedruleisbasictoanunderstandingoftheLRmetho d?Anitemisagrammarrulewithadotinitsright?handsideindi?catinghowfartheparseaccordingtothatparticularrulehasprogressed?Asetofitemsisanitemset?Aparsetableisagraphwhoseno desareitemsetsandwhose?lab eled?edgesaretransitionsb etweenitemsets?Astateoftheparserisanitemsetinthisgraph?Forexample?thegraphgeneratedforthefollowinggrammar

48CHAPTER2?INCREMENTALPARSERGENERATION

START" ::= • START

B ::= true •B ::= false •START ::= B •

B ::= B • and B

B ::= B • or B

Btruefalse

B ::= B and • BB ::= B or • B

andquotesdbs_dbs25.pdfusesText_31

[PDF] Benne TP Semi-Ronde - Anciens Et Réunions

[PDF] BENNE TRANSPORTEUR TRIVERSE, DEPOSABLE

[PDF] Benne Travaux Publics

[PDF] Bennes à béton - BureauPreventicas - Conception

[PDF] Bennes agricoles - Chambre d`agriculture du Loiret - Anciens Et Réunions

[PDF] BENNES AMOVIBLES - Fabrication

[PDF] Bennes et remorques

[PDF] bennes roues interieures bennes roues interieures - Anciens Et Réunions

[PDF] Bennes-Bacs-Rétention - Anciens Et Réunions

[PDF] BENNING ST 710

[PDF] Benny Hinn - Cadeaux

[PDF] BENODET - Anciens Et Réunions

[PDF] BÉNODET - CLOHARS-FOUESNANT - FOUESNANT - Gestion De Projet

[PDF] benodet - La Recouvrance - Anciens Et Réunions

[PDF] Bénodet - Quimper - Accueil :: clohars - Anciens Et Réunions