4.1.2左递归和回溯性 1.左递归 左递归在自顶向下的分析技术中是有害的,为此使用 自顶向下的芬析方法的文法中不能出现左递归,因此需要消 去左递归。如果对于某非终结符A存在着推导A=+=>Aα,则 称文法左递归或间接左递归;如果存在规则A→Aα,则称 规则左递归或直接左递归。对于规则左递归是可以消除的, 而对文法左递归只能对满足一定条的文法进行消去。 (1)规则左递归的消除 a改写规则成右递归 把E→E+TT改写成E→T+ET 虽然在这里消去了左递归并不改变语言,但改变了结合性 b引进新的文法符号把E→E+TTT→TFF→(E改写 成 E→忙E+T→F节*TεF→(E)i4.1.2 左递归和回溯性 1.左递归 左递归在自顶向下的分析技术中是有害的，为此使用 自顶向下的分析方法的文法中不能出现左递归,因此需要消 去左递归。如果对于某非终结符A存在着推导A=+=>Aα，则 称文法左递归或间接左递归；如果存在规则A→Aα，则称 规则左递归或直接左递归。对于规则左递归是可以消除的， 而对文法左递归只能对满足一定条的文法进行消去。 (1)规则左递归的消除 a.改写规则成右递归 把 E→E+T|T 改写成 E→T+E|T 虽然在这里消去了左递归并不改变语言，但改变了结合性。 b.引进新的文法符号把E→E+T|T T→T*F|F F→(E)|i 改写 成 E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i