编译原理 培法分析一自下而上分析 练习：设文法G(E)如下，试对i*i+i进行 “移进一归约”分析。 G(E):E→i川E+E|E-E|E*E|EE|(E) i*i+i E*i+i E*E+i E E+i E 米 E+E E 第引1页
编译原理 第11页 语法分析-自下而上分析 练习： 设文法G(E)如下，试对i*i+i进行 “移进－归约”分析。 G(E)： E → i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E i + * E i i E E E E
编泽原理 培法分折一自下而上分析 5.1.2规范归约 定义： @有文法G,开始符号为S,如果有S=>xy,则xy是文法G的 句型X,y是任意的符号串。 @如果有S>xAy,且有A=>B,则B是句型xy相对于非终结符A 的短语 @如果有S三>xAy,且有A->B,则B是句型xy相对于A->B的直接 短语 ©位于一个句型最左边的直接短语称为句柄. 句型>短语>直接短语>句柄 墨注：每次归约的部分必须是称之为句柄的字符串（最右 推导)。 墨关键的问题是如何识别句柄 第2觉
编译原理 第12页 语法分析-自下而上分析 5.1.2 规范归约 定义： 有文法G，开始符号为S, 如果有S=>xβy,则xβy是文法G的 句型，x,y是任意的符号串。 如果有S=>xAy, 且有A=>β,则β是句型xβy相对于非终结符A 的短语 如果有S=>xAy, 且有A->β,则β是句型xβy相对于A->β的直接 短语 位于一个句型最左边的直接短语称为句柄. 句型---> 短语 ---> 直接短语 --->句柄 注: 每次归约的部分必须是称之为句柄的字符串(最右 推导)。 关键的问题是如何识别句柄 * +
编泽原理 培法分析一自下而上分析 考虑文法G(E):E→T|E+T T->FT*F F-(E)i 和句型i1*i2+i3: E→E+T→E+F→E+i3→T+i3 →T*F+i3→T*i2+i3→F*i2+i3 →i1*i2tig 短语：i1,i2,3,i*i2,i*i2+i 直接短语：i1,i2,3 句柄：i 第3贡
编译原理 第13页 语法分析-自下而上分析 考虑文法G(E)： E → T | E+T T → F | T*F F → (E) | i 和句型i1 *i2+i3： E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1 *i2+i3 短语： i1，i2，i3， i1 *i2， i1 *i2+i3 直接短语： i1，i2，i3 句柄： i1
编泽原理 培法分折一自下而上分析 E 在一个句型对应的语 法树中，以某非终结符 E 十 T 为根的两代以上的子树 F 的所有叶子结点从左到 右排列就是相对于该非 T F 终结符的一个短语，如 果子树只有两代，则该 F 短语就是直接短语。 最左边的两代子树的 所有叶子结点从左到右 排列就是句柄。 第4负
编译原理 第14页 语法分析-自下而上分析 在一个句型对应的语 法树中，以某非终结符 为根的两代以上的子树 的所有叶子结点从左到 右排列就是相对于该非 终结符的一个短语，如 果子树只有两代，则该 短语就是直接短语。 最左边的两代子树的 所有叶子结点从左到右 排列就是句柄。 E F F T T T i1 + * E F i3 i2
编泽原理 培法分析一自下而上分析 练习：文法G(E)的另一个句型： E+T*F+i 其短语、直接短语、句柄分别是？ E→T|E+T T→F|T*F E F→i|(E) 短语有：i,T*F,E+T*F,E+T*F+i 直接短语有：i,T*F 句柄是：T*F 第5贡
编译原理 第15页 语法分析-自下而上分析 练习 ：文法G(E) 的另一个句型： E+T * F + i 其短语、直接短语、句柄分别是？ E→T | E+T T→F | T*F F→i | (E) E E + T F i E + T T * F 短语有：i, T * F, E+T * F, E + T * F + i 直接短语有： i, T * F 句柄是：T * F