上下文无关文法，在计算机科学中，若一个形式文法 G = 的产生式规则都取如下的形式：A -> α，则谓之。其中 A∈V ，α∈* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 A 总可以被字串 α 自由替换，而无需考虑字符 A 出现的上下文。如果一个形式语言是由上下文无关文法生成的，那么可以说这个形式语言是上下文无关的。。
1
扩展巴科斯-瑙尔范式是表达作为描述计算机编程语言和形式语言的正规方式的上下文无关文法的元语法符号表示法。它是基本巴科斯-瑙尔范式元语法符号表示法的一种扩展。
LL分析器是一种处理某些上下文无关文法的自顶向下分析器。因为它从左到右处理输入，再对句型执行上下文无关文法出语法树。能以此方法分析的文法称为LL 文法。
上下文有关文法是一种形式文法，其中任何产生式规则的左手端和右手端都可以被终结符和非终结符构成的上下文所围绕。上下文有关文法比上下文无关文法更一般性，但仍足够有秩序得可以被线性有界自动机所解析。
上下文有关文法是一种形式文法，其中任何产生式规则的左手端和右手端都可以被终结符和非终结符构成的上下文所围绕。上下文有关文法比上下文无关文法更一般性，但仍足够有秩序得可以被线性有界自动机所解析。
上下文无关语言是可以用上下文无关文法定义的形式语言。所有上下文无关语言的集合同一于下推自动机所接受的语言的集合。
LL分析器是一种处理某些上下文无关文法的自顶向下分析器。因为它从左到右处理输入，再对句型执行上下文无关文法出语法树。能以此方法分析的文法称为LL 文法。
在计算机科学中，声称一个上下文无关文法是Greibach 标准式
CYK算法是由约翰·科克，Younger和嵩忠雄共同研究出来大约发表于1965年的一个算法，它是一个用来判定任意给定的字符串
w
∈
Σ
∗
{\displaystyle ~w\in \Sigma ^{*}}
是否属于一个上下文无关文法的算法。普通的回溯法在最坏的情况下需要指数时间才能解决这样的问题，而CYK算法只需要多项式时间就够了。CYK算法采用了动态规划的思想。
Mini wiki
