直接推导（直接归约）p22-23 口产生式右部代替左部 口当A→Y是文法G的一个产生式， 则有aAB=>aYB, 称aYB是aAB的直接推导 或称aYB直接归约到aAB G[E]E-E +EEE(E)i oE=>E+E=>i+E=>i+E米E 特点：只能用一次产生式替换 D
6 直接推导（直接归约）p22-23 产生式右部代替左部 当Ａ→γ是文法Ｇ的一个产生式， 则有αＡβ => αγβ， 称αγβ是αＡβ的直接推导 或称αγβ直接归约到αＡβ G[E]:E→E + E|E * E|( E )|i E=>E + E=>i + E => i + E * E 特点：只能用一次产生式替换
推导（归约)p23 0如果a0=〉a1=〉a2=>.=〉an,则称这个序列 是从ao至an的一个推导。 口用ao=t>an表示从ao出发，经一步或多步推 导，可推出ano 口例如E=>E*E=〉1*E=〉1*1 口E=+>i*i至少用一次产生式替换。 口用a>an表示从ao出发，经零步或多步推 导，可推出an,即aoan或a0t>an。 口例如E=E 加E=*〉E可以不用产生式替换
7 推导（归约）p23 如果α0=>α1=>α2=>.=>αn，则称这个序列 是从α0至αn的一个推导。 用α0= +>αn表示从α0出发，经一步或多步推 导，可推出αn。 例如 E => E * E => i * E => i * i E =+> i * i 至少用一次产生式替换。 用α0= *>αn表示从α0出发，经零步或多步推 导，可推出αn ，即α0=αn或α0= +>αn 。 例如 E = E E =*> E 可以不用产生式替换
句型和句子生成举例 口例：文法G(E)为： E→E+EE米E(E)i 口表达式（i*i+i)的生成 0E=>（E) => (E+E) =〉 （E米E+E) 句型(UV)* 0 =〉 (i E +E) 0 =〉 ii+E) 0 7 (i*i+i)句子V* ☒2
8 例: 文法G(E)为： E → E + E | E * E | ( E ) | i 表达式 (i * i + i) 的生成 E => ( E ) => ( E + E ) => ( E * E + E ) => ( i * E + E ) => ( i * i + E ) => ( i * i + i ) 句型和句子生成举例 句型(VT∪VN) * 句子 VT *
句型p23 口设G是一个文法 oS是开始符号，若有S=*>a,则称是α文法G的 一个句型。 0句子 0 完全由终结符组成的句型。 口合法句子的生成 口从S出发反复推导，每次得到一个句型，最终得 到句子。 L 9
9 句型 p23 设G是一个文法 S是开始符号，若有 S = *>α，则称是α文法G的 一个句型。 句子 完全由终结符组成的句型。 合法句子的生成 从Ｓ出发反复推导，每次得到一个句型，最终得 到句子
句型和句子生成练习 o例：文法G[E]为： E→E+EE*E（E)i 口表达式 i+i*i的生成BEGIN oE => E+E 0 => i+E 句型 0 => i+E米E => i+i米E => i+i*i 句子 口表达式i*(i+i)的生成过程 BEGIN 4 ☒ 0
10 例: 文法G[E]为： E → E + E | E * E | ( E ) | i 表达式 i + i * i 的生成 BEGIN E => E + E => i + E => i + E * E => i + i * E => i + i * i 句型和句子生成练习 句型 句子 表达式 i*(i+i)的生成过程 BEGIN