编泽原理 培法分析-自下而上分析 归约 采用“移进一归约”思想进行自下而上分析。 基本思想：用一个寄存符号的先进后出栈，把输 入符号一个一个地移进到栈里，当栈顶形成某个产 生式的候选式时，即把栈顶的这一部分替换成( 约为)该产生式的左部符号。 第26列
编译原理 第26页 语法分析-自下而上分析 归约 采用“移进－归约”思想进行自下而上分析。 基本思想：用一个寄存符号的先进后出栈，把输 入符号一个一个地移进到栈里，当栈顶形成某个产 生式的候选式时，即把栈顶的这一部分替换成(归 约为)该产生式的左部符号
编译原理 培法分析一自下而上分析 规范归约 定义：令G是一个文法，S是文法的开始符 号，假定cBδ是文法G的一个句型，如果有 S今46且ASB 则B称是句型oBδ相对于非终结符A的短语。 特别是，如果有A→B,则称B是句型Bδ相对 于规则A→B的直接短语。一个句型的最左 直接短语称为该句型的句柄。 第27贡
编译原理 第27页 语法分析-自下而上分析 规范归约 定义：令G是一个文法，S是文法的开始符 号，假定是文法G的一个句型，如果有 S * A 且 + A 则称是句型相对于非终结符A的短语。 特别是，如果有A,则称是句型相对 于规则A→ 的直接短语。一个句型的最左 直接短语称为该句型的句柄
编泽原理 培法分析一自下而上分析 定义：假定是文法G的一个句子，我们 称序列 0n’0n-l,…’00 是的一个规范归约，如果此序列满足： 10m=0 20为文法的开始符号，即oo=S 3对任何i,0≤i≤n,o.是从o经把句柄 替换成为相应产生式左部符号而得到的。 第28苑
编译原理 第28页 语法分析-自下而上分析 定义：假定是文法G的一个句子，我们 称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 2 0为文法的开始符号，即0=S 3 对任何i，0 i n， i-1是从i经把句柄 替换成为相应产生式左部符号而得到的
G(E): 晋法分析一自下而上分析 E→T|E+T T->FIT*F F→(E)I1 步骤 符号栈 输入串 动作 0 # i1*i2+i3# 预备 1 #i1 *i2+3# 进 2 #F *i2+i3# 归，用Fi 3 #T *i2+i3# 归，用T→F 4 #T* i2+i3# 进 第29贡1
编译原理 第29页 语法分析-自下而上分析 步骤 符号栈 输入串 动作 0 # i1*i2+i3# 预备 1 #i1 *i2+i3# 进 2 #F *i2+i3# 归，用F→i 3 #T *i2+i3# 归，用T→F 4 #T* i2+i3# 进 G(E)： E → T | E+T T → F | T*F F → (E) | i
G(E): 客法分析一自下而上分析 E→TIE+T T->FIT*F F→(E)1i 步骤 符号栈 输入串 动作 4 #T* i2+i3# 进 5 #T*i2 +i3# 进 6 #T*F +i3# 归，用Fi 7 #T +i3# 归，用T→T*F 8 #E +i3# 归，用ET 9 #E+ i3# 进 第30页
编译原理 第30页 语法分析-自下而上分析 步骤 符号栈 输入串 动作 4 #T* i2+i3# 进 5 #T*i2 +i3# 进 6 #T*F +i3# 归，用F→i 7 #T +i3# 归，用T→T*F 8 #E +i3# 归，用E→T 9 #E+ i3# 进 G(E)： E → T | E+T T → F | T*F F → (E) | i