PPT《编译原理与技术》

编译原理与技术 --自底向上分析 自底向上分析 移进-归约分析分析树的构建 从叶子结点开始,逐步构造各内部结点直至根结点出现.

分析技术的关键-句柄的识别句柄(handle)是什么? 简单讲,句柄是一个产生式的右部;

自底向上分析(移进-归约分析)过程,其实就是发现句柄并将句柄(产生式右部)替换成相应左部非终结符的过程.该替换称为最左归约,它对应着某最右推导逆过程的一步. 自底向上分析 分析技术的关键-句柄的识别句柄(handle)是什么? 一般地,如果有以下最右推导序列, 则产生式A??及其在右句型???中的位置称为右句型???的句柄. 自底向上分析 e.g.17 文法G6 1)S?aABe 2)A?Abc 3)A?b 4)B?d 串abbcde$的分析过程. 输入串 a b b c d e $ a A b c d e $ a A d e $ a A B e $ S $ 最左归约 最右推导 自底向上分析 e.g.17 文法G6 1)S?aABe 2)A?Abc 3)A?b 4)B?d 串abbcde$的对应分析树的建立过程. 输入串 a b b c d e $ 自底向上分析 e.g.17 文法G6 1)S?aABe 2)A?Abc 3)A?b 4)B?d 串abbcde$的对应分析树的建立过程. 输入串 a b b c d e $ 自底向上分析 e.g.17 文法G6 1)S?aABe 2)A?Abc 3)A?b 4)B?d 串abbcde$的对应分析树的建立过程. 输入串 a b b c d e $ A 自底向上分析 e.g.17 文法G6 1)S?aABe 2)A?Abc 3)A?b 4)B?d 串abbcde$的对应分析树的建立过程. 输入串 a b b c d e $ A 自底向上分析 e.g.17 文法G6 1)S?aABe 2)A?Abc 3)A?b 4)B?d 串abbcde$的对应分析树的建立过程. 输入串 a b b c d e $ A A 自底向上分析 e.g.17 文法G6 1)S?aABe 2)A?Abc 3)A?b 4)B?d 串abbcde$的对应分析树的建立过程. 输入串 a b b c d e $ A A B 自底向上分析 e.g.17 文法G6 1)S?aABe 2)A?Abc 3)A?b 4)B?d 串abbcde$的对应分析树的建立过程. 输入串 a b b c d e $ A A B S 移进-归约分析 e.g.17 用栈来实现串abbcde$的分析(1) 分析栈 输入串 动作 $ a b b c d e $ $ a b b c d e $ 移进a $ a b b c d e $ 移进b $ a A b c d e $ 归约:A?b $ a A b c d e $ 移进b $ a A b c d e $ 移进c 移进-归约分析 e.g.17 用栈来实现串abbcde$的分析(2) 分析栈 输入串 动作 $ a A b c d e $ 移进c $ a A d e $ 归约: A?Abc $ a A d e $ 移进d $ a A B e $ 归约:B?d $ a A B e $ 移进e $ S $ r: S?aABe 分析成功! 移进-归约分析 四种分析动作(action)? 移进(shift)-将当前输入符号移入栈顶top(why?) ? 归约(reduce)-当 句柄 出现在栈顶(从栈中某处到栈顶top),则将 句柄 从栈顶弹弹出,并将相应产生式左部非终结符置入栈顶top.(when?) ? 接受(accept)-分析成功! ? 报错(error)-出现语法错误,调错误恢复例程 移进-归约分析 分析动作冲突 ? 移进-归约冲突(shift-reduce conflict)当 句柄 处于栈顶时,分析动作指示既可以将下一输入符号移入栈顶top,又可以实施归约操作.如何动作呢? ? 归约-归约冲突(reduce-reduce conflict) 位于栈顶的 句柄 ,同时匹配两个(以上)产生式的右部.选谁呢? 怎么可能呢? 移进-归约分析冲突 二义文法G不适合移进-归约分析 e.g.

18 移进-归约冲突文法G7: S? if E then S | if E then S else S S? a $... … if E then S 句柄 ? else... … 分析栈 输入串: 当前输入符号 $... … if E then S else 栈顶 ... … 分析栈 输入串: S else ... … 分析栈 输入串: -归约动作 -移进动作 文法G7: S? if E then S | if E then S else S | a 期待新的 长句柄 e.g.19 二义性文法G8如下:E?E+E | E * E | (E) | id 输入串id+id+id$的最右推导:1)E?E+E?E+id?E+E+id?E+id+id?id+id+id2)E?E+E?E+E+E?E+E+id?E+id+id?id+id+id带下划线的符号串是相应句型的句柄. 移进-归约分析冲突 e.g.19输入串id+id+id$的栈分析过程 分析1)输入串分析2)id+id+id$id +id+id$id$E +id+id$E $E+id+id$E+$E+id +id$E+id$E+E +id$E+E$E +id$ id$E+E+ 归约 移进 e.g.19输入串id+id+id$的栈分析过程 分析1) 输入串分析2)$E+E +id$ +id$E+E$E +id$ id$E+E+$E+id$E+E+id$E+id E+E+E$E+E E+E $E E 移进-归约分析冲突 归约-归约冲突e.g.20 文法G91)Stat?id ( para_list ) | expr := expr2)para_list?para_list , para | para3)para?id4)expr?id ( expr_list ) 5)expr?id6)expr_list?expr_list , expr | expr e.g.20分析输入串id(id,id)$ 分析栈输入串 $ id ( id , id ) $1) $ id ( expr , id ) $2)id ( para , id ) $ para?id,目标:过程调用语句 expr?id 目标:数组引用 LR分析器 高效易实现的自底向上的分析方法文法限制少,适用于大多数CFG(包括含左递归、左因子的文法)LR(k)分析器L - 从左自右读(read from Left to right)R- 构造最右推导的逆(for constructing a Rightmost derivation in reverse) k - 向前看符号的个数(the number of input symbols of lookhead) LR分析器 输入串 LR控制程序 LR分析表 Sm Xm . . S0 a1 . . ai . . $ 状态 符号 栈 输出 Top Bottom 动作表Action 转移表GOTO 格局: 状态符号栈 输入串 分析表?动作表(Action):S ? (??{$})? { shift , reduce, accept, error}?转移表(GOTO):S ? VN ? S LR分析器 分析算法初始,状态S0位于栈底(栈顶);