Context-Free Language

定义 Definition

上下文无关语言：一种形式语言，其所有字符串都能由某个上下文无关文法（CFG）生成。它常用于描述编程语言的语法结构（如括号匹配、表达式的递归结构等）。除这一常见含义外，“language”在日常英语中也可指自然语言，但此处为计算机科学/语言学中的专门术语。

发音 Pronunciation (IPA)

/ˈkɑːn.tɛkst friː ˈlæŋ.ɡwɪdʒ/

例句 Examples

A context-free language can describe nested parentheses.
上下文无关语言可以描述嵌套的括号结构。

In compiler design, many programming-language syntaxes are modeled as context-free languages, though extra rules are often needed for semantic checks.
在编译器设计中，许多编程语言的语法会被建模为上下文无关语言，不过进行语义检查时通常还需要额外规则。

词源 Etymology

“context-free”由 context（上下文）+ free（不依赖、无须） 组成，意思是“不需要依赖周围上下文”。在形式语言理论里，它强调产生式规则的应用只取决于一个非终结符本身，而不取决于它在字符串中的邻接环境；“language”在此指“由规则生成的字符串集合”。

相关词 Related Words

• Context-Free Grammar
• Grammar
• Formal Language
• Parse Tree
• Pushdown Automaton
• Regular Language
• Chomsky Hierarchy
• Parsing

文学/著作中的用例 Literary / Notable Works

• Noam Chomsky（乔姆斯基）《Three Models for the Description of Language》（1956）：在形式文法框架下讨论语言描述模型，与上下文无关语言体系密切相关。
• John E. Hopcroft & Jeffrey D. Ullman《Introduction to Automata Theory, Languages, and Computation》：系统讲解上下文无关语言、下推自动机与解析。
• Michael Sipser《Introduction to the Theory of Computation》：以清晰的教学方式介绍上下文无关语言及其性质。
• Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman《Compilers: Principles, Techniques, and Tools》（“龙书”）：在编译原理中大量使用上下文无关语言/文法来描述语法分析。