Class9USTC自下而上分析分类Bottom-upParsing规范归约移进归约简单优先分析ZhangSihai算符优先分析shzhang@ustc.edu.cn0551-3600485EEIS,USTCNovember13,2009Class9USTC自下而上分析geþ©Û分类规范归约©a移进归约5‰8简单优先分析£?8算符优先分析{ü`k©ÛŽÎ`k©ÛÞ~Class9USTC自下而上分析©{分类I规范归约移进归约IS→aABe简单优先分析IA→Abc|b算符优先分析IB→dI输\GIabbcdeI{IlÑ\G开©，逐步?行8，直至8到©{的开©ÎÒIlŠ{ä的末端开©，步步•þ8直到根!点，Ïd，称’£?-8’{(Shift-reduceParsing)Class9Þ~-L§USTC自下而上分析分类S规范归约移进归约aABeS→aABe简单优先分析aAdeB→d算符优先分析aAbcdeA→AbcabbcdeA→bIS⇒rmaABe⇒rmaAde⇒rmaAbcde⇒rmabbcdeI´g顶•em推导的逆L程（5‰8）I3每个8步骤中，˜个†某产)ª体ƒ匹配的特定fG被替换该产)ª头部的š终(ÎÒClass9Þ~-L§2USTCS自下而上分析分类...规范归约aAAcBe?移进归约简单优先分析aAAcdeB→d算符优先分析aAbcdeA→babbcdeA→bIˆ«ØÓgeþ©Û¡ÓA:I边Ñ\ücÎÒ(£?负ÒÒ)，边?行8I3l†至m£?Ñ\G的L程中，˜旦uyÒ顶呈y可8GKá=?行8I'…¯KµI۞8？I^哪个产)ª?行8？©aClass9USTC自下而上分析IPrecedenceparser分类ŽÎ`k规范归约I(Operator-precedenceparser)移进归约ISimpleprecedenceparser简单优先分析Ihttp://en.wikipedia.org/wiki/Simple_算符优先分析precedence_parserIBoundedcontextparsingILRparserISimpleLR(SLR)parserILALRparserICanonicalLR(LR(1))parserIGLRparserICYKparser`k©Û{0Class9USTC自下而上分析分类{ü`k©Û{规范归约I移进归约对˜个©{按˜定¦K求出该©{¤kÎÒ（终(I简单优先分析Îښ终(Î）之m的`k'X，按ìù种'X(定算符优先分析8L程中的é柄I按ì©{ÎÒ（包)终(Îښ终(Î）的`k'X(定é柄I¢Sþ´˜种5‰8IŽÎ`k©ÛI只5定ŽÎ（终(Î）之m的`k'XIé到é柄Ò8，不´5‰8Class9LR©Û{0USTC©ÛìILR(k)自下而上分析IL：l†•m×描Ñ\分类：¨Em推导的逆规范归约IR移进归约Ik：•前|¢的ÎÒ个ê，"Ž1简单优先分析©ÛLILR算符优先分析ISLR：{üLR©Û器I5‰LR：ILALR：IŒõ数^þe©Ã'©{£述§SŠóь^LR©Û샱识OILR©Û{'ŽÎ`k©Û{½Ù¦’£?-8’E术\2IU^LR©Ûì©Û©{a§¹U^LL(1)©Ûì©ÛÜ©{aáŠÚéYClass9USTCDefinition自下而上分析分类令G是˜‡©{§S是©{m始ÎÒ,b½αβδ规范归约移进归约是G˜‡é..ek简单优先分析算符优先分析S⇒∗αAδandA⇒+βK¡β是é.αβδƒéuAáŠ.AO§ekA⇒βK¡β是é.αβδƒéuA⇒β†áŠ.Definition˜‡é.††ኡéY。éY~Class9USTC自下而上分析分类规范归约I虑©{移进归约IE→T|E+T简单优先分析IT→F|T∗F算符优先分析IF→i|(E)I虑é.1:i1∗i2+i3+IkE⇒i2+i3，那么i2+i3´短Ší？Ii1,i2Úi3´直短Š，其中i1´é柄I虑é.2:E+T∗F+iIT∗FÚi´直短Š，其中T∗F´é柄5‰8Class9USTC自下而上分析Definition分类规范归约移