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

S 。这种文法规定的语言可以被线性有界非确定图灵机接受。 2-型文法（上下文无关文法）生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。...

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

grammar）：在解析一个字符串的时候，只能有單一确定的語法分析树。据推测，存在上下文无关语言，不能用PEG处理，但尚未得到证实。这个特性使得PEG更适合计算机语言的解析，对于一般的CFG算法（如依尔利算法（英语：Earley parser））的性能可以与之比拟的自然语言就不是很合适。 形式上，一个解析表达文法由以下部分组成： 一个有限的非终结符的集合...

在理论计算机科学中，上下文有关语言是可被上下文有关文法定义的形式语言。它是乔姆斯基谱系中的四类文法之一。它在理论和实践中都是最少使用的。 上下文有关语言的可计算性等价于线性有界非确定图灵机。它是磁带只有 kn 个单元的非确定图灵机，这里的 n 是输入的大小而 k...

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

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

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

在理論計算機科學中，帕里克定理指出，对于上下文无关语言，如果只关心其中每个终止符号出现的次数，而不考虑它们的顺序，那么存在正则语言与其对应。这个定理可用于确定具有给定数量终止符号的字符串是否能为上下文无关语法接受。1961年罗希特·帕里克第一次证明了它，论文于1966年再次发表。 令 Σ = { a...

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

些引理的证明典型的需要计数论证比如鸽笼原理。 两个最重要例子是正则语言的泵引理和上下文无关语言的泵引理。鄂登引理是另一种更强的上下文无关语言的泵引理。 这些引理可以用来确定特定语言不在给定语言类中。但是它们不能被用来确定一个语言在给定类中，因为满足引理是类成员关系的必要条件，但不是充分条件。 泵引理是1961年由...

许多涉及L-systems研究的问题有待解决，比如： 描述所有那些确定的局部连锁的上下文无关L-systems（目前已知完成解决的只有包含两个变量的这一种情况）。 给定一个结构，找出生成此结构的L-systems文法。 维基共享资源上的相关多媒体资源：L系統 David J. Wright's...

如果映射中没有目标比特串是同一映射中不同源符号的目标比特串的前缀，则该代码是前缀码。这意味着符号可以在接收到整个码字后立即解码。此概念的其他常用名称包括无前缀代码、瞬时代码或上下文无关代码。 上一段中的示例映射 M 3 {\displaystyle M_{3}} 不是前缀码，因为我们在读取位串“0”后不知道它是否编码“a”源符...

{\displaystyle \epsilon } -转移的非确定有限自动机。 下推自动机存在“确定”与“非确定”两种形式，两者并不等价。（对有限自动机两者是等价的） 每一个下推自动机都接受一个形式语言。被“非确定下推自动机”接受的语言是上下文无关语言。 如果我们把下推自动机扩展，允许一个有限自动机存取...

语言模型。语言模型对系统所针对的语言进行建模。理论上，包括正则语言，上下文无关文法在内的各种语言模型都可以作为语言模型，但目前各种系统普遍采用的还是基于统计的N元文法及其变体。 解码器。解码器是语音识别系统的核心之一，其任务是对输入的信号，根据声学、语言模型及词典，寻找能够以最大概率输出该信号的词串。...

使用的是缩进还是花括号。这要求词法器保持状态，也就是当前的缩进层级，因而在缩进变更的时候可以检测到，因此这种词法文法不是上下文无关的，INDENT/DEDENT依赖于以前缩进层级的上下文信息。 ABC BOO BuddyScript（英语：BuddyScript） Cobra（英语：Cobra (programming...

acid structure prediction） 有限的假结点的子类。 较新的结构预测技术，如随机上下文无关文法也无法考虑假结结构。 大多数核酸二级结构预测方法都依赖于最近邻热力学模型。给定核苷酸序列，确定最可能结构的常用方法是使用动态规划算法，该算法寻求寻找具有低自由能的结构。...

这意味着无法在物理上构建比通用图灵机更强大的计算机。 存在很多并不图灵完备的语言，比如由正则表达式表示的正则语言，通过有限状态机进行识别。下推自动机和上下文无关文法更强大，但仍不是图灵完备的，他们一般用于在程序编译的初期阶段生成分析树。其他示例包括嵌入在Direct3D和OpenGL扩展名中的像素着色器语言的某些早期版本。[來源請求]...

），如此就使得一種书写对应含义不同的发音。 通过严格的构词法和明确叙述的发音规则，逻辑语大體上达到了上述目标。并且，它的发音规则还有如下特点： 上下文无关：一个书写符号对应于唯一的一类发音形式，无论其在文本中处于什么位置。 严格的等价：对应于书写符号的一类发音形式，无论采用哪一个都是合法的，都被辨认成同一个书写符号。...

在计算机科学和语言学中，语法分析（英語：syntactic analysis，也叫 parsing）是根据某种给定的形式文法对由单词序列（如英语单词序列）构成的输入文本进行分析并确定其语法结构的一种过程。 语法分析器（parser）通常是作为编译器或解释器的组件出现的，它的作用是进行语法检查、并构建...

68的定义使用了阿德里安·范·韦恩加登发明的一种数学形式主义的两级形式文法。van Wijngaarden文法（英语：Van Wijngaarden grammar）使用分别称为“元产生式规则”和“超规则”的两组上下文无关文法规则，生成形成一个可能无限的产生式（英语：Production (computer...

所用之计算模型； 所研究之计算资源的上界。 许多常见的复杂度类皆是基于使用图灵机解决决定性问题时所需时间或空间（内存）的多少来定义的。例如，P类问题包含了所有可由确定型图灵机在多项式时间内解决的问题。当然，也存在基于其他问题类型（如錯誤：語言代碼「Counting problem...

单一的空标签（类似于一个开始标签），无需结束标签。 许多标签是可选的，尤其是那些很常用的段落元素<p>的闭合端标签。HTML浏览器或其他媒介可以从上下文识别出元素的闭合端以及由HTML标准所定义的结构规则。这些规则非常复杂，不是大多数HTML编码人员可以完全理解的。 因此，一个HTML元素的一般形式为：<tag...

些分詞構造中，不定過去時分詞可以有要么時態要么文法體含義。) 假定了這種文法體的區別而非任何實際時態區別是 PIE 的“時態”的最初意義，并且時態區別最初如漢語那樣由副詞方式來指示。但是，似乎在后來的 PIE 中，如希臘語那樣不同的時態已經在特定上下文獲得了時態含義，并在后來的印度-歐洲語言中變為統治性的。...

b, c, ..., x, y, z, x1, x2, ...}，则所有的lambda表达式可以通过下述以BNF范式表达的上下文无关文法描述： <表达式> ::= <标识符> <表达式> ::= (λ<标识符>.<表达式>) <表达式> ::= (<表达式> <表达式>)...

角色图式：这些是关于社会角色的知识，表示特定社会地位中的人们的预期行为集。 上下文图式：其中包含有关情况和行为参数的适当设置的信息。上下文图式中的信息包括对为了实现各自上下文中的目标而要采取的适当行动的预测。信息还包括合理解决问题策略的建议。...

“村”，四个是与服饰有关的词。其中三个服装词具有中朝同源词，但其他四个词仍然“无法解释”。8世纪日本史书《日本书纪》还保留了一个新罗语的句子，通过上下文推测是某种誓言。 《三国史记》、《三国遗事》和中日文献记录了很多新罗的专有名词，包括人名、地名和头衔。这些通常以两种不同的形式给定：一个用汉字记音...