8(E+T,)# Reduce∶E→>E+T 9 Wny?不用E→T之 9(E # 若使用了E一>T,在栈中形成的(E+E不是规范句 型的活前缀( viable prefixes) (E+E不能和任何产生式的右端匹配(E+E)不是 规范句型 活前缀是规范句型(右句型)的前缀,但不超过 句柄 移进归约分析的中出现的内容加上余留输入 构成规范句型
8 (E + T )# Reduce:E –> E + T 9 why?不用 E –> T 9 (E ) # 若使用了E –> T，在栈中形成的(E+E不是规范句 型的活前缀（viable prefixes） （E+E不能和任何产生式的右端匹配 （E+E）不是 规范句型 活前缀 是规范句型（右句型）的前缀，但不超过 句柄 ❖ 移进归约分析的栈中出现的内容加上余留输入 构成规范句型
规范推导规范句型规范归约 最右推导:在推导的任何一步α→β,其中a、β是句型,都是对a中 的最右非终结符进行替换 最右推导被称为规范推导 由规范推导所得的句型称为规范句型 GS]:S→EE→E+T|TT→(E)|int S→E→T→(E)→E+1→(E+int) →(T+int)→( infant) 规范归约 假定a是G的一个句子,称序列an,an1…,a是a的一个规范归约 如果该序列满足: (1)a (2)a0为文法的开始符号 (3)对任何j,0<j,α是从a经把句柄替换为相应产生式的左部 而得到的
规范推导 规范句型 规范归约 最右推导：在推导的任何一步αβ，其中α、β是句型，都是对α中 的最右非终结符进行替换 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型 G[S]： S→E E→E+T|T T→(E)|int SE T (E) (E+T) (E+int) (T+int) (int+int) 规范归约 假定α是G的一个句子，称序列αn ,αn-1 …,α0是 α的一个规范归约 如果该序列满足： （1） αn = α （2） α0为文法的开始符号 （3）对任何j,0<j<=n, αj-1是从αj经把句柄替换为相应产生式的左部 而得到的
文法要求 shift-reduce or reduce-reduce冲突( conflicts) 分析程序不能决定是shif还是 reduce 或者分析程序归约时有多个产生式可选 例子( dangling else S-> if e then s if e then s else S 如输入 E then if e then s else s 分析某一时刻,栈的内容 E then if e then s 而else是下一 token归约还是移进?
文法要求 shift-reduce or reduce-reduce 冲突（conflicts） 分析程序不能决定是shift 还是 reduce 或者分析程序归约时有多个产生式可选 例子 （ dangling else） ： S –> if E then S | if E then S else S 如输入if E then if E then S else S 分析某一时刻，栈的内容:if E then if E then S 而 else 是下一 token 归约还是移进？
特定的一种s shift-reduce安现技术立 LR分析 L R最右推导 分析器模型和分析算法 LR分析特征讨论
特定的一种shift-reduce实现技术 ＬＲ分析 L R 最右推导 分析器模型和分析算法 ＬＲ 分析特征讨论
LR分析器模型 栈 npu # SIX 总控程序 output S1 X1 SO|# ACTION GOTO 状态一文法符号LR分析表 生 式 表
ＬＲ分析器模型 总控程序 output Input# S1 Xm … S1 … X1 S0 # 栈 状态 文法符号 ACTION GOTO LR分析表 产 生 式 表