| 上下文无关文法属于乔姆斯基定义的2型文法，被广泛地用于表示各种程序设计语言的语法。对于上下文无关文法G［S］=（VN，VT，P，S），其产生式的形式都是A→β，其中A∈VN，β∈（VN∪VT）*。
|
|
|
| 若不加特别说明，下面用大写英文字母A、B、C等表示非终结符，小写英文字母a、b、c等表示终结符号，u、v、w等表示终结符号串，小写希腊字母α、β、γ、δ等表示终结符和非终结符构成的文法符号串。由于一个上下文无关文法的核心部分是其产生式集合，所以文法可以简写为其产生式集合的描述形式。
|
|
|
（1）规范推导（最右推导）。如果在推导的任何一步 其中α、β是句型），都是对α中最右边的非终结符进行替换，则称这种推导为最右推导。最右推导常称为规范推导。同理可定义最左推导。
|
|
|
（2）短语、直接短语和句柄。设αδβ是文法G的一个句型，即 ，且满足 和 ，则称δ是句型αδβ相对于非终结符A的短语。特别地，如果有 ，则称δ是句型αδβ相对于产生式A→δ的直接短语。一个句型的最左直接短语称为该句型的句柄。
|
|
|
