上下文无关文法

定义

上下文无关文法是一种形式文法，由终结符、非终结符、起始符和一组产生式规则组成。每条产生式的左侧只有一个非终结符，右侧是终结符与非终结符的序列，因而替换不受上下文限制，故称「上下文无关」。

原理

从起始符出发，反复用产生式右侧替换非终结符，直到全部变为终结符，便生成一个句子。这一推导过程天然形成树状结构，即语法分析树。上下文无关文法能描述任意深度的嵌套，例如配对的括号或层层包含的表达式，这正是正则语言无法表达的能力。它对应的识别机器是带有栈的下推自动机。

应用

几乎所有编程语言的语法都用上下文无关文法定义，常以巴科斯范式书写。编译器的语法分析阶段依据文法构建语法树，自然语言处理也借助它分析句子结构。文法的二义性是设计时需要避免的问题，开发者会通过改写规则或规定运算符优先级来消除歧义，保证每个句子有唯一的解析结果。