Bottom-upparsingBottom-upparsingalgorithmsareingeneralmorepowerfulthantop-downmethods,butnotsurprisingly,theconstructionsrequiredinthesealgorithmsarealsomorecomplex.Itisdifficulttowriteabottom-upparserbyhandforanythingbutthemosttrivialofgrammars,butfortunately,thereareexcellentparsergeneratortoolslikeyaccthatbuildaparserfromaninputspecification.Shift-reduceparsingisthemostcommonlyusedandmostpowerfulofthebottom-uptechniques.LRparsingLRparsers(“L”forlefttorightscanofinput;“R”forrightmostderivation)areefficient,tabledrivenshift-reduceparsers.TheclassofgrammarsthatcanbeparsedusingLRmethodsisapropersupersetoftheclassofgrammarsthatcanbeparsedwithpredictiveLLparsers.Infact,virtuallyallprogramminglanguageconstructsforwhichCFGscanbewrittencanbeparsedwithLRtechniques..AnLRparserusestwotables:1.TheactiontableAction[s,a]tellstheparserwhattodowhenthestateontopofthestackissandterminalaisthenextinputtoken.Thepossibleactionsaretoshiftastateontothestack,toreducethehandleontopofthestack,toaccepttheinput,ortoreportanerror.2.ThegototableGoto[s,X]indicatesthenewstatetoplaceontopofthestackafterareduceofthenon-terminalXwhilestatesisontopofthestack.Thetwotablesareusuallycombined,withtheactiontablespecifyingentriesforterminals,andthegototablespecifyingentriesfornon-terminals.TypesofLRparsersTherearethreetypesofLRparsers:LR(k),simpleLR(k),andlookaheadLR(k)(abbreviatedtoLR(k),SLR(k),LALR(k)).Thekidentifiesthenumberoftokensoflookahead.Wewillusuallyonlyconcernourselveswith0or1tokensoflookahead,butitdoesgeneralizetok>1.Thedifferentclassesofparsersalloperatethesameway(asshownabove,beingdrivenbytheiractionandgototables),buttheydifferinhowtheiractionandgototablesareconstructed,andthesizeofthosetables.ConstructingLR(0)parsingtablesLR(0)configurationoritem.Aconfigurationisaproductionofthegrammarwithadotatsomepositiononitsrightside.1.ConstructF={I0,I1,...In},thecollectionofconfiguratingsetsforG'.2.StateiisdeterminedfromIi.Theparsingactionsforthestatearedeterminedasfollows:a)IfA–>u•isinIithens...
