归约是推导的逆过程,是把当前的符号串Ba8中构成文 法某个产生式4→a右部的子串a替换成产生式的左部 符号A,得到一个新的符号串B4δ。这样的一步动作, 称为进行了一步归约。 例如,符号串F+中的F可按产生式T少F归约为T, 从而得到新的符号串T+ 若归约的每一步都归约的是当前符号串中最左边的某 产生式的右部,则称该归约是最左归约。 最左归约是最右推导(规范推导)的逆过程,因此最 左归约也称为规范归约
6 自底向上的语法分析——归约 • 归约是推导的逆过程，是把当前的符号串中构成文 法某个产生式A→右部的子串替换成产生式的左部 符号A，得到一个新的符号串A。这样的一步动作， 称为进行了一步归约。 • 例如，符号串F+i*i中的F可按产生式T→F归约为T， 从而得到新的符号串T+i*i。 • 若归约的每一步都归约的是当前符号串中最左边的某 产生式的右部，则称该归约是最左归约。 • 最左归约是最右推导（规范推导）的逆过程，因此最 左归约也称为规范归约
自底向上的语法分析:从已给的符号串w出发,试图以 相反的方向为w建立一个规范推导,最终得到文法的 开始符。 若从给定的符号串w出发,一步步地将其归约,最终 得到文法的开始符号,则归约成功,说明w是该文法 定义的一个句子;否则,w不是该文法定义的句子
7 自底向上的语法分析过程 • 自底向上的语法分析：从已给的符号串w出发，试图以 相反的方向为w建立一个规范推导，最终得到文法的 开始符。 • 若从给定的符号串w出发，一步步地将其归约，最终 得到文法的开始符号，则归约成功，说明w是该文法 定义的一个句子；否则，w不是该文法定义的句子
符号串计i的归约过程 步序 当前符号串w 所用的产生式 i+ii G2{E: F+i*i T→F E→>E+TT 2 +i*i E→T T→>TF|F E+ii F→i F→>(E)i E+Fxi T→F E+TMi F→i E+TMF 个→T*F 7 E+T E→E+T 8 E 由上表可以看出,该归约过程是最左归约,其逆过程 就是规范推导(式25)
8 符号串i+i*i的归约过程 步序 当前符号串 wi 所用的产生式 0 i+i*i F→i 1 F+i*i T→F 2 T+i*i E→T 3 E+i*i F→i 4 E+F*i T→F 5 E+T*i F→i 6 E+T*F T→T*F 7 E+T E→E+T 8 E 由上表可以看出，该归约过程是最左归约，其逆过程 就是规范推导（式2.5）。 G2[E]: E→E+T|T T→T*F|F F→(E)|i
关于归约的一点说明 对于前面例子中归约的第五步,当前的符号串为E+T 有,可以有以下几种规约 E+T归约为符号串E站,继续归约得EE, 无法继续进行归约 E+T归约为符号串E+E,继续归约得E+EE, 无法继续进行归约 E+T归约为符号串E+TF,这是唯一正确的归约, 也就是说,i是唯一可被归约的最左子串。 那么,对于规范归约的每一步,如何确定符号串中的当 前应被归约的最左子串呢?这个问题将在23.3小节进行 讨论
9 关于归约的一点说明 • 对于前面例子中归约的第五步，当前的符号串为E+T*i， 有，可以有以下几种规约： E+T*i 归约为符号串E*i ，继续归约得E*E， 无法继续进行归约 E+T*i 归约为符号串E+E*i ，继续归约得E+ E*E， 无法继续进行归约 E+T*i 归约为符号串E+T*F ，这是唯一正确的归约， 也就是说，i是唯一可被归约的最左子串。 • 那么，对于规范归约的每一步，如何确定符号串中的当 前应被归约的最左子串呢？这个问题将在2.3.3小节进行 讨论