将号串i+i*i的▣约过程 步序 当前符号串W 所用的产生式 归约后的符号 iti*i F→i F+i*i 1 F+i*i T→F T+i*i T+i*i E→T E+i*i 3 E+i*i F→i E+F*i E+F*i T→F E+T*i E+T*i F-i E+T*F 6 E+T*F T→T*F E+T 7 E+T E→E+T E 由上表可以看出， 归约过程是最左归约，它恰好是规 范推导的逆过程。这正是把最左归约定义为规范归约 的原因
符号串i+i*i的归约过程 步序 当前符号串 wi 所用的产生式 归约后的符号 0 i+i*i F→i F+i*i 1 F+i*i T→F T+i*i 2 T+i*i E→T E+i*i 3 E+i*i F→i E+F*i 4 E+F*i T→F E+T*i 5 E+T*i F→i E+T*F 6 E+T*F T→T*F E+T 7 E+T E→E+T E 由上表可以看出，归约过程是最左归约，它恰好是规 范推导的逆过程。这正是把最左归约定义为规范归约 的原因
关于归约的一点说明 ·注意，前面例子中归约的第五步中，当前的符号串为 E+*i,除了可将归约成F外，还可将E+T或T归约成E, 分别得到符号串E*和E+E*i。但是，若真按这两个方案 进行归约，则当我们把其归约成E*E或E+E*E时，就再 也归约不下去了。这就告诉我们在第五步时，唯一正确 的归约是将归约为F,也就是说，是唯一可被归约的最 左子串。 那么，对于规范归约的每一步，如何确定符号串中的当 前应被归约的最左子串呢？ ·这里暂且按下不提，且听2.3.3小节分解
关于归约的一点说明 • 注意，前面例子中归约的第五步中，当前的符号串为 E+T*i，除了可将i归约成F外，还可将E+T或T归约成E， 分别得到符号串E*i和E+E*i。但是，若真按这两个方案 进行归约，则当我们把其归约成E*E或E+E*E时，就再 也归约不下去了。这就告诉我们在第五步时，唯一正确 的归约是将i归约为F，也就是说，i是唯一可被归约的最 左子串。 • 那么，对于规范归约的每一步，如何确定符号串中的当 前应被归约的最左子串呢？ • 这里暂且按下不提，且听2.3.3小节分解
2.32语法对和号义性 ·语法树用于直接地描述一个句型右句子的语法结构 语法树是一有向树（连通的) 1)有且仅有一个无任何前驱的结点，称为根（S); 2)除根外，每个结点恰有一个直接前驱； 3)对于任一结点m,从根m可达， 4)每个结点的后继是有序的（从左到右） 。 设G=,V,PS)是一文法，则满足下述条件的树称为语法树： 1)每个结点有一标记X,XeV; 2)根的标记为S(开始符)； 3)若结点X有后继，则XEVw; 4)A有k个后继，自左至右为X,X,X,则A→XX.X∈P
2.3.2 语法树和二义性 • 语法树用于直接地描述一个句型右句子的语法结构 • 语法树是一有向树（连通的） 1）有且仅有一个无任何前驱的结点，称为根 （S）； 2）除根外，每个结点恰有一个直接前驱； 3）对于任一结点m，从根到m可达; 4) 每个结点的后继是有序的（从左到右） • 设G=(VN,VT,P,S)是一文法，则满足下述条件的树称为语法树： 1）每个结点有一标记X，XV； 2）根的标记为S（开始符）； 3）若结点X有后继，则XVN； 4）A有k个后继，自左至右为X1, X2, …, Xk，则A→ X1X2…Xk P
语法树的性质及实例 。 语法树的所有叶结点自 E 左至右排列构成了文法G 的一个句型 ·对一语法树而言，其构造 过程不同对应了不同的推 导（归约）过程 例如，文法GE的句型 +*相应的语法树见右图。 i
语法树的性质及实例 • 语法树的所有叶结点自 左至右排列构成了文法G 的一个句型 • 对一语法树而言，其构造 过程不同对应了不同的推 导（归约）过程 • 例如，文法G[E]的句型 i+i*i相应的语法树见右图。 E E + T T F i T * F F i i