归约 ■采用“移进一按约”思想进行自下而上分析。 ■ 基本思想：用一个寄存符号的先进后出栈，把输 入符号一个一个地移进到栈里，当栈顶形成某个 产生式的候选式时，即把栈顶的这一部分替换成 (约为)该产生式的左部符号。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 归约 ◼ 采用“移进－归约”思想进行自下而上分析。 ◼ 基本思想：用一个寄存符号的先进后出栈，把输 入符号一个一个地移进到栈里，当栈顶形成某个 产生式的候选式时，即把栈顶的这一部分替换成 (归约为)该产生式的左部符号
规范归约 ■ 定义：令G是一个文法，S是文法的开始符 号，假定oBδ是文法G的一个句型，如果有 SSM6且A5B 则B称是句型Bδ相对于非终结符A的短语。 特别是，如果有A→B,则称B是句型oBδ相对 于规则A→B的直接短语。一个句型的最左 直接短语称为该句型的句柄。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 规范归约 ◼ 定义：令G是一个文法，S是文法的开始符 号，假定是文法G的一个句型，如果有 S * A 且 + A 则称是句型相对于非终结符A的短语。 特别是，如果有A,则称是句型相对 于规则A→ 的直接短语。一个句型的最左 直接短语称为该句型的句柄
■ 定义：假定是文法G的一个句子，我们 称序列 0n’0n-1’.’00 是的一个规范归约，如果此序列满足： 10n=0 20为文法的开始符号，即o,=S 3对任何i,0≤i≤n,1是从，经把句 柄替换成为相应产生式左部符号而得到 的。 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 ◼ 定义：假定是文法G的一个句子，我们 称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 2 0为文法的开始符号，即0=S 3 对任何i，0 i n， i-1是从i经把句 柄替换成为相应产生式左部符号而得到 的
G(E): E→TIE+T T→FIT*℉ F→(E)|i 步骤 符号栈 输入串 动作 0 # i1*i2+i3# 预备 1 #i1 *i2+i3# 进 2 #F *i2+i3# 归，用Fi 3 #T *i2+i3# 归，用T→F 4 #T* i2+i3# 进 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 步骤 符号栈 输入串 动作 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→T|E+T T→F|T*F F→(E)Ii 步骤 符号栈 输入串 动作 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# 进 国防科技大学计算机系602教研室
国防科技大学计算机系602教研室 步骤 符号栈 输入串 动作 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