摘要:上下文无关文法 正文 形式语言理论中一种重要的变换文法,用来描述上下文无关语言,在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上下文无关文法,因此应用十分广泛。 范式 上下文无关文法可以化为两种简单的范式之一,即任一上下文无关语言可用如下两种标准文法的任意一种生成:其一是乔姆斯基范式,它的产生式均取A→BC或A→α的形式;其二是格拉巴赫范式,它的产生式均取A→aBC或A→α的形式。其中A,B,C∈V,是非终结符,a∈Σ,是终结符;α∈Σ*,是终结符串。[阅读全文]