第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章自底向上的句法分析