【上下文无关文法】上下文无关语法是一种形式语法, 用于以给定形式语言生成所有可能的字符串。
上下文无关文法G可以由四个元组定义为：
G= (V, T, P, S)哪里,
G描述语法
T描述了一组有限的终端符号。
V描述了一组有限的非终端符号
P描述了一组生产规则
S是开始符号。
在CFG中, 起始符号用于导出字符串。你可以通过在生产的右侧重复替换一个非终结符来导出字符串, 直到所有非终结符都被终结符替换为止。
例：
L= {wcwR | w € (a, b)*}生产规则：
S → aSaS → bSbS → c现在检查abbcbba字符串是否可以从给定的CFG派生。
S ? aSaS ? abSbaS ? abbSbbaS ? abbcbba通过递归应用产品S→aSa, S→bSb, 最后应用产品S→c, 我们得到字符串abbcbba。
