32上下文无关文法(CFG) 定义33由CFGG所产生的语言L(G)被定义为 L(G=O S=+>0 and OET*i, C、L(G称为上下文无关语言( Context Free Language, ),O称为句子。 若S=*>0,α∈(NUT)*,则称α为G的一个句型。 定义34在推导过程中,若每次直接推导均替换句型中最左边 的非终结符,则称为最左推导,由最左推导产生的句型被称 为左句型。 类似可定义最右推导与右句型,最右推导也被称为规范推导 E→>→>(E)→>E+E)→>-(id+E)→>-(id+id) a1 a2 a3 04 05 06 06是句子,所有ai(i=1.6)均是句型。8 3.2 上下文无关文法(CFG) 定义3.3 由CFG G所产生的语言L(G)被定义为: L(G) = { ω┃S=+>ω and ω∈T* }， L(G)称为上下文无关语言(Context Free Language, CFL)，ω称为句子。 若S=*>α，α∈(N∪T)*，则称α为G的一个句型。 定义3.4 在推导过程中，若每次直接推导均替换句型中最左边 的非终结符，则称为最左推导，由最左推导产生的句型被称 为左句型。 类似可定义最右推导与右句型，最右推导也被称为规范推导。 E => -E => -(E) => -(E+E) => -(id+E) => -(id+id) α1 α2 α3 α4 α5 α6 α6是句子，所有αi (i=1...6)均是句型