上下文无关文法
| 上下文无关语言 | |
|---|---|
| 术语名称 | 上下文无关语言 |
| 英语名称 | context-free language |
| 上下文无关文法 | |
|---|---|
| 术语名称 | 上下文无关文法 |
| 英语名称 | context-free grammar |
| 别名 | CSG |
| 2型语言 | |
|---|---|
| 术语名称 | 2型语言 |
| 英语名称 | type-2 language |
| 2型文法 | |
|---|---|
| 术语名称 | 2型文法 |
| 英语名称 | type-2 grammar |
上下文无关文法(context-free grammar, CFG)指一种形式语言的生成文法，要求每个符号生成其他符号时，生成规则固定，不依赖于上下文其他符号。是 Chomsky 生成语法理论中的2 型文法(type-2 grammar)。上下文无关字面意义上地意味着这个语言中任何非终结符被重写为其他符号串时不会受到上下文的其他符号影响。
定义
若生成文法中，全部文法均有形式：
[math]\displaystyle{ A \rightarrow \alpha }[/math]
其中， [math]\displaystyle{ \alpha }[/math] 为任意终结符和非终结符构成的序列， [math]\displaystyle{ A }[/math] 为一个非终结符，
则称该文法为一种上下文无关文法(context-free grammar, CFG)，由这种文法生成的语言称为上下文无关语言(context-free language)。
有些定义中也允许添加 [math]\displaystyle{ S\rightarrow \epsilon }[/math] 来允许概念范围中允许任意符号生成空串。
说明
以上为形式化定义。通俗地说，上下文无关文法的含义是，文法中每个非终结符一定可以被展开生成其他文法符号串，且这一展开规则不受上下文中的其他序列影响。
与上下文有关文法相比，上下文无关文法的展开方式完全不依赖上下文，每个非终结符总是有固定的展开方式。 上下文无关文法对于非终结符生成后的内容没有要求，如果要求右侧只能是一个终结符或者非终结符加一个终结符， 也就是说每次或者减少一个可展开文法符号，或者只向符号串中增加一个不可展开的文法符号，就得到了更加严格的正则文法。
性质
上下文无关语言的：
都仍然是上下文无关的。
自动机等价
正则文法的表达能力等价于 Backus–Naul 范式。