【编译原理】什么是上下文无关文法、上下文有关文法？_上下文无关文法和上下文有关文法

百度百科解释：

上下文无关文法（英语：context-free grammar，缩写为CFG），在计算机科学中，若一个形式文法G = (N, Σ, P, S) 的产生式规则都取如下的形式：V->w，则谓之。其中 V∈N ，w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V 出现的上下文。

上下文有关文法(CSG)是其中任何产生规则的左手端和右手端都可以被终结符和非终结符的上下文所围绕的形式文法。上下文有关文法比上下文无关文法更一般性但仍足够有秩序得可以被线性有界自动机所解析。

百度百科的定义可能有点难理解，以下的解释会更为清晰直观：

一、上下文无关文法

上下文无关文法就是说这个文法中所有的产生式左边只有一个非终结符，比如：

S -> aSb
S -> ab
1
2

这个文法有两个产生式，每个产生式左边只有一个非终结符 S，这就是上下文无关文法，因为你只要找到符合产生式右边的串，就可以把它归约为对应的非终结符。

二、上下文有关文法

比如：

aSb -> aaSbb
S -> ab
1
2

这就是上下文有关文法，因为它的第一个产生式左边有不止一个符号，所以你在匹配这个产生式中的S的时候必需确保这个S有正确的“上下文”，也就是左边的a和右边的b，所以叫上下文相关文法。

参考：
知乎：https://www.zhihu.com/question/21833944