例:若有文法G2S]为: s→ApS→BqA→aA→cAB→bB-→dB 当输入串W=coap,那么试图推出输入串的推导过程为: S=>Ap=>CAp=>CCAp=>ccap A PAPA p A A a a) (b) (c) (d)
例：若有文法G2 [S]为： S→Ap S→Bq A→a A→cA B→b B→dB 当输入串W=ccap,那么试图推出输入串的推导过程为： S=>Ap=>cAp=>ccAp=>ccap
例:若有文法G3[S] S→aAS→dA→bAsA 若输入串为W=abd,则试图推导出abd串的推导过程为: S=>aA=>abAs=>abs=>abd A=aA=a b As b A s b A E
例：若有文法G3 [S]： S→aA S→d A→bAS A→ε 若输入串为W=abd,则试图推导出abd串的推导过程为： S=>aA=>abAS=>abS=>abd
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)i
4.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
般地: A→>Aa1Aa2|Aa3|…|Aanmβ1B2|3…|3n 改写成: A→B1A|B2AB3A…|BnA A→a1A|a2Aas3A…|mAlE 例:消去S→SSSS+|a中的左递归。 解:S→aS S’→S*SlS+S|E
一般地： A→Aα1 |Aα2 |Aα3 |···|Aαm|β1 |β2 |β3 |···|βn 改写成： A→β1 A’|β2 A’|β3 A’|···|βnA’ A’→ α1 A’|α2 A’|α3 A’|···|αm A’|ε 例：消去S→SS*|SS+|a中的左递归。 解：S→aS’ S’→ S*S’| S+S’|ε
(2)间接左递归的消除 如果一个文法是无环的(即P=+=>P)和没有E产生式,那么 可用下列算法消除 a以任意次序排列非终结符A1A2A3,…An b.for(i=1;<=n;i++) for(j=1; j<=1-1: j ++) 用产生式A61V|6263…|6k代替每个形式为 A→AY的产生式其中A→6162636是所有当前 生式; 消去A产生式中的直接左递归 C.除去那些从开始符号出发永远无法到达的非终结符的产生规 贝
(2)间接左递归的消除 如果一个文法是无环的(即P=+=>P)和没有ε产生式，那么 可用下列算法消除。 a.以任意次序排列非终结符A1 ,A2 ,A3 ,···,An b.for(i=1;i<=n;i++) { for(j=1;j<=i-1;j++) 用产生式Ai→δ1γ|δ2γ|δ3γ|···|δkγ代替每个形式为 Ai→Ajγ的产生式其中Aj→δ1 |δ2 |δ3 |···|δk是所有当前 Aj 产生式； 消去Ai产生式中的直接左递归 } c.除去那些从开始符号出发永远无法到达的非终结符的产生规 则