4.1.1回溯的消除及LL(1)文法 为解决回溯问题，我们从句子的最 为得到w的剩余部分aa+…am.由最左 左推导开始讨论. 推导的定义，考虑A的所有产生式： 设G=(N,VT,P,S)为一CFG, W=a1a..a是Vr上的符号串，现需判 A→Y1IY2…|Ym 明是否是L(G)中的句子.为此，从 $开始进行最左推导.设经若干步 对于当前输入符号a,若只有一个 推导后我们得到 (称为候选式)使得从Yβ出发可以推 导出一个以ā打头的符号串： S→w,4βA∈VxB∈V(4.17 YB→a,… 且w1=a,a2a-,l≤i≤n 而其它的Y(kj),YkB都推导不出以 a打头的符号串，则选定产生式A→M 注意，i=1时，w=8,A=S 就是唯一可行的推导即 由假设可知，到目前为止，w的前缀w1 WEL(G)→选A-→Y正确； 已匹配，现在需对AB进行推导. 影(G→选任何产生式均不能匹 显然，若P中产生式能满足上述要求， 则回湖可消除4.1.1 回溯的消除及LL(1)文法 • 为解决回溯问题,我们从句子的最 左推导开始讨论. • 设G=(VN,VT,P,S) 为一CFG, w=a1a2…an是VT上的符号串,现需判 明w是否是L(G)中的句子.为此,从 S开始进行最左推导.设经若干步 推导后我们得到 w a a a i n S w A A V V i N =       − ,1 (4.17) 1 1 2 1 * 1 * 且  注意,i=1时,w1=,A=S 由假设可知,到目前为止,w的前缀w1 已匹配,现在需对A进行推导. A m →  |  | |  1 2  对于当前输入符号ai,若只有一个 j (称为候选式)使得从j出发可以推 导出一个以ai打头的符号串:  j  * ai  而其它的k(kj), k 都推导不出以 ai打头的符号串,则选定产生式A→j 就是唯一可行的推导,即 wL(G)选A→j正确; wL(G)选任何产生式均不能匹 配 显然,若P中产生式能满足上述要求, 则回溯可消除 为得到w的剩余部分aiai+1…an.由最左 推导的定义,考虑A的所有产生式: