在文法生成语言的过程中,推导公式可以有多种表现形式。以文法为例:{S→AB, A→a, B→b},它允许两种不同的推导路径:S通过A和B的结合生成"ab",即S→AB→aB→ab;另一种是S→AB→Ab→ab。如果每次推导都从最左边的非终结符开始,如第一个例子中的方式,这种推导方式被称为左推导。如果一个文法存在两种不同的左推导方式产生相同的语言,那么我们称这个文法为二义性文法。反之,如果只有一个左推导方式,那么文法就是无二义的。
对于某些二义性文法,我们可以通过转换得到一个等价的无二义文法,尽管它们生成的语言相同。然而,有些语言本质上就是二义性的,这意味着不存在无二义文法能够完全描述它。例如,文法{S→A, S→a, A→a}就是一个二义性文法,因为它允许S直接生成a,也可以先生成A再生成a,两种方式都导致相同的结果。
上下文无关文法是文法的一种类型,它具有特定的结构和规则。尽管某些上下文无关文法可能表现出二义性,但这并不影响它们生成语言的能力。通过适当的转换,我们通常可以找到无二义的等价文法来描述同一个语言。
形式语言理论中一种重要的变换文法,用来描述上下文无关语言,在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上下文无关文法,因此应用十分广泛。