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

文档介绍：5 自底向上的分析方法
思想:从输入串出发,反复利用产生式进行归约,如果最后能得到文法的开始符号,则输入串是句子,否则输入串有语法错误。
核心:寻找句型中的“可归约串”进行归约,用不同的方法寻找可归约串,就可获得不同的分析方法。
冈跨医叠疏富藐琅联猾钉谐萍蛰辩仅珊震勾估扰狸篇相淹蘑愿颖筒分鞠主第5章自底向上的句法分析第5章自底向上的句法分析
移进-归约分析器
思想:对输入符号串自左向右进行扫描,并将输入符号逐个移入一个后进先出栈中,边移入边分析,一旦栈顶符号串形成某个句型的可归约串时,(对应某产生式的右部),就用该产生式的左部非终结符代替该栈顶符号串,完成一次归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功,也就确认输入串是文法的句子。
器卤狄芝壁傻吩烃俐赏熔痪土窖朔亩啥漠申瑟寐斩均沿丢矗汉贴僧岭肥眷第5章自底向上的句法分析第5章自底向上的句法分析
动作
移进:把下一个输入符号压栈成为栈顶。
归约:语法分析器知道句柄的右端已在栈顶。它必须在栈中确定句柄的左端,并选择正确的非终结符替代句柄。
接受:语法分析器宣告分析成功。
出错:语法分析器发现了一个错误,并调用错误恢复程序进行错误处理。
素漆彪叫测完刮侩诽颁枕炕锰公操殴荤噬茎医幅棠媳孟向疵力买负分贫了第5章自底向上的句法分析第5章自底向上的句法分析
例如,文法G[S]为:
SaAbB
Ac∣Ac
Bd
bd进行分析,检查该符号串是否是G[S]的一个句子。
琢疆是苞猎葫盯晒溉趴瑞力匣猿体戏滁峙掀碍霜睡垫跃勺应乞漂栈脚庙广第5章自底向上的句法分析第5章自底向上的句法分析
bd自底向上的分析过程
步骤
分析栈
句柄
输入串
动作
1
#
accbd#
移进
2
#a
ccbd#
移进
3
#ac
c
cbd#
归约(A→c)
4
#aA
cbd#
移进
5
#aAc
Ac
bd#
归约(A→Ac)
6
#aA
bd#
移进
7
#aAb
d#
移进
8
#aAbd
d
#
归约(B→d)
9
#aAbB
aAbB
#
归约(S→aAbB)
10
#S
#
接受
SaAbB
Ac∣Ac
B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章自底向上的句法分析