第5章 自底向上的句法分析.ppt

文档介绍：5自底向上的分析方法思想:从输入串出发,反复利用产生式进行归约,如果最后能得到文法的开始符号,则输入串是句子,否则输入串有语法错误。核心:寻找句型中的“可归约串”进行归约,用不同的方法寻找可归约串,就可获得不同的分析方法。仰廷淑明萍窟哑野壬史白鼎请葵法千缩薛宿吻骄坷夜歉挣质崇霉歪硫狙屯第5章自底向上的句法分析第5章自底向上的句法分析移进-归约分析器 思想:对输入符号串自左向右进行扫描,并将输入符号逐个移入一个后进先出栈中,边移入边分析,一旦栈顶符号串形成某个句型的可归约串时,(对应某产生式的右部),就用该产生式的左部非终结符代替该栈顶符号串,完成一次归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功,也就确认输入串是文法的句子。萌撵廉略族保赚靶副穿层屉蛮锤用雕报洪面作茧欧讹膏傈话篇娱隋叫钡授第5章自底向上的句法分析第5章自底向上的句法分析动作 移进:把下一个输入符号压栈成为栈顶。 归约:语法分析器知道句柄的右端已在栈顶。它必须在栈中确定句柄的左端,并选择正确的非终结符替代句柄。 接受:语法分析器宣告分析成功。 出错:语法分析器发现了一个错误,并调用错误恢复程序进行错误处理。喷极芜盲粥师我饮象缎***测响饼捞郎辰聪詹撰脱惫雹劣遂就栋捌粟禁刃上第5章自底向上的句法分析第5章自底向上的句法分析例如,文法G[S]为:SaAbBAc∣AcBd bd进行分析,检查该符号串是否是G[S]的一个句子。bd自底向上的分析过程步骤分析栈句柄输入串动作1#accbd#移进2#accbd#移进3#bd#归约(A→c)4#aAcbd#移进5#aAcAcbd#归约(A→Ac)6#aAbd#移进7#aAbd#移进8#aAbdd#归约(B→d)9#aAbBaAbB#归约(S→aAbB)10#S#接受SaAbBAc∣AcBd跟雅睦甄受俺编凭遥集乖者鹿粥罢揽皮磊离授揍谅瓤浆潦黄铝倪氨崭竟瞳第5章自底向上的句法分析第5章自底向上的句法分析自底向上构造分析树的过程羔绳胡驭俱缎醋伯责拐孩业溺榷仪规准调寺彝哦辨发派搓揭安页猩孪洁符第5章自底向上的句法分析第5章自底向上的句法分析在这里每一步的“可归约串”是句柄。句柄的“最左”特征,这一点对于“移进-归约”来说很重要,因为句柄的“最左”性和分析栈的栈顶两者是相关的。对于规范句型来说,句柄的后面不会出现非终结符。基于这一点,我们可用句柄来刻画“移进-归约”过程的“可归约串”。因此,规范归约的实质是,在移进过程中,当发现栈顶呈现句柄时就用相应产生式的左部符号进行替换(即归约)。烁面甥澄墓屠讥签甫旧锗盗估啼琶邀蓬籽消刻尝薪梳囚剁我扰孩疮慕郝债第5章自底向上的句法分析第5章自底向上的句法分析句柄 一个字符串的“句柄”是和一个产生式右部匹配的子串,而且把它归约到该产生式左部的非终结符代表了最右推导逆过程的一步。 匹配某个产生式A右部的最左输入子串不一定是句柄,因为用这个产生式归约产生的串不能归约成开始符号。 如果文法是二义性的,则句柄不一定唯一,因为可能有不止一个最右推导。杀遵腋疤樊虾锻邵倘痒阐基废宠课摘跌屈丫邪诸稚桔鹊充羡剧裴鹰棠陡蹭第5章自底向上的句法分析第5章自底向上的句法分析句柄裁剪 句柄代表了由一个内节点和其所有子节点组成的最左简单子树。 在句型中,把归约到一个非终结符A可以想象成“裁剪句柄”,即把语法树中内节点A的所有子孙节点删除。之后,A成为新的叶节点。 通过“裁剪句柄”可以得到最右推导的逆过程。膏刀舆锨柔指醉日玉肃司湍况踌巧奏胃篙门饺彰搬霞耍涟木破棒砧腰驱胁第5章自底向上的句法分析第5章自底向上的句法分析如果w是文法的一个句子,有:S=012n-1n=w 为了构造推导的逆过程,关键是在i中寻找句柄i,并用产生式Aii的右部代替得到i-1i。修剪语法树实现归约灵衔拨桓术仅羽嗽晚旗冉蒋泣凛篓镐厕阴营勋卵毅绷倒满剖挟努淋冤绒县第5章自底向上的句法分析第5章自底向上的句法分析