A 出现的上下文。如果一个形式语言是由上下文无关文法生成的，那么可以说这个形式语言是上下文无关的。（条目上下文无关语言）。 上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面，上下文无关文法...

在形式文法理论中，确定上下文无关文法(DCFG)是上下文无关文法的真子集。确定上下文无关文法是确定下推自动机可识别的文法。确定上下文无关语言是确定上下文无关文法所定义的形式语言。 它们在计算机科学领域中特别重要，因为这些文法可以有效的识别，而非确定上下文无关文法...

上下文有关文法（CSG，英語：context-sensitive grammar）是一種形式文法，其中任何产生式规则的左手端和右手端都可以被终结符和非终结符構成的上下文所围绕。上下文有关文法比上下文无关文法更一般性，但仍足够有秩序得可以被线性有界自动机所解析。 上下文有关文法...

随機上下文无关文法（英語：Stochastic context-free grammar）即在上下文无关文法中，为每一个产生式规则赋予一个概率，标示应用一个产生式规则的可能性。 上下文有关文法 形式文法 分析表达式文法 随机上下文无关文法...

正规语言类包含于上下文无关语言类，上下文无关语言类包含于上下文相关语言类，上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系，也就是说：存在递归可枚举语言不属于上下文相关语言类，存在上下文相关语言不属于上下文无关语言类，存在上下文无关语言不属于正规语言类。 下表总结了上述四种类型的文法的主要特点：...

上下文无关语言是可以用上下文无关文法定义的形式语言。所有上下文无关语言的集合同一于下推自动机所接受的语言的集合。 一个原型上下文无关语言是 L = { a n b n : n ≥ 1 } {\displaystyle L=\{a^{n}b^{n}:n\geq 1\}} ，它是所有非空、偶数长度字符串的语言，字符串的整个前半部分都是...

1956年诺姆·乔姆斯基首次将生成文法形式化时， 他将它们分为现在称为乔姆斯基谱系的四种类型。其中两种重要的文法类型分别是上下文无关文法（2型）和正则文法（3型）。可以用这两种文法描述的语言分别称为上下文无关语言和正则语言。尽管比无限制文法（0型，实际上无限制文法...

Ford）推出，它与20世纪70年代初引入的自顶向下的语法分析语言（英语：Top-down parsing language）家族密切相关。 在语法上，PEG很接近上下文无关文法（CFG），但是他們採用了不同的解釋：例如PEG中的选择操作符總是会选中第一个匹配项，而在CFG中则是不明确的。这更接近于字符串识别在实际中的...

文法由此排除了所有包含歧义和左递归的文法。虽然任何一种上下文无关文法都可以转化为没有左递归的等效文法，但是去除了左递归却不一定能够得到 LL(k) 文法。预测性解析器能够在线性时间内运行。 具有回溯的递归下降是一种通过依次尝试生成规则来生成结果的技术。具有回溯的递归下降不限于 LL(k) 文法，但只在文法是...

LL分析器是一种处理某些上下文无关文法的自顶向下分析器。因为它从左（Left）到右处理输入，再对句型执行最左推导出语法树（Left derivation，相对于LR分析器）。能以此方法分析的文法称为LL文法。 在解析句子时使用 k {\displaystyle k} 个词法单元作向前探查的LL分析器被称为...

BNF），又称为巴科斯-诺尔范式（英語：Backus-Naur Form，縮寫同樣為 BNF，也譯为巴科斯-瑙尔范式、巴克斯-诺尔范式），是一种用于表示上下文无关文法的语言，上下文无关文法描述了一类形式语言。它是由约翰·巴科斯（John Backus）和彼得·诺尔（Peter Naur）首先引入的用来描述计算机语言语法的符号集。...

的长度）。CYK算法采用了动态规划的思想。 对于一个任意给定的上下文无关文法，都可以使用CYK算法来计算上述问题，但首先要将该文法转换成乔姆斯基范式。   G = ( V , Σ , S , P ) {\displaystyle ~G=(V,\Sigma ,S,P)} 是一个上下文无关文法 对于任意字符串 w = σ 1 ....

上下文有关语言的泵引理来保证。 3: 语言应当容许有限的跨序列依赖(cross-serial dependencies)，允许在两个任意长子短语之间施加文法协定；上下文无关文法不满足这个条件。要求由与自身相串接的字符串所构成的语言属于适度上下文有关语言在形式上确保了这个条件。 在建立适度上下文有关语言公式化上的一些尝试包括...

两级文法是下列两种形式结构之一： 两级形式语言的形式文法，这种语言是按两个级别来指定的形式语言，比如，字和句两个级别。 用来生成其他形式文法的形式文法[1]（页面存档备份，存于互联网档案馆）。定义次级文法的规则的上下文无关文法可以生成导出文法的规则的一个有效的无限集合。可以生成另一个上下文无关文法...

，拥有更好的运行效率而且减少了程序员的工作量。 1965年，Donald Knuth发明了LR分析器。LR分析器可以在线性时间里分析一个确定的上下文无关文法的输入。但是，最右推导技术所需的分析表需要一个巨大的内存空间，所以在那个内存空间紧缺的年代，LR分析技术被认为是不可行的。 为了解决这个缺点，在1969年，Frank...

bison（Bison意为犎牛；而Yacc与意为牦牛的Yak同音）是一个自由软件，用于自动生成语法分析器程序，实际上可用于所有常见的操作系统。Bison把LALR形式的上下文无关文法描述转换为可做语法分析的C或C++程序。在新近版本中，Bison增加了对GLR语法分析算法的支持。 GNU bison基本兼容Yacc，并做了一些改进。它一般与flex一起使用。...

都不可以是开始符号。 所有的 Chomsky 范式的文法都是上下文无关，反过来，所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。 除了（在文法可能生成空串的时候包括的）可选规则 S → ε 是例外，Chomsky 范式的文法的所有规则都是扩张的，就是说在字符串的整个导出过程中，每...

Form）是表达作为描述计算机编程语言和形式语言的正规方式的上下文无关文法的元语法(metalanguage)符号表示法。它是基本巴科斯范式(BNF)元语法符号表示法的一种扩展。 它最初由尼克劳斯·维尔特开发，最常用的 EBNF 变体由标准，特别是 ISO-14977 所定义。 扩展巴科斯范式是一种表达形式语言文法...

可观察出这种文法没有左递归。 所有上下文无关文法口可以被转换成等价的 Greibach 范式的文法。（某些定义不认可第二种形式的规则，在这种情况下能生成空串的上下文无关文法不能被如此转换。）这可以被用来证明所有上下文无关语言可以被非确定下推自动机所接受。 给定 GNF 的一个文法和长度为 n 的符合这个文法...

树-邻接文法(TAG)是 Aravind Joshi 定义的文法形式化。树-邻接（adjoining）文法在某种意义上类似于上下文无关文法，但是基本的重写单位是树而不是符号。上下文无关文法有把符号重写为其他符号的规则，而树-毗连文法有把树的节点重写为其他树的规则。 TAG...

在上下文無關文法內裡的說法，若一個非终结符號（non-terminal）r有任何直接的文法規則或者透過多個文法規則，推導出的句型（sentential form）其中最左邊的符號 又會出現r，則我們說這個非终结符號r是左遞歸的。 使用類似的方式我們可以定義出某文法本身是左遞歸的。 "一個文法...

的（更加复杂）的不收缩文法。 有容易的过程把任何不收缩文法转换成 Kuroda范式。 已知把任何不收缩文法变换成上下文有关文法或反之的过程。 所以，不收缩文法，Kuroda 范式的文法，和上下文有关文法有同样的表达能力。 更精确地说，不收缩文法精确的描述不包含空串的上下文有关语言，而本质不收缩文法精确的描述上下文有关语言的集合。...

量之间更复杂的关系。因此，生成模型更适用于无监督的任务，如分类和聚类。 典型的生成模型包括： 高斯混合模型和其他混合模型 隐马尔可夫模型 随机上下文无关文法 朴素贝叶斯分类器 AODE分类器 潜在狄利克雷分配模型 受限玻尔兹曼机 如果观测数据是由生成模型中采样的，那么最大化数据似然概率是一个常见的...

LR剖析器是一種由下而上（bottom-up）的上下文無關語法剖析器。LR意指由左（Left）至右處理輸入字串，並以最右邊優先衍生（Right derivation）的推導順序（相對於LL剖析器）建構語法樹。能以此方式剖析的語法稱為LR語法。而在LR(k)這樣的名稱中，k代表的是剖析時所需前瞻符號（lookahead...

內部外部演算法（英語：inside-outside algorithm）是一種重新檢驗隨機上下文無關文法生成機率的方式，由詹姆斯·K·貝克於1979年提出，是一個一般化的向前向後演算法，用來作為隨機上下文無關文法其隱馬爾可夫模型的屬性評估。這種演算法是用來計算某種期望值，舉例來說，可以用來成為最大期...

在理論語言學中，生成文法（英語：generative grammar）是一種嘗試接近句法學（英語：Syntax）的方式 。生成文法嘗試給出一套規則，其能正確的預測，在一個語言中，甚麼樣的詞匯組合能成為正確的句子；而在討論生成文法的同時，這些規則通常也能預測句子中的構詞法。 生成文法...

中的语言，可等效于某些正则语言。因此，每一个上下文无关语言都可等效于某些正则语言。 帕里克定理表明，有些上下文无关语言可能只有歧义语法[需要更深入解释]。这样的语言称为固有歧义语言。从形式文法的角度看，这意味着某些有歧义的上下文无关文法无法转换为明确的上下文无关文法。 Kozen, Dexter. Automata...

嵌入下推自动机或 EPDA 是分析树-邻接文法(TAG)的计算模型。除了不再使用堆栈来存储符号之外，它类似于分析上下文无关文法的下推自动机。它有存储符号的重复堆栈组成的一个栈，这给予了 TAG 在上下文无关文法和上下文有关文法之间的复杂度，或者说是适度上下文有关文法的子集。 EPDA 最初由 K. Vijay-Shanker...

不是上下文無關的上下文有關語言的一個例子是 L = { ap : p 是質數 }。證明它的最容易方式是使用線性有界圖靈機。 两个上下文有关语言的并集、交集和串接也是上下文有关的。 上下文有关语言的补集自身是上下文有关的。 所有上下文无关语言都是上下文有关的。 一个字符串在由任意上下文有关文法...

范式的文法都是单调的，因此生成上下文有关语言。反过来说，所有不生成空串的上下文有关语言都可以被 Kuroda 范式的文法所生成。 巴科斯范式 乔姆斯基范式 Greibach范式 上下文有关文法 形式文法 分析表达式文法 随机上下文无关文法 S.-Y. Kuroda, "Classes of languages and linear-bounded...

附标文法是描述附标语言的形式文法。它们有三个无交集的符号集合: 普通终结符、非终结符和只出现在中间推导中的附标(index)的集合。产生式可以如上下文无关文法那样把一个非终结符替代为终结符和非终结符的字符串，但是它还把非终结符替代为跟随着一个附标的非终结符，把跟随着一个附标的非终结符替代为非终结符。...